Skip to content

Commit 8550fb3

Browse files
nikicnikic
committedJun 15, 2019
[SCEV] Use unsigned/signed intersection type in SCEV
Based on D59959, this switches SCEV to use unsigned/signed range intersection based on the sign hint. This will prefer non-wrapping ranges in the relevant domain. I've left the one intersection in getRangeForAffineAR() to use the smallest intersection heuristic, as there doesn't seem to be any obvious preference there. Differential Revision: https://reviews.llvm.org/D60035 llvm-svn: 363490
1 parent 9145562 commit 8550fb3

File tree

6 files changed

+43
-30
lines changed

6 files changed

+43
-30
lines changed
 

‎llvm/lib/Analysis/ScalarEvolution.cpp

+32-19
Original file line numberDiff line numberDiff line change
@@ -5535,6 +5535,9 @@ ScalarEvolution::getRangeRef(const SCEV *S,
55355535
DenseMap<const SCEV *, ConstantRange> &Cache =
55365536
SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges
55375537
: SignedRanges;
5538+
ConstantRange::PreferredRangeType RangeType =
5539+
SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED
5540+
? ConstantRange::Unsigned : ConstantRange::Signed;
55385541

55395542
// See if we've computed this range already.
55405543
DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S);
@@ -5565,53 +5568,60 @@ ScalarEvolution::getRangeRef(const SCEV *S,
55655568
ConstantRange X = getRangeRef(Add->getOperand(0), SignHint);
55665569
for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
55675570
X = X.add(getRangeRef(Add->getOperand(i), SignHint));
5568-
return setRange(Add, SignHint, ConservativeResult.intersectWith(X));
5571+
return setRange(Add, SignHint,
5572+
ConservativeResult.intersectWith(X, RangeType));
55695573
}
55705574

55715575
if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
55725576
ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint);
55735577
for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
55745578
X = X.multiply(getRangeRef(Mul->getOperand(i), SignHint));
5575-
return setRange(Mul, SignHint, ConservativeResult.intersectWith(X));
5579+
return setRange(Mul, SignHint,
5580+
ConservativeResult.intersectWith(X, RangeType));
55765581
}
55775582

55785583
if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
55795584
ConstantRange X = getRangeRef(SMax->getOperand(0), SignHint);
55805585
for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
55815586
X = X.smax(getRangeRef(SMax->getOperand(i), SignHint));
5582-
return setRange(SMax, SignHint, ConservativeResult.intersectWith(X));
5587+
return setRange(SMax, SignHint,
5588+
ConservativeResult.intersectWith(X, RangeType));
55835589
}
55845590

55855591
if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
55865592
ConstantRange X = getRangeRef(UMax->getOperand(0), SignHint);
55875593
for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
55885594
X = X.umax(getRangeRef(UMax->getOperand(i), SignHint));
5589-
return setRange(UMax, SignHint, ConservativeResult.intersectWith(X));
5595+
return setRange(UMax, SignHint,
5596+
ConservativeResult.intersectWith(X, RangeType));
55905597
}
55915598

55925599
if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
55935600
ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint);
55945601
ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint);
55955602
return setRange(UDiv, SignHint,
5596-
ConservativeResult.intersectWith(X.udiv(Y)));
5603+
ConservativeResult.intersectWith(X.udiv(Y), RangeType));
55975604
}
55985605

55995606
if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
56005607
ConstantRange X = getRangeRef(ZExt->getOperand(), SignHint);
56015608
return setRange(ZExt, SignHint,
5602-
ConservativeResult.intersectWith(X.zeroExtend(BitWidth)));
5609+
ConservativeResult.intersectWith(X.zeroExtend(BitWidth),
5610+
RangeType));
56035611
}
56045612

56055613
if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
56065614
ConstantRange X = getRangeRef(SExt->getOperand(), SignHint);
56075615
return setRange(SExt, SignHint,
5608-
ConservativeResult.intersectWith(X.signExtend(BitWidth)));
5616+
ConservativeResult.intersectWith(X.signExtend(BitWidth),
5617+
RangeType));
56095618
}
56105619

56115620
if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
56125621
ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint);
56135622
return setRange(Trunc, SignHint,
5614-
ConservativeResult.intersectWith(X.truncate(BitWidth)));
5623+
ConservativeResult.intersectWith(X.truncate(BitWidth),
5624+
RangeType));
56155625
}
56165626

