[CVP] No-wrap deduction for `shl`

[lebedev.ri]

Summary

This is the last OverflowingBinaryOperator for which we don't deduce flags.
D69217 taught ConstantRange::makeGuaranteedNoWrapRegion() about it.

The effect is better than of the mul patch (D69203):

statistic	old	new	delta	% change
correlated-value-propagation.NumAddNUW	7145	7144	-1	-0.0140%
correlated-value-propagation.NumAddNW	12126	12125	-1	-0.0082%
correlated-value-propagation.NumAnd	443	446	3	0.6772%
correlated-value-propagation.NumNSW	5986	7158	1172	19.5790%
correlated-value-propagation.NumNUW	10512	13304	2792	26.5601%
correlated-value-propagation.NumNW	16498	20462	3964	24.0272%
correlated-value-propagation.NumShlNSW	0	1172	1172
correlated-value-propagation.NumShlNUW	0	2793	2793
correlated-value-propagation.NumShlNW	0	3965	3965
instcount.NumAShrInst	13824	13790	-34	-0.2459%
instcount.NumAddInst	277584	277586	2	0.0007%
instcount.NumAndInst	66061	66056	-5	-0.0076%
instcount.NumBrInst	709153	709147	-6	-0.0008%
instcount.NumICmpInst	483709	483708	-1	-0.0002%
instcount.NumSExtInst	79497	79496	-1	-0.0013%
instcount.NumShlInst	40691	40654	-37	-0.0909%
instcount.NumSubInst	61997	61996	-1	-0.0016%
instcount.NumZExtInst	68208	68211	3	0.0044%
instcount.TotalBlocks	843916	843910	-6	-0.0007%
instcount.TotalInsts	7387528	7387448	-80	-0.0011%

[nikic]

LGTM. Small overall effect, but I think it still makes sense for completeness, and as far as I know this shouldn't be particularly expensive.

Can I interest you in making LVI use the recently added addWithNoWrap() method, to get some cross-pollination from nowrap flags inferred by other passes? Would be interesting to see if that allows us to infer/simplify more in CVP. If it does, we can invest some effort in adding this functionality for other operators as well.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 STATISTIC(NumAddNSW,    "Number of no-signed-wrap deductions for add");
 STATISTIC(NumAddNUW,    "Number of no-unsigned-wrap deductions for add");
 STATISTIC(NumSubNW,     "Number of no-wrap deductions for sub");
 STATISTIC(NumSubNSW,    "Number of no-signed-wrap deductions for sub");
 STATISTIC(NumSubNUW,    "Number of no-unsigned-wrap deductions for sub");
 STATISTIC(NumMulNW,     "Number of no-wrap deductions for mul");
 STATISTIC(NumMulNSW,    "Number of no-signed-wrap deductions for mul");
 STATISTIC(NumMulNUW,    "Number of no-unsigned-wrap deductions for mul");
