[CVP] Remove a masking operation if range information implies it's a noop

[reames]

Summary

This is really a known bits style transformation, but known bits isn't context sensitive. The particular case which comes up happens to involve a range which allows range based reasoning to eliminate the mask pattern, so handle that case specifically in CVP.

InstCombine likes to generate the mask-by-low-bits pattern when widening an arithmetic expression which includes a zext in the middle.

[lebedev.ri]

I agree that instcombine likes that pattern, so it may make sense to deal with it.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

65 ↗

(On Diff #224390)

STATISTIC(NumAndMasks, "Number of constant low-bit-masking ands dropped");

715–716 ↗

(On Diff #224390)

Do we want to query constanrange, or use getPredicateAt()?
Different folds here take different routes.
Should this be:

if (LVI->getPredicateAt(ICmpInst::ICMP_ULE, LHS, RHS, SDI) !=
    LazyValueInfo::True)
  return false;

? (i don't know)

720–721 ↗

(On Diff #224390)

++NumAndMasks();

[reames]

Add statistic, and update a couple other tests which should have been in initial patch.

[reames]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

715–716 ↗

(On Diff #224390)

In this case, I think they're basically equivalent in practice for this case. The getPredicateAt form is slightly more powerful as it does predicate pushback through one layer of predecessors, but skipping that is slightly faster compile time wise.

Hm, having written that, I think I'll switch to the predicate form just for future proofing ad consistency. Update coming.

[reames]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

715–716 ↗

(On Diff #224390)

Correction: the getPredicateAt form does predicate pushback, but is weaker on conditions which are implied by edge local facts. (i.e. I tried to switch and the results are strictly worse.) This is arguably an LVI bug - one I remember from past occurrences now - but not something I'm going to fix just for this issue.

[nikic]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

713 ↗

(On Diff #224423)

The limit to masks seems a bit stronger than strictly necessary: The range needs to be <= than the trailing ones in RHS. That is for 0b11001111, if the range is <= 0b00001111 that is sufficient. Not sure if this is worth handling.

715–716 ↗

(On Diff #224390)

Right, this is a longstanding LVI limitation.

[lebedev.ri]

Thanks, this looks ok to me, but i'll leave final review to others.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

713 ↗

(On Diff #224423)

I'd say this is intentional to limit the number of ands we handle.

[reames]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

713 ↗

(On Diff #224423)

It's definitely more restrictive than necessary. I decided the mask case (which is specifically what instcombine generates) was a reasonable case to break at.

I'm happy to generalize (slightly) but will definitely do so in a separate patch.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
 STATISTIC(NumUDivs,     "Number of udivs whose width was decreased");
 STATISTIC(NumAShrs,     "Number of ashr converted to lshr");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
 STATISTIC(NumSExt,      "Number of sext converted to zext");
+STATISTIC(NumAnd,       "Number of ands removed");
 STATISTIC(NumOverflows, "Number of overflow checks removed");
 STATISTIC(NumSaturating,
     "Number of saturating arithmetics converted to normal arithmetics");
 
 static cl::opt<bool> DontAddNoWrapFlags("cvp-dont-add-nowrap-flags", cl::init(false));
 
 namespace {
 
if (!NSW) {
     bool NewNSW = NSWRange.contains(LRange);
     BinOp->setHasNoSignedWrap(NewNSW);
     Changed |= NewNSW;
   }
 
   return Changed;
 }
 
+static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
+  if (BinOp->getType()->isVectorTy())
+    return false;
+
+  // Pattern match (and lhs, C) where C includes a superset of bits which might
+  // be set in lhs.  This is a common truncation idiom created by instcombine.
+  BasicBlock *BB = BinOp->getParent();
+  Value *LHS = BinOp->getOperand(0);
+  ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
+  if (!RHS || !RHS->getValue().isMask())
+    return false;
+
+  ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
+  if (!LRange.getUnsignedMax().ule(RHS->getValue()))
+    return false;
+
+  BinOp->replaceAllUsesWith(LHS);
+  BinOp->eraseFromParent();
+  NumAnd++;
+  return true;
+}
+
+
 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
 
   // TODO: The following really should be sunk inside LVI's core algorithm, or
   // at least the outer shims around such.
   auto *C = dyn_cast<CmpInst>(V);
   if (!C) return nullptr;
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
         break;
       case Instruction::SExt:
         BBChanged |= processSExt(cast<SExtInst>(II), LVI);
         break;
       case Instruction::Add:
       case Instruction::Sub:
         BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
         break;
+      case Instruction::And:
+        BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
+        break;
       }
     }
 
     Instruction *Term = BB->getTerminator();
     switch (Term->getOpcode()) {
     case Instruction::Switch:
       BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI, DT);
       break;

llvm/test/Transforms/CorrelatedValuePropagation/and.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+define i32 @test(i32 %a) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 128
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 128
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @test2(i32 %a) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @test3(i32 %a) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 1023
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+
+define i32 @neg1(i32 %a) {
+; CHECK-LABEL: @neg1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A]], 255
+; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ule i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @neg2(i32 %a) {
+; CHECK-LABEL: @neg2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 513
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A]], 255
+; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 513
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 255
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+
+define i32 @neg3(i32 %a) {
+; CHECK-LABEL: @neg3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 256
+; CHECK-NEXT:    br i1 [[CMP]], label [[CONTINUE:%.*]], label [[EXIT:%.*]]
+; CHECK:       continue:
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A]], 254
+; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 -1
+;
+entry:
+  %cmp = icmp ult i32 %a, 256
+  br i1 %cmp, label %continue, label %exit
+continue:
+  %and = and i32 %a, 254
+  ret i32 %and
+exit:
+  ret i32 -1
+}
+

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y_OFFSET]], 19
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[RES1:%.*]] = mul nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
-; CHECK-NEXT:    [[CMP5:%.*]] = and i1 true, true
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %x.offset = add i32 %x, 9
   %cmp1 = icmp ult i32 %x.offset, 19
   br i1 %cmp1, label %cont1, label %out

llvm/test/Transforms/CorrelatedValuePropagation/range.ll

 
 target93:
   ret i8 %c
 }
 
 define i1 @test17_i1(i1 %a) {
 ; CHECK-LABEL: @test17_i1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A:%.*]], true
 ; CHECK-NEXT:    br label [[DISPATCH:%.*]]
 ; CHECK:       dispatch:
-; CHECK-NEXT:    br i1 [[A]], label [[TRUE:%.*]], label [[DISPATCH]]
+; CHECK-NEXT:    br i1 [[A:%.*]], label [[TRUE:%.*]], label [[DISPATCH]]
 ; CHECK:       true:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %c = and i1 %a, true
   br label %dispatch
 
 dispatch: