diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index fd5c29f..50f79dc 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -17,6 +17,8 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.GraphLense;
 import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.ir.optimize.EnumOrdinalMapCollector;
+import com.android.tools.r8.ir.optimize.SwitchMapCollector;
 import com.android.tools.r8.naming.Minifier;
 import com.android.tools.r8.naming.NamingLens;
 import com.android.tools.r8.optimize.BridgeMethodAnalysis;
@@ -36,6 +38,7 @@
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.shaking.SimpleClassMerger;
 import com.android.tools.r8.shaking.TreePruner;
+import com.android.tools.r8.shaking.protolite.ProtoLiteExtension;
 import com.android.tools.r8.utils.AndroidApp;
 import com.android.tools.r8.utils.CfgPrinter;
 import com.android.tools.r8.utils.FileUtils;
@@ -241,6 +244,7 @@
         }
         rootSet = new RootSetBuilder(application, appInfo, options.keepRules).run(executorService);
         Enqueuer enqueuer = new Enqueuer(appInfo);
+        enqueuer.addExtension(new ProtoLiteExtension(appInfo));
         appInfo = enqueuer.traceApplication(rootSet, timing);
         if (options.printSeeds) {
           ByteArrayOutputStream bytes = new ByteArrayOutputStream();
@@ -270,8 +274,7 @@
 
       GraphLense graphLense = GraphLense.getIdentityLense();
 
-      if (appInfo.withLiveness() != null) {
-        // No-op until class merger is added.
+      if (appInfo.hasLiveness()) {
         graphLense = new MemberRebindingAnalysis(appInfo.withLiveness(), graphLense).run();
         // Class merging requires inlining.
         if (!options.skipClassMerging && options.inlineAccessors) {
@@ -282,6 +285,9 @@
         }
         appInfo = appInfo.withLiveness().prunedCopyFrom(application);
         appInfo = appInfo.withLiveness().rewrittenWithLense(graphLense);
+        // Collect switch maps and ordinals maps.
+        new SwitchMapCollector(appInfo.withLiveness(), options).run();
+        new EnumOrdinalMapCollector(appInfo.withLiveness(), options).run();
       }
 
       graphLense = new BridgeMethodAnalysis(graphLense, appInfo.withSubtyping()).run();
diff --git a/src/main/java/com/android/tools/r8/R8Command.java b/src/main/java/com/android/tools/r8/R8Command.java
index 1f45dec..8d3d937 100644
--- a/src/main/java/com/android/tools/r8/R8Command.java
+++ b/src/main/java/com/android/tools/r8/R8Command.java
@@ -87,6 +87,7 @@
       minimalMainDex = value;
       return self();
     }
+
     /**
      * Add proguard configuration file resources.
      */
diff --git a/src/main/java/com/android/tools/r8/graph/DelegatingUseRegistry.java b/src/main/java/com/android/tools/r8/graph/DelegatingUseRegistry.java
new file mode 100644
index 0000000..0e28d3d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/DelegatingUseRegistry.java
@@ -0,0 +1,68 @@
+// 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.graph;
+
+public class DelegatingUseRegistry extends UseRegistry {
+    private final UseRegistry delegate;
+
+    public DelegatingUseRegistry(UseRegistry delegate) {
+      this.delegate = delegate;
+    }
+
+    @Override
+    public boolean registerInvokeVirtual(DexMethod method) {
+      return delegate.registerInvokeVirtual(method);
+    }
+
+    @Override
+    public boolean registerInvokeDirect(DexMethod method) {
+      return delegate.registerInvokeDirect(method);
+    }
+
+    @Override
+    public boolean registerInvokeStatic(DexMethod method) {
+      return delegate.registerInvokeStatic(method);
+    }
+
+    @Override
+    public boolean registerInvokeInterface(DexMethod method) {
+      return delegate.registerInvokeInterface(method);
+    }
+
+    @Override
+    public boolean registerInvokeSuper(DexMethod method) {
+      return delegate.registerInvokeSuper(method);
+    }
+
+    @Override
+    public boolean registerInstanceFieldWrite(DexField field) {
+      return delegate.registerInstanceFieldWrite(field);
+    }
+
+    @Override
+    public boolean registerInstanceFieldRead(DexField field) {
+      return delegate.registerInstanceFieldRead(field);
+    }
+
+    @Override
+    public boolean registerNewInstance(DexType type) {
+      return delegate.registerNewInstance(type);
+    }
+
+    @Override
+    public boolean registerStaticFieldRead(DexField field) {
+      return delegate.registerStaticFieldRead(field);
+    }
+
+    @Override
+    public boolean registerStaticFieldWrite(DexField field) {
+      return delegate.registerStaticFieldWrite(field);
+    }
+
+    @Override
+    public boolean registerTypeReference(DexType type) {
+      return delegate.registerTypeReference(type);
+    }
+
+}
diff --git a/src/main/java/com/android/tools/r8/graph/DexString.java b/src/main/java/com/android/tools/r8/graph/DexString.java
index 25416d9..e6914ec 100644
--- a/src/main/java/com/android/tools/r8/graph/DexString.java
+++ b/src/main/java/com/android/tools/r8/graph/DexString.java
@@ -321,4 +321,28 @@
     builder.append("]");
     return builder.toString();
   }