56175627
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
@@ -5621,7 +5631,7 @@ ScalarEvolution::getRangeRef(const SCEV *S,
56215631
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
56225632
if (!C->getValue()->isZero())
56235633
ConservativeResult = ConservativeResult.intersectWith(
5624-
ConstantRange(C->getAPInt(), APInt(BitWidth, 0)));
5634+
ConstantRange(C->getAPInt(), APInt(BitWidth, 0)), RangeType);
56255635

56265636
// If there's no signed wrap, and all the operands have the same sign or
56275637
// zero, the value won't ever change sign.
@@ -5635,11 +5645,11 @@ ScalarEvolution::getRangeRef(const SCEV *S,
56355645
if (AllNonNeg)
56365646
ConservativeResult = ConservativeResult.intersectWith(
56375647
ConstantRange(APInt(BitWidth, 0),
5638-
APInt::getSignedMinValue(BitWidth)));
5648+
APInt::getSignedMinValue(BitWidth)), RangeType);
56395649
else if (AllNonPos)
56405650
ConservativeResult = ConservativeResult.intersectWith(
56415651
ConstantRange(APInt::getSignedMinValue(BitWidth),
5642-
APInt(BitWidth, 1)));
5652+
APInt(BitWidth, 1)), RangeType);
56435653
}
56445654

56455655
// TODO: non-affine addrec
@@ -5652,14 +5662,14 @@ ScalarEvolution::getRangeRef(const SCEV *S,
56525662
BitWidth);
56535663
if (!RangeFromAffine.isFullSet())
56545664
ConservativeResult =
5655-
ConservativeResult.intersectWith(RangeFromAffine);
5665+
ConservativeResult.intersectWith(RangeFromAffine, RangeType);
56565666

56575667
auto RangeFromFactoring = getRangeViaFactoring(
56585668
AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
56595669
BitWidth);
56605670
if (!RangeFromFactoring.isFullSet())
56615671
ConservativeResult =
5662-
ConservativeResult.intersectWith(RangeFromFactoring);
5672+
ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
56635673
}
56645674
}
56655675

@@ -5670,7 +5680,8 @@ ScalarEvolution::getRangeRef(const SCEV *S,
56705680
// Check if the IR explicitly contains !range metadata.
56715681
Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue());
56725682
if (MDRange.hasValue())
5673-
ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue());
5683+
ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue(),
5684+
RangeType);
56745685

56755686
// Split here to avoid paying the compile-time cost of calling both
56765687
// computeKnownBits and ComputeNumSignBits. This restriction can be lifted
@@ -5681,16 +5692,17 @@ ScalarEvolution::getRangeRef(const SCEV *S,
56815692
KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
56825693
if (Known.One != ~Known.Zero + 1)
56835694
ConservativeResult =
5684-
ConservativeResult.intersectWith(ConstantRange(Known.One,
5685-
~Known.Zero + 1));
5695+
ConservativeResult.intersectWith(
5696+
ConstantRange(Known.One, ~Known.Zero + 1), RangeType);
56865697
} else {
56875698
assert(SignHint == ScalarEvolution::HINT_RANGE_SIGNED &&
56885699
"generalize as needed!");
56895700
unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
56905701
if (NS > 1)
56915702
ConservativeResult = ConservativeResult.intersectWith(
56925703
ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
5693-
APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1));
5704+
APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1),
5705+
RangeType);
56945706
}
56955707

56965708
// A range of Phi is a subset of union of all ranges of its input.
@@ -5705,7 +5717,8 @@ ScalarEvolution::getRangeRef(const SCEV *S,
57055717
if (RangeFromOps.isFullSet())
57065718
break;
57075719
}
5708-
ConservativeResult = ConservativeResult.intersectWith(RangeFromOps);
5720+
ConservativeResult =
5721+
ConservativeResult.intersectWith(RangeFromOps, RangeType);
57095722
bool Erased = PendingPhiRanges.erase(Phi);
57105723
assert(Erased && "Failed to erase Phi properly?");
57115724
(void) Erased;
@@ -5812,7 +5825,7 @@ ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
58125825
MaxBECountValue, BitWidth, /* Signed = */ false);
58135826

58145827
// Finally, intersect signed and unsigned ranges.
5815-
return SR.intersectWith(UR);
5828+
return SR.intersectWith(UR, ConstantRange::Smallest);
58165829
}
58175830

58185831
ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start,

‎llvm/test/Analysis/ScalarEvolution/extract-highbits-sameconstmask.ll

