This is an archive of the discontinued LLVM Phabricator instance.

Differential D69942

[ConstantRange][LVI] Use overflow flags from `sub` to constrain the range
ClosedPublic

Authored by lebedev.ri on Nov 7 2019, 4:22 AM.

Details

Reviewers
nikic
reames
spatel
Commits
rG69ce2ae990e7: [ConstantRange][LVI] Use overflow flags from `sub` to constrain the range
Summary

This notably improves non-negativity deduction:

| statistic                              |     old |     new | delta | % change |
| correlated-value-propagation.NumAShrs  |     209 |     227 |    18 |  8.6124% |
| correlated-value-propagation.NumAddNSW |    4972 |    4988 |    16 |  0.3218% |
| correlated-value-propagation.NumAddNUW |    7141 |    7148 |     7 |  0.0980% |
| correlated-value-propagation.NumAddNW  |   12113 |   12136 |    23 |  0.1899% |
| correlated-value-propagation.NumAnd    |     442 |     445 |     3 |  0.6787% |
| correlated-value-propagation.NumNSW    |    7160 |    7176 |    16 |  0.2235% |
| correlated-value-propagation.NumNUW    |   13306 |   13316 |    10 |  0.0752% |
| correlated-value-propagation.NumNW     |   20466 |   20492 |    26 |  0.1270% |
| correlated-value-propagation.NumSDivs  |     207 |     212 |     5 |  2.4155% |
| correlated-value-propagation.NumSExt   |    6279 |    6679 |   400 |  6.3704% |
| correlated-value-propagation.NumSRems  |      28 |      29 |     1 |  3.5714% |
| correlated-value-propagation.NumShlNUW |    2793 |    2796 |     3 |  0.1074% |
| correlated-value-propagation.NumShlNW  |    3964 |    3967 |     3 |  0.0757% |
| correlated-value-propagation.NumUDivs  |     353 |     358 |     5 |  1.4164% |
| instcount.NumAShrInst                  |   13763 |   13741 |   -22 | -0.1598% |
| instcount.NumAddInst                   |  277349 |  277348 |    -1 | -0.0004% |
| instcount.NumLShrInst                  |   27437 |   27463 |    26 |  0.0948% |
| instcount.NumOrInst                    |  102677 |  102678 |     1 |  0.0010% |
| instcount.NumSDivInst                  |    8732 |    8727 |    -5 | -0.0573% |
| instcount.NumSExtInst                  |   80872 |   80468 |  -404 | -0.4996% |
| instcount.NumSRemInst                  |    1679 |    1678 |    -1 | -0.0596% |
| instcount.NumTruncInst                 |   62154 |   62153 |    -1 | -0.0016% |
| instcount.NumUDivInst                  |    2526 |    2527 |     1 |  0.0396% |
| instcount.NumURemInst                  |    1589 |    1590 |     1 |  0.0629% |
| instcount.NumZExtInst                  |   69405 |   69809 |   404 |  0.5821% |
| instcount.TotalInsts                   | 7439575 | 7439574 |    -1 |  0.0000% |

Diff Detail

Event Timeline

lebedev.ri created this revision.Nov 7 2019, 4:22 AM
Herald added a subscriber: hiraditya. · View Herald TranscriptNov 7 2019, 4:22 AM
nikic accepted this revision.Nov 7 2019, 5:10 AM

LGTM

This revision is now accepted and ready to land.Nov 7 2019, 5:10 AM
lebedev.ri added a comment.Nov 7 2019, 5:18 AM
In D69942#1736906, @nikic wrote:

LGTM

Thank you for the review.
Looking into mul/shl, will need to add ConstantRange::[us]{mul,shl}_sat() at the same time.

Closed by commit rG69ce2ae990e7: [ConstantRange][LVI] Use overflow flags from `sub` to constrain the range (authored by lebedev.ri). · Explain WhyNov 7 2019, 5:23 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
lib/
IR/
2 lines
test/
Transforms/
CorrelatedValuePropagation/
8 lines

Diff 228224

llvm/lib/IR/ConstantRange.cpp

