# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1309272348 -7200
# Node ID 25b5ec0568e61ac73c35878971e05b7c0d7e7bce
# Parent  d5218b2465548cad75e7d06f2389aa02c25901e4# Parent  46fe56f202a4db5b9dc2a7c2096d66259c4987e9
Merge

diff -r 46fe56f202a4 -r 25b5ec0568e6 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 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java	Tue Jun 28 16:45:48 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.io.*;
 import java.util.*;
+import java.util.AbstractMap.SimpleImmutableEntry;
 import java.util.Map.Entry;
 
 import com.oracle.max.graal.compiler.ir.*;
@@ -109,10 +110,14 @@
         flush();
     }
 
+    public void print(Graph graph, String title, boolean shortNames) {
+        print(graph, title, shortNames, Collections.<String, Object>emptyMap());
+    }
+
     /**
      * Prints an entire {@link Graph} with the specified title, optionally using short names for nodes.
      */
-    public void print(Graph graph, String title, boolean shortNames) {
+    public void print(Graph graph, String title, boolean shortNames, Map<String, Object> debugObjects) {
         stream.printf(" <graph name='%s'>%n", escape(title));
         noBlockNodes.clear();
         IdentifyBlocksPhase schedule = null;
@@ -121,12 +126,12 @@
             schedule.apply(graph);
         } catch (Throwable t) {
             // nothing to do here...
-            t.printStackTrace();
+            //t.printStackTrace();
         }
         List<Loop> loops = LoopUtil.computeLoops(graph);
 
         stream.println("  <nodes>");
-        List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock(), loops);
+        List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock(), loops, debugObjects);
         stream.println("  </nodes>");
 
         stream.println("  <edges>");
@@ -148,11 +153,50 @@
         flush();
     }
 
-    private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock, List<Loop> loops) {
+    private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock, List<Loop> loops, Map<String, Object> debugObjects) {
         ArrayList<Edge> edges = new ArrayList<Edge>();
         NodeBitMap loopExits = graph.createNodeBitMap();
         for (Loop loop : loops) {
-            loopExits.markAll(loop.exist());
+            loopExits.setUnion(loop.exits());
+        }
+
+        Map<Node, Set<Entry<String, Integer>>> colors = new HashMap<Node, Set<Entry<String, Integer>>>();
+        Map<Node, Set<String>> bits = new HashMap<Node, Set<String>>();
+        if (debugObjects != null) {
+            for (Entry<String, Object> entry : debugObjects.entrySet()) {
+                String name = entry.getKey();
+                Object obj = entry.getValue();
+                if (obj instanceof NodeMap) {
+                    Map<Object, Integer> colorNumbers = new HashMap<Object, Integer>();
+                    int nextColor = 0;
+                    NodeMap<?> map = (NodeMap<?>) obj;
+                    for (Entry<Node, ?> mapEntry : map.entries()) {
+                        Node node = mapEntry.getKey();
+                        Object color = mapEntry.getValue();
+                        Integer colorNumber = colorNumbers.get(color);
+                        if (colorNumber == null) {
+                            colorNumber = nextColor++;
+                            colorNumbers.put(color, colorNumber);
+                        }
+                        Set<Entry<String, Integer>> nodeColors = colors.get(node);
+                        if (nodeColors == null) {
+                            nodeColors = new HashSet<Entry<String, Integer>>();
+                            colors.put(node, nodeColors);
+                        }
+                        nodeColors.add(new SimpleImmutableEntry<String, Integer>(name + "Color", colorNumber));
+                    }
+                } else if (obj instanceof NodeBitMap) {
+                    NodeBitMap bitmap = (NodeBitMap) obj;
+                    for (Node node : bitmap) {
+                        Set<String> nodeBits = bits.get(node);
+                        if (nodeBits == null) {
+                            nodeBits = new HashSet<String>();
+                            bits.put(node, nodeBits);
+                        }
+                        nodeBits.add(name);
+                    }
+                }
+            }
         }
 
         for (Node node : graph.getNodes()) {
@@ -199,6 +243,22 @@
             if (sb.length() > 0) {
                 stream.printf("    <p name='loops'>%s</p>%n", sb);
             }
+
+            Set<Entry<String, Integer>> nodeColors = colors.get(node);
+            if (nodeColors != null) {
+                for (Entry<String, Integer> color : nodeColors) {
+                    String name = color.getKey();
+                    Integer value = color.getValue();
+                    stream.printf("    <p name='%s'>%d</p>%n", name, value);
+                }
+            }
+            Set<String> nodeBits = bits.get(node);
+            if (nodeBits != null) {
+                for (String bit : nodeBits) {
+                    stream.printf("    <p name='%s'>true</p>%n", bit);
+                }
+            }
+
             for (Entry<Object, Object> entry : props.entrySet()) {
                 String key = entry.getKey().toString();
                 String value = entry.getValue() == null ? "null" : entry.getValue().toString();
@@ -237,11 +297,9 @@
         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());
-//            }
+            }
         }
         stream.printf("    </successors>%n");
         stream.printf("    <nodes>%n");
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java	Tue Jun 28 16:45:48 2011 +0200
@@ -142,7 +142,7 @@
     public void compilationEvent(CompilationEvent event) {
         if (printer != null && event.getGraph() != null && event.isHIRValid()) {
             Graph graph = event.getGraph();
-            printer.print(graph, event.getLabel(), true);
+            printer.print(graph, event.getLabel(), true, event.getDebugObjects());
         }
     }
 
