diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 261ead8..38f3cb0 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.39";
+  public static final String LABEL = "1.6.40";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
index e7d8ab2..04251a6 100644
--- a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
+++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java
@@ -46,6 +46,10 @@
     return THE_EMPTY_ANNOTATIONS_SET;
   }
 
+  public int size() {
+    return annotations.length;
+  }
+
   @Override
   public int computeHashCode() {
     return Arrays.hashCode(annotations);
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index de9aab7..9676a05 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -537,6 +537,9 @@
     if (liveTypes.contains(type)) {
       return true;
     }
+    if (prunedTypes.contains(type)) {
+      return false;
+    }
     DexClass clazz = definitionFor(type);
     return clazz == null || !clazz.isProgramClass();
   }
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 8b2e770..b38471a 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -2613,11 +2613,12 @@
       if (encodedMethod == null) {
         return;
       }
+      KeepReason reason = KeepReason.reflectiveUseIn(method);
       if (encodedMethod.accessFlags.isStatic() || encodedMethod.accessFlags.isConstructor()) {
-        markDirectStaticOrConstructorMethodAsLive(
-            clazz, encodedMethod, KeepReason.reflectiveUseIn(method));
+        markMethodAsTargeted(clazz, encodedMethod, reason);
+        markDirectStaticOrConstructorMethodAsLive(clazz, encodedMethod, reason);
       } else {
-        markVirtualMethodAsLive(clazz, encodedMethod, KeepReason.reflectiveUseIn(method));
+        markVirtualMethodAsLive(clazz, encodedMethod, reason);
       }
     }
   }
diff --git a/src/test/java/com/android/tools/r8/shaking/annotations/ProgramAnnotationRemovalTest.java b/src/test/java/com/android/tools/r8/shaking/annotations/ProgramAnnotationRemovalTest.java
new file mode 100644
index 0000000..0cf779d
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/annotations/ProgramAnnotationRemovalTest.java
@@ -0,0 +1,118 @@
+// 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.CoreMatchers.not;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.R8TestRunResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.lang.annotation.Annotation;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+import java.lang.reflect.Method;
+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 ProgramAnnotationRemovalTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimesAndApiLevels().build();
+  }
+
+  public ProgramAnnotationRemovalTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test() throws Exception {
+    R8TestRunResult result =
+        testForR8(parameters.getBackend())
+            .addInnerClasses(ProgramAnnotationRemovalTest.class)
+            .addKeepMainRule(TestClass.class)
+            .addKeepAttributes("RuntimeVisibleAnnotations")
+            .setMinApi(parameters.getApiLevel())
+            .compile()
+            .run(parameters.getRuntime(), TestClass.class);
+
+    CodeInspector inspector = result.inspector();
+
+    ClassSubject liveAnnotationClassSubject = inspector.clazz(LiveProgramAnnotation.class);
+    assertThat(liveAnnotationClassSubject, isPresent());
+
+    ClassSubject deadAnnotationClassSubject = inspector.clazz(DeadProgramAnnotation.class);
+    assertThat(deadAnnotationClassSubject, not(isPresent()));
+
+    ClassSubject testClassSubject = inspector.clazz(TestClass.class);
+    assertThat(testClassSubject, isPresent());
+
+    MethodSubject methodWithLiveProgramAnnotationSubject =
+        testClassSubject.uniqueMethodWithName("methodWithLiveProgramAnnotation");
+    assertThat(methodWithLiveProgramAnnotationSubject, isPresent());
+    assertEquals(1, methodWithLiveProgramAnnotationSubject.getMethod().annotations.size());
+
+    MethodSubject methodWithDeadProgramAnnotationSubject =
+        testClassSubject.uniqueMethodWithName("methodWithDeadProgramAnnotation");
+    assertThat(methodWithDeadProgramAnnotationSubject, isPresent());
+    assertEquals(0, methodWithDeadProgramAnnotationSubject.getMethod().annotations.size());
+
+    result.assertSuccessWithOutputLines("@" + liveAnnotationClassSubject.getFinalName() + "()");
+  }
+
+  static class TestClass {
+
+    public static void main(String[] args) throws Exception {
+      methodWithLiveProgramAnnotation();
+      methodWithDeadProgramAnnotation();
+
+      // Do something with LiveProgramAnnotation to ensure it becomes live.
+      if (System.currentTimeMillis() <= 0) {
+        System.out.println(LiveProgramAnnotation.class);
+      }
+    }
+
+    @NeverInline
+    @LiveProgramAnnotation
+    static void methodWithLiveProgramAnnotation() throws Exception {
+      Method method = TestClass.class.getDeclaredMethod("methodWithLiveProgramAnnotation");
+      for (Annotation annotation : method.getDeclaredAnnotations()) {
+        System.out.println(annotation);
+      }
+    }
+
+    @NeverInline
+    @DeadProgramAnnotation
+    static void methodWithDeadProgramAnnotation() throws Exception {
+      Method method = TestClass.class.getDeclaredMethod("methodWithDeadProgramAnnotation");
+      for (Annotation annotation : method.getDeclaredAnnotations()) {
+        System.out.println(annotation);
+      }
+    }
+  }
+
+  @Target(ElementType.METHOD)
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface LiveProgramAnnotation {}
+
+  @Target(ElementType.METHOD)
+  @Retention(RetentionPolicy.RUNTIME)
+  @interface DeadProgramAnnotation {}
+}