# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1309421255 -7200
# Node ID d9fa4309f89e9dfc10959eb1e222259f45b801d3
# Parent  f14632d52ab33f4648dea5ddb14324b0faf835ec
Fix some coloring bug, fix to keep more Placeholders at loop exits, fix for loop nodes computation

diff -r f14632d52ab3 -r d9fa4309f89e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Wed Jun 29 12:23:13 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Thu Jun 30 10:07:35 2011 +0200
@@ -325,12 +325,12 @@
                     Merge merge = new Merge(graph);
                     assert p.predecessors().size() == 1 : "predecessors size: " + p.predecessors().size();
                     FixedNode next = p.next();
-                    p.setNext(null);
                     EndNode end = new EndNode(graph);
-                    p.replaceAndDelete(end);
+                    p.setNext(end);
                     merge.setNext(next);
                     merge.addEnd(end);
                     merge.setStateAfter(existingState);
+                    p.setStateAfter(existingState.duplicate(bci));
                     if (!(next instanceof LoopEnd)) {
                         target.firstInstruction = merge;
                     }
@@ -1198,7 +1198,14 @@
             } else {
                 EndNode end = new EndNode(graph);
                 ((Merge) result).addEnd(end);
-                result = end;
+                Placeholder p = new Placeholder(graph);
+                int bci = block.startBci;
+                if (block instanceof ExceptionBlock) {
+                    bci = ((ExceptionBlock) block).deoptBci;
+                }
+                p.setStateAfter(stateAfter.duplicate(bci));
+                p.setNext(end);
+                result = p;
             }
         }
         assert !(result instanceof LoopBegin || result instanceof Merge);
diff -r f14632d52ab3 -r d9fa4309f89e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java	Wed Jun 29 12:23:13 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java	Thu Jun 30 10:07:35 2011 +0200
@@ -35,13 +35,55 @@
 
     public static interface ColoringLambda<T> {
         T color(Iterable<T> incomming, Merge merge);
+        T danglingColor(Iterable<T> incomming, Merge merge);
     }
 
     /**
      * colors down, applying the lambda at merge points, starting at the pre-colored points.
      */
     public static <T> void colorCFGDown(NodeMap<T> colors, ColoringLambda<T> lambda) {
-        List<Node> startingPoints = new LinkedList<Node>();
+        Set<Merge> delayed = new HashSet<Merge>();
+        Set<Node> currentPoints = new HashSet<Node>();
+        Set<Node> otherPoints = new HashSet<Node>();
+        Set<Merge> otherMerges = new HashSet<Merge>();
+        for (Entry<Node, T> entry : colors.entries()) {
+            currentPoints.add(entry.getKey());
+        }
+        ArrayList<T> incomming = new ArrayList<T>(2);
+        while (!currentPoints.isEmpty()) {
+            for (Node node : currentPoints) {
+                otherMerges.addAll(colorCFGDownToMerge(node, colors.get(node), colors));
+            }
+            for (Merge merge : otherMerges) {
+                incomming.clear();
+                for (EndNode end : merge.cfgPredecessors()) {
+                    incomming.add(colors.get(end));
+                }
+                T color = lambda.color(incomming, merge);
+                if (color != null) {
+                    colors.set(merge, color);
+                    colors.set(merge.next(), color);
+                    otherPoints.add(merge.next());
+                    delayed.remove(merge);
+                } else {
+                    delayed.add(merge);
+                }
+            }
+            Set<Node> tmp = currentPoints;
+            currentPoints = otherPoints;
+            otherPoints = tmp;
+            otherPoints.clear();
+            otherMerges.clear();
+        }
+        for (Merge merge : delayed) {
+            T color = lambda.danglingColor(incomming, merge);
+            if (color != null) {
+                colors.set(merge, color);
+            }
+        }
+
+
+        /*List<Node> startingPoints = new LinkedList<Node>();
         for (Entry<Node, T> entry : colors.entries()) {
             startingPoints.add(entry.getKey());
         }
@@ -65,9 +107,10 @@
                 colors.set(merge, color);
                 work.addAll(colorCFGDownToMerge(merge.next(), color, colors));
             } else {
+                System.out.println("Can not color " + merge);
                 work.addAgain(merge);
             }
-        }
+        }*/
     }
 
     private static <T> Collection<Merge> colorCFGDownToMerge(Node from, T color, NodeMap<T> colors) {
@@ -155,12 +198,9 @@
                                     Value v = phi.valueAt(i);
                                     if (v == node) {
                                         T color = internalColoring.get(merge.phiPredecessorAt(i));
-                                        if (color == null) {
-                                            //System.out.println("Split : color from " + usage + " is null");
-                                            delay = true;
-                                            break;
+                                        if (color != null) {
+                                            colors.add(color);
                                         }
-                                        colors.add(color);
                                     }
                                 }
                             } else {
@@ -265,7 +305,7 @@
                 }
                 Map<String, Object> debug = new HashMap<String, Object>();
                 debug.put("split", debugColoring);
