summaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Scalar/IndVarSimplify.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp')
-rw-r--r--lib/Transforms/Scalar/IndVarSimplify.cpp137
1 files changed, 75 insertions, 62 deletions
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 88cf60e..e2d9e0b 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -51,11 +51,11 @@
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Support/CFG.h"
-#include "llvm/Support/Compiler.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
@@ -67,7 +67,7 @@ STATISTIC(NumReplaced, "Number of exit values replaced");
STATISTIC(NumLFTR , "Number of loop exit tests replaced");
namespace {
- class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
+ class IndVarSimplify : public LoopPass {
IVUsers *IU;
LoopInfo *LI;
ScalarEvolution *SE;
@@ -75,30 +75,30 @@ namespace {
bool Changed;
public:
- static char ID; // Pass identification, replacement for typeid
- IndVarSimplify() : LoopPass(&ID) {}
-
- virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<DominatorTree>();
- AU.addRequired<ScalarEvolution>();
- AU.addRequiredID(LoopSimplifyID);
- AU.addRequired<LoopInfo>();
- AU.addRequired<IVUsers>();
- AU.addRequiredID(LCSSAID);
- AU.addPreserved<ScalarEvolution>();
- AU.addPreservedID(LoopSimplifyID);
- AU.addPreserved<IVUsers>();
- AU.addPreservedID(LCSSAID);
- AU.setPreservesCFG();
- }
+ static char ID; // Pass identification, replacement for typeid
+ IndVarSimplify() : LoopPass(&ID) {}
+
+ virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<DominatorTree>();
+ AU.addRequired<LoopInfo>();
+ AU.addRequired<ScalarEvolution>();
+ AU.addRequiredID(LoopSimplifyID);
+ AU.addRequiredID(LCSSAID);
+ AU.addRequired<IVUsers>();
+ AU.addPreserved<ScalarEvolution>();
+ AU.addPreservedID(LoopSimplifyID);
+ AU.addPreservedID(LCSSAID);
+ AU.addPreserved<IVUsers>();
+ AU.setPreservesCFG();
+ }
private:
void RewriteNonIntegerIVs(Loop *L);
- ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV* BackedgeTakenCount,
+ ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
BranchInst *BI,
@@ -129,7 +129,7 @@ Pass *llvm::createIndVarSimplifyPass() {
/// SCEV analysis can determine a loop-invariant trip count of the loop, which
/// is actually a much broader range than just linear tests.
ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
- const SCEV* BackedgeTakenCount,
+ const SCEV *BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
BranchInst *BI,
@@ -138,13 +138,13 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
// against the preincremented value, otherwise we prefer to compare against
// the post-incremented value.
Value *CmpIndVar;
- const SCEV* RHS = BackedgeTakenCount;
+ const SCEV *RHS = BackedgeTakenCount;
if (ExitingBlock == L->getLoopLatch()) {
// Add one to the "backedge-taken" count to get the trip count.
// If this addition may overflow, we have to be more pessimistic and
// cast the induction variable before doing the add.
- const SCEV* Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
- const SCEV* N =
+ const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
+ const SCEV *N =
SE->getAddExpr(BackedgeTakenCount,
SE->getIntegerSCEV(1, BackedgeTakenCount->getType()));
if ((isa<SCEVConstant>(N) && !N->isZero()) ||
@@ -182,13 +182,13 @@ ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
else
Opcode = ICmpInst::ICMP_EQ;
- DOUT << "INDVARS: Rewriting loop exit condition to:\n"
- << " LHS:" << *CmpIndVar // includes a newline
- << " op:\t"
- << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
- << " RHS:\t" << *RHS << "\n";
+ DEBUG(errs() << "INDVARS: Rewriting loop exit condition to:\n"
+ << " LHS:" << *CmpIndVar << '\n'
+ << " op:\t"
+ << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
+ << " RHS:\t" << *RHS << "\n");
- ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
+ ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond");
Instruction *OrigCond = cast<Instruction>(BI->getCondition());
// It's tempting to use replaceAllUsesWith here to fully replace the old
@@ -264,7 +264,7 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
// Okay, this instruction has a user outside of the current loop
// and varies predictably *inside* the loop. Evaluate the value it
// contains when the loop exits, if possible.
- const SCEV* ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
+ const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
if (!ExitValue->isLoopInvariant(L))
continue;
@@ -273,25 +273,23 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L,
Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
- DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
- << " LoopVal = " << *Inst << "\n";
+ DEBUG(errs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n'
+ << " LoopVal = " << *Inst << "\n");
PN->setIncomingValue(i, ExitVal);
// If this instruction is dead now, delete it.
RecursivelyDeleteTriviallyDeadInstructions(Inst);
- // If we're inserting code into the exit block rather than the
- // preheader, we can (and have to) remove the PHI entirely.
- // This is safe, because the NewVal won't be variant
- // in the loop, so we don't need an LCSSA phi node anymore.
- if (ExitBlocks.size() == 1) {
+ if (NumPreds == 1) {
+ // Completely replace a single-pred PHI. This is safe, because the
+ // NewVal won't be variant in the loop, so we don't need an LCSSA phi
+ // node anymore.
PN->replaceAllUsesWith(ExitVal);
RecursivelyDeleteTriviallyDeadInstructions(PN);
- break;
}
}
- if (ExitBlocks.size() != 1) {
+ if (NumPreds != 1) {
// Clone the PHI and delete the original one. This lets IVUsers and
// any other maps purge the original user from their records.
PHINode *NewPN = PN->clone();
@@ -339,7 +337,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
RewriteNonIntegerIVs(L);
BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
- const SCEV* BackedgeTakenCount = SE->getBackedgeTakenCount(L);
+ const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
// Create a rewriter object which we'll use to transform the code with.
SCEVExpander Rewriter(*SE);
@@ -367,14 +365,14 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
NeedCannIV = true;
}
for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
- const SCEV* Stride = IU->StrideOrder[i];
+ const SCEV *Stride = IU->StrideOrder[i];
const Type *Ty = SE->getEffectiveSCEVType(Stride->getType());
if (!LargestType ||
SE->getTypeSizeInBits(Ty) >
SE->getTypeSizeInBits(LargestType))
LargestType = Ty;
- std::map<const SCEV*, IVUsersOfOneStride *>::iterator SI =
+ std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI =
IU->IVUsesByStride.find(IU->StrideOrder[i]);
assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
@@ -403,7 +401,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
++NumInserted;
Changed = true;
- DOUT << "INDVARS: New CanIV: " << *IndVar;
+ DEBUG(errs() << "INDVARS: New CanIV: " << *IndVar << '\n');
// Now that the official induction variable is established, reinsert
// the old canonical-looking variable after it so that the IR remains
@@ -458,9 +456,9 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
// the need for the code evaluation methods to insert induction variables
// of different sizes.
for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
- const SCEV* Stride = IU->StrideOrder[i];
+ const SCEV *Stride = IU->StrideOrder[i];
- std::map<const SCEV*, IVUsersOfOneStride *>::iterator SI =
+ std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI =
IU->IVUsesByStride.find(IU->StrideOrder[i]);
assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
ilist<IVStrideUse> &List = SI->second->Users;
@@ -471,7 +469,7 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
Instruction *User = UI->getUser();
// Compute the final addrec to expand into code.
- const SCEV* AR = IU->getReplacementExpr(*UI);
+ const SCEV *AR = IU->getReplacementExpr(*UI);
// FIXME: It is an extremely bad idea to indvar substitute anything more
// complex than affine induction variables. Doing so will put expensive
@@ -508,8 +506,8 @@ void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
NewVal->takeName(Op);
User->replaceUsesOfWith(Op, NewVal);
UI->setOperandValToReplace(NewVal);
- DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op
- << " into = " << *NewVal << "\n";
+ DEBUG(errs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n'
+ << " into = " << *NewVal << "\n");
++NumRemoved;
Changed = true;
@@ -546,8 +544,19 @@ void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
// New instructions were inserted at the end of the preheader.
if (isa<PHINode>(I))
break;
- if (I->isTrapping())
+ // Don't move instructions which might have side effects, since the side
+ // effects need to complete before instructions inside the loop. Also
+ // don't move instructions which might read memory, since the loop may
+ // modify memory. Note that it's okay if the instruction might have
+ // undefined behavior: LoopSimplify guarantees that the preheader
+ // dominates the exit block.
+ if (I->mayHaveSideEffects() || I->mayReadFromMemory())
continue;
+ // Don't sink static AllocaInsts out of the entry block, which would
+ // turn them into dynamic allocas!
+ if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
+ if (AI->isStaticAlloca())
+ continue;
// Determine if there is a use in or before the loop (direct or
// otherwise).
bool UsedInLoop = false;
@@ -630,7 +639,8 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
// Check incoming value.
ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge));
if (!InitValue) return;
- uint64_t newInitValue = Type::Int32Ty->getPrimitiveSizeInBits();
+ uint64_t newInitValue =
+ Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
if (!convertToInt(InitValue->getValueAPF(), &newInitValue))
return;
@@ -646,7 +656,8 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
IncrVIndex = 0;
IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex));
if (!IncrValue) return;
- uint64_t newIncrValue = Type::Int32Ty->getPrimitiveSizeInBits();
+ uint64_t newIncrValue =
+ Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue))
return;
@@ -677,7 +688,7 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
EVIndex = 0;
EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex));
if (!EV) return;
- uint64_t intEV = Type::Int32Ty->getPrimitiveSizeInBits();
+ uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
if (!convertToInt(EV->getValueAPF(), &intEV))
return;
@@ -710,24 +721,26 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return;
// Insert new integer induction variable.
- PHINode *NewPHI = PHINode::Create(Type::Int32Ty,
+ PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()),
PH->getName()+".int", PH);
- NewPHI->addIncoming(Context->getConstantInt(Type::Int32Ty, newInitValue),
+ NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()),
+ newInitValue),
PH->getIncomingBlock(IncomingEdge));
Value *NewAdd = BinaryOperator::CreateAdd(NewPHI,
- Context->getConstantInt(Type::Int32Ty,
+ ConstantInt::get(Type::getInt32Ty(PH->getContext()),
newIncrValue),
Incr->getName()+".int", Incr);
NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge));
// The back edge is edge 1 of newPHI, whatever it may have been in the
// original PHI.
- ConstantInt *NewEV = Context->getConstantInt(Type::Int32Ty, intEV);
+ ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()),
+ intEV);
Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV);
Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1));
- ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(),
- EC->getParent()->getTerminator());
+ ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(),
+ NewPred, LHS, RHS, EC->getName());
// In the following deltions, PH may become dead and may be deleted.
// Use a WeakVH to observe whether this happens.
@@ -739,7 +752,7 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
RecursivelyDeleteTriviallyDeadInstructions(EC);
// Delete old, floating point, increment instruction.
- Incr->replaceAllUsesWith(Context->getUndef(Incr->getType()));
+ Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
RecursivelyDeleteTriviallyDeadInstructions(Incr);
// Replace floating induction variable, if it isn't already deleted.
OpenPOWER on IntegriCloud