// which starts at zero and steps by one.
// 2. The canonical induction variable is guaranteed to be the first PHI node
// in the loop header block.
-// 3. Any pointer arithmetic recurrences are raised to use array subscripts.
+// 3. The canonical induction variable is guaranteed to be in a wide enough
+// type so that IV expressions need not be (directly) zero-extended or
+// sign-extended.
+// 4. Any pointer arithmetic recurrences are raised to use array subscripts.
//
// If the trip count of a loop is computable, this pass also makes the following
// changes:
// expression, this transformation will make the loop dead.
//
// This transformation should be followed by strength reduction after all of the
-// desired loop transformations have been performed. Additionally, on targets
-// where it is profitable, the loop could be transformed to count down to zero
-// (the "do loop" optimization).
+// desired loop transformations have been performed.
//
//===----------------------------------------------------------------------===//
#include "llvm/BasicBlock.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Type.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Support/CFG.h"
#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/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
using namespace llvm;
STATISTIC(NumRemoved , "Number of aux indvars removed");
namespace {
class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
+ IVUsers *IU;
LoopInfo *LI;
- TargetData *TD;
ScalarEvolution *SE;
+ DominatorTree *DT;
bool Changed;
public:
virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<DominatorTree>();
AU.addRequired<ScalarEvolution>();
- AU.addRequiredID(LCSSAID);
AU.addRequiredID(LoopSimplifyID);
AU.addRequired<LoopInfo>();
- AU.addRequired<TargetData>();
+ AU.addRequired<IVUsers>();
+ AU.addRequiredID(LCSSAID);
AU.addPreserved<ScalarEvolution>();
AU.addPreservedID(LoopSimplifyID);
+ AU.addPreserved<IVUsers>();
AU.addPreservedID(LCSSAID);
AU.setPreservesCFG();
}
void RewriteNonIntegerIVs(Loop *L);
- void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
+ ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
BranchInst *BI,
SCEVExpander &Rewriter);
- void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount);
+ void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount,
+ SCEVExpander &Rewriter);
- void DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts);
+ void RewriteIVExpressions(Loop *L, const Type *LargestType,
+ SCEVExpander &Rewriter);
- void HandleFloatingPointIV(Loop *L, PHINode *PH,
- SmallPtrSet<Instruction*, 16> &DeadInsts);
+ void SinkUnusedInvariants(Loop *L);
+
+ void HandleFloatingPointIV(Loop *L, PHINode *PH);
};
}
return new IndVarSimplify();
}
-/// DeleteTriviallyDeadInstructions - If any of the instructions is the
-/// specified set are trivially dead, delete them and see if this makes any of
-/// their operands subsequently dead.
-void IndVarSimplify::
-DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts) {
- while (!Insts.empty()) {
- Instruction *I = *Insts.begin();
- Insts.erase(I);
- if (isInstructionTriviallyDead(I)) {
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
- Insts.insert(U);
- SE->deleteValueFromRecords(I);
- DOUT << "INDVARS: Deleting: " << *I;
- I->eraseFromParent();
- 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
/// SCEV analysis can determine a loop-invariant trip count of the loop, which
/// is actually a much broader range than just linear tests.
-void IndVarSimplify::LinearFunctionTestReplace(Loop *L,
- SCEVHandle BackedgeTakenCount,
+ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
+ const SCEV *BackedgeTakenCount,
Value *IndVar,
BasicBlock *ExitingBlock,
BranchInst *BI,
// against the preincremented value, otherwise we prefer to compare against
// the post-incremented value.
Value *CmpIndVar;
- SCEVHandle 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.
- SCEVHandle Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
- SCEVHandle 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()) ||
CmpIndVar = IndVar;
}
- // Expand the code for the iteration count into the preheader of the loop.
- BasicBlock *Preheader = L->getLoopPreheader();
- Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(),
- Preheader->getTerminator());
+ // Expand the code for the iteration count.
+ assert(RHS->isLoopInvariant(L) &&
+ "Computed iteration count is not loop invariant!");
+ Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI);
// Insert a new icmp_ne or icmp_eq instruction before the branch.
ICmpInst::Predicate Opcode;
<< (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
<< " RHS:\t" << *RHS << "\n";
- Value *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
+ // comparison, but that's not immediately safe, since users of the old
+ // comparison may not be dominated by the new comparison. Instead, just
+ // update the branch to use the new comparison; in the common case this
+ // will make old comparison dead.
BI->setCondition(Cond);
+ RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
+
++NumLFTR;
Changed = true;
+ return Cond;
}
/// RewriteLoopExitValues - Check to see if this loop has a computable
/// final value of any expressions that are recurrent in the loop, and
/// substitute the exit values from the loop into any instructions outside of
/// the loop that use the final values of the current expressions.
+///
+/// This is mostly redundant with the regular IndVarSimplify activities that
+/// happen later, except that it's more powerful in some cases, because it's
+/// able to brute-force evaluate arbitrary instructions as long as they have
+/// constant operands at the beginning of the loop.
void IndVarSimplify::RewriteLoopExitValues(Loop *L,
- const SCEV *BackedgeTakenCount) {
- BasicBlock *Preheader = L->getLoopPreheader();
-
- // Scan all of the instructions in the loop, looking at those that have
- // extra-loop users and which are recurrences.
- SCEVExpander Rewriter(*SE, *LI, *TD);
+ const SCEV *BackedgeTakenCount,
+ SCEVExpander &Rewriter) {
+ // Verify the input to the pass in already in LCSSA form.
+ assert(L->isLCSSAForm());
- // 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.
- BasicBlock *BlockToInsertInto;
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
- if (ExitBlocks.size() == 1)
- BlockToInsertInto = ExitBlocks[0];
- else
- BlockToInsertInto = Preheader;
- BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI();
-
- bool HasConstantItCount = isa<SCEVConstant>(BackedgeTakenCount);
-
- SmallPtrSet<Instruction*, 16> InstructionsToDelete;
- std::map<Instruction*, Value*> ExitValues;
// Find all values that are computed inside the loop, but used outside of it.
// Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
// Iterate over all of the PHI nodes.
BasicBlock::iterator BBI = ExitBB->begin();
while ((PN = dyn_cast<PHINode>(BBI++))) {
-
+ if (PN->use_empty())
+ continue; // dead use, don't replace it
// Iterate over all of the values in all the PHI nodes.
for (unsigned i = 0; i != NumPreds; ++i) {
// If the value being merged in is not integer or is not defined
if (!L->contains(Inst->getParent()))
continue;
- // We require that this value either have a computable evolution or that
- // the loop have a constant iteration count. In the case where the loop
- // has a constant iteration count, we can sometimes force evaluation of
- // the exit value through brute force.
- SCEVHandle SH = SE->getSCEV(Inst);
- if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount)
- continue; // Cannot get exit evolution for the loop value.
-
// 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.
- SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(ExitValue) ||
- !ExitValue->isLoopInvariant(L))
+ const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
+ if (!ExitValue->isLoopInvariant(L))
continue;
Changed = true;
++NumReplaced;
- // See if we already computed the exit value for the instruction, if so,
- // just reuse it.
- Value *&ExitVal = ExitValues[Inst];
- if (!ExitVal)
- ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt);
+ Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
<< " LoopVal = " << *Inst << "\n";
PN->setIncomingValue(i, ExitVal);
- // If this instruction is dead now, schedule it to be removed.
- if (Inst->use_empty())
- InstructionsToDelete.insert(Inst);
+ // If this instruction is dead now, delete it.
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
- // See if this is a single-entry LCSSA PHI node. If so, we can (and
- // have to) remove
- // the PHI entirely. This is safe, because the NewVal won't be variant
+ // 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 (NumPreds == 1) {
- SE->deleteValueFromRecords(PN);
+ if (ExitBlocks.size() == 1) {
PN->replaceAllUsesWith(ExitVal);
- PN->eraseFromParent();
+ RecursivelyDeleteTriviallyDeadInstructions(PN);
break;
}
}
+ if (ExitBlocks.size() != 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(*Context);
+ NewPN->takeName(PN);
+ NewPN->insertBefore(PN);
+ PN->replaceAllUsesWith(NewPN);
+ PN->eraseFromParent();
+ }
}
}
-
- DeleteTriviallyDeadInstructions(InstructionsToDelete);
}
void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
//
BasicBlock *Header = L->getHeader();
- SmallPtrSet<Instruction*, 16> DeadInsts;
- for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- HandleFloatingPointIV(L, PN, DeadInsts);
- }
+ SmallVector<WeakVH, 8> PHIs;
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ PHIs.push_back(PN);
+
+ for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
+ if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
+ HandleFloatingPointIV(L, PN);
// 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)
SE->forgetLoopBackedgeTakenCount(L);
-
- if (!DeadInsts.empty())
- DeleteTriviallyDeadInstructions(DeadInsts);
-}
-
-/// getEffectiveIndvarType - Determine the widest type that the
-/// induction-variable PHINode Phi is cast to.
-///
-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();
- UI != UE; ++UI) {
- const Type *CandidateType = NULL;
- if (const ZExtInst *ZI = dyn_cast<ZExtInst>(UI))
- CandidateType = ZI->getDestTy();
- else if (const SExtInst *SI = dyn_cast<SExtInst>(UI))
- CandidateType = SI->getDestTy();
- if (CandidateType &&
- TD->getTypeSizeInBits(CandidateType) > TD->getTypeSizeInBits(Ty))
- Ty = CandidateType;
- }
-
- return Ty;
-}
-
-/// TestOrigIVForWrap - Analyze the original induction variable
-/// that controls the loop's iteration to determine whether it
-/// would ever undergo signed or unsigned overflow. Also, check
-/// whether an induction variable in the same type that starts
-/// at 0 would undergo signed overflow.
-///
-/// In addition to setting the NoSignedWrap and NoUnsignedWrap
-/// variables to true when appropriate (they are not set to false here),
-/// return the PHI for this induction variable. Also record the initial
-/// and final values and the increment; these are not meaningful unless
-/// either NoSignedWrap or NoUnsignedWrap is true, and are always meaningful
-/// in that case, although the final value may be 0 indicating a nonconstant.
-///
-/// TODO: This duplicates a fair amount of ScalarEvolution logic.
-/// Perhaps this can be merged with
-/// ScalarEvolution::getBackedgeTakenCount
-/// and/or ScalarEvolution::get{Sign,Zero}ExtendExpr.
-///
-static const PHINode *TestOrigIVForWrap(const Loop *L,
- const BranchInst *BI,
- const Instruction *OrigCond,
- const TargetData *TD,
- bool &NoSignedWrap,
- bool &NoUnsignedWrap,
- const ConstantInt* &InitialVal,
- const ConstantInt* &IncrVal,
- const ConstantInt* &LimitVal) {
- // Verify that the loop is sane and find the exit condition.
- const ICmpInst *Cmp = dyn_cast<ICmpInst>(OrigCond);
- if (!Cmp) return 0;
-
- const Value *CmpLHS = Cmp->getOperand(0);
- const Value *CmpRHS = Cmp->getOperand(1);
- const BasicBlock *TrueBB = BI->getSuccessor(0);
- const BasicBlock *FalseBB = BI->getSuccessor(1);
- ICmpInst::Predicate Pred = Cmp->getPredicate();
-
- // Canonicalize a constant to the RHS.
- if (isa<ConstantInt>(CmpLHS)) {
- Pred = ICmpInst::getSwappedPredicate(Pred);
- std::swap(CmpLHS, CmpRHS);
- }
- // Canonicalize SLE to SLT.
- if (Pred == ICmpInst::ICMP_SLE)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxSignedValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_SLT;
- }
- // Canonicalize SGT to SGE.
- if (Pred == ICmpInst::ICMP_SGT)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxSignedValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_SGE;
- }
- // Canonicalize SGE to SLT.
- if (Pred == ICmpInst::ICMP_SGE) {
- std::swap(TrueBB, FalseBB);
- Pred = ICmpInst::ICMP_SLT;
- }
- // Canonicalize ULE to ULT.
- if (Pred == ICmpInst::ICMP_ULE)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_ULT;
- }
- // Canonicalize UGT to UGE.
- if (Pred == ICmpInst::ICMP_UGT)
- if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS))
- if (!CI->getValue().isMaxValue()) {
- CmpRHS = ConstantInt::get(CI->getValue() + 1);
- Pred = ICmpInst::ICMP_UGE;
- }
- // Canonicalize UGE to ULT.
- if (Pred == ICmpInst::ICMP_UGE) {
- std::swap(TrueBB, FalseBB);
- Pred = ICmpInst::ICMP_ULT;
- }
- // For now, analyze only LT loops for signed overflow.
- if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_ULT)
- return 0;
-
- bool isSigned = Pred == ICmpInst::ICMP_SLT;
-
- // Get the increment instruction. Look past casts if we will
- // be able to prove that the original induction variable doesn't
- // undergo signed or unsigned overflow, respectively.
- const Value *IncrInst = CmpLHS;
- if (isSigned) {
- if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) {
- if (!isa<ConstantInt>(CmpRHS) ||
- !cast<ConstantInt>(CmpRHS)->getValue()
- .isSignedIntN(TD->getTypeSizeInBits(IncrInst->getType())))
- return 0;
- IncrInst = SI->getOperand(0);
- }
- } else {
- if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) {
- if (!isa<ConstantInt>(CmpRHS) ||
- !cast<ConstantInt>(CmpRHS)->getValue()
- .isIntN(TD->getTypeSizeInBits(IncrInst->getType())))
- return 0;
- IncrInst = ZI->getOperand(0);
- }
- }
-
- // For now, only analyze induction variables that have simple increments.
- const BinaryOperator *IncrOp = dyn_cast<BinaryOperator>(IncrInst);
- if (!IncrOp || IncrOp->getOpcode() != Instruction::Add)
- return 0;
- IncrVal = dyn_cast<ConstantInt>(IncrOp->getOperand(1));
- if (!IncrVal)
- return 0;
-
- // Make sure the PHI looks like a normal IV.
- const PHINode *PN = dyn_cast<PHINode>(IncrOp->getOperand(0));
- if (!PN || PN->getNumIncomingValues() != 2)
- return 0;
- unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
- unsigned BackEdge = !IncomingEdge;
- if (!L->contains(PN->getIncomingBlock(BackEdge)) ||
- PN->getIncomingValue(BackEdge) != IncrOp)
- return 0;
- if (!L->contains(TrueBB))
- return 0;
-
- // For now, only analyze loops with a constant start value, so that
- // we can easily determine if the start value is not a maximum value
- // which would wrap on the first iteration.
- InitialVal = dyn_cast<ConstantInt>(PN->getIncomingValue(IncomingEdge));
- if (!InitialVal)
- return 0;
-
- // The upper limit need not be a constant; we'll check later.
- LimitVal = dyn_cast<ConstantInt>(CmpRHS);
-
- // We detect the impossibility of wrapping in two cases, both of
- // which require starting with a non-max value:
- // - The IV counts up by one, and the loop iterates only while it remains
- // less than a limiting value (any) in the same type.
- // - The IV counts up by a positive increment other than 1, and the
- // constant limiting value + the increment is less than the max value
- // (computed as max-increment to avoid overflow)
- if (isSigned && !InitialVal->getValue().isMaxSignedValue()) {
- if (IncrVal->equalsInt(1))
- NoSignedWrap = true; // LimitVal need not be constant
- else if (LimitVal) {
- uint64_t numBits = LimitVal->getValue().getBitWidth();
- if (IncrVal->getValue().sgt(APInt::getNullValue(numBits)) &&
- (APInt::getSignedMaxValue(numBits) - IncrVal->getValue())
- .sgt(LimitVal->getValue()))
- NoSignedWrap = true;
- }
- } else if (!isSigned && !InitialVal->getValue().isMaxValue()) {
- if (IncrVal->equalsInt(1))
- NoUnsignedWrap = true; // LimitVal need not be constant
- else if (LimitVal) {
- uint64_t numBits = LimitVal->getValue().getBitWidth();
- if (IncrVal->getValue().ugt(APInt::getNullValue(numBits)) &&
- (APInt::getMaxValue(numBits) - IncrVal->getValue())
- .ugt(LimitVal->getValue()))
- NoUnsignedWrap = true;
- }
- }
- return PN;
-}
-
-static Value *getSignExtendedTruncVar(const SCEVAddRecExpr *AR,
- ScalarEvolution *SE,
- const Type *LargestType, Loop *L,
- const Type *myType,
- SCEVExpander &Rewriter,
- BasicBlock::iterator InsertPt) {
- SCEVHandle ExtendedStart =
- SE->getSignExtendExpr(AR->getStart(), LargestType);
- SCEVHandle ExtendedStep =
- SE->getSignExtendExpr(AR->getStepRecurrence(*SE), LargestType);
- SCEVHandle ExtendedAddRec =
- SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
- if (LargestType != myType)
- ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt);
-}
-
-static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR,
- ScalarEvolution *SE,
- const Type *LargestType, Loop *L,
- const Type *myType,
- SCEVExpander &Rewriter,
- BasicBlock::iterator InsertPt) {
- SCEVHandle ExtendedStart =
- SE->getZeroExtendExpr(AR->getStart(), LargestType);
- SCEVHandle ExtendedStep =
- SE->getZeroExtendExpr(AR->getStepRecurrence(*SE), LargestType);
- SCEVHandle ExtendedAddRec =
- SE->getAddRecExpr(ExtendedStart, ExtendedStep, L);
- if (LargestType != myType)
- ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType);
- return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt);
-}
-
-/// allUsesAreSameTyped - See whether all Uses of I are instructions
-/// with the same Opcode and the same type.
-static bool allUsesAreSameTyped(unsigned int Opcode, Instruction *I) {
- const Type* firstType = NULL;
- for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
- UI != UE; ++UI) {
- Instruction *II = dyn_cast<Instruction>(*UI);
- if (!II || II->getOpcode() != Opcode)
- return false;
- if (!firstType)
- firstType = II->getType();
- else if (firstType != II->getType())
- return false;
- }
- return true;
}
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
+ IU = &getAnalysis<IVUsers>();
LI = &getAnalysis<LoopInfo>();
- TD = &getAnalysis<TargetData>();
SE = &getAnalysis<ScalarEvolution>();
+ DT = &getAnalysis<DominatorTree>();
Changed = false;
// If there are any floating-point recurrences, attempt to
// transform them to use integer recurrences.
RewriteNonIntegerIVs(L);
- BasicBlock *Header = L->getHeader();
- BasicBlock *ExitingBlock = L->getExitingBlock();
- SmallPtrSet<Instruction*, 16> DeadInsts;
+ BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
+ const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
- // Verify the input to the pass in already in LCSSA form.
- assert(L->isLCSSAForm());
+ // Create a rewriter object which we'll use to transform the code with.
+ SCEVExpander Rewriter(*SE);
// Check to see if this loop has a computable loop-invariant execution count.
// If so, this means that we can compute the final value of any expressions
// loop into any instructions outside of the loop that use the final values of
// the current expressions.
//
- SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L);
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
- RewriteLoopExitValues(L, BackedgeTakenCount);
-
- // Next, analyze all of the induction variables in the loop, canonicalizing
- // auxillary induction variables.
- std::vector<std::pair<PHINode*, SCEVHandle> > IndVars;
+ RewriteLoopExitValues(L, BackedgeTakenCount, Rewriter);
- for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- 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
- // polynomial evaluations inside of the loop, and the str reduction pass
- // currently can only reduce affine polynomials. For now just disable
- // indvar subst on anything more complex than an affine addrec.
- if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV))
- if (AR->getLoop() == L && AR->isAffine())
- IndVars.push_back(std::make_pair(PN, SCEV));
- }
- }
-
- // Compute the type of the largest recurrence expression, and collect
- // the set of the types of the other recurrence expressions.
+ // Compute the type of the largest recurrence expression, and decide whether
+ // a canonical induction variable should be inserted.
const Type *LargestType = 0;
- SmallSetVector<const Type *, 4> SizesToInsert;
+ bool NeedCannIV = false;
if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
LargestType = BackedgeTakenCount->getType();
- if (isa<PointerType>(LargestType))
- LargestType = TD->getIntPtrType();
- SizesToInsert.insert(LargestType);
+ LargestType = SE->getEffectiveSCEVType(LargestType);
+ // If we have a known trip count and a single exit block, we'll be
+ // rewriting the loop exit test condition below, which requires a
+ // canonical induction variable.
+ if (ExitingBlock)
+ NeedCannIV = true;
}
- for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
- const PHINode *PN = IndVars[i].first;
- 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);
+ for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
+ const SCEV *Stride = IU->StrideOrder[i];
+ const Type *Ty = SE->getEffectiveSCEVType(Stride->getType());
if (!LargestType ||
- TD->getTypeSizeInBits(EffTy) >
- TD->getTypeSizeInBits(LargestType))
- LargestType = EffTy;
- }
+ SE->getTypeSizeInBits(Ty) >
+ SE->getTypeSizeInBits(LargestType))
+ LargestType = Ty;
- // Create a rewriter object which we'll use to transform the code with.
- SCEVExpander Rewriter(*SE, *LI, *TD);
+ std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI =
+ IU->IVUsesByStride.find(IU->StrideOrder[i]);
+ assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
+
+ if (!SI->second->Users.empty())
+ NeedCannIV = true;
+ }
- // Now that we know the largest of of the induction variables in this loop,
- // insert a canonical induction variable of the largest size.
+ // Now that we know the largest of of the induction variable expressions
+ // in this loop, insert a canonical induction variable of the largest size.
Value *IndVar = 0;
- if (!SizesToInsert.empty()) {
- IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType);
+ if (NeedCannIV) {
+ // Check to see if the loop already has a canonical-looking induction
+ // variable. If one is present and it's wider than the planned canonical
+ // induction variable, temporarily remove it, so that the Rewriter
+ // doesn't attempt to reuse it.
+ PHINode *OldCannIV = L->getCanonicalInductionVariable();
+ if (OldCannIV) {
+ if (SE->getTypeSizeInBits(OldCannIV->getType()) >
+ SE->getTypeSizeInBits(LargestType))
+ OldCannIV->removeFromParent();
+ else
+ OldCannIV = 0;
+ }
+
+ IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType);
+
++NumInserted;
Changed = true;
DOUT << "INDVARS: New CanIV: " << *IndVar;
+
+ // Now that the official induction variable is established, reinsert
+ // the old canonical-looking variable after it so that the IR remains
+ // consistent. It will be deleted as part of the dead-PHI deletion at
+ // the end of the pass.
+ if (OldCannIV)
+ OldCannIV->insertAfter(cast<Instruction>(IndVar));
}
// If we have a trip count expression, rewrite the loop's exit condition
// using it. We can currently only handle loops with a single exit.
- bool NoSignedWrap = false;
- bool NoUnsignedWrap = false;
- const ConstantInt* InitialVal, * IncrVal, * LimitVal;
- const PHINode *OrigControllingPHI = 0;
- if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock)
+ ICmpInst *NewICmp = 0;
+ if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) {
+ assert(NeedCannIV &&
+ "LinearFunctionTestReplace requires a canonical induction variable");
// Can't rewrite non-branch yet.
- if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) {
- if (Instruction *OrigCond = dyn_cast<Instruction>(BI->getCondition())) {
- // Determine if the OrigIV will ever undergo overflow.
- OrigControllingPHI =
- TestOrigIVForWrap(L, BI, OrigCond, TD,
- NoSignedWrap, NoUnsignedWrap,
- InitialVal, IncrVal, LimitVal);
-
- // We'll be replacing the original condition, so it'll be dead.
- DeadInsts.insert(OrigCond);
- }
+ if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
+ NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
+ ExitingBlock, BI, Rewriter);
+ }
- LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
- ExitingBlock, BI, Rewriter);
- }
+ // Rewrite IV-derived expressions. Clears the rewriter cache.
+ RewriteIVExpressions(L, LargestType, Rewriter);
- // Now that we have a canonical induction variable, we can rewrite any
- // recurrences in terms of the induction variable. Start with the auxillary
- // induction variables, and recursively rewrite any of their uses.
- BasicBlock::iterator InsertPt = Header->getFirstNonPHI();
-
- // If there were induction variables of other sizes, cast the primary
- // induction variable to the right size for them, avoiding the need for the
- // code evaluation methods to insert induction variables of different sizes.
- for (unsigned i = 0, e = SizesToInsert.size(); i != e; ++i) {
- const Type *Ty = SizesToInsert[i];
- if (Ty != LargestType) {
- Instruction *New = new TruncInst(IndVar, Ty, "indvar", InsertPt);
- Rewriter.addInsertedValue(New, SE->getSCEV(New));
- DOUT << "INDVARS: Made trunc IV for type " << *Ty << ": "
- << *New << "\n";
- }
- }
+ // The Rewriter may not be used from this point on.
- // Rewrite all induction variables in terms of the canonical induction
- // variable.
- while (!IndVars.empty()) {
- PHINode *PN = IndVars.back().first;
- const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(IndVars.back().second);
- Value *NewVal = Rewriter.expandCodeFor(AR, PN->getType(), InsertPt);
- DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *PN
- << " into = " << *NewVal << "\n";
- NewVal->takeName(PN);
-
- /// If the new canonical induction variable is wider than the original,
- /// and the original has uses that are casts to wider types, see if the
- /// truncate and extend can be omitted.
- if (PN == OrigControllingPHI && PN->getType() != LargestType)
- for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
- UI != UE; ++UI) {
- Instruction *UInst = dyn_cast<Instruction>(*UI);
- if (UInst && isa<SExtInst>(UInst) && NoSignedWrap) {
- Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, L,
- UInst->getType(), Rewriter, InsertPt);
- UInst->replaceAllUsesWith(TruncIndVar);
- DeadInsts.insert(UInst);
- }
- // See if we can figure out sext(i+constant) doesn't wrap, so we can
- // use a larger add. This is common in subscripting.
- if (UInst && UInst->getOpcode()==Instruction::Add &&
- allUsesAreSameTyped(Instruction::SExt, UInst) &&
- isa<ConstantInt>(UInst->getOperand(1)) &&
- NoSignedWrap && LimitVal) {
- uint64_t oldBitSize = LimitVal->getValue().getBitWidth();
- uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
- ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
- if (((APInt::getSignedMaxValue(oldBitSize) - IncrVal->getValue()) -
- AddRHS->getValue()).sgt(LimitVal->getValue())) {
- // We've determined this is (i+constant) and it won't overflow.
- if (isa<SExtInst>(UInst->use_begin())) {
- SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin());
- Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
- L, oldSext->getType(), Rewriter,
- InsertPt);
- APInt APcopy = APInt(AddRHS->getValue());
- ConstantInt* newAddRHS =ConstantInt::get(APcopy.sext(newBitSize));
- Value *NewAdd =
- BinaryOperator::CreateAdd(TruncIndVar, newAddRHS,
- UInst->getName()+".nosex", UInst);
- for (Value::use_iterator UI2 = UInst->use_begin(),
- UE2 = UInst->use_end(); UI2 != UE2; ++UI2) {
- Instruction *II = dyn_cast<Instruction>(UI2);
- II->replaceAllUsesWith(NewAdd);
- DeadInsts.insert(II);
- }
- DeadInsts.insert(UInst);
- }
- }
- }
- // Try for sext(i | constant). This is safe as long as the
- // high bit of the constant is not set.
- if (UInst && UInst->getOpcode()==Instruction::Or &&
- allUsesAreSameTyped(Instruction::SExt, UInst) && NoSignedWrap &&
- isa<ConstantInt>(UInst->getOperand(1))) {
- ConstantInt* RHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
- if (!RHS->getValue().isNegative()) {
- uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
- SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin());
- Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
- L, oldSext->getType(), Rewriter,
- InsertPt);
- APInt APcopy = APInt(RHS->getValue());
- ConstantInt* newRHS =ConstantInt::get(APcopy.sext(newBitSize));
- Value *NewAdd =
- BinaryOperator::CreateOr(TruncIndVar, newRHS,
- UInst->getName()+".nosex", UInst);
- for (Value::use_iterator UI2 = UInst->use_begin(),
- UE2 = UInst->use_end(); UI2 != UE2; ++UI2) {
- Instruction *II = dyn_cast<Instruction>(UI2);
- II->replaceAllUsesWith(NewAdd);
- DeadInsts.insert(II);
- }
- DeadInsts.insert(UInst);
- }
- }
- // A zext of a signed variable known not to overflow is still safe.
- if (UInst && isa<ZExtInst>(UInst) && (NoUnsignedWrap || NoSignedWrap)) {
- Value *TruncIndVar = getZeroExtendedTruncVar(AR, SE, LargestType, L,
- UInst->getType(), Rewriter, InsertPt);
- UInst->replaceAllUsesWith(TruncIndVar);
- DeadInsts.insert(UInst);
- }
- // If we have zext(i&constant), it's always safe to use the larger
- // variable. This is not common but is a bottleneck in Openssl.
- // (RHS doesn't have to be constant. There should be a better approach
- // than bottom-up pattern matching for this...)
- if (UInst && UInst->getOpcode()==Instruction::And &&
- allUsesAreSameTyped(Instruction::ZExt, UInst) &&
- isa<ConstantInt>(UInst->getOperand(1))) {
- uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
- ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
- ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst->use_begin());
- Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
- L, oldZext->getType(), Rewriter, InsertPt);
- APInt APcopy = APInt(AndRHS->getValue());
- ConstantInt* newAndRHS = ConstantInt::get(APcopy.zext(newBitSize));
- Value *NewAnd =
- BinaryOperator::CreateAnd(TruncIndVar, newAndRHS,
- UInst->getName()+".nozex", UInst);
- for (Value::use_iterator UI2 = UInst->use_begin(),
- UE2 = UInst->use_end(); UI2 != UE2; ++UI2) {
- Instruction *II = dyn_cast<Instruction>(UI2);
- II->replaceAllUsesWith(NewAnd);
- DeadInsts.insert(II);
- }
- DeadInsts.insert(UInst);
- }
- // If we have zext((i+constant)&constant), we can use the larger
- // variable even if the add does overflow. This works whenever the
- // constant being ANDed is the same size as i, which it presumably is.
- // We don't need to restrict the expression being and'ed to i+const,
- // but we have to promote everything in it, so it's convenient.
- // zext((i | constant)&constant) is also valid and accepted here.
- if (UInst && (UInst->getOpcode()==Instruction::Add ||
- UInst->getOpcode()==Instruction::Or) &&
- UInst->hasOneUse() &&
- isa<ConstantInt>(UInst->getOperand(1))) {
- uint64_t newBitSize = LargestType->getPrimitiveSizeInBits();
- ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1));
- Instruction *UInst2 = dyn_cast<Instruction>(UInst->use_begin());
- if (UInst2 && UInst2->getOpcode() == Instruction::And &&
- allUsesAreSameTyped(Instruction::ZExt, UInst2) &&
- isa<ConstantInt>(UInst2->getOperand(1))) {
- ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst2->use_begin());
- Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType,
- L, oldZext->getType(), Rewriter, InsertPt);
- ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst2->getOperand(1));
- APInt APcopy = APInt(AddRHS->getValue());
- ConstantInt* newAddRHS = ConstantInt::get(APcopy.zext(newBitSize));
- Value *NewAdd = ((UInst->getOpcode()==Instruction::Add) ?
- BinaryOperator::CreateAdd(TruncIndVar, newAddRHS,
- UInst->getName()+".nozex", UInst2) :
- BinaryOperator::CreateOr(TruncIndVar, newAddRHS,
- UInst->getName()+".nozex", UInst2));
- APInt APcopy2 = APInt(AndRHS->getValue());
- ConstantInt* newAndRHS = ConstantInt::get(APcopy2.zext(newBitSize));
- Value *NewAnd =
- BinaryOperator::CreateAnd(NewAdd, newAndRHS,
- UInst->getName()+".nozex", UInst2);
- for (Value::use_iterator UI2 = UInst2->use_begin(),
- UE2 = UInst2->use_end(); UI2 != UE2; ++UI2) {
- Instruction *II = dyn_cast<Instruction>(UI2);
- II->replaceAllUsesWith(NewAnd);
- DeadInsts.insert(II);
- }
- DeadInsts.insert(UInst);
- DeadInsts.insert(UInst2);
+ // Loop-invariant instructions in the preheader that aren't used in the
+ // loop may be sunk below the loop to reduce register pressure.
+ SinkUnusedInvariants(L);
+
+ // For completeness, inform IVUsers of the IV use in the newly-created
+ // loop exit test instruction.
+ if (NewICmp)
+ IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
+
+ // Clean up dead instructions.
+ DeleteDeadPHIs(L->getHeader());
+ // Check a post-condition.
+ assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
+ return Changed;
+}
+
+void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
+ SCEVExpander &Rewriter) {
+ SmallVector<WeakVH, 16> DeadInsts;
+
+ // Rewrite all induction variable expressions in terms of the canonical
+ // induction variable.
+ //
+ // If there were induction variables of other sizes or offsets, manually
+ // add the offsets to the primary induction variable and cast, avoiding
+ // 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];
+
+ 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;
+ for (ilist<IVStrideUse>::iterator UI = List.begin(),
+ E = List.end(); UI != E; ++UI) {
+ Value *Op = UI->getOperandValToReplace();
+ const Type *UseTy = Op->getType();
+ Instruction *User = UI->getUser();
+
+ // Compute the final addrec to expand into code.
+ 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
+ // polynomial evaluations inside of the loop, and the str reduction pass
+ // currently can only reduce affine polynomials. For now just disable
+ // indvar subst on anything more complex than an affine addrec, unless
+ // it can be expanded to a trivial value.
+ if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L))
+ continue;
+
+ // Determine the insertion point for this user. By default, insert
+ // immediately before the user. The SCEVExpander class will automatically
+ // hoist loop invariants out of the loop. For PHI nodes, there may be
+ // multiple uses, so compute the nearest common dominator for the
+ // incoming blocks.
+ Instruction *InsertPt = User;
+ if (PHINode *PHI = dyn_cast<PHINode>(InsertPt))
+ for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
+ if (PHI->getIncomingValue(i) == Op) {
+ if (InsertPt == User)
+ InsertPt = PHI->getIncomingBlock(i)->getTerminator();
+ else
+ InsertPt =
+ DT->findNearestCommonDominator(InsertPt->getParent(),
+ PHI->getIncomingBlock(i))
+ ->getTerminator();
}
- }
- }
- // Replace the old PHI Node with the inserted computation.
- PN->replaceAllUsesWith(NewVal);
- DeadInsts.insert(PN);
- IndVars.pop_back();
- ++NumRemoved;
- Changed = true;
+ // Now expand it into actual Instructions and patch it into place.
+ Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt);
+
+ // Patch the new value into place.
+ if (Op->hasName())
+ NewVal->takeName(Op);
+ User->replaceUsesOfWith(Op, NewVal);
+ UI->setOperandValToReplace(NewVal);
+ DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op
+ << " into = " << *NewVal << "\n";
+ ++NumRemoved;
+ Changed = true;
+
+ // The old value may be dead now.
+ DeadInsts.push_back(Op);
+ }
}
- DeleteTriviallyDeadInstructions(DeadInsts);
- assert(L->isLCSSAForm());
- return Changed;
+ // Clear the rewriter cache, because values that are in the rewriter's cache
+ // can be deleted in the loop below, causing the AssertingVH in the cache to
+ // trigger.
+ Rewriter.clear();
+ // Now that we're done iterating through lists, clean up any instructions
+ // which are now dead.
+ while (!DeadInsts.empty()) {
+ Instruction *Inst = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
+ if (Inst)
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
+ }
+}
+
+/// If there's a single exit block, sink any loop-invariant values that
+/// were defined in the preheader but not used inside the loop into the
+/// exit block to reduce register pressure in the loop.
+void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
+ BasicBlock *ExitBlock = L->getExitBlock();
+ if (!ExitBlock) return;
+
+ Instruction *InsertPt = ExitBlock->getFirstNonPHI();
+ BasicBlock *Preheader = L->getLoopPreheader();
+ BasicBlock::iterator I = Preheader->getTerminator();
+ while (I != Preheader->begin()) {
+ --I;
+ // New instructions were inserted at the end of the preheader.
+ if (isa<PHINode>(I))
+ break;
+ if (I->isTrapping())
+ continue;
+ // Determine if there is a use in or before the loop (direct or
+ // otherwise).
+ bool UsedInLoop = false;
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI) {
+ BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
+ if (PHINode *P = dyn_cast<PHINode>(UI)) {
+ unsigned i =
+ PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
+ UseBB = P->getIncomingBlock(i);
+ }
+ if (UseBB == Preheader || L->contains(UseBB)) {
+ UsedInLoop = true;
+ break;
+ }
+ }
+ // If there is, the def must remain in the preheader.
+ if (UsedInLoop)
+ continue;
+ // Otherwise, sink it to the exit block.
+ Instruction *ToMove = I;
+ bool Done = false;
+ if (I != Preheader->begin())
+ --I;
+ else
+ Done = true;
+ ToMove->moveBefore(InsertPt);
+ if (Done)
+ break;
+ InsertPt = ToMove;
+ }
}
/// Return true if it is OK to use SIToFPInst for an inducation variable
// If the iteration range can be handled by SIToFPInst then use it.
APInt Max = APInt::getSignedMaxValue(32);
- if (Max.getZExtValue() > static_cast<uint64_t>(abs(intEV - intIV)))
+ if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV)))
return true;
return false;
/// for(int i = 0; i < 10000; ++i)
/// bar((double)i);
///
-void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH,
- SmallPtrSet<Instruction*, 16> &DeadInsts) {
+void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
unsigned BackEdge = IncomingEdge^1;
BinaryOperator *Incr =
dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge));
if (!Incr) return;
- if (Incr->getOpcode() != Instruction::Add) return;
+ if (Incr->getOpcode() != Instruction::FAdd) return;
ConstantFP *IncrValue = NULL;
unsigned IncrVIndex = 1;
if (Incr->getOperand(1) == PH)
// Insert new integer induction variable.
PHINode *NewPHI = PHINode::Create(Type::Int32Ty,
PH->getName()+".int", PH);
- NewPHI->addIncoming(ConstantInt::get(Type::Int32Ty, newInitValue),
+ NewPHI->addIncoming(Context->getConstantInt(Type::Int32Ty, newInitValue),
PH->getIncomingBlock(IncomingEdge));
Value *NewAdd = BinaryOperator::CreateAdd(NewPHI,
- ConstantInt::get(Type::Int32Ty,
+ Context->getConstantInt(Type::Int32Ty,
newIncrValue),
Incr->getName()+".int", Incr);
NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge));
- ConstantInt *NewEV = ConstantInt::get(Type::Int32Ty, intEV);
- Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(BackEdge) : NewEV);
- Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(BackEdge));
- ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(),
- EC->getParent()->getTerminator());
+ // The back edge is edge 1 of newPHI, whatever it may have been in the
+ // original PHI.
+ ConstantInt *NewEV = Context->getConstantInt(Type::Int32Ty, intEV);
+ Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV);
+ Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1));
+ ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(),
+ NewPred, LHS, RHS, EC->getNameStart());
+
+ // In the following deltions, PH may become dead and may be deleted.
+ // Use a WeakVH to observe whether this happens.
+ WeakVH WeakPH = PH;
// Delete old, floating point, exit comparision instruction.
+ NewEC->takeName(EC);
EC->replaceAllUsesWith(NewEC);
- DeadInsts.insert(EC);
+ RecursivelyDeleteTriviallyDeadInstructions(EC);
// Delete old, floating point, increment instruction.
- Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
- DeadInsts.insert(Incr);
-
- // Replace floating induction variable. Give SIToFPInst preference over
- // UIToFPInst because it is faster on platforms that are widely used.
- if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
- SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
- PH->getParent()->getFirstNonPHI());
- PH->replaceAllUsesWith(Conv);
- } else {
- UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
- PH->getParent()->getFirstNonPHI());
- PH->replaceAllUsesWith(Conv);
+ Incr->replaceAllUsesWith(Context->getUndef(Incr->getType()));
+ RecursivelyDeleteTriviallyDeadInstructions(Incr);
+
+ // Replace floating induction variable, if it isn't already deleted.
+ // Give SIToFPInst preference over UIToFPInst because it is faster on
+ // platforms that are widely used.
+ if (WeakPH && !PH->use_empty()) {
+ if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
+ SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
+ PH->getParent()->getFirstNonPHI());
+ PH->replaceAllUsesWith(Conv);
+ } else {
+ UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
+ PH->getParent()->getFirstNonPHI());
+ PH->replaceAllUsesWith(Conv);
+ }
+ RecursivelyDeleteTriviallyDeadInstructions(PH);
}
- DeadInsts.insert(PH);
-}
+ // Add a new IVUsers entry for the newly-created integer PHI.
+ IU->AddUsersIfInteresting(NewPHI);
+}
projects / oota-llvm.git / blobdiff