diff -r 46fe56f202a4 -r 25b5ec0568e6 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 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Tue Jun 28 16:45:48 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) {
@@ -1464,6 +1464,9 @@
     }
 
     private void moveToPhi(Merge merge, Node pred) {
+        if (GraalOptions.TraceLIRGeneratorLevel >= 1) {
+            TTY.println("MOVE TO PHI from " + pred + " to " + merge);
+        }
         int nextSuccIndex = merge.phiPredecessorIndex(pred);
         PhiResolver resolver = new PhiResolver(this);
         for (Phi phi : merge.phis()) {
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java	Tue Jun 28 16:45:48 2011 +0200
@@ -22,6 +22,8 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import java.util.*;
+
 import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
@@ -67,4 +69,9 @@
         assertTrue(predecessors().size() <= 1, "at most one predecessor");
         return true;
     }
+
+    @Override
+    public Iterable< ? extends Node> dataUsages() {
+        return Collections.emptyList();
+    }
 }
diff -r 46fe56f202a4 -r 25b5ec0568e6 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 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java	Tue Jun 28 16:45:48 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() {
@@ -83,6 +82,16 @@
         throw Util.shouldNotReachHere("unknown pred : " + pred + "(sp=" + forwardEdge() + ", le=" + this.loopEnd() + ")");
     }
 
+    @Override
+    public Node phiPredecessorAt(int index) {
+        if (index == 0) {
+            return forwardEdge();
+        } else if (index == 1) {
+            return loopEnd();
+        }
+        throw Util.shouldNotReachHere();
+    }
+
     public Collection<LoopCounter> counters() {
         return Util.filter(this.usages(), LoopCounter.class);
     }
@@ -109,6 +118,12 @@
     }
 
     @Override
+    public Node singlePredecessor() {
+        assert endCount() == 1;
+        return endAt(0).singlePredecessor();
+    }
+
+    @Override
     public Iterable< ? extends Node> dataUsages() {
         final Iterator< ? extends Node> dataUsages = super.dataUsages().iterator();
         return new Iterable<Node>() {
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java	Tue Jun 28 16:45:48 2011 +0200
@@ -337,6 +337,10 @@
         return endIndex(end);
     }
 
+    public Node phiPredecessorAt(int index) {
+        return endAt(index);
+    }
+
     public Collection<Phi> phis() {
         return Util.filter(this.usages(), Phi.class);
     }
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java	Tue Jun 28 16:45:48 2011 +0200
@@ -22,7 +22,10 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import java.util.*;
+
 import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.ir.StateSplit.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
 
@@ -59,6 +62,7 @@
     }
 
     public void setMerge(Merge n) {
+        assert n != null;
         inputs().set(super.inputCount() + INPUT_MERGE, n);
     }
 
@@ -156,4 +160,16 @@
         x.isDead = isDead;
         return x;
     }
+
+    @Override
+    public Iterable<? extends Node> dataInputs() {
+        final Iterator< ? extends Node> input = super.dataInputs().iterator();
+        return new Iterable<Node>() {
+            @Override
+            public Iterator<Node> iterator() {
+                // TODO Auto-generated method stub
+                return new FilteringIterator(input, Merge.class);
+            }
+        };
+    }
 }
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java	Tue Jun 28 16:45:48 2011 +0200
@@ -26,7 +26,6 @@
 
 import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.compiler.gen.*;
-import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
 import com.sun.cri.ri.*;
@@ -179,7 +178,7 @@
         return properties;
     }
 
-    @Override
+    /*@Override
     public Iterable<? extends Node> dataUsages() {
         final Iterator<? extends Node> dataUsages = super.dataUsages().iterator();
         return new Iterable<Node>() {
@@ -188,5 +187,5 @@
                 return new StateSplit.FilteringIterator(dataUsages, FrameState.class);
             }
         };
-    }
+    }*/
 }
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/observer/CompilationEvent.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/observer/CompilationEvent.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/observer/CompilationEvent.java	Tue Jun 28 16:45:48 2011 +0200
@@ -56,6 +56,7 @@
     private Interval[] intervals;
     private int intervalsSize;
     private Interval[] intervalsCopy = null;
+    Map<String, Object> debugObjects;
 
     public CompilationEvent(GraalCompilation compilation) {
         this(compilation, null);
@@ -74,6 +75,14 @@
         this.lirValid = lirValid;
     }
 
