From 7cd7f4a83b7a4ab852734ad9188dde14dcfb5072 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Mon, 21 Oct 2019 21:31:19 +0000 Subject: [PATCH] [CVP] No-wrap deduction for `shl` 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% | Reviewers: nikic, reames, sanjoy, timshen Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69277 llvm-svn: 375455 --- .../Scalar/CorrelatedValuePropagation.cpp | 9 +++++++++ .../Transforms/CorrelatedValuePropagation/icmp.ll | 4 ++-- .../Transforms/CorrelatedValuePropagation/shl.ll | 22 +++++++++++----------- 3 files changed, 22 insertions(+), 13 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index 6be715c..2ef8526 100644 --- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -76,6 +76,9 @@ 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"); @@ -450,6 +453,11 @@ static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode, 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"); } @@ -861,6 +869,7 @@ static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT, case Instruction::Add: case Instruction::Sub: case Instruction::Mul: + case Instruction::Shl: BBChanged |= processBinOp(cast(II), LVI); break; case Instruction::And: diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll b/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll index 3b0f33a..7f28dad 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll @@ -173,7 +173,7 @@ define i1 @test5(i32 %x, i32 %y) #0 { ; 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]] @@ -212,7 +212,7 @@ define i1 @test6(i32 %x, i32 %y) #0 { ; 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 diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/shl.ll b/llvm/test/Transforms/CorrelatedValuePropagation/shl.ll index 81d26c9..0514ec9 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/shl.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/shl.ll @@ -85,7 +85,7 @@ define i8 @test4(i8 %a, i8 %b) { ; 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 @@ -104,7 +104,7 @@ exit: 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 @@ -113,7 +113,7 @@ define i8 @test5(i8 %b) { 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 @@ -126,7 +126,7 @@ define i8 @test7(i8 %b) { ; 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 @@ -145,7 +145,7 @@ exit: 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 @@ -158,7 +158,7 @@ define i8 @test9(i8 %b) { ; 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 @@ -190,7 +190,7 @@ define i8 @test11(i8 %b) { ; 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 @@ -213,7 +213,7 @@ define i8 @test12(i8 %b) { ; 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 @@ -268,7 +268,7 @@ define i8 @test15(i8 %b) { ; 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 @@ -314,7 +314,7 @@ define i8 @test17(i8 %b) { ; 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 @@ -337,7 +337,7 @@ define i8 @test18(i8 %b) { ; 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 -- 2.7.4