# HG changeset patch # User Gilles Duboscq # Date 1382026685 -7200 # Node ID 45daf0d65522436a2d7799a2d8f64cc216bb6c3e # Parent 47200418768d752d43967412397294452ca16b74 Replace EliminatePartiallyRedundantGuardsPhase with OptimizeGuardAnchors * OptimizeGuardAnchors implements optimization at control split in a more efficient way * OptimizeGuardAnchors ensure Guards have their optimal anchor point *** OptimizeGuardAnchors header diff -r 47200418768d -r 45daf0d65522 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ReadAfterCheckCastTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ReadAfterCheckCastTest.java Thu Oct 17 18:18:05 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ReadAfterCheckCastTest.java Thu Oct 17 18:18:05 2013 +0200 @@ -86,7 +86,7 @@ PhaseContext context = new PhaseContext(getProviders(), new Assumptions(false)); new LoweringPhase(new CanonicalizerPhase(true)).apply(graph, context); new FloatingReadPhase().apply(graph); - new EliminatePartiallyRedundantGuardsPhase(true, false).apply(graph); + new OptimizeGuardAnchors().apply(graph); new ReadEliminationPhase().apply(graph); new CanonicalizerPhase(true).apply(graph, context); diff -r 47200418768d -r 45daf0d65522 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/MidTier.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/MidTier.java Thu Oct 17 18:18:05 2013 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/MidTier.java Thu Oct 17 18:18:05 2013 +0200 @@ -64,7 +64,7 @@ } if (OptEliminatePartiallyRedundantGuards.getValue()) { - appendPhase(new EliminatePartiallyRedundantGuardsPhase(false, true)); + appendPhase(new OptimizeGuardAnchors()); } if (ConditionalElimination.getValue() && OptCanonicalizer.getValue()) { @@ -72,7 +72,7 @@ } if (OptEliminatePartiallyRedundantGuards.getValue()) { - appendPhase(new EliminatePartiallyRedundantGuardsPhase(true, true)); + appendPhase(new OptimizeGuardAnchors()); } if (OptCanonicalizer.getValue()) { diff -r 47200418768d -r 45daf0d65522 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Thu Oct 17 18:18:05 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Thu Oct 17 18:18:05 2013 +0200 @@ -22,13 +22,14 @@ */ package com.oracle.graal.nodes; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.type.*; /** * The {@code ControlSplitNode} is a base class for all instructions that split the control flow * (ie. have more than one successor). */ -public abstract class ControlSplitNode extends FixedNode { +public abstract class ControlSplitNode extends FixedNode implements IterableNodeType { public ControlSplitNode(Stamp stamp) { super(stamp); diff -r 47200418768d -r 45daf0d65522 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Thu Oct 17 18:18:05 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Thu Oct 17 18:18:05 2013 +0200 @@ -32,7 +32,7 @@ import com.oracle.graal.nodes.util.*; @NodeInfo(nameTemplate = "Invoke!#{p#targetMethod/s}") -public class InvokeWithExceptionNode extends ControlSplitNode implements IterableNodeType, Invoke, MemoryCheckpoint.Single, LIRLowerable { +public class InvokeWithExceptionNode extends ControlSplitNode implements Invoke, MemoryCheckpoint.Single, LIRLowerable { private static final double EXCEPTION_PROBA = 1e-5; diff -r 47200418768d -r 45daf0d65522 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/EliminatePartiallyRedundantGuardsPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/EliminatePartiallyRedundantGuardsPhase.java Thu Oct 17 18:18:05 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,193 +0,0 @@ -/* - * 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.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 final boolean eliminateAtSplit; - private final boolean eliminateAtMerge; - - public EliminatePartiallyRedundantGuardsPhase(boolean eliminateAtSplit, boolean eliminateAtMerge) { - assert eliminateAtMerge || eliminateAtSplit; - this.eliminateAtSplit = eliminateAtSplit; - this.eliminateAtMerge = eliminateAtMerge; - } - - private static class Condition { - - final LogicNode conditionNode; - final boolean negated; - - public Condition(LogicNode 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; - if (eliminateAtMerge) { - for (MergeNode merge : graph.getNodes(MergeNode.class)) { - hits |= eliminateAtMerge(merge); - } - } - if (eliminateAtSplit) { - 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 hits = new LinkedList<>(); - for (GuardNode guard : merge.guards()) { - for (AbstractEndNode end : merge.forwardEnds()) { - AbstractBeginNode begin = AbstractBeginNode.prevBegin(end); - boolean found = false; - for (GuardNode predecessorGuard : begin.guards()) { - 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.addWithoutUnique(new PhiNode(PhiType.Guard, merge, null)); - for (AbstractEndNode otherEnd : merge.forwardEnds()) { - phi.addInput(graph.unique(new GuardNode(guard.condition(), AbstractBeginNode.prevBegin(otherEnd), guard.reason(), guard.action(), guard.negated()))); - } - guard.replaceAndDelete(phi); - metricPRGuardsEliminatedAtMerge.increment(); - } - return !hits.isEmpty(); - } - - private static boolean eliminateAtControlSplit(ControlSplitNode controlSplit) { - Map> conditionToGuard = new HashMap<>(); - for (Node successor : controlSplit.successors()) { - AbstractBeginNode begin = (AbstractBeginNode) successor; - for (GuardNode guard : begin.guards()) { - Condition condition = new Condition(guard.condition(), guard.negated()); - Collection guards = conditionToGuard.get(condition); - if (guards == null) { - guards = new LinkedList<>(); - conditionToGuard.put(condition, guards); - } - guards.add(guard); - } - } - - boolean hits = false; - for (Entry> entry : conditionToGuard.entrySet()) { - Collection guards = entry.getValue(); - if (guards.size() < 2) { - continue; - } - DeoptimizationReason reason = null; - DeoptimizationAction action = DeoptimizationAction.None; - Set begins = new HashSet<>(3); - for (GuardNode guard : guards) { - AbstractBeginNode begin = (AbstractBeginNode) guard.getGuard(); - 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 (begins.size() == controlSplit.successors().count()) { - hits = true; - Condition condition = entry.getKey(); - GuardNode newGuard = controlSplit.graph().unique(new GuardNode(condition.conditionNode, AbstractBeginNode.prevBegin(controlSplit), reason, action, condition.negated)); - for (GuardNode guard : guards) { - guard.replaceAndDelete(newGuard); - metricPRGuardsEliminatedAtSplit.increment(); - } - } - } - return hits; - } -} diff -r 47200418768d -r 45daf0d65522 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/OptimizeGuardAnchors.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/OptimizeGuardAnchors.java Thu Oct 17 18:18:05 2013 +0200 @@ -0,0 +1,136 @@ +/* + * Copyright (c) 2013, 2013, 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 com.oracle.graal.debug.*; +import com.oracle.graal.graph.NodeClass.NodeClassIterator; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.phases.*; + +public class OptimizeGuardAnchors extends Phase { + private static final DebugMetric metricGuardsAnchorOptimized = Debug.metric("GuardsAnchorOptimized"); + private static final DebugMetric metricGuardsOptimizedAtSplit = Debug.metric("GuardsOptimizedAtSplit"); + + private static class LazyCFG { + private ControlFlowGraph cfg; + private StructuredGraph graph; + + public LazyCFG(StructuredGraph graph) { + this.graph = graph; + } + + public ControlFlowGraph get() { + if (cfg == null) { + cfg = ControlFlowGraph.compute(graph, true, false, true, true); + } + return cfg; + } + } + + @Override + protected void run(StructuredGraph graph) { + LazyCFG cfg = new LazyCFG(graph); + for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.class)) { + if (!(begin instanceof StartNode || begin.predecessor() instanceof ControlSplitNode)) { + NodeIterable guards = begin.guards(); + if (guards.isNotEmpty()) { + AbstractBeginNode newAnchor = computeOptimalAnchor(cfg.get(), begin); + // newAnchor == begin is possible because postdominator computation assumes that + // loops never end + if (newAnchor != begin) { + for (GuardNode guard : guards.snapshot()) { + guard.setGuard(newAnchor); + } + metricGuardsAnchorOptimized.increment(); + } + } + } + } + for (ControlSplitNode controlSplit : graph.getNodes(ControlSplitNode.class)) { + otpimizeAtControlSplit(controlSplit, cfg); + } + } + + private static AbstractBeginNode computeOptimalAnchor(ControlFlowGraph cfg, AbstractBeginNode begin) { + Block anchor = cfg.blockFor(begin); + while (anchor.getDominator() != null && anchor.getDominator().getPostdominator() == anchor) { + anchor = anchor.getDominator(); + } + return anchor.getBeginNode(); + } + + private static void otpimizeAtControlSplit(ControlSplitNode controlSplit, LazyCFG cfg) { + AbstractBeginNode successor = findMinimumUsagesSuccessor(controlSplit); + int successorCount = controlSplit.successors().count(); + List otherGuards = new ArrayList<>(successorCount - 1); + for (GuardNode guard : successor.guards().snapshot()) { + if (guard.condition().usages().count() < successorCount) { + continue; + } + + for (GuardNode conditonGuard : guard.condition().usages().filter(GuardNode.class)) { + if (conditonGuard != guard) { + GuardingNode conditonGuardAnchor = conditonGuard.getGuard(); + if (conditonGuardAnchor.asNode().predecessor() == controlSplit && compatibleGuards(guard, conditonGuard)) { + otherGuards.add(conditonGuard); + } + } + } + + if (otherGuards.size() == successorCount - 1) { + AbstractBeginNode anchor = computeOptimalAnchor(cfg.get(), AbstractBeginNode.prevBegin(controlSplit)); + GuardNode newGuard = controlSplit.graph().unique(new GuardNode(guard.condition(), anchor, guard.reason(), guard.action(), guard.negated())); + for (GuardNode otherGuard : otherGuards) { + otherGuard.replaceAndDelete(newGuard); + } + guard.replaceAndDelete(newGuard); + metricGuardsOptimizedAtSplit.increment(); + } + otherGuards.clear(); + } + } + + private static boolean compatibleGuards(GuardNode guard, GuardNode conditonGuard) { + return conditonGuard.negated() == guard.negated() && conditonGuard.action() == guard.action() && conditonGuard.reason() == guard.reason(); + } + + private static AbstractBeginNode findMinimumUsagesSuccessor(ControlSplitNode controlSplit) { + NodeClassIterator successors = controlSplit.successors().iterator(); + AbstractBeginNode min = (AbstractBeginNode) successors.next(); + int minUsages = min.usages().count(); + while (successors.hasNext()) { + AbstractBeginNode successor = (AbstractBeginNode) successors.next(); + int count = successor.usages().count(); + if (count < minUsages) { + minUsages = count; + min = successor; + } + } + return min; + } +}