+    public CompilationEvent(GraalCompilation compilation, String label, Graph graph, boolean hirValid, boolean lirValid, Map<String, Object> debugObjects) {
+        this(compilation, label);
+        this.graph = graph;
+        this.hirValid = hirValid;
+        this.lirValid = lirValid;
+        this.debugObjects = debugObjects;
+    }
+
     public CompilationEvent(GraalCompilation compilation, String label, Graph graph, boolean hirValid, boolean lirValid, CiTargetMethod targetMethod) {
         this(compilation, label, graph, hirValid, lirValid);
         this.targetMethod = targetMethod;
@@ -139,4 +148,9 @@
     public int getCodeSize() {
         return codeSize;
     }
+
+
+    public Map<String, Object> getDebugObjects() {
+        return debugObjects;
+    }
 }
diff -r 46fe56f202a4 -r 25b5ec0568e6 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 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Tue Jun 28 16:45:48 2011 +0200
@@ -201,7 +201,7 @@
         List<Loop> loops = LoopUtil.computeLoops(graph);
         NodeBitMap loopExits = graph.createNodeBitMap();
         for (Loop loop : loops) {
-            loopExits.markAll(loop.exist());
+            loopExits.setUnion(loop.exits());
         }
 
         // remove Placeholders
@@ -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 46fe56f202a4 -r 25b5ec0568e6 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 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Tue Jun 28 16:45:48 2011 +0200
@@ -26,6 +26,7 @@
 
 import com.oracle.max.graal.compiler.ir.*;
 import com.oracle.max.graal.compiler.util.*;
+import com.oracle.max.graal.compiler.util.LoopUtil.Loop;
 import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
@@ -35,14 +36,21 @@
 
     @Override
     protected void run(Graph graph) {
-        for (LoopBegin n : graph.getNodes(LoopBegin.class)) {
-            doLoop(n);
+        List<Loop> loops = LoopUtil.computeLoops(graph);
+
+//        for (Loop loop : loops) {
+//            LoopUtil.peelLoop(loop);
+//        }
+//        loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops
+
+        for (Loop loop : loops) {
+            doLoopCounters(loop);
         }
     }
 
-    private void doLoop(LoopBegin loopBegin) {
-        NodeBitMap loopNodes = LoopUtil.computeLoopNodes(loopBegin);
-        List<LoopCounter> counters = findLoopCounters(loopBegin, loopNodes);
+    private void doLoopCounters(Loop loop) {
+        LoopBegin loopBegin = loop.loopBegin();
+        List<LoopCounter> counters = findLoopCounters(loopBegin, loop.nodes());
         mergeLoopCounters(counters, loopBegin);
     }
 
@@ -102,6 +110,9 @@
                 if (phi.valueCount() == 2) {
                     Value backEdge = phi.valueAt(1);
                     Value init = phi.valueAt(0);
+                    if (loopNodes.isNew(init) || loopNodes.isNew(backEdge)) {
+                        continue;
+                    }
                     if (loopNodes.isMarked(init)) {
                         // try to reverse init/backEdge order
                         Value tmp = backEdge;
@@ -127,7 +138,7 @@
                             useCounterAfterAdd = true;
                         }
                     }
-                    if (stride != null && !loopNodes.isMarked(stride)) {
+                    if (stride != null && !loopNodes.isNew(stride) &&  !loopNodes.isMarked(stride)) {
                         Graph graph = loopBegin.graph();
                         LoopCounter counter = new LoopCounter(init.kind, init, stride, loopBegin, graph);
                         counters.add(counter);
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java	Tue Jun 28 16:45:48 2011 +0200
@@ -0,0 +1,272 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.max.graal.compiler.util;
+
+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.*;
+
+public class GraphUtil {
+
+    public static interface ColoringLambda<T> {
+        T color(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>();
+        for (Entry<Node, T> entry : colors.entries()) {
+            startingPoints.add(entry.getKey());
+        }
+        NodeWorkList work = colors.graph().createNodeWorkList();
+        for (Node startingPoint : startingPoints) {
+            if (startingPoint instanceof Merge) {
+                work.addAll(colorCFGDownToMerge(((Merge) startingPoint).next(), colors.get(startingPoint), colors));
+            } else {
+                work.addAll(colorCFGDownToMerge(startingPoint, colors.get(startingPoint), colors));
+            }
+        }
+        for (Node n : work) {
+            //System.out.println("Color : work on " + n);
+            Merge merge = (Merge) n;
+            ArrayList<T> incomming = new ArrayList<T>(2);
+            for (EndNode end : merge.cfgPredecessors()) {
+                incomming.add(colors.get(end));
+            }
+            T color = lambda.color(incomming, merge);
+            if (color != null) {
+                colors.set(merge, color);
+                work.addAll(colorCFGDownToMerge(merge.next(), color, colors));
+            } else {
+                work.addAgain(merge);
+            }
+        }
+    }
+
+    private static <T> Collection<Merge> colorCFGDownToMerge(Node from, T color, NodeMap<T> colors) {
+        //System.out.println("colorCFGDownToMerge(" + from + ", " + color + ", colors)");
+        NodeFlood work = from.graph().createNodeFlood();
+        Collection<Merge> merges = new LinkedList<Merge>();
+        work.add(from);
+        for (Node node : work) {
+            //System.out.println("colorToMerge : work on " + node);
+            Node current = node;
+            while (current != null) {
+                //System.out.println("colorToMerge : current " + current);
+                if (current instanceof Merge) {
+                    merges.add((Merge) current);
+                    break;
+                }
+                colors.set(current, color);
+                if (current instanceof FixedNodeWithNext) {
+                    current = ((FixedNodeWithNext) current).next();
+                } else if (current instanceof EndNode) {
+                    current = ((EndNode) current).merge();
+                } else {
+                    if (current instanceof ControlSplit) {
+                        for (Node sux : current.cfgSuccessors()) {
+                            work.add(sux);
+                        }
+                    }
+                    current = null;
+                }
+            }
+        }
+        //System.out.println("return " + merges);
+        return merges;
+    }
+
+    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) 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>();
+        NodeWorkList work = coloring.graph().createNodeWorkList();
+        for (Entry<Node, T> entry : coloring.entries()) {
+            T color = entry.getValue();
+            Node node = entry.getKey();
+            work.add(node);
+            internalColoring.put(node, color);
+        }
+        Set<T> colors = new HashSet<T>();
+        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;
+                                    break;
+                                }
+                                colors.add(color);
+                            }
+                        }
+                        if (delay) {
+                            //System.out.println("Split : delay");
+                            work.addAgain(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);
+                            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) {
+                                        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 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);
+                    }
+                }
+            }
+        } 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 46fe56f202a4 -r 25b5ec0568e6 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 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Tue Jun 28 16:45:48 2011 +0200
@@ -23,10 +23,17 @@
 package com.oracle.max.graal.compiler.util;
 
 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.schedule.*;
