# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1348588201 -7200
# Node ID 5395ecdfce8a86e9cb5002bdf8395a6d408d6fdf
# Parent  9ce24a27f0351c7348e95526bd7b4f09e7bb50fa
move monitors into FrameState (fixes subtle issues for tail duplication and other optimizations)

diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java	Tue Sep 25 17:50:01 2012 +0200
@@ -27,7 +27,6 @@
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
-import com.oracle.graal.compiler.gen.LIRGenerator.LockScope;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.*;
@@ -45,7 +44,7 @@
     private HashMap<VirtualObjectNode, VirtualObject> virtualObjects = new HashMap<>();
     private IdentityHashMap<VirtualObjectNode, EscapeObjectState> objectStates = new IdentityHashMap<>();
 
-    public LIRFrameState build(FrameState topState, LockScope locks, List<StackSlot> pointerSlots, LabelRef exceptionEdge, long leafGraphId) {
+    public LIRFrameState build(FrameState topState, List<StackSlot> lockData, List<StackSlot> pointerSlots, LabelRef exceptionEdge, long leafGraphId) {
         assert virtualObjects.size() == 0;
         assert objectStates.size() == 0;
 
@@ -65,7 +64,7 @@
             current = current.outerFrameState();
         } while (current != null);
 
-        BytecodeFrame frame = computeFrameForState(topState, locks, leafGraphId);
+        BytecodeFrame frame = computeFrameForState(topState, lockData, leafGraphId);
 
         VirtualObject[] virtualObjectsArray = null;
         if (virtualObjects.size() != 0) {
@@ -105,10 +104,10 @@
         return new LIRFrameState(frame, virtualObjectsArray, pointerSlots, exceptionEdge);
     }
 
-    private BytecodeFrame computeFrameForState(FrameState state, LockScope locks, long leafGraphId) {
+    private BytecodeFrame computeFrameForState(FrameState state, List<StackSlot> lockDataSlots, long leafGraphId) {
         int numLocals = state.localsSize();
         int numStack = state.stackSize();
-        int numLocks = (locks != null && locks.inliningIdentifier == state.inliningIdentifier()) ? locks.stateDepth + 1 : 0;
+        int numLocks = state.locksSize();
 
         Value[] values = new Value[numLocals + numStack + numLocks];
         for (int i = 0; i < numLocals; i++) {
@@ -117,30 +116,24 @@
         for (int i = 0; i < numStack; i++) {
             values[numLocals + i] = toValue(state.stackAt(i));
         }
-
-        LockScope nextLock = locks;
-        for (int i = numLocks - 1; i >= 0; i--) {
-            assert locks != null && nextLock.inliningIdentifier == state.inliningIdentifier() && nextLock.stateDepth == i;
-
-            Value owner = toValue(nextLock.object);
-            StackSlot lockData = nextLock.lockData;
-            boolean eliminated = nextLock.eliminated;
-            values[numLocals + numStack + nextLock.stateDepth] = new MonitorValue(owner, lockData, eliminated);
-
-            nextLock = nextLock.outer;
+        for (int i = 0; i < numLocks; i++) {
+            // frames are traversed from the outside in, so the locks for the current frame are at the end of the lockDataSlot list
+            StackSlot lockData = lockDataSlots.get(lockDataSlots.size() - numLocks + i);
+            values[numLocals + numStack + i] = new MonitorValue(toValue(state.lockAt(i)), lockData, state.lockAt(i) instanceof VirtualObjectNode);
         }
 
         BytecodeFrame caller = null;
         if (state.outerFrameState() != null) {
-            caller = computeFrameForState(state.outerFrameState(), nextLock, -1);
+            // remove the locks that were used for this frame from the list
+            List<StackSlot> nextLockDataSlots = lockDataSlots.subList(0, lockDataSlots.size() - numLocks);
+            caller = computeFrameForState(state.outerFrameState(), nextLockDataSlots, -1);
         } else {
-            if (nextLock != null) {
-                throw new BailoutException("unbalanced monitors: found monitor for unknown frame");
+            if (lockDataSlots.size() != numLocks) {
+                throw new BailoutException("unbalanced monitors: found monitor for unknown frame (%d != %d) at %s", lockDataSlots.size(), numLocks, state);
             }
         }
         assert state.bci >= 0 || state.bci == FrameState.BEFORE_BCI;
-        BytecodeFrame frame = new BytecodeFrame(caller, state.method(), state.bci, state.rethrowException(), state.duringCall(), values, state.localsSize(), state.stackSize(), numLocks, leafGraphId);
-        return frame;
+        return new BytecodeFrame(caller, state.method(), state.bci, state.rethrowException(), state.duringCall(), values, numLocals, numStack, numLocks, leafGraphId);
     }
 
     private Value toValue(ValueNode value) {
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Tue Sep 25 17:50:01 2012 +0200
@@ -46,7 +46,6 @@
 import com.oracle.graal.lir.asm.TargetMethodAssembler.CallPositionListener;
 import com.oracle.graal.lir.cfg.*;
 import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.FrameState.InliningIdentifier;
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.extended.*;
@@ -87,82 +86,24 @@
     private FrameState lastState;
 
     /**
-     * Class used to reconstruct the nesting of locks that is required for debug information.
+     * Mapping from blocks to the last encountered frame state at the end of the block.
      */
-    public static class LockScope {
-        /**
-         * Linked list of locks. {@link LIRGenerator#curLocks} is the head of the list.
-         */
-        public final LockScope outer;
-
-        /**
-         * The identifier of the actual inlined method instance performing the lock, or null if the outermost method
-         * performs the lock. This information is used to compute the {@link BytecodeFrame} that this lock belongs to.
-         */
-        public final InliningIdentifier inliningIdentifier;
-
-        /**
-         * The number of locks already found for this frame state.
-         */
-        public final int stateDepth;
-
-        /**
-         * The object that is locked.
-         */
-        public final ValueNode object;
-
-        /**
-         * Whether or not the lock is eliminated.
-         */
-        public final boolean eliminated;
-
-        /**
-         * Space in the stack frame needed by the VM to perform the locking.
-         */
-        public final StackSlot lockData;
-
-        public LockScope(LockScope outer, InliningIdentifier inliningIdentifier, ValueNode object, boolean eliminated, StackSlot lockData) {
-            this.outer = outer;
-            this.inliningIdentifier = inliningIdentifier;
-            this.object = object;
-            this.eliminated = eliminated;
-            this.lockData = lockData;
-            if (outer != null && outer.inliningIdentifier == inliningIdentifier) {
-                this.stateDepth = outer.stateDepth + 1;
-            } else {
-                this.stateDepth = 0;
-            }
-        }
-
-        @Override
-        public String toString() {
-            InliningIdentifier identifier = inliningIdentifier;
-            StringBuilder sb = new StringBuilder().append(identifier).append(": ");
-            for (LockScope scope = this; scope != null; scope = scope.outer) {
-                if (scope.inliningIdentifier != identifier) {
-                    identifier = scope.inliningIdentifier;
-                    sb.append('\n').append(identifier).append(": ");
-                }
-                if (scope.eliminated) {
-                    sb.append('!');
-                }
-                sb.append(scope.object).append(' ');
-            }
-            return sb.toString();
-        }
-    }
+    private final BlockMap<FrameState> blockLastState;
 
     /**
-     * Mapping from blocks to the lock state at the end of the block, indexed by the id number of the block.
+     * The number of currently locked monitors.
      */
-    private BlockMap<LockScope> blockLocks;
-
-    private BlockMap<FrameState> blockLastState;
+    private int currentLockCount;
 
     /**
-     * The list of currently locked monitors.
+     * Mapping from blocks to the number of locked monitors at the end of the block.
      */
-    private LockScope curLocks;
+    private final BlockMap<Integer> blockLastLockCount;
+
+    /**
+     * Contains the lock data slot for each lock depth (so these may be reused within a compiled method).
+     */
+    private final ArrayList<StackSlot> lockDataSlots;
 
 
     public LIRGenerator(Graph graph, CodeCacheProvider runtime, TargetDescription target, FrameMap frameMap, ResolvedJavaMethod method, LIR lir, XirGenerator xir, Assumptions assumptions) {
@@ -176,7 +117,8 @@
         this.xir = xir;
         this.xirSupport = new XirSupport(assumptions);
         this.debugInfoBuilder = new DebugInfoBuilder(nodeOperands);
-        this.blockLocks = new BlockMap<>(lir.cfg);
+        this.blockLastLockCount = new BlockMap<>(lir.cfg);
+        this.lockDataSlots = new ArrayList<>();
         this.blockLastState = new BlockMap<>(lir.cfg);
     }
 
@@ -299,7 +241,7 @@
     }
 
     public LIRFrameState stateFor(FrameState state, List<StackSlot> pointerSlots, LabelRef exceptionEdge, long leafGraphId) {
-        return debugInfoBuilder.build(state, curLocks, pointerSlots, exceptionEdge, leafGraphId);
+        return debugInfoBuilder.build(state, lockDataSlots.subList(0, currentLockCount), pointerSlots, exceptionEdge, leafGraphId);
     }
 
     /**
@@ -346,23 +288,24 @@
             TTY.println("BEGIN Generating LIR for block B" + block.getId());
         }
 
-        curLocks = null;
-        for (Block pred : block.getPredecessors()) {
-            LockScope predLocks = blockLocks.get(pred);
-            if (curLocks == null) {
-                curLocks = predLocks;
-            } else if (curLocks != predLocks && (!pred.isLoopEnd() || predLocks != null)) {
-//                throw new GraalInternalError("cause: %s", predLocks);
-                throw new BailoutException("unbalanced monitors: predecessor blocks have different monitor states");
-            }
-        }
-
         if (block == lir.cfg.getStartBlock()) {
             assert block.getPredecessors().size() == 0;
+            currentLockCount = 0;
             emitPrologue();
 
         } else {
             assert block.getPredecessors().size() > 0;
+
+            currentLockCount = -1;
+            for (Block pred : block.getPredecessors()) {
+                Integer predLocks = blockLastLockCount.get(pred);
+                if (currentLockCount == -1) {
+                    currentLockCount = predLocks;
+                } else {
+                    assert (predLocks == null && pred.isLoopEnd()) || currentLockCount == predLocks;
+                }
+            }
+
             FrameState fs = null;
 
             for (Block pred : block.getPredecessors()) {
@@ -464,7 +407,7 @@
         // share the frame state that flowed into the loop
         assert blockLastState.get(block) == null || blockLastState.get(block) == lastState;
 
-        blockLocks.put(currentBlock, curLocks);
+        blockLastLockCount.put(currentBlock, currentLockCount);
         blockLastState.put(block, lastState);
         currentBlock = null;
 
@@ -550,62 +493,74 @@
         setResult(x, operand(x.object()));
     }
 
-    public void lock(ValueNode object, boolean eliminated, StackSlot lock, InliningIdentifier inliningIdentifier) {
-        assert lastState != null : "must have state before instruction";
-        curLocks = new LockScope(curLocks, inliningIdentifier, object, eliminated, lock);
+    /**
+     * Increases the number of currently locked monitors and makes sure that a lock data slot is available for the new lock.
+     */
+    public void lock() {
+        if (lockDataSlots.size() == currentLockCount) {
+            lockDataSlots.add(frameMap.allocateStackBlock(runtime.sizeOfLockData(), false));
+        }
+        currentLockCount++;
     }
 
-    public StackSlot peekLock() {
-        assert curLocks.lockData != null;
-        return curLocks.lockData;
+    /**
+     * Decreases the number of currently locked monitors.
+     *
+     * @throws GraalInternalError if the number of currently locked monitors is already zero.
+     */
+    public void unlock() {
+        if (currentLockCount == 0) {
+            throw new GraalInternalError("unmatched locks");
+        }
+        currentLockCount--;
     }
 
-    public void unlock(ValueNode object, boolean eliminated) {
-        if (curLocks == null || curLocks.object != object || curLocks.eliminated != eliminated) {
-            throw new BailoutException("unbalanced monitors: attempting to unlock an object that is not on top of the locking stack");
-        }
-        curLocks = curLocks.outer;
+    /**
+     * @return The lock data slot for the topmost locked monitor.
+     */
+    public StackSlot peekLock() {
+        return lockDataSlots.get(currentLockCount - 1);
     }
 
     @Override
     public void visitMonitorEnter(MonitorEnterNode x) {
-        StackSlot lockData = frameMap.allocateStackBlock(runtime.sizeOfLockData(), false);
         if (x.eliminated()) {
-            // No code is emitted for eliminated locks, but for proper debug information generation we need to
-            // register the monitor and its lock data.
-            lock(x.object(), true, lockData, x.stateAfter().inliningIdentifier());
-            return;
-        }
+            // No code is emitted for eliminated locks.
+            lock();
+        } else {
+
+            // The state before the monitor enter is used for null checks, so it must not contain the newly locked object.
+            LIRFrameState stateBefore = state();
+            lock();
 
-        XirArgument obj = toXirArgument(x.object());
-        XirArgument lockAddress = lockData == null ? null : toXirArgument(emitLea(lockData));
+            XirArgument obj = toXirArgument(x.object());
+            XirArgument lockAddress = toXirArgument(emitLea(peekLock()));
 
-        LIRFrameState stateBefore = state();
-        // The state before the monitor enter is used for null checks, so it must not contain the newly locked object.
-        lock(x.object(), false, lockData, x.stateAfter().inliningIdentifier());
-        // The state after the monitor enter is used for deoptimization, after the monitor has blocked, so it must contain the newly locked object.
-        LIRFrameState stateAfter = stateFor(x.stateAfter(), -1);
+            // The state after the monitor enter is used for deoptimization, after the monitor has blocked, so it must contain the newly locked object.
+            LIRFrameState stateAfter = stateFor(x.stateAfter(), -1);
 
-        XirSnippet snippet = xir.genMonitorEnter(site(x, x.object()), obj, lockAddress);
-        emitXir(snippet, x, stateBefore, stateAfter, true, null, null);
+            XirSnippet snippet = xir.genMonitorEnter(site(x, x.object()), obj, lockAddress);
+            emitXir(snippet, x, stateBefore, stateAfter, true, null, null);
+        }
     }
 
     @Override
     public void visitMonitorExit(MonitorExitNode x) {
         if (x.eliminated()) {
-            unlock(x.object(), true);
-            return;
-        }
+            // No code is emitted for eliminated locks.
+            unlock();
+        } else {
+            // The state before the monitor exit is used for null checks, so it must contain the locked object.
+            LIRFrameState stateBefore = state();
 
-        Value lockData = peekLock();
-        XirArgument obj = toXirArgument(x.object());
-        XirArgument lockAddress = lockData == null ? null : toXirArgument(emitLea(lockData));
+            XirArgument obj = toXirArgument(x.object());
+            XirArgument lockAddress = toXirArgument(emitLea(peekLock()));
 
-        LIRFrameState stateBefore = state();
-        unlock(x.object(), false);
+            unlock();
 
-        XirSnippet snippet = xir.genMonitorExit(site(x, x.object()), obj, lockAddress);
-        emitXir(snippet, x, stateBefore, true);
+            XirSnippet snippet = xir.genMonitorExit(site(x, x.object()), obj, lockAddress);
+            emitXir(snippet, x, stateBefore, true);
+        }
     }
 
     @Override
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/BeginLockScopeNode.java
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/BeginLockScopeNode.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/BeginLockScopeNode.java	Tue Sep 25 17:50:01 2012 +0200
@@ -26,13 +26,11 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.gen.*;
 import com.oracle.graal.compiler.target.*;
-import com.oracle.graal.hotspot.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.snippets.*;
 
-
 /**
  * Intrinsic for opening a scope binding a stack-based lock with an object.
  * A lock scope must be closed with an {@link EndLockScopeNode}.
@@ -42,12 +40,10 @@
  */
 public final class BeginLockScopeNode extends AbstractStateSplit implements LIRGenLowerable, MonitorEnter {
 
-    @Input private ValueNode object;
     private final boolean eliminated;
 
-    public BeginLockScopeNode(ValueNode object, boolean eliminated, Kind wordKind) {
+    public BeginLockScopeNode(boolean eliminated, Kind wordKind) {
         super(StampFactory.forWord(wordKind, true));
-        this.object = object;
         this.eliminated = eliminated;
     }
 
@@ -58,18 +54,17 @@
 
     @Override
     public void generate(LIRGenerator gen) {
-        int size = HotSpotGraalRuntime.getInstance().getConfig().basicLockSize;
-        StackSlot lock = gen.frameMap().allocateStackBlock(size, false);
-        Value result = eliminated ? new Constant(gen.target().wordKind, 0L) : gen.emitLea(lock);
+        gen.lock();
+        StackSlot lockData = gen.peekLock();
+        Value result = eliminated ? new Constant(gen.target().wordKind, 0L) : gen.emitLea(lockData);
         FrameState stateAfter = stateAfter();
         assert stateAfter != null;
-        gen.lock(object, eliminated, lock, stateAfter.inliningIdentifier());
         gen.setResult(this, result);
     }
 
     @SuppressWarnings("unused")
     @NodeIntrinsic
-    public static Word beginLockScope(Object object, @ConstantNodeParameter boolean eliminated, @ConstantNodeParameter Kind wordKind) {
+    public static Word beginLockScope(@ConstantNodeParameter boolean eliminated, @ConstantNodeParameter Kind wordKind) {
         throw new UnsupportedOperationException();
     }
 }
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/CurrentLockNode.java
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/CurrentLockNode.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/CurrentLockNode.java	Tue Sep 25 17:50:01 2012 +0200
@@ -29,7 +29,6 @@
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.snippets.*;
 
-
 /**
  * Intrinsic for getting the lock in the current {@linkplain BeginLockScopeNode lock scope}.
  */
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/EndLockScopeNode.java
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/EndLockScopeNode.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/EndLockScopeNode.java	Tue Sep 25 17:50:01 2012 +0200
@@ -34,13 +34,8 @@
  */
 public final class EndLockScopeNode extends AbstractStateSplit implements LIRGenLowerable, MonitorExit {
 
-    @Input private ValueNode object;
-    private final boolean eliminated;
-
-    public EndLockScopeNode(ValueNode object, boolean eliminated) {
+    public EndLockScopeNode() {
         super(StampFactory.forVoid());
-        this.object = object;
-        this.eliminated = eliminated;
     }
 
     @Override
@@ -50,12 +45,11 @@
 
     @Override
     public void generate(LIRGenerator gen) {
-        gen.unlock(object, eliminated);
+        gen.unlock();
     }
 
-    @SuppressWarnings("unused")
     @NodeIntrinsic
-    public static void endLockScope(Object object, @ConstantNodeParameter boolean eliminated) {
+    public static void endLockScope() {
         throw new UnsupportedOperationException();
     }
 }
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/MonitorSnippets.java
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/MonitorSnippets.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/snippets/MonitorSnippets.java	Tue Sep 25 17:50:01 2012 +0200
@@ -87,7 +87,7 @@
         // Load the mark word - this includes a null-check on object
         final Word mark = loadWordFromObject(object, markOffset());
 
-        final Word lock = beginLockScope(object, false, wordKind());
+        final Word lock = beginLockScope(false, wordKind());
 
         if (useBiasedLocking()) {
             // See whether the lock is currently biased toward our thread and
@@ -233,8 +233,8 @@
     }
 
     @Snippet
-    public static void monitorenterEliminated(@Parameter("object") Object object) {
-        beginLockScope(object, true, wordKind());
+    public static void monitorenterEliminated() {
+        beginLockScope(true, wordKind());
     }
 
     /**
@@ -248,7 +248,7 @@
         }
         // BeginLockScope nodes do not read from object so a use of object
         // cannot float about the null check above
-        final Word lock = beginLockScope(object, false, wordKind());
+        final Word lock = beginLockScope(false, wordKind());
         log(logEnabled, "+lock{stub}", object);
         MonitorEnterStubCall.call(object, lock);
     }
@@ -264,7 +264,7 @@
             // the bias bit would be clear.
             final Word mark = loadWordFromObject(object, markOffset());
             if (mark.and(biasedLockMaskInPlace()).toLong() == biasedLockPattern()) {
-                endLockScope(object, false);
+                endLockScope();
                 log(logEnabled, "-lock{bias}", object);
                 return;
             }
@@ -292,7 +292,7 @@
                 log(logEnabled, "-lock{cas}", object);
             }
         }
-        endLockScope(object, false);
+        endLockScope();
     }
 
     /**
@@ -303,12 +303,12 @@
         verifyOop(object);
         log(logEnabled, "-lock{stub}", object);
         MonitorExitStubCall.call(object);
-        endLockScope(object, false);
+        endLockScope();
     }
 
     @Snippet
-    public static void monitorexitEliminated(@Parameter("object") Object object) {
-        endLockScope(object, true);
+    public static void monitorexitEliminated() {
+        endLockScope();
     }
 
     public static class Templates extends AbstractTemplates<MonitorSnippets> {
@@ -327,8 +327,8 @@
             monitorexit = snippet("monitorexit", Object.class, boolean.class);
             monitorenterStub = snippet("monitorenterStub", Object.class, boolean.class, boolean.class);
             monitorexitStub = snippet("monitorexitStub", Object.class, boolean.class);
-            monitorenterEliminated = snippet("monitorenterEliminated", Object.class);
-            monitorexitEliminated = snippet("monitorexitEliminated", Object.class);
+            monitorenterEliminated = snippet("monitorenterEliminated");
+            monitorexitEliminated = snippet("monitorexitEliminated");
             this.useFastLocking = useFastLocking;
         }
 
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/FrameStateBuilder.java	Tue Sep 25 17:50:01 2012 +0200
@@ -35,13 +35,19 @@
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 
 public class FrameStateBuilder {
+
+    private static final ValueNode[] EMPTY_ARRAY = new ValueNode[0];
+
     private final ResolvedJavaMethod method;
     private final StructuredGraph graph;
 
     private final ValueNode[] locals;
     private final ValueNode[] stack;
+    private ValueNode[] locks;
+
     private int stackSize;
     private boolean rethrowException;
 
@@ -52,6 +58,7 @@
         this.locals = new ValueNode[method.maxLocals()];
         // we always need at least one stack slot (for exceptions)
         this.stack = new ValueNode[Math.max(1, method.maxStackSize())];
+        this.locks = EMPTY_ARRAY;
 
         int javaIndex = 0;
         int index = 0;
@@ -84,16 +91,17 @@
         }
     }
 
-    private FrameStateBuilder(ResolvedJavaMethod method, StructuredGraph graph, ValueNode[] locals, ValueNode[] stack, int stackSize, boolean rethrowException) {
+    private FrameStateBuilder(FrameStateBuilder other) {
+        method = other.method;
+        graph = other.graph;
+        locals = other.locals.clone();
+        stack = other.stack.clone();
+        locks = other.locks == EMPTY_ARRAY ? EMPTY_ARRAY : other.locks.clone();
+        stackSize = other.stackSize;
+        rethrowException = other.rethrowException;
+
         assert locals.length == method.maxLocals();
         assert stack.length == Math.max(1, method.maxStackSize());
-
-        this.method = method;
-        this.graph = graph;
-        this.locals = locals;
-        this.stack = stack;
-        this.stackSize = stackSize;
-        this.rethrowException = rethrowException;
     }
 
     @Override
@@ -107,6 +115,10 @@
         for (int i = 0; i < stackSize; i++) {
             sb.append(i == 0 ? "" : ",").append(stack[i] == null ? "_" : stack[i].toString(Verbosity.Id));
         }
+        sb.append("] locks: [");
+        for (int i = 0; i < locks.length; i++) {
+            sb.append(i == 0 ? "" : ",").append(locks[i] == null ? "_" : locks[i].toString(Verbosity.Id));
+        }
         sb.append("]");
         if (rethrowException) {
             sb.append(" rethrowException");
@@ -116,11 +128,11 @@
     }
 
     public FrameState create(int bci) {
-        return graph.add(new FrameState(method, bci, locals, stack, stackSize, rethrowException, false, null));
+        return graph.add(new FrameState(method, bci, locals, Arrays.asList(stack).subList(0, stackSize), locks, rethrowException, false, null));
     }
 
     public FrameStateBuilder copy() {
-        return new FrameStateBuilder(method, graph, Arrays.copyOf(locals, locals.length), Arrays.copyOf(stack, stack.length), stackSize, rethrowException);
+        return new FrameStateBuilder(this);
     }
 
     public boolean isCompatibleWith(FrameStateBuilder other) {
@@ -136,6 +148,15 @@
                 return false;
             }
         }
+        if (locks.length != other.locks.length) {
+            return false;
+        }
+        for (int i = 0; i < locks.length; i++) {
+            if (GraphUtil.originalValue(locks[i]) != GraphUtil.originalValue(other.locks[i])) {
+                System.out.println("unbalanced monitors");
+                return false;
+            }
+        }
         return true;
     }
 
@@ -186,7 +207,7 @@
         if (node.isDeleted()) {
             return;
         }
-        // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselfs to avoid circles).
+        // Collect all phi functions that use this phi so that we can delete them recursively (after we delete ourselves to avoid circles).
         List<FloatingNode> propagateUsages = node.usages().filter(FloatingNode.class).filter(isA(PhiNode.class).or(ValueProxyNode.class)).snapshot();
 
         // Remove the phi function from all FrameStates where it is used and then delete it.
@@ -223,6 +244,13 @@
                 storeStack(i, graph.unique(new ValueProxyNode(value, loopExit, PhiType.Value)));
             }
         }
+        for (int i = 0; i < locks.length; i++) {
+            ValueNode value = locks[i];
+            if (value != null && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
+                Debug.log(" inserting proxy for %s", value);
+                locks[i] = graph.unique(new ValueProxyNode(value, loopExit, PhiType.Value));
+            }
+        }
     }
 
     private PhiNode createLoopPhi(MergeNode block, ValueNode value) {
@@ -302,6 +330,36 @@
     }
 
     /**
+     * Adds a locked monitor to this frame state.
+     *
+     * @param object the object whose monitor will be locked.
+     */
+    public void pushLock(ValueNode object) {
+        locks = Arrays.copyOf(locks, locks.length + 1);
+        locks[locks.length - 1] = object;
+    }
+
+    /**
+     * Removes a locked monitor from this frame state.
+     *
+     * @return the object whose monitor was removed from the locks list.
+     */
+    public ValueNode popLock() {
+        try {
+            return locks[locks.length - 1];
+        } finally {
+            locks = locks.length == 1 ? EMPTY_ARRAY : Arrays.copyOf(locks, locks.length - 1);
+        }
+    }
+
+    /**
+     * @return true if there are no locks within this frame state.
+     */
+    public boolean locksEmpty() {
+        return locks.length == 0;
+    }
+
+    /**
      * Loads the local variable at the specified index, checking that the returned value is non-null
      * and that two-stack values are properly handled.
      *
@@ -560,6 +618,11 @@
                 return true;
             }
         }
+        for (int i = 0; i < locks.length; i++) {
+            if (locks[i] == value) {
+                return true;
+            }
+        }
         return false;
     }
 }
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Tue Sep 25 17:50:01 2012 +0200
@@ -1005,12 +1005,17 @@
     }
 
     private MonitorEnterNode genMonitorEnter(ValueNode x) {
+        frameState.pushLock(GraphUtil.originalValue(x));
         MonitorEnterNode monitorEnter = currentGraph.add(new MonitorEnterNode(x));
         appendWithBCI(monitorEnter);
         return monitorEnter;
     }
 
     private MonitorExitNode genMonitorExit(ValueNode x) {
+        ValueNode lockedObject = frameState.popLock();
+        if (lockedObject != GraphUtil.originalValue(x)) {
+            throw new BailoutException("unbalanced monitors: mismatch at monitorexit %s %s", GraphUtil.originalValue(x), lockedObject);
+        }
         MonitorExitNode monitorExit = currentGraph.add(new MonitorExitNode(x));
         appendWithBCI(monitorExit);
         return monitorExit;
@@ -1360,7 +1365,12 @@
         }
 
         synchronizedEpilogue(FrameState.AFTER_BCI);
+        if (!frameState.locksEmpty()) {
+            System.out.println("unbalanced monitors");
+            throw new BailoutException("unbalanced monitors");
+        }
         ReturnNode returnNode = currentGraph.add(new ReturnNode(x));
+
         append(returnNode);
     }
 
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FrameState.java	Tue Sep 25 17:50:01 2012 +0200
@@ -121,12 +121,12 @@
      * @param stackSize size of the stack
      * @param rethrowException if true the VM should re-throw the exception on top of the stack when deopt'ing using this framestate
      */
-    public FrameState(ResolvedJavaMethod method, int bci, List<ValueNode> values, int stackSize, boolean rethrowException, boolean duringCall, InliningIdentifier inliningIdentifier, List<EscapeObjectState> virtualObjectMappings) {
+    public FrameState(ResolvedJavaMethod method, int bci, List<ValueNode> values, int localsSize, int stackSize, boolean rethrowException, boolean duringCall, InliningIdentifier inliningIdentifier, List<EscapeObjectState> virtualObjectMappings) {
         assert stackSize >= 0;
         assert (bci >= 0 && method != null) || (bci < 0 && method == null && values.isEmpty());
         this.method = method;
         this.bci = bci;
-        this.localsSize = values.size() - stackSize;
+        this.localsSize = localsSize;
         this.stackSize = stackSize;
         this.values = new NodeInputList<>(this, values);
         this.virtualObjectMappings = new NodeInputList<>(this, virtualObjectMappings);
@@ -141,22 +141,28 @@
      * @param bci marker bci, needs to be < 0
      */
     public FrameState(int bci) {
-        this(null, bci, Collections.<ValueNode>emptyList(), 0, false, false, null, Collections.<EscapeObjectState>emptyList());
+        this(null, bci, Collections.<ValueNode>emptyList(), 0, 0, false, false, null, Collections.<EscapeObjectState>emptyList());
     }
 
-    public FrameState(ResolvedJavaMethod method, int bci, ValueNode[] locals, ValueNode[] stack, int stackSize, boolean rethrowException, boolean duringCall, InliningIdentifier inliningIdentifier) {
+    public FrameState(ResolvedJavaMethod method, int bci, ValueNode[] locals, List<ValueNode> stack, ValueNode[] locks, boolean rethrowException, boolean duringCall,
+                    InliningIdentifier inliningIdentifier) {
         this.method = method;
         this.bci = bci;
         this.localsSize = locals.length;
-        this.stackSize = stackSize;
-        final ValueNode[] newValues = new ValueNode[locals.length + stackSize];
-        for (int i = 0; i < locals.length; i++) {
-            assert locals[i] == null || !locals[i].isDeleted();
-            newValues[i] = locals[i];
+        this.stackSize = stack.size();
+        final ValueNode[] newValues = new ValueNode[locals.length + stack.size() + locks.length];
+        int pos = 0;
+        for (ValueNode value : locals) {
+            newValues[pos++] = value;
         }
-        for (int i = 0; i < stackSize; i++) {
-            assert stack[i] == null || !stack[i].isDeleted();
-            newValues[localsSize + i] = stack[i];
+        for (ValueNode value : stack) {
+            newValues[pos++] = value;
+        }
+        for (ValueNode value : locks) {
+            newValues[pos++] = value;
+        }
+        for (ValueNode value : newValues) {
+            assert value == null || value.isAlive();
         }
         this.values = new NodeInputList<>(this, newValues);
         this.virtualObjectMappings = new NodeInputList<>(this);
@@ -223,7 +229,7 @@
      * Gets a copy of this frame state.
      */
     public FrameState duplicate(int newBci) {
-        FrameState other = graph().add(new FrameState(method, newBci, values, stackSize, rethrowException, duringCall, inliningIdentifier, virtualObjectMappings));
+        FrameState other = graph().add(new FrameState(method, newBci, values, localsSize, stackSize, rethrowException, duringCall, inliningIdentifier, virtualObjectMappings));
         other.setOuterFrameState(outerFrameState());
         return other;
     }
@@ -249,7 +255,7 @@
         for (EscapeObjectState state : virtualObjectMappings) {
             newVirtualMappings.add(state.duplicateWithVirtualState());
         }
-        FrameState other = graph().add(new FrameState(method, bci, values, stackSize, rethrowException, duringCall, inliningIdentifier, newVirtualMappings));
+        FrameState other = graph().add(new FrameState(method, bci, values, localsSize, stackSize, rethrowException, duringCall, inliningIdentifier, newVirtualMappings));
         other.setOuterFrameState(newOuterFrameState);
         return other;
     }
@@ -260,7 +266,7 @@
      * or double is followed by a null slot.
      */
     public FrameState duplicateModified(int newBci, boolean newRethrowException, Kind popKind, ValueNode... pushedValues) {
-        ArrayList<ValueNode> copy = new ArrayList<>(values);
+        ArrayList<ValueNode> copy = new ArrayList<>(values.subList(0, localsSize + stackSize));
         if (popKind != Kind.Void) {
             if (stackAt(stackSize() - 1) == null) {
                 copy.remove(copy.size() - 1);
@@ -270,8 +276,10 @@
             copy.remove(copy.size() - 1);
         }
         Collections.addAll(copy, pushedValues);
+        int newStackSize = copy.size() - localsSize;
+        copy.addAll(values.subList(localsSize + stackSize, values.size()));
 
-        FrameState other = graph().add(new FrameState(method, newBci, copy, copy.size() - localsSize, newRethrowException, false, inliningIdentifier, virtualObjectMappings));
+        FrameState other = graph().add(new FrameState(method, newBci, copy, localsSize, newStackSize, newRethrowException, false, inliningIdentifier, virtualObjectMappings));
         other.setOuterFrameState(outerFrameState());
         return other;
     }
@@ -291,6 +299,13 @@
     }
 
     /**
+     * Gets the number of locked monitors in this frame state.
+     */
+    public int locksSize() {
+        return values.size() - localsSize - stackSize;
+    }
+
+    /**
      * Gets the value in the local variables at the specified index.
      *
      * @param i the index into the locals
@@ -312,6 +327,17 @@
         return values.get(localsSize + i);
     }
 
+    /**
+     * Get the monitor owner at the specified index.
+     *
+     * @param i the index into the list of locked monitors.
+     * @return the lock owner at the given index.
+     */
+    public ValueNode lockAt(int i) {
+        assert i >= 0 && i < locksSize();
+        return values.get(localsSize + stackSize + i);
+    }
+
     public MergeNode block() {
         return usages().filter(MergeNode.class).first();
     }
@@ -339,7 +365,11 @@
             for (int i = 0; i < fs.stackSize(); i++) {
                 sb.append(i == 0 ? "" : ", ").append(fs.stackAt(i) == null ? "_" : fs.stackAt(i).toString(Verbosity.Id));
             }
-            sb.append(nl);
+            sb.append("]").append(nl).append("locks: ");
+            for (int i = 0; i < fs.locksSize(); i++) {
+                sb.append(i == 0 ? "" : ", ").append(fs.lockAt(i) == null ? "_" : fs.lockAt(i).toString(Verbosity.Id));
+            }
+            sb.append(']').append(nl);
             fs = fs.outerFrameState();
         }
         return sb.toString();
@@ -367,6 +397,7 @@
                 properties.put("sourceLine", ste.getLineNumber());
             }
         }
+        properties.put("locksSize", values.size() - stackSize - localsSize);
         return properties;
     }
 
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/GraphUtil.java	Tue Sep 25 17:50:01 2012 +0200
@@ -236,4 +236,23 @@
         str.append("]");
         return str.toString();
     }
+
+    public static ValueNode originalValue(ValueNode proxy) {
+        ValueNode v = proxy;
+        do {
+            if (v instanceof ValueProxyNode) {
+                v = ((ValueProxyNode) v).value();
+                continue;
+            }
+            if (v instanceof PhiNode) {
+                ValueNode singleValue = ((PhiNode) v).singleValue();
+                if (singleValue != null) {
+                    v = singleValue;
+                    continue;
+                }
+            }
+            break;
+        } while (true);
+        return v;
+    }
 }
diff -r 9ce24a27f035 -r 5395ecdfce8a graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Tue Sep 25 16:35:27 2012 +0200
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java	Tue Sep 25 17:50:01 2012 +0200
@@ -396,6 +396,12 @@
             }
             buf.append("\n");
 
+            buf.append("locks: ");
+            for (int i = 0; i < curState.locksSize(); i++) {
+                buf.append(stateValueToString(curState.lockAt(i))).append(' ');
+            }
+            buf.append("\n");
+
             curState = curState.outerFrameState();
         } while (curState != null);