+STATISTIC(NumShlNW,     "Number of no-wrap deductions for shl");
+STATISTIC(NumShlNSW,    "Number of no-signed-wrap deductions for shl");
+STATISTIC(NumShlNUW,    "Number of no-unsigned-wrap deductions for shl");
 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 {
 
case Instruction::Sub:
     OpcNSW = &NumSubNSW;
     OpcNUW = &NumSubNUW;
     break;
   case Instruction::Mul:
     OpcNW = &NumMulNW;
     OpcNSW = &NumMulNSW;
     OpcNUW = &NumMulNUW;
     break;
+  case Instruction::Shl:
+    OpcNW = &NumShlNW;
+    OpcNSW = &NumShlNSW;
+    OpcNUW = &NumShlNUW;
+    break;
   default:
     llvm_unreachable("Will not be called with other binops");
   }
 
   auto *Inst = dyn_cast<Instruction>(V);
   if (NewNSW) {
     ++NumNW;
     ++*OpcNW;
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
         BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
         break;
       case Instruction::SExt:
         BBChanged |= processSExt(cast<SExtInst>(II), LVI);
         break;
       case Instruction::Add:
       case Instruction::Sub:
       case Instruction::Mul:
+      case Instruction::Shl:
         BBChanged |= processBinOp(cast<BinaryOperator>(II), LVI);
         break;
       case Instruction::And:
         BBChanged |= processAnd(cast<BinaryOperator>(II), LVI);
         break;
       }
     }
 

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[X:%.*]], 5
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[CONT1:%.*]], label [[OUT:%.*]]
 ; CHECK:       cont1:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 5
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
-; CHECK-NEXT:    [[SHIFTED:%.*]] = shl i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[SHIFTED:%.*]] = shl nuw nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %cmp1 = icmp ult i32 %x, 5

 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[X:%.*]], 5
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[CONT1:%.*]], label [[OUT:%.*]]
 ; CHECK:       cont1:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 15
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
-; CHECK-NEXT:    [[SHIFTED:%.*]] = shl i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[SHIFTED:%.*]] = shl nuw nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
 ; CHECK:       cont3:
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[SHIFTED]], 65536
 ; CHECK-NEXT:    br label [[OUT]]
 ; CHECK:       out:
 ; CHECK-NEXT:    [[RET:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ true, [[CONT1]] ], [ [[CMP3]], [[CONT3]] ]
 ; CHECK-NEXT:    ret i1 [[RET]]
 ;

llvm/test/Transforms/CorrelatedValuePropagation/shl.ll

 }
 
 define i8 @test4(i8 %a, i8 %b) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[B:%.*]], 7
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[A:%.*]], [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i8 [[A:%.*]], [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp ugt i8 %b, 7
   br i1 %cmp, label %bb, label %exit
 
 bb:
   %shl = shl i8 %a, %b
   ret i8 %shl
 
 exit:
   ret i8 0
 }
 
 define i8 @test5(i8 %b) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 0, [[B:%.*]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i8 0, [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ;
   %shl = shl i8 0, %b
   ret i8 %shl
 }
 
 define i8 @test6(i8 %b) {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 1, [[B:%.*]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i8 1, [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ;
   %shl = shl i8 1, %b
   ret i8 %shl
 }
 
 define i8 @test7(i8 %b) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[B:%.*]], 7
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 1, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i8 1, [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp ult i8 %b, 7
   br i1 %cmp, label %bb, label %exit
 
 bb:
   %shl = shl i8 1, %b
   ret i8 %shl
 
 exit:
   ret i8 0
 }
 
 define i8 @test8(i8 %b) {
 ; CHECK-LABEL: @test8(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 -1, [[B:%.*]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nsw i8 -1, [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ;
   %shl = shl i8 -1, %b
   ret i8 %shl
 }
 
 define i8 @test9(i8 %b) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[B:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 -1, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i8 -1, [[B]]
 ; CHECK-NEXT:    ret i8 -1
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp eq i8 %b, 0
   br i1 %cmp, label %bb, label %exit
 

 }
 
 define i8 @test11(i8 %b) {
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[B:%.*]], 2
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 42, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i8 42, [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp ult i8 %b, 2
   br i1 %cmp, label %bb, label %exit
 
 bb:
   %shl = shl i8 42, %b
   ret i8 %shl
 
 exit:
   ret i8 0
 }
 
 define i8 @test12(i8 %b) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[B:%.*]], 3
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 42, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i8 42, [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp ult i8 %b, 3
   br i1 %cmp, label %bb, label %exit
 

 }
 
 define i8 @test15(i8 %b) {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[B:%.*]], 2
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 -42, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nsw i8 -42, [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp ult i8 %b, 2
   br i1 %cmp, label %bb, label %exit
 

 }
 
 define i8 @test17(i8 %b) {
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[B:%.*]], 2
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 42, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i8 42, [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp slt i8 %b, 2
   br i1 %cmp, label %bb, label %exit
 
 bb:
   %shl = shl i8 42, %b
   ret i8 %shl
 
 exit:
   ret i8 0
 }
 
 define i8 @test18(i8 %b) {
 ; CHECK-LABEL: @test18(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[B:%.*]], 3
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 42, [[B]]
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i8 42, [[B]]
 ; CHECK-NEXT:    ret i8 [[SHL]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %cmp = icmp slt i8 %b, 3
   br i1 %cmp, label %bb, label %exit