+import com.oracle.max.graal.compiler.util.GraphUtil.ColorSplitingLambda;
+import com.oracle.max.graal.compiler.util.GraphUtil.ColoringLambda;
+import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
+import com.sun.cri.ci.*;
 
 public class LoopUtil {
 
@@ -34,11 +41,11 @@
         private final LoopBegin loopBegin;
         private final NodeBitMap nodes;
         private Loop parent;
-        private final List<FixedNode> exits;
-        public Loop(LoopBegin loopBegin, NodeBitMap nodes) {
+        private final NodeBitMap exits;
+        public Loop(LoopBegin loopBegin, NodeBitMap nodes, NodeBitMap exits) {
             this.loopBegin = loopBegin;
             this.nodes = nodes;
-            this.exits = new LinkedList<FixedNode>();
+            this.exits = exits;
         }
 
         public LoopBegin loopBegin() {
@@ -53,7 +60,7 @@
             return parent;
         }
 
-        public List<FixedNode> exist() {
+        public NodeBitMap exits() {
             return exits;
         }
 
@@ -62,11 +69,29 @@
         }
     }
 
+    private static class PeelingResult {
+        public final FixedNode begin;
+        public final FixedNode end;
+        public final NodeMap<Placeholder> exits;
+        public final NodeMap<Placeholder> phis;
+        public final NodeMap<Node> phiInits;
+        public final NodeMap<Node> dataOut;
+        public PeelingResult(FixedNode begin, FixedNode end, NodeMap<Placeholder> exits, NodeMap<Placeholder> phis, NodeMap<Node> phiInits, NodeMap<Node> dataOut) {
+            this.begin = begin;
+            this.end = end;
+            this.exits = exits;
+            this.phis = phis;
+            this.phiInits = phiInits;
+            this.dataOut = dataOut;
+        }
+    }
+
     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);
-            Loop loop = new Loop(loopBegin, nodes);
+            NodeBitMap exits = graph.createNodeBitMap();
+            Loop loop = new Loop(loopBegin, nodes, exits);
             NodeFlood workCFG = graph.createNodeFlood();
             workCFG.add(loopBegin.loopEnd());
             for (Node n : workCFG) {
@@ -76,7 +101,7 @@
                 if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
                     for (Node sux : n.cfgSuccessors()) {
                         if (!nodes.isMarked(sux) && sux instanceof FixedNode) {
-                            loop.exits.add((FixedNode) sux);
+                            exits.mark(sux);
                         }
                     }
                 }
@@ -99,30 +124,33 @@
     }
 
     public static NodeBitMap computeLoopNodes(LoopBegin loopBegin) {
-        LoopEnd loopEnd = loopBegin.loopEnd();
-        NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap();
-        NodeFlood workCFG = loopBegin.graph().createNodeFlood();
+        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();
-        workCFG.add(loopEnd);
-        for (Node n : workCFG) {
+        NodeBitMap loopNodes = markUpCFG(loopBegin, from);
+        loopNodes.mark(loopBegin);
+        for (Node n : loopNodes) {
             workData1.add(n);
             workData2.add(n);
-            loopNodes.mark(n);
-            if (n == loopBegin) {
-                continue;
-            }
-            if (n instanceof LoopBegin) {
-                workCFG.add(((LoopBegin) n).loopEnd());
-            }
-            for (Node pred : n.cfgPredecessors()) {
-                workCFG.add(pred);
-            }
         }
         NodeBitMap inOrAfter = loopBegin.graph().createNodeBitMap();
         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);
             }
         }
