Index: lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
+++ lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
@@ -470,13 +470,14 @@
       // Unsigned shift right.
       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
 
+      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
+        return I;
+
       // If the shift is exact, then it does demand the low bits (and knows that
-      // they are zero).
+      // they are zero). Do this after we simplify the operand.
       if (cast<LShrOperator>(I)->isExact())
         DemandedMaskIn.setLowBits(ShiftAmt);
 
-      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
-        return I;
       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
       Known.Zero.lshrInPlace(ShiftAmt);
       Known.One.lshrInPlace(ShiftAmt);
@@ -513,14 +514,14 @@
       if (DemandedMask.countLeadingZeros() <= ShiftAmt)
         DemandedMaskIn.setSignBit();
 
+      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
+        return I;
+
       // If the shift is exact, then it does demand the low bits (and knows that
-      // they are zero).
+      // they are zero). Do this after we simplify the operand.
       if (cast<AShrOperator>(I)->isExact())
         DemandedMaskIn.setLowBits(ShiftAmt);
 
-      if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
-        return I;
-
       unsigned SignBits = ComputeNumSignBits(I->getOperand(0), Depth + 1, CxtI);
 
       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
@@ -671,6 +672,19 @@
     }
     computeKnownBits(V, Known, Depth, CxtI);
     break;
+  case Instruction::PHI: {
+    APInt IKnownZero = APInt::getAllOnesValue(BitWidth);
+    APInt IKnownOne = APInt::getAllOnesValue(BitWidth);
+    for (unsigned i = 0; i != cast<PHINode>(I)->getNumIncomingValues(); ++i) {
+      KnownBits PhiOperandKnown(BitWidth);
+      SimplifyDemandedBits(I, i, DemandedMask, PhiOperandKnown, Depth + 1);
+      IKnownZero = IKnownZero & PhiOperandKnown.Zero;
+      IKnownOne = IKnownOne & PhiOperandKnown.One;
+    }
+    Known.Zero = std::move(IKnownZero);
+    Known.One = std::move(IKnownOne);
+    break;
+  }
   }
 
   // If the client is only demanding bits that we know, return the known
Index: test/Transforms/InstCombine/simplify-demanded-bits-across-phi.ll
===================================================================
--- test/Transforms/InstCombine/simplify-demanded-bits-across-phi.ll
+++ test/Transforms/InstCombine/simplify-demanded-bits-across-phi.ll
@@ -0,0 +1,43 @@
+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+@bar = local_unnamed_addr global i32 0, align 4
+
+define void @foo(i64, i32) {
+  switch i32 %1, label %10 [
+    i32 1, label %3
+    i32 2, label %6
+  ]
+
+; <label>:3:
+  %4 = mul i64 %0, -4132994306676758123
+  %5 = and i64 %4, -4294967296
+  br label %10
+; CHECK: ; <label>:[[L1:[0-9]+]]:
+; CHECK: %[[V1:[0-9]+]] = mul i64 %0, -4132994306676758123
+; CHECK-NOT: %{{[0-9]+}} = and i64
+
+
+; <label>:6:
+  %7 = mul i64 %0, -4132994306676758123
+  %8 = add i64 %7, -8265988613353516246
+  %9 = and i64 %8, -4294967296
+; CHECK: ; <label>:[[L2:[0-9]+]]:
+; CHECK: %[[V2:[0-9]+]] = mul i64 %0, -4132994306676758123
+; CHECK: %[[V3:[0-9]+]] = add i64 %[[V2]], 87027708318506
+; CHECK-NOT: %{{[0-9]+}} = and i64
+  br label %10
+
+; <label>:10:
+  %11 = phi i64 [ %9, %6 ], [ %5, %3 ], [ 0, %2 ]
+; ssCHECK: %{{[0-9]+}} = phi i64 [ %[[V3]], %[[L2]] ], [ %[[V1]], %[[L1]] ], [ 0, %{{[0-9]+}} ]
+  %12 = lshr exact i64 %11, 32
+  %13 = trunc i64 %12 to i32
+  %14 = and i32 %13, 65535
+  %15 = mul i32 %14, %1
+  %16 = lshr i32 %15, 16
+  store i32 %16, i32* @bar, align 4
+  ret void
+}