# HG changeset patch # User Tom Rodriguez # Date 1406680822 25200 # Node ID c164a505fc2347b1537acf90ed9344ccbc6d6153 # Parent 29404eec7ced1e0ca5588f13f1fa86f697c40dde Properly handle multiple copies of the same test when unswitching diff -r 29404eec7ced -r c164a505fc23 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Tue Jul 29 17:40:15 2014 -0700 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Tue Jul 29 17:40:22 2014 -0700 @@ -24,6 +24,7 @@ import static com.oracle.graal.compiler.common.GraalOptions.*; +import java.util.*; import java.util.function.*; import com.oracle.graal.debug.*; @@ -63,25 +64,27 @@ return loop.loopBegin().unswitches() <= LoopMaxUnswitch.getValue(); } - public static boolean shouldUnswitch(LoopEx loop, ControlSplitNode controlSplit) { - Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(controlSplit).getPostdominator(); - BeginNode postDom = postDomBlock != null ? postDomBlock.getBeginNode() : null; + public static boolean shouldUnswitch(LoopEx loop, List controlSplits) { int loopTotal = loop.size(); int inBranchTotal = 0; double maxProbability = 0; - for (Node successor : controlSplit.successors()) { - BeginNode branch = (BeginNode) successor; - // this may count twice because of fall-through in switches - inBranchTotal += loop.nodesInLoopFrom(branch, postDom).count(); - double probability = controlSplit.probability(branch); - if (probability > maxProbability) { - maxProbability = probability; + for (ControlSplitNode controlSplit : controlSplits) { + Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(controlSplit).getPostdominator(); + BeginNode postDom = postDomBlock != null ? postDomBlock.getBeginNode() : null; + for (Node successor : controlSplit.successors()) { + BeginNode branch = (BeginNode) successor; + // this may count twice because of fall-through in switches + inBranchTotal += loop.nodesInLoopFrom(branch, postDom).count(); + double probability = controlSplit.probability(branch); + if (probability > maxProbability) { + maxProbability = probability; + } } } int netDiff = loopTotal - (inBranchTotal); double uncertainty = 1 - maxProbability; int maxDiff = LoopUnswitchMaxIncrease.getValue() + (int) (LoopUnswitchUncertaintyBoost.getValue() * loop.loopBegin().loopFrequency() * uncertainty); - Debug.log("shouldUnswitch(%s, %s) : delta=%d, max=%d, %.2f%% inside of branches", loop, controlSplit, netDiff, maxDiff, (double) (inBranchTotal) / loopTotal * 100); + Debug.log("shouldUnswitch(%s, %s) : delta=%d, max=%d, %.2f%% inside of branches", loop, controlSplits, netDiff, maxDiff, (double) (inBranchTotal) / loopTotal * 100); return netDiff <= maxDiff; } diff -r 29404eec7ced -r c164a505fc23 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java Tue Jul 29 17:40:15 2014 -0700 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java Tue Jul 29 17:40:22 2014 -0700 @@ -24,6 +24,8 @@ import static com.oracle.graal.compiler.common.GraalOptions.*; +import java.util.*; + import com.oracle.graal.api.code.*; import com.oracle.graal.graph.Graph.Mark; import com.oracle.graal.graph.*; @@ -71,36 +73,53 @@ } } - public static void unswitch(LoopEx loop, ControlSplitNode controlSplitNode) { + public static void unswitch(LoopEx loop, List controlSplitNodeSet) { + ControlSplitNode firstNode = controlSplitNodeSet.iterator().next(); LoopFragmentWhole originalLoop = loop.whole(); + StructuredGraph graph = firstNode.graph(); + // create new control split out of loop - ControlSplitNode newControlSplit = (ControlSplitNode) controlSplitNode.copyWithInputs(); + ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs(); originalLoop.entryPoint().replaceAtPredecessor(newControlSplit); - NodeClassIterator successors = controlSplitNode.successors().iterator(); + /* + * The code below assumes that all of the control split nodes have the same successor + * structure, which should have been enforced by findUnswitchable. + */ + NodeClassIterator successors = firstNode.successors().iterator(); assert successors.hasNext(); // original loop is used as first successor Position firstPosition = successors.nextPosition(); - NodeClass controlSplitClass = controlSplitNode.getNodeClass(); + NodeClass controlSplitClass = firstNode.getNodeClass(); BeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint()); controlSplitClass.set(newControlSplit, firstPosition, originalLoopBegin); - StructuredGraph graph = controlSplitNode.graph(); while (successors.hasNext()) { Position position = successors.nextPosition(); - // create a new loop duplicate, connect it and simplify it + // create a new loop duplicate and connect it. LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); BeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint()); controlSplitClass.set(newControlSplit, position, newBegin); - ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode); - BeginNode survivingSuccessor = (BeginNode) controlSplitClass.get(duplicatedControlSplit, position); - survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin); - graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor); + + // For each cloned ControlSplitNode, simplify the proper path + for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { + ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode); + if (duplicatedControlSplit.isAlive()) { + BeginNode survivingSuccessor = (BeginNode) controlSplitClass.get(duplicatedControlSplit, position); + survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin); + graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor); + } + } } // original loop is simplified last to avoid deleting controlSplitNode too early - BeginNode survivingSuccessor = (BeginNode) controlSplitClass.get(controlSplitNode, firstPosition); - survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin); - graph.removeSplitPropagate(controlSplitNode, survivingSuccessor); + for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { + if (controlSplitNode.isAlive()) { + BeginNode survivingSuccessor = (BeginNode) controlSplitClass.get(controlSplitNode, firstPosition); + survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin); + graph.removeSplitPropagate(controlSplitNode, survivingSuccessor); + } + } + // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) } @@ -125,17 +144,36 @@ } } - public static ControlSplitNode findUnswitchable(LoopEx loop) { + public static List findUnswitchable(LoopEx loop) { + List controls = null; + ValueNode invariantValue = null; for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { if (loop.isOutsideLoop(ifNode.condition())) { - return ifNode; + if (controls == null) { + invariantValue = ifNode.condition(); + controls = new ArrayList<>(); + controls.add(ifNode); + } else if (ifNode.condition() == invariantValue) { + controls.add(ifNode); + } } } - for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) { - if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) { - return switchNode; + if (controls == null) { + SwitchNode firstSwitch = null; + for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) { + if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) { + if (controls == null) { + firstSwitch = switchNode; + invariantValue = switchNode.value(); + controls = new ArrayList<>(); + controls.add(switchNode); + } else if (switchNode.value() == invariantValue && firstSwitch.equalKeys(switchNode)) { + // Only collect switches which test the same values in the same order + controls.add(switchNode); + } + } } } - return null; + return controls; } } diff -r 29404eec7ced -r c164a505fc23 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformLowPhase.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformLowPhase.java Tue Jul 29 17:40:15 2014 -0700 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformLowPhase.java Tue Jul 29 17:40:22 2014 -0700 @@ -24,6 +24,8 @@ import static com.oracle.graal.compiler.common.GraalOptions.*; +import java.util.*; + import com.oracle.graal.debug.*; import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.graph.NodeClass.NodeClassIterator; @@ -34,6 +36,7 @@ public class LoopTransformLowPhase extends Phase { private static final DebugMetric UNSWITCHED = Debug.metric("Unswitched"); + private static final DebugMetric UNSWITCH_CANDIDATES = Debug.metric("UnswitchCandidates"); @Override protected void run(StructuredGraph graph) { @@ -56,16 +59,18 @@ final LoopsData dataUnswitch = new LoopsData(graph); for (LoopEx loop : dataUnswitch.loops()) { if (LoopPolicies.shouldTryUnswitch(loop)) { - ControlSplitNode controlSplit = LoopTransformations.findUnswitchable(loop); - if (controlSplit != null && LoopPolicies.shouldUnswitch(loop, controlSplit)) { - if (Debug.isLogEnabled()) { - logUnswitch(loop, controlSplit); + List controlSplits = LoopTransformations.findUnswitchable(loop); + if (controlSplits != null) { + UNSWITCH_CANDIDATES.increment(); + if (LoopPolicies.shouldUnswitch(loop, controlSplits)) { + if (Debug.isLogEnabled()) { + logUnswitch(loop, controlSplits); + } + LoopTransformations.unswitch(loop, controlSplits); + UNSWITCHED.increment(); + unswitched = true; + break; } - LoopTransformations.unswitch(loop, controlSplit); - UNSWITCHED.increment(); - Debug.dump(graph, "After unswitch %s", loop); - unswitched = true; - break; } } } @@ -74,17 +79,20 @@ } } - private static void logUnswitch(LoopEx loop, ControlSplitNode controlSplit) { + private static void logUnswitch(LoopEx loop, List controlSplits) { StringBuilder sb = new StringBuilder("Unswitching "); - sb.append(loop).append(" at ").append(controlSplit).append(" ["); - NodeClassIterator it = controlSplit.successors().iterator(); - while (it.hasNext()) { - sb.append(controlSplit.probability((BeginNode) it.next())); - if (it.hasNext()) { - sb.append(", "); + sb.append(loop).append(" at "); + for (ControlSplitNode controlSplit : controlSplits) { + sb.append(controlSplit).append(" ["); + NodeClassIterator it = controlSplit.successors().iterator(); + while (it.hasNext()) { + sb.append(controlSplit.probability((BeginNode) it.next())); + if (it.hasNext()) { + sb.append(", "); + } } + sb.append("]"); } - sb.append("]"); Debug.log("%s", sb); } } diff -r 29404eec7ced -r c164a505fc23 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java Tue Jul 29 17:40:15 2014 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java Tue Jul 29 17:40:22 2014 -0700 @@ -42,7 +42,7 @@ /** * Constructs a integer switch instruction. The keyProbabilities and keySuccessors array contain * key.length + 1 entries, the last entry describes the default (fall through) case. - * + * * @param value the instruction producing the value being switched on * @param successors the list of successors * @param keys the sorted list of keys @@ -68,7 +68,7 @@ /** * Constructs a integer switch instruction. The keyProbabilities and keySuccessors array contain * key.length + 1 entries, the last entry describes the default (fall through) case. - * + * * @param value the instruction producing the value being switched on * @param successorCount the number of successors * @param keys the sorted list of keys @@ -86,7 +86,7 @@ /** * Gets the key at the specified index. - * + * * @param i the index * @return the key at that index */ @@ -101,6 +101,15 @@ } @Override + public boolean equalKeys(SwitchNode switchNode) { + if (!(switchNode instanceof IntegerSwitchNode)) { + return false; + } + IntegerSwitchNode other = (IntegerSwitchNode) switchNode; + return Arrays.equals(keys, other.keys); + } + + @Override public void generate(NodeLIRBuilderTool gen) { gen.emitSwitch(this); } diff -r 29404eec7ced -r c164a505fc23 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Tue Jul 29 17:40:15 2014 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Tue Jul 29 17:40:22 2014 -0700 @@ -104,6 +104,11 @@ public abstract Constant keyAt(int i); /** + * Returns true if the switch has the same keys in the same order as this switch. + */ + public abstract boolean equalKeys(SwitchNode switchNode); + + /** * Returns the index of the successor belonging to the key at the specified index. */ public int keySuccessorIndex(int i) {