@@ -138,8 +166,442 @@
                 }
             }
         }
-        inOrBefore.setIntersect(inOrAfter);
-        loopNodes.setUnion(inOrBefore);
+        /*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;
+    }
+
+    private static NodeBitMap markUpCFG(LoopBegin loopBegin, FixedNode from) {
+        NodeFlood workCFG = loopBegin.graph().createNodeFlood();
+        workCFG.add(from);
+        NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap();
+        for (Node n : workCFG) {
+            if (n == loopBegin) {
+                continue;
+            }
+            loopNodes.mark(n);
+            if (n instanceof LoopBegin) {
+                workCFG.add(((LoopBegin) n).loopEnd());
+            }
+            for (Node pred : n.cfgPredecessors()) {
+                workCFG.add(pred);
+            }
+        }
         return loopNodes;
     }
+
+    public static void ifDoWhileTransform(Loop loop, If split) {
+        assert loop.nodes().isMarked(split);
+        FixedNode noExit = split.trueSuccessor();
+        FixedNode exit = split.falseSuccessor();
+        if (loop.nodes().isMarked(exit) && !loop.nodes().isMarked(noExit)) {
+            FixedNode tmp = noExit;
+            noExit = exit;
+            exit = tmp;
+        }
+        assert !loop.nodes().isMarked(exit);
+        assert loop.nodes().isMarked(noExit);
+
+        PeelingResult peeling = preparePeeling(loop, split);
+        rewirePeeling(peeling, loop, split);
+        // TODO (gd) move peeled part to the end, rewire dataOut
+    }
+
+    public static void peelLoop(Loop loop) {
+        LoopEnd loopEnd = loop.loopBegin().loopEnd();
+        PeelingResult peeling = preparePeeling(loop, loopEnd);
+        GraalCompilation compilation = GraalCompilation.compilation();
+        if (compilation.compiler.isObserved()) {
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After peeling preparation", loopEnd.graph(), true, false));
+        }
+        /*System.out.println("Peeling : ");
+        System.out.println(" begin = " + peeling.begin);
+        System.out.println(" end = " + peeling.end);
+        System.out.println(" Phis :");
+        for (Entry<Node, Placeholder> entry : peeling.phis.entries()) {
+            System.out.println("  - " + entry.getKey() + " -> " + entry.getValue());
+        }
+        System.out.println(" Exits :");
+        for (Entry<Node, Placeholder> entry : peeling.exits.entries()) {
+            System.out.println("  - " + entry.getKey() + " -> " + entry.getValue());
+        }
+        System.out.println(" PhiInits :");
+        for (Entry<Node, Node> entry : peeling.phiInits.entries()) {
+            System.out.println("  - " + entry.getKey() + " -> " + entry.getValue());
+        }
+        System.out.println(" DataOut :");
+        for (Entry<Node, Node> entry : peeling.dataOut.entries()) {
+            System.out.println("  - " + entry.getKey() + " -> " + entry.getValue());
+        }*/
+        rewirePeeling(peeling, loop, loopEnd);
+        if (compilation.compiler.isObserved()) {
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After rewirePeeling", loopEnd.graph(), true, false));
+        }
+    }
+
+    private static void rewirePeeling(PeelingResult peeling, Loop loop, FixedNode from) {
+        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();
+        }
+        NodeBitMap loopNodes = loop.nodes();
+        Node originalLast = from;
+        if (originalLast == loopBegin.loopEnd()) {
+            originalLast = loopBegin.loopEnd().singlePredecessor();
+        }
+        int size = originalLast.successors().size();
+        boolean found = false;
+        for (int i = 0; i < size; i++) {
+            Node sux = originalLast.successors().get(i);
+            if (sux == null) {
+                continue;
+            }
+            if (loopNodes.isMarked(sux)) {
+                assert !found;
+                peeling.end.successors().set(i, loopBegin.forwardEdge());
+                found = true;
+            }
+        }
+        assert found;
+        int phiInitIndex = loopBegin.phiPredecessorIndex(loopBegin.forwardEdge());
+        for (Entry<Node, Placeholder> entry : peeling.phis.entries()) {
+            Phi phi = (Phi) entry.getKey();
+            Placeholder p = entry.getValue();
+            p.replaceAndDelete(phi.valueAt(phiInitIndex));
+        }
+        for (Entry<Node, Node> entry : peeling.phiInits.entries()) {
+            Phi phi = (Phi) entry.getKey();
+            Node newInit = entry.getValue();
+            phi.setValueAt(phiInitIndex, (Value) newInit);
+        }
+
+        if (from == loopBegin.loopEnd()) {
+            for (LoopCounter counter : loopBegin.counters()) {
+                counter.setInit(new IntegerAdd(counter.kind, counter.init(), counter.stride(), graph));
+            }
+        }
+        NodeMap<NodeMap<Value>> newExitValues = graph.createNodeMap();
+        List<Node> exitPoints = new LinkedList<Node>();
+        for (Node exit : loop.exits()) {
+            exitPoints.add(exit);
+        }
+        for (Entry<Node, Placeholder> entry : peeling.exits.entries()) {
+            Placeholder original = (Placeholder) entry.getKey();
+            Placeholder newExit = entry.getValue();
+            FixedNode next = original.next();
+            EndNode oEnd = new EndNode(graph);
+            EndNode nEnd = new EndNode(graph);
+            Merge merge = new Merge(graph);
+            merge.setNext(next);
+            FrameState newState = newExit.stateAfter();
+            merge.addEnd(nEnd);
+            merge.setStateAfter(newState);
+            //newState.merge(merge, original.stateAfter());
+            merge.addEnd(oEnd);
+            original.setNext(oEnd);
+            newExit.setStateAfter(null);
+            newExit.replaceAndDelete(nEnd);
+
+            exitPoints.add(nEnd);
+        }
+
+        for (Entry<Node, Placeholder> entry : peeling.exits.entries()) {
+            Placeholder original = (Placeholder) entry.getKey();
+            EndNode oEnd = (EndNode) original.next();
+            Merge merge = oEnd.merge();
+            EndNode nEnd = merge.endAt(1 - merge.phiPredecessorIndex(oEnd));
+            FrameState newState = merge.stateAfter();
+            NodeArray oInputs = original.stateAfter().inputs();
+            NodeArray nInputs = newState.inputs();
+            int oSize = oInputs.size();
+            for (int i = 0; i < oSize; i++) {
+                Node newValue = nInputs.get(i);
+                Node originalValue = oInputs.get(i);
+                if (newValue != originalValue) {
+                    NodeMap<Value> phiMap = newExitValues.get(originalValue);
+                    if (phiMap == null) {
+                        phiMap = graph.createNodeMap();
+                        newExitValues.set(originalValue, phiMap);
+                    }
+                    phiMap.set(oEnd, (Value) originalValue);
+                    phiMap.set(nEnd, (Value) newValue);
+
+                    phiMap = newExitValues.get(newValue);
+                    if (phiMap == null) {
+                        phiMap = graph.createNodeMap();
+                        newExitValues.set(newValue, phiMap);
+                    }
+                    phiMap.set(oEnd, (Value) originalValue);
+                    phiMap.set(nEnd, (Value) newValue);
+                }
+            }
+            /*Placeholder original = (Placeholder) entry.getKey();
+            Merge merge = ((EndNode) original.next()).merge();
+            FrameState newState = merge.stateAfter();
+            NodeArray oInputs = original.stateAfter().inputs();
+            NodeArray nInputs = newState.inputs();
+            int oSize = oInputs.size();
+            for (int i = 0; i < oSize; i++) {
+                Node newValue = nInputs.get(i);
+                Node originalValue = oInputs.get(i);
+                if (newValue != originalValue && newValue instanceof Phi) {
+                    Phi newPhi = (Phi) newValue;
+                    assert newPhi.valueAt(1) == originalValue;
+                    NodeMap<Value> phiMap = newExitValues.get(originalValue);
+                    if (phiMap == null) {
+                        phiMap = graph.createNodeMap();
+                        newExitValues.set(originalValue, phiMap);
+                    }
+                    phiMap.set(merge, newPhi);
+                }
+            }*/
+        }
+        for (Entry<Node, NodeMap<Value>> entry : newExitValues.entries()) {
+            Value original = (Value) entry.getKey();
+            NodeMap<Value> pointToValue = entry.getValue();
+            for (Node exit : exitPoints) {
+                Node valueAtExit = pointToValue.get(exit);
+                if (valueAtExit == null) {
+                    pointToValue.set(exit, original);
+                }
+            }
+        }
+
+        replaceValuesAtLoopExits(newExitValues, loop, exitPoints);
+    }
+
+    private static void replaceValuesAtLoopExits(final NodeMap<NodeMap<Value>> newExitValues, Loop loop, List<Node> exitPoints) {
+        Graph graph = loop.loopBegin().graph();
+        final NodeMap<Node> colors = graph.createNodeMap();
+
+        // prepare inital colors
+        for (Node exitPoint : exitPoints) {
+                colors.set(exitPoint, exitPoint);
+        }
+
+        /*System.out.println("newExitValues");
+        for (Entry<Node, NodeMap<Value>> entry : newExitValues.entries()) {
+            System.out.println(" - " + entry.getKey() + " :");
+            for (Entry<Node, Value> entry2 : entry.getValue().entries()) {
+                System.out.println("    + " + entry2.getKey() + " -> " + entry2.getValue());
+            }
+        }*/
+
+        // color
+        GraphUtil.colorCFGDown(colors, new ColoringLambda<Node>() {
+            @Override
+            public Node color(Iterable<Node> incomming, Merge merge) {
+                Node color = null;
+                for (Node c : incomming) {
+                    if (c == null) {
+                        return null;
+                    }
+                    if (color == null) {
+                        color = c;
+                    } else if (color != c) {
+                        return merge;
+                    }
+                }
+                return color;
+            }
+        });
+
+        final NodeBitMap inOrBefore = inOrBefore(loop);
+
+        GraalCompilation compilation = GraalCompilation.compilation();
+        if (compilation.compiler.isObserved()) {
+            Map<String, Object> debug = new HashMap<String, Object>();
+            debug.put("loopExits", colors);
+            debug.put("inOrBefore", inOrBefore);
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After coloring", graph, true, false, debug));
+        }
+
+        GraphUtil.splitFromColoring(colors, new ColorSplitingLambda<Node>(){
+            @Override
+            public void fixSplit(Node oldNode, Node newNode, Node color) {
+                this.fixNode(newNode, color);
+            }
+            private Value getValueAt(Node point, NodeMap<Value> valueMap, CiKind kind) {
+                Value value = valueMap.get(point);
+                if (value != null) {
+                    return value;
+                }
+                Merge merge = (Merge) point;
+                ArrayList<Value> values = new ArrayList<Value>(merge.phiPredecessorCount());
+                Value v = null;
+                boolean createPhi = false;
+                for (EndNode end : merge.cfgPredecessors()) {
+                    Value valueAt = getValueAt(colors.get(end), valueMap, kind);
+                    if (v == null) {
+                        v = valueAt;
+                    } else if (v != valueAt) {
+                        createPhi = true;
+                    }
+                    values.add(valueAt);
+                }
+                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) {
+                return !inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && !(n instanceof Local); //TODO (gd) hum
+            }
+            @Override
+            public void fixNode(Node node, Node color) {
+                for (int i = 0; i < node.inputs().size(); i++) {
+                    Node input = node.inputs().get(i);
+                    if (input == null || newExitValues.isNew(input)) {
+                        continue;
+                    }
+                    NodeMap<Value> valueMap = newExitValues.get(input);
+                    if (valueMap != null) {
+                        Value replacement = getValueAt(color, valueMap, ((Value) input).kind);
+                        //if (!(replacement instanceof Phi && replacement == node)) { // handle the Phi that were created when merging loop exits
+                            node.inputs().set(i, replacement);
+                        //}
+                    }
+                }
+            }
+            @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()) {
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After split from colors", graph, true, false));
+        }
+    }
+
+    private static PeelingResult preparePeeling(Loop loop, FixedNode from) {
+        LoopBegin loopBegin = loop.loopBegin();
+        Graph graph = loopBegin.graph();
+        NodeBitMap marked = computeLoopNodesFrom(loopBegin, from);
+        if (from == loopBegin.loopEnd()) {
+            marked.clear(from);
+        }
+        marked.clear(loopBegin);
+        Map<Node, Node> replacements = new HashMap<Node, Node>();
+        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());
+                Placeholder p = new Placeholder(graph);
+                replacements.put(exit, p);
+                exits.set(exit, p);
+            }
+        }
+
+        for (Node n : marked) {
+            if (n instanceof StateSplit) {
+                FrameState stateAfter = ((StateSplit) n).stateAfter();
+                if (stateAfter != null) {
+                    marked.mark(stateAfter);
+                }
+            }
+            if (n instanceof Phi && ((Phi) n).merge() == loopBegin) {
+                Placeholder p = new Placeholder(graph);
+                replacements.put(n, p);
+                phis.set(n, p);
+                marked.clear(n);
+            }
+            for (Node input : n.dataInputs()) {
+                if (!marked.isMarked(input) && (!(input instanceof Phi) || ((Phi) input).merge() != loopBegin)) {
+                    replacements.put(input, input);
+                }
+            }
+        }
+
+        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, "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()) {
+                if (!marked.isMarked(usage)
+                                && !loop.nodes().isNew(usage) && loop.nodes().isMarked(usage)
+                                && !((usage instanceof Phi) || ((Phi) usage).merge() != loopBegin)) {
+                    dataOut.set(n, duplicates.get(n));
+                    break;
+                }
+            }
+        }
+        NodeMap<Node> phiInits = graph.createNodeMap();
+        int backIndex = loopBegin.phiPredecessorIndex(loopBegin.loopEnd());
+        int fowardIndex = loopBegin.phiPredecessorIndex(loopBegin.forwardEdge());
+        for (Phi phi : loopBegin.phis()) {
+            Value backValue = phi.valueAt(backIndex);
+            if (marked.isMarked(backValue)) {
+                phiInits.set(phi, duplicates.get(backValue));
+            } else if (backValue instanceof Phi && ((Phi) backValue).merge() == loopBegin) {
+                Phi backPhi = (Phi) backValue;
+                phiInits.set(phi, backPhi.valueAt(fowardIndex));
+            }
+        }
+
+        FixedNode newBegin = (FixedNode) duplicates.get(loopBegin.next());
+        FixedNode newFrom = (FixedNode) duplicates.get(from == loopBegin.loopEnd() ? from.singlePredecessor() : from);
+        return new PeelingResult(newBegin, newFrom, exits, phis, phiInits, dataOut);
+    }
+
+    private static NodeBitMap inOrBefore(Loop loop) {
+        Graph graph = loop.loopBegin().graph();
+        NodeBitMap inOrBefore = graph.createNodeBitMap();
+        NodeFlood work = graph.createNodeFlood();
+        work.addAll(loop.nodes());
+        for (Node n : work) {
+            inOrBefore.mark(n);
+            for (Node pred : n.predecessors()) {
+                work.add(pred);
+            }
+            for (Node in : n.inputs()) {
+                if (in != null) {
+                    work.add(in);
+                }
+            }
+        }
+        return inOrBefore;
+    }
 }
