[ValueTracking] peek through min/max to find isKnownToBeAPowerOfTwo

[spatel]

Summary

This is similar to the select logic just ahead of the new code. Min/max choose exactly one value from the inputs, so if both of those are a power-of-2, then the result must be a power-of-2. This might help with D98152, but we likely still need other pieces of the puzzle to avoid regressions.

The part I'm not sure about is the diff in PatternMatch.h. Without that, I get a pile of errors like:
error: assigning to 'llvm::Value *' from incompatible type 'const llvm::Value *'

...and I haven't been able to find a combination of const to avoid it. I did try const_cast<Value *>(V) in the caller code, and that also works. Is that better or worse?

[lebedev.ri]

LGTM

llvm/include/llvm/IR/PatternMatch.h

1738

Yeah, i think that's fine..

[RKSimon]

LGTM with one minor

llvm/include/llvm/IR/PatternMatch.h

1738

Really we should be avoiding auto for anything but casts or iterators

[spatel]

llvm/include/llvm/IR/PatternMatch.h

1738

So const_cast in the caller, or do you see another way to avoid the build errors?

[RKSimon]

llvm/include/llvm/IR/PatternMatch.h

1738

if its calling build errors then by all means use auto

llvm/include/llvm/IR/PatternMatch.h

template <typename OpTy> bool match(OpTy *V) {
     auto *SI = dyn_cast<SelectInst>(V);
     if (!SI)
       return false;
     auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
     if (!Cmp)
       return false;
     // At this point we have a select conditioned on a comparison.  Check that
     // it is the values returned by the select that are being compared.
-    Value *TrueVal = SI->getTrueValue();
-    Value *FalseVal = SI->getFalseValue();
-    Value *LHS = Cmp->getOperand(0);
-    Value *RHS = Cmp->getOperand(1);
+    auto *TrueVal = SI->getTrueValue();
+    auto *FalseVal = SI->getFalseValue();
+    auto *LHS = Cmp->getOperand(0);
+    auto *RHS = Cmp->getOperand(1);
     if ((TrueVal != LHS || FalseVal != RHS) &&
         (TrueVal != RHS || FalseVal != LHS))
       return false;
     typename CmpInst_t::Predicate Pred =
         LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
     // Does "(x pred y) ? x : y" represent the desired max/min operation?
     if (!Pred_t::match(Pred))
       return false;

llvm/lib/Analysis/ValueTracking.cpp

bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
 
   if (const ZExtInst *ZI = dyn_cast<ZExtInst>(V))
     return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth, Q);
 
   if (const SelectInst *SI = dyn_cast<SelectInst>(V))
     return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth, Q) &&
            isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth, Q);
 
+  // Peek through min/max.
+  if (match(V, m_MaxOrMin(m_Value(X), m_Value(Y)))) {
+    return isKnownToBeAPowerOfTwo(X, OrZero, Depth, Q) &&
+           isKnownToBeAPowerOfTwo(Y, OrZero, Depth, Q);
+  }
+
   if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) {
     // A power of two and'd with anything is a power of two or zero.
     if (isKnownToBeAPowerOfTwo(X, /*OrZero*/ true, Depth, Q) ||
         isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, Depth, Q))
       return true;
     // X & (-X) is always a power of two or zero.
     if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X))))
       return true;

llvm/test/Transforms/InstSimplify/AndOrXor.ll

;
   ret i64 %e2
 }
 
 define i32 @pow2b_max(i32 %x, i32 %y) {
 ; CHECK-LABEL: @pow2b_max(
 ; CHECK-NEXT:    [[SHX:%.*]] = shl i32 2, [[X:%.*]]
 ; CHECK-NEXT:    [[SHY:%.*]] = shl i32 32, [[Y:%.*]]
 ; CHECK-NEXT:    [[M:%.*]] = call i32 @llvm.smax.i32(i32 [[SHX]], i32 [[SHY]])
-; CHECK-NEXT:    [[NEG:%.*]] = sub i32 0, [[M]]
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[M]], [[NEG]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    ret i32 [[M]]
 ;
   %shx = shl i32 2, %x
   %shy = shl i32 32, %y
   %m = call i32 @llvm.smax.i32(i32 %shx, i32 %shy)
   %neg = sub i32 0, %m
   %r = and i32 %m, %neg
   ret i32 %r
 }
;
   %x = and <2 x i32> %p, <i32 2048, i32 2048>
   %a = add <2 x i32> %x, <i32 -1, i32 -1>
   %r = and <2 x i32> %x, %a
   ret <2 x i32> %r
 }
 
 define <2 x i32> @pow2_decrement_min_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @pow2_decrement_min_vec(
-; CHECK-NEXT:    [[P1:%.*]] = and <2 x i32> [[X:%.*]], <i32 2048, i32 2048>
-; CHECK-NEXT:    [[P2:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[Y:%.*]]
-; CHECK-NEXT:    [[M:%.*]] = call <2 x i32> @llvm.umin.v2i32(<2 x i32> [[P1]], <2 x i32> [[P2]])
-; CHECK-NEXT:    [[A:%.*]] = add <2 x i32> [[M]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i32> [[M]], [[A]]
-; CHECK-NEXT:    ret <2 x i32> [[R]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %p1 = and <2 x i32> %x, <i32 2048, i32 2048>
   %p2 = shl <2 x i32> <i32 1, i32 1>, %y
   %m = call <2 x i32> @llvm.umin.v2i32(<2 x i32> %p1, <2 x i32> %p2)
   %a = add <2 x i32> %m, <i32 -1, i32 -1>
   %r = and <2 x i32> %m, %a
   ret <2 x i32> %r
 }