Mercurial > hg > truffle

changeset 16617:c164a505fc23

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Properly handle multiple copies of the same test when unswitching
author Tom Rodriguez <tom.rodriguez@oracle.com>
date Tue, 29 Jul 2014 17:40:22 -0700
parents 29404eec7ced
children 0b0726730fbd
files graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformLowPhase.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java
diffstat 5 files changed, 113 insertions(+), 50 deletions(-) [+]
line wrap: on
line diff
--- 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<ControlSplitNode> 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;
     }
 
--- 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<ControlSplitNode> 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<ControlSplitNode> findUnswitchable(LoopEx loop) {
+        List<ControlSplitNode> 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;
     }
 }
--- 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<ControlSplitNode> 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<ControlSplitNode> 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);
     }
 }
--- 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);
     }
--- 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) {