+3-3
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ define i32 @div(i32 %val) nounwind {
88
; CHECK-NEXT: %tmp1 = udiv i32 %val, 16
99
; CHECK-NEXT: --> (%val /u 16) U: [0,268435456) S: [0,268435456)
1010
; CHECK-NEXT: %tmp2 = mul i32 %tmp1, 16
11-
; CHECK-NEXT: --> (16 * (%val /u 16))<nuw> U: [0,-15) S: [0,-15)
11+
; CHECK-NEXT: --> (16 * (%val /u 16))<nuw> U: [0,-15) S: [-2147483648,2147483633)
1212
; CHECK-NEXT: Determining loop execution counts for: @div
1313
;
1414
%tmp1 = udiv i32 %val, 16
@@ -38,7 +38,7 @@ define i32 @mask_b(i32 %val) nounwind {
3838
; CHECK-LABEL: 'mask_b'
3939
; CHECK-NEXT: Classifying expressions for: @mask_b
4040
; CHECK-NEXT: %masked = and i32 %val, -16
41-
; CHECK-NEXT: --> (16 * (%val /u 16))<nuw> U: [0,-15) S: [0,-15)
41+
; CHECK-NEXT: --> (16 * (%val /u 16))<nuw> U: [0,-15) S: [-2147483648,2147483633)
4242
; CHECK-NEXT: Determining loop execution counts for: @mask_b
4343
;
4444
%masked = and i32 %val, -16
@@ -51,7 +51,7 @@ define i32 @mask_d(i32 %val) nounwind {
5151
; CHECK-NEXT: %lowbitscleared = lshr i32 %val, 4
5252
; CHECK-NEXT: --> (%val /u 16) U: [0,268435456) S: [0,268435456)
5353
; CHECK-NEXT: %masked = shl i32 %lowbitscleared, 4
54-
; CHECK-NEXT: --> (16 * (%val /u 16))<nuw> U: [0,-15) S: [0,-15)
54+
; CHECK-NEXT: --> (16 * (%val /u 16))<nuw> U: [0,-15) S: [-2147483648,2147483633)
5555
; CHECK-NEXT: Determining loop execution counts for: @mask_d
5656
;
5757
%lowbitscleared = lshr i32 %val, 4

‎llvm/test/Analysis/ScalarEvolution/increasing-or-decreasing-iv.ll

+4-4
Original file line numberDiff line numberDiff line change
@@ -58,15 +58,15 @@ loop:
5858
; CHECK: %iv.m1 = sub i32 %iv, 1
5959
; CHECK-NEXT: --> {(-1 + %start)<nsw>,+,%step}<%loop> U: [-1,120) S: [-1,120)
6060
; CHECK: %iv.m2 = sub i32 %iv, 2
61-
; CHECK-NEXT: --> {(-2 + %start)<nsw>,+,%step}<%loop> U: [-2,119) S: [-2,119)
61+
; CHECK-NEXT: --> {(-2 + %start)<nsw>,+,%step}<%loop> U: [0,-1) S: [-2,119)
6262
; CHECK: %iv.m3 = sub i32 %iv, 3
6363
; CHECK-NEXT: --> {(-3 + %start)<nsw>,+,%step}<%loop> U: [-3,118) S: [-3,118)
6464
; CHECK: %iv.m4 = sub i32 %iv, 4
65-
; CHECK-NEXT: --> {(-4 + %start)<nsw>,+,%step}<%loop> U: [-4,117) S: [-4,117)
65+
; CHECK-NEXT: --> {(-4 + %start)<nsw>,+,%step}<%loop> U: [0,-3) S: [-4,117)
6666
; CHECK: %iv.m5 = sub i32 %iv, 5
6767
; CHECK-NEXT: --> {(-5 + %start)<nsw>,+,%step}<%loop> U: [-5,116) S: [-5,116)
6868
; CHECK: %iv.m6 = sub i32 %iv, 6
69-
; CHECK-NEXT: --> {(-6 + %start)<nsw>,+,%step}<%loop> U: [-6,115) S: [-6,115)
69+
; CHECK-NEXT: --> {(-6 + %start)<nsw>,+,%step}<%loop> U: [0,-1) S: [-6,115)
7070
; CHECK: %iv.m7 = sub i32 %iv, 7
7171
; CHECK-NEXT: --> {(-7 + %start)<nsw>,+,%step}<%loop> U: [-7,114) S: [-7,114)
7272

@@ -206,7 +206,7 @@ loop:
206206
%iv.next = add i32 %iv, %step.plus.one
207207
%iv.sext = sext i32 %iv to i64
208208
; CHECK: %iv.sext = sext i32 %iv to i64
209-
; CHECK-NEXT: --> {(sext i32 %start to i64),+,(1 + (sext i32 %step to i64))<nsw>}<nsw><%loop> U: [0,128) S: [0,128)
209+
; CHECK-NEXT: --> {(sext i32 %start to i64),+,(1 + (sext i32 %step to i64))<nuw><nsw>}<nsw><%loop> U: [0,128) S: [0,128)
210210
%loop.iv.inc = add i16 %loop.iv, 1
211211
%be.cond = icmp ne i16 %loop.iv.inc, 128
212212
br i1 %be.cond, label %loop, label %leave

‎llvm/test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ define void @infer.sext.1(i32 %start, i1* %c) {
5959
%idx = phi i32 [ %start.real, %entry ], [ %idx.inc, %loop ]
6060
%idx.sext = sext i32 %idx to i64
6161
; CHECK: %idx.sext = sext i32 %idx to i64
62-
; CHECK-NEXT: --> {(2 + (sext i32 (4 * %start) to i64))<nsw>,+,2}<nsw><%loop>
62+
; CHECK-NEXT: --> {(2 + (sext i32 (4 * %start) to i64))<nuw><nsw>,+,2}<nsw><%loop>
6363
%idx.inc = add nsw i32 %idx, 2
6464
%condition = load i1, i1* %c
6565
br i1 %condition, label %exit, label %loop

‎llvm/test/Analysis/ScalarEvolution/lshr-shl-differentconstmask.ll

+1-1
Original file line numberDiff line numberDiff line change
@@ -121,7 +121,7 @@ define i32 @masky_biggerShr(i32 %val) {
121121
; CHECK-NEXT: %tmp1 = shl i32 %val, 2
122122
; CHECK-NEXT: --> (4 * %val) U: [0,-3) S: [-2147483648,2147483645)
123123
; CHECK-NEXT: %tmp2 = and i32 %tmp1, -64
124-
; CHECK-NEXT: --> (64 * (zext i26 (trunc i32 (%val /u 16) to i26) to i32))<nuw> U: [0,-63) S: [0,-63)
124+
; CHECK-NEXT: --> (64 * (zext i26 (trunc i32 (%val /u 16) to i26) to i32))<nuw> U: [0,-63) S: [-2147483648,2147483585)
125125
; CHECK-NEXT: Determining loop execution counts for: @masky_biggerShr
126126
;
127127
%tmp1 = shl i32 %val, 2

‎llvm/test/Analysis/ScalarEvolution/sext-mul.ll

+2-2
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
; CHECK: %tmp11 = getelementptr inbounds i32, i32* %arg, i64 %tmp10
88
; CHECK-NEXT: --> {{.*}} Exits: ((4 * (sext i32 (-2 + (2 * %arg2)) to i64))<nsw> + %arg)
99
; CHECK: %tmp14 = or i64 %tmp10, 1
10-
; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i32 (-2 + (2 * %arg2)) to i64))<nsw>
10+
; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i32 (-2 + (2 * %arg2)) to i64))<nuw><nsw>
1111
; CHECK: %tmp15 = getelementptr inbounds i32, i32* %arg, i64 %tmp14
1212
; CHECK-NEXT: --> {{.*}} Exits: (4 + (4 * (sext i32 (-2 + (2 * %arg2)) to i64))<nsw> + %arg)
1313
; CHECK:Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg2 to i64))<nsw>
@@ -50,7 +50,7 @@ bb7: ; preds = %bb7, %bb3
5050
; CHECK: %t10 = ashr exact i128 %t9, 1
5151
; CHECK-NEXT: --> {{.*}} Exits: (sext i127 (-633825300114114700748351602688 + (633825300114114700748351602688 * (zext i32 %arg5 to i127))) to i128)
5252
; CHECK: %t14 = or i128 %t10, 1
53-
; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i127 (-633825300114114700748351602688 + (633825300114114700748351602688 * (zext i32 %arg5 to i127))) to i128))<nsw>
53+
; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i127 (-633825300114114700748351602688 + (633825300114114700748351602688 * (zext i32 %arg5 to i127))) to i128))<nuw><nsw>
5454
; CHECK: Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg5 to i128))<nsw>
5555
; CHECK-NEXT: Loop %bb7: max backedge-taken count is -1
5656
; CHECK-NEXT: Loop %bb7: Predicated backedge-taken count is (-1 + (zext i32 %arg5 to i128))<nsw>

0 commit comments

Comments
 (0)
Please sign in to comment.