[CF] Compute stack-map frames.

This adds stack-maps for all locals. This is very simple at the moment because
stack is empty on all joins of more than one control edge, thus only types of
locals are needed. Due to the lack of register allocation, local indexes are
invariant and map to a unique SSA value or phi. The verification types are
computed as a fixed-point over the flow of values (so phis will resolve to
the join/least-upper-bound of its inflows).

Change-Id: I300f41c86e9a71d0df83944c7f9aee08f35f0ba9
diff --git a/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java b/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java
new file mode 100644
index 0000000..7215eed
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/LoadStoreHelper.java
@@ -0,0 +1,146 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.cf;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.ConstClass;
+import com.android.tools.r8.ir.code.ConstInstruction;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.ConstString;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.Load;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Pop;
+import com.android.tools.r8.ir.code.Position;
+import com.android.tools.r8.ir.code.StackValue;
+import com.android.tools.r8.ir.code.Store;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.ir.conversion.CfBuilder.FixedLocal;
+import java.util.Map;
+
+public class LoadStoreHelper {
+
+  private final IRCode code;
+  private final Map<Value, DexType> types;
+
+  public LoadStoreHelper(IRCode code, Map<Value, DexType> types) {
+    this.code = code;
+    this.types = types;
+  }
+
+  public void insertLoadsAndStores() {
+    // Insert phi stores in all predecessors.
+    for (BasicBlock block : code.blocks) {
+      if (!block.getPhis().isEmpty()) {
+        for (int predIndex = 0; predIndex < block.getPredecessors().size(); predIndex++) {
+          BasicBlock pred = block.getPredecessors().get(predIndex);
+          for (Phi phi : block.getPhis()) {
+            Value value = phi.getOperand(predIndex);
+            InstructionListIterator it = pred.listIterator(pred.getInstructions().size());
+            it.previous();
+            movePhi(phi, value, it);
+          }
+        }
+      }
+    }
+    // Insert per-instruction loads and stores.
+    for (BasicBlock block : code.blocks) {
+      InstructionListIterator it = block.listIterator();
+      while (it.hasNext()) {
+        Instruction current = it.next();
+        current.insertLoadAndStores(it, this);
+      }
+    }
+  }
+
+  private StackValue createStackValue(Value value, int height) {
+    if (value.outType().isObject()) {
+      return StackValue.forObjectType(types.get(value), height);
+    }
+    return StackValue.forNonObjectType(value.outType(), height);
+  }
+
+  private StackValue createStackValue(DexType type, int height) {
+    if (type.isPrimitiveType()) {
+      return StackValue.forNonObjectType(ValueType.fromDexType(type), height);
+    }
+    return StackValue.forObjectType(type, height);
+  }
+
+  public void loadInValues(Instruction instruction, InstructionListIterator it) {
+    int topOfStack = 0;
+    it.previous();
+    for (Value value : instruction.inValues()) {
+      StackValue stackValue = createStackValue(value, topOfStack++);
+      add(load(stackValue, value), instruction, it);
+      value.removeUser(instruction);
+      instruction.replaceValue(value, stackValue);
+    }
+    it.next();
+  }
+
+  public void storeOutValue(Instruction instruction, InstructionListIterator it) {
+    if (instruction.outValue() instanceof StackValue) {
+      assert instruction.isConstInstruction();
+      return;
+    }
+    StackValue newOutValue = createStackValue(instruction.outValue(), 0);
+    Value oldOutValue = instruction.swapOutValue(newOutValue);
+    add(new Store(oldOutValue, newOutValue), instruction, it);
+  }
+
+  public void popOutValue(Value value, Instruction instruction, InstructionListIterator it) {
+    StackValue newOutValue = createStackValue(value, 0);
+    instruction.swapOutValue(newOutValue);
+    add(new Pop(newOutValue), instruction, it);
+  }
+
+  public void popOutType(DexType type, Instruction instruction, InstructionListIterator it) {
+    StackValue newOutValue = createStackValue(type, 0);
+    instruction.swapOutValue(newOutValue);
+    add(new Pop(newOutValue), instruction, it);
+  }
+
+  public void movePhi(Phi phi, Value value, InstructionListIterator it) {
+    StackValue tmp = createStackValue(phi, 0);
+    FixedLocal out = new FixedLocal(phi);
+    add(load(tmp, value), phi.getBlock(), Position.none(), it);
+    add(new Store(out, tmp), phi.getBlock(), Position.none(), it);
+    value.removePhiUser(phi);
+    phi.replaceUsers(out);
+  }
+
+  private Instruction load(StackValue stackValue, Value value) {
+    if (value.isConstant()) {
+      ConstInstruction constant = value.getConstInstruction();
+      if (constant.isConstNumber()) {
+        return new ConstNumber(stackValue, constant.asConstNumber().getRawValue());
+      } else if (constant.isConstString()) {
+        return new ConstString(stackValue, constant.asConstString().getValue());
+      } else if (constant.isConstClass()) {
+        return new ConstClass(stackValue, constant.asConstClass().getValue());
+      } else {
+        throw new Unreachable("Unexpected constant value: " + value);
+      }
+    }
+    return new Load(stackValue, value);
+  }
+
+  private static void add(
+      Instruction newInstruction, Instruction existingInstruction, InstructionListIterator it) {
+    add(newInstruction, existingInstruction.getBlock(), existingInstruction.getPosition(), it);
+  }
+
+  private static void add(
+      Instruction newInstruction, BasicBlock block, Position position, InstructionListIterator it) {
+    newInstruction.setBlock(block);
+    newInstruction.setPosition(position);
+    it.add(newInstruction);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
new file mode 100644
index 0000000..d22ff65
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
@@ -0,0 +1,119 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.cf;
+
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.Value;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+// Compute the types of all reference values.
+// The actual types are needed to emit stack-map frames for Java 1.6 and above.
+public class TypeVerificationHelper {
+
+  private final IRCode code;
+  private final DexItemFactory factory;
+
+  private Map<Value, DexType> types;
+
+  public TypeVerificationHelper(IRCode code, DexItemFactory factory) {
+    this.code = code;
+    this.factory = factory;
+  }
+
+  public DexItemFactory getFactory() {
+    return factory;
+  }
+
+  public DexType getType(Value value) {
+    assert value.outType().isObject();
+    return types.get(value);
+  }
+
+  // Helper to compute the join of a set of reference types.
+  public DexType join(Set<DexType> types) {
+    if (types.isEmpty()) {
+      return null; // Bottom element. Unknown type.
+    }
+    if (types.size() != 1) {
+      throw new Unimplemented("compute the join of the types");
+    }
+    return types.iterator().next();
+  }
+
+  public Map<Value, DexType> computeVerificationTypes() {
+    types = new HashMap<>();
+    Set<Value> worklist = new HashSet<>();
+    {
+      InstructionIterator it = code.instructionIterator();
+      Instruction instruction = null;
+      // Set the out-value types of each argument based on the method signature.
+      int argumentIndex = code.method.accessFlags.isStatic() ? 0 : -1;
+      while (it.hasNext()) {
+        instruction = it.next();
+        if (!instruction.isArgument()) {
+          break;
+        }
+        DexType argumentType =
+            (argumentIndex < 0)
+                ? code.method.method.getHolder()
+                : code.method.method.proto.parameters.values[argumentIndex];
+        Value outValue = instruction.outValue();
+        types.put(outValue, argumentType);
+        addUsers(outValue, worklist);
+        ++argumentIndex;
+      }
+      // Compute the out-value type of each normal instruction with an out-value but no in values.
+      while (instruction != null) {
+        assert !instruction.isArgument();
+        if (instruction.outValue() != null && instruction.outType().isObject()) {
+          Value outValue = instruction.outValue();
+          if (instruction.hasInvariantVerificationType()) {
+            DexType type = instruction.computeVerificationType(this);
+            assert type != null;
+            types.put(outValue, type);
+            addUsers(outValue, worklist);
+          }
+        }
+        instruction = it.hasNext() ? it.next() : null;
+      }
+    }
+    // Compute the fixed-point of all the out-value types.
+    while (!worklist.isEmpty()) {
+      Value item = worklist.iterator().next();
+      worklist.remove(item);
+      DexType previousType = types.get(item);
+      DexType refinedType = computeVerificationType(item);
+      if (previousType != refinedType) {
+        types.put(item, refinedType);
+        addUsers(item, worklist);
+      }
+    }
+    return types;
+  }
+
+  private DexType computeVerificationType(Value value) {
+    return value.isPhi()
+        ? value.asPhi().computeVerificationType(this)
+        : value.definition.computeVerificationType(this);
+  }
+
+  private static void addUsers(Value value, Set<Value> worklist) {
+    worklist.addAll(value.uniquePhiUsers());
+    for (Instruction instruction : value.uniqueUsers()) {
+      if (instruction.outValue() != null
+          && instruction.outType().isObject()
+          && !instruction.hasInvariantVerificationType()) {
+        worklist.add(instruction.outValue());
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfFrame.java b/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
new file mode 100644
index 0000000..11b4acc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/cf/code/CfFrame.java
@@ -0,0 +1,65 @@
+// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.cf.code;
+
+import static org.objectweb.asm.Opcodes.F_NEW;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+import org.objectweb.asm.Type;
+
+public class CfFrame extends CfInstruction {
+
+  private final Int2ReferenceSortedMap<DexType> locals;
+
+  public CfFrame(Int2ReferenceSortedMap<DexType> locals) {
+    this.locals = locals;
+  }
+
+  public void write(MethodVisitor visitor) {
+    int type = F_NEW;
+    int localsSize = locals.size();
+    Object[] localsCopy = new Object[localsSize];
+    int localIndex = 0;
+    for (Entry<DexType> entry : locals.int2ReferenceEntrySet()) {
+      Object typeOpcode = getType(entry.getValue());
+      if (typeOpcode == Opcodes.LONG || typeOpcode == Opcodes.DOUBLE) {
+        localsCopy[localIndex++] = Opcodes.TOP;
+      }
+      localsCopy[localIndex++] = typeOpcode;
+    }
+    // TODO(zerny): Compute the stack types too.
+    visitor.visitFrame(type, localsSize, localsCopy, 0, new Object[0]);
+  }
+
+  private Object getType(DexType type) {
+    if (type == DexItemFactory.nullValueType) {
+      return Opcodes.NULL;
+    }
+    switch (type.toShorty()) {
+      case 'L':
+        return Type.getType(type.toDescriptorString()).getInternalName();
+      case 'I':
+        return Opcodes.INTEGER;
+      case 'F':
+        return Opcodes.FLOAT;
+      case 'J':
+        return Opcodes.LONG;
+      case 'D':
+        return Opcodes.DOUBLE;
+      default:
+        throw new Unreachable("Unexpected value type: " + type);
+    }
+  }
+
+  @Override
+  public String toString() {
+    return getClass().getSimpleName();
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index 4ca9e94..8f45a2e 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -54,7 +54,17 @@
   boolean sorted = false;
 
   public static final DexType catchAllType = new DexType(new DexString("CATCH_ALL"));
-  private static final Set<DexItem> internalSentinels = ImmutableSet.of(catchAllType);
+
+  // Internal type containing only the null value.
+  public static final DexType nullValueType = new DexType(new DexString("NULL"));
+
+  private static final Set<DexItem> internalSentinels = ImmutableSet.of(
+      catchAllType,
+      nullValueType);
+
+  public static boolean isInternalSentinel(DexItem item) {
+    return internalSentinels.contains(item);
+  }
 
   public final DexString booleanDescriptor = createString("Z");
   public final DexString byteDescriptor = createString("B");
@@ -294,7 +304,7 @@
 
   private static <T extends DexItem> T canonicalize(ConcurrentHashMap<T, T> map, T item) {
     assert item != null;
-    assert !internalSentinels.contains(item);
+    assert !DexItemFactory.isInternalSentinel(item);
     T previous = map.putIfAbsent(item, item);
     return previous == null ? item : previous;
   }
@@ -329,7 +339,7 @@
       result = new DexType(descriptor);
       assert result.isArrayType() || result.isClassType() || result.isPrimitiveType() ||
           result.isVoidType();
-      assert !internalSentinels.contains(result);
+      assert !isInternalSentinel(result);
       types.put(descriptor, result);
     }
     return result;
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index d4deb54..69a71f9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -228,8 +228,8 @@
   public String toSourceString() {
     if (toStringCache == null) {
       // TODO(ager): Pass in a ProguardMapReader to map names back to original names.
-      if (this == DexItemFactory.catchAllType) {
-        toStringCache = "CATCH_ALL";
+      if (DexItemFactory.isInternalSentinel(this)) {
+        toStringCache = descriptor.toString();
       } else {
         toStringCache = DescriptorUtils.descriptorToJavaType(toDescriptorString());
       }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Argument.java b/src/main/java/com/android/tools/r8/ir/code/Argument.java
index 4da6eaf..a33c150 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Argument.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Argument.java
@@ -3,11 +3,13 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
@@ -80,11 +82,16 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     // Arguments are defined by locals so nothing to load or store.
   }
 
   @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    throw new Unreachable();
+  }
+
+  @Override
   public void buildCf(CfBuilder builder) {
     builder.addArgument(this);
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
index be0e6db..0fbac8f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.code.CfArrayLoad;
 import com.android.tools.r8.code.Aget;
 import com.android.tools.r8.code.AgetBoolean;
@@ -16,7 +17,6 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -131,9 +131,9 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.loadInValues(this, it);
-    stack.storeOutValue(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.loadInValues(this, it);
+    helper.storeOutValue(this, it);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
index c78f9ad..d02863f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfConstNull;
 import com.android.tools.r8.cf.code.CfConstNumber;
 import com.android.tools.r8.code.Const;
@@ -14,8 +16,8 @@
 import com.android.tools.r8.code.ConstWide32;
 import com.android.tools.r8.code.ConstWideHigh16;
 import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.NumberUtils;
 
@@ -134,8 +136,8 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.storeOutValue(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.storeOutValue(this, it);
   }
 
   @Override
@@ -240,4 +242,10 @@
   public ConstNumber asConstNumber() {
     return this;
   }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    assert outType().isObject();
+    return helper.getFactory().nullValueType;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstString.java b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
index 07c7c53..febbda3 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
@@ -3,11 +3,13 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfConstString;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.InternalOptions;
 
@@ -89,12 +91,17 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.storeOutValue(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.storeOutValue(this, it);
   }
 
   @Override
   public void buildCf(CfBuilder builder) {
     builder.add(new CfConstString(value));
   }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return helper.getFactory().stringType;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugLocalWrite.java b/src/main/java/com/android/tools/r8/ir/code/DebugLocalWrite.java
index 6833568..4355598 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugLocalWrite.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugLocalWrite.java
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.TypeVerificationHelper;
+import com.android.tools.r8.graph.DexType;
+
 /**
  * Instruction introducing an SSA value with attached local information.
  *
@@ -42,4 +45,14 @@
     assert other.isDebugLocalWrite();
     return true;
   }
+
+  @Override
+  public boolean hasInvariantVerificationType() {
+    return false;
+  }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return helper.getType(src());
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java b/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
index dbcf734..78ce128 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DebugPosition.java
@@ -3,11 +3,11 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
@@ -66,7 +66,7 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     // Nothing to do for positions which are not actual instructions.
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/Goto.java b/src/main/java/com/android/tools/r8/ir/code/Goto.java
index 4b88706..95089a7 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Goto.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Goto.java
@@ -3,9 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.code.CfGoto;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
 import java.util.List;
@@ -99,7 +99,7 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     // Nothing to do.
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/If.java b/src/main/java/com/android/tools/r8/ir/code/If.java
index 8cdf209..c6e62af 100644
--- a/src/main/java/com/android/tools/r8/ir/code/If.java
+++ b/src/main/java/com/android/tools/r8/ir/code/If.java
@@ -6,10 +6,10 @@
 import static com.android.tools.r8.dex.Constants.U4BIT_MAX;
 import static com.android.tools.r8.dex.Constants.U8BIT_MAX;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.code.CfIf;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
 import java.util.List;
@@ -191,8 +191,8 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.loadInValues(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.loadInValues(this, it);
   }
 
   @Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index eeee6f8..ca68f64 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -3,13 +3,14 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.errors.Unimplemented;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DebugLocalInfo;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -965,7 +966,19 @@
   // Returns the inlining constraint for this instruction.
   public abstract Constraint inliningConstraint(AppInfoWithSubtyping info, DexType holder);
 
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     throw new Unimplemented("Implement load/store insertion for: " + getInstructionName());
   }
+
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    throw new Unimplemented("Implement verification type computation for: " + getInstructionName());
+  }
+
+  public boolean hasInvariantVerificationType() {
+    if (inValues().isEmpty()) {
+      return true;
+    }
+    throw new Unimplemented(
+        "Implement has-invariant verification type for: " + getInstructionName());
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index fef03c3..e7ca1b7 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -3,13 +3,14 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
 import com.android.tools.r8.ir.optimize.InliningOracle;
@@ -84,15 +85,26 @@
   public abstract InlineAction computeInlining(InliningOracle decider);
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.loadInValues(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.loadInValues(this, it);
     if (method.proto.returnType.isVoidType()) {
       return;
     }
     if (outValue == null) {
-      stack.popOutValue(ValueType.fromDexType(method.proto.returnType), this, it);
+      helper.popOutType(method.proto.returnType, this, it);
     } else {
-      stack.storeOutValue(this, it);
+      assert outValue.isUsed();
+      helper.storeOutValue(this, it);
     }
   }
+
+  @Override
+  public boolean hasInvariantVerificationType() {
+    return true;
+  }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return getInvokedMethod().proto.returnType;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Load.java b/src/main/java/com/android/tools/r8/ir/code/Load.java
index 401a880..74cf861 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Load.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Load.java
@@ -3,12 +3,13 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfLoad;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 
 public class Load extends Instruction {
@@ -59,7 +60,12 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return helper.getType(inValues.get(0));
+  }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     // Nothing to do. This is only hit because loads and stores are insert for phis.
   }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/MoveException.java b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
index 2b419fd..23fdebf 100644
--- a/src/main/java/com/android/tools/r8/ir/code/MoveException.java
+++ b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
@@ -3,14 +3,18 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
 
 public class MoveException extends Instruction {
 
@@ -73,11 +77,11 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     if (outValue.isUsed()) {
-      stack.storeOutValue(this, it);
+      helper.storeOutValue(this, it);
     } else {
-      stack.popOutValue(outValue.type, this, it);
+      helper.popOutValue(outValue, this, it);
     }
   }
 
@@ -85,4 +89,24 @@
   public void buildCf(CfBuilder builder) {
     // Nothing to do. The exception is implicitly pushed on the stack.
   }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    Set<DexType> exceptionTypes = new HashSet<>(getBlock().getPredecessors().size());
+    for (BasicBlock block : getBlock().getPredecessors()) {
+      int size = block.getCatchHandlers().size();
+      List<BasicBlock> targets = block.getCatchHandlers().getAllTargets();
+      List<DexType> guards = block.getCatchHandlers().getGuards();
+      for (int i = 0; i < size; i++) {
+        if (targets.get(i) == getBlock()) {
+          DexType guard = guards.get(i);
+          exceptionTypes.add(
+              guard == helper.getFactory().catchAllType
+                  ? helper.getFactory().throwableType
+                  : guard);
+        }
+      }
+    }
+    return helper.join(exceptionTypes);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
index 1e77217..7c24034 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.code.NewArray;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
@@ -75,4 +76,14 @@
   public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType holder) {
     return Constraint.classIsVisible(holder, type, info);
   }
+
+  @Override
+  public boolean hasInvariantVerificationType() {
+    return true;
+  }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return type;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
index 979b491..f3426a0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
@@ -3,12 +3,13 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfNew;
 import com.android.tools.r8.dex.Constants;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 
@@ -81,12 +82,17 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.storeOutValue(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.storeOutValue(this, it);
   }
 
   @Override
   public void buildCf(CfBuilder builder) {
     builder.add(new CfNew(clazz));
   }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return clazz;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Phi.java b/src/main/java/com/android/tools/r8/ir/code/Phi.java
index faab702..2d9efb0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Phi.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Phi.java
@@ -3,8 +3,10 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.DebugLocalInfo;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.BasicBlock.EdgeType;
 import com.android.tools.r8.ir.conversion.IRBuilder;
 import com.android.tools.r8.utils.CfgPrinter;
@@ -371,4 +373,16 @@
   public boolean usesValueOneTime(Value usedValue) {
     return operands.indexOf(usedValue) == operands.lastIndexOf(usedValue);
   }
+
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    assert outType().isObject();
+    Set<DexType> operandTypes = new HashSet<>(operands.size());
+    for (Value operand : operands) {
+      DexType operandType = helper.getType(operand);
+      if (operandType != null) {
+        operandTypes.add(operandType);
+      }
+    }
+    return helper.join(operandTypes);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Return.java b/src/main/java/com/android/tools/r8/ir/code/Return.java
index a197c87..1177abb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Return.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Return.java
@@ -3,6 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
 import com.android.tools.r8.cf.code.CfReturn;
 import com.android.tools.r8.code.MoveType;
 import com.android.tools.r8.code.ReturnObject;
@@ -13,7 +14,6 @@
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 
@@ -117,9 +117,9 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     if (!isReturnVoid()) {
-      stack.loadInValues(this, it);
+      helper.loadInValues(this, it);
     }
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/code/StackValue.java b/src/main/java/com/android/tools/r8/ir/code/StackValue.java
index 3bf1417..65c4d3f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StackValue.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StackValue.java
@@ -3,16 +3,40 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
+
 public class StackValue extends Value {
 
   private final int height;
+  private final DexType objectType;
 
-  public StackValue(ValueType type, int height) {
-    super(Value.UNDEFINED_NUMBER, type, null);
+  private StackValue(DexType objectType, ValueType valueType, int height) {
+    super(Value.UNDEFINED_NUMBER, valueType, null);
     this.height = height;
+    this.objectType = objectType;
     assert height >= 0;
   }
 
+  public static StackValue forObjectType(DexType type, int height) {
+    assert DexItemFactory.nullValueType == type || type.isClassType();
+    return new StackValue(type, ValueType.OBJECT, height);
+  }
+
+  public static StackValue forNonObjectType(ValueType valueType, int height) {
+    assert valueType.isPreciseType() && !valueType.isObject();
+    return new StackValue(null, valueType, height);
+  }
+
+  public int getHeight() {
+    return height;
+  }
+
+  public DexType getObjectType() {
+    assert outType().isObject();
+    return objectType;
+  }
+
   @Override
   public String toString() {
     return "s" + height;
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
index 23069f2..32871b3 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
@@ -3,6 +3,8 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfStaticGet;
 import com.android.tools.r8.code.Sget;
 import com.android.tools.r8.code.SgetBoolean;
@@ -18,7 +20,6 @@
 import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.conversion.DexBuilder;
 
 public class StaticGet extends FieldInstruction {
@@ -121,12 +122,17 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
-    stack.storeOutValue(this, it);
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
+    helper.storeOutValue(this, it);
   }
 
   @Override
   public void buildCf(CfBuilder builder) {
     builder.add(new CfStaticGet(field));
   }
+
+  @Override
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return field.type;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/Store.java b/src/main/java/com/android/tools/r8/ir/code/Store.java
index bc1e419..7bdf7ad 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Store.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Store.java
@@ -3,13 +3,14 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.code;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
 import com.android.tools.r8.cf.code.CfStore;
 import com.android.tools.r8.errors.Unreachable;
 import com.android.tools.r8.graph.AppInfoWithSubtyping;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.conversion.CfBuilder;
 import com.android.tools.r8.ir.conversion.CfBuilder.FixedLocal;
-import com.android.tools.r8.ir.conversion.CfBuilder.StackHelper;
 import com.android.tools.r8.ir.optimize.Inliner.Constraint;
 import com.android.tools.r8.utils.InternalOptions;
 
@@ -60,7 +61,12 @@
   }
 
   @Override
-  public void insertLoadAndStores(InstructionListIterator it, StackHelper stack) {
+  public DexType computeVerificationType(TypeVerificationHelper helper) {
+    return helper.getType(inValues.get(0));
+  }
+
+  @Override
+  public void insertLoadAndStores(InstructionListIterator it, LoadStoreHelper helper) {
     // Nothing to do. This is only hit because loads and stores are insert for phis.
   }
 
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
index f07b61e..835cae2 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
@@ -3,6 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.ir.conversion;
 
+import com.android.tools.r8.cf.LoadStoreHelper;
+import com.android.tools.r8.cf.TypeVerificationHelper;
+import com.android.tools.r8.cf.code.CfFrame;
 import com.android.tools.r8.cf.code.CfInstruction;
 import com.android.tools.r8.cf.code.CfLabel;
 import com.android.tools.r8.cf.code.CfTryCatch;
@@ -11,31 +14,30 @@
 import com.android.tools.r8.graph.CfCode;
 import com.android.tools.r8.graph.Code;
 import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.ir.code.Argument;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.CatchHandlers;
-import com.android.tools.r8.ir.code.ConstClass;
-import com.android.tools.r8.ir.code.ConstInstruction;
-import com.android.tools.r8.ir.code.ConstNumber;
-import com.android.tools.r8.ir.code.ConstString;
 import com.android.tools.r8.ir.code.IRCode;
 import com.android.tools.r8.ir.code.Instruction;
 import com.android.tools.r8.ir.code.InstructionIterator;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.Load;
 import com.android.tools.r8.ir.code.Phi;
-import com.android.tools.r8.ir.code.Pop;
-import com.android.tools.r8.ir.code.Position;
 import com.android.tools.r8.ir.code.StackValue;
 import com.android.tools.r8.ir.code.Store;
 import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.code.ValueType;
 import com.android.tools.r8.ir.optimize.CodeRewriter;
 import com.android.tools.r8.ir.optimize.DeadCodeRemover;
 import com.android.tools.r8.utils.InternalOptions;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
 import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
@@ -44,15 +46,16 @@
 
 public class CfBuilder {
 
+  private final DexItemFactory factory;
   private final DexEncodedMethod method;
   private final IRCode code;
 
   private int maxLocals = -1;
-  private int maxStack = 0;
-  private int currentStack = 0;
-  private List<CfInstruction> instructions;
+
+  private Map<Value, DexType> types;
   private Reference2IntMap<Value> registers;
   private Map<BasicBlock, CfLabel> labels;
+  private List<CfInstruction> instructions;
 
   /**
    * Value that represents a shared physical location defined by the phi value.
@@ -81,94 +84,44 @@
     }
   }
 
-  public static class StackHelper {
+  // Internal abstraction of the stack values and height.
+  private static class Stack {
+    int maxHeight = 0;
+    int height = 0;
 
-    private int currentStackHeight = 0;
-
-    public void loadInValues(Instruction instruction, InstructionListIterator it) {
-      int topOfStack = currentStackHeight;
-      it.previous();
-      for (Value value : instruction.inValues()) {
-        StackValue stackValue = new StackValue(value.outType(), topOfStack++);
-        add(load(stackValue, value), instruction, it);
-        value.removeUser(instruction);
-        instruction.replaceValue(value, stackValue);
-      }
-      it.next();
+    boolean isEmpty() {
+      return height == 0;
     }
 
-    public void storeOutValue(Instruction instruction, InstructionListIterator it) {
-      if (instruction.outValue() instanceof StackValue) {
-        assert instruction.isConstInstruction();
-        return;
-      }
-      StackValue newOutValue = new StackValue(instruction.outType(), currentStackHeight);
-      Value oldOutValue = instruction.swapOutValue(newOutValue);
-      add(new Store(oldOutValue, newOutValue), instruction, it);
+    void push(Value value) {
+      assert value instanceof StackValue;
+      height += value.requiredRegisters();
+      maxHeight = Math.max(maxHeight, height);
     }
 
-    public void popOutValue(ValueType type, Instruction instruction, InstructionListIterator it) {
-      StackValue newOutValue = new StackValue(type, currentStackHeight);
-      instruction.swapOutValue(newOutValue);
-      add(new Pop(newOutValue), instruction, it);
+    void pop(Value value) {
+      assert value instanceof StackValue;
+      height -= value.requiredRegisters();
     }
-
-    public void movePhi(Phi phi, Value value, InstructionListIterator it) {
-      StackValue tmp = new StackValue(phi.outType(), currentStackHeight);
-      FixedLocal out = new FixedLocal(phi);
-      add(load(tmp, value), phi.getBlock(), Position.none(), it);
-      add(new Store(out, tmp), phi.getBlock(), Position.none(), it);
-      value.removePhiUser(phi);
-      phi.replaceUsers(out);
-    }
-
-    private Instruction load(StackValue stackValue, Value value) {
-      if (value.isConstant()) {
-        ConstInstruction constant = value.getConstInstruction();
-        if (constant.isConstNumber()) {
-          return new ConstNumber(stackValue, constant.asConstNumber().getRawValue());
-        } else if (constant.isConstString()) {
-          return new ConstString(stackValue, constant.asConstString().getValue());
-        } else if (constant.isConstClass()) {
-          return new ConstClass(stackValue, constant.asConstClass().getValue());
-        } else {
-          throw new Unreachable("Unexpected constant value: " + value);
-        }
-      }
-      return new Load(stackValue, value);
-    }
-
-    private static void add(
-        Instruction newInstruction, Instruction existingInstruction, InstructionListIterator it) {
-      add(newInstruction, existingInstruction.getBlock(), existingInstruction.getPosition(), it);
-    }
-
-    private static void add(
-        Instruction newInstruction,
-        BasicBlock block,
-        Position position,
-        InstructionListIterator it) {
-      newInstruction.setBlock(block);
-      newInstruction.setPosition(position);
-      it.add(newInstruction);
-    }
-
   }
 
-  public CfBuilder(DexEncodedMethod method, IRCode code) {
+  public CfBuilder(DexEncodedMethod method, IRCode code, DexItemFactory factory) {
     this.method = method;
     this.code = code;
+    this.factory = factory;
   }
 
   public Code build(CodeRewriter rewriter, InternalOptions options) {
     try {
+      types = new TypeVerificationHelper(code, factory).computeVerificationTypes();
       splitExceptionalBlocks();
-      loadStoreInsertion();
+      new LoadStoreHelper(code, types).insertLoadsAndStores();
       DeadCodeRemover.removeDeadCode(code, rewriter, options);
       removeUnneededLoadsAndStores();
       allocateLocalRegisters();
       // TODO(zerny): Compute debug info.
-      return buildCfCode();
+      CfCode code = buildCfCode();
+      return code;
     } catch (Unimplemented e) {
       System.out.println("Incomplete CF construction: " + e.getMessage());
       return method.getCode().asJarCode();
@@ -207,32 +160,6 @@
     }
   }
 
-  private void loadStoreInsertion() {
-    StackHelper stack = new StackHelper();
-    // Insert phi stores in all predecessors.
-    for (BasicBlock block : code.blocks) {
-      if (!block.getPhis().isEmpty()) {
-        for (int predIndex = 0; predIndex < block.getPredecessors().size(); predIndex++) {
-          BasicBlock pred = block.getPredecessors().get(predIndex);
-          for (Phi phi : block.getPhis()) {
-            Value value = phi.getOperand(predIndex);
-            InstructionListIterator it = pred.listIterator(pred.getInstructions().size());
-            it.previous();
-            stack.movePhi(phi, value, it);
-          }
-        }
-      }
-    }
-    // Insert per-instruction loads and stores.
-    for (BasicBlock block : code.blocks) {
-      InstructionListIterator it = block.listIterator();
-      while (it.hasNext()) {
-        Instruction current = it.next();
-        current.insertLoadAndStores(it, stack);
-      }
-    }
-  }
-
   private void removeUnneededLoadsAndStores() {
     Iterator<BasicBlock> blockIterator = code.listIterator();
     while (blockIterator.hasNext()) {
@@ -287,18 +214,8 @@
     maxLocals = nextFreeRegister;
   }
 
-  private void push(Value value) {
-    assert value instanceof StackValue;
-    currentStack += value.requiredRegisters();
-    maxStack = Math.max(maxStack, currentStack);
-  }
-
-  private void pop(Value value) {
-    assert value instanceof StackValue;
-    currentStack -= value.requiredRegisters();
-  }
-
   private CfCode buildCfCode() {
+    Stack stack = new Stack();
     List<CfTryCatch> tryCatchRanges = new ArrayList<>();
     labels = new HashMap<>(code.blocks.size());
     instructions = new ArrayList<>();
@@ -328,39 +245,73 @@
         tryCatchHandlers = handlers;
       }
       BasicBlock nextBlock = blockIterator.hasNext() ? blockIterator.next() : null;
-      buildCfInstructions(block, nextBlock);
+      boolean fallthrough = block.exit().isGoto() && block.exit().asGoto().getTarget() == nextBlock;
+      buildCfInstructions(block, fallthrough, stack);
+      if (nextBlock != null && (!fallthrough || nextBlock.getPredecessors().size() > 1)) {
+        assert stack.isEmpty();
+        instructions.add(getLabel(nextBlock));
+        if (nextBlock.getPredecessors().size() > 1) {
+          addFrame(Collections.emptyList(), types.keySet());
+        }
+      }
       block = nextBlock;
     } while (block != null);
-    assert currentStack == 0;
-    return new CfCode(maxStack, maxLocals, instructions, tryCatchRanges);
+    assert stack.isEmpty();
+    return new CfCode(stack.maxHeight, maxLocals, instructions, tryCatchRanges);
   }
 
-  private void buildCfInstructions(BasicBlock block, BasicBlock nextBlock) {
-    boolean fallthrough = false;
+  private void buildCfInstructions(BasicBlock block, boolean fallthrough, Stack stack) {
     InstructionIterator it = block.iterator();
     while (it.hasNext()) {
       Instruction instruction = it.next();
-      if (instruction.isGoto() && instruction.asGoto().getTarget() == nextBlock) {
-        fallthrough = true;
-        continue;
+      if (fallthrough && instruction.isGoto()) {
+        assert block.exit() == instruction;
+        return;
       }
-      for (Value inValue : instruction.inValues()) {
-        if (inValue instanceof StackValue) {
-          pop(inValue);
+      for (int i = instruction.inValues().size() - 1; i >= 0; i--) {
+        if (instruction.inValues().get(i) instanceof StackValue) {
+          stack.pop(instruction.inValues().get(i));
         }
       }
       if (instruction.outValue() != null) {
         Value outValue = instruction.outValue();
         if (outValue instanceof StackValue) {
-          push(outValue);
+          stack.push(outValue);
         }
       }
       instruction.buildCf(this);
     }
-    if (nextBlock == null || (fallthrough && nextBlock.getPredecessors().size() == 1)) {
-      return;
+  }
+
+  private void addFrame(Collection<StackValue> stack, Collection<Value> locals) {
+    // TODO(zerny): Support having values on the stack on control-edges.
+    assert stack.isEmpty();
+    Int2ReferenceSortedMap<DexType> mapping = new Int2ReferenceAVLTreeMap();
+    for (Value local : locals) {
+      DexType type;
+      switch (local.outType()) {
+        case INT:
+          type = factory.intType;
+          break;
+        case FLOAT:
+          type = factory.floatType;
+          break;
+        case LONG:
+          type = factory.longType;
+          break;
+        case DOUBLE:
+          type = factory.doubleType;
+          break;
+        case OBJECT:
+          type = types.get(local);
+          break;
+        default:
+          throw new Unreachable(
+              "Unexpected local type: " + local.outType() + " for local: " + local);
+      }
+      mapping.put(getLocalRegister(local), type);
     }
-    instructions.add(getLabel(nextBlock));
+    instructions.add(new CfFrame(mapping));
   }
 
   // Callbacks
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index a9735c4..6728afe 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -590,7 +590,7 @@
 
   private void finalizeToCf(DexEncodedMethod method, IRCode code, OptimizationFeedback feedback) {
     assert method.getCode().isJarCode();
-    CfBuilder builder = new CfBuilder(method, code);
+    CfBuilder builder = new CfBuilder(method, code, options.itemFactory);
     // TODO(zerny): Change the return type of CfBuilder::build CfCode once complete.
     Code result = builder.build(codeRewriter, options);
     assert result.isCfCode() || result.isJarCode();