diff options
Diffstat (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/IndVarSimplify.cpp | 935 |
1 files changed, 369 insertions, 566 deletions
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 3d9017d17e..80d34f6f16 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -43,6 +43,8 @@ #include "llvm/Constants.h" #include "llvm/Instructions.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" @@ -51,11 +53,12 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/GetElementPtrTypeIterator.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"); @@ -65,6 +68,7 @@ STATISTIC(NumLFTR , "Number of loop exit tests replaced"); namespace { class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { + IVUsers *IU; LoopInfo *LI; ScalarEvolution *SE; bool Changed; @@ -76,12 +80,15 @@ namespace { 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<IVUsers>(); AU.addPreserved<ScalarEvolution>(); AU.addPreservedID(LoopSimplifyID); + AU.addPreserved<IVUsers>(); AU.addPreservedID(LCSSAID); AU.setPreservesCFG(); } @@ -90,17 +97,21 @@ namespace { void RewriteNonIntegerIVs(Loop *L); - void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount, + ICmpInst *LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount, Value *IndVar, BasicBlock *ExitingBlock, BranchInst *BI, SCEVExpander &Rewriter); void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount); - 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, SCEVExpander &Rewriter); + + void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter); + + void HandleFloatingPointIV(Loop *L, PHINode *PH); }; } @@ -112,31 +123,12 @@ Pass *llvm::createIndVarSimplifyPass() { 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); - 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, +ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount, Value *IndVar, BasicBlock *ExitingBlock, @@ -196,10 +188,15 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L, << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" << " RHS:\t" << *RHS << "\n"; - Value *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI); - BI->setCondition(Cond); + ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI); + + Instruction *OrigCond = cast<Instruction>(BI->getCondition()); + OrigCond->replaceAllUsesWith(Cond); + RecursivelyDeleteTriviallyDeadInstructions(OrigCond); + ++NumLFTR; Changed = true; + return Cond; } /// RewriteLoopExitValues - Check to see if this loop has a computable @@ -207,8 +204,16 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L, /// 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) { + // Verify the input to the pass in already in LCSSA form. + assert(L->isLCSSAForm()); + BasicBlock *Preheader = L->getLoopPreheader(); // Scan all of the instructions in the loop, looking at those that have @@ -226,9 +231,6 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, 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. @@ -268,18 +270,11 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, 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()); + SCEVHandle SH = SE->getSCEV(Inst); + SCEVHandle ExitValue = SE->getSCEVAtScope(SH, L->getParentLoop()); if (isa<SCEVCouldNotCompute>(ExitValue) || !ExitValue->isLoopInvariant(L)) continue; @@ -298,9 +293,8 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, 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 @@ -308,14 +302,12 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, // in the loop, so we don't need an LCSSA phi node anymore. if (NumPreds == 1) { PN->replaceAllUsesWith(ExitVal); - PN->eraseFromParent(); + RecursivelyDeleteTriviallyDeadInstructions(PN); break; } } } } - - DeleteTriviallyDeadInstructions(InstructionsToDelete); } void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { @@ -325,266 +317,24 @@ 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 ScalarEvolution *SE) { - 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(); - else if (const IntToPtrInst *IP = dyn_cast<IntToPtrInst>(UI)) - CandidateType = IP->getDestTy(); - else if (const PtrToIntInst *PI = dyn_cast<PtrToIntInst>(UI)) - CandidateType = PI->getDestTy(); - if (CandidateType && - SE->isSCEVable(CandidateType) && - SE->getTypeSizeInBits(CandidateType) > SE->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. -/// -/// 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 ScalarEvolution &SE, - 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(SE.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(SE.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) { - 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); -} - -static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR, - ScalarEvolution *SE, - const Type *LargestType, Loop *L, - const Type *myType, - SCEVExpander &Rewriter) { - 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); -} - -/// 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>(); SE = &getAnalysis<ScalarEvolution>(); Changed = false; @@ -594,11 +344,8 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { RewriteNonIntegerIVs(L); BasicBlock *Header = L->getHeader(); - BasicBlock *ExitingBlock = L->getExitingBlock(); - SmallPtrSet<Instruction*, 16> DeadInsts; - - // Verify the input to the pass in already in LCSSA form. - assert(L->isLCSSAForm()); + BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null + SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L); // 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 @@ -606,59 +353,45 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // 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; - - for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { - PHINode *PN = cast<PHINode>(I); - if (SE->isSCEVable(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(); LargestType = SE->getEffectiveSCEVType(LargestType); - SizesToInsert.insert(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(); - PNTy = SE->getEffectiveSCEVType(PNTy); - SizesToInsert.insert(PNTy); - const Type *EffTy = getEffectiveIndvarType(PN, SE); - EffTy = SE->getEffectiveSCEVType(EffTy); - SizesToInsert.insert(EffTy); + for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { + SCEVHandle Stride = IU->StrideOrder[i]; + const Type *Ty = SE->getEffectiveSCEVType(Stride->getType()); if (!LargestType || - SE->getTypeSizeInBits(EffTy) > + SE->getTypeSizeInBits(Ty) > SE->getTypeSizeInBits(LargestType)) - LargestType = EffTy; + LargestType = Ty; + + std::map<SCEVHandle, 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; } // Create a rewriter object which we'll use to transform the code with. SCEVExpander Rewriter(*SE, *LI); - // 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()) { + if (NeedCannIV) { IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); ++NumInserted; Changed = true; @@ -667,229 +400,291 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { // 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, *SE, - 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); - } + Rewriter.setInsertionPoint(Header->getFirstNonPHI()); - // 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(); - Rewriter.setInsertionPoint(InsertPt); - - // 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"; - } - } + // Rewrite IV-derived expressions. + RewriteIVExpressions(L, LargestType, Rewriter); - // 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()); - 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); - 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 && - !UInst->use_empty() && - 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()); - uint64_t truncSize = oldSext->getType()->getPrimitiveSizeInBits(); - Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, - L, oldSext->getType(), Rewriter); - APInt APnewAddRHS = APInt(AddRHS->getValue()).sext(newBitSize); - if (newBitSize > truncSize) - APnewAddRHS = APnewAddRHS.trunc(truncSize); - ConstantInt* newAddRHS =ConstantInt::get(APnewAddRHS); - 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 && - !UInst->use_empty() && - 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()); - uint64_t truncSize = oldSext->getType()->getPrimitiveSizeInBits(); - Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, - L, oldSext->getType(), Rewriter); - APInt APnewOrRHS = APInt(RHS->getValue()).sext(newBitSize); - if (newBitSize > truncSize) - APnewOrRHS = APnewOrRHS.trunc(truncSize); - ConstantInt* newOrRHS =ConstantInt::get(APnewOrRHS); - Value *NewOr = - BinaryOperator::CreateOr(TruncIndVar, newOrRHS, - 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(NewOr); - 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); - 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 && - !UInst->use_empty() && - 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()); - uint64_t truncSize = oldZext->getType()->getPrimitiveSizeInBits(); - Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, - L, oldZext->getType(), Rewriter); - APInt APnewAndRHS = APInt(AndRHS->getValue()).zext(newBitSize); - if (newBitSize > truncSize) - APnewAndRHS = APnewAndRHS.trunc(truncSize); - ConstantInt* newAndRHS = ConstantInt::get(APnewAndRHS); - 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); + // 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, Rewriter); + + // Reorder instructions to avoid use-before-def conditions. + FixUsesBeforeDefs(L, Rewriter); + + // 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) { + SCEVHandle Stride = IU->StrideOrder[i]; + + std::map<SCEVHandle, 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) { + SCEVHandle Offset = UI->getOffset(); + Value *Op = UI->getOperandValToReplace(); + Instruction *User = UI->getUser(); + bool isSigned = UI->isSigned(); + + // Compute the final addrec to expand into code. + SCEVHandle 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 (!Stride->isLoopInvariant(L) && + !isa<SCEVConstant>(AR) && + L->contains(User->getParent())) + continue; + + Value *NewVal = 0; + if (AR->isLoopInvariant(L)) { + BasicBlock::iterator I = Rewriter.getInsertionPoint(); + // Expand loop-invariant values in the loop preheader. They will + // be sunk to the exit block later, if possible. + NewVal = + Rewriter.expandCodeFor(AR, LargestType, + L->getLoopPreheader()->getTerminator()); + Rewriter.setInsertionPoint(I); + ++NumReplaced; + } else { + const Type *IVTy = Offset->getType(); + const Type *UseTy = Op->getType(); + + // Promote the Offset and Stride up to the canonical induction + // variable's bit width. + SCEVHandle PromotedOffset = Offset; + SCEVHandle PromotedStride = Stride; + if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType)) { + // It doesn't matter for correctness whether zero or sign extension + // is used here, since the value is truncated away below, but if the + // value is signed, sign extension is more likely to be folded. + if (isSigned) { + PromotedOffset = SE->getSignExtendExpr(PromotedOffset, LargestType); + PromotedStride = SE->getSignExtendExpr(PromotedStride, LargestType); + } else { + PromotedOffset = SE->getZeroExtendExpr(PromotedOffset, LargestType); + // If the stride is obviously negative, use sign extension to + // produce things like x-1 instead of x+255. + if (isa<SCEVConstant>(PromotedStride) && + cast<SCEVConstant>(PromotedStride) + ->getValue()->getValue().isNegative()) + PromotedStride = SE->getSignExtendExpr(PromotedStride, + LargestType); + else + PromotedStride = SE->getZeroExtendExpr(PromotedStride |