# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1312194465 -7200
# Node ID 2c5b4dd06d3be241106fa4befb5b6198a4eb82a1
# Parent  9498c20925de797d724c0731a2b4f0e81dc0d59f# Parent  be4ca325525a02339d7ad318f40210c6d382971e
Merge

diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Mon Aug 01 12:27:45 2011 +0200
@@ -166,9 +166,10 @@
     public static boolean OptReadElimination                 = ____;
     public static boolean OptGVN                             = ____;
     public static boolean Rematerialize                      = ____;
+    public static boolean SplitMaterialization               = ____;
     public static boolean OptCanonicalizer                   = true;
     public static boolean OptLoops                           = ____;
-    public static boolean OptOptimisticSchedule              = ____;
+    public static boolean ScheduleOutOfLoops                 = true;
     public static boolean OptReorderLoops                    = ____;
     public static boolean LoopPeeling                        = ____;
     public static boolean LoopInversion                      = ____;
diff -r be4ca325525a -r 2c5b4dd06d3b 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	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java	Mon Aug 01 12:27:45 2011 +0200
@@ -121,12 +121,21 @@
         stream.printf(" <graph name='%s'>%n", escape(title));
         noBlockNodes.clear();
         IdentifyBlocksPhase schedule = null;
-        try {
-            schedule = new IdentifyBlocksPhase(true);
-            schedule.apply(graph, false, false);
-        } catch (Throwable t) {
-            // nothing to do here...
-            //t.printStackTrace();
+        if (debugObjects != null) {
+            for (Object obj : debugObjects.values()) {
+                if (obj instanceof IdentifyBlocksPhase) {
+                    schedule = (IdentifyBlocksPhase) obj;
+                }
+            }
+        }
+        if (schedule == null) {
+            try {
+                schedule = new IdentifyBlocksPhase(true, false);
+                schedule.apply(graph, false, false);
+            } catch (Throwable t) {
+                // nothing to do here...
+                //t.printStackTrace();
+            }
         }
         List<Loop> loops = null;
         try {
diff -r be4ca325525a -r 2c5b4dd06d3b 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	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Mon Aug 01 12:27:45 2011 +0200
@@ -504,9 +504,11 @@
         lir.branch(cond, trueSuccessor);
     }
 
-    public void emitBooleanBranch(Node node, LIRBlock trueSuccessor, LIRBlock falseSuccessor, LIRDebugInfo info) {
+    public void emitBooleanBranch(BooleanNode node, LIRBlock trueSuccessor, LIRBlock falseSuccessor, LIRDebugInfo info) {
         if (node instanceof NegateBooleanNode) {
             emitBooleanBranch(((NegateBooleanNode) node).value(), falseSuccessor, trueSuccessor, info);
+        } else if (node instanceof IsNonNull) {
+            emitIsNonNullBranch((IsNonNull) node, trueSuccessor, falseSuccessor);
         } else if (node instanceof Compare) {
             emitCompare((Compare) node, trueSuccessor, falseSuccessor);
         } else if (node instanceof InstanceOf) {
@@ -518,6 +520,25 @@
         }
     }
 
+    private void emitIsNonNullBranch(IsNonNull node, LIRBlock trueSuccessor, LIRBlock falseSuccessor) {
+        Condition cond = Condition.NE;
+        if (trueSuccessor == null) {
+            cond = cond.negate();
+            trueSuccessor = falseSuccessor;
+            falseSuccessor = null;
+        }
+
+        LIRItem xitem = new LIRItem(node.object(), this);
+        xitem.loadItem();
+
+        lir.cmp(cond, xitem.result(), CiConstant.NULL_OBJECT);
+        lir.branch(cond, trueSuccessor);
+
+        if (falseSuccessor != null) {
+            lir.jump(falseSuccessor);
+        }
+    }
+
     private void emitInstanceOf(TypeCheck x, LIRBlock trueSuccessor, LIRBlock falseSuccessor, LIRDebugInfo info) {
         XirArgument obj = toXirArgument(x.object());
         XirSnippet snippet = xir.genInstanceOf(site(x), obj, toXirArgument(x.targetClassInstruction()), x.targetClass());
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/globalstub/GlobalStub.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/globalstub/GlobalStub.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/globalstub/GlobalStub.java	Mon Aug 01 12:27:45 2011 +0200
@@ -40,9 +40,6 @@
 public class GlobalStub {
 
     public enum Id {
-
-        fneg(Float, Float),
-        dneg(Double, Double),
         f2i(Int, Float),
         f2l(Long, Float),
         d2i(Int, Double),
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Mon Aug 01 12:27:45 2011 +0200
@@ -131,7 +131,7 @@
             new GlobalValueNumberingPhase().apply(graph);
             if (GraalOptions.Rematerialize) {
                 //new Rematerialization2Phase().apply(graph);
-                new RematerializationPhase().apply(graph);
+                //new RematerializationPhase().apply(graph);
             }
             graph.stopRecordModifications();
         }
@@ -143,7 +143,7 @@
                 graph.recordModifications(EdgeType.USAGES);
                 new GlobalValueNumberingPhase().apply(graph);
                 if (GraalOptions.Rematerialize) {
-                    new RematerializationPhase().apply(graph);
+                    //new RematerializationPhase().apply(graph);
                 }
                 graph.stopRecordModifications();
             }
@@ -156,6 +156,12 @@
         schedule.apply(graph);
         compilation.stats.loopCount = schedule.loopCount();
 
+        if (compilation.compiler.isObserved()) {
+            Map<String, Object> debug = new HashMap<String, Object>();
+            debug.put("schedule", schedule);
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After IdentifyBlocksPhase", graph, true, false, debug));
+        }
+
 
         List<Block> blocks = schedule.getBlocks();
         List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>();
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java	Mon Aug 01 12:27:45 2011 +0200
@@ -170,7 +170,12 @@
         @Override
         public Node canonical(Node node) {
             Compare compare = (Compare) node;
-            if (compare.x().isConstant() && compare.y().isConstant()) {
+            if (compare.x().isConstant() && !compare.y().isConstant()) { // move constants to the left (y)
+                Value x = compare.x();
+                compare.setX(compare.y());
+                compare.setY(x);
+                compare.condition = compare.condition.mirror();
+            } else if (compare.x().isConstant() && compare.y().isConstant()) {
                 CiConstant constX = compare.x().asConstant();
                 CiConstant constY = compare.y().asConstant();
                 Boolean result = compare.condition().foldCondition(constX, constY, ((CompilerGraph) node.graph()).runtime());
@@ -184,18 +189,36 @@
                         TTY.println("if not removed %s %s %s (%s %s)", constX, compare.condition(), constY, constX.kind, constY.kind);
                     }
                 }
-            } else if (compare.x().isConstant() && compare.y() instanceof MaterializeNode) {
-                return optimizeMaterialize(compare, compare.x().asConstant(), (MaterializeNode) compare.y());
-            } else if (compare.y().isConstant() && compare.x() instanceof MaterializeNode) {
-                return optimizeMaterialize(compare, compare.y().asConstant(), (MaterializeNode) compare.x());
-            } else if (compare.x().isConstant() && compare.y() instanceof NormalizeCompare) {
-                return optimizeNormalizeCmp(compare, compare.x().asConstant(), (NormalizeCompare) compare.y());
-            } else if (compare.y().isConstant() && compare.x() instanceof NormalizeCompare) {
-                return optimizeNormalizeCmp(compare, compare.y().asConstant(), (NormalizeCompare) compare.x());
             }
+
+            if (compare.y().isConstant()) {
+                if (compare.x() instanceof MaterializeNode) {
+                    return optimizeMaterialize(compare, compare.y().asConstant(), (MaterializeNode) compare.x());
+                } else if (compare.x() instanceof NormalizeCompare) {
+                    return optimizeNormalizeCmp(compare, compare.y().asConstant(), (NormalizeCompare) compare.x());
+                }
+            }
+
             if (compare.x() == compare.y() && compare.x().kind != CiKind.Float && compare.x().kind != CiKind.Double) {
                 return Constant.forBoolean(compare.condition().check(1, 1), compare.graph());
             }
+            if ((compare.condition == Condition.NE || compare.condition == Condition.EQ) && compare.x().kind == CiKind.Object) {
+                Value object = null;
+                if (compare.x().isNullConstant()) {
+                    object = compare.y();
+                } else if (compare.y().isNullConstant()) {
+                    object = compare.x();
+                }
+                if (object != null) {
+                    IsNonNull nonNull =  new IsNonNull(object, compare.graph());
+                    if (compare.condition == Condition.NE) {
+                        return nonNull;
+                    } else {
+                        assert compare.condition == Condition.EQ;
+                        return new NegateBooleanNode(nonNull, compare.graph());
+                    }
+                }
+            }
             return compare;
         }
 
@@ -206,7 +229,7 @@
                     if (compare.condition == Condition.NE) {
                         isFalseCheck = !isFalseCheck;
                     }
-                    Value result = materializeNode.value();
+                    BooleanNode result = materializeNode.value();
                     if (isFalseCheck) {
                         result = new NegateBooleanNode(result, compare.graph());
                     }
diff -r be4ca325525a -r 2c5b4dd06d3b 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	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java	Mon Aug 01 12:27:45 2011 +0200
@@ -142,7 +142,7 @@
         return new Iterable<Node>() {
             @Override
             public Iterator<Node> iterator() {
-                return new StateSplit.FilteringIterator(dataUsages, LoopBegin.class);
+                return new StateSplit.FilteringIterator(dataUsages, LoopEnd.class);
             }
         };
     }
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java	Mon Aug 01 12:27:45 2011 +0200
@@ -84,11 +84,6 @@
     }
 
     @Override
