Expand GEPs in ScalarEvolution expressions. SCEV expressions can now
have pointer types, though in contrast to C pointer types, SCEV
addition is never implicitly scaled. This not only eliminates the
need for special code like IndVars' EliminatePointerRecurrence
and LSR's own GEP expansion code, it also does a better job because
it lets the normal optimizations handle pointer expressions just
like integer expressions.
Also, since LLVM IR GEPs can't directly index into multi-dimensional
VLAs, moving the GEP analysis out of client code and into the SCEV
framework makes it easier for clients to handle multi-dimensional
VLAs the same way as other arrays.
Some existing regression tests show improved optimization.
test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to
the point where if-conversion started kicking in; I turned it off
for this test to preserve the intent of the test.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69258 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index c979613..01c9574 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -50,6 +50,7 @@
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
+#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/SmallVector.h"
@@ -59,7 +60,6 @@
using namespace llvm;
STATISTIC(NumRemoved , "Number of aux indvars removed");
-STATISTIC(NumPointer , "Number of pointer indvars promoted");
STATISTIC(NumInserted, "Number of canonical indvars added");
STATISTIC(NumReplaced, "Number of exit values replaced");
STATISTIC(NumLFTR , "Number of loop exit tests replaced");
@@ -67,6 +67,7 @@
namespace {
class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
LoopInfo *LI;
+ TargetData *TD;
ScalarEvolution *SE;
bool Changed;
public:
@@ -81,6 +82,7 @@
AU.addRequiredID(LCSSAID);
AU.addRequiredID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
+ AU.addRequired<TargetData>();
AU.addPreserved<ScalarEvolution>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreservedID(LCSSAID);
@@ -91,8 +93,6 @@
void RewriteNonIntegerIVs(Loop *L);
- void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader,
- SmallPtrSet<Instruction*, 16> &DeadInsts);
void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
@@ -135,97 +135,6 @@
}
}
-
-/// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer
-/// recurrence. If so, change it into an integer recurrence, permitting
-/// analysis by the SCEV routines.
-void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
- BasicBlock *Preheader,
- SmallPtrSet<Instruction*, 16> &DeadInsts) {
- assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!");
- unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
- unsigned BackedgeIdx = PreheaderIdx^1;
- if (GetElementPtrInst *GEPI =
- dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
- if (GEPI->getOperand(0) == PN) {
- assert(GEPI->getNumOperands() == 2 && "GEP types must match!");
- DOUT << "INDVARS: Eliminating pointer recurrence: " << *GEPI;
-
- // Okay, we found a pointer recurrence. Transform this pointer
- // recurrence into an integer recurrence. Compute the value that gets
- // added to the pointer at every iteration.
- Value *AddedVal = GEPI->getOperand(1);
-
- // Insert a new integer PHI node into the top of the block.
- PHINode *NewPhi = PHINode::Create(AddedVal->getType(),
- PN->getName()+".rec", PN);
- NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader);
-
- // Create the new add instruction.
- Value *NewAdd = BinaryOperator::CreateAdd(NewPhi, AddedVal,
- GEPI->getName()+".rec", GEPI);
- NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx));
-
- // Update the existing GEP to use the recurrence.
- GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx));
-
- // Update the GEP to use the new recurrence we just inserted.
- GEPI->setOperand(1, NewAdd);
-
- // If the incoming value is a constant expr GEP, try peeling out the array
- // 0 index if possible to make things simpler.
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0)))
- if (CE->getOpcode() == Instruction::GetElementPtr) {
- unsigned NumOps = CE->getNumOperands();
- assert(NumOps > 1 && "CE folding didn't work!");
- if (CE->getOperand(NumOps-1)->isNullValue()) {
- // Check to make sure the last index really is an array index.
- gep_type_iterator GTI = gep_type_begin(CE);
- for (unsigned i = 1, e = CE->getNumOperands()-1;
- i != e; ++i, ++GTI)
- /*empty*/;
- if (isa<SequentialType>(*GTI)) {
- // Pull the last index out of the constant expr GEP.
- SmallVector<Value*, 8> CEIdxs(CE->op_begin()+1, CE->op_end()-1);
- Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0),
- &CEIdxs[0],
- CEIdxs.size());
- Value *Idx[2];
- Idx[0] = Constant::getNullValue(Type::Int32Ty);
- Idx[1] = NewAdd;
- GetElementPtrInst *NGEPI = GetElementPtrInst::Create(
- NCE, Idx, Idx + 2,
- GEPI->getName(), GEPI);
- SE->deleteValueFromRecords(GEPI);
- GEPI->replaceAllUsesWith(NGEPI);
- GEPI->eraseFromParent();
- GEPI = NGEPI;
- }
- }
- }
-
-
- // Finally, if there are any other users of the PHI node, we must
- // insert a new GEP instruction that uses the pre-incremented version
- // of the induction amount.
- if (!PN->use_empty()) {
- BasicBlock::iterator InsertPos = PN; ++InsertPos;
- while (isa<PHINode>(InsertPos)) ++InsertPos;
- Value *PreInc =
- GetElementPtrInst::Create(PN->getIncomingValue(PreheaderIdx),
- NewPhi, "", InsertPos);
- PreInc->takeName(PN);
- PN->replaceAllUsesWith(PreInc);
- }
-
- // Delete the old PHI for sure, and the GEP if its otherwise unused.
- DeadInsts.insert(PN);
-
- ++NumPointer;
- Changed = true;
- }
-}
-
/// LinearFunctionTestReplace - This method rewrites the exit condition of the
/// loop to be a canonical != comparison against the incremented loop induction
/// variable. This pass is able to rewrite the exit tests of any loop where the
@@ -275,7 +184,7 @@
// Expand the code for the iteration count into the preheader of the loop.
BasicBlock *Preheader = L->getLoopPreheader();
- Value *ExitCnt = Rewriter.expandCodeFor(RHS,
+ Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(),
Preheader->getTerminator());
// Insert a new icmp_ne or icmp_eq instruction before the branch.
@@ -307,7 +216,7 @@
// Scan all of the instructions in the loop, looking at those that have
// extra-loop users and which are recurrences.
- SCEVExpander Rewriter(*SE, *LI);
+ SCEVExpander Rewriter(*SE, *LI, *TD);
// We insert the code into the preheader of the loop if the loop contains
// multiple exit blocks, or in the exit block if there is exactly one.
@@ -349,7 +258,8 @@
Value *InVal = PN->getIncomingValue(i);
if (!isa<Instruction>(InVal) ||
// SCEV only supports integer expressions for now.
- !isa<IntegerType>(InVal->getType()))
+ (!isa<IntegerType>(InVal->getType()) &&
+ !isa<PointerType>(InVal->getType())))
continue;
// If this pred is for a subloop, not L itself, skip it.
@@ -384,7 +294,7 @@
// just reuse it.
Value *&ExitVal = ExitValues[Inst];
if (!ExitVal)
- ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt);
+ ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt);
DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
<< " LoopVal = " << *Inst << "\n";
@@ -413,23 +323,19 @@
}
void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
- // First step. Check to see if there are any trivial GEP pointer recurrences.
+ // First step. Check to see if there are any floating-point recurrences.
// If there are, change them into integer recurrences, permitting analysis by
// the SCEV routines.
//
BasicBlock *Header = L->getHeader();
- BasicBlock *Preheader = L->getLoopPreheader();
SmallPtrSet<Instruction*, 16> DeadInsts;
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
- if (isa<PointerType>(PN->getType()))
- EliminatePointerRecurrence(PN, Preheader, DeadInsts);
- else
- HandleFloatingPointIV(L, PN, DeadInsts);
+ HandleFloatingPointIV(L, PN, DeadInsts);
}
- // If the loop previously had a pointer or floating-point IV, ScalarEvolution
+ // If the loop previously had floating-point IV, ScalarEvolution
// may not have been able to compute a trip count. Now that we've done some
// re-writing, the trip count may be computable.
if (Changed)
@@ -442,7 +348,8 @@
/// getEffectiveIndvarType - Determine the widest type that the
/// induction-variable PHINode Phi is cast to.
///
-static const Type *getEffectiveIndvarType(const PHINode *Phi) {
+static const Type *getEffectiveIndvarType(const PHINode *Phi,
+ const TargetData *TD) {
const Type *Ty = Phi->getType();
for (Value::use_const_iterator UI = Phi->use_begin(), UE = Phi->use_end();
@@ -453,8 +360,7 @@
else if (const SExtInst *SI = dyn_cast<SExtInst>(UI))
CandidateType = SI->getDestTy();
if (CandidateType &&
- CandidateType->getPrimitiveSizeInBits() >
- Ty->getPrimitiveSizeInBits())
+ TD->getTypeSizeInBits(CandidateType) > TD->getTypeSizeInBits(Ty))
Ty = CandidateType;
}
@@ -482,6 +388,7 @@
static const PHINode *TestOrigIVForWrap(const Loop *L,
const BranchInst *BI,
const Instruction *OrigCond,
+ const TargetData *TD,
bool &NoSignedWrap,
bool &NoUnsignedWrap,
const ConstantInt* &InitialVal,
@@ -554,7 +461,7 @@
if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) {
if (!isa<ConstantInt>(CmpRHS) ||
!cast<ConstantInt>(CmpRHS)->getValue()
- .isSignedIntN(IncrInst->getType()->getPrimitiveSizeInBits()))
+ .isSignedIntN(TD->getTypeSizeInBits(IncrInst->getType())))
return 0;
IncrInst = SI->getOperand(0);
}
@@ -562,7 +469,7 @@
if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) {
if (!isa<ConstantInt>(CmpRHS) ||
!cast<ConstantInt>(CmpRHS)->getValue()
- .isIntN(IncrInst->getType()->getPrimitiveSizeInBits()))
+ .isIntN(TD->getTypeSizeInBits(IncrInst->getType())))
return 0;
IncrInst = ZI->getOperand(0);
}
@@ -643,7 +550,7 @@
SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
if (LargestType != myType)
ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, InsertPt);
+ return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt);
}
static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR,
@@ -660,7 +567,7 @@
SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
if (LargestType != myType)
ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, InsertPt);
+ return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt);
}
/// allUsesAreSameTyped - See whether all Uses of I are instructions
@@ -682,10 +589,11 @@
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
LI = &getAnalysis<LoopInfo>();
+ TD = &getAnalysis<TargetData>();
SE = &getAnalysis<ScalarEvolution>();
Changed = false;
- // If there are any floating-point or pointer recurrences, attempt to
+ // If there are any floating-point recurrences, attempt to
// transform them to use integer recurrences.
RewriteNonIntegerIVs(L);
@@ -712,7 +620,7 @@
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
- if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable!
+ if (PN->getType()->isInteger() || isa<PointerType>(PN->getType())) {
SCEVHandle SCEV = SE->getSCEV(PN);
// FIXME: It is an extremely bad idea to indvar substitute anything more
// complex than affine induction variables. Doing so will put expensive
@@ -731,21 +639,26 @@
SmallSetVector<const Type *, 4> SizesToInsert;
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
LargestType = BackedgeTakenCount->getType();
- SizesToInsert.insert(BackedgeTakenCount->getType());
+ if (isa<PointerType>(LargestType))
+ LargestType = TD->getIntPtrType();
+ SizesToInsert.insert(LargestType);
}
for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
const PHINode *PN = IndVars[i].first;
- SizesToInsert.insert(PN->getType());
- const Type *EffTy = getEffectiveIndvarType(PN);
+ const Type *PNTy = PN->getType();
+ if (isa<PointerType>(PNTy)) PNTy = TD->getIntPtrType();
+ SizesToInsert.insert(PNTy);
+ const Type *EffTy = getEffectiveIndvarType(PN, TD);
+ if (isa<PointerType>(EffTy)) EffTy = TD->getIntPtrType();
SizesToInsert.insert(EffTy);
if (!LargestType ||
- EffTy->getPrimitiveSizeInBits() >
- LargestType->getPrimitiveSizeInBits())
+ TD->getTypeSizeInBits(EffTy) >
+ TD->getTypeSizeInBits(LargestType))
LargestType = EffTy;
}
// Create a rewriter object which we'll use to transform the code with.
- SCEVExpander Rewriter(*SE, *LI);
+ SCEVExpander Rewriter(*SE, *LI, *TD);
// Now that we know the largest of of the induction variables in this loop,
// insert a canonical induction variable of the largest size.
@@ -769,7 +682,7 @@
if (Instruction *OrigCond = dyn_cast<Instruction>(BI->getCondition())) {
// Determine if the OrigIV will ever undergo overflow.
OrigControllingPHI =
- TestOrigIVForWrap(L, BI, OrigCond,
+ TestOrigIVForWrap(L, BI, OrigCond, TD,
NoSignedWrap, NoUnsignedWrap,
InitialVal, IncrVal, LimitVal);
@@ -804,7 +717,7 @@
while (!IndVars.empty()) {
PHINode *PN = IndVars.back().first;
SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(IndVars.back().second);
- Value *NewVal = Rewriter.expandCodeFor(AR, InsertPt);
+ Value *NewVal = Rewriter.expandCodeFor(AR, PN->getType(), InsertPt);
DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *PN
<< " into = " << *NewVal << "\n";
NewVal->takeName(PN);