X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopStrengthReduce.cpp;h=db8ab485e394c428ae1b60e83ab27864e3f17893;hb=1d31290634eccc3b360c427282d59780d76b9169;hp=c4ee5237ae83b42b44723fc42db130332f54ea37;hpb=a5dae0cac062a53edb2fc2dcd5be7658388d025a;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index c4ee5237ae8..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,6 +43,9 @@ 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' @@ -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 @@ -412,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; @@ -618,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)) @@ -682,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 @@ -709,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()); @@ -719,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! @@ -732,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); @@ -746,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()); @@ -873,41 +887,67 @@ static bool isZero(SCEVHandle &V) { 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)) { - APInt SInt(SC->getValue()->getValue()); - 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) { - APInt Scale(SInt.getBitWidth(), *I); - if (SInt.abs().ult(Scale) || SInt.srem(Scale) != 0) - continue; - std::map::iterator SI = - IVsByStride.find(SCEVUnknown::getIntegerSCEV(SInt.sdiv(Scale))); - if (SI == IVsByStride.end()) + int64_t SInt = SC->getValue()->getSExtValue(); + if (SInt == 1) return 0; + + 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() == Ty) { - IV = *II; - return Scale.getZExtValue(); - } + 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; } @@ -953,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 @@ -990,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); @@ -1009,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 @@ -1045,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(), @@ -1098,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", @@ -1272,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. @@ -1285,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 @@ -1369,5 +1415,5 @@ void LoopStrengthReduce::runOnLoop(Loop *L) { CastedPointers.clear(); IVUsesByStride.clear(); StrideOrder.clear(); - return; + return false; }