+
+  public boolean beginsWith(DexString prefix) {
+    if (content.length < prefix.content.length) {
+      return false;
+    }
+    for (int i = 0; i < prefix.content.length - 1; i++) {
+      if (content[i] != prefix.content[i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  public boolean endsWith(DexString suffix) {
+    if (content.length < suffix.content.length) {
+      return false;
+    }
+    for (int i = content.length - suffix.content.length, j = 0; i < content.length; i++, j++) {
+      if (content[i] != suffix.content[j]) {
+        return false;
+      }
+    }
+    return true;
+  }
 }
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 ac7d9ee..e06c0ad 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -139,6 +139,11 @@
 
   private boolean isSubtypeOfClass(DexType other, AppInfo appInfo) {
     DexType self = this;
+    if (other.hierarchyLevel == UNKNOWN_LEVEL) {
+      // We have no definition for this class, hence it is not part of the
+      // hierarchy.
+      return false;
+    }
     while (other.hierarchyLevel < self.hierarchyLevel) {
       DexClass holder = appInfo.definitionFor(self);
       assert holder != null && !holder.isInterface();
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 5c9d171..5f1b33f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -44,6 +44,12 @@
     return localsAtEntry;
   }
 
+  public void replaceLastInstruction(Instruction instruction) {
+    InstructionListIterator iterator = listIterator(getInstructions().size());
+    iterator.previous();
+    iterator.replaceCurrentInstruction(instruction);
+  }
+
   public enum ThrowingInfo {
     NO_THROW, CAN_THROW
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java b/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java
index b5a7b75..9f28eea 100644
--- a/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java
+++ b/src/main/java/com/android/tools/r8/ir/code/DominatorTree.java
@@ -87,6 +87,29 @@
     return dominator;
   }
 
+  /**
+   * Returns an iterator over all blocks dominated by dominator, including dominator itself.
+   */
+  public Iterable<BasicBlock> dominatedBlocks(BasicBlock domintator) {
+    return () -> new Iterator<BasicBlock>() {
+      private int current = domintator.getNumber();
+
+      @Override
+      public boolean hasNext() {
+        return dominatedBy(sorted[current], domintator);
+      }
+
+      @Override
+      public BasicBlock next() {
+        if (!hasNext()) {
+          return null;
+        } else {
+          return sorted[current++];
+        }
+      }
+    };
+  }
+
   public BasicBlock[] getSortedBlocks() {
     return sorted;
   }
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 7c37649..824d75c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -390,4 +390,9 @@
   public final int getHighestBlockNumber() {
     return blocks.stream().max(Comparator.comparingInt(BasicBlock::getNumber)).get().getNumber();
   }
+
+  public Instruction createConstNull(Instruction from) {
+    Value newValue = createValue(from.outType());
+    return new ConstNumber(ConstType.fromMoveType(from.outType()), newValue, 0);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java
index 997b092..2cb8185 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionIterator.java
@@ -4,9 +4,7 @@
 
 package com.android.tools.r8.ir.code;
 
-import java.util.Iterator;
-
-public interface InstructionIterator extends Iterator<Instruction> {
+public interface InstructionIterator extends NextUntilIterator<Instruction> {
   /**
    * Replace the current instruction (aka the {@link Instruction} returned by the previous call to
    * {@link #next} with the passed in <code>newInstruction</code>.
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
index bb88b64..431d338 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstructionListIterator.java
@@ -10,7 +10,8 @@
 import java.util.ListIterator;
 import java.util.function.Predicate;
 
-public interface InstructionListIterator extends ListIterator<Instruction> {
+public interface InstructionListIterator extends ListIterator<Instruction>,
+    NextUntilIterator<Instruction> {
 
   /**
    * Peek the previous instruction.
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
index cdc8644..6ccf1cc 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethodWithReceiver.java
@@ -34,6 +34,9 @@
     return this;
   }
 
+  public Value getReceiver() {
+    return inValues.get(0);
+  }
 
   @Override
   public final InlineAction computeInlining(InliningOracle decider) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/NextUntilIterator.java b/src/main/java/com/android/tools/r8/ir/code/NextUntilIterator.java
new file mode 100644
index 0000000..d15376e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/code/NextUntilIterator.java
@@ -0,0 +1,26 @@
+// 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.ir.code;
+
+import java.util.Iterator;
+import java.util.function.Predicate;
+
+public interface NextUntilIterator<T> extends Iterator<T> {
+
+  /**
+   * Continue to call {@link #next} while {@code predicate} tests {@code false}.
+   *
+   * @returns the item that matched the predicate or {@code null} if all items fail
+   * the predicate test
+   */
+  default T nextUntil(Predicate<T> predicate) {
+    while (hasNext()) {
+      T item = next();
+      if (predicate.test(item)) {
+        return item;
+      }
+    }
+    return null;
+  }
+}
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 e6b592d..8e613c0 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
@@ -32,6 +32,7 @@
 import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
 import com.android.tools.r8.ir.regalloc.RegisterAllocator;
 import com.android.tools.r8.logging.Log;
+import com.android.tools.r8.shaking.protolite.ProtoLitePruner;
 import com.android.tools.r8.utils.CfgPrinter;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
@@ -64,9 +65,10 @@
   private final MemberValuePropagation memberValuePropagation;
   private final LensCodeRewriter lensCodeRewriter;
   private final Inliner inliner;
+  private final ProtoLitePruner protoLiteRewriter;
   private CallGraph callGraph;
-  private OptimizationFeedback ignoreOptimizationFeedback = new OptimizationFeedbackIgnore();
 
+  private OptimizationFeedback ignoreOptimizationFeedback = new OptimizationFeedbackIgnore();
   private DexString highestSortingString;
 
   private IRConverter(
@@ -94,16 +96,22 @@
         (enableDesugaring && enableInterfaceMethodDesugaring())
             ? new InterfaceMethodRewriter(this) : null;
     if (enableWholeProgramOptimizations) {
-      assert appInfo.withSubtyping() != null;
+      assert appInfo.hasSubtyping();
       this.inliner = new Inliner(appInfo.withSubtyping(), graphLense, options);
       this.outliner = new Outliner(appInfo, options);
       this.memberValuePropagation = new MemberValuePropagation(appInfo);
       this.lensCodeRewriter = new LensCodeRewriter(graphLense, appInfo.withSubtyping());
+      if (appInfo.hasLiveness()) {
+        this.protoLiteRewriter = new ProtoLitePruner(appInfo.withLiveness());
+      } else {
+        this.protoLiteRewriter = null;
+      }
     } else {
       this.inliner = null;
       this.outliner = null;
       this.memberValuePropagation = null;
       this.lensCodeRewriter = null;
+      this.protoLiteRewriter = null;
     }
   }
 
@@ -427,15 +435,20 @@
     printC1VisualizerHeader(method);
     printMethod(code, "Initial IR (SSA)");
 
-    if (lensCodeRewriter != null) {
-      lensCodeRewriter.rewrite(code, method);
-    } else {
-      assert graphLense.isIdentityLense();
+    if (!method.isProcessed()) {
+      if (protoLiteRewriter != null && protoLiteRewriter.appliesTo(method)) {
+        protoLiteRewriter.rewriteProtoLiteSpecialMethod(code, method);
+      }
+      if (lensCodeRewriter != null) {
+        lensCodeRewriter.rewrite(code, method);
+      } else {
+        assert graphLense.isIdentityLense();
+      }
     }
     if (memberValuePropagation != null) {
       memberValuePropagation.rewriteWithConstantValues(code);
     }
-    if (options.removeSwitchMaps) {
+    if (options.removeSwitchMaps && appInfo.hasLiveness()) {
       // TODO(zerny): Should we support removeSwitchMaps in debug mode? b/62936642
       assert !options.debug;
       codeRewriter.removeSwitchMaps(code);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 14cd563..b1cdcbc 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -9,12 +9,10 @@
 import com.android.tools.r8.graph.AppInfo;
 import com.android.tools.r8.graph.DexClass;
 import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexField;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProto;
 import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.code.ArrayGet;
 import com.android.tools.r8.ir.code.ArrayPut;
 import com.android.tools.r8.ir.code.BasicBlock;
 import com.android.tools.r8.ir.code.Binop;
@@ -32,7 +30,6 @@
 import com.android.tools.r8.ir.code.InstructionIterator;
 import com.android.tools.r8.ir.code.InstructionListIterator;
 import com.android.tools.r8.ir.code.Invoke;
-import com.android.tools.r8.ir.code.InvokeDirect;
 import com.android.tools.r8.ir.code.InvokeMethod;
 import com.android.tools.r8.ir.code.InvokeVirtual;
 import com.android.tools.r8.ir.code.MemberType;
@@ -47,6 +44,7 @@
 import com.android.tools.r8.ir.code.Switch;
 import com.android.tools.r8.ir.code.Value;
 import com.android.tools.r8.ir.conversion.OptimizationFeedback;
+import com.android.tools.r8.ir.optimize.SwitchUtils.EnumSwitchInfo;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.LongInterval;
 import com.google.common.base.Equivalence;
@@ -56,12 +54,8 @@
 import com.google.common.collect.ListMultimap;
 import it.unimi.dsi.fastutil.ints.Int2IntArrayMap;
 import it.unimi.dsi.fastutil.ints.Int2IntMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
 import it.unimi.dsi.fastutil.ints.IntArrayList;
 import it.unimi.dsi.fastutil.ints.IntList;
-import it.unimi.dsi.fastutil.objects.Reference2IntArrayMap;
-import it.unimi.dsi.fastutil.objects.Reference2IntMap;
 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.HashMap;
@@ -371,8 +365,6 @@
    *   ...
    * }
    * </pre></blockquote>
-   * See {@link #extractIndexMapFrom} and {@link #extractOrdinalsMapFor} for
-   * details of the companion class and ordinals computation.
    */
   public void removeSwitchMaps(IRCode code) {
     for (BasicBlock block : code.blocks) {
@@ -382,68 +374,38 @@
         // Pattern match a switch on a switch map as input.
         if (insn.isSwitch()) {
           Switch switchInsn = insn.asSwitch();
-          Instruction input = switchInsn.inValues().get(0).definition;
-          if (input == null || !input.isArrayGet()) {
-            continue;
-          }
-          ArrayGet arrayGet = input.asArrayGet();
-          Instruction index = arrayGet.index().definition;
-          if (index == null || !index.isInvokeVirtual()) {
-            continue;
-          }
-          InvokeVirtual ordinalInvoke = index.asInvokeVirtual();
-          DexMethod ordinalMethod = ordinalInvoke.getInvokedMethod();
-          DexClass enumClass = appInfo.definitionFor(ordinalMethod.holder);
-          if (enumClass == null
-              || (!enumClass.accessFlags.isEnum() && enumClass.type != dexItemFactory.enumType)
-              || ordinalMethod.name != dexItemFactory.ordinalMethodName
-              || ordinalMethod.proto.returnType != dexItemFactory.intType
-              || !ordinalMethod.proto.parameters.isEmpty()) {
-            continue;
-          }
-          Instruction array = arrayGet.array().definition;
-          if (array == null || !array.isStaticGet()) {
-            continue;
-          }
-          StaticGet staticGet = array.asStaticGet();
-          if (staticGet.getField().name.toSourceString().startsWith("$SwitchMap$")) {
-            Int2ReferenceMap<DexField> indexMap = extractIndexMapFrom(staticGet.getField());
-            if (indexMap == null || indexMap.isEmpty()) {
-              continue;
+          EnumSwitchInfo info = SwitchUtils
+              .analyzeSwitchOverEnum(switchInsn, appInfo.withLiveness());
+          if (info != null) {
+            Int2IntMap targetMap = new Int2IntArrayMap();
+            IntList keys = new IntArrayList(switchInsn.numberOfKeys());
+            for (int i = 0; i < switchInsn.numberOfKeys(); i++) {
+              assert switchInsn.targetBlockIndices()[i] != switchInsn.getFallthroughBlockIndex();
+              int key = info.ordinalsMap.getInt(info.indexMap.get(switchInsn.getKey(i)));
+              keys.add(key);
+              targetMap.put(key, switchInsn.targetBlockIndices()[i]);
             }
-            // Due to member rebinding, only the fields are certain to provide the actual enums
-            // class.
-            DexType switchMapHolder = indexMap.values().iterator().next().getHolder();
-            Reference2IntMap<DexField> ordinalsMap = extractOrdinalsMapFor(switchMapHolder);
-            if (ordinalsMap != null) {
-              Int2IntMap targetMap = new Int2IntArrayMap();
-              IntList keys = new IntArrayList(switchInsn.numberOfKeys());
-              for (int i = 0; i < switchInsn.numberOfKeys(); i++) {
-                assert switchInsn.targetBlockIndices()[i] != switchInsn.getFallthroughBlockIndex();
-                int key = ordinalsMap.getInt(indexMap.get(switchInsn.getKey(i)));
-                keys.add(key);
-                targetMap.put(key, switchInsn.targetBlockIndices()[i]);
-              }
-              keys.sort(Comparator.naturalOrder());
-              int[] targets = new int[keys.size()];
-              for (int i = 0; i < keys.size(); i++) {
-                targets[i] = targetMap.get(keys.getInt(i));
-              }
+            keys.sort(Comparator.naturalOrder());
+            int[] targets = new int[keys.size()];
+            for (int i = 0; i < keys.size(); i++) {
+              targets[i] = targetMap.get(keys.getInt(i));
+            }
 
-              Switch newSwitch = new Switch(ordinalInvoke.outValue(), keys.toIntArray(),
-                  targets, switchInsn.getFallthroughBlockIndex());
-              // Replace the switch itself.
-              it.replaceCurrentInstruction(newSwitch);
-              // If the original input to the switch is now unused, remove it too. It is not dead
-              // as it might have side-effects but we ignore these here.
-              if (arrayGet.outValue().numberOfUsers() == 0) {
-                arrayGet.inValues().forEach(v -> v.removeUser(arrayGet));
-                arrayGet.getBlock().removeInstruction(arrayGet);
-              }
-              if (staticGet.outValue().numberOfUsers() == 0) {
-                assert staticGet.inValues().isEmpty();
-                staticGet.getBlock().removeInstruction(staticGet);
-              }
+            Switch newSwitch = new Switch(info.ordinalInvoke.outValue(), keys.toIntArray(),
+                targets, switchInsn.getFallthroughBlockIndex());
+            // Replace the switch itself.
+            it.replaceCurrentInstruction(newSwitch);
+            // If the original input to the switch is now unused, remove it too. It is not dead
+            // as it might have side-effects but we ignore these here.
+            Instruction arrayGet = info.arrayGet;
+            if (arrayGet.outValue().numberOfUsers() == 0) {
+              arrayGet.inValues().forEach(v -> v.removeUser(arrayGet));
+              arrayGet.getBlock().removeInstruction(arrayGet);
+            }
+            Instruction staticGet = info.staticGet;
+            if (staticGet.outValue().numberOfUsers() == 0) {
+              assert staticGet.inValues().isEmpty();
+              staticGet.getBlock().removeInstruction(staticGet);
             }
           }
         }
@@ -451,156 +413,6 @@
     }
   }
 
-
-  /**
-   * Extracts the mapping from ordinal values to switch case constants.
-   * <p>
-   * This is done by pattern-matching on the class initializer of the synthetic switch map class.
-   * For a switch
-   *
-   * <blockquote><pre>
-   * switch (day) {
-   *   case WEDNESDAY:
-   *   case FRIDAY:
-   *     System.out.println("3 or 5");
-   *     break;
-   *   case SUNDAY:
-   *     System.out.println("7");
-   *     break;
-   *   default:
-   *     System.out.println("other");
-   * }
-   * </pre></blockquote>
-   *
-   * the generated companing class initializer will have the form
-   *
-   * <blockquote><pre>
-   * class Switches$1 {
-   *   static {
-   *   $SwitchMap$switchmaps$Days[Days.WEDNESDAY.ordinal()] = 1;
-   *   $SwitchMap$switchmaps$Days[Days.FRIDAY.ordinal()] = 2;
-   *   $SwitchMap$switchmaps$Days[Days.SUNDAY.ordinal()] = 3;
-   * }
-   * </pre></blockquote>
-   *
-   * Note that one map per class is generated, so the map might contain additional entries as used
-   * by other switches in the class.
-   */
-  private Int2ReferenceMap<DexField> extractIndexMapFrom(DexField field) {
-    DexClass clazz = appInfo.definitionFor(field.getHolder());
-    if (!clazz.accessFlags.isSynthetic()) {
-      return null;
-    }
-    DexEncodedMethod initializer = clazz.getClassInitializer();
-    if (initializer == null || initializer.getCode() == null) {
-      return null;
-    }
-    IRCode code = initializer.getCode().buildIR(initializer, new InternalOptions());
-    Int2ReferenceMap<DexField> switchMap = new Int2ReferenceArrayMap<>();
-    for (BasicBlock block : code.blocks) {
-      InstructionListIterator it = block.listIterator();
-      Instruction insn = it.nextUntil(i -> i.isStaticGet() && i.asStaticGet().getField() == field);
-      if (insn == null) {
-        continue;
-      }
-      for (Instruction use : insn.outValue().uniqueUsers()) {
-        if (use.isArrayPut()) {
-          Instruction index = use.asArrayPut().source().definition;
-          if (index == null || !index.isConstNumber()) {
-            return null;
-          }
-          int integerIndex = index.asConstNumber().getIntValue();
-          Instruction value = use.asArrayPut().index().definition;
-          if (value == null || !value.isInvokeVirtual()) {
-            return null;
-          }
-          InvokeVirtual invoke = value.asInvokeVirtual();
-          DexClass holder = appInfo.definitionFor(invoke.getInvokedMethod().holder);
-          if (holder == null ||
-              (!holder.accessFlags.isEnum() && holder.type != dexItemFactory.enumType)) {
-            return null;
-          }
-          Instruction enumGet = invoke.arguments().get(0).definition;
-          if (enumGet == null || !enumGet.isStaticGet()) {
-            return null;
-          }
-          DexField enumField = enumGet.asStaticGet().getField();
-          if (!appInfo.definitionFor(enumField.getHolder()).accessFlags.isEnum()) {
-            return null;
-          }
-          if (switchMap.put(integerIndex, enumField) != null) {
-            return null;
-          }
-        } else {
-          return null;
-        }
-      }
-    }
-    return switchMap;
-  }
-
-  /**
-   * Extracts the ordinal values for an Enum class from the classes static initializer.
-   * <p>
-   * An Enum class has a field for each value. In the class initializer, each field is initialized
-   * to a singleton object that represents the value. This code matches on the corresponding call
-   * to the constructor (instance initializer) and extracts the value of the second argument, which
-   * is the ordinal.
-   */
-  private Reference2IntMap<DexField> extractOrdinalsMapFor(DexType enumClass) {
-    DexClass clazz = appInfo.definitionFor(enumClass);
-    if (clazz == null || clazz.isLibraryClass()) {
-      // We have to keep binary compatibility in tact for libraries.
-      return null;
-    }
-    DexEncodedMethod initializer = clazz.getClassInitializer();
-    if (!clazz.accessFlags.isEnum() || initializer == null || initializer.getCode() == null) {
-      return null;
-    }
-    if (initializer.getCode().isDexCode()) {
-      // If the initializer have been optimized we cannot extract the ordinals map reliably.
-      return null;
-    }
-    IRCode code = initializer.getCode().buildIR(initializer, new InternalOptions());
-    Reference2IntMap<DexField> ordinalsMap = new Reference2IntArrayMap<>();
-    ordinalsMap.defaultReturnValue(-1);
-    InstructionIterator it = code.instructionIterator();
-    while (it.hasNext()) {
-      Instruction insn = it.next();
-      if (!insn.isStaticPut()) {
-        continue;
-      }
-      StaticPut staticPut = insn.asStaticPut();
-      if (staticPut.getField().type != enumClass) {
-        continue;
-      }
-      Instruction newInstance = staticPut.inValue().definition;
-      if (newInstance == null || !newInstance.isNewInstance()) {
-        continue;
-      }
-      Instruction ordinal = null;
-      for (Instruction ctorCall : newInstance.outValue().uniqueUsers()) {
-        if (!ctorCall.isInvokeDirect()) {
-          continue;
-        }
-        InvokeDirect invoke = ctorCall.asInvokeDirect();
-        if (!dexItemFactory.isConstructor(invoke.getInvokedMethod())
-            || invoke.arguments().size() < 3) {
-          continue;
-        }
-        ordinal = invoke.arguments().get(2).definition;
-        break;
-      }
-      if (ordinal == null || !ordinal.isConstNumber()) {
-        return null;
-      }
-      if (ordinalsMap.put(staticPut.getField(), ordinal.asConstNumber().getIntValue()) != -1) {
-        return null;
-      }
-    }
-    return ordinalsMap;
-  }
-
   /**
    * Rewrite all branch targets to the destination of trivial goto chains when possible.
    * Does not rewrite fallthrough targets as that would require block reordering and the
@@ -1287,7 +1099,7 @@
           }
         }
         assert theIf == block.exit();
-        replaceLastInstruction(block, new Goto());
+        block.replaceLastInstruction(new Goto());
         assert block.exit().isGoto();
         assert block.exit().asGoto().getTarget() == target;
       }
@@ -1310,7 +1122,7 @@
         int left = leftValue.getConstInstruction().asConstNumber().getIntValue();
         if (left == 0) {
           If ifz = new If(theIf.getType().forSwappedOperands(), rightValue);
-          replaceLastInstruction(block, ifz);
+          block.replaceLastInstruction(ifz);
           assert block.exit() == ifz;
         }
       } else {
@@ -1318,19 +1130,13 @@
         int right = rightValue.getConstInstruction().asConstNumber().getIntValue();
         if (right == 0) {
           If ifz = new If(theIf.getType(), leftValue);
-          replaceLastInstruction(block, ifz);
+          block.replaceLastInstruction(ifz);
           assert block.exit() == ifz;
         }
       }
     }
   }
 
-  private void replaceLastInstruction(BasicBlock block, Instruction instruction) {
-    InstructionListIterator iterator = block.listIterator(block.getInstructions().size());
-    iterator.previous();
-    iterator.replaceCurrentInstruction(instruction);
-  }
-
   public void rewriteLongCompareAndRequireNonNull(IRCode code, InternalOptions options) {
     if (options.canUseLongCompareAndObjectsNonNull()) {
       return;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/EnumOrdinalMapCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/EnumOrdinalMapCollector.java
new file mode 100644
index 0000000..b2ebecc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/EnumOrdinalMapCollector.java
@@ -0,0 +1,102 @@
+// 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.ir.optimize;
+
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexProgramClass;
+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.InvokeDirect;
+import com.android.tools.r8.ir.code.StaticPut;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions;
+import it.unimi.dsi.fastutil.objects.Reference2IntArrayMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.Map;
+
+/**
+ * Extracts the ordinal values for all Enum classes from their static initializer.
+ * <p>
+ * An Enum class has a field for each value. In the class initializer, each field is initialized
+ * to a singleton object that represents the value. This code matches on the corresponding call
+ * to the constructor (instance initializer) and extracts the value of the second argument, which
+ * is the ordinal.
+ */
+public class EnumOrdinalMapCollector {
+
+  private final AppInfoWithLiveness appInfo;
+  private final InternalOptions options;
+
+  private final Map<DexType, Reference2IntMap<DexField>> ordinalsMaps = new IdentityHashMap<>();
+
+  public EnumOrdinalMapCollector(AppInfoWithLiveness appInfo, InternalOptions options) {
+    this.appInfo = appInfo;
+    this.options = options;
+  }
+
+  public static Reference2IntMap<DexField> getOrdinalsMapFor(DexType enumClass,
+      AppInfoWithLiveness appInfo) {
+    Map<DexType, Reference2IntMap<DexField>> ordinalsMaps = appInfo
+        .getExtension(EnumOrdinalMapCollector.class, Collections.emptyMap());
+    return ordinalsMaps.get(enumClass);
+  }
+
+  public void run() {
+    appInfo.classes().forEach(this::processClasses);
+    if (!ordinalsMaps.isEmpty()) {
+      appInfo.setExtension(EnumOrdinalMapCollector.class, ordinalsMaps);
+    }
+  }
+
+  private void processClasses(DexProgramClass clazz) {
+    // Enum classes are flagged as such. Also, for library classes, the ordinals are not known.
+    if (!clazz.accessFlags.isEnum() || clazz.isLibraryClass() || !clazz.hasClassInitializer()) {
+      return;
+    }
+    DexEncodedMethod initializer = clazz.getClassInitializer();
+    IRCode code = initializer.getCode().buildIR(initializer, options);
+    Reference2IntMap<DexField> ordinalsMap = new Reference2IntArrayMap<>();
+    ordinalsMap.defaultReturnValue(-1);
+    InstructionIterator it = code.instructionIterator();
+    while (it.hasNext()) {
+      Instruction insn = it.next();
+      if (!insn.isStaticPut()) {
+        continue;
+      }
+      StaticPut staticPut = insn.asStaticPut();
+      if (staticPut.getField().type != clazz.type) {
+        continue;
+      }
+      Instruction newInstance = staticPut.inValue().definition;
+      if (newInstance == null || !newInstance.isNewInstance()) {
+        continue;
+      }
+      Instruction ordinal = null;
+      for (Instruction ctorCall : newInstance.outValue().uniqueUsers()) {
+        if (!ctorCall.isInvokeDirect()) {
+          continue;
+        }
+        InvokeDirect invoke = ctorCall.asInvokeDirect();
+        if (!appInfo.dexItemFactory.isConstructor(invoke.getInvokedMethod())
+            || invoke.arguments().size() < 3) {
+          continue;
+        }
+        ordinal = invoke.arguments().get(2).definition;
+        break;
+      }
+      if (ordinal == null || !ordinal.isConstNumber()) {
+        return;
+      }
+      if (ordinalsMap.put(staticPut.getField(), ordinal.asConstNumber().getIntValue()) != -1) {
+        return;
+      }
+    }
+    ordinalsMaps.put(clazz.type, ordinalsMap);
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java
new file mode 100644
index 0000000..44f0759
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/SwitchMapCollector.java
@@ -0,0 +1,155 @@
+// 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.ir.optimize;
+
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexString;
+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.InvokeVirtual;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceArrayMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+/**
+ * Extracts the mapping from ordinal values to switch case constants.
+ * <p>
+ * This is done by pattern-matching on the class initializer of the synthetic switch map class.
+ * For a switch
+ *
+ * <blockquote><pre>
+ * switch (day) {
+ *   case WEDNESDAY:
+ *   case FRIDAY:
+ *     System.out.println("3 or 5");
+ *     break;
+ *   case SUNDAY:
+ *     System.out.println("7");
+ *     break;
+ *   default:
+ *     System.out.println("other");
+ * }
+ * </pre></blockquote>
+ *
+ * the generated companing class initializer will have the form
+ *
+ * <blockquote><pre>
+ * class Switches$1 {
+ *   static {
+ *   $SwitchMap$switchmaps$Days[Days.WEDNESDAY.ordinal()] = 1;
+ *   $SwitchMap$switchmaps$Days[Days.FRIDAY.ordinal()] = 2;
+ *   $SwitchMap$switchmaps$Days[Days.SUNDAY.ordinal()] = 3;
+ * }
+ * </pre></blockquote>
+ *
+ * Note that one map per class is generated, so the map might contain additional entries as used
+ * by other switches in the class.
+ */
+public class SwitchMapCollector {
+
+  private final AppInfoWithLiveness appInfo;
+  private final InternalOptions options;
+  private final DexString switchMapPrefix;
+  private final DexType intArrayType;
+
+  private final Map<DexField, Int2ReferenceMap<DexField>> switchMaps = new IdentityHashMap<>();
+
+  public SwitchMapCollector(AppInfoWithLiveness appInfo, InternalOptions options) {
+    this.appInfo = appInfo;
+    this.options = options;
+    switchMapPrefix = appInfo.dexItemFactory.createString("$SwitchMap$");
+    intArrayType = appInfo.dexItemFactory.createType("[I");
+  }
+
+  public void run() {
+    appInfo.classes().forEach(this::processClasses);
+    if (!switchMaps.isEmpty()) {
+      appInfo.setExtension(SwitchMapCollector.class, switchMaps);
+    }
+  }
+
+  public static Int2ReferenceMap<DexField> getSwitchMapFor(DexField field,
+      AppInfoWithLiveness appInfo) {
+    Map<DexField, Int2ReferenceMap<DexField>> switchMaps = appInfo
+        .getExtension(SwitchMapCollector.class, Collections.emptyMap());
+    return switchMaps.get(field);
+  }
+
+  private void processClasses(DexProgramClass clazz) {
+    // Switchmap classes are synthetic and have a class initializer.
+    if (!clazz.accessFlags.isSynthetic() && !clazz.hasClassInitializer()) {
+      return;
+    }
+    List<DexEncodedField> switchMapFields = Arrays.stream(clazz.staticFields())
+        .filter(this::maybeIsSwitchMap).collect(Collectors.toList());
+    if (!switchMapFields.isEmpty()) {
+      IRCode initializer = clazz.getClassInitializer().buildIR(options);
+      switchMapFields.forEach(field -> extractSwitchMap(field, initializer));
+    }
+  }
+
+  private void extractSwitchMap(DexEncodedField encodedField, IRCode initializer) {
+    DexField field = encodedField.field;
+    Int2ReferenceMap<DexField> switchMap = new Int2ReferenceArrayMap<>();
+    InstructionIterator it = initializer.instructionIterator();
+    Instruction insn;
+    Predicate<Instruction> predicate = i -> i.isStaticGet() && i.asStaticGet().getField() == field;
+    while ((insn = it.nextUntil(predicate)) != null) {
+      for (Instruction use : insn.outValue().uniqueUsers()) {
+        if (use.isArrayPut()) {
+          Instruction index = use.asArrayPut().source().definition;
+          if (index == null || !index.isConstNumber()) {
+            return;
+          }
+          int integerIndex = index.asConstNumber().getIntValue();
+          Instruction value = use.asArrayPut().index().definition;
+          if (value == null || !value.isInvokeVirtual()) {
+            return;
+          }
+          InvokeVirtual invoke = value.asInvokeVirtual();
+          DexClass holder = appInfo.definitionFor(invoke.getInvokedMethod().holder);
+          if (holder == null ||
+              (!holder.accessFlags.isEnum() && holder.type != appInfo.dexItemFactory.enumType)) {
+            return;
+          }
+          Instruction enumGet = invoke.arguments().get(0).definition;
+          if (enumGet == null || !enumGet.isStaticGet()) {
+            return;
+          }
+          DexField enumField = enumGet.asStaticGet().getField();
+          if (!appInfo.definitionFor(enumField.getHolder()).accessFlags.isEnum()) {
+            return;
+          }
+          if (switchMap.put(integerIndex, enumField) != null) {
+            return;
+          }
+        } else {
+          return;
+        }
+      }
+    }
+    switchMaps.put(field, switchMap);
+  }
+
+  private boolean maybeIsSwitchMap(DexEncodedField dexEncodedField) {
+    // We are looking for synthetic fields of type int[].
+    DexField field = dexEncodedField.field;
+    return dexEncodedField.accessFlags.isSynthetic()
+        && field.name.beginsWith(switchMapPrefix)
+        && field.type == intArrayType;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/SwitchUtils.java b/src/main/java/com/android/tools/r8/ir/optimize/SwitchUtils.java
new file mode 100644
index 0000000..0c33561
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/SwitchUtils.java
@@ -0,0 +1,102 @@
+// 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.ir.optimize;
+
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.ArrayGet;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.StaticGet;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+
+public class SwitchUtils {
+
+  public static final class EnumSwitchInfo {
+    public final DexType enumClass;
+    public final Instruction ordinalInvoke;
+    public final Instruction arrayGet;
+    public final Instruction staticGet;
+    public final Int2ReferenceMap<DexField> indexMap;
+    public final Reference2IntMap ordinalsMap;
+
+    private EnumSwitchInfo(DexType enumClass,
+        Instruction ordinalInvoke,
+        Instruction arrayGet, Instruction staticGet,
+        Int2ReferenceMap<DexField> indexMap,
+        Reference2IntMap ordinalsMap) {
+      this.enumClass = enumClass;
+      this.ordinalInvoke = ordinalInvoke;
+      this.arrayGet = arrayGet;
+      this.staticGet = staticGet;
+      this.indexMap = indexMap;
+      this.ordinalsMap = ordinalsMap;
+    }
+  }
+
+  /**
+   * Looks for a switch statement over the enum companion class of the form
+   *
+   * <blockquote><pre>
+   * switch(CompanionClass.$switchmap$field[enumValue.ordinal()]) {
+   *   ...
+   * }
+   * </pre></blockquote>
+   *
+   * and extracts the components and the index and ordinal maps. See
+   * {@link EnumOrdinalMapCollector} and
+   * {@link SwitchMapCollector} for details.
+   */
+  public static EnumSwitchInfo analyzeSwitchOverEnum(Instruction switchInsn,
+      AppInfoWithLiveness appInfo) {
+    Instruction input = switchInsn.inValues().get(0).definition;
+    if (input == null || !input.isArrayGet()) {
+      return null;
+    }
+    ArrayGet arrayGet = input.asArrayGet();
+    Instruction index = arrayGet.index().definition;
+    if (index == null || !index.isInvokeVirtual()) {
+      return null;
+    }
+    InvokeVirtual ordinalInvoke = index.asInvokeVirtual();
+    DexMethod ordinalMethod = ordinalInvoke.getInvokedMethod();
+    DexClass enumClass = appInfo.definitionFor(ordinalMethod.holder);
+    DexItemFactory dexItemFactory = appInfo.dexItemFactory;
+    // After member rebinding, enumClass will be the actual java.lang.Enum class.
+    if (enumClass == null
+        || (!enumClass.accessFlags.isEnum() && enumClass.type != dexItemFactory.enumType)
+        || ordinalMethod.name != dexItemFactory.ordinalMethodName
+        || ordinalMethod.proto.returnType != dexItemFactory.intType
+        || !ordinalMethod.proto.parameters.isEmpty()) {
+      return null;
+    }
+    Instruction array = arrayGet.array().definition;
+    if (array == null || !array.isStaticGet()) {
+      return null;
+    }
+    StaticGet staticGet = array.asStaticGet();
+    Int2ReferenceMap<DexField> indexMap
+        = SwitchMapCollector.getSwitchMapFor(staticGet.getField(), appInfo);
+    if (indexMap == null || indexMap.isEmpty()) {
+      return null;
+    }
+    // Due to member rebinding, only the fields are certain to provide the actual enums
+    // class.
+    DexType enumTyoe = indexMap.values().iterator().next().getHolder();
+    Reference2IntMap ordinalsMap
+        = EnumOrdinalMapCollector.getOrdinalsMapFor(enumTyoe, appInfo);
+    if (ordinalsMap == null) {
+      return null;
+    }
+    return new EnumSwitchInfo(enumTyoe, ordinalInvoke, arrayGet, staticGet, indexMap,
+        ordinalsMap);
+  }
+
+
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index b8fa85a..d25c4bc 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -37,12 +37,14 @@
 import com.google.common.collect.Sets;
 import com.google.common.collect.Sets.SetView;
 import java.util.ArrayDeque;
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.IdentityHashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Queue;
@@ -75,6 +77,9 @@
   private Map<DexType, Set<DexField>> staticFieldsRead = Maps.newIdentityHashMap();
   private Map<DexType, Set<DexField>> staticFieldsWritten = Maps.newIdentityHashMap();
 
+  private final List<SemanticsProvider> extensions = new ArrayList<>();
+  private final Map<Class, Object> extensionsState = new HashMap<>();
+
   /**
    * This map keeps a view of all virtual methods that are reachable from virtual invokes. A method
    * is reachable even if no live subtypes exist, so this is not sufficient for inclusion in the
@@ -152,6 +157,10 @@
     this.appInfo = appInfo;
   }
 
+  public void addExtension(SemanticsProvider extension) {
+    extensions.add(extension);
+  }
+
   private void enqueueRootItems(Map<DexItem, ProguardKeepRule> items) {
     workList.addAll(
         items.entrySet().stream().map(Action::forRootItem).collect(Collectors.toList()));
@@ -852,7 +861,21 @@
       for (DexAnnotationSet parameterAnnotation : method.parameterAnnotations.values) {
         processAnnotations(parameterAnnotation.annotations);
       }
-      method.registerReachableDefinitions(new UseRegistry(method));
+      boolean processed = false;
+      if (!extensions.isEmpty()) {
+        for (SemanticsProvider extension : extensions) {
+          if (extension.appliesTo(method)) {
+            assert extensions.stream().filter(e -> e.appliesTo(method)).count() == 1;
+            extensionsState.put(extension.getClass(),
+                extension.processMethod(method, new UseRegistry(method),
+                    extensionsState.get(extension.getClass())));
+            processed = true;
+          }
+        }
+      }
+      if (!processed) {
+        method.registerReachableDefinitions(new UseRegistry(method));
+      }
       // Add all dependent members to the workqueue.
       enqueueRootItems(rootSet.getDependentItems(method));
     }
@@ -1007,7 +1030,7 @@
      * Set of fields that belong to live classes and can be reached by invokes. These need to be
      * kept.
      */
-    final Set<DexField> liveFields;
+    public final Set<DexField> liveFields;
     /**
      * Set of all fields which may be touched by a get operation. This is actual field definitions.
      */
@@ -1060,6 +1083,10 @@
      * All items with assumevalues rule.
      */
     public final Map<DexItem, ProguardMemberRule> assumedValues;
+    /**
+     * Map from the class of an extension to the state it produced.
+     */
+    public final Map<Class, Object> extensions;
 
     private AppInfoWithLiveness(AppInfoWithSubtyping appInfo, Enqueuer enqueuer) {
       super(appInfo);
@@ -1081,6 +1108,7 @@
       this.staticInvokes = joinInvokedMethods(enqueuer.staticInvokes);
       this.noSideEffects = enqueuer.rootSet.noSideEffects;
       this.assumedValues = enqueuer.rootSet.assumedValues;
+      this.extensions = enqueuer.extensionsState;
       assert Sets.intersection(instanceFieldReads, staticFieldReads).size() == 0;
       assert Sets.intersection(instanceFieldWrites, staticFieldWrites).size() == 0;
     }
@@ -1106,6 +1134,7 @@
       this.superInvokes = previous.superInvokes;
       this.directInvokes = previous.directInvokes;
       this.staticInvokes = previous.staticInvokes;
+      this.extensions = previous.extensions;
       assert Sets.intersection(instanceFieldReads, staticFieldReads).size() == 0;
       assert Sets.intersection(instanceFieldWrites, staticFieldWrites).size() == 0;
     }
@@ -1131,6 +1160,7 @@
       this.superInvokes = rewriteItems(previous.superInvokes, lense::lookupMethod);
       this.directInvokes = rewriteItems(previous.directInvokes, lense::lookupMethod);
       this.staticInvokes = rewriteItems(previous.staticInvokes, lense::lookupMethod);
+      this.extensions = previous.extensions;
       assert Sets.intersection(instanceFieldReads, staticFieldReads).size() == 0;
       assert Sets.intersection(instanceFieldWrites, staticFieldWrites).size() == 0;
     }
@@ -1159,6 +1189,20 @@
       return builder.build();
     }
 
+    @SuppressWarnings("unchecked")
+    public <T> T getExtension(Class extension, T defaultValue) {
+      if (extensions.containsKey(extension)) {
+        return (T) extensions.get(extension);
+      } else {
+        return defaultValue;
+      }
+    }
+
+    public <T> void setExtension(Class extension, T value) {
+      assert !extensions.containsKey(extension);
+      extensions.put(extension, value);
+    }
+
     @Override
     public boolean hasLiveness() {
       return true;
@@ -1299,4 +1343,12 @@
       return false;
     }
   }
+
+  public interface SemanticsProvider {
+
+    boolean appliesTo(DexEncodedMethod method);
+
+    Object processMethod(DexEncodedMethod method,
+        com.android.tools.r8.graph.UseRegistry useRegistry, Object state);
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLiteBase.java b/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLiteBase.java
new file mode 100644
index 0000000..c2264f2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLiteBase.java
@@ -0,0 +1,98 @@
+// 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.shaking.protolite;
+
+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.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+
+/**
+ * Contains common definitions used by the {@link ProtoLiteExtension} for tree shaking and the
+ * corresponding {@link ProtoLitePruner} code rewriting.
+ */
+abstract class ProtoLiteBase {
+
+  static final int GETTER_NAME_PREFIX_LENGTH = 3;
+  static final int COUNT_POSTFIX_LENGTH = 5;
+
+  final AppInfoWithSubtyping appInfo;
+
+  final DexType messageType;
+  final DexString dynamicMethodName;
+  final DexString writeToMethodName;
+  final DexString getSerializedSizeMethodName;
+  final DexString constructorMethodName;
+  final DexString setterNamePrefix;
+  final DexString getterNamePrefix;
+  final DexString bitFieldPrefix;
+  final DexString underscore;
+
+  ProtoLiteBase(AppInfoWithSubtyping appInfo) {
+    this.appInfo = appInfo;
+    DexItemFactory factory = appInfo.dexItemFactory;
+    this.messageType = factory.createType("Lcom/google/protobuf/GeneratedMessageLite;");
+    this.dynamicMethodName = factory.createString("dynamicMethod");
+    this.writeToMethodName = factory.createString("writeTo");
+    this.getSerializedSizeMethodName = factory.createString("getSerializedSize");
+    this.constructorMethodName = factory.constructorMethodName;
+    this.setterNamePrefix = factory.createString("set");
+    this.getterNamePrefix = factory.createString("get");
+    this.bitFieldPrefix = factory.createString("bitField");
+    this.underscore = factory.createString("_");
+    assert getterNamePrefix.size == GETTER_NAME_PREFIX_LENGTH;
+  }
+
+  /**
+   * Returns true of the given method is a setter on a message class that does need processing
+   * by this phase of proto lite shaking.
+   * <p>
+   * False positives are ok.
+   */
+  abstract boolean isSetterThatNeedsProcessing(DexEncodedMethod method);
+
+  DexField getterToField(DexMethod getter) {
+    return getterToField(getter, 0);
+  }
+
+  DexField getterToField(DexMethod getter, int postfixLength) {
+    String getterName = getter.name.toString();
+    assert getterName.length() > GETTER_NAME_PREFIX_LENGTH + postfixLength;
+    String fieldName = Character.toLowerCase(getterName.charAt(GETTER_NAME_PREFIX_LENGTH))
+        + getterName.substring(GETTER_NAME_PREFIX_LENGTH + 1, getterName.length() - postfixLength)
+        + "_";
+    DexItemFactory factory = appInfo.dexItemFactory;
+    return factory
+        .createField(getter.holder, getter.proto.returnType, factory.createString(fieldName));
+  }
+
+  boolean hasSingleIntArgument(DexMethod method) {
+    return method.getArity() == 1
+        && method.proto.parameters.values[0] == appInfo.dexItemFactory.intType;
+  }
+
+  public boolean appliesTo(DexEncodedMethod method) {
+    if (!method.method.holder.isSubtypeOf(messageType, appInfo)) {
+      return false;
+    }
+    DexClass clazz = appInfo.definitionFor(method.method.holder);
+    // We only care for the actual leaf classes that implement a specific proto.
+    if (!clazz.accessFlags.isFinal()) {
+      return false;
+    }
+    DexString methodName = method.method.name;
+    // We could be even more precise here and check for the signature. However, there is only
+    // one of each method generated.
+    return methodName == dynamicMethodName
+        || methodName == writeToMethodName
+        || methodName == getSerializedSizeMethodName
+        || methodName == constructorMethodName
+        || isSetterThatNeedsProcessing(method);
+  }
+
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLiteExtension.java b/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLiteExtension.java
new file mode 100644
index 0000000..b217194
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLiteExtension.java
@@ -0,0 +1,208 @@
+// 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.shaking.protolite;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DelegatingUseRegistry;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.UseRegistry;
+import com.android.tools.r8.shaking.Enqueuer.SemanticsProvider;
+import com.android.tools.r8.utils.MethodJavaSignatureEquivalence;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Equivalence.Wrapper;
+import com.google.common.collect.Sets;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * Extends the tree shaker with special treatment for ProtoLite generated classes.
+ * <p>
+ * The goal is to remove unused fields from proto classes. To achieve this, we filter the
+ * dependency processing of certain methods of ProtoLite classes. Read/write references to
+ * fields or corresponding getters are ignored. If the fields or getters are not used otherwise
+ * in the program, they will be pruned even though they are referenced from the processed
+ * ProtoLite class.
+ * <p>
+ * The companion code rewriter in {@link ProtoLitePruner} then fixes up the code and removes
+ * references to these dead fields and getters in a semantics preserving way. For proto2, the
+ * fields are turned into unknown fields and hence are preserved over the wire. For proto3, the
+ * fields are removed and, as with unknown fields in proto3, their data is lost on retransmission.
+ * <p>
+ * We have to process the following three methods specially:
+ * <dl>
+ *   <dt>dynamicMethod</dt>
+ *   <dd>implements most proto operations, like merging, comparing, etc</dd>
+ *   <dt>writeTo</dt>
+ *   <dd>performs the actual write operations</dd>
+ *   <dt>getSerializedSize</dt>
+ *   <dd>implements computing the serialized size of a proto, very similar to writeTo</dd>
+ * </dl>
+ * As they access all fields of a proto, regardless of whether they are used, we have to mask
+ * their accesses to ensure actually dead fields are not made live.
+ * <p>
+ * We also have to treat setters specially. While their code does not need to be rewritten, we
+ * need to ensure that the fields they write are actually kept and marked as live. We achieve
+ * this by also marking them read.
+ */
+public class ProtoLiteExtension extends ProtoLiteBase implements SemanticsProvider {
+
+  private final Equivalence<DexMethod> equivalence = MethodJavaSignatureEquivalence.get();
+  /**
+   * Set of all methods directly defined on the GeneratedMessageLite class. Used to filter
+   * getters from other methods that begin with get.
+   */
+  private final Set<Wrapper<DexMethod>> methodsOnMessageType;
+
+  private final DexString caseGetterSuffix;
+  private final DexString caseFieldSuffix;
+
+  public ProtoLiteExtension(AppInfoWithSubtyping appInfo) {
+    super(appInfo);
+    DexItemFactory factory = appInfo.dexItemFactory;
+    this.methodsOnMessageType = computeMethodsOnMessageType();
+    this.caseGetterSuffix = factory.createString("Case");
+    this.caseFieldSuffix = factory.createString("Case_");
+  }
+
+  private Set<Wrapper<DexMethod>> computeMethodsOnMessageType() {
+    DexClass messageClass = appInfo.definitionFor(messageType);
+    if (messageClass == null) {
+      return Collections.emptySet();
+    }
+    Set<Wrapper<DexMethod>> superMethods = new HashSet<>();
+    messageClass.forEachMethod(method -> superMethods.add(equivalence.wrap(method.method)));
+    return superMethods;
+  }
+
+  boolean isSetterThatNeedsProcessing(DexEncodedMethod method) {
+    return method.accessFlags.isPrivate()
+        && method.method.name.beginsWith(setterNamePrefix)
+        && !methodsOnMessageType.contains(equivalence.wrap(method.method));
+  }
+
+  private boolean isGetter(DexMethod method, DexType instanceType) {
+    return method.holder == instanceType
+        && (method.proto.parameters.isEmpty() || hasSingleIntArgument(method))
+        && method.name.beginsWith(getterNamePrefix)
+        && !method.name.endsWith(caseGetterSuffix)
+        && !methodsOnMessageType.contains(equivalence.wrap(method));
+  }
+
+  private boolean isProtoField(DexField field, DexType instanceType) {
+    if (field.getHolder() != instanceType) {
+      return false;
+    }
+    // All instance fields that end with _ are proto fields. For proto2, there are also the
+    // bitField<n>_ fields that are used to store presence information. We process those normally.
+    // Likewise, the XXXCase_ fields for oneOfs.
+    DexString name = field.name;
+    return name.endsWith(underscore)
+        && !name.beginsWith(bitFieldPrefix)
+        && !name.endsWith(caseFieldSuffix);
+  }
+
+  @Override
+  @SuppressWarnings("unchecked")
+  public Object processMethod(DexEncodedMethod method, UseRegistry registry, Object state) {
+    return processMethod(method, registry, (Set<DexField>) state);
+  }
+
+  private Set<DexField> processMethod(DexEncodedMethod method, UseRegistry registry,
+      Set<DexField> state) {
+    if (state == null) {
+      state = Sets.newIdentityHashSet();
+    }
+    if (isSetterThatNeedsProcessing(method)) {
+      // If a field is accessed by a live setter, the field is live as it has to be written to the
+      // serialized stream for this proto. As we mask all reads in the writing code and normally
+      // remove fields that are only written but never read, we have to mark fields used in setters
+      // as read and written.
+      method.registerReachableDefinitions(
+          new FieldWriteImpliesReadUseRegistry(registry, method.method.holder));
+    } else {
+      // Filter all getters and field accesses in these methods. We do not want fields to become
+      // live just due to being referenced in a special method. The pruning phase will remove
+      // all references to dead fields in the code later.
+      method.registerReachableDefinitions(new FilteringUseRegistry(registry, method.method.holder,
+          state));
+    }
+    return state;
+  }
+
+  private class FieldWriteImpliesReadUseRegistry extends DelegatingUseRegistry {
+
+    private final DexType instanceType;
+
+    FieldWriteImpliesReadUseRegistry(UseRegistry delegate,
+        DexType instanceType) {
+      super(delegate);
+      this.instanceType = instanceType;
+    }
+
+    @Override
+    public boolean registerInstanceFieldWrite(DexField field) {
+      if (isProtoField(field, instanceType)) {
+        super.registerInstanceFieldRead(field);
+      }
+      return super.registerInstanceFieldWrite(field);
+    }
+  }
+
+  private class FilteringUseRegistry extends DelegatingUseRegistry {
+
+    private final DexType instanceType;
+    private final Set<DexField> registerField;
+
+    private FilteringUseRegistry(UseRegistry delegate,
+        DexType instanceType, Set<DexField> registerField) {
+      super(delegate);
+      this.instanceType = instanceType;
+      this.registerField = registerField;
+    }
+
+    @Override
+    public boolean registerInstanceFieldWrite(DexField field) {
+      if (isProtoField(field, instanceType)) {
+        registerField.add(field);
+        return false;
+      }
+      return super.registerInstanceFieldWrite(field);
+    }
+
+    @Override
+    public boolean registerInstanceFieldRead(DexField field) {
+      if (isProtoField(field, instanceType)) {
+        registerField.add(field);
+        return false;
+      }
+      return super.registerInstanceFieldRead(field);
+    }
+
+    @Override
+    public boolean registerInvokeVirtual(DexMethod method) {
+      if (isGetter(method, instanceType)) {
+        // Try whether this is a getXXX method.
+        DexField field = getterToField(method);
+        if (isProtoField(field, instanceType)) {
+          registerField.add(field);
+          return false;
+        }
+        // Try whether this is a getXXXCount method.
+        field = getterToField(method, COUNT_POSTFIX_LENGTH);
+        if (isProtoField(field, instanceType)) {
+          registerField.add(field);
+          return false;
+        }
+      }
+      return super.registerInvokeVirtual(method);
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLitePruner.java b/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLitePruner.java
new file mode 100644
index 0000000..8b0ac9e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/protolite/ProtoLitePruner.java
@@ -0,0 +1,739 @@
+// 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.shaking.protolite;
+
+import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexField;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.DominatorTree;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InstanceGet;
+import com.android.tools.r8.ir.code.InstancePut;
+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.InvokeInterface;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.MemberType;
+import com.android.tools.r8.ir.code.MoveType;
+import com.android.tools.r8.ir.code.Switch;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.SwitchUtils;
+import com.android.tools.r8.ir.optimize.SwitchUtils.EnumSwitchInfo;
+import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntList;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.function.BiPredicate;
+
+/**
+ * Implements the second phase of proto lite tree shaking.
+ * <p>
+ * In the pruner pass, we remove all references to the now dead fields from the methods that
+ * were treated specially during tree shaking using the {@link ProtoLiteExtension}.
+ * <p>
+ * For proto2 code, we aim to keep presence information for fields alive and move the values of
+ * dead fields to the unknown fields storage. For proto3, as it has no concept of passing on
+ * unknown fields, dead fields are completely removed. In particular, reading a proto and writing
+ * it again might loose data.
+ */
+public class ProtoLitePruner extends ProtoLiteBase {
+
+  private final AppInfoWithLiveness appInfo;
+
+  private final DexType visitorType;
+
+  private final DexType methodEnumType;
+  private final DexType codedOutputStreamType;
+  private final DexType protobufListType;
+  private final DexType listType;
+
+  private final DexString visitTag;
+  private final DexString mergeTag;
+  private final DexString isInitializedTag;
+  private final DexString makeImmutabkeTag;
+  private final DexString computeMethodPrefix;
+  private final DexString writeMethodPrefix;
+  private final DexString isInitializedMethodName;
+
+  private final DexString makeImmutableMethodName;
+  private final DexString sizeMethodName;
+  private final Set<DexField> seenFields;
+  private final DexMethod sizeMethod;
+
+  public ProtoLitePruner(AppInfoWithLiveness appInfo) {
+    super(appInfo);
+    this.appInfo = appInfo;
+    DexItemFactory factory = appInfo.dexItemFactory;
+    this.visitorType = factory.createType("Lcom/google/protobuf/GeneratedMessageLite$Visitor;");
+    this.methodEnumType = factory
+        .createType("Lcom/google/protobuf/GeneratedMessageLite$MethodToInvoke;");
+    this.codedOutputStreamType = factory.createType("Lcom/google/protobuf/CodedOutputStream;");
+    this.protobufListType = factory.createType("Lcom/google/protobuf/Internal$ProtobufList;");
+    this.listType = factory.createType("Ljava/util/List;");
+    this.visitTag = factory.createString("VISIT");
+    this.mergeTag = factory.createString("MERGE_FROM_STREAM");
+    this.isInitializedTag = factory.createString("IS_INITIALIZED");
+    this.makeImmutabkeTag = factory.createString("MAKE_IMMUTABLE");
+    this.computeMethodPrefix = factory.createString("compute");
+    this.writeMethodPrefix = factory.createString("write");
+    this.sizeMethodName = factory.createString("size");
+    this.isInitializedMethodName = factory.createString("isInitialized");
+    this.makeImmutableMethodName = factory.createString("makeImmutable");
+    this.sizeMethod = factory.createMethod(listType,
+        factory.createProto(factory.intType), sizeMethodName);
+
+    seenFields = appInfo.withLiveness()
+        .getExtension(ProtoLiteExtension.class, Collections.emptySet());
+  }
+
+  private boolean isPresenceField(DexField field, DexType instanceType) {
+    if (field.getHolder() != instanceType) {
+      return false;
+    }
+    // Proto2 uses fields named bitField<n>_ fields to store presence information.
+    String fieldName = field.name.toString();
+    return fieldName.endsWith("_")
+        && fieldName.startsWith("bitField");
+  }
+
+  boolean isSetterThatNeedsProcessing(DexEncodedMethod method) {
+    // The pruner does not need to process setters, so this method always returns false.
+    return false;
+  }
+
+  private boolean isGetter(DexMethod method) {
+    return isGetterHelper(method, 0);
+  }
+
+  private boolean isCountGetter(DexMethod method) {
+    return isGetterHelper(method, COUNT_POSTFIX_LENGTH);
+  }
+
+  private boolean isGetterHelper(DexMethod method, int postFixLength) {
+    if (!method.name.beginsWith(getterNamePrefix)
+        || !(method.proto.parameters.isEmpty() || hasSingleIntArgument(method))
+        || (method.holder == messageType)
+        || !method.holder.isSubtypeOf(messageType, appInfo)
+        || method.name.size <= GETTER_NAME_PREFIX_LENGTH + postFixLength) {
+      return false;
+    }
+    DexField correspondingField = getterToField(method, postFixLength);
+    return seenFields.contains(correspondingField);
+  }
+
+  private boolean isDefinedAsNull(Value value) {
+    return value.definition != null && value.definition.isConstNumber()
+        && value.definition.asConstNumber().isZero();
+  }
+
+  private boolean isComputeSizeMethod(DexMethod invokedMethod) {
+    return invokedMethod.holder == codedOutputStreamType
+        && invokedMethod.name.beginsWith(computeMethodPrefix);
+  }
+
+  private boolean isWriteMethod(DexMethod invokedMethod) {
+    return invokedMethod.holder == codedOutputStreamType
+        && invokedMethod.name.beginsWith(writeMethodPrefix);
+  }
+
+  private boolean isProtoField(DexField field) {
+    return seenFields.contains(field);
+  }
+
+  public void rewriteProtoLiteSpecialMethod(IRCode code, DexEncodedMethod method) {
+    DexString methodName = method.method.name;
+    if (methodName == dynamicMethodName) {
+      rewriteDynamicMethod(code, method);
+    } else if ((methodName == writeToMethodName) || (methodName == getSerializedSizeMethodName)) {
+      rewriteSizeOrWriteMethod(code);
+    } else if (methodName == constructorMethodName) {
+      rewriteConstructor(code);
+    } else {
+      throw new Unreachable();
+    }
+  }
+
+  /**
+   * For protos with repeated fields, the constructor may contain field initialization code like
+   *
+   * <pre>
+   * private Repeated() {
+   *  repeated_ = com.google.protobuf.GeneratedMessageLite.emptyProtobufList();
+   *  other_ = emptyBooleanList();
+   *  sub_ = emptyProtobufList();
+   * }
+   * </pre>
+   *
+   * which this rewriting removes.
+   */
+  private void rewriteConstructor(IRCode code) {
+    boolean wasRewritten;
+    do {
+      wasRewritten = false;
+      InstructionIterator it = code.instructionIterator();
+      while (it.hasNext()) {
+        Instruction insn = it.next();
+        if (insn.isInstancePut() && isDeadProtoField(insn.asInstancePut().getField())) {
+          // Remove initializations of dead fields.
+          it.remove();
+          wasRewritten = true;
+        } else if (insn.isInvokeStatic()) {
+          // Remove now unneeded constructor calls.
+          InvokeStatic invokeStatic = insn.asInvokeStatic();
+          DexMethod invokedMethod = invokeStatic.getInvokedMethod();
+          if ((invokeStatic.outValue().numberOfAllUsers() == 0)
+              && invokedMethod.proto.returnType.isSubtypeOf(protobufListType, appInfo)) {
+            it.remove();
+          }
+        }
+      }
+    } while (wasRewritten);
+  }
+
+
+  /**
+   * The writeTo and getSerializedSize methods of a generated proto access all fields. We have to
+   * remove the accesses to dead fields. The actual code of these methods varies to quite some
+   * degree depending on the types of the fields. For example
+   *
+   * <pre>
+   * public void writeTo(com.google.protobuf.CodedOutputStream output) throws java.io.IOException {
+   *   if (((bitField0_ & 0x00000001) == 0x00000001)) {
+   *     output.writeInt32(1, id_);
+   *   }
+   *   if (((bitField0_ & 0x00000002) == 0x00000002)) {
+   *     output.writeMessage(2, getInner());
+   *   }
+   *   for (int i = 0; i < repeated_.size(); i++) {
+   *     output.writeString(3, repeated_.get(i));
+   *   }
+   *   for (int i = 0; i < other_.size(); i++) {
+   *     output.writeBool(4, other_.getBoolean(i));
+   *   }
+   *   for (int i = 0; i < sub_.size(); i++) {
+   *     output.writeMessage(5, sub_.get(i));
+   *   }
+   *   unknownFields.writeTo(output);
+   * }
+   * </pre>
+   *
+   * We look for direct field accesses (id_, repeated_, etc. above) and getters (getInner) and
+   * rewrite those to null/0. We also rewrite all uses of the results, like the size() and
+   * write methods above.
+   */
+  private void rewriteSizeOrWriteMethod(IRCode code) {
+    boolean wasRewritten;
+    do {
+      wasRewritten = false;
+      InstructionIterator it = code.instructionIterator();
+      while (it.hasNext()) {
+        Instruction insn = it.next();
+        if (insn.isInstanceGet()) {
+          DexField field = insn.asInstanceGet().getField();
+          if (isDeadProtoField(field)) {
+            // Rewrite deads field access to corresponding 0.
+            it.replaceCurrentInstruction(code.createConstNull(insn.asInstanceGet()));
+            wasRewritten = true;
+          }
+        } else if (insn.isInvokeMethodWithReceiver()) {
+          InvokeMethodWithReceiver invokeMethod = insn.asInvokeMethodWithReceiver();
+          DexMethod invokedMethod = invokeMethod.getInvokedMethod();
+          if (isDeadProtoGetter(invokedMethod)) {
+            // Rewrite dead getters.
+            it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+            wasRewritten = true;
+          } else if (invokedMethod.name == sizeMethodName
+              && invokedMethod.holder.isSubtypeOf(listType, appInfo)) {
+            Value receiver = invokeMethod.getReceiver();
+            if (isDefinedAsNull(receiver)) {
+              // Rewrite size() methods with null receiver.
+              it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+            }
+          } else if (invokedMethod.name == getterNamePrefix
+              && invokedMethod.holder.isSubtypeOf(listType, appInfo)) {
+            Value receiver = invokeMethod.getReceiver();
+            if (isDefinedAsNull(receiver)) {
+              // Rewrite get(x) methods with null receiver.
+              it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+              wasRewritten = true;
+            }
+          } else if (isWriteMethod(invokedMethod)) {
+            Value lastArg = Iterables.getLast(invokeMethod.inValues());
+            if (isDefinedAsNull(lastArg)) {
+              it.remove();
+            }
+          }
+        } else if (insn.isInvokeMethod()) {
+          InvokeMethod invokeMethod = insn.asInvokeMethod();
+          DexMethod invokedMethod = invokeMethod.getInvokedMethod();
+          if (isComputeSizeMethod(invokedMethod)) {
+            Value lastArg = Iterables.getLast(invokeMethod.inValues());
+            if (isDefinedAsNull(lastArg)) {
+              // This is a computeSize method on a constant null. The field was dead.
+              assert (invokeMethod.outValue() != null);
+              it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+              wasRewritten = true;
+            }
+          }
+        }
+      }
+    } while (wasRewritten);
+  }
+
+  /**
+   * The dyanmicMethod code is actually a collection of various methods contained in one.
+   * It uses a switch statement over an enum to identify which actual operation is performed.
+   * We need to rewrite all cases that might access dead fields. These are
+   * <dl>
+   * <dt>IS_INITIALIZED</dt>
+   * <dd>See {@link #rewriteIsInitializedCase}.</dd>
+   * <dt>MAKE_IMMUTABLE</dt>
+   * <dd>See {@link #rewriteMakeImmutableCase}.</dd>
+   * <dt>VISIT</dt>
+   * <dd>See {@link #rewriteVisitCase}.</dd>
+   * <dt>MERGE_FROM_STREAM</dt>
+   * <dd>See {@link #rewriteMergeCase}.</dd>
+   * </dl>
+   */
+  private void rewriteDynamicMethod(IRCode code, DexEncodedMethod method) {
+    // This method contains a switch and we are interested in some of the cases only.
+    InstructionIterator iterator = code.instructionIterator();
+    Instruction matchingInstr = iterator.nextUntil(Instruction::isSwitch);
+    if (matchingInstr == null) {
+      throw new CompilationError("dynamicMethod in protoLite without switch.");
+    }
+    Switch switchInstr = matchingInstr.asSwitch();
+    EnumSwitchInfo info = SwitchUtils.analyzeSwitchOverEnum(switchInstr, appInfo);
+    if (info == null || info.enumClass != methodEnumType) {
+      throw new CompilationError("Malformed switch in dynamicMethod of proto lite.");
+    }
+    BasicBlock initializedCase = null;
+    BasicBlock visitCase = null;
+    BasicBlock mergeCase = null;
+    BasicBlock makeImmutableCase = null;
+    for (int keyIdx = 0; keyIdx < switchInstr.numberOfKeys(); keyIdx++) {
+      int key = switchInstr.getKey(keyIdx);
+      DexField label = info.indexMap.get(key);
+      assert label != null;
+      if (label.name == visitTag) {
+        assert visitCase == null;
+        visitCase = switchInstr.targetBlock(keyIdx);
+      } else if (label.name == mergeTag) {
+        assert mergeCase == null;
+        mergeCase = switchInstr.targetBlock(keyIdx);
+      } else if (label.name == isInitializedTag) {
+        assert initializedCase == null;
+        initializedCase = switchInstr.targetBlock(keyIdx);
+      } else if (label.name == makeImmutabkeTag) {
+        assert makeImmutableCase == null;
+        makeImmutableCase = switchInstr.targetBlock(keyIdx);
+      }
+    }
+    DexType instanceType = method.method.getHolder();
+    rewriteIsInitializedCase(initializedCase, instanceType, code);
+    assert code.isConsistentSSA();
+    rewriteMakeImmutableCase(makeImmutableCase, code);
+    assert code.isConsistentSSA();
+    rewriteVisitCase(visitCase, code);
+    assert code.isConsistentSSA();
+    rewriteMergeCase(mergeCase, instanceType, code);
+    assert code.isConsistentSSA();
+  }
+
+  /**
+   * In the presence of repeated fields, the MAKE_IMMUTABLE case will contain code of the form
+   *
+   * <pre>
+   * case MAKE_IMMUTABLE: {
+   *   repeated_.makeImmutable();
+   *   other_.makeImmutable();
+   *   sub_.makeImmutable();
+   *   return null;
+   * }
+   * </pre>
+   *
+   * For dead fields, we remove the field access and the call to makeImmutable.
+   */
+  private void rewriteMakeImmutableCase(BasicBlock switchCase, IRCode code) {
+    DominatorTree dom = new DominatorTree(code);
+    boolean wasRewritten;
+    do {
+      wasRewritten = false;
+      for (BasicBlock current : dom.dominatedBlocks(switchCase)) {
+        InstructionIterator it = current.iterator();
+        while (it.hasNext()) {
+          Instruction insn = it.next();
+          if (insn.isInstanceGet() && isDeadProtoField(insn.asInstanceGet().getField())) {
+            it.replaceCurrentInstruction(code.createConstNull(insn));
+            wasRewritten = true;
+          } else if (insn.isInvokeMethodWithReceiver()) {
+            InvokeMethodWithReceiver invokeMethod = insn.asInvokeMethodWithReceiver();
+            DexMethod invokedMethod = invokeMethod.getInvokedMethod();
+            if (isDeadProtoGetter(invokedMethod)) {
+              it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+              wasRewritten = true;
+            } else if (invokedMethod.name == makeImmutableMethodName
+                && invokedMethod.getHolder().isSubtypeOf(protobufListType, appInfo)) {
+              Value receiver = invokeMethod.getReceiver();
+              if (isDefinedAsNull(receiver)) {
+                it.remove();
+              }
+            }
+          }
+        }
+      }
+    } while (wasRewritten);
+  }
+
+  /**
+   * The IS_INITIALIZED case also has a high degree of variability depending on the type of fields.
+   * Common code looks as follows
+   *
+   * <pre>
+   * case IS_INITIALIZED: {
+   *   byte isInitialized = memoizedIsInitialized;
+   *   if (isInitialized == 1) return DEFAULT_INSTANCE;
+   *   if (isInitialized == 0) return null;
+   *
+   *   boolean shouldMemoize = ((Boolean) arg0).booleanValue();
+   *   if (!hasId()) {
+   *     if (shouldMemoize) {
+   *       memoizedIsInitialized = 0;
+   *     }
+   *     return null;
+   *   }
+   *   for (int i = 0; i < getSubCount(); i++) {
+   *     if (!getSub(i).isInitialized()) {
+   *       if (shouldMemoize) {
+   *         memoizedIsInitialized = 0;
+   *       }
+   *       return null;
+   *     }
+   *   }
+   *   if (shouldMemoize) memoizedIsInitialized = 1;
+   *   return DEFAULT_INSTANCE;
+   * }
+   * </pre>
+   *
+   * We remove all the accesses of dead fields and getters. We also replace secondary invokes
+   * (like getSubCount or isInitialized) with conservative default values (e.g. 0, true).
+   * <p>
+   * We also rewrite getXXXCount methods on live fields, as accesses to those methods was filtered
+   * during tree shaking. In place of those methods, we inline their definition.
+   */
+  private void rewriteIsInitializedCase(BasicBlock switchCase, DexType instanceType,
+      IRCode code) {
+    DominatorTree dom = new DominatorTree(code);
+    boolean wasRewritten;
+    do {
+      wasRewritten = false;
+      for (BasicBlock current : dom.dominatedBlocks(switchCase)) {
+        InstructionIterator it = current.iterator();
+        while (it.hasNext()) {
+          Instruction insn = it.next();
+          if (insn.isInvokeMethodWithReceiver()) {
+            InvokeMethodWithReceiver invokeMethod = insn.asInvokeMethodWithReceiver();
+            DexMethod invokedMethod = invokeMethod.getInvokedMethod();
+            if (isDeadProtoGetter(invokedMethod)) {
+              it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+              wasRewritten = true;
+            } else if (invokedMethod.name == isInitializedMethodName
+                && invokedMethod.getHolder().isSubtypeOf(messageType, appInfo)) {
+              Value receiver = invokeMethod.getReceiver();
+              if (isDefinedAsNull(receiver)) {
+                // We cannot compute initialization state for nested messages and repeated
+                // messages that have been removed or moved to unknown fields. Just return
+                // true.
+                it.replaceCurrentInstruction(code.createTrue());
+                wasRewritten = true;
+              }
+            } else if (isCountGetter(invokedMethod)) {
+              // We have to rewrite these as a precaution, as they might be dead due to
+              // tree shaking ignoring them.
+              DexField field = getterToField(invokedMethod, 5);
+              if (appInfo.liveFields.contains(field)) {
+                // Effectively inline the code that is normally inside these methods.
+                Value thisReference = invokeMethod.getReceiver();
+                Value newResult = code.createValue(MoveType.SINGLE);
+                invokeMethod.outValue().replaceUsers(newResult);
+                Value theList = code.createValue(MoveType.OBJECT);
+                it.replaceCurrentInstruction(
+                    new InstanceGet(MemberType.OBJECT, theList, thisReference, field));
+                it.add(new InvokeInterface(sizeMethod, newResult, Collections.emptyList()));
+              } else {
+                // The field is dead, so its count is always 0.
+                it.replaceCurrentInstruction(code.createConstNull(invokeMethod));
+              }
+            }
+          }
+        }
+      }
+    } while (wasRewritten);
+  }
+
+  private InstancePut findProtoFieldWrite(BasicBlock block, DexType instanceType,
+      BiPredicate<DexField, DexType> filter, DominatorTree dom) {
+    for (BasicBlock current : dom.dominatedBlocks(block)) {
+      InstructionIterator insns = current.iterator();
+      InstancePut instancePut = (InstancePut) insns.nextUntil(Instruction::isInstancePut);
+      if (instancePut != null && filter.test(instancePut.getField(), instanceType)) {
+        return instancePut;
+      }
+    }
+    return null;
+  }
+
+  /**
+   * For the merge case, we typically see code that contains a switch over the field tags. The inner
+   * switch has the form
+   *
+   * <pre>
+   * switch (tag) {
+   *   case 0:
+   *     done = true;
+   *     break;
+   *   default: {
+   *     if (!parseUnknownField(tag, input)) {
+   *       done = true;
+   *     }
+   *     break;
+   *   }
+   *   case 8: {
+   *     bitField0_ |= 0x00000001;
+   *     id_ = input.readInt32();
+   *     break;
+   *   }
+   *   case 18: {
+   *     nestedproto2.GeneratedNestedProto.NestedOne.Builder subBuilder = null;
+   *     if (((bitField0_ & 0x00000002) == 0x00000002)) {
+   *       subBuilder = inner_.toBuilder();
+   *     }
+   *     inner_ = input.readMessage(nestedproto2.GeneratedNestedProto.NestedOne.parser(),
+   *         extensionRegistry);
+   *     if (subBuilder != null) {
+   *       subBuilder.mergeFrom(inner_);
+   *       inner_ = subBuilder.buildPartial();
+   *     }
+   *     bitField0_ |= 0x00000002;
+   *     break;
+   *   }
+   *   case 24: {
+   *     if (!other_.isModifiable()) {
+   *       other_ =
+   *           com.google.protobuf.GeneratedMessageLite.mutableCopy(other_);
+   *     }
+   *     other_.addBoolean(input.readBool());
+   *     break;
+   *   }
+   *   case 26: {
+   *     int length = input.readRawVarint32();
+   *     int limit = input.pushLimit(length);
+   *     if (!other_.isModifiable() && input.getBytesUntilLimit() > 0) {
+   *       final int currentSize = other_.size();
+   *       other_ = other_.mutableCopyWithCapacity(
+   *       currentSize + (length/1));
+   *     }
+   *     while (input.getBytesUntilLimit() > 0) {
+   *       other_.addBoolean(input.readBool());
+   *     }
+   *     input.popLimit(limit);
+   *     break;
+   *   }
+   * }
+   * </pre>
+   *
+   * The general approach here is to identify the field that is processed by a case and, if
+   * the field is dead, remove the entire case.
+   * <p>
+   * We slightly complicate the rewriting by also checking whether the block computes a
+   * presence bitfield (bitField0_ above). If so, we move that computation to a new block that
+   * continues to the default case. This ensures that presence is recorded correctly, yet the
+   * field is moved to the unknownFields collection, if such exists.
+   */
+  private void rewriteMergeCase(BasicBlock caseBlock, DexType instanceType,
+      IRCode code) {
+    // We are looking for a switch statement over the input tag. Just traverse all blocks until
+    // we find it.
+    List<BasicBlock> deadBlocks = new ArrayList<>();
+    DominatorTree dom = new DominatorTree(code);
+    for (BasicBlock current : dom.dominatedBlocks(caseBlock)) {
+      InstructionIterator it = current.iterator();
+      Switch switchInstr;
+      if ((switchInstr = (Switch) it.nextUntil(Instruction::isSwitch)) != null) {
+        int nextBlock = code.getHighestBlockNumber() + 1;
+        IntList liveKeys = new IntArrayList(switchInstr.numberOfKeys());
+        List<BasicBlock> liveBlocks = new ArrayList<>(switchInstr.numberOfKeys());
+        boolean needsCleanup = false;
+        // Filter out all the cases that contain writes to dead fields.
+        for (int keyIdx = 0; keyIdx < switchInstr.numberOfKeys(); keyIdx++) {
+          BasicBlock targetBlock = switchInstr.targetBlock(keyIdx);
+          InstancePut instancePut =
+              findProtoFieldWrite(targetBlock, instanceType, (field, holder) -> isProtoField(field),
+                  dom);
+          if (instancePut == null
+              || appInfo.withLiveness().liveFields.contains(instancePut.getField())) {
+            // This is a live case. Keep it.
+            liveKeys.add(switchInstr.getKey(keyIdx));
+            liveBlocks.add(targetBlock);
+          } else {
+            // We cannot just remove this entire switch case if there is some computation here
+            // for whether the field is present. We check this by searching for a write to
+            // the bitField<xxx>_ fields. If such write exists, we move the corresponding
+            // instructions to the first block in the switch.
+            //TODO(herhut): Only do this if the written field has a live hasMethod.
+            InstancePut bitFieldUpdate = findProtoFieldWrite(targetBlock, instanceType,
+                this::isPresenceField, dom);
+            if (bitFieldUpdate != null) {
+              BasicBlock newBlock = BasicBlock.createGotoBlock(nextBlock++);
+              newBlock.link(switchInstr.fallthroughBlock());
+              // Copy over the computation of the field;
+              moveInstructionTo(newBlock.listIterator(), bitFieldUpdate, dom, targetBlock);
+              switchInstr.getBlock().link(newBlock);
+              liveKeys.add(switchInstr.getKey(keyIdx));
+              liveBlocks.add(newBlock);
+              code.blocks.add(newBlock);
+            }
+            needsCleanup = true;
+          }
+        }
+        if (needsCleanup) {
+          DominatorTree updatedTree = new DominatorTree(code);
+          BasicBlock fallThrough = switchInstr.fallthroughBlock();
+          List<BasicBlock> successors = ImmutableList.copyOf(current.getNormalSucessors());
+          for (BasicBlock successor : successors) {
+            if (successor != fallThrough && !liveBlocks.contains(successor)) {
+              deadBlocks.addAll(current.unlink(successor, updatedTree));
+            }
+          }
+          int[] blockIndices = new int[liveBlocks.size()];
+          for (int i = 0; i < liveBlocks.size(); i++) {
+            blockIndices[i] = current.getSuccessors().indexOf(liveBlocks.get(i));
+          }
+          Switch newSwitch = new Switch(switchInstr.inValues().get(0), liveKeys.toIntArray(),
+              blockIndices, current.getSuccessors().indexOf(fallThrough));
+          it.replaceCurrentInstruction(newSwitch);
+        }
+        break;
+      }
+    }
+    code.removeBlocks(deadBlocks);
+  }
+
+  //TODO(herhut): This should really be a copy with a value substitution map.
+  private void moveInstructionTo(InstructionListIterator iterator, Instruction insn,
+      DominatorTree dom,
+      BasicBlock dominator) {
+    for (Value value : insn.inValues()) {
+      Instruction input = value.definition;
+      // We do not support phis.
+      assert input != null;
+      if (dom.dominatedBy(input.getBlock(), dominator)) {
+        // And no shared instructions.
+        assert input.outValue().numberOfUsers() == 1;
+        moveInstructionTo(iterator, input, dom, dominator);
+      }
+    }
+    insn.getBlock().removeInstruction(insn);
+    iterator.add(insn);
+  }
+
+  private boolean isDeadProtoField(DexField field) {
+    return isProtoField(field) && !appInfo.liveFields.contains(field);
+  }
+
+  private boolean isDeadProtoGetter(DexMethod method) {
+    return isGetter(method) && isDeadProtoField(getterToField(method));
+  }
+
+  private boolean isVisitOfDeadField(Instruction instruction) {
+    if (!instruction.isInvokeMethod()) {
+      return false;
+    }
+    InvokeMethod invokeMethod = instruction.asInvokeMethod();
+    if (invokeMethod.getInvokedMethod().getHolder() == visitorType
+        && invokeMethod.getInvokedMethod().getArity() >= 2) {
+      Instruction secondArg = invokeMethod.inValues().get(2).definition;
+      return secondArg.isConstNumber();
+    }
+    return false;
+  }
+
+  /**
+   * The visit case has typically the form
+   *
+   * <pre>
+   * case VISIT: {
+   *   Visitor visitor = (Visitor) arg0;
+   *   repeatedproto.GeneratedRepeatedProto.Repeated other =
+   *       (repeatedproto.GeneratedRepeatedProto.Repeated) arg1;
+   *   id_ = visitor.visitInt(
+   *       hasId(), id_,
+   *       other.hasId(), other.id_);
+   *   repeated_= visitor.visitList(repeated_, other.repeated_);
+   *   inner_ = visitor.visitMessage(inner_, other.inner_);
+   *   if (visitor == com.google.protobuf.GeneratedMessageLite.MergeFromVisitor.INSTANCE) {
+   *     bitField0_ |= other.bitField0_;
+   *   }
+   *   return this;
+   * }
+   * </pre>
+   *
+   * We remove all writes and reads to dead fields and correspondign secondary instructions, like
+   * the visitXXX methods.
+   * <p>
+   * Note that the invoked hasMethods are benign, as the only access the bitFieldXXX_ fields, which
+   * we currently do not remove. Inlining will likely remove the methods.
+   */
+  private void rewriteVisitCase(BasicBlock switchCase, IRCode code) {
+    DominatorTree dom = new DominatorTree(code);
+    boolean wasRewritten;
+    do {
+      wasRewritten = false;
+      for (BasicBlock target : dom.dominatedBlocks(switchCase)) {
+        InstructionIterator it = target.iterator();
+        while (it.hasNext()) {
+          Instruction insn = it.next();
+          if (insn.isInstanceGet()) {
+            InstanceGet instanceGet = insn.asInstanceGet();
+            if (isDeadProtoField(instanceGet.getField())) {
+              it.replaceCurrentInstruction(code.createConstNull(instanceGet));
+              wasRewritten = true;
+            }
+          } else if (insn.isInstancePut()) {
+            if (isDeadProtoField(insn.asInstancePut().getField())) {
+              it.remove();
+            }
+          } else if (isVisitOfDeadField(insn)) {
+            it.replaceCurrentInstruction(code.createConstNull(insn));
+          } else if (insn.isCheckCast()) {
+            // The call to visitXXX is a generic method invoke, so it will be followed by a check
+            // cast to fix up the type. As the result is no longer needed once we are done, we can
+            // remove the cast. This removes a potential last reference to an inner message class.
+            // TODO(herhut): We should have a generic dead cast removal.
+            Value inValue = insn.inValues().get(0);
+            if (isDefinedAsNull(inValue)) {
+              insn.outValue().replaceUsers(inValue);
+              it.remove();
+            }
+          }
+
+        }
+      }
+    } while (wasRewritten);
+  }
+}
diff --git a/src/test/examples/enumproto/Enumproto.java b/src/test/examples/enumproto/Enumproto.java
new file mode 100644
index 0000000..9176378
--- /dev/null
+++ b/src/test/examples/enumproto/Enumproto.java
@@ -0,0 +1,66 @@
+// 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 enumproto;
+
+
+import enumproto.GeneratedEnumProto.Enum;
+import enumproto.three.GeneratedEnumProto.EnumThree;
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+
+public class Enumproto {
+
+  private static final byte[] WITH_ALL_FIELDS = new byte[]{6, 8, 42, 16, 2, 24, 3};
+  private static final byte[] WITH_DEFAULT_FOR_ENUM = new byte[]{2, 8, 42};
+
+
+  public static void main(String... args) throws IOException {
+    readProtoAndPrintDaEnum(WITH_ALL_FIELDS);
+    readProtoAndPrintDaEnum(WITH_DEFAULT_FOR_ENUM);
+    readProtoThreeAndPrintDaEnum(WITH_ALL_FIELDS);
+    readProtoThreeAndPrintDaEnum(WITH_DEFAULT_FOR_ENUM);
+    roundTrip(WITH_ALL_FIELDS);
+    roundTrip(WITH_DEFAULT_FOR_ENUM);
+    roundTripThree(WITH_ALL_FIELDS);
+    roundTripThree(WITH_DEFAULT_FOR_ENUM);
+  }
+
+  private static void readProtoAndPrintDaEnum(byte[] bytes) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(bytes);
+    Enum.Builder builder = Enum.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Enum buffer = builder.build();
+    System.out.println(buffer.getEnum());
+  }
+
+  private static void readProtoThreeAndPrintDaEnum(byte[] bytes) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(bytes);
+    EnumThree.Builder builder = EnumThree.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    EnumThree buffer = builder.build();
+    System.out.println(buffer.getEnum());
+  }
+
+  private static void roundTrip(byte[] bytes) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(bytes);
+    Enum.Builder builder = Enum.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Enum buffer = builder.build();
+    ByteArrayOutputStream output = new ByteArrayOutputStream();
+    buffer.writeDelimitedTo(output);
+    readProtoAndPrintDaEnum(output.toByteArray());
+  }
+
+  private static void roundTripThree(byte[] bytes) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(bytes);
+    EnumThree.Builder builder = EnumThree.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    EnumThree buffer = builder.build();
+    ByteArrayOutputStream output = new ByteArrayOutputStream();
+    buffer.writeDelimitedTo(output);
+    readProtoThreeAndPrintDaEnum(output.toByteArray());
+  }
+
+}
diff --git a/src/test/examples/enumproto/enum.proto b/src/test/examples/enumproto/enum.proto
new file mode 100644
index 0000000..0fa5695
--- /dev/null
+++ b/src/test/examples/enumproto/enum.proto
@@ -0,0 +1,25 @@
+// 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.
+syntax = "proto2";
+package enumproto;
+
+option java_outer_classname = "GeneratedEnumProto";
+
+message Enum {
+  required int32 id = 1;
+  enum DaEnum {
+    UNKOWN = 0;
+    KNOWN = 1;
+    BELIEF = 2;
+  }
+  optional DaEnum enum = 2;
+  enum OtherEnum {
+    BLACK = 0;
+    RED = 1;
+    GREEN = 2;
+    OKALALALA = 3;
+  }
+  optional OtherEnum other = 3;
+}
+
diff --git a/src/test/examples/enumproto/enum_three.proto b/src/test/examples/enumproto/enum_three.proto
new file mode 100644
index 0000000..a2731fb
--- /dev/null
+++ b/src/test/examples/enumproto/enum_three.proto
@@ -0,0 +1,25 @@
+// Copyright (c) 2016, 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.
+syntax = "proto3";
+package enumproto.three;
+
+option java_outer_classname = "GeneratedEnumProto";
+
+message EnumThree {
+  int32 id = 1;
+  enum DaEnum {
+    UNKOWN = 0;
+    KNOWN = 1;
+    BELIEF = 2;
+  }
+  DaEnum enum = 2;
+  enum OtherEnum {
+    BLACK = 0;
+    RED = 1;
+    GREEN = 2;
+    OKALALALA = 3;
+  }
+  OtherEnum other = 3;
+}
+
diff --git a/src/test/examples/enumproto/keep-rules.txt b/src/test/examples/enumproto/keep-rules.txt
new file mode 100644
index 0000000..088f88f
--- /dev/null
+++ b/src/test/examples/enumproto/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class enumproto.Enumproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/nestedproto1/Nestedproto.java b/src/test/examples/nestedproto1/Nestedproto.java
new file mode 100644
index 0000000..fe1a535
--- /dev/null
+++ b/src/test/examples/nestedproto1/Nestedproto.java
@@ -0,0 +1,31 @@
+// 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 nestedproto1;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import nestedproto1.GeneratedNestedProto.Outer;
+
+public class Nestedproto {
+
+  private static final byte[] NESTED_MESSAGE_WITH_BOTH = new byte[] {25, 8, 42, 18, 12, 8, 1, 18, 8,
+      105, 110, 110, 101, 114, 79, 110, 101, 26, 7, 8, 2, 21, 0, 0, -10, 66};
+
+  private static final byte[] NESTED_MESSAGE_WITH_ONE = new byte[]{16, 8, 42, 18, 12, 8, 1, 18, 8,
+      105,
+      110, 110, 101, 114, 79, 110, 101};
+
+  public static void main(String... args) throws IOException {
+    testWith(NESTED_MESSAGE_WITH_BOTH);
+    testWith(NESTED_MESSAGE_WITH_ONE);
+  }
+
+  public static void testWith(byte[] data) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(data);
+    Outer.Builder builder = Outer.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Outer outer = builder.build();
+    System.out.println(outer.getInner().getOther());
+  }
+}
diff --git a/src/test/examples/nestedproto1/keep-rules.txt b/src/test/examples/nestedproto1/keep-rules.txt
new file mode 100644
index 0000000..1c47672
--- /dev/null
+++ b/src/test/examples/nestedproto1/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class nestedproto1.Nestedproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/nestedproto1/nested.proto b/src/test/examples/nestedproto1/nested.proto
new file mode 100644
index 0000000..0d05749
--- /dev/null
+++ b/src/test/examples/nestedproto1/nested.proto
@@ -0,0 +1,24 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package nestedproto1;
+
+option java_outer_classname = "GeneratedNestedProto";
+
+message NestedOne {
+  required int32 id = 1;
+  optional string other = 2;
+}
+
+message NestedTwo {
+  required int32 id = 1;
+  optional float other = 2;
+}
+
+message Outer {
+  required int32 id = 1;
+  required NestedOne inner = 2;
+  optional NestedTwo inner2 = 3;
+}
+
diff --git a/src/test/examples/nestedproto2/Nestedproto.java b/src/test/examples/nestedproto2/Nestedproto.java
new file mode 100644
index 0000000..59217de
--- /dev/null
+++ b/src/test/examples/nestedproto2/Nestedproto.java
@@ -0,0 +1,33 @@
+// 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 nestedproto2;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import nestedproto2.GeneratedNestedProto.Outer;
+
+public class Nestedproto {
+
+  private static final byte[] NESTED_MESSAGE_WITH_BOTH = new byte[]{25, 8, 42, 18, 12, 8, 1, 18, 8,
+      105, 110, 110, 101, 114, 79, 110, 101, 26, 7, 8, 2, 21, 0, 0, -10, 66};
+
+  private static final byte[] NESTED_MESSAGE_WITH_ONE = new byte[]{16, 8, 42, 18, 12, 8, 1, 18, 8,
+      105,
+      110, 110, 101, 114, 79, 110, 101};
+
+  // Test that all fields remain when roundtripping with removed fields.
+  public static void main(String... args) throws IOException {
+    testWith(NESTED_MESSAGE_WITH_BOTH);
+    testWith(NESTED_MESSAGE_WITH_ONE);
+  }
+
+  private static void testWith(byte[] data) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(data);
+    Outer.Builder builder = Outer.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    builder.setId(1982);
+    Outer outer = builder.build();
+    outer.writeTo(System.out);
+  }
+}
diff --git a/src/test/examples/nestedproto2/keep-rules.txt b/src/test/examples/nestedproto2/keep-rules.txt
new file mode 100644
index 0000000..87c9218
--- /dev/null
+++ b/src/test/examples/nestedproto2/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class nestedproto2.Nestedproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/nestedproto2/nested.proto b/src/test/examples/nestedproto2/nested.proto
new file mode 100644
index 0000000..ac56f40
--- /dev/null
+++ b/src/test/examples/nestedproto2/nested.proto
@@ -0,0 +1,24 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package nestedproto2;
+
+option java_outer_classname = "GeneratedNestedProto";
+
+message NestedOne {
+  required int32 id = 1;
+  optional string other = 2;
+}
+
+message NestedTwo {
+  required int32 id = 1;
+  optional float other = 2;
+}
+
+message Outer {
+  required int32 id = 1;
+  required NestedOne inner = 2;
+  optional NestedTwo inner2 = 3;
+}
+
diff --git a/src/test/examples/oneofproto/Oneofproto.java b/src/test/examples/oneofproto/Oneofproto.java
new file mode 100644
index 0000000..261705f
--- /dev/null
+++ b/src/test/examples/oneofproto/Oneofproto.java
@@ -0,0 +1,38 @@
+// 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 oneofproto;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+import oneofproto.GeneratedOneOfProto.Oneof;
+
+public class Oneofproto {
+
+  private static final byte[] WITH_BOOL_FIELD = new byte[]{4, 8, 42, 24, 1};
+  private static final byte[] WITH_FLOAT_FIELD = new byte[]{7, 8, 42, 21, 0, 0, -10, 66};
+  private static final byte[] WITH_STRING_FIELD = new byte[]{9, 8, 42, 34, 5, 104, 101, 108, 108,
+      111};
+  private static final byte[] WITH_NO_FIELD = new byte[]{2, 8, 42};
+
+
+  public static void main(String... args) throws IOException {
+    roundTrip(WITH_BOOL_FIELD);
+    roundTrip(WITH_FLOAT_FIELD);
+    roundTrip(WITH_STRING_FIELD);
+    roundTrip(WITH_NO_FIELD);
+  }
+
+  private static void roundTrip(byte[] data) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(data);
+    Oneof.Builder builder = Oneof.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Oneof oneof = builder.build();
+    ByteArrayOutputStream output = new ByteArrayOutputStream();
+    oneof.writeDelimitedTo(output);
+    System.out.println(Arrays.toString(output.toByteArray()));
+  }
+
+}
diff --git a/src/test/examples/oneofproto/keep-rules.txt b/src/test/examples/oneofproto/keep-rules.txt
new file mode 100644
index 0000000..70f00f1
--- /dev/null
+++ b/src/test/examples/oneofproto/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class oneofproto.Oneofproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/oneofproto/oneof.proto b/src/test/examples/oneofproto/oneof.proto
new file mode 100644
index 0000000..c5a67a1
--- /dev/null
+++ b/src/test/examples/oneofproto/oneof.proto
@@ -0,0 +1,17 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package oneofproto;
+
+option java_outer_classname = "GeneratedOneOfProto";
+
+message Oneof {
+  required int32 id = 1;
+  oneof otherfields {
+    float floatField = 2;
+    bool boolField = 3;
+    string stringField = 4;
+  }
+}
+
diff --git a/src/test/examples/protowithexts/withexts.proto b/src/test/examples/protowithexts/withexts.proto
new file mode 100644
index 0000000..d384173
--- /dev/null
+++ b/src/test/examples/protowithexts/withexts.proto
@@ -0,0 +1,19 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package protowithexts;
+
+option java_outer_classname = "GeneratedProtoWithExts";
+
+message Simple {
+  required int32 id = 1;
+
+  optional int32 other = 2;
+
+  extensions 10 to 19;
+}
+
+extend Simple {
+  optional string extra = 10;
+}
diff --git a/src/test/examples/repeatedproto/Repeatedproto.java b/src/test/examples/repeatedproto/Repeatedproto.java
new file mode 100644
index 0000000..280070d
--- /dev/null
+++ b/src/test/examples/repeatedproto/Repeatedproto.java
@@ -0,0 +1,22 @@
+// 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 repeatedproto;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import repeatedproto.GeneratedRepeatedProto.Repeated;
+
+public class Repeatedproto {
+
+  private static final byte[] WITH_ALL_FIELDS = new byte[]{29, 8, 123, 18, 3, 111, 110, 101, 18, 3,
+      116, 119, 111, 18, 5, 116, 104, 114, 101, 101, 24, 1, 34, 2, 8, 42, 34, 2, 8, 42};
+
+  public static void main(String... args) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(WITH_ALL_FIELDS);
+    Repeated.Builder builder = Repeated.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Repeated repeated = builder.build();
+    System.out.println(repeated.getRepeatedList());
+  }
+}
diff --git a/src/test/examples/repeatedproto/keep-rules.txt b/src/test/examples/repeatedproto/keep-rules.txt
new file mode 100644
index 0000000..3d02352
--- /dev/null
+++ b/src/test/examples/repeatedproto/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class repeatedproto.Repeatedproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/repeatedproto/repeated.proto b/src/test/examples/repeatedproto/repeated.proto
new file mode 100644
index 0000000..7414e6f
--- /dev/null
+++ b/src/test/examples/repeatedproto/repeated.proto
@@ -0,0 +1,20 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package repeatedproto;
+
+option java_outer_classname = "GeneratedRepeatedProto";
+
+message Repeated {
+  required int32 id = 1;
+  repeated string repeated = 2;
+  repeated bool other = 3;
+
+  message Sub {
+    required int32 value = 1;
+  }
+
+  repeated Sub sub = 4;
+}
+
diff --git a/src/test/examples/repeatedproto/repeated_three.proto b/src/test/examples/repeatedproto/repeated_three.proto
new file mode 100644
index 0000000..7da7881
--- /dev/null
+++ b/src/test/examples/repeatedproto/repeated_three.proto
@@ -0,0 +1,15 @@
+// Copyright (c) 2016, 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.
+syntax = "proto3";
+package repeatedproto.three;
+
+option java_outer_classname = "GeneratedRepeatedProto";
+
+
+message RepeatedThree {
+  int32 id = 1;
+  repeated string repeated = 2;
+  repeated bool other = 3;
+}
+
diff --git a/src/test/examples/simpleproto1/Simpleproto.java b/src/test/examples/simpleproto1/Simpleproto.java
new file mode 100644
index 0000000..d07ce8d
--- /dev/null
+++ b/src/test/examples/simpleproto1/Simpleproto.java
@@ -0,0 +1,56 @@
+// 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 simpleproto1;
+
+import com.google.protobuf.UninitializedMessageException;
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+import simpleproto1.GeneratedSimpleProto.Simple;
+
+public class Simpleproto {
+
+  private static final byte[] WITH_REQUIRED_FIELDS = new byte[]{7, 8, 42, 21, 0, 0, -10, 66};
+  private static final byte[] WITH_MISSING_FIELD = new byte[]{2, 8, 42};
+
+
+  public static void main(String... args) throws IOException {
+    readProtoWithAllReqFields();
+    partialBuildFails();
+    partialReadFails();
+  }
+
+  private static void partialBuildFails() {
+    Simple.Builder builder = Simple.newBuilder();
+    builder.setId(32);
+    try {
+      builder.build();
+    } catch (UninitializedMessageException e) {
+      System.out.println("got exception");
+    }
+  }
+
+  private static void partialReadFails() throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(WITH_MISSING_FIELD);
+    Simple.Builder builder = Simple.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    try {
+      builder.build();
+    } catch (UninitializedMessageException e) {
+      System.out.println("got exception");
+    }
+  }
+
+  private static void readProtoWithAllReqFields() throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(WITH_REQUIRED_FIELDS);
+    Simple.Builder builder = Simple.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Simple simple = builder.build();
+    ByteArrayOutputStream output = new ByteArrayOutputStream(WITH_REQUIRED_FIELDS.length);
+    simple.writeDelimitedTo(output);
+    System.out.println(Arrays.toString(output.toByteArray()));
+    System.out.println(Arrays.equals(WITH_REQUIRED_FIELDS, output.toByteArray()));
+  }
+}
diff --git a/src/test/examples/simpleproto1/keep-rules.txt b/src/test/examples/simpleproto1/keep-rules.txt
new file mode 100644
index 0000000..3c3c33f
--- /dev/null
+++ b/src/test/examples/simpleproto1/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class simpleproto1.Simpleproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/simpleproto1/simple.proto b/src/test/examples/simpleproto1/simple.proto
new file mode 100644
index 0000000..f4e1be4
--- /dev/null
+++ b/src/test/examples/simpleproto1/simple.proto
@@ -0,0 +1,14 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package simpleproto1;
+
+option java_outer_classname = "GeneratedSimpleProto";
+
+message Simple {
+  required int32 id = 1;
+  required float unusedRequired = 2;
+  optional bool other = 3;
+}
+
diff --git a/src/test/examples/simpleproto2/Simpleproto.java b/src/test/examples/simpleproto2/Simpleproto.java
new file mode 100644
index 0000000..f333d72
--- /dev/null
+++ b/src/test/examples/simpleproto2/Simpleproto.java
@@ -0,0 +1,30 @@
+// 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 simpleproto2;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import simpleproto2.GeneratedSimpleProto.Simple;
+
+/**
+ * A class that only uses a has method but otherwise ignores the value of a field.
+ */
+public class Simpleproto {
+
+  private static final byte[] WITHOUT_HASME_FIELD = new byte[]{2, 8, 42};
+  private static final byte[] WITH_HASME_FIELD = new byte[]{7, 8, 42, 21, 0, 0, -10, 66};
+
+  public static void main(String... args) throws IOException {
+    testHasWorks(WITHOUT_HASME_FIELD, false);
+    testHasWorks(WITH_HASME_FIELD, true);
+  }
+
+  private static void testHasWorks(byte[] msg, boolean expected) throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(msg);
+    Simple.Builder builder = Simple.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Simple simple = builder.build();
+    System.out.println("Expected " + expected + " and got " + simple.hasHasMe());
+  }
+}
diff --git a/src/test/examples/simpleproto2/keep-rules.txt b/src/test/examples/simpleproto2/keep-rules.txt
new file mode 100644
index 0000000..8f9c93e
--- /dev/null
+++ b/src/test/examples/simpleproto2/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class simpleproto2.Simpleproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/simpleproto2/simple.proto b/src/test/examples/simpleproto2/simple.proto
new file mode 100644
index 0000000..b9173e9
--- /dev/null
+++ b/src/test/examples/simpleproto2/simple.proto
@@ -0,0 +1,14 @@
+// Copyright (c) 2016, 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.
+syntax = "proto2";
+package simpleproto2;
+
+option java_outer_classname = "GeneratedSimpleProto";
+
+message Simple {
+  required int32 id = 1;
+  optional float hasMe = 2;
+  optional int32 other = 3;
+}
+
diff --git a/src/test/examples/simpleproto3/Simpleproto.java b/src/test/examples/simpleproto3/Simpleproto.java
new file mode 100644
index 0000000..2cdbae8
--- /dev/null
+++ b/src/test/examples/simpleproto3/Simpleproto.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 simpleproto3;
+
+import com.google.protobuf.UninitializedMessageException;
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import simpleproto3.GeneratedSimpleProto.Simple;
+
+public class Simpleproto {
+
+  private static final byte[] WITH_REQUIRED_FIELDS = new byte[]{7, 8, 42, 21, 0, 0, -10, 66};
+  private static final byte[] WITH_MISSING_FIELD = new byte[]{2, 8, 42};
+
+
+  public static void main(String... args) throws IOException {
+    readProtoWithAllReqFields();
+    partialBuildFails();
+    partialReadFails();
+  }
+
+  private static void partialBuildFails() {
+    Simple.Builder builder = Simple.newBuilder();
+    builder.setId(32);
+    try {
+      builder.build();
+    } catch (UninitializedMessageException e) {
+      System.out.println("got exception");
+    }
+  }
+
+  private static void partialReadFails() throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(WITH_MISSING_FIELD);
+    Simple.Builder builder = Simple.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    try {
+      builder.build();
+    } catch (UninitializedMessageException e) {
+      System.out.println("got exception");
+    }
+  }
+
+  private static void readProtoWithAllReqFields() throws IOException {
+    ByteArrayInputStream input = new ByteArrayInputStream(WITH_REQUIRED_FIELDS);
+    Simple.Builder builder = Simple.newBuilder();
+    builder.mergeDelimitedFrom(input);
+    Simple simple = builder.build();
+    ByteArrayOutputStream output = new ByteArrayOutputStream(WITH_REQUIRED_FIELDS.length);
+    simple.writeDelimitedTo(output);
+    System.out.println(isContained(WITH_REQUIRED_FIELDS, output.toByteArray()));
+  }
+
+  // After shaking, the serialized proto will no longer contain fields that are not referenced.
+  private static boolean isContained(byte[] fullBytes, byte[] reducedBytes) {
+    int j = 1;
+    for (int i = 1; i < fullBytes.length && j < reducedBytes.length; i++) {
+      if (fullBytes[i] == reducedBytes[j]) {
+        j++;
+      }
+    }
+    return j == reducedBytes.length;
+  }
+}
diff --git a/src/test/examples/simpleproto3/keep-rules.txt b/src/test/examples/simpleproto3/keep-rules.txt
new file mode 100644
index 0000000..186e9f8
--- /dev/null
+++ b/src/test/examples/simpleproto3/keep-rules.txt
@@ -0,0 +1,12 @@
+# 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.
+
+# Keep the application entry point. Get rid of everything that is not
+# reachable from there.
+-keep public class simpleproto3.Simpleproto {
+  public static void main(...);
+}
+
+# allow access modification to enable minification
+-allowaccessmodification
diff --git a/src/test/examples/simpleproto3/simple.proto b/src/test/examples/simpleproto3/simple.proto
new file mode 100644
index 0000000..87512d1
--- /dev/null
+++ b/src/test/examples/simpleproto3/simple.proto
@@ -0,0 +1,14 @@
+// Copyright (c) 2016, 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.
+syntax = "proto3";
+package simpleproto3;
+
+option java_outer_classname = "GeneratedSimpleProto";
+
+message Simple {
+  int32 id = 1;
+  float unusedRequired = 2;
+  bool other = 3;
+}
+
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
index afa437e..ca713fd 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10DeployJarVerificationTest.java
@@ -9,27 +9,22 @@
 import com.android.tools.r8.R8RunArtTestsTest.CompilerUnderTest;
 import com.android.tools.r8.shaking.ProguardRuleParserException;
 import com.android.tools.r8.utils.AndroidApp;
-import com.android.tools.r8.utils.InternalOptions;
 import java.io.IOException;
 import java.util.concurrent.ExecutionException;
 import org.junit.Test;
 
 public class R8GMSCoreV10DeployJarVerificationTest extends GMSCoreDeployJarVerificationTest {
 
-  private void configureDeterministic(InternalOptions options) {
-    options.removeSwitchMaps = false;
-  }
-
   @Test
   public void buildFromDeployJar()
       // TODO(tamaskenez): set hasReference = true when we have the noshrink file for V10
       throws ExecutionException, IOException, ProguardRuleParserException, CompilationException {
     AndroidApp app1 = buildFromDeployJar(
         CompilerUnderTest.R8, CompilationMode.RELEASE,
-        GMSCoreCompilationTestBase.GMSCORE_V10_DIR, false, this::configureDeterministic);
+        GMSCoreCompilationTestBase.GMSCORE_V10_DIR, false);
     AndroidApp app2 = buildFromDeployJar(
         CompilerUnderTest.R8, CompilationMode.RELEASE,
-        GMSCoreCompilationTestBase.GMSCORE_V10_DIR, false, this::configureDeterministic);
+        GMSCoreCompilationTestBase.GMSCORE_V10_DIR, false);
 
     // Verify that the result of the two compilations was the same.
     assertIdenticalApplications(app1, app2);
diff --git a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
index 2640f13..766de9d 100644
--- a/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
+++ b/src/test/java/com/android/tools/r8/internal/R8GMSCoreV10TreeShakeJarVerificationTest.java
@@ -20,7 +20,6 @@
 
   private void configureDeterministic(InternalOptions options) {
     options.skipMinification = true;
-    options.removeSwitchMaps = false;
   }
 
   @Test
diff --git a/src/test/java/com/android/tools/r8/rewrite/switchmaps/RewriteSwitchMapsTest.java b/src/test/java/com/android/tools/r8/rewrite/switchmaps/RewriteSwitchMapsTest.java
index 646a481..4e8881a 100644
--- a/src/test/java/com/android/tools/r8/rewrite/switchmaps/RewriteSwitchMapsTest.java
+++ b/src/test/java/com/android/tools/r8/rewrite/switchmaps/RewriteSwitchMapsTest.java
@@ -13,7 +13,6 @@
 import java.nio.file.Paths;
 import java.util.concurrent.ExecutionException;
 import org.junit.Assert;
-import org.junit.Ignore;
 import org.junit.Test;
 
 public class RewriteSwitchMapsTest extends TestBase {
@@ -24,8 +23,6 @@
       "-keep class switchmaps.Switches { public static void main(...); } " +
           "-dontobfuscate";
 
-  // TODO(sgjesse): Re-enable this when the switch-map extraction has been fixed.
-  @Ignore
   @Test
   public void checkSwitchMapsRemoved()
       throws IOException, ProguardRuleParserException, ExecutionException, CompilationException {
diff --git a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
index 3435577..99be74a 100644
--- a/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/TreeShakingTest.java
@@ -372,6 +372,80 @@
         subclass.method("double", "anotherMethod", ImmutableList.of("double")).isPresent());
   }
 
+  private static void simpleproto1UnusedFieldIsGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("simpleproto1.GeneratedSimpleProto$Simple");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertFalse(protoClass.field("boolean", "other_").isPresent());
+  }
+
+  private static void simpleproto2UnusedFieldsAreGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("simpleproto2.GeneratedSimpleProto$Simple");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertFalse(protoClass.field("int", "id_").isPresent());
+    Assert.assertFalse(protoClass.field("float", "hasMe_").isPresent());
+    Assert.assertFalse(protoClass.field("int", "other_").isPresent());
+  }
+
+  private static void nestedproto1UnusedFieldsAreGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("nestedproto1.GeneratedNestedProto$Outer");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertFalse(protoClass.field("int", "id_").isPresent());
+    Assert.assertTrue(
+        protoClass.field("nestedproto1.GeneratedNestedProto$NestedOne", "inner_").isPresent());
+    Assert.assertFalse(
+        protoClass.field("nestedproto1.GeneratedNestedProto$NestedTwo", "inner2_").isPresent());
+    ClassSubject nestedOne = inspector.clazz("nestedproto1.GeneratedNestedProto$NestedOne");
+    Assert.assertTrue(nestedOne.isPresent());
+    Assert.assertTrue(nestedOne.field("java.lang.String", "other_").isPresent());
+    Assert.assertFalse(nestedOne.field("int", "id_").isPresent());
+    Assert.assertFalse(inspector.clazz("nestedproto1.GeneratedNestedProto$NestedTwo").isPresent());
+  }
+
+  private static void nestedproto2UnusedFieldsAreGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("nestedproto2.GeneratedNestedProto$Outer");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertTrue(protoClass.field("int", "id_").isPresent());
+    Assert.assertFalse(
+        protoClass.field("nestedproto2.GeneratedNestedProto$NestedOne", "inner_").isPresent());
+    Assert.assertFalse(
+        protoClass.field("nestedproto2.GeneratedNestedProto$NestedTwo", "inner2_").isPresent());
+    Assert.assertFalse(inspector.clazz("nestedproto2.GeneratedNestedProto$NestedOne").isPresent());
+    Assert.assertFalse(inspector.clazz("nestedproto2.GeneratedNestedProto$NestedTwo").isPresent());
+  }
+
+
+  private static void enumprotoUnusedFieldsAreGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("enumproto.GeneratedEnumProto$Enum");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertFalse(protoClass.field("int", "id_").isPresent());
+    Assert.assertTrue(protoClass.field("int", "enum_").isPresent());
+    Assert.assertFalse(protoClass.field("int", "other_").isPresent());
+    ClassSubject protoThreeClass = inspector.clazz("enumproto.three.GeneratedEnumProto$EnumThree");
+    Assert.assertTrue(protoThreeClass.isPresent());
+    Assert.assertFalse(protoThreeClass.field("int", "id_").isPresent());
+    Assert.assertTrue(protoThreeClass.field("int", "enum_").isPresent());
+    Assert.assertFalse(protoThreeClass.field("int", "other_").isPresent());
+  }
+
+  private static void repeatedUnusedFieldsAreGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("repeatedproto.GeneratedRepeatedProto$Repeated");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertFalse(protoClass.field("int", "id_").isPresent());
+    Assert.assertTrue(
+        protoClass.field("com.google.protobuf.Internal$ProtobufList", "repeated_").isPresent());
+    Assert.assertFalse(
+        protoClass.field("com.google.protobuf.Internal$ProtobufList", "sub_").isPresent());
+    Assert.assertFalse(
+        protoClass.field("com.google.protobuf.Internal$BooleanList", "other_").isPresent());
+  }
+
+  private static void oneofprotoUnusedFieldsAreGone(DexInspector inspector) {
+    ClassSubject protoClass = inspector.clazz("oneofproto.GeneratedOneOfProto$Oneof");
+    Assert.assertTrue(protoClass.isPresent());
+    Assert.assertFalse(protoClass.field("int", "id_").isPresent());
+    Assert.assertFalse(protoClass.field("Object", "otherfields_").isPresent());
+  }
+
   private static List<String> names =
       ImmutableList.of("pqr", "vw$", "abc", "def", "stu", "ghi", "jkl", "ea", "xyz_", "mno");
 
