From f25ddd991a5601d0101602c4c263a58c7af4b8a2 Mon Sep 17 00:00:00 2001 From: rdivacky Date: Tue, 16 Feb 2010 09:30:23 +0000 Subject: Update LLVM to r96341. --- lib/Analysis/IVUsers.cpp | 176 ++++++++++++++++++++--------------------------- 1 file changed, 76 insertions(+), 100 deletions(-) (limited to 'lib/Analysis/IVUsers.cpp') diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index 38611cc..4ce6868 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -21,6 +21,7 @@ #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/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -35,42 +36,30 @@ Pass *llvm::createIVUsersPass() { return new IVUsers(); } -/// containsAddRecFromDifferentLoop - Determine whether expression S involves a -/// subexpression that is an AddRec from a loop other than L. An outer loop -/// of L is OK, but not an inner loop nor a disjoint loop. -static bool containsAddRecFromDifferentLoop(const SCEV *S, Loop *L) { - // This is very common, put it first. - if (isa(S)) - return false; - if (const SCEVCommutativeExpr *AE = dyn_cast(S)) { - for (unsigned int i=0; i< AE->getNumOperands(); i++) - if (containsAddRecFromDifferentLoop(AE->getOperand(i), L)) - return true; - return false; - } - if (const SCEVAddRecExpr *AE = dyn_cast(S)) { - if (const Loop *newLoop = AE->getLoop()) { - if (newLoop == L) - return false; - // if newLoop is an outer loop of L, this is OK. - if (newLoop->contains(L)) - return false; +/// 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; } - return true; } - if (const SCEVUDivExpr *DE = dyn_cast(S)) - return containsAddRecFromDifferentLoop(DE->getLHS(), L) || - containsAddRecFromDifferentLoop(DE->getRHS(), L); -#if 0 - // SCEVSDivExpr has been backed out temporarily, but will be back; we'll - // need this when it is. - if (const SCEVSDivExpr *DE = dyn_cast(S)) - return containsAddRecFromDifferentLoop(DE->getLHS(), L) || - containsAddRecFromDifferentLoop(DE->getRHS(), L); -#endif - if (const SCEVCastExpr *CE = dyn_cast(S)) - return containsAddRecFromDifferentLoop(CE->getOperand(), L); - return false; + + // Otherwise use the value itself. + Ops.push_back(S); } /// getSCEVStartAndStride - Compute the start and stride of this expression, @@ -89,35 +78,42 @@ static bool getSCEVStartAndStride(const SCEV *&SH, Loop *L, Loop *UseLoop, 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))) { - if (AddRec->getLoop() == L) - TheAddRec = SE->getAddExpr(AddRec, TheAddRec); - else - return false; // Nested IV of some sort? - } else { + 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. } - const SCEVAddRecExpr *AddRec = dyn_cast(TheAddRec); - if (!AddRec || AddRec->getLoop() != L) return false; + // 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; + } + } + 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. - const SCEV *AddRecStart = AddRec->getStart(); AddRecStart = SE->getSCEVAtScope(AddRecStart, UseLoop); - const SCEV *AddRecStride = AddRec->getStepRecurrence(*SE); - - // FIXME: If Start contains an SCEVAddRecExpr from a different loop, other - // than an outer loop of the current loop, reject it. LSR has no concept of - // operating on more than one loop at a time so don't confuse it with such - // expressions. - if (containsAddRecFromDifferentLoop(AddRecStart, L)) - return false; Start = SE->getAddExpr(Start, AddRecStart); @@ -130,7 +126,7 @@ static bool getSCEVStartAndStride(const SCEV *&SH, Loop *L, Loop *UseLoop, DEBUG(dbgs() << "["; WriteAsOperand(dbgs(), L->getHeader(), /*PrintType=*/false); - dbgs() << "] Variable stride: " << *AddRec << "\n"); + dbgs() << "] Variable stride: " << *AddRecStride << "\n"); } Stride = AddRecStride; @@ -246,14 +242,6 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) { } if (AddUserToIVUsers) { - IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride]; - if (!StrideUses) { // First occurrence of this stride? - StrideOrder.push_back(Stride); - StrideUses = new IVUsersOfOneStride(Stride); - IVUses.push_back(StrideUses); - IVUsesByStride[Stride] = StrideUses; - } - // 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. @@ -261,27 +249,21 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) { // 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); - StrideUses->addUser(NewStart, User, I); - StrideUses->Users.back().setIsUseOfPostIncrementedValue(true); + IVUses.push_back(new IVStrideUse(this, Stride, NewStart, User, I)); + IVUses.back().setIsUseOfPostIncrementedValue(true); DEBUG(dbgs() << " USING POSTINC SCEV, START=" << *NewStart<< "\n"); } else { - StrideUses->addUser(Start, User, I); + IVUses.push_back(new IVStrideUse(this, Stride, Start, User, I)); } } } return true; } -void IVUsers::AddUser(const SCEV *Stride, const SCEV *Offset, - Instruction *User, Value *Operand) { - IVUsersOfOneStride *StrideUses = IVUsesByStride[Stride]; - if (!StrideUses) { // First occurrence of this stride? - StrideOrder.push_back(Stride); - StrideUses = new IVUsersOfOneStride(Stride); - IVUses.push_back(StrideUses); - IVUsesByStride[Stride] = StrideUses; - } - IVUsesByStride[Stride]->addUser(Offset, User, Operand); +IVStrideUse &IVUsers::AddUser(const SCEV *Stride, const SCEV *Offset, + Instruction *User, Value *Operand) { + IVUses.push_back(new IVStrideUse(this, Stride, Offset, User, Operand)); + return IVUses.back(); } IVUsers::IVUsers() @@ -315,15 +297,15 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { /// 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.getParent()->Stride->getType()); + const SCEV *RetVal = SE->getIntegerSCEV(0, U.getStride()->getType()); // Create the basic add recurrence. - RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L); + 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.getParent()->Stride); + RetVal = SE->getAddExpr(RetVal, U.getStride()); return RetVal; } @@ -332,9 +314,9 @@ const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const { /// isUseOfPostIncrementedValue flag. const SCEV *IVUsers::getCanonicalExpr(const IVStrideUse &U) const { // Start with zero. - const SCEV *RetVal = SE->getIntegerSCEV(0, U.getParent()->Stride->getType()); + const SCEV *RetVal = SE->getIntegerSCEV(0, U.getStride()->getType()); // Create the basic add recurrence. - RetVal = SE->getAddRecExpr(RetVal, U.getParent()->Stride, L); + 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; @@ -349,24 +331,20 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const { } OS << ":\n"; - for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e; ++Stride) { - std::map::const_iterator SI = - IVUsesByStride.find(StrideOrder[Stride]); - assert(SI != IVUsesByStride.end() && "Stride doesn't exist!"); - OS << " Stride " << *SI->first->getType() << " " << *SI->first << ":\n"; - - for (ilist::const_iterator UI = SI->second->Users.begin(), - E = SI->second->Users.end(); UI != E; ++UI) { - OS << " "; - WriteAsOperand(OS, UI->getOperandValToReplace(), false); - OS << " = "; - OS << *getReplacementExpr(*UI); - if (UI->isUseOfPostIncrementedValue()) - OS << " (post-inc)"; - OS << " in "; - UI->getUser()->print(OS); - 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)"; + OS << " in "; + UI->getUser()->print(OS, &Annotator); + OS << '\n'; } } @@ -375,14 +353,12 @@ void IVUsers::dump() const { } void IVUsers::releaseMemory() { - IVUsesByStride.clear(); - StrideOrder.clear(); Processed.clear(); IVUses.clear(); } void IVStrideUse::deleted() { // Remove this user from the list. - Parent->Users.erase(this); + Parent->IVUses.erase(this); // this now dangles! } -- cgit v1.1