Mercurial > hg > truffle
changeset 6669:7f6823cc5d26
Simple elimination of some partially redundant guards
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Tue, 06 Nov 2012 14:26:30 +0100 |
parents | eaca0ecbf0ca |
children | 81ad987772f6 a52320a6bbda |
files | graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/EliminatePartiallyRedundantGuardsPhase.java |
diffstat | 5 files changed, 211 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Nov 06 13:59:07 2012 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Nov 06 14:26:30 2012 +0100 @@ -189,6 +189,8 @@ new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } + new EliminatePartiallyRedundantGuardsPhase().apply(graph); + if (GraalOptions.CheckCastElimination && GraalOptions.OptCanonicalizer) { new IterativeConditionalEliminationPhase(target, runtime, assumptions).apply(graph); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Tue Nov 06 13:59:07 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Tue Nov 06 14:26:30 2012 +0100 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.type.*; /** @@ -61,7 +62,7 @@ branchProbability[successorIndex] = x; } - public Iterable<BeginNode> blockSuccessors() { + public NodeIterable<BeginNode> blockSuccessors() { return blockSuccessors; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java Tue Nov 06 13:59:07 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java Tue Nov 06 14:26:30 2012 +0100 @@ -49,6 +49,15 @@ private boolean negated; private final long leafGraphId; + public GuardNode(BooleanNode condition, FixedNode anchor, DeoptimizationReason reason, DeoptimizationAction action, boolean negated, long leafGraphId) { + super(StampFactory.dependency(), anchor); + this.condition = condition; + this.reason = reason; + this.action = action; + this.negated = negated; + this.leafGraphId = leafGraphId; + } + /** * The instruction that produces the tested boolean value. */ @@ -73,13 +82,8 @@ return action; } - public GuardNode(BooleanNode condition, FixedNode anchor, DeoptimizationReason reason, DeoptimizationAction action, boolean negated, long leafGraphId) { - super(StampFactory.dependency(), anchor); - this.condition = condition; - this.reason = reason; - this.action = action; - this.negated = negated; - this.leafGraphId = leafGraphId; + public long getLeafGraphId() { + return leafGraphId; } @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Tue Nov 06 13:59:07 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Tue Nov 06 14:26:30 2012 +0100 @@ -37,6 +37,7 @@ public static enum PhiType { Value(null), // normal value phis + Guard(StampFactory.dependency()), Memory(StampFactory.dependency()); public final Stamp stamp;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/EliminatePartiallyRedundantGuardsPhase.java Tue Nov 06 14:26:30 2012 +0100 @@ -0,0 +1,195 @@ +/* + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.phases.common; + +import java.util.*; +import java.util.Map.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.phases.*; + + +public class EliminatePartiallyRedundantGuardsPhase extends Phase { + + private static final DebugMetric metricPRGuardsEliminatedAtMerge = Debug.metric("PRGuardsEliminatedAtMerge"); + private static final DebugMetric metricPRGuardsEliminatedAtSplit = Debug.metric("PRGuardsEliminatedAtSplit"); + + private static class Condition { + final BooleanNode conditionNode; + final boolean negated; + public Condition(BooleanNode conditionNode, boolean negated) { + this.conditionNode = conditionNode; + this.negated = negated; + } + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((conditionNode == null) ? 0 : conditionNode.hashCode()); + result = prime * result + (negated ? 1231 : 1237); + return result; + } + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj == null) { + return false; + } + if (getClass() != obj.getClass()) { + return false; + } + Condition other = (Condition) obj; + if (conditionNode == null) { + if (other.conditionNode != null) { + return false; + } + } else if (!conditionNode.equals(other.conditionNode)) { + return false; + } + if (negated != other.negated) { + return false; + } + return true; + } + } + + @Override + protected void run(StructuredGraph graph) { + boolean hits; + do { + hits = false; + for (MergeNode merge : graph.getNodes(MergeNode.class)) { + hits |= eliminateAtMerge(merge); + } + for (ControlSplitNode controlSplit : graph.getNodes().filter(ControlSplitNode.class)) { + hits |= eliminateAtControlSplit(controlSplit); + } + } while(hits); + } + + private static boolean eliminateAtMerge(MergeNode merge) { + if (merge.forwardEndCount() < 2) { + return false; + } + Collection<GuardNode> hits = new LinkedList<>(); + for (GuardNode guard : merge.guards()) { + if (guard.dependencies().size() != 1) { + continue; + } + for (EndNode end : merge.forwardEnds()) { + BeginNode begin = BeginNode.prevBegin(end); + boolean found = false; + for (GuardNode predecessorGuard : begin.guards()) { + if (predecessorGuard.dependencies().size() != 1) { + continue; + } + if (guard.condition() == predecessorGuard.condition() && guard.negated() == predecessorGuard.negated()) { + hits.add(guard); + found = true; + break; + } + } + if (found) { + break; + } + } + } + Graph graph = merge.graph(); + for (GuardNode guard : hits) { + PhiNode phi = graph.add(new PhiNode(PhiType.Guard, merge)); + for (EndNode otherEnd : merge.forwardEnds()) { + phi.addInput(graph.unique(new GuardNode(guard.condition(), BeginNode.prevBegin(otherEnd), guard.reason(), guard.action(), guard.negated(), guard.getLeafGraphId()))); + } + guard.replaceAndDelete(phi); + metricPRGuardsEliminatedAtMerge.increment(); + } + return !hits.isEmpty(); + } + + private static boolean eliminateAtControlSplit(ControlSplitNode controlSplit) { + Map<Condition, Collection<GuardNode>> conditionToGuard = new HashMap<>(); + for (BeginNode begin : controlSplit.blockSuccessors()) { + for (GuardNode guard : begin.guards()) { + if (guard.dependencies().size() != 1) { + continue; + } + Condition condition = new Condition(guard.condition(), guard.negated()); + Collection<GuardNode> guards = conditionToGuard.get(condition); + if (guards == null) { + guards = new LinkedList<>(); + conditionToGuard.put(condition, guards); + } + guards.add(guard); + } + } + + boolean hits = false; + for (Entry<Condition, Collection<GuardNode>> entry : conditionToGuard.entrySet()) { + Collection<GuardNode> guards = entry.getValue(); + if (guards.size() < 2) { + continue; + } + DeoptimizationReason reason = null; + DeoptimizationAction action = DeoptimizationAction.None; + long leafGraphId = -1; + Set<BeginNode> begins = new HashSet<>(3); + for (GuardNode guard : guards) { + BeginNode begin = (BeginNode) guard.dependencies().first(); + begins.add(begin); + if (guard.action().ordinal() > action.ordinal()) { + action = guard.action(); + } + if (reason == null) { + reason = guard.reason(); + } else if (reason != guard.reason()) { + reason = DeoptimizationReason.None; + } + if (leafGraphId == -1) { + leafGraphId = guard.getLeafGraphId(); + } else if (leafGraphId != guard.getLeafGraphId()) { + leafGraphId = -1; + } + } + if (leafGraphId < 0) { + continue; + } + if (begins.size() == controlSplit.blockSuccessors().count()) { + hits = true; + Condition condition = entry.getKey(); + GuardNode newGuard = controlSplit.graph().unique(new GuardNode(condition.conditionNode, BeginNode.prevBegin(controlSplit), reason, action, condition.negated, leafGraphId)); + for (GuardNode guard : guards) { + guard.replaceAndDelete(newGuard); + metricPRGuardsEliminatedAtSplit.increment(); + } + } + } + return hits; + } +}