diff -r 46fe56f202a4 -r 25b5ec0568e6 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java	Tue Jun 28 14:17:06 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java	Tue Jun 28 16:45:48 2011 +0200
@@ -420,6 +420,15 @@
         return null;
     }
 
+    public StateSplit stateSplit() {
+        for (Node n : usages()) {
+            if (n instanceof StateSplit) {
+                return (StateSplit) n;
+            }
+        }
+        return null;
+    }
+
     /**
      * The interface implemented by a client of {@link FrameState#forEachPhi(Merge, PhiProcedure)} and
      * {@link FrameState#forEachLivePhi(Merge, PhiProcedure)}.
@@ -467,7 +476,7 @@
 
     @Override
     public String toString() {
-        StringBuilder sb = new StringBuilder();
+        /*StringBuilder sb = new StringBuilder();
         String nl = String.format("%n");
         sb.append("[bci: ").append(bci).append("]").append(nl);
         for (int i = 0; i < localsSize(); ++i) {
@@ -482,7 +491,8 @@
             Value value = lockAt(i);
             sb.append(String.format("  lock[%d] = %-8s : %s%n", i, value == null ? "bogus" : value.kind.javaName, value));
         }
-        return sb.toString();
+        return sb.toString();*/
+        return super.toString();
     }
 
     @Override