-                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in split", coloring.graph(), true, false, debug));
+                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in split", coloring.graph(), true, false, true, debug));
             }
         }
     }
diff -r f14632d52ab3 -r d9fa4309f89e graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Wed Jun 29 12:23:13 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Thu Jun 30 10:07:35 2011 +0200
@@ -147,9 +147,6 @@
                         if (merge instanceof LoopBegin) {
                             LoopBegin phiLoop = (LoopBegin) merge;
                             int backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd());
-                            if (backIndex >= phi.valueCount()) {
-                                System.out.println("Wierd phi : " + phi);
-                            }
                             if (phi.valueAt(backIndex) == n) {
                                 continue;
                             }
@@ -162,8 +159,25 @@
         NodeBitMap inOrBefore = loopBegin.graph().createNodeBitMap();
         for (Node n : workData2) {
             inOrBefore.mark(n);
-            for (Node input : n.dataInputs()) {
-                workData2.add(input);
+            if (n instanceof Phi) {
+                Phi phi = (Phi) n;
+                if (!phi.isDead()) {
+                    int backIndex = -1;
+                    Merge merge = phi.merge();
+                    if (merge instanceof LoopBegin) {
+                        LoopBegin phiLoop = (LoopBegin) merge;
+                        backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd());
+                    }
+                    for (int i = 0; i < phi.valueCount(); i++) {
+                        if (i != backIndex) {
+                            workData2.add(phi.valueAt(i));
+                        }
+                    }
+                }
+            } else {
+                for (Node input : n.dataInputs()) {
+                    workData2.add(input);
+                }
             }
             if (n instanceof Merge) { //add phis & counters
                 for (Node usage : n.dataUsages()) {
@@ -171,7 +185,7 @@
                 }
             }
         }
-        /*if (!recurse) {
+        if (!recurse) {
             recurse = true;
             GraalCompilation compilation = GraalCompilation.compilation();
             if (compilation.compiler.isObserved()) {
@@ -182,7 +196,7 @@
                 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Compute loop nodes", loopBegin.graph(), true, false, debug));
             }
             recurse = false;
-        }*/
+        }
         inOrAfter.setIntersect(inOrBefore);
         loopNodes.setUnion(inOrAfter);
         return loopNodes;
@@ -260,13 +274,7 @@
         LoopBegin loopBegin = loop.loopBegin();
         Graph graph = loopBegin.graph();
         Node loopPred = loopBegin.singlePredecessor();
-        if (loopPred instanceof FixedNodeWithNext) {
-            ((FixedNodeWithNext) loopPred).setNext(peeling.begin);
-        } else if (loopPred instanceof StartNode) {
-            ((StartNode) loopPred).setStart(peeling.begin);
-        } else {
-            Util.shouldNotReachHere();
-        }
+        loopPred.successors().replace(loopBegin.forwardEdge(), peeling.begin);
         NodeBitMap loopNodes = loop.nodes();
         Node originalLast = from;
         if (originalLast == loopBegin.loopEnd()) {
@@ -399,7 +407,7 @@
 
         // prepare inital colors
         for (Node exitPoint : exitPoints) {
-                colors.set(exitPoint, exitPoint);
+            colors.set(exitPoint, exitPoint);
         }
 
         /*System.out.println("newExitValues");
@@ -427,6 +435,19 @@
                 }
                 return color;
             }
+            @Override
+            public Node danglingColor(Iterable<Node> incomming, Merge merge) {
+                Node color = null;
+                for (Node c : incomming) {
+                    if (color == null) {
+                        color = c;
+                    } else if (color != c) {
+                        return merge;
+                    }
+                }
+                assert color != null;
+                return color;
+            }
         });
 
         final NodeBitMap inOrBefore = inOrBefore(loop);
@@ -518,6 +539,12 @@
         LoopBegin loopBegin = loop.loopBegin();
         Graph graph = loopBegin.graph();
         NodeBitMap marked = computeLoopNodesFrom(loopBegin, from);
+        GraalCompilation compilation = GraalCompilation.compilation();
+        if (compilation.compiler.isObserved()) {
+            Map<String, Object> debug = new HashMap<String, Object>();
+            debug.put("marked", marked);
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After computeLoopNodesFrom", loopBegin.graph(), true, false, debug));
+        }
         if (from == loopBegin.loopEnd()) {
             marked.clear(from);
         }
@@ -528,7 +555,6 @@
 
         for (Node exit : loop.exits()) {
             if (marked.isMarked(exit.singlePredecessor())) {
-                //System.out.println("Exit : " + exit);
                 marked.mark(((Placeholder) exit).stateAfter());
                 Placeholder p = new Placeholder(graph);
                 replacements.put(exit, p);
@@ -556,7 +582,7 @@
             }
         }
 
-        GraalCompilation compilation = GraalCompilation.compilation();
+        //GraalCompilation compilation = GraalCompilation.compilation();
         if (compilation.compiler.isObserved()) {
             Map<String, Object> debug = new HashMap<String, Object>();
             debug.put("marked", marked);