--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Sat May 24 00:54:20 2014 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Sat May 24 01:41:56 2014 +0200
@@ -65,7 +65,7 @@
 
     boolean callKillsRegisters;
 
-    private static final int INITIAL_SPLIT_INTERVALS_CAPACITY = 32;
+    private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
 
     public static class BlockData {
 
@@ -147,13 +147,6 @@
     BitMap2D intervalInLoop;
 
     /**
-     * The variable operands allocated from this pool. The {@linkplain #operandNumber(Value) number}
-     * of the first variable operand in this pool is one greater than the number of the last
-     * register operand in the pool.
-     */
-    private final ArrayList<Variable> variables;
-
-    /**
      * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
      */
     private final int firstVariableNumber;
@@ -167,7 +160,6 @@
 
         this.registers = target.arch.getRegisters();
         this.firstVariableNumber = registers.length;
-        this.variables = new ArrayList<>(ir.numVariables() * 3 / 2);
         this.blockData = new BlockMap<>(ir.getControlFlowGraph());
     }
 
@@ -204,20 +196,6 @@
     }
 
     /**
-     * Gets the operand denoted by a given operand number.
-     */
-    private AllocatableValue operandFor(int operandNumber) {
-        if (operandNumber < firstVariableNumber) {
-            assert operandNumber >= 0;
-            return registers[operandNumber].asValue();
-        }
-        int index = operandNumber - firstVariableNumber;
-        Variable variable = variables.get(index);
-        assert variable.index == index;
-        return variable;
-    }
-
-    /**
      * Gets the number of operands. This value will increase by 1 for new variable.
      */
     private int operandSize() {
@@ -304,12 +282,10 @@
             firstDerivedIntervalIndex = intervalsSize;
         }
         if (intervalsSize == intervals.length) {
-            intervals = Arrays.copyOf(intervals, intervals.length * 2);
+            intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT));
         }
         intervalsSize++;
         Variable variable = new Variable(source.kind(), ir.nextVariable());
-        assert variables.size() == variable.index;
-        variables.add(variable);
 
         Interval interval = createInterval(variable);
         assert intervals[intervalsSize - 1] == interval;
@@ -342,6 +318,10 @@
         return intervalInLoop.at(interval, loop);
     }
 
