[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.

[xbolva00]

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

1

Please use utils/update_test_checks.py

[davidxl]

llvm/lib/Analysis/ValueTracking.cpp

2028

run a clang-format on the changed part.

2045

typo: induction

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

26

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.

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 induciton 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;
+
+  switch (BO->getOpcode()) {
+  case Instruction::Mul:
+    // Power of two is closed under multiplication.
+    Q.CxtI = BO->getParent()->getTerminator();
+    return (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+           isKnownToBeAPowerOfTwo(Step, OrZero, Depth, Q);
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+    // Divisor must be a power of two.
+    Q.CxtI = BO->getParent()->getTerminator();
+    // 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::LShr:
+  case Instruction::AShr:
+    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

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; check value being deduced to be a power of two, thus allows urem optimization.
+; i.e. A urem B = A & (B - 1) if B is a power of two.
+
+define i64 @knwon_power_of_two_urem_select(i64 %size, i1 %cmp, i1 %cmp1) {
+; Note: can't check for exact sequence since %select2 - 1 may be folded into
+; select, and operands can be reordered, so just check "and" instruction has
+; replaced urem instruction.
+; CHECK-LABEL: @knwon_power_of_two_urem_select(
+; CHECK-NEXT:    {{%.*}} = select i1 {{.*}}
+; CHECK-NEXT:    {{%.*}} = select i1 {{.*}}
+; CHECK-NOT:     urem
+; CHECK-NOT:     srem
+; CHECK-NOT:     udiv
+; CHECK-NOT:     sdiv
+; CHECK:         [[R:%.*]] = and i64 {{%.*}}
+; CHECK-NEXT:    ret i64 [[R]]
+;
+  %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 @knwon_power_of_two_urem_phi(i64 %size, i1 %cmp, i1 %cmp1) {
+; CHECK-LABEL: @knwon_power_of_two_urem_phi(
+entry:
+  br i1 %cmp, label %cond.end, label %cond.false
+
+cond.false:
+  %select = select i1 %cmp1, i64 2, i64 8
+  br label %cond.end
+
+cond.end:
+; CHECK:       cond.end:
+; CHECK-NEXT:    {{%.*}} = phi i64 {{.*}}
+; CHECK-NOT:     urem
+; CHECK-NOT:     srem
+; CHECK-NOT:     udiv
+; CHECK-NOT:     sdiv
+; CHECK-NEXT:    [[R:%.*]] = and i64 {{%.*}}
+; CHECK-NEXT:    ret i64 [[R]]
+  %phi = phi i64 [ %select, %cond.false ], [ 64, %entry ]
+  %urem = urem i64 %size, %phi
+  ret i64 %urem
+}
+
+define i64 @known_power_of_two_urem_loop(i64 %size, i64 %a) {
+; CHECK-LABEL: @known_power_of_two_urem_loop(
+entry:
+  %shl = shl nuw i64 1, %a
+  br label %for.body
+
+for.body:
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 {{.*}}
+; CHECK-NEXT:    [[SUM:%.*]] = phi i64 {{.*}}
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[PHI]], -1
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[ADD]], %size
+; CHECK-NEXT:    {{%.*}} = add nsw i64 [[SUM]], [[AND]]
+  %phi = phi i64 [ %shl, %entry ], [ %mul, %for.body ]
+  %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %urem = urem i64 %size, %phi
+  %add = add nsw i64 %sum, %urem
+  %mul = mul nsw i64 %phi, 4
+  %icmp = icmp ult i64 %mul, 100000000
+  br i1 %icmp, label %for.body, label %for.end
+
+for.end:
+  %r = phi i64 [ %sum, %for.body ]
+  ret i64 %r
+}