X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopStrengthReduce.cpp;h=db8ab485e394c428ae1b60e83ab27864e3f17893;hb=1d31290634eccc3b360c427282d59780d76b9169;hp=1908693cc29f10b2d4665a6534d5cd1f618dfa90;hpb=e4d87aa2de6e52952dca73716386db09aad5a8fd;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 1908693cc29..db8ab485e39 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -23,6 +23,7 @@ #include "llvm/DerivedTypes.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Support/CFG.h" #include "llvm/Support/GetElementPtrTypeIterator.h" @@ -42,11 +43,14 @@ STATISTIC(NumInserted, "Number of PHIs inserted"); STATISTIC(NumVariable, "Number of PHIs with variable strides"); namespace { + + struct BasedUser; + /// IVStrideUse - Keep track of one use of a strided induction variable, where /// the stride is stored externally. The Offset member keeps track of the /// offset from the IV, User is the actual user of the operand, and 'Operand' /// is the operand # of the User that is the use. - struct IVStrideUse { + struct VISIBILITY_HIDDEN IVStrideUse { SCEVHandle Offset; Instruction *User; Value *OperandValToReplace; @@ -66,7 +70,7 @@ namespace { /// have an operand that is based on the trip count multiplied by some stride. /// The stride for all of these users is common and kept external to this /// structure. - struct IVUsersOfOneStride { + struct VISIBILITY_HIDDEN IVUsersOfOneStride { /// Users - Keep track of all of the users of this stride as well as the /// initial value and the operand that uses the IV. std::vector Users; @@ -79,15 +83,15 @@ namespace { /// IVInfo - This structure keeps track of one IV expression inserted during /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as /// well as the PHI node and increment value created for rewrite. - struct IVExpr { + struct VISIBILITY_HIDDEN IVExpr { SCEVHandle Stride; SCEVHandle Base; PHINode *PHI; Value *IncV; IVExpr() - : Stride(SCEVUnknown::getIntegerSCEV(0, Type::UIntTy)), - Base (SCEVUnknown::getIntegerSCEV(0, Type::UIntTy)) {} + : Stride(SCEVUnknown::getIntegerSCEV(0, Type::Int32Ty)), + Base (SCEVUnknown::getIntegerSCEV(0, Type::Int32Ty)) {} IVExpr(const SCEVHandle &stride, const SCEVHandle &base, PHINode *phi, Value *incv) : Stride(stride), Base(base), PHI(phi), IncV(incv) {} @@ -95,7 +99,7 @@ namespace { /// IVsOfOneStride - This structure keeps track of all IV expression inserted /// during StrengthReduceStridedIVUsers for a particular stride of the IV. - struct IVsOfOneStride { + struct VISIBILITY_HIDDEN IVsOfOneStride { std::vector IVs; void addIV(const SCEVHandle &Stride, const SCEVHandle &Base, PHINode *PHI, @@ -104,7 +108,7 @@ namespace { } }; - class VISIBILITY_HIDDEN LoopStrengthReduce : public FunctionPass { + class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass { LoopInfo *LI; ETForest *EF; ScalarEvolution *SE; @@ -143,19 +147,7 @@ namespace { : TLI(tli) { } - virtual bool runOnFunction(Function &) { - LI = &getAnalysis(); - EF = &getAnalysis(); - SE = &getAnalysis(); - TD = &getAnalysis(); - UIntPtrTy = TD->getIntPtrType(); - Changed = false; - - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - runOnLoop(*I); - - return Changed; - } + bool runOnLoop(Loop *L, LPPassManager &LPM); virtual void getAnalysisUsage(AnalysisUsage &AU) const { // We split critical edges, so we change the CFG. However, we do update @@ -179,14 +171,16 @@ namespace { /// Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V); private: - void runOnLoop(Loop *L); bool AddUsersIfInteresting(Instruction *I, Loop *L, std::set &Processed); SCEVHandle GetExpressionSCEV(Instruction *E, Loop *L); void OptimizeIndvars(Loop *L); - unsigned CheckForIVReuse(const SCEVHandle&, IVExpr&, const Type*); + unsigned CheckForIVReuse(const SCEVHandle&, IVExpr&, const Type*, + const std::vector& UsersToProcess); + + bool ValidStride(int64_t, const std::vector& UsersToProcess); void StrengthReduceStridedIVUsers(const SCEVHandle &Stride, IVUsersOfOneStride &Uses, @@ -196,7 +190,7 @@ private: RegisterPass X("loop-reduce", "Loop Strength Reduction"); } -FunctionPass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) { +LoopPass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) { return new LoopStrengthReduce(TLI); } @@ -241,6 +235,16 @@ DeleteTriviallyDeadInstructions(std::set &Insts) { /// GetExpressionSCEV - Compute and return the SCEV for the specified /// instruction. SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp, Loop *L) { + // Pointer to pointer bitcast instructions return the same value as their + // operand. + if (BitCastInst *BCI = dyn_cast(Exp)) { + if (SE->hasSCEV(BCI) || !isa(BCI->getOperand(0))) + return SE->getSCEV(BCI); + SCEVHandle R = GetExpressionSCEV(cast(BCI->getOperand(0)), L); + SE->setSCEV(BCI, R); + return R; + } + // Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions. // If this is a GEP that SE doesn't know about, compute it now and insert it. // If this is not a GEP, or if we have already done this computation, just let @@ -267,7 +271,7 @@ SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp, Loop *L) { if (const StructType *STy = dyn_cast(*GTI)) { const StructLayout *SL = TD->getStructLayout(STy); unsigned Idx = cast(GEP->getOperand(i))->getZExtValue(); - uint64_t Offset = SL->MemberOffsets[Idx]; + uint64_t Offset = SL->getElementOffset(Idx); GEPVal = SCEVAddExpr::get(GEPVal, SCEVUnknown::getIntegerSCEV(Offset, UIntPtrTy)); } else { @@ -334,12 +338,6 @@ static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L, << "] Variable stride: " << *AddRec << "\n"; Stride = AddRec->getOperand(1); - // Check that all constant strides are the unsigned type, we don't want to - // have two IV's one of signed stride 4 and one of unsigned stride 4 to not be - // merged. - assert((!isa(Stride) || Stride->getType()->isUnsigned()) && - "Constants should be canonicalized to unsigned!"); - return true; } @@ -418,10 +416,14 @@ bool LoopStrengthReduce::AddUsersIfInteresting(Instruction *I, Loop *L, SCEVHandle Stride = Start; if (!getSCEVStartAndStride(ISE, L, Start, Stride)) return false; // Non-reducible symbolic expression, bail out. - - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;++UI){ + + for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;) { Instruction *User = cast(*UI); + // Increment iterator now because IVUseShouldUsePostIncValue may remove + // User from the list of I users. + ++UI; + // Do not infinitely recurse on PHI nodes. if (isa(User) && Processed.count(User)) continue; @@ -546,7 +548,7 @@ Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, // If there is no immediate value, skip the next part. if (SCEVConstant *SC = dyn_cast(Imm)) - if (SC->getValue()->isNullValue()) + if (SC->getValue()->isZero()) return Rewriter.expandCodeFor(NewBase, BaseInsertPt, OperandValToReplace->getType()); @@ -624,14 +626,15 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, /// isTargetConstant - Return true if the following can be referenced by the /// immediate field of a target instruction. -static bool isTargetConstant(const SCEVHandle &V, const TargetLowering *TLI) { +static bool isTargetConstant(const SCEVHandle &V, const Type *UseTy, + const TargetLowering *TLI) { if (SCEVConstant *SC = dyn_cast(V)) { - int64_t V = SC->getValue()->getSExtValue(); + int64_t VC = SC->getValue()->getSExtValue(); if (TLI) - return TLI->isLegalAddressImmediate(V); + return TLI->isLegalAddressImmediate(VC, UseTy); else // Defaults to PPC. PPC allows a sign-extended 16-bit immediate field. - return (V > -(1 << 16) && V < (1 << 16)-1); + return (VC > -(1 << 16) && VC < (1 << 16)-1); } if (SCEVUnknown *SU = dyn_cast(V)) @@ -688,15 +691,20 @@ static void MoveLoopVariantsToImediateField(SCEVHandle &Val, SCEVHandle &Imm, /// that can fit into the immediate field of instructions in the target. /// Accumulate these immediate values into the Imm value. static void MoveImmediateValues(const TargetLowering *TLI, + Instruction *User, SCEVHandle &Val, SCEVHandle &Imm, bool isAddress, Loop *L) { + const Type *UseTy = User->getType(); + if (StoreInst *SI = dyn_cast(User)) + UseTy = SI->getOperand(0)->getType(); + if (SCEVAddExpr *SAE = dyn_cast(Val)) { std::vector NewOps; NewOps.reserve(SAE->getNumOperands()); for (unsigned i = 0; i != SAE->getNumOperands(); ++i) { SCEVHandle NewOp = SAE->getOperand(i); - MoveImmediateValues(TLI, NewOp, Imm, isAddress, L); + MoveImmediateValues(TLI, User, NewOp, Imm, isAddress, L); if (!NewOp->isLoopInvariant(L)) { // If this is a loop-variant expression, it must stay in the immediate @@ -715,7 +723,7 @@ static void MoveImmediateValues(const TargetLowering *TLI, } else if (SCEVAddRecExpr *SARE = dyn_cast(Val)) { // Try to pull immediates out of the start value of nested addrec's. SCEVHandle Start = SARE->getStart(); - MoveImmediateValues(TLI, Start, Imm, isAddress, L); + MoveImmediateValues(TLI, User, Start, Imm, isAddress, L); if (Start != SARE->getStart()) { std::vector Ops(SARE->op_begin(), SARE->op_end()); @@ -725,12 +733,12 @@ static void MoveImmediateValues(const TargetLowering *TLI, return; } else if (SCEVMulExpr *SME = dyn_cast(Val)) { // Transform "8 * (4 + v)" -> "32 + 8*V" if "32" fits in the immed field. - if (isAddress && isTargetConstant(SME->getOperand(0), TLI) && + if (isAddress && isTargetConstant(SME->getOperand(0), UseTy, TLI) && SME->getNumOperands() == 2 && SME->isLoopInvariant(L)) { SCEVHandle SubImm = SCEVUnknown::getIntegerSCEV(0, Val->getType()); SCEVHandle NewOp = SME->getOperand(1); - MoveImmediateValues(TLI, NewOp, SubImm, isAddress, L); + MoveImmediateValues(TLI, User, NewOp, SubImm, isAddress, L); // If we extracted something out of the subexpressions, see if we can // simplify this! @@ -738,7 +746,7 @@ static void MoveImmediateValues(const TargetLowering *TLI, // Scale SubImm up by "8". If the result is a target constant, we are // good. SubImm = SCEVMulExpr::get(SubImm, SME->getOperand(0)); - if (isTargetConstant(SubImm, TLI)) { + if (isTargetConstant(SubImm, UseTy, TLI)) { // Accumulate the immediate. Imm = SCEVAddExpr::get(Imm, SubImm); @@ -752,7 +760,7 @@ static void MoveImmediateValues(const TargetLowering *TLI, // Loop-variant expressions must stay in the immediate field of the // expression. - if ((isAddress && isTargetConstant(Val, TLI)) || + if ((isAddress && isTargetConstant(Val, UseTy, TLI)) || !Val->isLoopInvariant(L)) { Imm = SCEVAddExpr::get(Imm, Val); Val = SCEVUnknown::getIntegerSCEV(0, Val->getType()); @@ -785,7 +793,7 @@ static void SeparateSubExprs(std::vector &SubExprs, SeparateSubExprs(SubExprs, SARE->getOperand(0)); } } else if (!isa(Expr) || - !cast(Expr)->getValue()->isNullValue()) { + !cast(Expr)->getValue()->isZero()) { // Do not add zero. SubExprs.push_back(Expr); } @@ -875,45 +883,71 @@ RemoveCommonExpressionsFromUseBases(std::vector &Uses) { /// static bool isZero(SCEVHandle &V) { if (SCEVConstant *SC = dyn_cast(V)) - return SC->getValue()->getZExtValue() == 0; + return SC->getValue()->isZero(); return false; } +/// ValidStride - Check whether the given Scale is valid for all loads and +/// stores in UsersToProcess. Pulled into a function to avoid disturbing the +/// sensibilities of those who dislike goto's. +/// +bool LoopStrengthReduce::ValidStride(int64_t Scale, + const std::vector& UsersToProcess) { + int64_t Imm; + for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) { + if (SCEVConstant *SC = dyn_cast(UsersToProcess[i].Imm)) + Imm = SC->getValue()->getSExtValue(); + else + Imm = 0; + + // If this is a load or other access, pass the type of the access in. + const Type *AccessTy = Type::VoidTy; + if (StoreInst *SI = dyn_cast(UsersToProcess[i].Inst)) + AccessTy = SI->getOperand(0)->getType(); + else if (LoadInst *LI = dyn_cast(UsersToProcess[i].Inst)) + AccessTy = LI->getType(); + + if (!TLI->isLegalAddressScaleAndImm(Scale, Imm, AccessTy)) + return false; + } + return true; +} /// CheckForIVReuse - Returns the multiple if the stride is the multiple /// of a previous stride and it is a legal value for the target addressing /// mode scale component. This allows the users of this stride to be rewritten /// as prev iv * factor. It returns 0 if no reuse is possible. -unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle &Stride, - IVExpr &IV, const Type *Ty) { +unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle &Stride, + IVExpr &IV, const Type *Ty, + const std::vector& UsersToProcess) { if (!TLI) return 0; if (SCEVConstant *SC = dyn_cast(Stride)) { int64_t SInt = SC->getValue()->getSExtValue(); if (SInt == 1) return 0; - for (TargetLowering::legal_am_scale_iterator - I = TLI->legal_am_scale_begin(), E = TLI->legal_am_scale_end(); - I != E; ++I) { - unsigned Scale = *I; - if (unsigned(abs(SInt)) < Scale || (SInt % Scale) != 0) - continue; - std::map::iterator SI = - IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt/Scale, Type::UIntTy)); - if (SI == IVsByStride.end()) + for (std::map::iterator SI= IVsByStride.begin(), + SE = IVsByStride.end(); SI != SE; ++SI) { + int64_t SSInt = cast(SI->first)->getValue()->getSExtValue(); + if (SInt != -SSInt && + (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0)) continue; - for (std::vector::iterator II = SI->second.IVs.begin(), - IE = SI->second.IVs.end(); II != IE; ++II) - // FIXME: Only handle base == 0 for now. - // Only reuse previous IV if it would not require a type conversion. - if (isZero(II->Base) && - II->Base->getType()->canLosslesslyBitCastTo(Ty)) { - IV = *II; - return Scale; - } + int64_t Scale = SInt / SSInt; + // Check that this stride is valid for all the types used for loads and + // stores; if it can be used for some and not others, we might as well use + // the original stride everywhere, since we have to create the IV for it + // anyway. + if (ValidStride(Scale, UsersToProcess)) + for (std::vector::iterator II = SI->second.IVs.begin(), + IE = SI->second.IVs.end(); II != IE; ++II) + // FIXME: Only handle base == 0 for now. + // Only reuse previous IV if it would not require a type conversion. + if (isZero(II->Base) && II->Base->getType() == Ty) { + IV = *II; + return Scale; + } } } - return 0; } @@ -959,21 +993,6 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, SCEVHandle CommonExprs = RemoveCommonExpressionsFromUseBases(UsersToProcess); - // Check if it is possible to reuse a IV with stride that is factor of this - // stride. And the multiple is a number that can be encoded in the scale - // field of the target addressing mode. - PHINode *NewPHI = NULL; - Value *IncV = NULL; - IVExpr ReuseIV; - unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV, - CommonExprs->getType()); - if (RewriteFactor != 0) { - DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride - << " and BASE " << *ReuseIV.Base << " :\n"; - NewPHI = ReuseIV.PHI; - IncV = ReuseIV.IncV; - } - // Next, figure out what we can represent in the immediate fields of // instructions. If we can represent anything there, move it to the imm // fields of the BasedUsers. We do this so that it increases the commonality @@ -996,15 +1015,34 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, if (SI->getOperand(1) == UsersToProcess[i].OperandValToReplace) isAddress = true; - MoveImmediateValues(TLI, UsersToProcess[i].Base, UsersToProcess[i].Imm, - isAddress, L); + MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base, + UsersToProcess[i].Imm, isAddress, L); } } + // Check if it is possible to reuse a IV with stride that is factor of this + // stride. And the multiple is a number that can be encoded in the scale + // field of the target addressing mode. And we will have a valid + // instruction after this substition, including the immediate field, if any. + PHINode *NewPHI = NULL; + Value *IncV = NULL; + IVExpr ReuseIV; + unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV, + CommonExprs->getType(), + UsersToProcess); + if (RewriteFactor != 0) { + DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride + << " and BASE " << *ReuseIV.Base << " :\n"; + NewPHI = ReuseIV.PHI; + IncV = ReuseIV.IncV; + } + + const Type *ReplacedTy = CommonExprs->getType(); + // Now that we know what we need to do, insert the PHI node itself. // - DOUT << "INSERTING IV of STRIDE " << *Stride << " and BASE " - << *CommonExprs << " :\n"; + DOUT << "INSERTING IV of TYPE " << *ReplacedTy << " of STRIDE " + << *Stride << " and BASE " << *CommonExprs << " :\n"; SCEVExpander Rewriter(*SE, *LI); SCEVExpander PreheaderRewriter(*SE, *LI); @@ -1015,7 +1053,6 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, BasicBlock *LatchBlock = L->getLoopLatch(); - const Type *ReplacedTy = CommonExprs->getType(); // Emit the initial base value into the loop preheader. Value *CommonBaseV @@ -1051,7 +1088,7 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, Constant *C = dyn_cast(CommonBaseV); if (!C || (!C->isNullValue() && - !isTargetConstant(SCEVUnknown::get(CommonBaseV), TLI))) + !isTargetConstant(SCEVUnknown::get(CommonBaseV), ReplacedTy, TLI))) // We want the common base emitted into the preheader! This is just // using cast as a copy so BitCast (no-op cast) is appropriate CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV->getType(), @@ -1104,7 +1141,7 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, // this by forcing a BitCast (noop cast) to be inserted into the preheader // in this case. if (Constant *C = dyn_cast(BaseV)) { - if (!C->isNullValue() && !isTargetConstant(Base, TLI)) { + if (!C->isNullValue() && !isTargetConstant(Base, ReplacedTy, TLI)) { // We want this constant emitted into the preheader! This is just // using cast as a copy so BitCast (no-op cast) is appropriate BaseV = new BitCastInst(BaseV, BaseV->getType(), "preheaderinsert", @@ -1155,14 +1192,14 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, // are reusing an IV, it has not been used to initialize the PHI node. // Add it to the expression used to rewrite the uses. if (!isa(CommonBaseV) || - !cast(CommonBaseV)->isNullValue()) + !cast(CommonBaseV)->isZero()) RewriteExpr = SCEVAddExpr::get(RewriteExpr, SCEVUnknown::get(CommonBaseV)); } // Now that we know what we need to do, insert code before User for the // immediate and any loop-variant expressions. - if (!isa(BaseV) || !cast(BaseV)->isNullValue()) + if (!isa(BaseV) || !cast(BaseV)->isZero()) // Add BaseV to the PHI value if needed. RewriteExpr = SCEVAddExpr::get(RewriteExpr, SCEVUnknown::get(BaseV)); @@ -1278,12 +1315,15 @@ namespace { }; } -void LoopStrengthReduce::runOnLoop(Loop *L) { - // First step, transform all loops nesting inside of this loop. - for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I) - runOnLoop(*I); +bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) { + + LI = &getAnalysis(); + EF = &getAnalysis(); + SE = &getAnalysis(); + TD = &getAnalysis(); + UIntPtrTy = TD->getIntPtrType(); - // Next, find all uses of induction variables in this loop, and catagorize + // Find all uses of induction variables in this loop, and catagorize // 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. std::set Processed; // Don't reprocess instructions. @@ -1291,7 +1331,7 @@ void LoopStrengthReduce::runOnLoop(Loop *L) { AddUsersIfInteresting(I, L, Processed); // If we have nothing to do, return. - if (IVUsesByStride.empty()) return; + if (IVUsesByStride.empty()) return false; // Optimize induction variables. Some indvar uses can be transformed to use // strides that will be needed for other purposes. A common example of this @@ -1375,5 +1415,5 @@ void LoopStrengthReduce::runOnLoop(Loop *L) { CastedPointers.clear(); IVUsesByStride.clear(); StrideOrder.clear(); - return; + return false; }