Show First 20 Lines • Show All 818 Lines • ▼ Show 20 Lines
ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp, ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp,
const ConstantRange &Other, const ConstantRange &Other,
unsigned NoWrapKind) const { unsigned NoWrapKind) const {
assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
switch (BinOp) { switch (BinOp) {
case Instruction::Add: case Instruction::Add:
return addWithNoWrap(Other, NoWrapKind); return addWithNoWrap(Other, NoWrapKind);
case Instruction::Sub:
return subWithNoWrap(Other, NoWrapKind);
default: default:
// Don't know about this Overflowing Binary Operation. // Don't know about this Overflowing Binary Operation.
// Conservatively fallback to plain binop handling. // Conservatively fallback to plain binop handling.
return binaryOp(BinOp, Other); return binaryOp(BinOp, Other);
} }
} }
ConstantRange ConstantRange
▲ Show 20 Lines • Show All 686 Lines • Show Last 20 Lines

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

Show First 20 Lines • Show All 484 Lines • ▼ Show 20 Lines
; CHECK-NEXT: [[CMP0:%.*]] = icmp sge i32 [[A:%.*]], 0 ; CHECK-NEXT: [[CMP0:%.*]] = icmp sge i32 [[A:%.*]], 0
; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i32 [[B:%.*]], 0 ; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i32 [[B:%.*]], 0
; CHECK-NEXT: [[BR:%.*]] = and i1 [[CMP0]], [[CMP1]] ; CHECK-NEXT: [[BR:%.*]] = and i1 [[CMP0]], [[CMP1]]
; CHECK-NEXT: br i1 [[BR]], label [[BB:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[BR]], label [[BB:%.*]], label [[EXIT:%.*]]
; CHECK: bb: ; CHECK: bb:
; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 [[A]], [[B]] ; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 [[A]], [[B]]
; CHECK-NEXT: br label [[CONT:%.*]] ; CHECK-NEXT: br label [[CONT:%.*]]
; CHECK: cont: ; CHECK: cont:
; CHECK-NEXT: [[RES:%.*]] = icmp sge i32 [[SUB]], 0
; CHECK-NEXT: br label [[EXIT]] ; CHECK-NEXT: br label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[IV:%.*]] = phi i1 [ true, [[BEGIN:%.*]] ], [ [[RES]], [[CONT]] ] ; CHECK-NEXT: ret i1 true
; CHECK-NEXT: ret i1 [[IV]]
; ;
begin: begin:
%cmp0 = icmp sge i32 %a, 0 %cmp0 = icmp sge i32 %a, 0
%cmp1 = icmp sge i32 %b, 0 %cmp1 = icmp sge i32 %b, 0
%br = and i1 %cmp0, %cmp1 %br = and i1 %cmp0, %cmp1
br i1 %br, label %bb, label %exit br i1 %br, label %bb, label %exit
bb: bb:
▲ Show 20 Lines • Show All 87 Lines • ▼ Show 20 Lines
; CHECK-NEXT: [[CMP0:%.*]] = icmp sle i32 [[A:%.*]], 0 ; CHECK-NEXT: [[CMP0:%.*]] = icmp sle i32 [[A:%.*]], 0
; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i32 [[B:%.*]], 0 ; CHECK-NEXT: [[CMP1:%.*]] = icmp sge i32 [[B:%.*]], 0
; CHECK-NEXT: [[BR:%.*]] = and i1 [[CMP0]], [[CMP1]] ; CHECK-NEXT: [[BR:%.*]] = and i1 [[CMP0]], [[CMP1]]
; CHECK-NEXT: br i1 [[BR]], label [[BB:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[BR]], label [[BB:%.*]], label [[EXIT:%.*]]
; CHECK: bb: ; CHECK: bb:
; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[A]], [[B]] ; CHECK-NEXT: [[SUB:%.*]] = sub nsw i32 [[A]], [[B]]
; CHECK-NEXT: br label [[CONT:%.*]] ; CHECK-NEXT: br label [[CONT:%.*]]
; CHECK: cont: ; CHECK: cont:
; CHECK-NEXT: [[RES:%.*]] = icmp sle i32 [[SUB]], 0
; CHECK-NEXT: br label [[EXIT]] ; CHECK-NEXT: br label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[IV:%.*]] = phi i1 [ true, [[BEGIN:%.*]] ], [ [[RES]], [[CONT]] ] ; CHECK-NEXT: ret i1 true
; CHECK-NEXT: ret i1 [[IV]]
; ;
begin: begin:
%cmp0 = icmp sle i32 %a, 0 %cmp0 = icmp sle i32 %a, 0
%cmp1 = icmp sge i32 %b, 0 %cmp1 = icmp sge i32 %b, 0
%br = and i1 %cmp0, %cmp1 %br = and i1 %cmp0, %cmp1
br i1 %br, label %bb, label %exit br i1 %br, label %bb, label %exit
bb: bb:
Show All 13 Lines