@@ -557,7 +631,15 @@
             "assumevalues5",
             "annotationremoval",
             "memberrebinding2",
-            "memberrebinding3");
+            "memberrebinding3",
+            "simpleproto1",
+            "simpleproto2",
+            "simpleproto3",
+            "nestedproto1",
+            "nestedproto2",
+            "enumproto",
+            "repeatedproto",
+            "oneofproto");
 
     // Keys can be the name of the test or the name of the test followed by a colon and the name
     // of the keep file.
@@ -614,6 +696,20 @@
     inspections
         .put("annotationremoval:keep-rules-keep-innerannotation.txt",
             TreeShakingTest::annotationRemovalHasAllInnerClassAnnotations);
+    inspections
+        .put("simpleproto1:keep-rules.txt", TreeShakingTest::simpleproto1UnusedFieldIsGone);
+    inspections
+        .put("simpleproto2:keep-rules.txt", TreeShakingTest::simpleproto2UnusedFieldsAreGone);
+    inspections
+        .put("nestedproto1:keep-rules.txt", TreeShakingTest::nestedproto1UnusedFieldsAreGone);
+    inspections
+        .put("nestedproto2:keep-rules.txt", TreeShakingTest::nestedproto2UnusedFieldsAreGone);
+    inspections
+        .put("enumproto:keep-rules.txt", TreeShakingTest::enumprotoUnusedFieldsAreGone);
+    inspections
+        .put("repeatedproto:keep-rules.txt", TreeShakingTest::repeatedUnusedFieldsAreGone);
+    inspections
+        .put("oneofproto:keep-rules.txt", TreeShakingTest::oneofprotoUnusedFieldsAreGone);
 
     // Keys can be the name of the test or the name of the test followed by a colon and the name
     // of the keep file.
@@ -779,7 +875,7 @@
           Collections.singletonList(generated.toString()), mainClass, extraArtArgs, null);
       outputComparator.accept(output1, output2);
     } else {
-      ToolHelper.checkArtOutputIdentical(Collections.singletonList(originalDex),
+      String output = ToolHelper.checkArtOutputIdentical(Collections.singletonList(originalDex),
           Collections.singletonList(generated.toString()), mainClass,
           extraArtArgs, null);
     }