X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIVUsers.cpp;h=e0c5d8fa5f5a6d8c008892d99c152b39412abed3;hb=d9750d38e1af417c1afaed440fcba6bc068a529c;hp=44d72e8e0a90c38251fc5ccf0100d743c0bf0cc8;hpb=454d26dc43207ec537d843229db6f5e6a302e23d;p=oota-llvm.git diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index 44d72e8e0a9..e0c5d8fa5f5 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -12,352 +12,362 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "iv-users" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/IVUsers.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Assembly/AsmAnnotationWriter.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Type.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include using namespace llvm; +#define DEBUG_TYPE "iv-users" + char IVUsers::ID = 0; -static RegisterPass -X("iv-users", "Induction Variable Users", false, true); +INITIALIZE_PASS_BEGIN(IVUsers, "iv-users", + "Induction Variable Users", false, true) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_END(IVUsers, "iv-users", + "Induction Variable Users", false, true) Pass *llvm::createIVUsersPass() { return new IVUsers(); } -/// CollectSubexprs - Split S into subexpressions which can be pulled out into -/// separate registers. -static void CollectSubexprs(const SCEV *S, - SmallVectorImpl &Ops, - ScalarEvolution &SE) { - if (const SCEVAddExpr *Add = dyn_cast(S)) { - // Break out add operands. - for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); - I != E; ++I) - CollectSubexprs(*I, Ops, SE); - return; - } else if (const SCEVAddRecExpr *AR = dyn_cast(S)) { - // Split a non-zero base out of an addrec. - if (!AR->getStart()->isZero()) { - CollectSubexprs(AR->getStart(), Ops, SE); - CollectSubexprs(SE.getAddRecExpr(SE.getIntegerSCEV(0, AR->getType()), - AR->getStepRecurrence(SE), - AR->getLoop()), Ops, SE); - return; - } - } - - // Otherwise use the value itself. - Ops.push_back(S); -} - -/// getSCEVStartAndStride - Compute the start and stride of this expression, -/// returning false if the expression is not a start/stride pair, or true if it -/// is. The stride must be a loop invariant expression, but the start may be -/// a mix of loop invariant and loop variant expressions. The start cannot, -/// however, contain an AddRec from a different loop, unless that loop is an -/// outer loop of the current loop. -static bool getSCEVStartAndStride(const SCEV *&SH, Loop *L, Loop *UseLoop, - const SCEV *&Start, const SCEV *&Stride, - ScalarEvolution *SE, DominatorTree *DT) { - const SCEV *TheAddRec = Start; // Initialize to zero. - - // If the outer level is an AddExpr, the operands are all start values except - // for a nested AddRecExpr. - if (const SCEVAddExpr *AE = dyn_cast(SH)) { - for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i) - if (const SCEVAddRecExpr *AddRec = - dyn_cast(AE->getOperand(i))) - TheAddRec = SE->getAddExpr(AddRec, TheAddRec); - else - Start = SE->getAddExpr(Start, AE->getOperand(i)); - } else if (isa(SH)) { - TheAddRec = SH; - } else { - return false; // not analyzable. +/// isInteresting - Test whether the given expression is "interesting" when +/// used by the given expression, within the context of analyzing the +/// given loop. +static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, + ScalarEvolution *SE, LoopInfo *LI) { + // An addrec is interesting if it's affine or if it has an interesting start. + if (const SCEVAddRecExpr *AR = dyn_cast(S)) { + // Keep things simple. Don't touch loop-variant strides unless they're + // only used outside the loop and we can simplify them. + if (AR->getLoop() == L) + return AR->isAffine() || + (!L->contains(I) && + SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR); + // Otherwise recurse to see if the start value is interesting, and that + // the step value is not interesting, since we don't yet know how to + // do effective SCEV expansions for addrecs with interesting steps. + return isInteresting(AR->getStart(), I, L, SE, LI) && + !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI); } - // Break down TheAddRec into its component parts. - SmallVector Subexprs; - CollectSubexprs(TheAddRec, Subexprs, *SE); - - // Look for an addrec on the current loop among the parts. - const SCEV *AddRecStride = 0; - for (SmallVectorImpl::iterator I = Subexprs.begin(), - E = Subexprs.end(); I != E; ++I) { - const SCEV *S = *I; - if (const SCEVAddRecExpr *AR = dyn_cast(S)) - if (AR->getLoop() == L) { - *I = AR->getStart(); - AddRecStride = AR->getStepRecurrence(*SE); - break; + // An add is interesting if exactly one of its operands is interesting. + if (const SCEVAddExpr *Add = dyn_cast(S)) { + bool AnyInterestingYet = false; + for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); + OI != OE; ++OI) + if (isInteresting(*OI, I, L, SE, LI)) { + if (AnyInterestingYet) + return false; + AnyInterestingYet = true; } - } - if (!AddRecStride) - return false; - - // Add up everything else into a start value (which may not be - // loop-invariant). - const SCEV *AddRecStart = SE->getAddExpr(Subexprs); - - // Use getSCEVAtScope to attempt to simplify other loops out of - // the picture. - AddRecStart = SE->getSCEVAtScope(AddRecStart, UseLoop); - - Start = SE->getAddExpr(Start, AddRecStart); - - // If stride is an instruction, make sure it properly dominates the header. - // Otherwise we could end up with a use before def situation. - if (!isa(AddRecStride)) { - BasicBlock *Header = L->getHeader(); - if (!AddRecStride->properlyDominates(Header, DT)) - return false; - - DEBUG(dbgs() << "["; - WriteAsOperand(dbgs(), L->getHeader(), /*PrintType=*/false); - dbgs() << "] Variable stride: " << *AddRecStride << "\n"); + return AnyInterestingYet; } - Stride = AddRecStride; - return true; + // Nothing else is interesting here. + return false; } -/// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression -/// and now we need to decide whether the user should use the preinc or post-inc -/// value. If this user should use the post-inc version of the IV, return true. -/// -/// Choosing wrong here can break dominance properties (if we choose to use the -/// post-inc value when we cannot) or it can end up adding extra live-ranges to -/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we -/// should use the post-inc value). -static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV, - Loop *L, DominatorTree *DT) { - // If the user is in the loop, use the preinc value. - if (L->contains(User)) return false; - - BasicBlock *LatchBlock = L->getLoopLatch(); - if (!LatchBlock) - return false; - - // Ok, the user is outside of the loop. If it is dominated by the latch - // block, use the post-inc value. - if (DT->dominates(LatchBlock, User->getParent())) - return true; - - // There is one case we have to be careful of: PHI nodes. These little guys - // can live in blocks that are not dominated by the latch block, but (since - // their uses occur in the predecessor block, not the block the PHI lives in) - // should still use the post-inc value. Check for this case now. - PHINode *PN = dyn_cast(User); - if (!PN) return false; // not a phi, not dominated by latch block. - - // Look at all of the uses of IV by the PHI node. If any use corresponds to - // a block that is not dominated by the latch block, give up and use the - // preincremented value. - unsigned NumUses = 0; - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingValue(i) == IV) { - ++NumUses; - if (!DT->dominates(LatchBlock, PN->getIncomingBlock(i))) +/// Return true if all loop headers that dominate this block are in simplified +/// form. +static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, + const LoopInfo *LI, + SmallPtrSetImpl &SimpleLoopNests) { + Loop *NearestLoop = nullptr; + for (DomTreeNode *Rung = DT->getNode(BB); + Rung; Rung = Rung->getIDom()) { + BasicBlock *DomBB = Rung->getBlock(); + Loop *DomLoop = LI->getLoopFor(DomBB); + if (DomLoop && DomLoop->getHeader() == DomBB) { + // If the domtree walk reaches a loop with no preheader, return false. + if (!DomLoop->isLoopSimplifyForm()) return false; + // If we have already checked this loop nest, stop checking. + if (SimpleLoopNests.count(DomLoop)) + break; + // If we have not already checked this loop nest, remember the loop + // header nearest to BB. The nearest loop may not contain BB. + if (!NearestLoop) + NearestLoop = DomLoop; } - - // Okay, all uses of IV by PN are in predecessor blocks that really are - // dominated by the latch block. Use the post-incremented value. + } + if (NearestLoop) + SimpleLoopNests.insert(NearestLoop); return true; } -/// AddUsersIfInteresting - Inspect the specified instruction. If it is a +/// AddUsersImpl - Inspect the specified instruction. If it is a /// reducible SCEV, recursively add its users to the IVUsesByStride set and /// return true. Otherwise, return false. -bool IVUsers::AddUsersIfInteresting(Instruction *I) { +bool IVUsers::AddUsersImpl(Instruction *I, + SmallPtrSetImpl &SimpleLoopNests) { + const DataLayout &DL = I->getModule()->getDataLayout(); + + // Add this IV user to the Processed set before returning false to ensure that + // all IV users are members of the set. See IVUsers::isIVUserOrOperand. + if (!Processed.insert(I).second) + return true; // Instruction already handled. + if (!SE->isSCEVable(I->getType())) return false; // Void and FP expressions cannot be reduced. + // IVUsers is used by LSR which assumes that all SCEV expressions are safe to + // pass to SCEVExpander. Expressions are not safe to expand if they represent + // operations that are not safe to speculate, namely integer division. + if (!isa(I) && !isSafeToSpeculativelyExecute(I)) + return false; + // LSR is not APInt clean, do not touch integers bigger than 64-bits. - if (SE->getTypeSizeInBits(I->getType()) > 64) + // Also avoid creating IVs of non-native types. For example, we don't want a + // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. + uint64_t Width = SE->getTypeSizeInBits(I->getType()); + if (Width > 64 || !DL.isLegalInteger(Width)) return false; - if (!Processed.insert(I)) - return true; // Instruction already handled. + // Don't attempt to promote ephemeral values to indvars. They will be removed + // later anyway. + if (EphValues.count(I)) + return false; // Get the symbolic expression for this instruction. const SCEV *ISE = SE->getSCEV(I); - if (isa(ISE)) return false; - - // Get the start and stride for this expression. - Loop *UseLoop = LI->getLoopFor(I->getParent()); - const SCEV *Start = SE->getIntegerSCEV(0, ISE->getType()); - const SCEV *Stride = Start; - if (!getSCEVStartAndStride(ISE, L, UseLoop, Start, Stride, SE, DT)) - return false; // Non-reducible symbolic expression, bail out. - - // Keep things simple. Don't touch loop-variant strides. - if (!Stride->isLoopInvariant(L) && L->contains(I)) + // If we've come to an uninteresting expression, stop the traversal and + // call this a user. + if (!isInteresting(ISE, I, L, SE, LI)) return false; SmallPtrSet UniqueUsers; - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - Instruction *User = cast(*UI); - if (!UniqueUsers.insert(User)) + for (Use &U : I->uses()) { + Instruction *User = cast(U.getUser()); + if (!UniqueUsers.insert(User).second) continue; // Do not infinitely recurse on PHI nodes. if (isa(User) && Processed.count(User)) continue; + // Only consider IVUsers that are dominated by simplified loop + // headers. Otherwise, SCEVExpander will crash. + BasicBlock *UseBB = User->getParent(); + // A phi's use is live out of its predecessor block. + if (PHINode *PHI = dyn_cast(User)) { + unsigned OperandNo = U.getOperandNo(); + unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); + UseBB = PHI->getIncomingBlock(ValNo); + } + if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests)) + return false; + // Descend recursively, but not into PHI nodes outside the current loop. // It's important to see the entire expression outside the loop to get // choices that depend on addressing mode use right, although we won't - // consider references ouside the loop in all cases. + // consider references outside the loop in all cases. // If User is already in Processed, we don't want to recurse into it again, // but do want to record a second reference in the same instruction. bool AddUserToIVUsers = false; if (LI->getLoopFor(User->getParent()) != L) { if (isa(User) || Processed.count(User) || - !AddUsersIfInteresting(User)) { + !AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; } - } else if (Processed.count(User) || - !AddUsersIfInteresting(User)) { + } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) { DEBUG(dbgs() << "FOUND USER: " << *User << '\n' << " OF SCEV: " << *ISE << '\n'); AddUserToIVUsers = true; } if (AddUserToIVUsers) { - // Okay, we found a user that we cannot reduce. Analyze the instruction - // and decide what to do with it. If we are a use inside of the loop, use - // the value before incrementation, otherwise use it after incrementation. - if (IVUseShouldUsePostIncValue(User, I, L, DT)) { - // The value used will be incremented by the stride more than we are - // expecting, so subtract this off. - const SCEV *NewStart = SE->getMinusSCEV(Start, Stride); - IVUses.push_back(new IVStrideUse(this, Stride, NewStart, User, I)); - IVUses.back().setIsUseOfPostIncrementedValue(true); - DEBUG(dbgs() << " USING POSTINC SCEV, START=" << *NewStart<< "\n"); - } else { - IVUses.push_back(new IVStrideUse(this, Stride, Start, User, I)); + // Okay, we found a user that we cannot reduce. + IVStrideUse &NewUse = AddUser(User, I); + // Autodetect the post-inc loop set, populating NewUse.PostIncLoops. + // The regular return value here is discarded; instead of recording + // it, we just recompute it when we need it. + const SCEV *OriginalISE = ISE; + ISE = TransformForPostIncUse(NormalizeAutodetect, + ISE, User, I, + NewUse.PostIncLoops, + *SE, *DT); + + // PostIncNormalization effectively simplifies the expression under + // pre-increment assumptions. Those assumptions (no wrapping) might not + // hold for the post-inc value. Catch such cases by making sure the + // transformation is invertible. + if (OriginalISE != ISE) { + const SCEV *DenormalizedISE = + TransformForPostIncUse(Denormalize, ISE, User, I, + NewUse.PostIncLoops, *SE, *DT); + + // If we normalized the expression, but denormalization doesn't give the + // original one, discard this user. + if (OriginalISE != DenormalizedISE) { + DEBUG(dbgs() << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): " + << *ISE << '\n'); + IVUses.pop_back(); + return false; + } } + DEBUG(if (SE->getSCEV(I) != ISE) + dbgs() << " NORMALIZED TO: " << *ISE << '\n'); } } return true; } -IVStrideUse &IVUsers::AddUser(const SCEV *Stride, const SCEV *Offset, - Instruction *User, Value *Operand) { - IVUses.push_back(new IVStrideUse(this, Stride, Offset, User, Operand)); +bool IVUsers::AddUsersIfInteresting(Instruction *I) { + // SCEVExpander can only handle users that are dominated by simplified loop + // entries. Keep track of all loops that are only dominated by other simple + // loops so we don't traverse the domtree for each user. + SmallPtrSet SimpleLoopNests; + + return AddUsersImpl(I, SimpleLoopNests); +} + +IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { + IVUses.push_back(new IVStrideUse(this, User, Operand)); return IVUses.back(); } IVUsers::IVUsers() - : LoopPass(&ID) { + : LoopPass(ID) { + initializeIVUsersPass(*PassRegistry::getPassRegistry()); } void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { L = l; - LI = &getAnalysis(); - DT = &getAnalysis(); - SE = &getAnalysis(); + AC = &getAnalysis().getAssumptionCache( + *L->getHeader()->getParent()); + LI = &getAnalysis().getLoopInfo(); + DT = &getAnalysis().getDomTree(); + SE = &getAnalysis().getSE(); + + // Collect ephemeral values so that AddUsersIfInteresting skips them. + EphValues.clear(); + CodeMetrics::collectEphemeralValues(L, AC, EphValues); // Find all uses of induction variables in this loop, and categorize // them by stride. Start by finding all of the PHI nodes in the header for // this loop. If they are induction variables, inspect their uses. for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) - AddUsersIfInteresting(I); + (void)AddUsersIfInteresting(&*I); return false; } -/// getReplacementExpr - Return a SCEV expression which computes the -/// value of the OperandValToReplace of the given IVStrideUse. -const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const { - // Start with zero. - const SCEV *RetVal = SE->getIntegerSCEV(0, U.getStride()->getType()); - // Create the basic add recurrence. - RetVal = SE->getAddRecExpr(RetVal, U.getStride(), L); - // Add the offset in a separate step, because it may be loop-variant. - RetVal = SE->getAddExpr(RetVal, U.getOffset()); - // For uses of post-incremented values, add an extra stride to compute - // the actual replacement value. - if (U.isUseOfPostIncrementedValue()) - RetVal = SE->getAddExpr(RetVal, U.getStride()); - return RetVal; -} - -/// getCanonicalExpr - Return a SCEV expression which computes the -/// value of the SCEV of the given IVStrideUse, ignoring the -/// isUseOfPostIncrementedValue flag. -const SCEV *IVUsers::getCanonicalExpr(const IVStrideUse &U) const { - // Start with zero. - const SCEV *RetVal = SE->getIntegerSCEV(0, U.getStride()->getType()); - // Create the basic add recurrence. - RetVal = SE->getAddRecExpr(RetVal, U.getStride(), L); - // Add the offset in a separate step, because it may be loop-variant. - RetVal = SE->getAddExpr(RetVal, U.getOffset()); - return RetVal; -} - void IVUsers::print(raw_ostream &OS, const Module *M) const { OS << "IV Users for loop "; - WriteAsOperand(OS, L->getHeader(), false); + L->getHeader()->printAsOperand(OS, false); if (SE->hasLoopInvariantBackedgeTakenCount(L)) { OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L); } OS << ":\n"; - // Use a defualt AssemblyAnnotationWriter to suppress the default info - // comments, which aren't relevant here. - AssemblyAnnotationWriter Annotator; for (ilist::const_iterator UI = IVUses.begin(), E = IVUses.end(); UI != E; ++UI) { OS << " "; - WriteAsOperand(OS, UI->getOperandValToReplace(), false); - OS << " = " - << *getReplacementExpr(*UI); - if (UI->isUseOfPostIncrementedValue()) - OS << " (post-inc)"; + UI->getOperandValToReplace()->printAsOperand(OS, false); + OS << " = " << *getReplacementExpr(*UI); + for (PostIncLoopSet::const_iterator + I = UI->PostIncLoops.begin(), + E = UI->PostIncLoops.end(); I != E; ++I) { + OS << " (post-inc with loop "; + (*I)->getHeader()->printAsOperand(OS, false); + OS << ")"; + } OS << " in "; - UI->getUser()->print(OS, &Annotator); + if (UI->getUser()) + UI->getUser()->print(OS); + else + OS << "Printing User"; OS << '\n'; } } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void IVUsers::dump() const { print(dbgs()); } +#endif void IVUsers::releaseMemory() { Processed.clear(); IVUses.clear(); } +/// getReplacementExpr - Return a SCEV expression which computes the +/// value of the OperandValToReplace. +const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const { + return SE->getSCEV(IU.getOperandValToReplace()); +} + +/// getExpr - Return the expression for the use. +const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const { + return + TransformForPostIncUse(Normalize, getReplacementExpr(IU), + IU.getUser(), IU.getOperandValToReplace(), + const_cast(IU.getPostIncLoops()), + *SE, *DT); +} + +static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { + if (const SCEVAddRecExpr *AR = dyn_cast(S)) { + if (AR->getLoop() == L) + return AR; + return findAddRecForLoop(AR->getStart(), L); + } + + if (const SCEVAddExpr *Add = dyn_cast(S)) { + for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); + I != E; ++I) + if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) + return AR; + return nullptr; + } + + return nullptr; +} + +const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { + if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L)) + return AR->getStepRecurrence(*SE); + return nullptr; +} + +void IVStrideUse::transformToPostInc(const Loop *L) { + PostIncLoops.insert(L); +} + void IVStrideUse::deleted() { // Remove this user from the list. + Parent->Processed.erase(this->getUser()); Parent->IVUses.erase(this); // this now dangles! }