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 8194593..e7c8333 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
@@ -1993,14 +1993,32 @@
     if (!appView.enableWholeProgramOptimizations()) {
       return;
     }
-
+    // If we can remove a CheckCast it is due to us having at least as much information about the
+    // type as the CheckCast gives. We then need to propagate that information to the users of
+    // the CheckCast to ensure further optimizations and removals of CheckCast:
+    //
+    //    : 1: NewArrayEmpty        v2 <- v1(1) java.lang.String[]  <-- v2 = String[]
+    // ...
+    //    : 2: CheckCast            v5 <- v2; java.lang.Object[]    <-- v5 = Object[]
+    // ...
+    //    : 3: ArrayGet             v7 <- v5, v6(0)                 <-- v7 = Object
+    //    : 4: CheckCast            v8 <- v7; java.lang.String      <-- v8 = String
+    // ...
+    //
+    // When looking at line 2 we can conclude that the CheckCast is trivial because v2 is String[]
+    // and remove it. However, v7 is still only known to be Object and we cannot remove the
+    // CheckCast at line 4 unless we update v7 with the most precise information by narrowing the
+    // affected values of v5. We therefore have to run the type analysis after each CheckCast
+    // removal.
+    TypeAnalysis typeAnalysis = new TypeAnalysis(appView, code.method);
+    Set<Value> affectedValues = Sets.newIdentityHashSet();
     InstructionIterator it = code.instructionIterator();
     boolean needToRemoveTrivialPhis = false;
     while (it.hasNext()) {
       Instruction current = it.next();
       if (current.isCheckCast()) {
         boolean hasPhiUsers = current.outValue().numberOfPhiUsers() != 0;
-        if (removeCheckCastInstructionIfTrivial(current.asCheckCast(), it, code)) {
+        if (removeCheckCastInstructionIfTrivial(current.asCheckCast(), it, code, affectedValues)) {
           needToRemoveTrivialPhis |= hasPhiUsers;
         }
       } else if (current.isInstanceOf()) {
@@ -2009,6 +2027,10 @@
           needToRemoveTrivialPhis |= hasPhiUsers;
         }
       }
+      if (!affectedValues.isEmpty()) {
+        typeAnalysis.narrowing(affectedValues);
+        affectedValues.clear();
+      }
     }
     // ... v1
     // ...
@@ -2024,7 +2046,7 @@
 
   // Returns true if the given check-cast instruction was removed.
   private boolean removeCheckCastInstructionIfTrivial(
-      CheckCast checkCast, InstructionIterator it, IRCode code) {
+      CheckCast checkCast, InstructionIterator it, IRCode code, Set<Value> affectedValues) {
     Value inValue = checkCast.object();
     Value outValue = checkCast.outValue();
     DexType castType = checkCast.getType();
@@ -2076,6 +2098,7 @@
       //   A a = ...
       //   B b = (B) a;
       assert inTypeLattice.lessThanOrEqual(outTypeLattice, appView);
+      affectedValues.addAll(outValue.affectedValues());
       removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
       return true;
     }
@@ -2167,13 +2190,14 @@
       }
     }
     if (result != InstanceOfResult.UNKNOWN) {
-      it.replaceCurrentInstruction(
+      ConstNumber newInstruction =
           new ConstNumber(
               new Value(
                   code.valueNumberGenerator.next(),
                   TypeLatticeElement.INT,
                   instanceOf.outValue().getLocalInfo()),
-              result == InstanceOfResult.TRUE ? 1 : 0));
+              result == InstanceOfResult.TRUE ? 1 : 0);
+      it.replaceCurrentInstruction(newInstruction);
       return true;
     }
     return false;
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java
index 83890de..aa58df7 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/checkcast/CheckCastRemovalTest.java
@@ -218,7 +218,6 @@
   }
 
   @Test
-  @Ignore("b/133739171")
   public void bothUpAndDowncast() throws Exception {
     JasminBuilder builder = new JasminBuilder();
     ClassBuilder classBuilder = builder.addClass(CLASS_NAME);