# HG changeset patch
# User Gilles Duboscq <duboscq@ssw.jku.at>
# Date 1340897946 -7200
# Node ID e1d5c642d022dc29d88bbdffa41164582a3b1cb2
# Parent  3d5e2e330ae3ecad055657dbcc9bca75f774fb2e
Started to draft a loop unswitching policy

diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java	Thu Jun 28 17:39:06 2012 +0200
@@ -103,6 +103,8 @@
     public static boolean FullUnroll                         = true;
     public static int     FullUnrollMaxNodes                 = 150; // TODO (gd) tune
     public static boolean LoopUnswitch                       = ____;
+    public static int     LoopUnswitchMaxIncrease            = 50;
+    public static int     LoopUnswitchUncertaintyBoost       = 5;
 
     // debugging settings
     public static int     MethodEndBreakpointGuards          = 0;
diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java	Thu Jun 28 17:39:06 2012 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.graal.compiler.loop;
 
+import java.util.*;
+
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
@@ -137,4 +139,30 @@
     public void setCounted(CountedLoopInfo countedLoopInfo) {
         counted = countedLoopInfo;
     }
+
+    public LoopsData loopsData() {
+        return data;
+    }
+
+    public NodeBitMap nodesInLoopFrom(BeginNode point, BeginNode until) {
+        Collection<BeginNode> blocks = new LinkedList<>();
+        Collection<BeginNode> exits = new LinkedList<>();
+        Queue<Block> work = new LinkedList<>();
+        ControlFlowGraph cfg = loopsData().controlFlowGraph();
+        work.add(cfg.blockFor(point));
+        Block untilBlock = until != null ? cfg.blockFor(until) : null;
+        while (!work.isEmpty()) {
+            Block b = work.remove();
+            if (b == untilBlock) {
+                continue;
+            }
+            if (lirLoop().exits.contains(b)) {
+                exits.add(b.getBeginNode());
+            } else if (lirLoop().blocks.contains(b)) {
+                blocks.add(b.getBeginNode());
+                work.addAll(b.getDominated());
+            }
+        }
+        return LoopFragment.computeNodes(point.graph(), blocks, exits);
+    }
 }
diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java	Thu Jun 28 17:39:06 2012 +0200
@@ -30,7 +30,8 @@
 import com.oracle.graal.lir.cfg.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;
-import com.oracle.graal.nodes.VirtualState.*;
+import com.oracle.graal.nodes.VirtualState.NodeClosure;
+import com.oracle.graal.nodes.VirtualState.VirtualClosure;
 
 
 public abstract class LoopFragment {
@@ -127,14 +128,6 @@
         }
     }
 
-    public static Collection<BeginNode> toHirBlocks(Collection<Block> blocks) {
-        List<BeginNode> hir = new ArrayList<>(blocks.size());
-        for (Block b : blocks) {
-            hir.add(b.getBeginNode());
-        }
-        return hir;
-    }
-
     protected static NodeBitMap computeNodes(Graph graph, Collection<BeginNode> blocks) {
         return computeNodes(graph, blocks, Collections.<BeginNode>emptyList());
     }
@@ -212,13 +205,21 @@
         return false;
     }
 