diff -r 46fe56f202a4 -r 25b5ec0568e6 src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalColoringFilter.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalColoringFilter.java	Tue Jun 28 16:45:48 2011 +0200
@@ -0,0 +1,79 @@
+/*
+ * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+package com.sun.hotspot.igv.graal.filters;
+
+import com.sun.hotspot.igv.data.Properties;
+import com.sun.hotspot.igv.filter.AbstractFilter;
+import com.sun.hotspot.igv.graph.Diagram;
+import com.sun.hotspot.igv.graph.Figure;
+import java.awt.Color;
+import java.util.List;
+
+public class GraalColoringFilter extends AbstractFilter {
+    
+    private String colorName;
+
+    public GraalColoringFilter(String colorName) {
+        this.colorName = colorName;
+    }
+
+    public String getName() {
+        return "Graal Coloring Filter (" + colorName + ")";
+    }
+
+    public void apply(Diagram d) {
+        List<Figure> figures = d.getFigures();
+        int colors = 0;
+        for (Figure f : figures) {
+            Properties p = f.getProperties();
+            final String prop = p.get(colorName + "Color");
+            if (prop == null) {
+                continue;
+            }
+            try {
+                int color = Integer.parseInt(prop);
+                if (color > colors) {
+                    colors = color;
+                }
+            } catch (NumberFormatException nfe) {
+                // nothing to do
+            }
+        }
+        colors++;
+        for (Figure f : figures) {
+            Properties p = f.getProperties();
+            final String prop = p.get(colorName + "Color");
+            if (prop == null) {
+                continue;
+            }
+            try {
+                int color = Integer.parseInt(prop);
+                Color c = Color.getHSBColor((float) color / colors, 1.0f, 0.7f);
+                f.setColor(c);
+            } catch (NumberFormatException nfe) {
+                // nothing to do
+            }
+        }
+    }
+}
diff -r 46fe56f202a4 -r 25b5ec0568e6 src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/color.filter
--- a/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/color.filter	Tue Jun 28 14:17:06 2011 +0200
+++ b/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/color.filter	Tue Jun 28 16:45:48 2011 +0200
@@ -1,9 +1,11 @@
 colorize("name", ".*", white);
-colorize("name", "StartNode|EndNode|LoopBegin|LoopEnd|Return", red);
+colorize("name", "StartNode|EndNode|LoopBegin|LoopEnd|Return", orange);
 colorize("name", "Phi:.*", magenta);
 colorize("name", "FrameState@.*", new java.awt.Color(0.5, 0.8, 1.0));
 colorize("name", "If", pink);
 colorize("name", "const.*", new java.awt.Color(0.7, 0.7, 0.7));
 colorize("name", "Local", new java.awt.Color(0.85, 0.85, 0.85));
 colorize("name", "\\+|-|\\*|/", cyan);
-colorize("name", "Comp .*", yellow);
\ No newline at end of file
+colorize("name", "Comp .*", yellow);
+
+colorize("notInOwnBlock", "true", red);
\ No newline at end of file