Mercurial > hg > truffle

changeset 3199:494f0ff09b14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
More precise inOrBefore, make both inOrBefore and inOrAfter accessible on Loop, compute inOrAfter, inOrBefore and full loop nodes only if needed
author Gilles Duboscq <gilles.duboscq@oracle.com>
date Fri, 08 Jul 2011 13:38:38 +0200
parents adfd999fff7d
children 536b02e3cd2b
files graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java
diffstat 3 files changed, 136 insertions(+), 23 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java	Thu Jul 07 18:21:30 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java	Fri Jul 08 13:38:38 2011 +0200
@@ -74,4 +74,9 @@
     public Iterable< ? extends Node> dataUsages() {
         return Collections.emptyList();
     }
+
+    @Override
+    public Iterable< ? extends Node> cfgSuccessors() {
+        return Arrays.asList(this.merge());
+    }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Thu Jul 07 18:21:30 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Fri Jul 08 13:38:38 2011 +0200
@@ -26,6 +26,7 @@
 
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.compiler.ir.*;
+import com.oracle.max.graal.compiler.observer.*;
 import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.compiler.util.LoopUtil.Loop;
 import com.oracle.max.graal.compiler.value.*;
@@ -43,6 +44,15 @@
         if (GraalOptions.LoopPeeling) {
 peeling:
             for (Loop loop : loops) {
+                GraalCompilation compilation = GraalCompilation.compilation();
+                if (compilation.compiler.isObserved()) {
+                    Map<String, Object> debug = new HashMap<String, Object>();
+                    debug.put("loopExits", loop.exits());
+                    debug.put("inOrBefore", loop.inOrBefore());
+                    debug.put("inOrAfter", loop.inOrAfter());
+                    debug.put("nodes", loop.nodes());
+                    compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Loop #" + loop.loopBegin().id(), graph, true, false, debug));
+                }
                 //System.out.println("Peel loop : " + loop.loopBegin());
                 for (Node exit : loop.exits()) {
                     if (!(exit instanceof StateSplit) || ((StateSplit) exit).stateAfter() == null) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Thu Jul 07 18:21:30 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Fri Jul 08 13:38:38 2011 +0200
@@ -39,12 +39,15 @@
 
     public static class Loop {
         private final LoopBegin loopBegin;
-        private NodeBitMap nodes;
+        private NodeBitMap cfgNodes;
         private Loop parent;
         private NodeBitMap exits;
+        private NodeBitMap inOrBefore;
+        private NodeBitMap inOrAfter;
+        private NodeBitMap nodes;
         public Loop(LoopBegin loopBegin, NodeBitMap nodes, NodeBitMap exits) {
             this.loopBegin = loopBegin;
-            this.nodes = nodes;
+            this.cfgNodes = nodes;
             this.exits = exits;
         }
 
@@ -52,7 +55,16 @@
             return loopBegin;
         }
 
+        public NodeBitMap cfgNodes() {
+            return cfgNodes;
+        }
+
         public NodeBitMap nodes() {
+            if (nodes == null) {
+                nodes = loopBegin().graph().createNodeBitMap();
+                nodes.setUnion(inOrAfter());
+                nodes.setIntersect(inOrBefore());
+            }
             return nodes;
         }
 
@@ -71,6 +83,31 @@
         public boolean isChild(Loop loop) {
             return loop.parent != null && (loop.parent == this || loop.parent.isChild(this));
         }
+
+        public NodeBitMap inOrAfter() {
+            if (inOrAfter == null) {
+                inOrAfter = LoopUtil.inOrAfter(this);
+            }
+            return inOrAfter;
+        }
+
+        public NodeBitMap inOrBefore() {
+            if (inOrBefore == null) {
+                inOrBefore = LoopUtil.inOrBefore(this, inOrAfter());
+            }
+            return inOrBefore;
+        }
+
+        public void invalidateCached() {
+            inOrAfter = null;
+            inOrBefore = null;
+            nodes = null;
+        }
+
+        @Override
+        public String toString() {
+            return "Loop #" + loopBegin().id();
+        }
     }
 
     private static class PeelingResult {
@@ -97,14 +134,15 @@
     public static List<Loop> computeLoops(Graph graph) {
         List<Loop> loops = new LinkedList<LoopUtil.Loop>();
         for (LoopBegin loopBegin : graph.getNodes(LoopBegin.class)) {
-            NodeBitMap nodes = computeLoopNodes(loopBegin);
-            NodeBitMap exits = computeLoopExits(loopBegin, nodes);
-            loops.add(new Loop(loopBegin, nodes, exits));
+            NodeBitMap cfgNodes = markUpCFG(loopBegin, loopBegin.loopEnd()); // computeLoopNodes(loopBegin);
+            cfgNodes.mark(loopBegin);
+            NodeBitMap exits = computeLoopExits(loopBegin, cfgNodes);
+            loops.add(new Loop(loopBegin, cfgNodes, exits));
         }
         for (Loop loop : loops) {
             for (Loop other : loops) {
-                if (other != loop && other.nodes().isMarked(loop.loopBegin())) {
-                    if (loop.parent() == null || loop.parent().nodes().isMarked(other.loopBegin())) {
+                if (other != loop && other.cfgNodes().isMarked(loop.loopBegin())) {
+                    if (loop.parent() == null || loop.parent().cfgNodes().isMarked(other.loopBegin())) {
                         loop.setParent(other);
                     }
                 }
@@ -113,13 +151,13 @@
         return loops;
     }
 
-    public static NodeBitMap computeLoopExits(LoopBegin loopBegin, NodeBitMap nodes) {
+    public static NodeBitMap computeLoopExits(LoopBegin loopBegin, NodeBitMap cfgNodes) {
         Graph graph = loopBegin.graph();
         NodeBitMap exits = graph.createNodeBitMap();
-        for (Node n : markUpCFG(loopBegin, loopBegin.loopEnd())) {
+        for (Node n : cfgNodes) {
             if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
                 for (Node sux : n.cfgSuccessors()) {
-                    if (!nodes.isMarked(sux) && sux instanceof FixedNode) {
+                    if (!cfgNodes.isMarked(sux) && sux instanceof FixedNode) {
                         exits.mark(sux);
                     }
                 }
@@ -187,7 +225,9 @@
             }
             if (n instanceof Merge) { //add phis & counters
                 for (Node usage : n.dataUsages()) {
-                    workData2.add(usage);
+                    if (!(usage instanceof LoopEnd)) {
+                        workData2.add(usage);
+                    }
                 }
             }
             if (n instanceof StateSplit) {
@@ -234,16 +274,16 @@
     }
 
     public static void inverseLoop(Loop loop, If split) {
-        assert loop.nodes().isMarked(split);
+        assert loop.cfgNodes().isMarked(split);
         FixedNode noExit = split.trueSuccessor();
         FixedNode exit = split.falseSuccessor();
-        if (loop.nodes().isMarked(exit) && !loop.nodes().isMarked(noExit)) {
+        if (loop.cfgNodes().isMarked(exit) && !loop.cfgNodes().isMarked(noExit)) {
             FixedNode tmp = noExit;
             noExit = exit;
             exit = tmp;
         }
-        assert !loop.nodes().isMarked(exit);
-        assert loop.nodes().isMarked(noExit);
+        assert !loop.cfgNodes().isMarked(exit);
+        assert loop.cfgNodes().isMarked(noExit);
 
         PeelingResult peeling = preparePeeling(loop, split);
         rewirePeeling(peeling, loop, split);
@@ -283,8 +323,9 @@
         // update parents
         Loop parent = loop.parent();
         while (parent != null) {
-            parent.nodes = computeLoopNodes(parent.loopBegin);
-            parent.exits = computeLoopExits(parent.loopBegin, parent.nodes);
+            parent.cfgNodes = computeLoopNodes(parent.loopBegin);
+            parent.invalidateCached();
+            parent.exits = computeLoopExits(parent.loopBegin, parent.cfgNodes);
             parent = parent.parent;
         }
         GraalMetrics.LoopsPeeled++;
@@ -295,7 +336,7 @@
         Graph graph = loopBegin.graph();
         Node loopPred = loopBegin.singlePredecessor();
         loopPred.successors().replace(loopBegin.forwardEdge(), peeling.begin);
-        NodeBitMap loopNodes = loop.nodes();
+        NodeBitMap loopNodes = loop.cfgNodes();
         Node originalLast = from;
         if (originalLast == loopBegin.loopEnd()) {
             originalLast = loopBegin.loopEnd().singlePredecessor();
@@ -442,13 +483,17 @@
             }
         });
 
-        final NodeBitMap inOrBefore = inOrBefore(loop);
+
+        loop.invalidateCached();
+        final NodeBitMap inOrBefore = loop.inOrBefore();
 
         GraalCompilation compilation = GraalCompilation.compilation();
         if (compilation.compiler.isObserved()) {
             Map<String, Object> debug = new HashMap<String, Object>();
             debug.put("loopExits", colors);
             debug.put("inOrBefore", inOrBefore);
+            debug.put("inOrAfter", loop.inOrAfter());
+            debug.put("nodes", loop.nodes());
             debug.put("exitFrameStates", exitFrameStates);
             compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After coloring", graph, true, false, debug));
         }
@@ -495,6 +540,11 @@
             }
             @Override
             public boolean explore(Node n) {
+                /*System.out.println("Explore " + n + "?");
+                System.out.println(" - exitFS : " + (!exitFrameStates.isNew(n) && exitFrameStates.isMarked(n)));
+                System.out.println(" - !inOrBefore : " + (!inOrBefore.isNew(n) && !inOrBefore.isMarked(n)));
+                System.out.println(" - inputs > 0 : " + (n.inputs().size() > 0));
+                System.out.println(" - !danglingMergeFrameState : " + (!danglingMergeFrameState(n)));*/
                 return (!exitFrameStates.isNew(n) && exitFrameStates.isMarked(n))
                 || (!inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && n.inputs().size() > 0 && !danglingMergeFrameState(n)); //TODO (gd) hum
             }
@@ -510,7 +560,9 @@
                 //System.out.println("fixNode(" + node + ", " + color + ")");
                 if (color == null) {
                     // 'white' it out : make non-explorable
-                    exitFrameStates.clear(node);
+                    if (!exitFrameStates.isNew(node)) {
+                        exitFrameStates.clear(node);
+                    }
                     inOrBefore.mark(node);
                 } else {
                     for (int i = 0; i < node.inputs().size(); i++) {
@@ -677,11 +729,45 @@
         return (StateSplit) exit;
     }
 
-    private static NodeBitMap inOrBefore(Loop loop) {
+    private static NodeBitMap inOrAfter(Loop loop) {
+        Graph graph = loop.loopBegin().graph();
+        NodeBitMap inOrAfter = graph.createNodeBitMap();
+        NodeFlood work = graph.createNodeFlood();
+        NodeBitMap loopNodes = loop.cfgNodes();
+        work.addAll(loopNodes);
+        for (Node n : work) {
+            //inOrAfter.mark(n);
+            markWithState(n, inOrAfter);
+            for (Node sux : n.successors()) {
+                if (sux != null) {
+                    work.add(sux);
+                }
+            }
+            for (Node usage : n.usages()) {
+                if (usage instanceof Phi) { // filter out data graph cycles
+                    Phi phi = (Phi) usage;
+                    if (!phi.isDead()) {
+                        Merge merge = phi.merge();
+                        if (merge instanceof LoopBegin) {
+                            LoopBegin phiLoop = (LoopBegin) merge;
+                            int backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd());
+                            if (phi.valueAt(backIndex) == n) {
+                                continue;
+                            }
+                        }
+                    }
+                }
+                work.add(usage);
+            }
+        }
+        return inOrAfter;
+    }
+
+    private static NodeBitMap inOrBefore(Loop loop, NodeBitMap inOrAfter) {
         Graph graph = loop.loopBegin().graph();
         NodeBitMap inOrBefore = graph.createNodeBitMap();
         NodeFlood work = graph.createNodeFlood();
-        NodeBitMap loopNodes = loop.nodes();
+        NodeBitMap loopNodes = loop.cfgNodes();
         work.addAll(loopNodes);
         for (Node n : work) {
             inOrBefore.mark(n);
@@ -709,7 +795,19 @@
                         work.add(in);
                     }
                 }
-                if (n instanceof LoopBegin) {
+                for (Node sux : n.cfgSuccessors()) { // go down into branches that are not 'inOfAfter'
+                    if (sux != null && !inOrAfter.isMarked(sux)) {
+                        work.add(sux);
+                    }
+                }
+                if (n instanceof Merge) { //add phis & counters
+                    for (Node usage : n.dataUsages()) {
+                        if (!(usage instanceof LoopEnd)) {
+                            work.add(usage);
+                        }
+                    }
+                }
+                if (n instanceof LoopBegin && n != loop.loopBegin()) {
                     Loop p = loop.parent;
                     boolean isParent = false;
                     while (p != null) {