[ValueTracking] Added support to deduce PHI Nodes values being a power of 2

[huangjd]

Summary

Added support to deduce PHI Nodes values being a power of 2 in ValueTracking. This enables more optimizations in applications such as calculating alignment.

[davidxl]

Can you add back the original list of reviewers and mark the places where the prior comments are addressed?

[huangjd]

llvm/lib/Analysis/ValueTracking.cpp

2028

Original comment from davidxl:
run a clang-format on the changed part.

2044

Original comment from davidxl:
typo: induction

llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll

2

Original comment from xbolva00
Please use utils/update_test_checks.py

20

Original comment from davidxl:

Please also add tests for

1. other operators for simple recurrence.
2. for other type of recurrence (change at line 2177).
3. chained phi case
4. negative cases.

[davidxl]

llvm/lib/Analysis/ValueTracking.cpp

2058

is the power2 check for start done above already?

[huangjd]

llvm/lib/Analysis/ValueTracking.cpp

2058

This one checks for constant literal. The check before is for any expression that can be deduced to be a power of 2, which is not sufficient to be correct in this case because it may equal to sign bit (0x8000...) and sdiv of this number is no longer a power of 2

[Carrot]

[Carrot]

llvm/lib/Analysis/ValueTracking.cpp

2173

Please add a comment here. I searched the source code for a while to understand its purpose.

[davidxl]

The patch looks reasonable. Please wait for other reviewers (Sanjay ) to comment as well.

[spatel]

llvm/lib/Analysis/ValueTracking.cpp

2173

This request was not answered. We are using max depth to avoid a compile-time explosion because we are recursing on every phi operand?

2181–2187

It would be safer to split this patch into 2 parts. The first would be just this part (and eliminate adding isPowerOfTwoRecurrence until the next patch). We can't currently handle even minimal non-loop patterns like:

define i64 @known_power_of_two_urem_phi(i64 %x, i1 %b) {
entry:
  br i1 %b, label %t, label %f

t:                
  br label %end

f:           
  br label %end

end:             
  %p = phi i64 [ 4096, %t ], [ 4, %f ]
  %r = urem i64 %x, %p
  ret i64 %r
}

llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll

7

If I understand correctly, there's no difference for this test - no phis, and it already works as expected.

Please pre-commit the tests with baseline CHECKs, so we just show test diffs in this review.

[huangjd]

llvm/lib/Analysis/ValueTracking.cpp

2173

Looks like it should be just Depth instead, will fix it.

A similar appearance in line 2580 (isKnownNonZero) may be a bug then? This limits the level of recursion to be 2, instead of MaxAnalysisRecursionDepth.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2173

This request was not answered. We are using max depth to avoid a compile-time explosion because we are recursing on every phi operand?

Yes. The depth limit is based on the assumption that instructions have few operands over which we recurse, generally resulting in up to 2^Depth recursive calls at most. For phis the branching factor may be arbitrarily high, resulting in Operands^Depth recursive calls.

The limit is not strictly necessary for the recurrence case though, and I don't think we apply it for recurrences in KnownBits/NonZero.

[davidxl]

From the feedbacks, the action items are

1. checkin baseine tests;
2. split out recurrence handling from the main patch -- have it reviewed and committed
3. send the recurrence handling patch, get it reviewed and committed (the depth may not be needed in this case)

[spatel]

Abandon this patch? It is split up now:
D124885
D124889
D124890

llvm/lib/Analysis/ValueTracking.cpp

#endif
   // Therefore, we run them after computeKnownBitsFromOperator.
 
   // Check whether a nearby assume intrinsic can determine some known bits.
   computeKnownBitsFromAssume(V, Known, Depth, Q);
 
   assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?");
 }
 
