Index: llvm/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/lib/Analysis/ValueTracking.cpp
+++ llvm/lib/Analysis/ValueTracking.cpp
@@ -967,6 +967,91 @@
   }
 }
 
+/// Match a small linear recurrence cycle involving shift opcodes.
+/// Specifically, recognize the following:
+///   %iv = phi iN [%start, %?], [%iv.next, %backedge]
+///   %iv.next = shift_op %iv, %step
+///
+/// TODO: This can fairly trivially be generalized for other
+/// binary instructions if that were useful.
+static bool MatchShiftRecurrence(const Operator *O,
+                                 Value *&StartV, Value *&StepV) {
+  PHINode* PN = nullptr;
+  switch (O->getOpcode()) {
+  case Instruction::Shl:
+  case Instruction::AShr:
+  case Instruction::LShr:
+    PN = dyn_cast<PHINode>(O->getOperand(0));
+    StepV = O->getOperand(1);
+    break;
+  default:
+    return false;
+  }
+  if (!PN)
+    return false;
+
+  if (PN->getNumIncomingValues() != 2)
+    return false;
+
+  StartV = nullptr;
+  for (Value *IncV : PN->incoming_values()) {
+    if (IncV == O)
+      continue;
+    if (!StartV) {
+      StartV = IncV;
+      continue;
+    }
+    if (StartV != IncV)
+      return false;
+  }
+
+  if (!StartV)
+    return false;
+
+  return true;
+}
+
+/// If operator is part of a small recurrence cycle, use facts about the
+/// recurrence itself to refine the known bits of the result.
+/// As is idiomatic, Known2 is used as scratch.  Known is refined.
+static void RefineRecurrence(const Operator *O, const APInt &DemandedElts,
+                             KnownBits &Known, KnownBits &Known2,
+                             unsigned Depth, const Query &Q) {
+  unsigned Opcode = O->getOpcode();
+
+  // For the moment, we only handle the shift cases here.  This can
+  // probably be extended to most binary instructions.
+  if (Opcode != Instruction::LShr &&
+      Opcode != Instruction::AShr &&
+      Opcode != Instruction::Shl)
+    return;
+
+  Value *StartV = nullptr, *StepV = nullptr;
+  if (MatchShiftRecurrence(O, StartV, StepV)) {
+    // Recurse with the phi context to avoid concern about whether facts
+    // inferred hold at original context instruction.  TODO: It may be
+    // correct to use the original context.  IF warranted, explore and add
+    // sufficient tests to cover.
+    Query Q2 = Q;
+    Q2.CxtI = cast<Instruction>(O->getOperand(0));
+    computeKnownBits(StartV, DemandedElts, Known2, Depth + 1, Q2);
+    switch(Opcode) {
+    case Instruction::Shl:
+      // A shl recurrence will only increase the tailing zeros
+      Known.Zero.setLowBits(Known2.countMinTrailingZeros());
+      break;
+    case Instruction::LShr:
+      // A lshr recurrence will preserve the leading zeros of the start value
+      Known.Zero.setHighBits(Known2.countMinLeadingZeros());
+      break;
+    case Instruction::AShr:
+      // An ashr recurrence will extend the initial sign bit
+      Known.Zero.setHighBits(Known2.countMinLeadingZeros());
+      Known.One.setHighBits(Known2.countMinLeadingOnes());
+    };
+  }
+}
+
 /// Compute known bits from a shift operator, including those with a
 /// non-constant shift amount. Known is the output of this function. Known2 is a
 /// pre-allocated temporary with the same bit width as Known and on return
@@ -1381,6 +1466,11 @@
         if (!LU)
           continue;
         unsigned Opcode = LU->getOpcode();
+
+        // If this is an small recurrence cycle, use facts about the
+        // recurrence itself to refine the result.
+        RefineRecurrence(LU, DemandedElts, Known, Known2, Depth, Q);
+
         // Check for operations that have the property that if
         // both their operands have low zero bits, the result
         // will have low zero bits.