-    public String toString() {
-        return "LoopEnd:" + super.toString();
-    }
-
-    @Override
     public Iterable< ? extends Node> dataInputs() {
         return Collections.emptyList();
     }
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MaterializeNode.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MaterializeNode.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MaterializeNode.java	Mon Aug 01 12:27:45 2011 +0200
@@ -49,15 +49,15 @@
     /**
      * The instruction which produces the input value to this instruction.
      */
-     public Value value() {
-        return (Value) inputs().get(super.inputCount() + INPUT_VALUE);
+     public BooleanNode value() {
+        return (BooleanNode) inputs().get(super.inputCount() + INPUT_VALUE);
     }
 
-    public void setValue(Value n) {
+    public void setValue(BooleanNode n) {
         inputs().set(super.inputCount() + INPUT_VALUE, n);
     }
 
-    public MaterializeNode(Value value, Graph graph) {
+    public MaterializeNode(BooleanNode value, Graph graph) {
         super(CiKind.Int, INPUT_COUNT, SUCCESSOR_COUNT, graph);
         setValue(value);
     }
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java	Mon Aug 01 12:27:45 2011 +0200
@@ -128,7 +128,7 @@
                     case Double: return Constant.forDouble(-x.asConstant().asDouble(), graph);
                 }
             }
-            if (x instanceof Negate && (x.kind == CiKind.Int || x.kind == CiKind.Long)) {
+            if (x instanceof Negate) {
                 return ((Negate) x).x();
             }
             return negate;
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NegateBooleanNode.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NegateBooleanNode.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NegateBooleanNode.java	Mon Aug 01 12:27:45 2011 +0200
@@ -46,15 +46,15 @@
     /**
      * The instruction that produces the array object.
      */
-     public Value value() {
-        return (Value) inputs().get(super.inputCount() + INPUT_NODE);
+     public BooleanNode value() {
+        return (BooleanNode) inputs().get(super.inputCount() + INPUT_NODE);
     }
 
-    public Value setValue(Value n) {
-        return (Value) inputs().set(super.inputCount() + INPUT_NODE, n);
+    public BooleanNode setValue(BooleanNode n) {
+        return (BooleanNode) inputs().set(super.inputCount() + INPUT_NODE, n);
     }
 
-    public NegateBooleanNode(Value value, Graph graph) {
+    public NegateBooleanNode(BooleanNode value, Graph graph) {
         super(CiKind.Int, INPUT_COUNT, SUCCESSOR_COUNT, graph);
         setValue(value);
     }
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRList.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRList.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRList.java	Mon Aug 01 12:27:45 2011 +0200
@@ -104,9 +104,8 @@
         append(new LIRLabel(lbl));
     }
 
-    public void negate(CiValue src, CiValue dst, GlobalStub globalStub) {
+    public void negate(CiValue src, CiValue dst) {
         LIRNegate op = new LIRNegate(src, dst);
-        op.globalStub = globalStub;
         append(op);
     }
 
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRNegate.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRNegate.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRNegate.java	Mon Aug 01 12:27:45 2011 +0200
@@ -22,7 +22,6 @@
  */
 package com.oracle.max.graal.compiler.lir;
 
-import com.oracle.max.graal.compiler.globalstub.*;
 import com.sun.cri.ci.*;
 
 /**
@@ -33,8 +32,6 @@
  */
 public class LIRNegate extends LIROp1 {
 
-    public GlobalStub globalStub;
-
     /**
      * Constructs a new instruction LIRNegate for a given operand.
      *
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Mon Aug 01 12:27:45 2011 +0200
@@ -33,13 +33,15 @@
     private int blockID;
     private final List<Block> successors = new ArrayList<Block>();
     private final List<Block> predecessors = new ArrayList<Block>();
+    private final List<Block> dominated = new ArrayList<Block>();
     private List<Node> instructions = new ArrayList<Node>();
     private Block dominator;
     private Block javaBlock;
-    private final List<Block> dominators = new ArrayList<Block>();
     private Anchor anchor;
+    private EndNode end;
     private int loopDepth = 0;
     private int loopIndex = -1;
+    private double probability;
 
     private Node firstNode;
     private Node lastNode;
@@ -53,6 +55,14 @@
         this.anchor = null;
     }
 
+    public EndNode end() {
+        return end;
+    }
+
+    public void setEnd(EndNode end) {
+        this.end = end;
+    }
+
     public Block javaBlock() {
         return javaBlock;
     }
@@ -81,6 +91,17 @@
         loopIndex = i;
     }
 
+    public double probability() {
+        return probability;
+    }
+
+
+    public void setProbability(double probability) {
+        if (probability > this.probability) {
+            this.probability = probability;
+        }
+    }
+
     public Anchor createAnchor() {
         if (anchor == null) {
             if (firstNode instanceof Anchor) {
@@ -131,11 +152,11 @@
         assert this.dominator == null;
         assert dominator != null;
         this.dominator = dominator;
-        dominator.dominators.add(this);
+        dominator.dominated.add(this);
     }
 
-    public List<Block> getDominators() {
-        return Collections.unmodifiableList(dominators);
+    public List<Block> getDominated() {
+        return Collections.unmodifiableList(dominated);
     }
 
     public List<Node> getInstructions() {
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Mon Aug 01 12:27:45 2011 +0200
@@ -33,15 +33,29 @@
 
 
 public class IdentifyBlocksPhase extends Phase {
+    private static final double LIVE_RANGE_COST_FACTOR = 0.05;
+    private static final double MATERIALIZATION_COST_FACTOR = 1.0 - LIVE_RANGE_COST_FACTOR;
+
     private final List<Block> blocks = new ArrayList<Block>();
     private NodeMap<Block> nodeToBlock;
+    private NodeMap<Block> earliestCache;
     private Graph graph;
     private boolean scheduleAllNodes;
+    private boolean splitMaterialization;
     private int loopCount;
 
     public IdentifyBlocksPhase(boolean scheduleAllNodes) {
+        this(scheduleAllNodes, GraalOptions.SplitMaterialization && filter());
+    }
+
+    public static boolean filter() {
+        return true; //GraalCompilation.compilation().method.name().contains("mergeOrClone");
+    }
+
+    public IdentifyBlocksPhase(boolean scheduleAllNodes, boolean splitMaterialization) {
         super(scheduleAllNodes ? "FullSchedule" : "PartSchedule", false);
         this.scheduleAllNodes = scheduleAllNodes;
+        this.splitMaterialization = splitMaterialization;
     }
 
 
@@ -49,6 +63,7 @@
     protected void run(Graph graph) {
         this.graph = graph;
         nodeToBlock = graph.createNodeMap();
+        earliestCache = graph.createNodeMap();
         identifyBlocks();
     }
 
@@ -91,6 +106,10 @@
 
             }
         }
+        if (n instanceof EndNode) {
+            assert b.end() == null || n == b.end();
+            b.setEnd((EndNode) n);
+        }
         if (b.lastNode() == null) {
             b.setFirstNode(n);
             b.setLastNode(n);
@@ -118,7 +137,7 @@
         System.out.println(nodeToBlock);
         System.out.println("Blocks :");
         for (Block b : blocks) {
-            System.out.println(b + " [S:" + b.getSuccessors() + ", P:" + b.getPredecessors() + ", D:" + b.getDominators());
+            System.out.println(b + " [S:" + b.getSuccessors() + ", P:" + b.getPredecessors() + ", D:" + b.getDominated());
             System.out.println("  f " + b.firstNode());
             for (Node n : b.getInstructions()) {
                 System.out.println("  - " + n);
@@ -140,6 +159,9 @@
                         block = null;
                     }
                     block = assignBlockNew(currentNode, block);
+                    if (currentNode instanceof FixedNode) {
+                        block.setProbability(((FixedNode) currentNode).probability());
+                    }
                     if (currentNode.predecessors().size() == 0) {
                         // Either dead code or at a merge node => stop iteration.
                         break;
@@ -175,7 +197,7 @@
 
         if (scheduleAllNodes) {
             computeLoopInformation(); // Will make the graph cyclic.
-            assignLatestPossibleBlockToNodes();
+            assignBlockToNodes();
             sortNodesWithinBlocks();
         } else {
             computeJavaBlocks();
@@ -283,132 +305,353 @@
         }
     }
 
-    private void assignLatestPossibleBlockToNodes() {
+    private void assignBlockToNodes() {
         for (Node n : graph.getNodes()) {
-            assignLatestPossibleBlockToNode(n);
+            assignBlockToNode(n);
         }
     }
 
-    private Block assignLatestPossibleBlockToNode(Node n) {
+    private void assignBlockToNode(Node n) {
         if (n == null) {
-            return null;
+            return;
         }
 
         assert !n.isDeleted();
 
         Block prevBlock = nodeToBlock.get(n);
         if (prevBlock != null) {
-            return prevBlock;
-        }
-
-        Block block = null;
-        for (Node succ : n.successors()) {
-            block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ));
+            return;
         }
-        for (Node usage : n.usages()) {
-            if (usage instanceof Phi) {
-                Phi phi = (Phi) usage;
-                Merge merge = phi.merge();
-                Block mergeBlock = nodeToBlock.get(merge);
-                assert mergeBlock != null : "no block for merge " + merge.id();
-                for (int i = 0; i < phi.valueCount(); ++i) {
-                    if (phi.valueAt(i) == n) {
-                        if (mergeBlock.getPredecessors().size() <= i) {
-                            TTY.println(merge.toString());
-                            TTY.println(phi.toString());
-                            TTY.println(merge.phiPredecessors().toString());
-                            TTY.println(phi.inputs().toString());
-                            TTY.println("value count: " + phi.valueCount());
-                        }
-                        block = getCommonDominator(block, mergeBlock.getPredecessors().get(i));
-                    }
-                }
-            } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
-                Merge merge = ((FrameState) usage).block();
-                for (Node pred : merge.cfgPredecessors()) {
-                    block = getCommonDominator(block, nodeToBlock.get(pred));
-                }
-            } else if (usage instanceof LoopCounter) {
-                LoopCounter counter = (LoopCounter) usage;
-                if (n == counter.init() || n == counter.stride()) {
-                    LoopBegin loopBegin = counter.loopBegin();
-                    Block mergeBlock = nodeToBlock.get(loopBegin);
-                    block = getCommonDominator(block, mergeBlock.dominator());
-                }
+        //TTY.println("Earliest for " + n + " : " + earliest);
+        // if in CFG, schedule at the latest position possible in the outermost loop possible
+        // if floating, use rematerialization to place the node, it tries to compute the value only when it will be used,
+        // in the block with the smallest probability (outside of loops), while minimizing live ranges
+        if (!splitMaterialization || noRematerialization(n) || n.predecessors().size() > 0 || nonNullSuccessorCount(n) > 0) {
+            Block latestBlock = latestBlock(n);
+            //TTY.println("Latest for " + n + " : " + latestBlock);
+            Block block;
+            if (latestBlock == null) {
+                block = earliestBlock(n);
+            } else if (GraalOptions.ScheduleOutOfLoops) {
+                block = scheduleOutOfLoops(n, latestBlock, earliestBlock(n));
             } else {
-                block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage));
+                block = latestBlock;
+            }
+            nodeToBlock.set(n, block);
+            block.getInstructions().add(n);
+        } else {
+            GraalTimers timer = GraalTimers.get("earliest");
+            timer.start();
+            Block earliest = earliestBlock(n);
+            timer.stop();
+            Map<Block, Set<Usage>> usages = computeUsages(n, earliest);
+            if (usages.isEmpty()) {
+                nodeToBlock.set(n, earliest);
+                earliest.getInstructions().add(n);
+            } else {
+                maybeMaterialize(n, earliest, usages, false);
             }
         }
+    }
+
+    private int nonNullSuccessorCount(Node n) {
+        int suxCount = 0;
+        for (Node sux : n.successors()) {
+            if (sux != null) {
+                suxCount++;
+            }
+        }
+        return suxCount;
+    }
 
 
-        if (block != null) {
-            if (GraalOptions.OptOptimisticSchedule) {
-                block = scheduleOutOfLoops(n, block);
+    private void maybeMaterialize(Node node, Block block, Map<Block, Set<Usage>> usages, boolean materializedInDominator) {
+        Set<Usage> blockUsages = usages.get(block);
+        if (blockUsages == null || blockUsages.isEmpty()) {
+            return;
+        }
+        boolean forced = false;
+        if (!materializedInDominator) {
+            for (Usage usage : blockUsages) {
+                if (usage.block == block) {
+                    forced = true;
+                    break;
+                }
             }
+        }
+        //TODO (gd) if materializedInDominator, compare cost of materialization to cost of current live range instead
+        if (forced || materializationCost(block, blockUsages) < materializationCostAtChildren(block, usages)) {
+            Node n;
+            if (nodeToBlock.get(node) == null) {
+                n = node;
+            } else {
+                n = node.copy();
+                for (int i = 0; i < node.inputs().size(); i++) {
+                    n.inputs().set(i, node.inputs().get(i));
+                }
+                for (Usage usage : blockUsages) {
+                    patch(usage, node, n);
+                }
+                //TTY.println("> Rematerialized " + node + " (new node id = " + n.id() + ") in " + block);
+                GraalMetrics.Rematerializations++;
+                nodeToBlock.grow(n);
+            }
+            materializedInDominator = true;
             nodeToBlock.set(n, block);
             block.getInstructions().add(n);
         }
-        return block;
+        if (!materializedInDominator || GraalOptions.Rematerialize) {
+            for (Block child : block.getDominated()) {
+                maybeMaterialize(node, child, usages, materializedInDominator);
+            }
+        }
     }
 
-    private Block scheduleOutOfLoops(Node n, Block latestBlock) {
-        Block cur = latestBlock;
-        while (cur.loopDepth() != 0) {
-            if (cur.isLoopHeader()) {
-                assert cur.getPredecessors().size() == 2 : cur.getPredecessors().size();
-                if (canSchedule(n, cur.getPredecessors().get(0))) {
-                   // TTY.println("can schedule out of loop!" + n);
-                    return scheduleOutOfLoops(n, cur.getPredecessors().get(0));
-                } else {
-                    break;
-                }
-            }
-            Block prev = cur;
-            cur = cur.dominator();
-
-            // This must be a loop exit.
-            if (cur.loopDepth() > prev.loopDepth()) {
-//                TTY.println("break out because of different loop depth");
-                break;
+    private double materializationCostAtChildren(Block block, Map<Block, Set<Usage>> usages) {
+        double cost = 0.0;
+        for (Block child : block.getDominated()) {
+            Set<Usage> blockUsages = usages.get(child);
+            if (blockUsages != null && !blockUsages.isEmpty()) { // XXX should never be empty if not null
+                cost += materializationCost(child, blockUsages);
             }
         }
-        return latestBlock;
+        return cost;
+    }
+
+    private double materializationCost(Block block, Set<Usage> usages) {
+        //TODO node cost
+        return /*LIVE_RANGE_COST_FACTOR * liveRange(block, usages) + MATERIALIZATION_COST_FACTOR **/ block.probability() * 1.0;
     }
 
-    private boolean canSchedule(Node n, Block block) {
-        Set<Block> allowedBlocks = new HashSet<Block>();
-        Block cur = block;
-        while (cur != null) {
-            allowedBlocks.add(cur);
-            cur = cur.dominator();
+
+    private Block latestBlock(Node n) {
+        Block block = null;
+        for (Node succ : n.successors()) {
+            if (succ == null) {
+                continue;
+            }
+            assignBlockToNode(succ);
+            block = getCommonDominator(block, nodeToBlock.get(succ));
         }
-        // Now we know the allowed blocks for inputs and predecessors.
-        return checkNodesAbove(allowedBlocks, n);
+        ensureScheduledUsages(n);
+        CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(block);
+        for (Node usage : n.usages()) {
+            blocksForUsage(n, usage, cdbc);
+        }
+        return cdbc.block;
     }
 
-    private boolean checkNodesAbove(Set<Block> allowedBlocks, Node n) {
-        if (n == null) {
-            return true;
+    private class CommonDominatorBlockClosure implements BlockClosure {
+        public Block block;
+        public CommonDominatorBlockClosure(Block block) {
+            this.block = block;
         }
-
-        if (nodeToBlock.get(n) != null) {
-            return allowedBlocks.contains(nodeToBlock.get(n));
-        } else {
-            assert !(n instanceof Phi) : ((Phi) n).merge();
-            for (Node input : n.inputs()) {
-                if (!checkNodesAbove(allowedBlocks, input)) {
-                    return false;
-                }
-            }
-            for (Node pred : n.predecessors()) {
-                if (!checkNodesAbove(allowedBlocks, pred)) {
-                    return false;
-                }
-            }
-            return true;
+        @Override
+        public void apply(Block block) {
+            this.block = getCommonDominator(this.block, block);
         }
     }
 
+    private Block earliestBlock(Node n) {
+        Block earliest = nodeToBlock.get(n);
+        if (earliest != null) {
+            return earliest;
+        }
+        earliest = earliestCache.get(n);
+        if (earliest != null) {
+            return earliest;
+        }
+        BitMap bits = new BitMap(blocks.size());
+        ArrayList<Node> before = new ArrayList<Node>(n.predecessors().size() + n.inputs().size());
+        before.addAll(n.predecessors());
+        before.addAll(n.inputs());
+        for (Node pred : before) {
+            if (pred == null) {
+                continue;
+            }
+            Block b = earliestBlock(pred);
+            if (!bits.get(b.blockID())) {
+                earliest = b;
+                do {
+                    bits.set(b.blockID());
+                    b = b.dominator();
+                } while(b != null && !bits.get(b.blockID()));
+            }
+        }
+        if (earliest == null) {
+            Block start = nodeToBlock.get(graph.start());
+            assert start != null;
+            return start;
+        }
+        earliestCache.set(n, earliest);
+        return earliest;
+    }
+
+
+    private Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
+        assert latestBlock != null : "no latest : " + n;
+        Block cur = latestBlock;
+        Block prevDepth = latestBlock;
+        while (cur.loopDepth() != 0 && cur != earliest && cur.dominator() != null && cur.dominator().loopDepth() <= cur.loopDepth()) {
+            Block dom = cur.dominator();
+            if (dom.loopDepth() < prevDepth.loopDepth()) {
+                prevDepth = dom;
+            }
+            cur = dom;
+        }
+        return prevDepth;
+    }
+
+    private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
+        if (usage instanceof Phi) {
+            Phi phi = (Phi) usage;
+            Merge merge = phi.merge();
+            Block mergeBlock = nodeToBlock.get(merge);
+            assert mergeBlock != null : "no block for merge " + merge.id();
+            for (int i = 0; i < phi.valueCount(); ++i) {
+                if (phi.valueAt(i) == node) {
+                    if (mergeBlock.getPredecessors().size() <= i) {
+                        TTY.println(merge.toString());
+                        TTY.println(phi.toString());
+                        TTY.println(merge.phiPredecessors().toString());
+                        TTY.println(phi.inputs().toString());
+                        TTY.println("value count: " + phi.valueCount());
+                    }
+                    closure.apply(mergeBlock.getPredecessors().get(i));
+                }
+            }
+        } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
+            Merge merge = ((FrameState) usage).block();
+            Block block = null;
+            for (Node pred : merge.cfgPredecessors()) {
+                block = getCommonDominator(block, nodeToBlock.get(pred));
+            }
+            closure.apply(block);
+        } else if (usage instanceof LoopCounter) {
+            LoopCounter counter = (LoopCounter) usage;
+            if (node == counter.init() || node == counter.stride()) {
+                LoopBegin loopBegin = counter.loopBegin();
+                Block mergeBlock = nodeToBlock.get(loopBegin);
+                closure.apply(mergeBlock.dominator());
+            }
+        } else {
+            assignBlockToNode(usage);
+            closure.apply(nodeToBlock.get(usage));
+        }
+    }
+
+    private void patch(Usage usage, Node original, Node patch) {
+        if (usage.node instanceof Phi) {
+            Phi phi = (Phi) usage.node;
+            Node pred;
+            Block phiBlock = nodeToBlock.get(phi);
+            if (phiBlock.isLoopHeader()) {
+                LoopBegin loopBegin = (LoopBegin) phiBlock.firstNode();
+                if (usage.block == phiBlock.dominator()) {
+                    pred = loopBegin.forwardEdge();
+                } else {
+                    assert usage.block == nodeToBlock.get(loopBegin.loopEnd());
+                    pred = loopBegin.loopEnd();
+                }
+            } else {
+                pred = usage.block.end();
+            }
+            int index = phi.merge().phiPredecessorIndex(pred);
+            phi.setValueAt(index, (Value) patch);
+        } else {
+            usage.node.inputs().replace(original, patch);
+        }
+    }
+
+    private void ensureScheduledUsages(Node node) {
+        //  assign block to all usages to ensure that any splitting/rematerialization is done on them
+        List<Node> usages = new ArrayList<Node>(node.usages());
+        for (Node usage : usages) {
+            assignBlockToNode(usage);
+        }
+        // now true usages are ready
+    }
+
+    private Map<Block, Set<Usage>> computeUsages(Node node, final Block from) { //TODO use a List instead of a Set here ?
+        final Map<Block, Set<Usage>> blockUsages = new HashMap<Block, Set<Usage>>();
+        ensureScheduledUsages(node);
+        for (final Node usage : node.dataUsages()) {
+            blocksForUsage(node, usage, new BlockClosure() {
+                @Override
+                public void apply(Block block) {
+                    addUsageToTree(usage, block, from, blockUsages);
+                }
+            });
+        }
+        /*TTY.println("Usages for " + node + " from " + from);
+        for (Entry<Block, Set<Usage>> entry : blockUsages.entrySet()) {
+            TTY.println(" - " + entry.getKey() + " :");
+            for (Usage usage : entry.getValue()) {
+                TTY.println(" + " + usage.node + " in  " + usage.block);
+            }
+        }*/
+        return blockUsages;
+    }
+
+    private void addUsageToTree(Node usage, Block usageBlock, Block from, Map<Block, Set<Usage>> blockUsages) {
+        Block current = usageBlock;
+        while (current != null) {
+            Set<Usage> usages = blockUsages.get(current);
+            if (usages == null) {
+                usages = new HashSet<Usage>();
+                blockUsages.put(current, usages);
+            }
+            usages.add(new Usage(usageBlock, usage));
+            if (current == from) {
+                current = null;
+            } else {
+                current = current.dominator();
+            }
+        }
+    }
+
+    private static class Usage {
+        public final Block block;
+        public final Node node;
+        public Usage(Block block, Node node) {
+            this.block = block;
+            this.node = node;
+        }
+    }
+
+    private boolean noRematerialization(Node n) {
+        return n instanceof Local || n instanceof LocationNode || n instanceof Constant || n instanceof StateSplit || n instanceof FrameState;
+    }
+
+    private double liveRange(Block from, Set<Usage> usages) {
+        BitMap subTree = new BitMap(blocks.size());
+        markSubTree(from, subTree);
+        double range = 0.0;
+        for (Usage usage : usages) {
+            range += markRangeUp(usage.block, subTree);
+        }
+        return range;
+    }
+
+    private void markSubTree(Block from, BitMap subTree) {
+        subTree.set(from.blockID());
+        for (Block b : from.getDominated()) {
+            markSubTree(b, subTree);
+        }
+    }
+
+    private double markRangeUp(Block from, BitMap subTree) {
+        int blockID = from.blockID();
+        if (!subTree.get(blockID)) {
+            return 0.0;
+        }
+        subTree.clear(blockID);
+        double range = from.probability() * (from.getInstructions().size() + 2);
+        for (Block pred : from.getPredecessors()) {
+            range += markRangeUp(pred, subTree);
+        }
+        return range;
+    }
 
     private Block getCommonDominator(Block a, Block b) {
         if (a == null) {
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64GlobalStubEmitter.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64GlobalStubEmitter.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64GlobalStubEmitter.java	Mon Aug 01 12:27:45 2011 +0200
@@ -46,8 +46,6 @@
     private static final long DoubleSignFlip = 0x8000000000000000L;
     private static final CiRegister convertArgument = AMD64.xmm0;
     private static final CiRegister convertResult = AMD64.rax;
-    private static final CiRegister negateArgument = AMD64.xmm0;
-    private static final CiRegister negateTemp = AMD64.xmm1;
 
     private TargetMethodAssembler tasm;
     private AMD64MacroAssembler asm;
@@ -118,12 +116,6 @@
             case d2l:
                 emitD2L();
                 break;
-            case fneg:
-                emitFNEG();
-                break;
-            case dneg:
-                emitDNEG();
-                break;
         }
 
         String name = "stub-" + stub;
@@ -251,30 +243,6 @@
         return result;
     }
 
-    private void negatePrologue() {
-        partialSavePrologue(negateArgument, negateTemp);
-        loadArgument(0, negateArgument);
-    }
-
-    private void negateEpilogue() {
-        storeArgument(0, negateArgument);
-        epilogue();
-    }
-
-    private void emitDNEG() {
-        negatePrologue();
-        asm.movsd(negateTemp, tasm.recordDataReferenceInCode(CiConstant.forLong(DoubleSignFlip)));
-        asm.xorpd(negateArgument, negateTemp);
-        negateEpilogue();
-    }
-
-    private void emitFNEG() {
-        negatePrologue();
-        asm.movsd(negateTemp, tasm.recordDataReferenceInCode(CiConstant.forLong(FloatSignFlip)));
-        asm.xorps(negateArgument, negateTemp);
-        negateEpilogue();
-    }
-
     private void convertPrologue() {
         partialSavePrologue(convertArgument, convertResult);
         loadArgument(0, convertArgument);
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRAssembler.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRAssembler.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRAssembler.java	Mon Aug 01 12:27:45 2011 +0200
@@ -1517,14 +1517,12 @@
             if (asXmmFloatReg(left) != asXmmFloatReg(dest)) {
                 masm.movflt(asXmmFloatReg(dest), asXmmFloatReg(left));
             }
-            callGlobalStub(op.globalStub, null, asXmmFloatReg(dest), dest);
-
+            masm.xorps(asXmmFloatReg(dest), tasm.recordDataReferenceInCode(CiConstant.forLong(0x8000000080000000L)));
         } else if (dest.kind.isDouble()) {
             if (asXmmDoubleReg(left) != asXmmDoubleReg(dest)) {
                 masm.movdbl(asXmmDoubleReg(dest), asXmmDoubleReg(left));
             }
-
-            callGlobalStub(op.globalStub, null, asXmmDoubleReg(dest), dest);
+            masm.xorpd(asXmmDoubleReg(dest), tasm.recordDataReferenceInCode(CiConstant.forLong(0x8000000000000000L)));
         } else {
             CiRegister lreg = left.asRegister();
             CiRegister dreg = dest.asRegister();
diff -r be4ca325525a -r 2c5b4dd06d3b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java	Wed Jul 27 17:32:44 2011 -0700
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java	Mon Aug 01 12:27:45 2011 +0200
@@ -126,13 +126,7 @@
         value.setDestroysRegister();
         value.loadItem();
         CiVariable reg = newVariable(x.kind);
-        GlobalStub globalStub = null;
-        if (x.kind == CiKind.Float) {
-            globalStub = stubFor(GlobalStub.Id.fneg);
-        } else if (x.kind == CiKind.Double) {
-            globalStub = stubFor(GlobalStub.Id.dneg);
-        }
-        lir.negate(value.result(), reg, globalStub);
+        lir.negate(value.result(), reg);
         setResult(x, reg);
     }