diff --git a/llvm/include/llvm/Transforms/Utils/InstructionWorklist.h b/llvm/include/llvm/Transforms/Utils/InstructionWorklist.h
--- a/llvm/include/llvm/Transforms/Utils/InstructionWorklist.h
+++ b/llvm/include/llvm/Transforms/Utils/InstructionWorklist.h
@@ -108,6 +108,17 @@
       push(cast<Instruction>(U));
   }
 
+  /// Should be called *after* decrementing the use-count on V.
+  void handleUseCountDecrement(Value *V) {
+    if (auto *I = dyn_cast<Instruction>(V)) {
+      add(I);
+      // Many folds have one-use limitations. If there's only one use left,
+      // revisit that use.
+      if (I->hasOneUse())
+        add(cast<Instruction>(*I->user_begin()));
+    }
+  }
+
   /// Check that the worklist is empty and nuke the backing store for the map.
   void zap() {
     assert(WorklistMap.empty() && "Worklist empty, but map not?");
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -411,12 +411,11 @@
 
     // Make sure that we reprocess all operands now that we reduced their
     // use counts.
-    for (Use &Operand : I.operands())
-      if (auto *Inst = dyn_cast<Instruction>(Operand))
-        Worklist.add(Inst);
-
+    SmallVector<Value *> Ops(I.operands());
     Worklist.remove(&I);
     I.eraseFromParent();
+    for (Value *Op : Ops)
+      Worklist.handleUseCountDecrement(Op);
     MadeIRChange = true;
     return nullptr; // Don't do anything with FI
   }
diff --git a/llvm/test/Other/print-debug-counter.ll b/llvm/test/Other/print-debug-counter.ll
--- a/llvm/test/Other/print-debug-counter.ll
+++ b/llvm/test/Other/print-debug-counter.ll
@@ -8,7 +8,7 @@
 ; CHECK:       early-cse
 ; CHECK-SAME:  {4,1,1}
 ; CHECK:       instcombine-visit
-; CHECK-SAME:  {12,0,-1}
+; CHECK-SAME:  {13,0,-1}
 ; CHECK:       newgvn-vn
 ; CHECK-SAME:  {9,1,2}
 define i32 @f1(i32 %a, i32 %b) {
diff --git a/llvm/test/Transforms/InstCombine/or-shifted-masks.ll b/llvm/test/Transforms/InstCombine/or-shifted-masks.ll
--- a/llvm/test/Transforms/InstCombine/or-shifted-masks.ll
+++ b/llvm/test/Transforms/InstCombine/or-shifted-masks.ll
@@ -54,10 +54,13 @@
 
 define i32 @multiuse1(i32 %x) {
 ; CHECK-LABEL: @multiuse1(
-; CHECK-NEXT:    [[I21:%.*]] = shl i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[I:%.*]] = lshr i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[I3:%.*]] = and i32 [[I]], 1
+; CHECK-NEXT:    [[I1:%.*]] = lshr i32 [[X]], 1
+; CHECK-NEXT:    [[I5:%.*]] = and i32 [[I1]], 2
+; CHECK-NEXT:    [[I21:%.*]] = shl i32 [[X]], 6
 ; CHECK-NEXT:    [[I6:%.*]] = and i32 [[I21]], 384
-; CHECK-NEXT:    [[I32:%.*]] = lshr i32 [[X]], 1
-; CHECK-NEXT:    [[I7:%.*]] = and i32 [[I32]], 3
+; CHECK-NEXT:    [[I7:%.*]] = or i32 [[I3]], [[I5]]
 ; CHECK-NEXT:    [[I8:%.*]] = or i32 [[I7]], [[I6]]
 ; CHECK-NEXT:    ret i32 [[I8]]
 ;
@@ -75,10 +78,16 @@
 
 define i32 @multiuse2(i32 %x) {
 ; CHECK-LABEL: @multiuse2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[I:%.*]] = shl i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[I2:%.*]] = and i32 [[I]], 12
+; CHECK-NEXT:    [[I3:%.*]] = shl i32 [[X]], 1
+; CHECK-NEXT:    [[I5:%.*]] = and i32 [[I3]], 48
+; CHECK-NEXT:    [[I6:%.*]] = shl i32 [[X]], 1
+; CHECK-NEXT:    [[I8:%.*]] = and i32 [[I6]], 192
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X]], 8
 ; CHECK-NEXT:    [[I10:%.*]] = and i32 [[TMP1]], 32256
-; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[X]], 1
-; CHECK-NEXT:    [[I12:%.*]] = and i32 [[TMP2]], 252
+; CHECK-NEXT:    [[I11:%.*]] = or i32 [[I8]], [[I5]]
+; CHECK-NEXT:    [[I12:%.*]] = or i32 [[I2]], [[I11]]
 ; CHECK-NEXT:    [[I13:%.*]] = or i32 [[I10]], [[I12]]
 ; CHECK-NEXT:    ret i32 [[I13]]
 ;
@@ -101,10 +110,13 @@
 
 define i32 @multiuse3(i32 %x) {
 ; CHECK-LABEL: @multiuse3(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 6
+; CHECK-NEXT:    [[I:%.*]] = lshr i32 [[X:%.*]], 1
+; CHECK-NEXT:    [[I2:%.*]] = and i32 [[I]], 48
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X]], 6
 ; CHECK-NEXT:    [[I5:%.*]] = and i32 [[TMP1]], 8064
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[X]], 1
-; CHECK-NEXT:    [[I8:%.*]] = and i32 [[TMP2]], 63
+; CHECK-NEXT:    [[I6:%.*]] = lshr i32 [[X]], 1
+; CHECK-NEXT:    [[I7:%.*]] = and i32 [[I6]], 15
+; CHECK-NEXT:    [[I8:%.*]] = or i32 [[I2]], [[I7]]
 ; CHECK-NEXT:    [[I9:%.*]] = or i32 [[I8]], [[I5]]
 ; CHECK-NEXT:    ret i32 [[I9]]
 ;