+/// Try to detect a recurrence that the value of the induction variable is
+/// always a power of two (or zero).
+static bool isPowerOfTwoRecurrence(const PHINode *PN, bool OrZero,
+                                   unsigned Depth, Query &Q) {
+  BinaryOperator *BO = nullptr;
+  Value *Start = nullptr, *Step = nullptr;
+  if (!matchSimpleRecurrence(PN, BO, Start, Step))
+    return false;
+
+  // Initial value must be a power of two.
+  for (const Use &U : PN->operands()) {
+    if (U.get() == Start) {
+      Q.CxtI = PN->getIncomingBlock(U)->getTerminator();
+      if (!isKnownToBeAPowerOfTwo(Start, OrZero, Depth, Q))
+        return false;
+    }
+  }
+
+  // Except for Mul, the induction variable must be on the left side of the
+  // increment expression, otherwise its value can be arbitrary.
+  if (BO->getOpcode() != Instruction::Mul && BO->getOperand(1) != Step)
+    return false;
+
+  Q.CxtI = BO->getParent()->getTerminator();
+  switch (BO->getOpcode()) {
+  case Instruction::Mul:
+    // Power of two is closed under multiplication.
+    return (OrZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+           isKnownToBeAPowerOfTwo(Step, OrZero, Depth, Q);
+  case Instruction::SDiv:
+    // Start value must not be signmask for signed division, therefore can only
+    // be a constant value.
+    if (!match(Start, m_Power2()) || match(Start, m_SignMask()))
+      return false;
+    LLVM_FALLTHROUGH;
+  case Instruction::UDiv:
+    // Divisor must be a power of two.
+    // If OrZero is false, cannot guarantee induction variable is non-zero after
+    // division, same for Shr.
+    return OrZero && isKnownToBeAPowerOfTwo(Step, false, Depth, Q);
+  case Instruction::Shl:
+    return OrZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap();
+  case Instruction::AShr:
+    if (!match(Start, m_Power2()) || match(Start, m_SignMask()))
+      return false;
+    LLVM_FALLTHROUGH;
+  case Instruction::LShr:
+    return OrZero;
+  default:
+    return false;
+  }
+}
+
 /// Return true if the given value is known to have exactly one
 /// bit set when defined. For vectors return true if every element is known to
 /// be a power of two when defined. Supports values with integer or pointer
 /// types and vectors of integers.
 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
                             const Query &Q) {
   assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
 
if (OrZero || Q.IIQ.hasNoUnsignedWrap(VOBO) ||
       if ((~(LHSBits.Zero & RHSBits.Zero)).isPowerOf2())
         // If OrZero isn't set, we cannot give back a zero result.
         // Make sure either the LHS or RHS has a bit set.
         if (OrZero || RHSBits.One.getBoolValue() || LHSBits.One.getBoolValue())
           return true;
     }
   }
 
+  // A PHI node is power of two if all incoming values are power of two, or if
+  // it is an induction variable where in each step its value is a power of two
+  if (const PHINode *PN = dyn_cast<PHINode>(V)) {
+    unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
+    Query RecQ = Q;
+
+    // Check if it is an induction variable and always power of two
+    if (Q.IIQ.UseInstrInfo &&
+        isPowerOfTwoRecurrence(PN, OrZero, NewDepth, RecQ))
+      return true;
+
+    // Recursively check all incoming values
+    return llvm::all_of(PN->operands(), [&](const Use &U) {
+      if (U.get() == PN)
+        return true;
+      RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
+      return isKnownToBeAPowerOfTwo(U.get(), OrZero, NewDepth, RecQ);
+    });
+  }
+
   // An exact divide or right shift can only shift off zero bits, so the result
   // is a power of two only if the first operand is a power of two and not
   // copying a sign bit (sdiv int_min, 2).
   if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) ||
       match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) {
     return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero,
                                   Depth, Q);
   }

llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; Check if a value can be deduced as a power of 2, allowing urem optimization.
+; i.e. A urem B = A & (B - 1) if B is a power of 2.
+
+define i64 @known_power_of_two_urem_select(i64 %size, i1 %cmp, i1 %cmp1) {
+; CHECK-LABEL: @known_power_of_two_urem_select(
+; CHECK-NEXT:    [[SELECT_OP:%.*]] = select i1 [[CMP:%.*]], i64 63, i64 4095
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[CMP1:%.*]], i64 7, i64 [[SELECT_OP]]
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP1]], [[SIZE:%.*]]
+; CHECK-NEXT:    ret i64 [[UREM]]
+;
+  %select = select i1 %cmp, i64 64, i64 4096
+  %select1 = select i1 %cmp1, i64 8, i64 %select
+  %urem = urem i64 %size, %select1
+  ret i64 %urem
+}
+
+define i64 @known_power_of_two_urem_phi(i64 %size, i1 %cmp, i1 %cmp1) {
+; CHECK-LABEL: @known_power_of_two_urem_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br i1 [[CMP1:%.*]], label [[COND_TRUE_TRUE:%.*]], label [[COND_TRUE_FALSE:%.*]]
+; CHECK:       cond.true.true:
+; CHECK-NEXT:    br label [[COND_TRUE_END:%.*]]
+; CHECK:       cond.true.false:
+; CHECK-NEXT:    br label [[COND_TRUE_END]]
+; CHECK:       cond.true.end:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 2, [[COND_TRUE_TRUE]] ], [ 4, [[COND_TRUE_FALSE]] ]
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[PHI1:%.*]] = phi i64 [ 4096, [[ENTRY:%.*]] ], [ [[PHI]], [[COND_TRUE_END]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[PHI1]], -1
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
+; CHECK-NEXT:    ret i64 [[UREM]]
+;
+entry:
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  br i1 %cmp1, label %cond.true.true, label %cond.true.false
+
+cond.true.true:
+  br label %cond.true.end
+
+cond.true.false:
+  br label %cond.true.end
+
+cond.true.end:
+  %phi = phi i64 [ 2, %cond.true.true ], [ 4, %cond.true.false ]
+  br label %cond.end
+
+cond.end:
+  %phi1 = phi i64 [ 4096, %entry ], [ %phi, %cond.true.end ]
+  %urem = urem i64 %size, %phi1
+  ret i64 %urem
+}
+
+define i64 @known_power_of_two_urem_nested_expr(i64 %size, i1 %cmp, i1 %cmp1, i64 %0) {
+; CHECK-LABEL: @known_power_of_two_urem_nested_expr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i64 1, [[TMP0:%.*]]
+; CHECK-NEXT:    br label [[COND_END:%.*]]
+; CHECK:       cond.false:
+; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP1:%.*]], i64 2, i64 8
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[SELECT]], [[COND_FALSE]] ], [ [[TMP1]], [[COND_TRUE]] ], [ [[PHI]], [[COND_END]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[PHI]], -1
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP2]], [[SIZE:%.*]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[UREM]], 10
+; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_END]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i64 [[UREM]]
+;
+entry:
+  br i1 %cmp, label %cond.true, label %cond.false
+
+cond.true:
+  %1 = shl nuw i64 1, %0
+  br label %cond.end
+
+cond.false:
+  %select = select i1 %cmp1, i64 2, i64 8
+  br label %cond.end
+
+cond.end:
+  %phi = phi i64 [ %select, %cond.false ], [ %1, %cond.true ], [ %phi, %cond.end ]
+  %2 = phi i64 [ %size, %cond.false ], [ %size, %cond.true ], [ %0, %cond.end ]
+  %urem = urem i64 %size, %phi
+  %cmp2 = icmp ult i64 %urem, 10
+  br i1 %cmp2, label %cond.end, label %end
+
+end:
+  ret i64 %urem
+}
+
+define i64 @known_power_of_two_urem_negative(i64 %size, i1 %cmp, i64 %0) {
+; urem is not replaced if not all operands are power of 2.
+;
+; CHECK-LABEL: @known_power_of_two_urem_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 4, [[ENTRY:%.*]] ], [ [[TMP0:%.*]], [[COND_TRUE]] ]
+; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
+; CHECK-NEXT:    ret i64 [[UREM]]
+;
+entry:
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  br label %cond.end
+
+cond.end:
+  %phi = phi i64 [ 4, %entry ], [ %0, %cond.true ]
+  %urem = urem i64 %size, %phi
+  ret i64 %urem
+}
+
+define i64 @known_power_of_two_urem_loop_mul(i64 %size, i64 %a) {
+; CHECK-LABEL: @known_power_of_two_urem_loop_mul(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PHI]], -1
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
+; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = shl nuw i64 [[PHI]], 2
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i64 [[PHI]], 25000000
+; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  %start = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nuw i64 %sum, %urem
+  %i = mul nuw i64 %phi, 4
+  %icmp = icmp ult i64 %i, 100000000
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+define i64 @known_power_of_two_urem_loop_mul_negative(i64 %size, i64 %a) {
+; Cannot deduce induction variable is a power of 2 if it is multiplied by 3.
+;
+; CHECK-LABEL: @known_power_of_two_urem_loop_mul_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
+; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = mul nuw i64 [[PHI]], 3
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i64 [[I]], 100000000
+; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  %start = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nuw i64 %sum, %urem
+  %i = mul nuw i64 %phi, 3
+  %icmp = icmp ult i64 %i, 100000000
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+define i64 @known_power_of_two_urem_loop_shl(i64 %size, i64 %a) {
+; CHECK-LABEL: @known_power_of_two_urem_loop_shl(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PHI]], -1
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
+; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = shl nuw i64 [[PHI]], 1
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i64 [[PHI]], 50000000
+; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  %start = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nuw i64 %sum, %urem
+  %i = shl nuw i64 %phi, 1
+  %icmp = icmp ult i64 %i, 100000000
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+define i64 @known_power_of_two_urem_loop_lshr(i64 %size, i64 %a) {
+; CHECK-LABEL: @known_power_of_two_urem_loop_lshr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PHI]], -1
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
+; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = lshr i64 [[PHI]], 1
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp ult i64 [[PHI]], 2
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  %start = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nuw i64 %sum, %urem
+  %i = lshr i64 %phi, 1
+  %icmp = icmp ugt i64 %i, 0
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+
+define i64 @known_power_of_two_urem_loop_ashr(i64 %size, i64 %a) {
+; CHECK-LABEL: @known_power_of_two_urem_loop_ashr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 4096, [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[PHI]], -1
+; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
+; CHECK-NEXT:    [[ADD]] = add nsw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = lshr i64 [[PHI]], [[A:%.*]]
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i64 [[I]], 0
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ 4096, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nsw i64 %sum, %urem
+  %i = ashr i64 %phi, %a
+  %icmp = icmp ugt i64 %i, 0
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+define i64 @known_power_of_two_urem_loop_ashr_negative(i64 %size, i64 %a) {
+; Cannot deduce induction variable is a power of 2 for ashr if its starting
+; value is equal to sign bit
+;
+; CHECK-LABEL: @known_power_of_two_urem_loop_ashr_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ -9223372036854775808, [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
+; CHECK-NEXT:    [[ADD]] = add nsw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = ashr i64 [[PHI]], [[A:%.*]]
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ u0x8000000000000000, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nsw i64 %sum, %urem
+  %i = ashr i64 %phi, %a
+  %icmp = icmp ugt i64 %i, 0
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+define i64 @known_power_of_two_urem_loop_ashr_negative_2(i64 %size, i64 %a) {
+; Cannot deduce induction variable is a power of 2 for ashr if its starting
+; value may equal to sign bit.
+;
+; CHECK-LABEL: @known_power_of_two_urem_loop_ashr_negative_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
+; CHECK-NEXT:    [[ADD]] = add nsw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = ashr i64 [[PHI]], 2
+; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp ult i64 [[PHI]], 4
+; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  %start = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nsw i64 %sum, %urem
+  %i = ashr i64 %phi, 2
+  %icmp = icmp ugt i64 %i, 0
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}
+
+define i64 @known_power_of_two_urem_loop_negative(i64 %size, i64 %a) {
+; Cannot deduce induction variable is a power of 2 if the recurrence is not one
+; of the valid arithmetic operations.
+;
+; CHECK-LABEL: @known_power_of_two_urem_loop_negative(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
+; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
+; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
+; CHECK-NEXT:    [[I]] = add nuw i64 [[PHI]], 1
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i64 [[SUM]]
+;
+entry:
+  %start = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+  %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nuw i64 %sum, %urem
+  %i = add nuw i64 %phi, 1
+  %icmp = icmp ugt i64 %i, 0
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}