# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1309270412 -7200
# Node ID d5218b2465548cad75e7d06f2389aa02c25901e4
# Parent  0a5776813ff04901bfe3cc146bb3ceebc3dfa05c
Fix multiple bugs in loop peeling

diff -r 0a5776813ff0 -r d5218b246554 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java	Tue Jun 28 16:13:32 2011 +0200
@@ -297,9 +297,6 @@
         stream.printf("   <block name='%d'>%n", block.blockID());
         stream.printf("    <successors>%n");
         for (Block sux : block.getSuccessors()) {
-//            if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) { //TODO gd
-//                // Skip back edges.
-//            } else {
             if (sux != null) {
                 stream.printf("     <successor name='%d'/>%n", sux.blockID());
             }
diff -r 0a5776813ff0 -r d5218b246554 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Tue Jun 28 16:13:32 2011 +0200
@@ -1053,7 +1053,7 @@
             lastState = fs;
         } else if (block.blockPredecessors().size() == 1) {
             FrameState fs = block.blockPredecessors().get(0).lastState();
-            assert fs != null; //TODO gd maybe this assert should be removed
+            assert fs != null;
             if (GraalOptions.TraceLIRGeneratorLevel >= 2) {
                 TTY.println("STATE CHANGE (singlePred)");
                 if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
diff -r 0a5776813ff0 -r d5218b246554 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java	Tue Jun 28 16:13:32 2011 +0200
@@ -28,10 +28,9 @@
 import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.graph.*;
 
-public class LoopBegin extends Merge{
+public class LoopBegin extends Merge {
     public LoopBegin(Graph graph) {
         super(graph);
-        this.addEnd(new EndNode(graph));
     }
 
     public LoopEnd loopEnd() {
diff -r 0a5776813ff0 -r d5218b246554 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	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Tue Jun 28 16:13:32 2011 +0200
@@ -1167,6 +1167,7 @@
         if (block.firstInstruction == null) {
             if (block.isLoopHeader) {
                 LoopBegin loopBegin = new LoopBegin(graph);
+                loopBegin.addEnd(new EndNode(graph));
                 LoopEnd loopEnd = new LoopEnd(graph);
                 loopEnd.setLoopBegin(loopBegin);
                 Placeholder pBegin = new Placeholder(graph);
diff -r 0a5776813ff0 -r d5218b246554 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Tue Jun 28 16:13:32 2011 +0200
@@ -37,12 +37,12 @@
     @Override
     protected void run(Graph graph) {
         List<Loop> loops = LoopUtil.computeLoops(graph);
-        /*
-        for (Loop loop : loops) {
-            LoopUtil.peelLoop(loop);
-        }
+
+//        for (Loop loop : loops) {
+//            LoopUtil.peelLoop(loop);
+//        }
 //        loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops
-        */
+
         for (Loop loop : loops) {
             doLoopCounters(loop);
         }
diff -r 0a5776813ff0 -r d5218b246554 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	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java	Tue Jun 28 16:13:32 2011 +0200
@@ -25,7 +25,9 @@
 import java.util.*;
 import java.util.Map.Entry;
 
+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.value.*;
 import com.oracle.max.graal.graph.*;
 
@@ -104,40 +106,65 @@
     public static interface ColorSplitingLambda<T> {
         void fixSplit(Node oldNode, Node newNode, T color);
         void fixNode(Node node, T color);
+        Value fixPhiInput(Value input, T color);
         boolean explore(Node n);
     }
 
-    // TODO (gd) handle FrameSate inputs/usages properly
+    // TODO (gd) rework that code around Phi handling : too complicated
     public static <T> void splitFromColoring(NodeMap<T> coloring, ColorSplitingLambda<T> lambda) {
         Map<Node, T> internalColoring = new HashMap<Node, T>();
-        Queue<Node> work = new LinkedList<Node>();
+        NodeWorkList work = coloring.graph().createNodeWorkList();
         for (Entry<Node, T> entry : coloring.entries()) {
             T color = entry.getValue();
             Node node = entry.getKey();
-            work.offer(node);
+            work.add(node);
             internalColoring.put(node, color);
         }
         Set<T> colors = new HashSet<T>();
-        while (!work.isEmpty()) {
-            Node node = work.poll();
-            //System.out.println("Split : work on " + node);
-            boolean delay = false;
-            colors.clear();
-            T originalColoringColor = coloring.get(node);
-            if (originalColoringColor == null && internalColoring.get(node) != null) {
-                //System.out.println("Split : ori == null && intern != null -> continue");
-                continue;
-            }
-            if (originalColoringColor == null) {
-                for (Node usage : node.dataUsages()) {
-                    if (usage instanceof Phi) {
-                        Phi phi = (Phi) usage;
-                        Merge merge = phi.merge();
-                        //System.out.println("Split merge : " + merge + ".endCount = " + merge.endCount() + " phi " + phi + ".valueCount : " + phi.valueCount());
-                        for (int i = 0; i < phi.valueCount(); i++) {
-                            Value v = phi.valueAt(i);
-                            if (v == node) {
-                                T color = internalColoring.get(merge.phiPredecessorAt(i));
+        try {
+            for (Node node : work) {
+                //System.out.println("Split : work on " + node);
+                if (node instanceof Phi) {
+                    Phi phi = (Phi) node;
+                    Merge merge = phi.merge();
+                    for (int i = 0; i < phi.valueCount(); i++) {
+                        Value v = phi.valueAt(i);
+                        if (v != null) {
+                            T color = internalColoring.get(merge.phiPredecessorAt(i));
+                            Value replace = lambda.fixPhiInput(v, color);
+                            if (replace != v) {
+                                phi.setValueAt(i, replace);
+                            }
+                        }
+                    }
+                } else {
+                    boolean delay = false;
+                    colors.clear();
+                    T originalColoringColor = coloring.get(node);
+                    if (originalColoringColor == null && internalColoring.get(node) != null) {
+                        //System.out.println("Split : ori == null && intern != null -> continue");
+                        continue;
+                    }
+                    if (originalColoringColor == null) {
+                        for (Node usage : node.dataUsages()) {
+                            if (usage instanceof Phi) {
+                                Phi phi = (Phi) usage;
+                                Merge merge = phi.merge();
+                                //System.out.println("Split merge : " + merge + ".endCount = " + merge.endCount() + " phi " + phi + ".valueCount : " + phi.valueCount());
+                                for (int i = 0; i < phi.valueCount(); i++) {
+                                    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;
+                                        }
+                                        colors.add(color);
+                                    }
+                                }
+                            } else {
+                                T color = internalColoring.get(usage);
                                 if (color == null) {
                                     //System.out.println("Split : color from " + usage + " is null");
                                     delay = true;
@@ -146,79 +173,99 @@
                                 colors.add(color);
                             }
                         }
+                        if (delay) {
+                            //System.out.println("Split : delay");
+                            work.addAgain(node);
+                            continue;
+                        }
                     } else {
-                        T color = internalColoring.get(usage);
-                        if (color == null) {
-                            //System.out.println("Split : color from " + usage + " is null");
-                            delay = true;
-                            break;
-                        }
-                        colors.add(color);
+                        colors.add(originalColoringColor);
                     }
-                }
-                if (delay) {
-                    //System.out.println("Split : delay");
-                    work.offer(node);
-                    continue;
-                }
-            } else {
-                colors.add(originalColoringColor);
-            }
-            if (colors.size() == 1) {
-                //System.out.println("Split : 1 color, coloring, fixing");
-                T color = colors.iterator().next();
-                internalColoring.put(node, color);
-                lambda.fixNode(node, color);
-            } else {
-                //System.out.println("Split : " + colors.size() + " colors, coloring, spliting, fixing");
-                for (T color : colors) {
-                    Node newNode = node.copy();
-                    for (int i = 0; i < node.inputs().size(); i++) {
-                        Node input = node.inputs().get(i);
-                        newNode.inputs().setOrExpand(i, input);
-                    }
-                    for (int i = 0; i < node.successors().size(); i++) {
-                        Node input = node.successors().get(i);
-                        newNode.successors().setOrExpand(i, input);
-                    }
-                    internalColoring.put(newNode, color);
-                    lambda.fixSplit(node, newNode, color);
-                    for (Node usage : node.dataUsages()) {
-                        if (usage instanceof Phi) {
-                            Phi phi = (Phi) usage;
-                            Merge merge = phi.merge();
-                            for (int i = 0; i < phi.valueCount(); i++) {
-                                Value v = phi.valueAt(i);
-                                if (v == node) {
-                                    T uColor = internalColoring.get(merge.endAt(i));
+                    if (colors.size() == 1) {
+                        //System.out.println("Split : 1 color, coloring, fixing");
+                        T color = colors.iterator().next();
+                        internalColoring.put(node, color);
+                        lambda.fixNode(node, color);
+                    } else {
+                        //System.out.println("Split : " + colors.size() + " colors, coloring, spliting, fixing");
+                        for (T color : colors) {
+                            Node newNode = node.copy();
+                            for (int i = 0; i < node.inputs().size(); i++) {
+                                Node input = node.inputs().get(i);
+                                newNode.inputs().setOrExpand(i, input);
+                            }
+                            for (int i = 0; i < node.successors().size(); i++) {
+                                Node input = node.successors().get(i);
+                                newNode.successors().setOrExpand(i, input);
+                            }
+                            internalColoring.put(newNode, color);
+                            lambda.fixSplit(node, newNode, color);
+                            LinkedList<Node> dataUsages = new LinkedList<Node>();
+                            for (Node usage : node.dataUsages()) {
+                                dataUsages.add(usage);
+                            }
+                            for (Node usage : dataUsages) {
+                                if (usage instanceof Phi) {
+                                    Phi phi = (Phi) usage;
+                                    Merge merge = phi.merge();
+                                    for (int i = 0; i < phi.valueCount(); i++) {
+                                        Value v = phi.valueAt(i);
+                                        if (v == node) {
+                                            T uColor = internalColoring.get(merge.endAt(i));
+                                            if (uColor == color) {
+                                                phi.setValueAt(i, (Value) newNode);
+                                            }
+                                        }
+                                    }
+                                } else {
+                                    T uColor = internalColoring.get(usage);
                                     if (uColor == color) {
-                                        phi.setValueAt(i, (Value) newNode);
+                                        usage.inputs().replace(node, newNode);
                                     }
                                 }
                             }
-                        } else {
-                            T uColor = internalColoring.get(usage);
-                            if (uColor == color) {
-                                usage.inputs().replace(node, newNode);
-                            }
                         }
                     }
                 }
-            }
+
+                if (node instanceof StateSplit) {
+                    FrameState stateAfter = ((StateSplit) node).stateAfter();
+                    if (stateAfter != null && lambda.explore(stateAfter) && !work.isNew(stateAfter)) {
+                        //System.out.println("Split : Add framestate to work");
+                        work.add(stateAfter);
+                    }
+                }
 
-            if (node instanceof StateSplit) {
-                FrameState stateAfter = ((StateSplit) node).stateAfter();
-                if (stateAfter != null && lambda.explore(stateAfter)) {
-                    //System.out.println("Split : Add framestate to work");
-                    work.offer(stateAfter);
+                if (node instanceof Merge) {
+                    for (Node usage : node.usages()) {
+                        if (!work.isNew(usage)) {
+                            work.add(usage);
+                        }
+                    }
+                }
+
+                if (node instanceof LoopEnd) {
+                    work.add(((LoopEnd) node).loopBegin());
+                }
+
+                for (Node input : node.dataInputs()) {
+                    if (lambda.explore(input) && coloring.get(input) == null && !work.isNew(input)) {
+                        //System.out.println("Split : Add input " + input + " to work from " + node);
+                        work.add(input);
+                    }
                 }
             }
-
-            for (Node input : node.dataInputs()) {
-                if (lambda.explore(input) && coloring.get(input) == null) {
-                    //System.out.println("Split : Add input " + input + " to work");
-                    work.offer(input);
+        } catch (RuntimeException re) {
+            re.printStackTrace();
+            GraalCompilation compilation = GraalCompilation.compilation();
+            if (compilation.compiler.isObserved()) {
+                NodeMap<T> debugColoring = coloring.graph().createNodeMap();
+                for (Entry<Node, T> entry : internalColoring.entrySet()) {
+                    debugColoring.set(entry.getKey(), entry.getValue());
                 }
+                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));
             }
         }
     }
diff -r 0a5776813ff0 -r d5218b246554 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	Tue Jun 28 10:10:47 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Tue Jun 28 16:13:32 2011 +0200
@@ -126,7 +126,7 @@
     public static NodeBitMap computeLoopNodes(LoopBegin loopBegin) {
         return computeLoopNodesFrom(loopBegin, loopBegin.loopEnd());
     }
-
+    private static boolean recurse = false;
     public static NodeBitMap computeLoopNodesFrom(LoopBegin loopBegin, FixedNode from) {
         NodeFlood workData1 = loopBegin.graph().createNodeFlood();
         NodeFlood workData2 = loopBegin.graph().createNodeFlood();
@@ -140,6 +140,17 @@
         for (Node n : workData1) {
             inOrAfter.mark(n);
             for (Node usage : n.dataUsages()) {
+                if (usage instanceof Phi) { // filter out data graph cycles
+                    Phi phi = (Phi) usage;
+                    Merge merge = phi.merge();
+                    if (merge instanceof LoopBegin) {
+                        LoopBegin phiLoop = (LoopBegin) merge;
+                        int backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd());
+                        if (phi.valueAt(backIndex) == n) {
+                            continue;
+                        }
+                    }
+                }
                 workData1.add(usage);
             }
         }
@@ -155,6 +166,18 @@
                 }
             }
         }
+        /*if (!recurse) {
+            recurse = true;
+            GraalCompilation compilation = GraalCompilation.compilation();
+            if (compilation.compiler.isObserved()) {
+                Map<String, Object> debug = new HashMap<String, Object>();
+                debug.put("loopNodes", loopNodes);
+                debug.put("inOrAfter", inOrAfter);
+                debug.put("inOrBefore", inOrBefore);
+                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Compute loop nodes", loopBegin.graph(), true, false, debug));
+            }
+            recurse = false;
+        }*/
         inOrAfter.setIntersect(inOrBefore);
         loopNodes.setUnion(inOrAfter);
         return loopNodes;
@@ -297,8 +320,6 @@
             newExit.setStateAfter(null);
             newExit.replaceAndDelete(nEnd);
 
-            exitPoints.remove(original);
-            exitPoints.add(oEnd);
             exitPoints.add(nEnd);
         }
 
@@ -413,7 +434,6 @@
             compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After coloring", graph, true, false, debug));
         }
 
-        // TODO (gd) handle Phi inputs properly : use the color from the corresponding EndNode
         GraphUtil.splitFromColoring(colors, new ColorSplitingLambda<Node>(){
             @Override
             public void fixSplit(Node oldNode, Node newNode, Node color) {
@@ -425,12 +445,30 @@
                     return value;
                 }
                 Merge merge = (Merge) point;
-                Phi phi = new Phi(kind, merge, merge.graph());
-                valueMap.set(point, phi);
+                ArrayList<Value> values = new ArrayList<Value>(merge.phiPredecessorCount());
+                Value v = null;
+                boolean createPhi = false;
                 for (EndNode end : merge.cfgPredecessors()) {
-                    phi.addInput(getValueAt(colors.get(end), valueMap, kind));
+                    Value valueAt = getValueAt(colors.get(end), valueMap, kind);
+                    if (v == null) {
+                        v = valueAt;
+                    } else if (v != valueAt) {
+                        createPhi = true;
+                    }
+                    values.add(valueAt);
                 }
-                return phi;
+                if (createPhi) {
+                    Phi phi = new Phi(kind, merge, merge.graph());
+                    valueMap.set(point, phi);
+                    for (EndNode end : merge.cfgPredecessors()) {
+                        phi.addInput(getValueAt(colors.get(end), valueMap, kind));
+                    }
+                    return phi;
+                } else {
+                    assert v != null;
+                    valueMap.set(point, v);
+                    return v;
+                }
             }
             @Override
             public boolean explore(Node n) {
@@ -451,6 +489,17 @@
                         //}
                     }
                 }
+            }
+            @Override
+            public Value fixPhiInput(Value input, Node color) {
+                if (newExitValues.isNew(input)) {
+                    return input;
+                }
+                NodeMap<Value> valueMap = newExitValues.get(input);
+                if (valueMap != null) {
+                    return getValueAt(color, valueMap, input.kind);
+                }
+                return input;
             }});
 
         if (compilation.compiler.isObserved()) {
@@ -470,7 +519,6 @@
         NodeMap<Placeholder> phis = graph.createNodeMap();
         NodeMap<Placeholder> exits = graph.createNodeMap();
 
-
         for (Node exit : loop.exits()) {
             if (marked.isMarked(exit.singlePredecessor())) {
                 marked.mark(((Placeholder) exit).stateAfter());
@@ -500,17 +548,18 @@
             }
         }
 
-        Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements);
-
         GraalCompilation compilation = GraalCompilation.compilation();
         if (compilation.compiler.isObserved()) {
-            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After addDuplicate", graph, true, false));
+            Map<String, Object> debug = new HashMap<String, Object>();
+            debug.put("marked", marked);
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Before addDuplicate", loopBegin.graph(), true, false, debug));
         }
 
+        Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements);
+
         NodeMap<Node> dataOut = graph.createNodeMap();
         for (Node n : marked) {
             for (Node usage : n.dataUsages()) {
-                System.out.println("n = " + n + "; u= " + usage);
                 if (!marked.isMarked(usage)
                                 && !loop.nodes().isNew(usage) && loop.nodes().isMarked(usage)
                                 && !((usage instanceof Phi) || ((Phi) usage).merge() != loopBegin)) {