--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/DefUseTree.java	Tue Feb 24 19:02:59 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/DefUseTree.java	Wed Feb 25 15:16:14 2015 +0100
@@ -67,7 +67,7 @@
     }
 
     public void addUsage(AbstractBlockBase<?> b, LIRInstruction inst, ValuePosition position) {
-        uses.add(new UseEntry(b, inst, position));
+        uses.add(new UseEntry(b, inst, position.get(inst)));
     }
 
     public int usageCount() {

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/UseEntry.java	Tue Feb 24 19:02:59 2015 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/UseEntry.java	Wed Feb 25 15:16:14 2015 +0100
@@ -33,12 +33,12 @@
 
     private final AbstractBlockBase<?> block;
     private final LIRInstruction instruction;
-    private final ValuePosition position;
+    private final Value value;
 
-    public UseEntry(AbstractBlockBase<?> block, LIRInstruction instruction, ValuePosition position) {
+    public UseEntry(AbstractBlockBase<?> block, LIRInstruction instruction, Value value) {
         this.block = block;
         this.instruction = instruction;
-        this.position = position;
+        this.value = value;
     }
 
     public LIRInstruction getInstruction() {
@@ -50,11 +50,20 @@
     }
 
     public void setValue(Value newValue) {
-        position.set(getInstruction(), newValue);
+        replaceValue(instruction, value, newValue);
+    }
+
+    private static void replaceValue(LIRInstruction op, Value oldValue, Value newValue) {
+        ValueProcedure proc = (value, mode, flags) -> value.identityEquals(oldValue) ? newValue : value;
+        op.forEachAlive(proc);
+        op.forEachInput(proc);
+        op.forEachOutput(proc);
+        op.forEachTemp(proc);
+        op.forEachState(proc);
     }
 
     public Value getValue() {
-        return position.get(instruction);
+        return value;
     }
 
     @Override