+    Interval intervalFor(int operandNumber) {
+        return intervals[operandNumber];
+    }
+
     Interval intervalFor(Value operand) {
         int operandNumber = operandNumber(operand);
         assert operandNumber < intervalsSize;
@@ -609,16 +589,16 @@
      * {@linkplain ComputeBlockOrder linear scan order}.
      */
     void numberInstructions() {
+
+        intervalsSize = operandSize();
+        intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
+
         ValueProcedure setVariableProc = new ValueProcedure() {
 
             @Override
             public Value doValue(Value value) {
                 if (isVariable(value)) {
-                    int variableIdx = asVariable(value).index;
-                    while (variables.size() <= variableIdx) {
-                        variables.add(null);
-                    }
-                    variables.set(variableIdx, asVariable(value));
+                    getOrCreateInterval(asVariable(value));
                 }
                 return value;
             }
@@ -659,13 +639,6 @@
         }
         assert index == numInstructions : "must match";
         assert (index << 1) == opId : "must match: " + (index << 1);
-
-        if (DetailedAsserts.getValue()) {
-            for (int i = 0; i < variables.size(); i++) {
-                assert variables.get(i) != null && variables.get(i).index == i;
-            }
-            assert variables.size() == ir.numVariables();
-        }
     }
 
     /**
@@ -687,66 +660,66 @@
                 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
                 int numInst = instructions.size();
 
+                ValueProcedure useProc = new ValueProcedure() {
+
+                    @Override
+                    protected Value doValue(Value operand) {
+                        if (isVariable(operand)) {
+                            int operandNum = operandNumber(operand);
+                            if (!liveKill.get(operandNum)) {
+                                liveGen.set(operandNum);
+                                Debug.log("liveGen for operand %d", operandNum);
+                            }
+                            if (block.getLoop() != null) {
+                                intervalInLoop.setBit(operandNum, block.getLoop().getIndex());
+                            }
+                        }
+
+                        if (DetailedAsserts.getValue()) {
+                            verifyInput(block, liveKill, operand);
+                        }
+                        return operand;
+                    }
+                };
+                ValueProcedure stateProc = new ValueProcedure() {
+
+                    @Override
+                    public Value doValue(Value operand) {
+                        int operandNum = operandNumber(operand);
+                        if (!liveKill.get(operandNum)) {
+                            liveGen.set(operandNum);
+                            Debug.log("liveGen in state for operand %d", operandNum);
+                        }
+                        return operand;
+                    }
+                };
+                ValueProcedure defProc = new ValueProcedure() {
+
+                    @Override
+                    public Value doValue(Value operand) {
+                        if (isVariable(operand)) {
+                            int varNum = operandNumber(operand);
+                            liveKill.set(varNum);
+                            Debug.log("liveKill for operand %d", varNum);
+                            if (block.getLoop() != null) {
+                                intervalInLoop.setBit(varNum, block.getLoop().getIndex());
+                            }
+                        }
+
+                        if (DetailedAsserts.getValue()) {
+                            // fixed intervals are never live at block boundaries, so
+                            // they need not be processed in live sets
+                            // process them only in debug mode so that this can be checked
+                            verifyTemp(liveKill, operand);
+                        }
+                        return operand;
+                    }
+                };
+
                 // iterate all instructions of the block
                 for (int j = 0; j < numInst; j++) {
                     final LIRInstruction op = instructions.get(j);
 
-                    ValueProcedure useProc = new ValueProcedure() {
-
-                        @Override
-                        protected Value doValue(Value operand) {
-                            if (isVariable(operand)) {
-                                int operandNum = operandNumber(operand);
-                                if (!liveKill.get(operandNum)) {
-                                    liveGen.set(operandNum);
-                                    Debug.log("liveGen for operand %d", operandNum);
-                                }
-                                if (block.getLoop() != null) {
-                                    intervalInLoop.setBit(operandNum, block.getLoop().getIndex());
-                                }
-                            }
-
-                            if (DetailedAsserts.getValue()) {
-                                verifyInput(block, liveKill, operand);
-                            }
-                            return operand;
-                        }
-                    };
-                    ValueProcedure stateProc = new ValueProcedure() {
-
-                        @Override
-                        public Value doValue(Value operand) {
-                            int operandNum = operandNumber(operand);
-                            if (!liveKill.get(operandNum)) {
-                                liveGen.set(operandNum);
-                                Debug.log("liveGen in state for operand %d", operandNum);
-                            }
-                            return operand;
-                        }
-                    };
-                    ValueProcedure defProc = new ValueProcedure() {
-
-                        @Override
-                        public Value doValue(Value operand) {
-                            if (isVariable(operand)) {
-                                int varNum = operandNumber(operand);
-                                liveKill.set(varNum);
-                                Debug.log("liveKill for operand %d", varNum);
-                                if (block.getLoop() != null) {
-                                    intervalInLoop.setBit(varNum, block.getLoop().getIndex());
-                                }
-                            }
-
-                            if (DetailedAsserts.getValue()) {
-                                // fixed intervals are never live at block boundaries, so
-                                // they need not be processed in live sets
-                                // process them only in debug mode so that this can be checked
-                                verifyTemp(liveKill, operand);
-                            }
-                            return operand;
-                        }
-                    };
-
                     try (Indent indent2 = Debug.logAndIndent("handle op %d", op.id())) {
                         op.forEachInput(useProc);
                         op.forEachAlive(useProc);
@@ -906,14 +879,14 @@
                 BitSet startBlockLiveIn = blockData.get(ir.getControlFlowGraph().getStartBlock()).liveIn;
                 try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) {
                     for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
-                        Value operand = operandFor(operandNum);
+                        Value operand = intervalFor(operandNum).operand;
                         Debug.log("var %d; operand=%s; node=%s", operandNum, operand, getValueForOperandFromDebugContext(operand));
                     }
                 }
 
                 // print some additional information to simplify debugging
                 for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
-                    Value operand = operandFor(operandNum);
+                    Value operand = intervalFor(operandNum).operand;
                     try (Indent indent2 = Debug.logAndIndent("---- Detailed information for var %d; operand=%s; node=%s ----", operandNum, operand, getValueForOperandFromDebugContext(operand))) {
 
                         Deque<AbstractBlock<?>> definedIn = new ArrayDeque<>();
@@ -1151,9 +1124,6 @@
 
         try (Indent indent = Debug.logAndIndent("build intervals")) {
 
-            intervalsSize = operandSize();
-            intervals = new Interval[intervalsSize + INITIAL_SPLIT_INTERVALS_CAPACITY];
-
             // create a list with all caller-save registers (cpu, fpu, xmm)
             Register[] callerSaveRegs = frameMap.registerConfig.getCallerSaveRegisters();
 
@@ -1174,7 +1144,7 @@
                     BitSet live = blockData.get(block).liveOut;
                     for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) {
                         assert live.get(operandNum) : "should not stop here otherwise";
-                        AllocatableValue operand = operandFor(operandNum);
+                        AllocatableValue operand = intervalFor(operandNum).operand;
                         Debug.log("live in %d: %s", operandNum, operand);
 
                         addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, Kind.Illegal);
@@ -1184,7 +1154,7 @@
                         // that the block was part of a non-natural loop, so it might
                         // have an invalid loop index.
                         if (block.isLoopEnd() && block.getLoop() != null && isIntervalInLoop(operandNum, block.getLoop().getIndex())) {
-                            intervalFor(operand).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd);
+                            intervalFor(operandNum).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd);
                         }
                     }
 
@@ -1396,7 +1366,7 @@
         int newLen = newList.length;
 
         // conventional sort-algorithm for new intervals
-        Arrays.sort(newList, INTERVAL_COMPARATOR);
+        Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from());
 
         // merge old and new list (both already sorted) into one combined list
         Interval[] combinedList = new Interval[oldLen + newLen];
@@ -1416,25 +1386,6 @@
         sortedIntervals = combinedList;
     }
 
-    private static final Comparator<Interval> INTERVAL_COMPARATOR = new Comparator<Interval>() {
-
-        public int compare(Interval a, Interval b) {
-            if (a != null) {
-                if (b != null) {
-                    return a.from() - b.from();
-                } else {
-                    return -1;
-                }
-            } else {
-                if (b != null) {
-                    return 1;
-                } else {
-                    return 0;
-                }
-            }
-        }
-    };
-
     public void allocateRegisters() {
         try (Indent indent = Debug.logAndIndent("allocate registers")) {
             Interval precoloredIntervals;
@@ -1467,25 +1418,12 @@
         throw new BailoutException("LinearScan: interval is null");
     }
 
-    Interval intervalAtBlockBegin(AbstractBlock<?> block, Value operand) {
-        assert isVariable(operand) : "register number out of bounds";
-        assert intervalFor(operand) != null : "no interval found";
-
-        return splitChildAtOpId(intervalFor(operand), getFirstLirInstructionId(block), LIRInstruction.OperandMode.DEF);
+    Interval intervalAtBlockBegin(AbstractBlock<?> block, int operandNumber) {
+        return splitChildAtOpId(intervalFor(operandNumber), getFirstLirInstructionId(block), LIRInstruction.OperandMode.DEF);
     }
 
-    Interval intervalAtBlockEnd(AbstractBlock<?> block, Value operand) {
-        assert isVariable(operand) : "register number out of bounds";
-        assert intervalFor(operand) != null : "no interval found";
-
-        return splitChildAtOpId(intervalFor(operand), getLastLirInstructionId(block) + 1, LIRInstruction.OperandMode.DEF);
-    }
-
-    Interval intervalAtOpId(Value operand, int opId) {
-        assert isVariable(operand) : "register number out of bounds";
-        assert intervalFor(operand) != null : "no interval found";
-
-        return splitChildAtOpId(intervalFor(operand), opId, LIRInstruction.OperandMode.USE);
+    Interval intervalAtBlockEnd(AbstractBlock<?> block, int operandNumber) {
+        return splitChildAtOpId(intervalFor(operandNumber), getLastLirInstructionId(block) + 1, LIRInstruction.OperandMode.DEF);
     }
 
     void resolveCollectMappings(AbstractBlock<?> fromBlock, AbstractBlock<?> toBlock, MoveResolver moveResolver) {
@@ -1499,9 +1437,8 @@
             assert operandNum < numOperands : "live information set for not exisiting interval";
             assert blockData.get(fromBlock).liveOut.get(operandNum) && blockData.get(toBlock).liveIn.get(operandNum) : "interval not live at this edge";
 
-            Value liveOperand = operandFor(operandNum);
-            Interval fromInterval = intervalAtBlockEnd(fromBlock, liveOperand);
-            Interval toInterval = intervalAtBlockBegin(toBlock, liveOperand);
+            Interval fromInterval = intervalAtBlockEnd(fromBlock, operandNum);
+            Interval toInterval = intervalAtBlockBegin(toBlock, operandNum);
 
             if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) {
                 // need to insert move instruction
@@ -1912,7 +1849,6 @@
             }
 
             printLir("After register number assignment", true);
-
         }
     }
 
@@ -1944,10 +1880,6 @@
         // (check that all intervals have a correct register and that no registers are overwritten)
         verifyIntervals();
 
-        // verifyNoOopsInFixedIntervals();
-
-        verifyConstants();
-
         verifyRegisters();
 
         Debug.log("no errors found");
@@ -2101,23 +2033,6 @@
         }
     }
 
-    void verifyConstants() {
-        try (Indent indent = Debug.logAndIndent("verifying that unpinned constants are not alive across block boundaries")) {
-            for (AbstractBlock<?> block : sortedBlocks) {
-                BitSet liveAtEdge = blockData.get(block).liveIn;
-
-                // visit all operands where the liveAtEdge bit is set
-                for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) {
-                    Debug.log("checking interval %d of block B%d", operandNum, block.getId());
-                    Value operand = operandFor(operandNum);
-                    assert isVariable(operand) : "value must have variable operand";
-                    // TKR assert value.asConstant() == null || value.isPinned() :
-                    // "only pinned constants can be alive accross block boundaries";
-                }
-            }
-        }
-    }
-
     /**
      * Returns a value for a interval definition, which can be used for re-materialization.
      *

--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Sat May 24 00:54:20 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java	Sat May 24 01:41:56 2014 +0200
@@ -27,6 +27,7 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.api.meta.JavaTypeProfile.ProfiledType;
 import com.oracle.graal.api.meta.ProfilingInfo.TriState;
+import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.calc.*;
 import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.debug.*;
@@ -702,6 +703,18 @@
         connectEnds(falseEnds, phiValues, oldFalseSuccessor, merge, tool);
         connectEnds(trueEnds, phiValues, oldTrueSuccessor, merge, tool);
 
+        if (this.trueSuccessorProbability == 0.0) {
+            for (AbstractEndNode endNode : trueEnds) {
+                propagateZeroProbability(endNode);
+            }
+        }
+
+        if (this.trueSuccessorProbability == 1.0) {
+            for (AbstractEndNode endNode : falseEnds) {
+                propagateZeroProbability(endNode);
+            }
+        }
+
         /*
          * Remove obsolete ends only after processing all ends, otherwise oldTrueSuccessor or
          * oldFalseSuccessor might have been removed if it is a LoopExitNode.
@@ -723,6 +736,42 @@
         return true;
     }
 
+    private void propagateZeroProbability(FixedNode startNode) {
+        Node prev = null;
+        for (FixedNode node : GraphUtil.predecessorIterable(startNode)) {
+            if (node instanceof IfNode) {
+                IfNode ifNode = (IfNode) node;
+                if (ifNode.trueSuccessor() == prev) {
+                    if (ifNode.trueSuccessorProbability == 0.0) {
+                        return;
+                    } else if (ifNode.trueSuccessorProbability == 1.0) {
+                        continue;
+                    } else {
+                        ifNode.setTrueSuccessorProbability(0.0);
+                        return;
+                    }
+                } else if (ifNode.falseSuccessor() == prev) {
+                    if (ifNode.trueSuccessorProbability == 1.0) {
+                        return;
+                    } else if (ifNode.trueSuccessorProbability == 0.0) {
+                        continue;
+                    } else {
+                        ifNode.setTrueSuccessorProbability(1.0);
+                        return;
+                    }
+                } else {
+                    throw new GraalInternalError("Illegal state");
+                }
+            } else if (node instanceof MergeNode && !(node instanceof LoopBeginNode)) {
+                for (AbstractEndNode endNode : ((MergeNode) node).cfgPredecessors()) {
+                    propagateZeroProbability(endNode);
+                }
+                return;
+            }
+            prev = node;
+        }
+    }
+
     private static boolean checkFrameState(FixedNode start) {
         FixedNode node = start;
         while (true) {