diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 9cf1550..1be5bda 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.6.36";
+  public static final String LABEL = "1.6.37";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexValue.java b/src/main/java/com/android/tools/r8/graph/DexValue.java
index f9b12d3..a120a5d 100644
--- a/src/main/java/com/android/tools/r8/graph/DexValue.java
+++ b/src/main/java/com/android/tools/r8/graph/DexValue.java
@@ -54,6 +54,22 @@
     return null;
   }
 
+  public DexValueType asDexValueType() {
+    return null;
+  }
+
+  public DexValueArray asDexValueArray() {
+    return null;
+  }
+
+  public boolean isDexValueType() {
+    return false;
+  }
+
+  public boolean isDexValueArray() {
+    return false;
+  }
+
   public static DexValue fromAsmBootstrapArgument(
       Object value, JarApplicationReader application, DexType clazz) {
     if (value instanceof Integer) {
@@ -805,6 +821,16 @@
         DexMethod method, int instructionOffset) {
       value.collectIndexedItems(indexedItems, method, instructionOffset);
     }
+
+    @Override
+    public DexValueType asDexValueType() {
+      return this;
+    }
+
+    @Override
+    public boolean isDexValueType() {
+      return true;
+    }
   }
 
   static public class DexValueField extends NestedDexValue<DexField> {
@@ -949,6 +975,16 @@
     public String toString() {
       return "Array " + Arrays.toString(values);
     }
+
+    @Override
+    public boolean isDexValueArray() {
+      return true;
+    }
+
+    @Override
+    public DexValueArray asDexValueArray() {
+      return this;
+    }
   }
 
   static public class DexValueAnnotation extends DexValue {
diff --git a/src/main/java/com/android/tools/r8/graph/ParameterAnnotationsList.java b/src/main/java/com/android/tools/r8/graph/ParameterAnnotationsList.java
index 68c7da1..6ff5c75 100644
--- a/src/main/java/com/android/tools/r8/graph/ParameterAnnotationsList.java
+++ b/src/main/java/com/android/tools/r8/graph/ParameterAnnotationsList.java
@@ -5,8 +5,10 @@
 
 import com.android.tools.r8.dex.IndexedItemCollection;
 import com.android.tools.r8.dex.MixedSectionCollection;
+import com.android.tools.r8.utils.ArrayUtils;
 import java.util.Arrays;
 import java.util.function.Consumer;
+import java.util.function.Function;
 import java.util.function.Predicate;
 
 /**
@@ -193,4 +195,12 @@
     }
     return new ParameterAnnotationsList(filtered, missingParameterAnnotations);
   }
+
+  public ParameterAnnotationsList rewrite(Function<DexAnnotationSet, DexAnnotationSet> mapper) {
+    DexAnnotationSet[] rewritten = ArrayUtils.map(DexAnnotationSet[].class, values, mapper);
+    if (rewritten != values) {
+      return new ParameterAnnotationsList(rewritten, missingParameterAnnotations);
+    }
+    return this;
+  }
 }
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationFixer.java b/src/main/java/com/android/tools/r8/shaking/AnnotationFixer.java
new file mode 100644
index 0000000..356f609
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationFixer.java
@@ -0,0 +1,83 @@
+// Copyright (c) 2019, 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;
+
+import com.android.tools.r8.graph.DexAnnotation;
+import com.android.tools.r8.graph.DexAnnotationElement;
+import com.android.tools.r8.graph.DexEncodedAnnotation;
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexValue;
+import com.android.tools.r8.graph.DexValue.DexValueArray;
+import com.android.tools.r8.graph.DexValue.DexValueType;
+import com.android.tools.r8.graph.GraphLense;
+import com.android.tools.r8.utils.ArrayUtils;
+
+public class AnnotationFixer {
+
+  private final GraphLense lense;
+
+  public AnnotationFixer(GraphLense lense) {
+    this.lense = lense;
+  }
+
+  public void run(Iterable<DexProgramClass> classes) {
+    for (DexProgramClass clazz : classes) {
+      clazz.annotations = clazz.annotations.rewrite(this::rewriteAnnotation);
+      clazz.forEachMethod(this::processMethod);
+      clazz.forEachField(this::processField);
+    }
+  }
+
+  private void processMethod(DexEncodedMethod method) {
+    method.annotations = method.annotations.rewrite(this::rewriteAnnotation);
+    method.parameterAnnotationsList =
+        method.parameterAnnotationsList.rewrite(
+            dexAnnotationSet -> dexAnnotationSet.rewrite(this::rewriteAnnotation));
+  }
+
+  private void processField(DexEncodedField field) {
+    field.annotations = field.annotations.rewrite(this::rewriteAnnotation);
+  }
+
+  private DexAnnotation rewriteAnnotation(DexAnnotation original) {
+    return original.rewrite(this::rewriteEncodedAnnotation);
+  }
+
+  private DexEncodedAnnotation rewriteEncodedAnnotation(DexEncodedAnnotation original) {
+    DexEncodedAnnotation rewritten =
+        original.rewrite(lense::lookupType, this::rewriteAnnotationElement);
+    assert rewritten != null;
+    return rewritten;
+  }
+
+  private DexAnnotationElement rewriteAnnotationElement(DexAnnotationElement original) {
+    DexValue rewrittenValue = rewriteValue(original.value);
+    if (rewrittenValue != original.value) {
+      return new DexAnnotationElement(original.name, rewrittenValue);
+    }
+    return original;
+  }
+
+  private DexValue rewriteValue(DexValue value) {
+    if (value.isDexValueType()) {
+      DexType originalType = value.asDexValueType().value;
+      DexType rewrittenType = lense.lookupType(originalType);
+      if (rewrittenType != originalType) {
+        return new DexValueType(rewrittenType);
+      }
+    } else if (value.isDexValueArray()) {
+      DexValue[] originalValues = value.asDexValueArray().getValues();
+      DexValue[] rewrittenValues =
+          ArrayUtils.map(DexValue[].class, originalValues, this::rewriteValue);
+      if (rewrittenValues != originalValues) {
+        return new DexValueArray(rewrittenValues);
+      }
+    }
+    return value;
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
index cadd59c..2cbe484 100644
--- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
+++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java
@@ -108,11 +108,6 @@
 
   private boolean isAnnotationTypeLive(DexAnnotation annotation) {
     DexType annotationType = annotation.annotation.type.toBaseType(appView.dexItemFactory());
-    DexClass definition = appView.definitionFor(annotationType);
-    // TODO(b/73102187): How to handle annotations without definition.
-    if (appView.options().isShrinking() && definition == null) {
-      return false;
-    }
     return appView.appInfo().isNonProgramTypeOrLiveProgramType(annotationType);
   }
 
@@ -276,7 +271,8 @@
   private DexAnnotationElement rewriteAnnotationElement(
       DexType annotationType, DexAnnotationElement original) {
     DexClass definition = appView.definitionFor(annotationType);
-    // TODO(b/73102187): How to handle annotations without definition.
+    // We cannot strip annotations where we cannot look up the definition, because this will break
+    // apps that rely on the annotation to exist. See b/134766810 for more information.
     if (definition == null) {
       return original;
     }
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index cd77544..ef9a378 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -1454,7 +1454,9 @@
       for (SynthesizedBridgeCode synthesizedBridge : synthesizedBridges) {
         synthesizedBridge.updateMethodSignatures(this::fixupMethod);
       }
-      return lensBuilder.build(appView, mergedClasses);
+      GraphLense graphLense = lensBuilder.build(appView, mergedClasses);
+      new AnnotationFixer(graphLense).run(appView.appInfo().classes());
+      return graphLense;
     }
 
     private void fixupMethods(List<DexEncodedMethod> methods, MethodSetter setter) {
diff --git a/src/test/java/com/android/tools/r8/shaking/annotations/LibraryAndMissingAnnotationsTest.java b/src/test/java/com/android/tools/r8/shaking/annotations/LibraryAndMissingAnnotationsTest.java
new file mode 100644
index 0000000..4e6adad
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/annotations/LibraryAndMissingAnnotationsTest.java
@@ -0,0 +1,181 @@
+// Copyright (c) 2019, 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.annotations;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assume.assumeTrue;
+
+import com.android.tools.r8.BaseCompilerCommand;
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestCompileResult;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestRunResult;
+import com.android.tools.r8.TestShrinkerBuilder;
+import com.android.tools.r8.utils.BooleanUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.io.IOException;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.nio.file.Path;
+import java.util.List;
+import java.util.function.Function;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class LibraryAndMissingAnnotationsTest extends TestBase {
+
+  private final TestParameters parameters;
+  private final boolean includeOnLibraryPath;
+
+  @Parameters(name = "{0}, includeOnLibraryPath: {1}")
+  public static List<Object[]> data() {
+    return buildParameters(
+        getTestParameters().withAllRuntimesAndApiLevels().build(), BooleanUtils.values());
+  }
+
+  private static Function<TestParameters, Path> compilationResults =
+      memoizeFunction(LibraryAndMissingAnnotationsTest::compileLibraryAnnotationToRuntime);
+
+  private static Path compileLibraryAnnotationToRuntime(TestParameters parameters)
+      throws CompilationFailedException, IOException {
+    return testForR8(getStaticTemp(), parameters.getBackend())
+        .addProgramClasses(LibraryAnnotation.class)
+        .addKeepClassAndMembersRulesWithAllowObfuscation(LibraryAnnotation.class)
+        .setMinApi(parameters.getApiLevel())
+        .compile()
+        .writeToZip();
+  }
+
+  public LibraryAndMissingAnnotationsTest(TestParameters parameters, boolean includeOnLibraryPath) {
+    this.parameters = parameters;
+    this.includeOnLibraryPath = includeOnLibraryPath;
+  }
+
+  @Test
+  public void testMainWithUseR8() throws Exception {
+    runTest(testForR8(parameters.getBackend()), MainWithUse.class);
+  }
+
+  @Test
+  public void testMainWithUseR8Compat() throws Exception {
+    runTest(testForR8Compat(parameters.getBackend()), MainWithUse.class);
+  }
+
+  @Test
+  public void testMainWithUseProguard() throws Exception {
+    assumeTrue(parameters.isCfRuntime());
+    runTest(testForProguard(), MainWithUse.class);
+  }
+
+  @Test
+  public void testMainWithoutUseR8() throws Exception {
+    runTest(testForR8(parameters.getBackend()), MainWithoutUse.class);
+  }
+
+  @Test
+  public void testMainWithoutUseR8Compat() throws Exception {
+    runTest(testForR8Compat(parameters.getBackend()), MainWithoutUse.class);
+  }
+
+  @Test
+  public void testMainWithoutUseProguard() throws Exception {
+    assumeTrue(parameters.isCfRuntime());
+    runTest(testForProguard(), MainWithoutUse.class);
+  }
+
+  private <
+          C extends BaseCompilerCommand,
+          B extends BaseCompilerCommand.Builder<C, B>,
+          CR extends TestCompileResult<CR, RR>,
+          RR extends TestRunResult<RR>,
+          T extends TestShrinkerBuilder<C, B, CR, RR, T>>
+      void runTest(TestShrinkerBuilder<C, B, CR, RR, T> builder, Class<?> mainClass)
+          throws Exception {
+    T t =
+        builder
+            .addProgramClasses(Foo.class, mainClass)
+            .addKeepAttributes("*Annotation*")
+            .addLibraryFiles(runtimeJar(parameters))
+            .addKeepClassAndMembersRules(Foo.class)
+            .addKeepRules("-dontwarn " + LibraryAndMissingAnnotationsTest.class.getTypeName())
+            .addKeepMainRule(mainClass)
+            .setMinApi(parameters.getApiLevel());
+    if (includeOnLibraryPath) {
+      t.addLibraryClasses(LibraryAnnotation.class);
+    } else {
+      t.addKeepRules("-dontwarn " + LibraryAnnotation.class.getTypeName());
+    }
+    t.compile()
+        .addRunClasspathFiles(compilationResults.apply(parameters))
+        .run(parameters.getRuntime(), mainClass)
+        .inspect(
+            inspector -> {
+              ClassSubject clazz = inspector.clazz(Foo.class);
+              assertThat(clazz, isPresent());
+              assertThat(clazz.annotation(LibraryAnnotation.class.getTypeName()), isPresent());
+              MethodSubject foo = clazz.uniqueMethodWithName("foo");
+              assertThat(foo, isPresent());
+              assertThat(foo.annotation(LibraryAnnotation.class.getTypeName()), isPresent());
+              assertFalse(foo.getMethod().parameterAnnotationsList.isEmpty());
+              assertEquals(
+                  LibraryAnnotation.class.getTypeName(),
+                  foo.getMethod()
+                      .parameterAnnotationsList
+                      .get(0)
+                      .annotations[0]
+                      .getAnnotationType()
+                      .toSourceString());
+              assertThat(
+                  clazz
+                      .uniqueFieldWithName("bar")
+                      .annotation(LibraryAnnotation.class.getTypeName()),
+                  isPresent());
+            })
+        .assertSuccessWithOutputLines("Hello World!");
+  }
+
+  @Test
+  public void testMainWithoutUse() {}
+
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface LibraryAnnotation {}
+
+  @LibraryAnnotation
+  public static class Foo {
+
+    @LibraryAnnotation public String bar = "Hello World!";
+
+    @LibraryAnnotation
+    public void foo(@LibraryAnnotation String arg) {
+      System.out.println(arg);
+    }
+  }
+
+  public static class MainWithoutUse {
+
+    public static void main(String[] args) {
+      Foo foo = new Foo();
+      foo.foo(foo.bar);
+    }
+  }
+
+  public static class MainWithUse {
+    public static void main(String[] args) {
+      if (args.length > 0 && args[0].equals(LibraryAnnotation.class.getTypeName())) {
+        System.out.print("This will never be printed");
+      }
+      Foo foo = new Foo();
+      foo.foo(foo.bar);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/annotations/PrunedOrMergedAnnotationTest.java b/src/test/java/com/android/tools/r8/shaking/annotations/PrunedOrMergedAnnotationTest.java
new file mode 100644
index 0000000..45b29f7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/annotations/PrunedOrMergedAnnotationTest.java
@@ -0,0 +1,119 @@
+// Copyright (c) 2018, 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.annotations;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static junit.framework.TestCase.assertEquals;
+import static junit.framework.TestCase.assertTrue;
+import static org.hamcrest.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.NeverClassInline;
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.graph.DexAnnotationSet;
+import com.android.tools.r8.graph.DexEncodedAnnotation;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.DexValue;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class PrunedOrMergedAnnotationTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public PrunedOrMergedAnnotationTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testRewritingInFactory()
+      throws IOException, CompilationFailedException, ExecutionException {
+    testForR8(parameters.getBackend())
+        .addInnerClasses(PrunedOrMergedAnnotationTest.class)
+        .addKeepMainRule(Main.class)
+        .addKeepAttributes("*Annotation*")
+        .addKeepClassAndMembersRules(Factory.class)
+        .enableInliningAnnotations()
+        .enableClassInliningAnnotations()
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), Main.class)
+        .assertSuccessWithOutputLines("Hello", "World!")
+        .inspect(
+            inspector -> {
+              assertThat(inspector.clazz(A.class), not(isPresent()));
+              DexType mergedType = inspector.clazz(B.class).getDexClass().type;
+              ClassSubject classC = inspector.clazz(C.class);
+              assertThat(classC, isPresent());
+              DexEncodedAnnotation annotation =
+                  classC.annotation(Factory.class.getTypeName()).getAnnotation();
+              assertTrue(valueIsDexType(mergedType, annotation.elements[0].value));
+              assertTrue(
+                  Arrays.stream(annotation.elements[1].value.asDexValueArray().getValues())
+                      .allMatch(value -> valueIsDexType(mergedType, value)));
+              // Check that method parameter annotations are rewritten as well.
+              DexEncodedMethod method = inspector.clazz(Main.class).mainMethod().getMethod();
+              DexAnnotationSet annotationSet = method.parameterAnnotationsList.get(0);
+              DexEncodedAnnotation parameterAnnotation = annotationSet.annotations[0].annotation;
+              assertTrue(valueIsDexType(mergedType, parameterAnnotation.elements[0].value));
+            });
+  }
+
+  private boolean valueIsDexType(DexType type, DexValue value) {
+    assertTrue(value.isDexValueType());
+    assertEquals(type, value.asDexValueType().value);
+    return true;
+  }
+
+  public @interface Factory {
+
+    Class<?> extending() default Object.class;
+
+    Class<?>[] other() default Object[].class;
+  }
+
+  public static class A {}
+
+  @NeverClassInline
+  public static class B extends A {
+    @NeverInline
+    public void world() {
+      System.out.println("World!");
+    }
+  }
+
+  @Factory(
+      extending = A.class,
+      other = {A.class, B.class})
+  public static class C {
+    @NeverInline
+    public static void hello() {
+      System.out.println("Hello");
+    }
+  }
+
+  public static class Main {
+
+    public static void main(@Factory(extending = A.class) String[] args) {
+      C.hello();
+      new B().world();
+    }
+  }
+}