Generalize the cast-of-addrec folding to handle folding of SCEVs like
(sext i8 {-128,+,1} to i64) to i64 {-128,+,1}, where the iteration
crosses from negative to positive, but is still safe if the trip
count is within range.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70421 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index b81df12..257186f 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -718,7 +718,7 @@
SCEVHandle BECount = getBackedgeTakenCount(AR->getLoop());
if (!isa<SCEVCouldNotCompute>(BECount)) {
// Manually compute the final value for AR, checking for
- // overflow at each step.
+ // overflow.
SCEVHandle Start = AR->getStart();
SCEVHandle Step = AR->getStepRecurrence(*this);
@@ -730,41 +730,34 @@
getTruncateOrZeroExtend(CastedBECount, BECount->getType())) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
+ // Check whether Start+Step*BECount has no unsigned overflow.
SCEVHandle ZMul =
getMulExpr(CastedBECount,
getTruncateOrZeroExtend(Step, Start->getType()));
- // Check whether Start+Step*BECount has no unsigned overflow.
- if (getZeroExtendExpr(ZMul, WideTy) ==
- getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
- getZeroExtendExpr(Step, WideTy))) {
- SCEVHandle Add = getAddExpr(Start, ZMul);
- if (getZeroExtendExpr(Add, WideTy) ==
- getAddExpr(getZeroExtendExpr(Start, WideTy),
- getZeroExtendExpr(ZMul, WideTy)))
- // Return the expression with the addrec on the outside.
- return getAddRecExpr(getZeroExtendExpr(Start, Ty),
- getZeroExtendExpr(Step, Ty),
- AR->getLoop());
- }
+ SCEVHandle Add = getAddExpr(Start, ZMul);
+ if (getZeroExtendExpr(Add, WideTy) ==
+ getAddExpr(getZeroExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
+ getZeroExtendExpr(Step, WideTy))))
+ // Return the expression with the addrec on the outside.
+ return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+ getZeroExtendExpr(Step, Ty),
+ AR->getLoop());
// Similar to above, only this time treat the step value as signed.
// This covers loops that count down.
SCEVHandle SMul =
getMulExpr(CastedBECount,
getTruncateOrSignExtend(Step, Start->getType()));
- // Check whether Start+Step*BECount has no unsigned overflow.
- if (getSignExtendExpr(SMul, WideTy) ==
- getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
- getSignExtendExpr(Step, WideTy))) {
- SCEVHandle Add = getAddExpr(Start, SMul);
- if (getZeroExtendExpr(Add, WideTy) ==
- getAddExpr(getZeroExtendExpr(Start, WideTy),
- getSignExtendExpr(SMul, WideTy)))
- // Return the expression with the addrec on the outside.
- return getAddRecExpr(getZeroExtendExpr(Start, Ty),
- getSignExtendExpr(Step, Ty),
- AR->getLoop());
- }
+ Add = getAddExpr(Start, SMul);
+ if (getZeroExtendExpr(Add, WideTy) ==
+ getAddExpr(getZeroExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
+ getSignExtendExpr(Step, WideTy))))
+ // Return the expression with the addrec on the outside.
+ return getAddRecExpr(getZeroExtendExpr(Start, Ty),
+ getSignExtendExpr(Step, Ty),
+ AR->getLoop());
}
}
}
@@ -807,37 +800,31 @@
SCEVHandle BECount = getBackedgeTakenCount(AR->getLoop());
if (!isa<SCEVCouldNotCompute>(BECount)) {
// Manually compute the final value for AR, checking for
- // overflow at each step.
+ // overflow.
SCEVHandle Start = AR->getStart();
SCEVHandle Step = AR->getStepRecurrence(*this);
// Check whether the backedge-taken count can be losslessly casted to
- // the addrec's type. The count needs to be the same whether sign
- // extended or zero extended.
+ // the addrec's type. The count is always unsigned.
SCEVHandle CastedBECount =
getTruncateOrZeroExtend(BECount, Start->getType());
if (BECount ==
- getTruncateOrZeroExtend(CastedBECount, BECount->getType()) &&
- BECount ==
- getTruncateOrSignExtend(CastedBECount, BECount->getType())) {
+ getTruncateOrZeroExtend(CastedBECount, BECount->getType())) {
const Type *WideTy =
IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
+ // Check whether Start+Step*BECount has no signed overflow.
SCEVHandle SMul =
getMulExpr(CastedBECount,
getTruncateOrSignExtend(Step, Start->getType()));
- // Check whether Start+Step*BECount has no signed overflow.
- if (getSignExtendExpr(SMul, WideTy) ==
- getMulExpr(getSignExtendExpr(CastedBECount, WideTy),
- getSignExtendExpr(Step, WideTy))) {
- SCEVHandle Add = getAddExpr(Start, SMul);
- if (getSignExtendExpr(Add, WideTy) ==
- getAddExpr(getSignExtendExpr(Start, WideTy),
- getSignExtendExpr(SMul, WideTy)))
- // Return the expression with the addrec on the outside.
- return getAddRecExpr(getSignExtendExpr(Start, Ty),
- getSignExtendExpr(Step, Ty),
- AR->getLoop());
- }
+ SCEVHandle Add = getAddExpr(Start, SMul);
+ if (getSignExtendExpr(Add, WideTy) ==
+ getAddExpr(getSignExtendExpr(Start, WideTy),
+ getMulExpr(getZeroExtendExpr(CastedBECount, WideTy),
+ getSignExtendExpr(Step, WideTy))))
+ // Return the expression with the addrec on the outside.
+ return getAddRecExpr(getSignExtendExpr(Start, Ty),
+ getSignExtendExpr(Step, Ty),
+ AR->getLoop());
}
}
}