Index: lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
+++ lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
@@ -521,6 +521,8 @@
       // low bits known zero.
       if (ShiftAmt)
         Known.Zero.setLowBits(ShiftAmt);
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
@@ -544,6 +546,8 @@
       Known.One.lshrInPlace(ShiftAmt);
       if (ShiftAmt)
         Known.Zero.setHighBits(ShiftAmt);  // high bits known zero.
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
@@ -604,6 +608,8 @@
       } else if (Known.One[BitWidth-ShiftAmt-1]) { // New bits are known one.
         Known.One |= HighBits;
       }
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
@@ -625,6 +631,8 @@
       // Propagate zero bits from the input.
       Known.Zero.setHighBits(std::min(
           BitWidth, LHSKnown.Zero.countLeadingOnes() + RHSTrailingZeros));
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
@@ -683,7 +691,8 @@
     Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
     break;
   }
-  case Instruction::Call:
+  case Instruction::Call: {
+    bool KnownBitsComputed = false;
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
       switch (II->getIntrinsicID()) {
       default: break;
@@ -715,8 +724,6 @@
           NewVal->takeName(I);
           return InsertNewInstWith(NewVal, *I);
         }
-
-        // TODO: Could compute known zero/one bits based on the input.
         break;
       }
       case Intrinsic::fshr:
@@ -741,6 +748,7 @@
                      RHSKnown.Zero.lshr(BitWidth - ShiftAmt);
         Known.One = LHSKnown.One.shl(ShiftAmt) |
                     RHSKnown.One.lshr(BitWidth - ShiftAmt);
+        KnownBitsComputed = true;
         break;
       }
       case Intrinsic::x86_mmx_pmovmskb:
@@ -769,16 +777,21 @@
 
         // We know that the upper bits are set to zero.
         Known.Zero.setBitsFrom(ArgWidth);
-        return nullptr;
+        KnownBitsComputed = true;
+        break;
       }
       case Intrinsic::x86_sse42_crc32_64_64:
         Known.Zero.setBitsFrom(32);
-        return nullptr;
+        KnownBitsComputed = true;
+        break;
       }
     }
-    computeKnownBits(V, Known, Depth, CxtI);
+
+    if (!KnownBitsComputed)
+      computeKnownBits(V, Known, Depth, CxtI);
     break;
   }
+  }
 
   // If the client is only demanding bits that we know, return the known
   // constant.
Index: test/Transforms/InstCombine/all-bits-shift.ll
===================================================================
--- test/Transforms/InstCombine/all-bits-shift.ll
+++ test/Transforms/InstCombine/all-bits-shift.ll
@@ -13,33 +13,11 @@
 ;   ((2072 >> (L == 0)) >> 7) & 1
 ; is always zero.
 define signext i32 @main() #1 {
-; EXPENSIVE-OFF-LABEL: @main(
-; EXPENSIVE-OFF-NEXT:  entry:
-; EXPENSIVE-OFF-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
-; EXPENSIVE-OFF-NEXT:    [[TMP1:%.*]] = load i32, i32* @a, align 4
-; EXPENSIVE-OFF-NEXT:    [[LNOT:%.*]] = icmp eq i32 [[TMP1]], 0
-; EXPENSIVE-OFF-NEXT:    [[LNOT_EXT:%.*]] = zext i1 [[LNOT]] to i32
-; EXPENSIVE-OFF-NEXT:    [[SHR_I:%.*]] = lshr i32 2072, [[LNOT_EXT]]
-; EXPENSIVE-OFF-NEXT:    [[CALL_LOBIT:%.*]] = lshr i32 [[SHR_I]], 7
-; EXPENSIVE-OFF-NEXT:    [[TMP2:%.*]] = and i32 [[CALL_LOBIT]], 1
-; EXPENSIVE-OFF-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    [[OR:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; EXPENSIVE-OFF-NEXT:    store i32 [[OR]], i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
-; EXPENSIVE-OFF-NEXT:    [[LNOT_1:%.*]] = icmp eq i32 [[TMP4]], 0
-; EXPENSIVE-OFF-NEXT:    [[LNOT_EXT_1:%.*]] = zext i1 [[LNOT_1]] to i32
-; EXPENSIVE-OFF-NEXT:    [[SHR_I_1:%.*]] = lshr i32 2072, [[LNOT_EXT_1]]
-; EXPENSIVE-OFF-NEXT:    [[CALL_LOBIT_1:%.*]] = lshr i32 [[SHR_I_1]], 7
-; EXPENSIVE-OFF-NEXT:    [[TMP5:%.*]] = and i32 [[CALL_LOBIT_1]], 1
-; EXPENSIVE-OFF-NEXT:    [[OR_1:%.*]] = or i32 [[TMP5]], [[TMP3]]
-; EXPENSIVE-OFF-NEXT:    store i32 [[OR_1]], i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    ret i32 [[OR_1]]
-;
-; EXPENSIVE-ON-LABEL: @main(
-; EXPENSIVE-ON-NEXT:  entry:
-; EXPENSIVE-ON-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
-; EXPENSIVE-ON-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
-; EXPENSIVE-ON-NEXT:    ret i32 [[TMP1]]
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
 entry:
   %0 = load i32*, i32** @b, align 8
Index: test/Transforms/InstCombine/known-bits.ll
===================================================================
--- test/Transforms/InstCombine/known-bits.ll
+++ test/Transforms/InstCombine/known-bits.ll
@@ -3,16 +3,9 @@
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-ON
 
 define void @test_shl(i1 %x) {
-; EXPENSIVE-OFF-LABEL: @test_shl(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = zext i1 [[X:%.*]] to i8
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = shl i8 64, [[Y]]
-; EXPENSIVE-OFF-NEXT:    [[A:%.*]] = and i8 [[Z]], 1
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[A]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_shl(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_shl(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = zext i1 %x to i8
   %z = shl i8 64, %y
@@ -22,16 +15,9 @@
 }
 
 define void @test_lshr(i1 %x) {
-; EXPENSIVE-OFF-LABEL: @test_lshr(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = zext i1 [[X:%.*]] to i8
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = lshr i8 64, [[Y]]
-; EXPENSIVE-OFF-NEXT:    [[A:%.*]] = and i8 [[Z]], 1
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[A]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_lshr(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_lshr(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = zext i1 %x to i8
   %z = lshr i8 64, %y
@@ -41,16 +27,9 @@
 }
 
 define void @test_ashr(i1 %x) {
-; EXPENSIVE-OFF-LABEL: @test_ashr(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = zext i1 [[X:%.*]] to i8
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = ashr i8 -16, [[Y]]
-; EXPENSIVE-OFF-NEXT:    [[A:%.*]] = and i8 [[Z]], 3
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[A]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_ashr(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_ashr(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = zext i1 %x to i8
   %z = ashr i8 -16, %y
@@ -60,15 +39,9 @@
 }
 
 define void @test_udiv(i8 %x) {
-; EXPENSIVE-OFF-LABEL: @test_udiv(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = udiv i8 10, [[X:%.*]]
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = and i8 [[Y]], 64
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[Z]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_udiv(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_udiv(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = udiv i8 10, %x
   %z = and i8 %y, 64