+    public static Collection<BeginNode> toHirBlocks(Collection<Block> blocks) {
+        List<BeginNode> hir = new ArrayList<>(blocks.size());
+        for (Block b : blocks) {
+            hir.add(b.getBeginNode());
+        }
+        return hir;
+    }
+
     /**
      * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with the original fragment's exits.
      */
     protected void mergeEarlyExits() {
         assert isDuplicate();
         StructuredGraph graph = graph();
-        for (BeginNode earlyExit : toHirBlocks(original().loop().lirLoop().exits)) {
+        for (BeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().lirLoop().exits)) {
             FixedNode next = earlyExit.next();
             if (earlyExit.isDeleted() || !this.contains(earlyExit)) {
                 continue;
diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java	Thu Jun 28 17:39:06 2012 +0200
@@ -22,8 +22,8 @@
  */
 package com.oracle.graal.compiler.loop;
 
+import com.oracle.graal.graph.Graph.DuplicationReplacement;
 import com.oracle.graal.graph.*;
-import com.oracle.graal.graph.Graph.DuplicationReplacement;
 import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.lir.cfg.*;
 
diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopPolicies.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopPolicies.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopPolicies.java	Thu Jun 28 17:39:06 2012 +0200
@@ -23,6 +23,8 @@
 package com.oracle.graal.compiler.loop;
 
 import com.oracle.graal.compiler.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.cfg.*;
 import com.oracle.graal.nodes.*;
 
 
@@ -52,4 +54,19 @@
         // TODO (gd) maybe there should be a may number of unswitching per loop
         return true;
     }
+
+    public static boolean shouldUnswitch(LoopEx loop, IfNode ifNode) {
+        Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(ifNode).getPostdominator();
+        BeginNode postDom = postDomBlock != null ? postDomBlock.getBeginNode() : null;
+        int inTrueBranch = loop.nodesInLoopFrom(ifNode.trueSuccessor(), postDom).cardinality();
+        int inFalseBranch = loop.nodesInLoopFrom(ifNode.falseSuccessor(), postDom).cardinality();
+        int loopTotal = loop.size();
+        int netDiff = loopTotal - (inTrueBranch + inFalseBranch);
+        double uncertainty = (0.5 - Math.abs(ifNode.probability(IfNode.TRUE_EDGE) - 0.5)) * 2;
+        int maxDiff = GraalOptions.LoopUnswitchMaxIncrease + (int) (GraalOptions.LoopUnswitchUncertaintyBoost * loop.loopBegin().loopFrequency() * uncertainty);
+        Debug.log("shouldUnswitch(%s, %s) : delta=%d, max=%d, %.2f%% inside of if", loop, ifNode, netDiff, maxDiff, (double) (inTrueBranch + inFalseBranch) / loopTotal * 100);
+        return netDiff <= maxDiff;
+    }
+
+
 }
diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java	Thu Jun 28 17:39:06 2012 +0200
@@ -35,13 +35,14 @@
 public class LoopsData {
     private Map<Loop, LoopEx> lirLoopToEx = new IdentityHashMap<>();
     private Map<LoopBeginNode, LoopEx> loopBeginToEx = new IdentityHashMap<>();
+    private ControlFlowGraph cfg;
 
     public LoopsData(final StructuredGraph graph) {
 
-        ControlFlowGraph cfg = Debug.scope("ControlFlowGraph", new Callable<ControlFlowGraph>() {
+        cfg = Debug.scope("ControlFlowGraph", new Callable<ControlFlowGraph>() {
             @Override
             public ControlFlowGraph call() throws Exception {
-                return ControlFlowGraph.compute(graph, true, true, true, false);
+                return ControlFlowGraph.compute(graph, true, true, true, true);
             }
         });
         for (Loop lirLoop : cfg.getLoops()) {
@@ -150,4 +151,8 @@
             }
         }
     }
+
+    public ControlFlowGraph controlFlowGraph() {
+        return cfg;
+    }
 }
diff -r 3d5e2e330ae3 -r e1d5c642d022 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformLowPhase.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformLowPhase.java	Thu Jun 28 16:04:37 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformLowPhase.java	Thu Jun 28 17:39:06 2012 +0200
@@ -54,7 +54,7 @@
                     for (LoopEx loop : dataUnswitch.loops()) {
                         if (LoopPolicies.shouldTryUnswitch(loop)) {
                             IfNode ifNode = LoopTransformations.findUnswitchableIf(loop);
-                            if (ifNode != null && !unswitchedDebug.isMarked(ifNode)) {
+                            if (ifNode != null && !unswitchedDebug.isMarked(ifNode) && LoopPolicies.shouldUnswitch(loop, ifNode)) {
                                 unswitchedDebug.mark(ifNode);
                                 Debug.log("Unswitching %s at %s [%f - %f]", loop, ifNode, ifNode.probability(0), ifNode.probability(1));
                                 //LoopTransformations.unswitch(loop, ifNode);