LLVM API Documentation
00001 //===- LoopStrengthReduce.cpp - Strength Reduce IVs in Loops --------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This transformation analyzes and transforms the induction variables (and 00011 // computations derived from them) into forms suitable for efficient execution 00012 // on the target. 00013 // 00014 // This pass performs a strength reduction on array references inside loops that 00015 // have as one or more of their components the loop induction variable, it 00016 // rewrites expressions to take advantage of scaled-index addressing modes 00017 // available on the target, and it performs a variety of other optimizations 00018 // related to loop induction variables. 00019 // 00020 //===----------------------------------------------------------------------===// 00021 00022 #define DEBUG_TYPE "loop-reduce" 00023 #include "llvm/Transforms/Scalar.h" 00024 #include "llvm/Constants.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/IntrinsicInst.h" 00027 #include "llvm/LLVMContext.h" 00028 #include "llvm/Type.h" 00029 #include "llvm/DerivedTypes.h" 00030 #include "llvm/Analysis/Dominators.h" 00031 #include "llvm/Analysis/IVUsers.h" 00032 #include "llvm/Analysis/LoopInfo.h" 00033 #include "llvm/Analysis/LoopPass.h" 00034 #include "llvm/Analysis/ScalarEvolutionExpander.h" 00035 #include "llvm/Transforms/Utils/AddrModeMatcher.h" 00036 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00037 #include "llvm/Transforms/Utils/Local.h" 00038 #include "llvm/ADT/Statistic.h" 00039 #include "llvm/Support/CFG.h" 00040 #include "llvm/Support/Debug.h" 00041 #include "llvm/Support/Compiler.h" 00042 #include "llvm/Support/CommandLine.h" 00043 #include "llvm/Support/ValueHandle.h" 00044 #include "llvm/Support/raw_ostream.h" 00045 #include "llvm/Target/TargetLowering.h" 00046 #include <algorithm> 00047 using namespace llvm; 00048 00049 STATISTIC(NumReduced , "Number of IV uses strength reduced"); 00050 STATISTIC(NumInserted, "Number of PHIs inserted"); 00051 STATISTIC(NumVariable, "Number of PHIs with variable strides"); 00052 STATISTIC(NumEliminated, "Number of strides eliminated"); 00053 STATISTIC(NumShadow, "Number of Shadow IVs optimized"); 00054 STATISTIC(NumImmSunk, "Number of common expr immediates sunk into uses"); 00055 STATISTIC(NumLoopCond, "Number of loop terminating conds optimized"); 00056 00057 static cl::opt<bool> EnableFullLSRMode("enable-full-lsr", 00058 cl::init(false), 00059 cl::Hidden); 00060 00061 namespace { 00062 00063 struct BasedUser; 00064 00065 /// IVInfo - This structure keeps track of one IV expression inserted during 00066 /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as 00067 /// well as the PHI node and increment value created for rewrite. 00068 struct VISIBILITY_HIDDEN IVExpr { 00069 const SCEV *Stride; 00070 const SCEV *Base; 00071 PHINode *PHI; 00072 00073 IVExpr(const SCEV *const stride, const SCEV *const base, PHINode *phi) 00074 : Stride(stride), Base(base), PHI(phi) {} 00075 }; 00076 00077 /// IVsOfOneStride - This structure keeps track of all IV expression inserted 00078 /// during StrengthReduceStridedIVUsers for a particular stride of the IV. 00079 struct VISIBILITY_HIDDEN IVsOfOneStride { 00080 std::vector<IVExpr> IVs; 00081 00082 void addIV(const SCEV *const Stride, const SCEV *const Base, PHINode *PHI) { 00083 IVs.push_back(IVExpr(Stride, Base, PHI)); 00084 } 00085 }; 00086 00087 class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass { 00088 IVUsers *IU; 00089 LoopInfo *LI; 00090 DominatorTree *DT; 00091 ScalarEvolution *SE; 00092 bool Changed; 00093 00094 /// IVsByStride - Keep track of all IVs that have been inserted for a 00095 /// particular stride. 00096 std::map<const SCEV *, IVsOfOneStride> IVsByStride; 00097 00098 /// StrideNoReuse - Keep track of all the strides whose ivs cannot be 00099 /// reused (nor should they be rewritten to reuse other strides). 00100 SmallSet<const SCEV *, 4> StrideNoReuse; 00101 00102 /// DeadInsts - Keep track of instructions we may have made dead, so that 00103 /// we can remove them after we are done working. 00104 SmallVector<WeakVH, 16> DeadInsts; 00105 00106 /// TLI - Keep a pointer of a TargetLowering to consult for determining 00107 /// transformation profitability. 00108 const TargetLowering *TLI; 00109 00110 public: 00111 static char ID; // Pass ID, replacement for typeid 00112 explicit LoopStrengthReduce(const TargetLowering *tli = NULL) : 00113 LoopPass(&ID), TLI(tli) { 00114 } 00115 00116 bool runOnLoop(Loop *L, LPPassManager &LPM); 00117 00118 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00119 // We split critical edges, so we change the CFG. However, we do update 00120 // many analyses if they are around. 00121 AU.addPreservedID(LoopSimplifyID); 00122 AU.addPreserved<LoopInfo>(); 00123 AU.addPreserved<DominanceFrontier>(); 00124 AU.addPreserved<DominatorTree>(); 00125 00126 AU.addRequiredID(LoopSimplifyID); 00127 AU.addRequired<LoopInfo>(); 00128 AU.addRequired<DominatorTree>(); 00129 AU.addRequired<ScalarEvolution>(); 00130 AU.addPreserved<ScalarEvolution>(); 00131 AU.addRequired<IVUsers>(); 00132 AU.addPreserved<IVUsers>(); 00133 } 00134 00135 private: 00136 ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond, 00137 IVStrideUse* &CondUse, 00138 const SCEV *const * &CondStride); 00139 00140 void OptimizeIndvars(Loop *L); 00141 void OptimizeLoopCountIV(Loop *L); 00142 void OptimizeLoopTermCond(Loop *L); 00143 00144 /// OptimizeShadowIV - If IV is used in a int-to-float cast 00145 /// inside the loop then try to eliminate the cast opeation. 00146 void OptimizeShadowIV(Loop *L); 00147 00148 /// OptimizeMax - Rewrite the loop's terminating condition 00149 /// if it uses a max computation. 00150 ICmpInst *OptimizeMax(Loop *L, ICmpInst *Cond, 00151 IVStrideUse* &CondUse); 00152 00153 bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse, 00154 const SCEV *const * &CondStride); 00155 bool RequiresTypeConversion(const Type *Ty, const Type *NewTy); 00156 const SCEV *CheckForIVReuse(bool, bool, bool, const SCEV *const&, 00157 IVExpr&, const Type*, 00158 const std::vector<BasedUser>& UsersToProcess); 00159 bool ValidScale(bool, int64_t, 00160 const std::vector<BasedUser>& UsersToProcess); 00161 bool ValidOffset(bool, int64_t, int64_t, 00162 const std::vector<BasedUser>& UsersToProcess); 00163 const SCEV *CollectIVUsers(const SCEV *const &Stride, 00164 IVUsersOfOneStride &Uses, 00165 Loop *L, 00166 bool &AllUsesAreAddresses, 00167 bool &AllUsesAreOutsideLoop, 00168 std::vector<BasedUser> &UsersToProcess); 00169 bool ShouldUseFullStrengthReductionMode( 00170 const std::vector<BasedUser> &UsersToProcess, 00171 const Loop *L, 00172 bool AllUsesAreAddresses, 00173 const SCEV *Stride); 00174 void PrepareToStrengthReduceFully( 00175 std::vector<BasedUser> &UsersToProcess, 00176 const SCEV *Stride, 00177 const SCEV *CommonExprs, 00178 const Loop *L, 00179 SCEVExpander &PreheaderRewriter); 00180 void PrepareToStrengthReduceFromSmallerStride( 00181 std::vector<BasedUser> &UsersToProcess, 00182 Value *CommonBaseV, 00183 const IVExpr &ReuseIV, 00184 Instruction *PreInsertPt); 00185 void PrepareToStrengthReduceWithNewPhi( 00186 std::vector<BasedUser> &UsersToProcess, 00187 const SCEV *Stride, 00188 const SCEV *CommonExprs, 00189 Value *CommonBaseV, 00190 Instruction *IVIncInsertPt, 00191 const Loop *L, 00192 SCEVExpander &PreheaderRewriter); 00193 void StrengthReduceStridedIVUsers(const SCEV *const &Stride, 00194 IVUsersOfOneStride &Uses, 00195 Loop *L); 00196 void DeleteTriviallyDeadInstructions(); 00197 }; 00198 } 00199 00200 char LoopStrengthReduce::ID = 0; 00201 static RegisterPass<LoopStrengthReduce> 00202 X("loop-reduce", "Loop Strength Reduction"); 00203 00204 Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) { 00205 return new LoopStrengthReduce(TLI); 00206 } 00207 00208 /// DeleteTriviallyDeadInstructions - If any of the instructions is the 00209 /// specified set are trivially dead, delete them and see if this makes any of 00210 /// their operands subsequently dead. 00211 void LoopStrengthReduce::DeleteTriviallyDeadInstructions() { 00212 if (DeadInsts.empty()) return; 00213 00214 while (!DeadInsts.empty()) { 00215 Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.back()); 00216 DeadInsts.pop_back(); 00217 00218 if (I == 0 || !isInstructionTriviallyDead(I)) 00219 continue; 00220 00221 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) { 00222 if (Instruction *U = dyn_cast<Instruction>(*OI)) { 00223 *OI = 0; 00224 if (U->use_empty()) 00225 DeadInsts.push_back(U); 00226 } 00227 } 00228 00229 I->eraseFromParent(); 00230 Changed = true; 00231 } 00232 } 00233 00234 /// containsAddRecFromDifferentLoop - Determine whether expression S involves a 00235 /// subexpression that is an AddRec from a loop other than L. An outer loop 00236 /// of L is OK, but not an inner loop nor a disjoint loop. 00237 static bool containsAddRecFromDifferentLoop(const SCEV *S, Loop *L) { 00238 // This is very common, put it first. 00239 if (isa<SCEVConstant>(S)) 00240 return false; 00241 if (const SCEVCommutativeExpr *AE = dyn_cast<SCEVCommutativeExpr>(S)) { 00242 for (unsigned int i=0; i< AE->getNumOperands(); i++) 00243 if (containsAddRecFromDifferentLoop(AE->getOperand(i), L)) 00244 return true; 00245 return false; 00246 } 00247 if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) { 00248 if (const Loop *newLoop = AE->getLoop()) { 00249 if (newLoop == L) 00250 return false; 00251 // if newLoop is an outer loop of L, this is OK. 00252 if (!LoopInfo::isNotAlreadyContainedIn(L, newLoop)) 00253 return false; 00254 } 00255 return true; 00256 } 00257 if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S)) 00258 return containsAddRecFromDifferentLoop(DE->getLHS(), L) || 00259 containsAddRecFromDifferentLoop(DE->getRHS(), L); 00260 #if 0 00261 // SCEVSDivExpr has been backed out temporarily, but will be back; we'll 00262 // need this when it is. 00263 if (const SCEVSDivExpr *DE = dyn_cast<SCEVSDivExpr>(S)) 00264 return containsAddRecFromDifferentLoop(DE->getLHS(), L) || 00265 containsAddRecFromDifferentLoop(DE->getRHS(), L); 00266 #endif 00267 if (const SCEVCastExpr *CE = dyn_cast<SCEVCastExpr>(S)) 00268 return containsAddRecFromDifferentLoop(CE->getOperand(), L); 00269 return false; 00270 } 00271 00272 /// isAddressUse - Returns true if the specified instruction is using the 00273 /// specified value as an address. 00274 static bool isAddressUse(Instruction *Inst, Value *OperandVal) { 00275 bool isAddress = isa<LoadInst>(Inst); 00276 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 00277 if (SI->getOperand(1) == OperandVal) 00278 isAddress = true; 00279 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 00280 // Addressing modes can also be folded into prefetches and a variety 00281 // of intrinsics. 00282 switch (II->getIntrinsicID()) { 00283 default: break; 00284 case Intrinsic::prefetch: 00285 case Intrinsic::x86_sse2_loadu_dq: 00286 case Intrinsic::x86_sse2_loadu_pd: 00287 case Intrinsic::x86_sse_loadu_ps: 00288 case Intrinsic::x86_sse_storeu_ps: 00289 case Intrinsic::x86_sse2_storeu_pd: 00290 case Intrinsic::x86_sse2_storeu_dq: 00291 case Intrinsic::x86_sse2_storel_dq: 00292 if (II->getOperand(1) == OperandVal) 00293 isAddress = true; 00294 break; 00295 } 00296 } 00297 return isAddress; 00298 } 00299 00300 /// getAccessType - Return the type of the memory being accessed. 00301 static const Type *getAccessType(const Instruction *Inst) { 00302 const Type *AccessTy = Inst->getType(); 00303 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) 00304 AccessTy = SI->getOperand(0)->getType(); 00305 else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 00306 // Addressing modes can also be folded into prefetches and a variety 00307 // of intrinsics. 00308 switch (II->getIntrinsicID()) { 00309 default: break; 00310 case Intrinsic::x86_sse_storeu_ps: 00311 case Intrinsic::x86_sse2_storeu_pd: 00312 case Intrinsic::x86_sse2_storeu_dq: 00313 case Intrinsic::x86_sse2_storel_dq: 00314 AccessTy = II->getOperand(1)->getType(); 00315 break; 00316 } 00317 } 00318 return AccessTy; 00319 } 00320 00321 namespace { 00322 /// BasedUser - For a particular base value, keep information about how we've 00323 /// partitioned the expression so far. 00324 struct BasedUser { 00325 /// SE - The current ScalarEvolution object. 00326 ScalarEvolution *SE; 00327 00328 /// Base - The Base value for the PHI node that needs to be inserted for 00329 /// this use. As the use is processed, information gets moved from this 00330 /// field to the Imm field (below). BasedUser values are sorted by this 00331 /// field. 00332 const SCEV *Base; 00333 00334 /// Inst - The instruction using the induction variable. 00335 Instruction *Inst; 00336 00337 /// OperandValToReplace - The operand value of Inst to replace with the 00338 /// EmittedBase. 00339 Value *OperandValToReplace; 00340 00341 /// Imm - The immediate value that should be added to the base immediately 00342 /// before Inst, because it will be folded into the imm field of the 00343 /// instruction. This is also sometimes used for loop-variant values that 00344 /// must be added inside the loop. 00345 const SCEV *Imm; 00346 00347 /// Phi - The induction variable that performs the striding that 00348 /// should be used for this user. 00349 PHINode *Phi; 00350 00351 // isUseOfPostIncrementedValue - True if this should use the 00352 // post-incremented version of this IV, not the preincremented version. 00353 // This can only be set in special cases, such as the terminating setcc 00354 // instruction for a loop and uses outside the loop that are dominated by 00355 // the loop. 00356 bool isUseOfPostIncrementedValue; 00357 00358 BasedUser(IVStrideUse &IVSU, ScalarEvolution *se) 00359 : SE(se), Base(IVSU.getOffset()), Inst(IVSU.getUser()), 00360 OperandValToReplace(IVSU.getOperandValToReplace()), 00361 Imm(SE->getIntegerSCEV(0, Base->getType())), 00362 isUseOfPostIncrementedValue(IVSU.isUseOfPostIncrementedValue()) {} 00363 00364 // Once we rewrite the code to insert the new IVs we want, update the 00365 // operands of Inst to use the new expression 'NewBase', with 'Imm' added 00366 // to it. 00367 void RewriteInstructionToUseNewBase(const SCEV *const &NewBase, 00368 Instruction *InsertPt, 00369 SCEVExpander &Rewriter, Loop *L, Pass *P, 00370 LoopInfo &LI, 00371 SmallVectorImpl<WeakVH> &DeadInsts); 00372 00373 Value *InsertCodeForBaseAtPosition(const SCEV *const &NewBase, 00374 const Type *Ty, 00375 SCEVExpander &Rewriter, 00376 Instruction *IP, Loop *L, 00377 LoopInfo &LI); 00378 void dump() const; 00379 }; 00380 } 00381 00382 void BasedUser::dump() const { 00383 cerr << " Base=" << *Base; 00384 cerr << " Imm=" << *Imm; 00385 cerr << " Inst: " << *Inst; 00386 } 00387 00388 Value *BasedUser::InsertCodeForBaseAtPosition(const SCEV *const &NewBase, 00389 const Type *Ty, 00390 SCEVExpander &Rewriter, 00391 Instruction *IP, Loop *L, 00392 LoopInfo &LI) { 00393 // Figure out where we *really* want to insert this code. In particular, if 00394 // the user is inside of a loop that is nested inside of L, we really don't 00395 // want to insert this expression before the user, we'd rather pull it out as 00396 // many loops as possible. 00397 Instruction *BaseInsertPt = IP; 00398 00399 // Figure out the most-nested loop that IP is in. 00400 Loop *InsertLoop = LI.getLoopFor(IP->getParent()); 00401 00402 // If InsertLoop is not L, and InsertLoop is nested inside of L, figure out 00403 // the preheader of the outer-most loop where NewBase is not loop invariant. 00404 if (L->contains(IP->getParent())) 00405 while (InsertLoop && NewBase->isLoopInvariant(InsertLoop)) { 00406 BaseInsertPt = InsertLoop->getLoopPreheader()->getTerminator(); 00407 InsertLoop = InsertLoop->getParentLoop(); 00408 } 00409 00410 Value *Base = Rewriter.expandCodeFor(NewBase, 0, BaseInsertPt); 00411 00412 const SCEV *NewValSCEV = SE->getUnknown(Base); 00413 00414 // Always emit the immediate into the same block as the user. 00415 NewValSCEV = SE->getAddExpr(NewValSCEV, Imm); 00416 00417 return Rewriter.expandCodeFor(NewValSCEV, Ty, IP); 00418 } 00419 00420 00421 // Once we rewrite the code to insert the new IVs we want, update the 00422 // operands of Inst to use the new expression 'NewBase', with 'Imm' added 00423 // to it. NewBasePt is the last instruction which contributes to the 00424 // value of NewBase in the case that it's a diffferent instruction from 00425 // the PHI that NewBase is computed from, or null otherwise. 00426 // 00427 void BasedUser::RewriteInstructionToUseNewBase(const SCEV *const &NewBase, 00428 Instruction *NewBasePt, 00429 SCEVExpander &Rewriter, Loop *L, Pass *P, 00430 LoopInfo &LI, 00431 SmallVectorImpl<WeakVH> &DeadInsts) { 00432 if (!isa<PHINode>(Inst)) { 00433 // By default, insert code at the user instruction. 00434 BasicBlock::iterator InsertPt = Inst; 00435 00436 // However, if the Operand is itself an instruction, the (potentially 00437 // complex) inserted code may be shared by many users. Because of this, we 00438 // want to emit code for the computation of the operand right before its old 00439 // computation. This is usually safe, because we obviously used to use the 00440 // computation when it was computed in its current block. However, in some 00441 // cases (e.g. use of a post-incremented induction variable) the NewBase 00442 // value will be pinned to live somewhere after the original computation. 00443 // In this case, we have to back off. 00444 // 00445 // If this is a use outside the loop (which means after, since it is based 00446 // on a loop indvar) we use the post-incremented value, so that we don't 00447 // artificially make the preinc value live out the bottom of the loop. 00448 if (!isUseOfPostIncrementedValue && L->contains(Inst->getParent())) { 00449 if (NewBasePt && isa<PHINode>(OperandValToReplace)) { 00450 InsertPt = NewBasePt; 00451 ++InsertPt; 00452 } else if (Instruction *OpInst 00453 = dyn_cast<Instruction>(OperandValToReplace)) { 00454 InsertPt = OpInst; 00455 while (isa<PHINode>(InsertPt)) ++InsertPt; 00456 } 00457 } 00458 Value *NewVal = InsertCodeForBaseAtPosition(NewBase, 00459 OperandValToReplace->getType(), 00460 Rewriter, InsertPt, L, LI); 00461 // Replace the use of the operand Value with the new Phi we just created. 00462 Inst->replaceUsesOfWith(OperandValToReplace, NewVal); 00463 00464 DOUT << " Replacing with "; 00465 DEBUG(WriteAsOperand(*DOUT, NewVal, /*PrintType=*/false)); 00466 DOUT << ", which has value " << *NewBase << " plus IMM " << *Imm << "\n"; 00467 return; 00468 } 00469 00470 // PHI nodes are more complex. We have to insert one copy of the NewBase+Imm 00471 // expression into each operand block that uses it. Note that PHI nodes can 00472 // have multiple entries for the same predecessor. We use a map to make sure 00473 // that a PHI node only has a single Value* for each predecessor (which also 00474 // prevents us from inserting duplicate code in some blocks). 00475 DenseMap<BasicBlock*, Value*> InsertedCode; 00476 PHINode *PN = cast<PHINode>(Inst); 00477 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 00478 if (PN->getIncomingValue(i) == OperandValToReplace) { 00479 // If the original expression is outside the loop, put the replacement 00480 // code in the same place as the original expression, 00481 // which need not be an immediate predecessor of this PHI. This way we 00482 // need only one copy of it even if it is referenced multiple times in 00483 // the PHI. We don't do this when the original expression is inside the 00484 // loop because multiple copies sometimes do useful sinking of code in 00485 // that case(?). 00486 Instruction *OldLoc = dyn_cast<Instruction>(OperandValToReplace); 00487 if (L->contains(OldLoc->getParent())) { 00488 // If this is a critical edge, split the edge so that we do not insert 00489 // the code on all predecessor/successor paths. We do this unless this 00490 // is the canonical backedge for this loop, as this can make some 00491 // inserted code be in an illegal position. 00492 BasicBlock *PHIPred = PN->getIncomingBlock(i); 00493 if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 && 00494 (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) { 00495 00496 // First step, split the critical edge. 00497 SplitCriticalEdge(PHIPred, PN->getParent(), P, false); 00498 00499 // Next step: move the basic block. In particular, if the PHI node 00500 // is outside of the loop, and PredTI is in the loop, we want to 00501 // move the block to be immediately before the PHI block, not 00502 // immediately after PredTI. 00503 if (L->contains(PHIPred) && !L->contains(PN->getParent())) { 00504 BasicBlock *NewBB = PN->getIncomingBlock(i); 00505 NewBB->moveBefore(PN->getParent()); 00506 } 00507 00508 // Splitting the edge can reduce the number of PHI entries we have. 00509 e = PN->getNumIncomingValues(); 00510 } 00511 } 00512 Value *&Code = InsertedCode[PN->getIncomingBlock(i)]; 00513 if (!Code) { 00514 // Insert the code into the end of the predecessor block. 00515 Instruction *InsertPt = (L->contains(OldLoc->getParent())) ? 00516 PN->getIncomingBlock(i)->getTerminator() : 00517 OldLoc->getParent()->getTerminator(); 00518 Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(), 00519 Rewriter, InsertPt, L, LI); 00520 00521 DOUT << " Changing PHI use to "; 00522 DEBUG(WriteAsOperand(*DOUT, Code, /*PrintType=*/false)); 00523 DOUT << ", which has value " << *NewBase << " plus IMM " << *Imm << "\n"; 00524 } 00525 00526 // Replace the use of the operand Value with the new Phi we just created. 00527 PN->setIncomingValue(i, Code); 00528 Rewriter.clear(); 00529 } 00530 } 00531 00532 // PHI node might have become a constant value after SplitCriticalEdge. 00533 DeadInsts.push_back(Inst); 00534 } 00535 00536 00537 /// fitsInAddressMode - Return true if V can be subsumed within an addressing 00538 /// mode, and does not need to be put in a register first. 00539 static bool fitsInAddressMode(const SCEV *const &V, const Type *AccessTy, 00540 const TargetLowering *TLI, bool HasBaseReg) { 00541 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) { 00542 int64_t VC = SC->getValue()->getSExtValue(); 00543 if (TLI) { 00544 TargetLowering::AddrMode AM; 00545 AM.BaseOffs = VC; 00546 AM.HasBaseReg = HasBaseReg; 00547 return TLI->isLegalAddressingMode(AM, AccessTy); 00548 } else { 00549 // Defaults to PPC. PPC allows a sign-extended 16-bit immediate field. 00550 return (VC > -(1 << 16) && VC < (1 << 16)-1); 00551 } 00552 } 00553 00554 if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) 00555 if (GlobalValue *GV = dyn_cast<GlobalValue>(SU->getValue())) { 00556 if (TLI) { 00557 TargetLowering::AddrMode AM; 00558 AM.BaseGV = GV; 00559 AM.HasBaseReg = HasBaseReg; 00560 return TLI->isLegalAddressingMode(AM, AccessTy); 00561 } else { 00562 // Default: assume global addresses are not legal. 00563 } 00564 } 00565 00566 return false; 00567 } 00568 00569 /// MoveLoopVariantsToImmediateField - Move any subexpressions from Val that are 00570 /// loop varying to the Imm operand. 00571 static void MoveLoopVariantsToImmediateField(const SCEV *&Val, const SCEV *&Imm, 00572 Loop *L, ScalarEvolution *SE) { 00573 if (Val->isLoopInvariant(L)) return; // Nothing to do. 00574 00575 if (const SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) { 00576 SmallVector<const SCEV *, 4> NewOps; 00577 NewOps.reserve(SAE->getNumOperands()); 00578 00579 for (unsigned i = 0; i != SAE->getNumOperands(); ++i) 00580 if (!SAE->getOperand(i)->isLoopInvariant(L)) { 00581 // If this is a loop-variant expression, it must stay in the immediate 00582 // field of the expression. 00583 Imm = SE->getAddExpr(Imm, SAE->getOperand(i)); 00584 } else { 00585 NewOps.push_back(SAE->getOperand(i)); 00586 } 00587 00588 if (NewOps.empty()) 00589 Val = SE->getIntegerSCEV(0, Val->getType()); 00590 else 00591 Val = SE->getAddExpr(NewOps); 00592 } else if (const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) { 00593 // Try to pull immediates out of the start value of nested addrec's. 00594 const SCEV *Start = SARE->getStart(); 00595 MoveLoopVariantsToImmediateField(Start, Imm, L, SE); 00596 00597 SmallVector<const SCEV *, 4> Ops(SARE->op_begin(), SARE->op_end()); 00598 Ops[0] = Start; 00599 Val = SE->getAddRecExpr(Ops, SARE->getLoop()); 00600 } else { 00601 // Otherwise, all of Val is variant, move the whole thing over. 00602 Imm = SE->getAddExpr(Imm, Val); 00603 Val = SE->getIntegerSCEV(0, Val->getType()); 00604 } 00605 } 00606 00607 00608 /// MoveImmediateValues - Look at Val, and pull out any additions of constants 00609 /// that can fit into the immediate field of instructions in the target. 00610 /// Accumulate these immediate values into the Imm value. 00611 static void MoveImmediateValues(const TargetLowering *TLI, 00612 const Type *AccessTy, 00613 const SCEV *&Val, const SCEV *&Imm, 00614 bool isAddress, Loop *L, 00615 ScalarEvolution *SE) { 00616 if (const SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) { 00617 SmallVector<const SCEV *, 4> NewOps; 00618 NewOps.reserve(SAE->getNumOperands()); 00619 00620 for (unsigned i = 0; i != SAE->getNumOperands(); ++i) { 00621 const SCEV *NewOp = SAE->getOperand(i); 00622 MoveImmediateValues(TLI, AccessTy, NewOp, Imm, isAddress, L, SE); 00623 00624 if (!NewOp->isLoopInvariant(L)) { 00625 // If this is a loop-variant expression, it must stay in the immediate 00626 // field of the expression. 00627 Imm = SE->getAddExpr(Imm, NewOp); 00628 } else { 00629 NewOps.push_back(NewOp); 00630 } 00631 } 00632 00633 if (NewOps.empty()) 00634 Val = SE->getIntegerSCEV(0, Val->getType()); 00635 else 00636 Val = SE->getAddExpr(NewOps); 00637 return; 00638 } else if (const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) { 00639 // Try to pull immediates out of the start value of nested addrec's. 00640 const SCEV *Start = SARE->getStart(); 00641 MoveImmediateValues(TLI, AccessTy, Start, Imm, isAddress, L, SE); 00642 00643 if (Start != SARE->getStart()) { 00644 SmallVector<const SCEV *, 4> Ops(SARE->op_begin(), SARE->op_end()); 00645 Ops[0] = Start; 00646 Val = SE->getAddRecExpr(Ops, SARE->getLoop()); 00647 } 00648 return; 00649 } else if (const SCEVMulExpr *SME = dyn_cast<SCEVMulExpr>(Val)) { 00650 // Transform "8 * (4 + v)" -> "32 + 8*V" if "32" fits in the immed field. 00651 if (isAddress && 00652 fitsInAddressMode(SME->getOperand(0), AccessTy, TLI, false) && 00653 SME->getNumOperands() == 2 && SME->isLoopInvariant(L)) { 00654 00655 const SCEV *SubImm = SE->getIntegerSCEV(0, Val->getType()); 00656 const SCEV *NewOp = SME->getOperand(1); 00657 MoveImmediateValues(TLI, AccessTy, NewOp, SubImm, isAddress, L, SE); 00658 00659 // If we extracted something out of the subexpressions, see if we can 00660 // simplify this! 00661 if (NewOp != SME->getOperand(1)) { 00662 // Scale SubImm up by "8". If the result is a target constant, we are 00663 // good. 00664 SubImm = SE->getMulExpr(SubImm, SME->getOperand(0)); 00665 if (fitsInAddressMode(SubImm, AccessTy, TLI, false)) { 00666 // Accumulate the immediate. 00667 Imm = SE->getAddExpr(Imm, SubImm); 00668 00669 // Update what is left of 'Val'. 00670 Val = SE->getMulExpr(SME->getOperand(0), NewOp); 00671 return; 00672 } 00673 } 00674 } 00675 } 00676 00677 // Loop-variant expressions must stay in the immediate field of the 00678 // expression. 00679 if ((isAddress && fitsInAddressMode(Val, AccessTy, TLI, false)) || 00680 !Val->isLoopInvariant(L)) { 00681 Imm = SE->getAddExpr(Imm, Val); 00682 Val = SE->getIntegerSCEV(0, Val->getType()); 00683 return; 00684 } 00685 00686 // Otherwise, no immediates to move. 00687 } 00688 00689 static void MoveImmediateValues(const TargetLowering *TLI, 00690 Instruction *User, 00691 const SCEV *&Val, const SCEV *&Imm, 00692 bool isAddress, Loop *L, 00693 ScalarEvolution *SE) { 00694 const Type *AccessTy = getAccessType(User); 00695 MoveImmediateValues(TLI, AccessTy, Val, Imm, isAddress, L, SE); 00696 } 00697 00698 /// SeparateSubExprs - Decompose Expr into all of the subexpressions that are 00699 /// added together. This is used to reassociate common addition subexprs 00700 /// together for maximal sharing when rewriting bases. 00701 static void SeparateSubExprs(SmallVector<const SCEV *, 16> &SubExprs, 00702 const SCEV *Expr, 00703 ScalarEvolution *SE) { 00704 if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(Expr)) { 00705 for (unsigned j = 0, e = AE->getNumOperands(); j != e; ++j) 00706 SeparateSubExprs(SubExprs, AE->getOperand(j), SE); 00707 } else if (const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Expr)) { 00708 const SCEV *Zero = SE->getIntegerSCEV(0, Expr->getType()); 00709 if (SARE->getOperand(0) == Zero) { 00710 SubExprs.push_back(Expr); 00711 } else { 00712 // Compute the addrec with zero as its base. 00713 SmallVector<const SCEV *, 4> Ops(SARE->op_begin(), SARE->op_end()); 00714 Ops[0] = Zero; // Start with zero base. 00715 SubExprs.push_back(SE->getAddRecExpr(Ops, SARE->getLoop())); 00716 00717 00718 SeparateSubExprs(SubExprs, SARE->getOperand(0), SE); 00719 } 00720 } else if (!Expr->isZero()) { 00721 // Do not add zero. 00722 SubExprs.push_back(Expr); 00723 } 00724 } 00725 00726 // This is logically local to the following function, but C++ says we have 00727 // to make it file scope. 00728 struct SubExprUseData { unsigned Count; bool notAllUsesAreFree; }; 00729 00730 /// RemoveCommonExpressionsFromUseBases - Look through all of the Bases of all 00731 /// the Uses, removing any common subexpressions, except that if all such 00732 /// subexpressions can be folded into an addressing mode for all uses inside 00733 /// the loop (this case is referred to as "free" in comments herein) we do 00734 /// not remove anything. This looks for things like (a+b+c) and 00735 /// (a+c+d) and computes the common (a+c) subexpression. The common expression 00736 /// is *removed* from the Bases and returned. 00737 static const SCEV * 00738 RemoveCommonExpressionsFromUseBases(std::vector<BasedUser> &Uses, 00739 ScalarEvolution *SE, Loop *L, 00740 const TargetLowering *TLI) { 00741 unsigned NumUses = Uses.size(); 00742 00743 // Only one use? This is a very common case, so we handle it specially and 00744 // cheaply. 00745 const SCEV *Zero = SE->getIntegerSCEV(0, Uses[0].Base->getType()); 00746 const SCEV *Result = Zero; 00747 const SCEV *FreeResult = Zero; 00748 if (NumUses == 1) { 00749 // If the use is inside the loop, use its base, regardless of what it is: 00750 // it is clearly shared across all the IV's. If the use is outside the loop 00751 // (which means after it) we don't want to factor anything *into* the loop, 00752 // so just use 0 as the base. 00753 if (L->contains(Uses[0].Inst->getParent())) 00754 std::swap(Result, Uses[0].Base); 00755 return Result; 00756 } 00757 00758 // To find common subexpressions, count how many of Uses use each expression. 00759 // If any subexpressions are used Uses.size() times, they are common. 00760 // Also track whether all uses of each expression can be moved into an 00761 // an addressing mode "for free"; such expressions are left within the loop. 00762 // struct SubExprUseData { unsigned Count; bool notAllUsesAreFree; }; 00763 std::map<const SCEV *, SubExprUseData> SubExpressionUseData; 00764 00765 // UniqueSubExprs - Keep track of all of the subexpressions we see in the 00766 // order we see them. 00767 SmallVector<const SCEV *, 16> UniqueSubExprs; 00768 00769 SmallVector<const SCEV *, 16> SubExprs; 00770 unsigned NumUsesInsideLoop = 0; 00771 for (unsigned i = 0; i != NumUses; ++i) { 00772 // If the user is outside the loop, just ignore it for base computation. 00773 // Since the user is outside the loop, it must be *after* the loop (if it 00774 // were before, it could not be based on the loop IV). We don't want users 00775 // after the loop to affect base computation of values *inside* the loop, 00776 // because we can always add their offsets to the result IV after the loop 00777 // is done, ensuring we get good code inside the loop. 00778 if (!L->contains(Uses[i].Inst->getParent())) 00779 continue; 00780 NumUsesInsideLoop++; 00781 00782 // If the base is zero (which is common), return zero now, there are no 00783 // CSEs we can find. 00784 if (Uses[i].Base == Zero) return Zero; 00785 00786 // If this use is as an address we may be able to put CSEs in the addressing 00787 // mode rather than hoisting them. 00788 bool isAddrUse = isAddressUse(Uses[i].Inst, Uses[i].OperandValToReplace); 00789 // We may need the AccessTy below, but only when isAddrUse, so compute it 00790 // only in that case. 00791 const Type *AccessTy = 0; 00792 if (isAddrUse) 00793 AccessTy = getAccessType(Uses[i].Inst); 00794 00795 // Split the expression into subexprs. 00796 SeparateSubExprs(SubExprs, Uses[i].Base, SE); 00797 // Add one to SubExpressionUseData.Count for each subexpr present, and 00798 // if the subexpr is not a valid immediate within an addressing mode use, 00799 // set SubExpressionUseData.notAllUsesAreFree. We definitely want to 00800 // hoist these out of the loop (if they are common to all uses). 00801 for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) { 00802 if (++SubExpressionUseData[SubExprs[j]].Count == 1) 00803 UniqueSubExprs.push_back(SubExprs[j]); 00804 if (!isAddrUse || !fitsInAddressMode(SubExprs[j], AccessTy, TLI, false)) 00805 SubExpressionUseData[SubExprs[j]].notAllUsesAreFree = true; 00806 } 00807 SubExprs.clear(); 00808 } 00809 00810 // Now that we know how many times each is used, build Result. Iterate over 00811 // UniqueSubexprs so that we have a stable ordering. 00812 for (unsigned i = 0, e = UniqueSubExprs.size(); i != e; ++i) { 00813 std::map<const SCEV *, SubExprUseData>::iterator I = 00814 SubExpressionUseData.find(UniqueSubExprs[i]); 00815 assert(I != SubExpressionUseData.end() && "Entry not found?"); 00816 if (I->second.Count == NumUsesInsideLoop) { // Found CSE! 00817 if (I->second.notAllUsesAreFree) 00818 Result = SE->getAddExpr(Result, I->first); 00819 else 00820 FreeResult = SE->getAddExpr(FreeResult, I->first); 00821 } else 00822 // Remove non-cse's from SubExpressionUseData. 00823 SubExpressionUseData.erase(I); 00824 } 00825 00826 if (FreeResult != Zero) { 00827 // We have some subexpressions that can be subsumed into addressing 00828 // modes in every use inside the loop. However, it's possible that 00829 // there are so many of them that the combined FreeResult cannot 00830 // be subsumed, or that the target cannot handle both a FreeResult 00831 // and a Result in the same instruction (for example because it would 00832 // require too many registers). Check this. 00833 for (unsigned i=0; i<NumUses; ++i) { 00834 if (!L->contains(Uses[i].Inst->getParent())) 00835 continue; 00836 // We know this is an addressing mode use; if there are any uses that 00837 // are not, FreeResult would be Zero. 00838 const Type *AccessTy = getAccessType(Uses[i].Inst); 00839 if (!fitsInAddressMode(FreeResult, AccessTy, TLI, Result!=Zero)) { 00840 // FIXME: could split up FreeResult into pieces here, some hoisted 00841 // and some not. There is no obvious advantage to this. 00842 Result = SE->getAddExpr(Result, FreeResult); 00843 FreeResult = Zero; 00844 break; 00845 } 00846 } 00847 } 00848 00849 // If we found no CSE's, return now. 00850 if (Result == Zero) return Result; 00851 00852 // If we still have a FreeResult, remove its subexpressions from 00853 // SubExpressionUseData. This means they will remain in the use Bases. 00854 if (FreeResult != Zero) { 00855 SeparateSubExprs(SubExprs, FreeResult, SE); 00856 for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) { 00857 std::map<const SCEV *, SubExprUseData>::iterator I = 00858 SubExpressionUseData.find(SubExprs[j]); 00859 SubExpressionUseData.erase(I); 00860 } 00861 SubExprs.clear(); 00862 } 00863 00864 // Otherwise, remove all of the CSE's we found from each of the base values. 00865 for (unsigned i = 0; i != NumUses; ++i) { 00866 // Uses outside the loop don't necessarily include the common base, but 00867 // the final IV value coming into those uses does. Instead of trying to 00868 // remove the pieces of the common base, which might not be there, 00869 // subtract off the base to compensate for this. 00870 if (!L->contains(Uses[i].Inst->getParent())) { 00871 Uses[i].Base = SE->getMinusSCEV(Uses[i].Base, Result); 00872 continue; 00873 } 00874 00875 // Split the expression into subexprs. 00876 SeparateSubExprs(SubExprs, Uses[i].Base, SE); 00877 00878 // Remove any common subexpressions. 00879 for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) 00880 if (SubExpressionUseData.count(SubExprs[j])) { 00881 SubExprs.erase(SubExprs.begin()+j); 00882 --j; --e; 00883 } 00884 00885 // Finally, add the non-shared expressions together. 00886 if (SubExprs.empty()) 00887 Uses[i].Base = Zero; 00888 else 00889 Uses[i].Base = SE->getAddExpr(SubExprs); 00890 SubExprs.clear(); 00891 } 00892 00893 return Result; 00894 } 00895 00896 /// ValidScale - Check whether the given Scale is valid for all loads and 00897 /// stores in UsersToProcess. 00898 /// 00899 bool LoopStrengthReduce::ValidScale(bool HasBaseReg, int64_t Scale, 00900 const std::vector<BasedUser>& UsersToProcess) { 00901 if (!TLI) 00902 return true; 00903 00904 for (unsigned i = 0, e = UsersToProcess.size(); i!=e; ++i) { 00905 // If this is a load or other access, pass the type of the access in. 00906 const Type *AccessTy = 00907 Type::getVoidTy(UsersToProcess[i].Inst->getContext()); 00908 if (isAddressUse(UsersToProcess[i].Inst, 00909 UsersToProcess[i].OperandValToReplace)) 00910 AccessTy = getAccessType(UsersToProcess[i].Inst); 00911 else if (isa<PHINode>(UsersToProcess[i].Inst)) 00912 continue; 00913 00914 TargetLowering::AddrMode AM; 00915 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm)) 00916 AM.BaseOffs = SC->getValue()->getSExtValue(); 00917 AM.HasBaseReg = HasBaseReg || !UsersToProcess[i].Base->isZero(); 00918 AM.Scale = Scale; 00919 00920 // If load[imm+r*scale] is illegal, bail out. 00921 if (!TLI->isLegalAddressingMode(AM, AccessTy)) 00922 return false; 00923 } 00924 return true; 00925 } 00926 00927 /// ValidOffset - Check whether the given Offset is valid for all loads and 00928 /// stores in UsersToProcess. 00929 /// 00930 bool LoopStrengthReduce::ValidOffset(bool HasBaseReg, 00931 int64_t Offset, 00932 int64_t Scale, 00933 const std::vector<BasedUser>& UsersToProcess) { 00934 if (!TLI) 00935 return true; 00936 00937 for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) { 00938 // If this is a load or other access, pass the type of the access in. 00939 const Type *AccessTy = 00940 Type::getVoidTy(UsersToProcess[i].Inst->getContext()); 00941 if (isAddressUse(UsersToProcess[i].Inst, 00942 UsersToProcess[i].OperandValToReplace)) 00943 AccessTy = getAccessType(UsersToProcess[i].Inst); 00944 else if (isa<PHINode>(UsersToProcess[i].Inst)) 00945 continue; 00946 00947 TargetLowering::AddrMode AM; 00948 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm)) 00949 AM.BaseOffs = SC->getValue()->getSExtValue(); 00950 AM.BaseOffs = (uint64_t)AM.BaseOffs + (uint64_t)Offset; 00951 AM.HasBaseReg = HasBaseReg || !UsersToProcess[i].Base->isZero(); 00952 AM.Scale = Scale; 00953 00954 // If load[imm+r*scale] is illegal, bail out. 00955 if (!TLI->isLegalAddressingMode(AM, AccessTy)) 00956 return false; 00957 } 00958 return true; 00959 } 00960 00961 /// RequiresTypeConversion - Returns true if converting Ty1 to Ty2 is not 00962 /// a nop. 00963 bool LoopStrengthReduce::RequiresTypeConversion(const Type *Ty1, 00964 const Type *Ty2) { 00965 if (Ty1 == Ty2) 00966 return false; 00967 Ty1 = SE->getEffectiveSCEVType(Ty1); 00968 Ty2 = SE->getEffectiveSCEVType(Ty2); 00969 if (Ty1 == Ty2) 00970 return false; 00971 if (Ty1->canLosslesslyBitCastTo(Ty2)) 00972 return false; 00973 if (TLI && TLI->isTruncateFree(Ty1, Ty2)) 00974 return false; 00975 return true; 00976 } 00977 00978 /// CheckForIVReuse - Returns the multiple if the stride is the multiple 00979 /// of a previous stride and it is a legal value for the target addressing 00980 /// mode scale component and optional base reg. This allows the users of 00981 /// this stride to be rewritten as prev iv * factor. It returns 0 if no 00982 /// reuse is possible. Factors can be negative on same targets, e.g. ARM. 00983 /// 00984 /// If all uses are outside the loop, we don't require that all multiplies 00985 /// be folded into the addressing mode, nor even that the factor be constant; 00986 /// a multiply (executed once) outside the loop is better than another IV 00987 /// within. Well, usually. 00988 const SCEV *LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg, 00989 bool AllUsesAreAddresses, 00990 bool AllUsesAreOutsideLoop, 00991 const SCEV *const &Stride, 00992 IVExpr &IV, const Type *Ty, 00993 const std::vector<BasedUser>& UsersToProcess) { 00994 if (StrideNoReuse.count(Stride)) 00995 return SE->getIntegerSCEV(0, Stride->getType()); 00996 00997 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) { 00998 int64_t SInt = SC->getValue()->getSExtValue(); 00999 for (unsigned NewStride = 0, e = IU->StrideOrder.size(); 01000 NewStride != e; ++NewStride) { 01001 std::map<const SCEV *, IVsOfOneStride>::iterator SI = 01002 IVsByStride.find(IU->StrideOrder[NewStride]); 01003 if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first) || 01004 StrideNoReuse.count(SI->first)) 01005 continue; 01006 int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 01007 if (SI->first != Stride && 01008 (unsigned(abs64(SInt)) < SSInt || (SInt % SSInt) != 0)) 01009 continue; 01010 int64_t Scale = SInt / SSInt; 01011 // Check that this stride is valid for all the types used for loads and 01012 // stores; if it can be used for some and not others, we might as well use 01013 // the original stride everywhere, since we have to create the IV for it 01014 // anyway. If the scale is 1, then we don't need to worry about folding 01015 // multiplications. 01016 if (Scale == 1 || 01017 (AllUsesAreAddresses && 01018 ValidScale(HasBaseReg, Scale, UsersToProcess))) { 01019 // Prefer to reuse an IV with a base of zero. 01020 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 01021 IE = SI->second.IVs.end(); II != IE; ++II) 01022 // Only reuse previous IV if it would not require a type conversion 01023 // and if the base difference can be folded. 01024 if (II->Base->isZero() && 01025 !RequiresTypeConversion(II->Base->getType(), Ty)) { 01026 IV = *II; 01027 return SE->getIntegerSCEV(Scale, Stride->getType()); 01028 } 01029 // Otherwise, settle for an IV with a foldable base. 01030 if (AllUsesAreAddresses) 01031 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 01032 IE = SI->second.IVs.end(); II != IE; ++II) 01033 // Only reuse previous IV if it would not require a type conversion 01034 // and if the base difference can be folded. 01035 if (SE->getEffectiveSCEVType(II->Base->getType()) == 01036 SE->getEffectiveSCEVType(Ty) && 01037 isa<SCEVConstant>(II->Base)) { 01038 int64_t Base = 01039 cast<SCEVConstant>(II->Base)->getValue()->getSExtValue(); 01040 if (Base > INT32_MIN && Base <= INT32_MAX && 01041 ValidOffset(HasBaseReg, -Base * Scale, 01042 Scale, UsersToProcess)) { 01043 IV = *II; 01044 return SE->getIntegerSCEV(Scale, Stride->getType()); 01045 } 01046 } 01047 } 01048 } 01049 } else if (AllUsesAreOutsideLoop) { 01050 // Accept nonconstant strides here; it is really really right to substitute 01051 // an existing IV if we can. 01052 for (unsigned NewStride = 0, e = IU->StrideOrder.size(); 01053 NewStride != e; ++NewStride) { 01054 std::map<const SCEV *, IVsOfOneStride>::iterator SI = 01055 IVsByStride.find(IU->StrideOrder[NewStride]); 01056 if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first)) 01057 continue; 01058 int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 01059 if (SI->first != Stride && SSInt != 1) 01060 continue; 01061 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 01062 IE = SI->second.IVs.end(); II != IE; ++II) 01063 // Accept nonzero base here. 01064 // Only reuse previous IV if it would not require a type conversion. 01065 if (!RequiresTypeConversion(II->Base->getType(), Ty)) { 01066 IV = *II; 01067 return Stride; 01068 } 01069 } 01070 // Special case, old IV is -1*x and this one is x. Can treat this one as 01071 // -1*old. 01072 for (unsigned NewStride = 0, e = IU->StrideOrder.size(); 01073 NewStride != e; ++NewStride) { 01074 std::map<const SCEV *, IVsOfOneStride>::iterator SI = 01075 IVsByStride.find(IU->StrideOrder[NewStride]); 01076 if (SI == IVsByStride.end()) 01077 continue; 01078 if (const SCEVMulExpr *ME = dyn_cast<SCEVMulExpr>(SI->first)) 01079 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(ME->getOperand(0))) 01080 if (Stride == ME->getOperand(1) && 01081 SC->getValue()->getSExtValue() == -1LL) 01082 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 01083 IE = SI->second.IVs.end(); II != IE; ++II) 01084 // Accept nonzero base here. 01085 // Only reuse previous IV if it would not require type conversion. 01086 if (!RequiresTypeConversion(II->Base->getType(), Ty)) { 01087 IV = *II; 01088 return SE->getIntegerSCEV(-1LL, Stride->getType()); 01089 } 01090 } 01091 } 01092 return SE->getIntegerSCEV(0, Stride->getType()); 01093 } 01094 01095 /// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that 01096 /// returns true if Val's isUseOfPostIncrementedValue is true. 01097 static bool PartitionByIsUseOfPostIncrementedValue(const BasedUser &Val) { 01098 return Val.isUseOfPostIncrementedValue; 01099 } 01100 01101 /// isNonConstantNegative - Return true if the specified scev is negated, but 01102 /// not a constant. 01103 static bool isNonConstantNegative(const SCEV *const &Expr) { 01104 const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Expr); 01105 if (!Mul) return false; 01106 01107 // If there is a constant factor, it will be first. 01108 const SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0)); 01109 if (!SC) return false; 01110 01111 // Return true if the value is negative, this matches things like (-42 * V). 01112 return SC->getValue()->getValue().isNegative(); 01113 } 01114 01115 /// CollectIVUsers - Transform our list of users and offsets to a bit more 01116 /// complex table. In this new vector, each 'BasedUser' contains 'Base', the base 01117 /// of the strided accesses, as well as the old information from Uses. We 01118 /// progressively move information from the Base field to the Imm field, until 01119 /// we eventually have the full access expression to rewrite the use. 01120 const SCEV *LoopStrengthReduce::CollectIVUsers(const SCEV *const &Stride, 01121 IVUsersOfOneStride &Uses, 01122 Loop *L, 01123 bool &AllUsesAreAddresses, 01124 bool &AllUsesAreOutsideLoop, 01125 std::vector<BasedUser> &UsersToProcess) { 01126 // FIXME: Generalize to non-affine IV's. 01127 if (!Stride->isLoopInvariant(L)) 01128 return SE->getIntegerSCEV(0, Stride->getType()); 01129 01130 UsersToProcess.reserve(Uses.Users.size()); 01131 for (ilist<IVStrideUse>::iterator I = Uses.Users.begin(), 01132 E = Uses.Users.end(); I != E; ++I) { 01133 UsersToProcess.push_back(BasedUser(*I, SE)); 01134 01135 // Move any loop variant operands from the offset field to the immediate 01136 // field of the use, so that we don't try to use something before it is 01137 // computed. 01138 MoveLoopVariantsToImmediateField(UsersToProcess.back().Base, 01139 UsersToProcess.back().Imm, L, SE); 01140 assert(UsersToProcess.back().Base->isLoopInvariant(L) && 01141 "Base value is not loop invariant!"); 01142 } 01143 01144 // We now have a whole bunch of uses of like-strided induction variables, but 01145 // they might all have different bases. We want to emit one PHI node for this 01146 // stride which we fold as many common expressions (between the IVs) into as 01147 // possible. Start by identifying the common expressions in the base values 01148 // for the strides (e.g. if we have "A+C+B" and "A+B+D" as our bases, find 01149 // "A+B"), emit it to the preheader, then remove the expression from the 01150 // UsersToProcess base values. 01151 const SCEV *CommonExprs = 01152 RemoveCommonExpressionsFromUseBases(UsersToProcess, SE, L, TLI); 01153 01154 // Next, figure out what we can represent in the immediate fields of 01155 // instructions. If we can represent anything there, move it to the imm 01156 // fields of the BasedUsers. We do this so that it increases the commonality 01157 // of the remaining uses. 01158 unsigned NumPHI = 0; 01159 bool HasAddress = false; 01160 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) { 01161 // If the user is not in the current loop, this means it is using the exit 01162 // value of the IV. Do not put anything in the base, make sure it's all in 01163 // the immediate field to allow as much factoring as possible. 01164 if (!L->contains(UsersToProcess[i].Inst->getParent())) { 01165 UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm, 01166 UsersToProcess[i].Base); 01167 UsersToProcess[i].Base = 01168 SE->getIntegerSCEV(0, UsersToProcess[i].Base->getType()); 01169 } else { 01170 // Not all uses are outside the loop. 01171 AllUsesAreOutsideLoop = false; 01172 01173 // Addressing modes can be folded into loads and stores. Be careful that 01174 // the store is through the expression, not of the expression though. 01175 bool isPHI = false; 01176 bool isAddress = isAddressUse(UsersToProcess[i].Inst, 01177 UsersToProcess[i].OperandValToReplace); 01178 if (isa<PHINode>(UsersToProcess[i].Inst)) { 01179 isPHI = true; 01180 ++NumPHI; 01181 } 01182 01183 if (isAddress) 01184 HasAddress = true; 01185 01186 // If this use isn't an address, then not all uses are addresses. 01187 if (!isAddress && !isPHI) 01188 AllUsesAreAddresses = false; 01189 01190 MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base, 01191 UsersToProcess[i].Imm, isAddress, L, SE); 01192 } 01193 } 01194 01195 // If one of the use is a PHI node and all other uses are addresses, still 01196 // allow iv reuse. Essentially we are trading one constant multiplication 01197 // for one fewer iv. 01198 if (NumPHI > 1) 01199 AllUsesAreAddresses = false; 01200 01201 // There are no in-loop address uses. 01202 if (AllUsesAreAddresses && (!HasAddress && !AllUsesAreOutsideLoop)) 01203 AllUsesAreAddresses = false; 01204 01205 return CommonExprs; 01206 } 01207 01208 /// ShouldUseFullStrengthReductionMode - Test whether full strength-reduction 01209 /// is valid and profitable for the given set of users of a stride. In 01210 /// full strength-reduction mode, all addresses at the current stride are 01211 /// strength-reduced all the way down to pointer arithmetic. 01212 /// 01213 bool LoopStrengthReduce::ShouldUseFullStrengthReductionMode( 01214 const std::vector<BasedUser> &UsersToProcess, 01215 const Loop *L, 01216 bool AllUsesAreAddresses, 01217 const SCEV *Stride) { 01218 if (!EnableFullLSRMode) 01219 return false; 01220 01221 // The heuristics below aim to avoid increasing register pressure, but 01222 // fully strength-reducing all the addresses increases the number of 01223 // add instructions, so don't do this when optimizing for size. 01224 // TODO: If the loop is large, the savings due to simpler addresses 01225 // may oughtweight the costs of the extra increment instructions. 01226 if (L->getHeader()->getParent()->hasFnAttr(Attribute::OptimizeForSize)) 01227 return false; 01228 01229 // TODO: For now, don't do full strength reduction if there could 01230 // potentially be greater-stride multiples of the current stride 01231 // which could reuse the current stride IV. 01232 if (IU->StrideOrder.back() != Stride) 01233 return false; 01234 01235 // Iterate through the uses to find conditions that automatically rule out 01236 // full-lsr mode. 01237 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ) { 01238 const SCEV *Base = UsersToProcess[i].Base; 01239 const SCEV *Imm = UsersToProcess[i].Imm; 01240 // If any users have a loop-variant component, they can't be fully 01241 // strength-reduced. 01242 if (Imm && !Imm->isLoopInvariant(L)) 01243 return false; 01244 // If there are to users with the same base and the difference between 01245 // the two Imm values can't be folded into the address, full 01246 // strength reduction would increase register pressure. 01247 do { 01248 const SCEV *CurImm = UsersToProcess[i].Imm; 01249 if ((CurImm || Imm) && CurImm != Imm) { 01250 if (!CurImm) CurImm = SE->getIntegerSCEV(0, Stride->getType()); 01251 if (!Imm) Imm = SE->getIntegerSCEV(0, Stride->getType()); 01252 const Instruction *Inst = UsersToProcess[i].Inst; 01253 const Type *AccessTy = getAccessType(Inst); 01254 const SCEV *Diff = SE->getMinusSCEV(UsersToProcess[i].Imm, Imm); 01255 if (!Diff->isZero() && 01256 (!AllUsesAreAddresses || 01257 !fitsInAddressMode(Diff, AccessTy, TLI, /*HasBaseReg=*/true))) 01258 return false; 01259 } 01260 } while (++i != e && Base == UsersToProcess[i].Base); 01261 } 01262 01263 // If there's exactly one user in this stride, fully strength-reducing it 01264 // won't increase register pressure. If it's starting from a non-zero base, 01265 // it'll be simpler this way. 01266 if (UsersToProcess.size() == 1 && !UsersToProcess[0].Base->isZero()) 01267 return true; 01268 01269 // Otherwise, if there are any users in this stride that don't require 01270 // a register for their base, full strength-reduction will increase 01271 // register pressure. 01272 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 01273 if (UsersToProcess[i].Base->isZero()) 01274 return false; 01275 01276 // Otherwise, go for it. 01277 return true; 01278 } 01279 01280 /// InsertAffinePhi Create and insert a PHI node for an induction variable 01281 /// with the specified start and step values in the specified loop. 01282 /// 01283 /// If NegateStride is true, the stride should be negated by using a 01284 /// subtract instead of an add. 01285 /// 01286 /// Return the created phi node. 01287 /// 01288 static PHINode *InsertAffinePhi(const SCEV *Start, const SCEV *Step, 01289 Instruction *IVIncInsertPt, 01290 const Loop *L, 01291 SCEVExpander &Rewriter) { 01292 assert(Start->isLoopInvariant(L) && "New PHI start is not loop invariant!"); 01293 assert(Step->isLoopInvariant(L) && "New PHI stride is not loop invariant!"); 01294 01295 BasicBlock *Header = L->getHeader(); 01296 BasicBlock *Preheader = L->getLoopPreheader(); 01297 BasicBlock *LatchBlock = L->getLoopLatch(); 01298 const Type *Ty = Start->getType(); 01299 Ty = Rewriter.SE.getEffectiveSCEVType(Ty); 01300 01301 PHINode *PN = PHINode::Create(Ty, "lsr.iv", Header->begin()); 01302 PN->addIncoming(Rewriter.expandCodeFor(Start, Ty, Preheader->getTerminator()), 01303 Preheader); 01304 01305 // If the stride is negative, insert a sub instead of an add for the 01306 // increment. 01307 bool isNegative = isNonConstantNegative(Step); 01308 const SCEV *IncAmount = Step; 01309 if (isNegative) 01310 IncAmount = Rewriter.SE.getNegativeSCEV(Step); 01311 01312 // Insert an add instruction right before the terminator corresponding 01313 // to the back-edge or just before the only use. The location is determined 01314 // by the caller and passed in as IVIncInsertPt. 01315 Value *StepV = Rewriter.expandCodeFor(IncAmount, Ty, 01316 Preheader->getTerminator()); 01317 Instruction *IncV; 01318 if (isNegative) { 01319 IncV = BinaryOperator::CreateSub(PN, StepV, "lsr.iv.next", 01320 IVIncInsertPt); 01321 } else { 01322 IncV = BinaryOperator::CreateAdd(PN, StepV, "lsr.iv.next", 01323 IVIncInsertPt); 01324 } 01325 if (!isa<ConstantInt>(StepV)) ++NumVariable; 01326 01327 PN->addIncoming(IncV, LatchBlock); 01328 01329 ++NumInserted; 01330 return PN; 01331 } 01332 01333 static void SortUsersToProcess(std::vector<BasedUser> &UsersToProcess) { 01334 // We want to emit code for users inside the loop first. To do this, we 01335 // rearrange BasedUser so that the entries at the end have 01336 // isUseOfPostIncrementedValue = false, because we pop off the end of the 01337 // vector (so we handle them first). 01338 std::partition(UsersToProcess.begin(), UsersToProcess.end(), 01339 PartitionByIsUseOfPostIncrementedValue); 01340 01341 // Sort this by base, so that things with the same base are handled 01342 // together. By partitioning first and stable-sorting later, we are 01343 // guaranteed that within each base we will pop off users from within the 01344 // loop before users outside of the loop with a particular base. 01345 // 01346 // We would like to use stable_sort here, but we can't. The problem is that 01347 // const SCEV *'s don't have a deterministic ordering w.r.t to each other, so 01348 // we don't have anything to do a '<' comparison on. Because we think the 01349 // number of uses is small, do a horrible bubble sort which just relies on 01350 // ==. 01351 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) { 01352 // Get a base value. 01353 const SCEV *Base = UsersToProcess[i].Base; 01354 01355 // Compact everything with this base to be consecutive with this one. 01356 for (unsigned j = i+1; j != e; ++j) { 01357 if (UsersToProcess[j].Base == Base) { 01358 std::swap(UsersToProcess[i+1], UsersToProcess[j]); 01359 ++i; 01360 } 01361 } 01362 } 01363 } 01364 01365 /// PrepareToStrengthReduceFully - Prepare to fully strength-reduce 01366 /// UsersToProcess, meaning lowering addresses all the way down to direct 01367 /// pointer arithmetic. 01368 /// 01369 void 01370 LoopStrengthReduce::PrepareToStrengthReduceFully( 01371 std::vector<BasedUser> &UsersToProcess, 01372 const SCEV *Stride, 01373 const SCEV *CommonExprs, 01374 const Loop *L, 01375 SCEVExpander &PreheaderRewriter) { 01376 DOUT << " Fully reducing all users\n"; 01377 01378 // Rewrite the UsersToProcess records, creating a separate PHI for each 01379 // unique Base value. 01380 Instruction *IVIncInsertPt = L->getLoopLatch()->getTerminator(); 01381 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ) { 01382 // TODO: The uses are grouped by base, but not sorted. We arbitrarily 01383 // pick the first Imm value here to start with, and adjust it for the 01384 // other uses. 01385 const SCEV *Imm = UsersToProcess[i].Imm; 01386 const SCEV *Base = UsersToProcess[i].Base; 01387 const SCEV *Start = SE->getAddExpr(CommonExprs, Base, Imm); 01388 PHINode *Phi = InsertAffinePhi(Start, Stride, IVIncInsertPt, L, 01389 PreheaderRewriter); 01390 // Loop over all the users with the same base. 01391 do { 01392 UsersToProcess[i].Base = SE->getIntegerSCEV(0, Stride->getType()); 01393 UsersToProcess[i].Imm = SE->getMinusSCEV(UsersToProcess[i].Imm, Imm); 01394 UsersToProcess[i].Phi = Phi; 01395 assert(UsersToProcess[i].Imm->isLoopInvariant(L) && 01396 "ShouldUseFullStrengthReductionMode should reject this!"); 01397 } while (++i != e && Base == UsersToProcess[i].Base); 01398 } 01399 } 01400 01401 /// FindIVIncInsertPt - Return the location to insert the increment instruction. 01402 /// If the only use if a use of postinc value, (must be the loop termination 01403 /// condition), then insert it just before the use. 01404 static Instruction *FindIVIncInsertPt(std::vector<BasedUser> &UsersToProcess, 01405 const Loop *L) { 01406 if (UsersToProcess.size() == 1 && 01407 UsersToProcess[0].isUseOfPostIncrementedValue && 01408 L->contains(UsersToProcess[0].Inst->getParent())) 01409 return UsersToProcess[0].Inst; 01410 return L->getLoopLatch()->getTerminator(); 01411 } 01412 01413 /// PrepareToStrengthReduceWithNewPhi - Insert a new induction variable for the 01414 /// given users to share. 01415 /// 01416 void 01417 LoopStrengthReduce::PrepareToStrengthReduceWithNewPhi( 01418 std::vector<BasedUser> &UsersToProcess, 01419 const SCEV *Stride, 01420 const SCEV *CommonExprs, 01421 Value *CommonBaseV, 01422 Instruction *IVIncInsertPt, 01423 const Loop *L, 01424 SCEVExpander &PreheaderRewriter) { 01425 DOUT << " Inserting new PHI:\n"; 01426 01427 PHINode *Phi = InsertAffinePhi(SE->getUnknown(CommonBaseV), 01428 Stride, IVIncInsertPt, L, 01429 PreheaderRewriter); 01430 01431 // Remember this in case a later stride is multiple of this. 01432 IVsByStride[Stride].addIV(Stride, CommonExprs, Phi); 01433 01434 // All the users will share this new IV. 01435 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 01436 UsersToProcess[i].Phi = Phi; 01437 01438 DOUT << " IV="; 01439 DEBUG(WriteAsOperand(*DOUT, Phi, /*PrintType=*/false)); 01440 DOUT << "\n"; 01441 } 01442 01443 /// PrepareToStrengthReduceFromSmallerStride - Prepare for the given users to 01444 /// reuse an induction variable with a stride that is a factor of the current 01445 /// induction variable. 01446 /// 01447 void 01448 LoopStrengthReduce::PrepareToStrengthReduceFromSmallerStride( 01449 std::vector<BasedUser> &UsersToProcess, 01450 Value *CommonBaseV, 01451 const IVExpr &ReuseIV, 01452 Instruction *PreInsertPt) { 01453 DOUT << " Rewriting in terms of existing IV of STRIDE " << *ReuseIV.Stride 01454 << " and BASE " << *ReuseIV.Base << "\n"; 01455 01456 // All the users will share the reused IV. 01457 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 01458 UsersToProcess[i].Phi = ReuseIV.PHI; 01459 01460 Constant *C = dyn_cast<Constant>(CommonBaseV); 01461 if (C && 01462 (!C->isNullValue() && 01463 !fitsInAddressMode(SE->getUnknown(CommonBaseV), CommonBaseV->getType(), 01464 TLI, false))) 01465 // We want the common base emitted into the preheader! This is just 01466 // using cast as a copy so BitCast (no-op cast) is appropriate 01467 CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV->getType(), 01468 "commonbase", PreInsertPt); 01469 } 01470 01471 static bool IsImmFoldedIntoAddrMode(GlobalValue *GV, int64_t Offset, 01472 const Type *AccessTy, 01473 std::vector<BasedUser> &UsersToProcess, 01474 const TargetLowering *TLI) { 01475 SmallVector<Instruction*, 16> AddrModeInsts; 01476 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) { 01477 if (UsersToProcess[i].isUseOfPostIncrementedValue) 01478 continue; 01479 ExtAddrMode AddrMode = 01480 AddressingModeMatcher::Match(UsersToProcess[i].OperandValToReplace, 01481 AccessTy, UsersToProcess[i].Inst, 01482 AddrModeInsts, *TLI); 01483 if (GV && GV != AddrMode.BaseGV) 01484 return false; 01485 if (Offset && !AddrMode.BaseOffs) 01486 // FIXME: How to accurate check it's immediate offset is folded. 01487 return false; 01488 AddrModeInsts.clear(); 01489 } 01490 return true; 01491 } 01492 01493 /// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single 01494 /// stride of IV. All of the users may have different starting values, and this 01495 /// may not be the only stride. 01496 void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEV *const &Stride, 01497 IVUsersOfOneStride &Uses, 01498 Loop *L) { 01499 // If all the users are moved to another stride, then there is nothing to do. 01500 if (Uses.Users.empty()) 01501 return; 01502 01503 // Keep track if every use in UsersToProcess is an address. If they all are, 01504 // we may be able to rewrite the entire collection of them in terms of a 01505 // smaller-stride IV. 01506 bool AllUsesAreAddresses = true; 01507 01508 // Keep track if every use of a single stride is outside the loop. If so, 01509 // we want to be more aggressive about reusing a smaller-stride IV; a 01510 // multiply outside the loop is better than another IV inside. Well, usually. 01511 bool AllUsesAreOutsideLoop = true; 01512 01513 // Transform our list of users and offsets to a bit more complex table. In 01514 // this new vector, each 'BasedUser' contains 'Base' the base of the 01515 // strided accessas well as the old information from Uses. We progressively 01516 // move information from the Base field to the Imm field, until we eventually 01517 // have the full access expression to rewrite the use. 01518 std::vector<BasedUser> UsersToProcess; 01519 const SCEV *CommonExprs = CollectIVUsers(Stride, Uses, L, AllUsesAreAddresses, 01520 AllUsesAreOutsideLoop, 01521 UsersToProcess); 01522 01523 // Sort the UsersToProcess array so that users with common bases are 01524 // next to each other. 01525 SortUsersToProcess(UsersToProcess); 01526 01527 // If we managed to find some expressions in common, we'll need to carry 01528 // their value in a register and add it in for each use. This will take up 01529 // a register operand, which potentially restricts what stride values are 01530 // valid. 01531 bool HaveCommonExprs = !CommonExprs->isZero(); 01532 const Type *ReplacedTy = CommonExprs->getType(); 01533 01534 // If all uses are addresses, consider sinking the immediate part of the 01535 // common expression back into uses if they can fit in the immediate fields. 01536 if (TLI && HaveCommonExprs && AllUsesAreAddresses) { 01537 const SCEV *NewCommon = CommonExprs; 01538 const SCEV *Imm = SE->getIntegerSCEV(0, ReplacedTy); 01539 MoveImmediateValues(TLI, Type::getVoidTy( 01540 L->getLoopPreheader()->getContext()), 01541 NewCommon, Imm, true, L, SE); 01542 if (!Imm->isZero()) { 01543 bool DoSink = true; 01544 01545 // If the immediate part of the common expression is a GV, check if it's 01546 // possible to fold it into the target addressing mode. 01547 GlobalValue *GV = 0; 01548 if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(Imm)) 01549 GV = dyn_cast<GlobalValue>(SU->getValue()); 01550 int64_t Offset = 0; 01551 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Imm)) 01552 Offset = SC->getValue()->getSExtValue(); 01553 if (GV || Offset) 01554 // Pass VoidTy as the AccessTy to be conservative, because 01555 // there could be multiple access types among all the uses. 01556 DoSink = IsImmFoldedIntoAddrMode(GV, Offset, 01557 Type::getVoidTy(L->getLoopPreheader()->getContext()), 01558 UsersToProcess, TLI); 01559 01560 if (DoSink) { 01561 DOUT << " Sinking " << *Imm << " back down into uses\n"; 01562 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 01563 UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm, Imm); 01564 CommonExprs = NewCommon; 01565 HaveCommonExprs = !CommonExprs->isZero(); 01566 ++NumImmSunk; 01567 } 01568 } 01569 } 01570 01571 // Now that we know what we need to do, insert the PHI node itself. 01572 // 01573 DOUT << "LSR: Examining IVs of TYPE " << *ReplacedTy << " of STRIDE " 01574 << *Stride << ":\n" 01575 << " Common base: " << *CommonExprs << "\n"; 01576 01577 SCEVExpander Rewriter(*SE); 01578 SCEVExpander PreheaderRewriter(*SE); 01579 01580 BasicBlock *Preheader = L->getLoopPreheader(); 01581 Instruction *PreInsertPt = Preheader->getTerminator(); 01582 BasicBlock *LatchBlock = L->getLoopLatch(); 01583 Instruction *IVIncInsertPt = LatchBlock->getTerminator(); 01584 01585 Value *CommonBaseV = Constant::getNullValue(ReplacedTy); 01586 01587 const SCEV *RewriteFactor = SE->getIntegerSCEV(0, ReplacedTy); 01588 IVExpr ReuseIV(SE->getIntegerSCEV(0, 01589 Type::getInt32Ty(Preheader->getContext())), 01590 SE->getIntegerSCEV(0, 01591 Type::getInt32Ty(Preheader->getContext())), 01592 0); 01593 01594 /// Choose a strength-reduction strategy and prepare for it by creating 01595 /// the necessary PHIs and adjusting the bookkeeping. 01596 if (ShouldUseFullStrengthReductionMode(UsersToProcess, L, 01597 AllUsesAreAddresses, Stride)) { 01598 PrepareToStrengthReduceFully(UsersToProcess, Stride, CommonExprs, L, 01599 PreheaderRewriter); 01600 } else { 01601 // Emit the initial base value into the loop preheader. 01602 CommonBaseV = PreheaderRewriter.expandCodeFor(CommonExprs, ReplacedTy, 01603 PreInsertPt); 01604 01605 // If all uses are addresses, check if it is possible to reuse an IV. The 01606 // new IV must have a stride that is a multiple of the old stride; the 01607 // multiple must be a number that can be encoded in the scale field of the 01608 // target addressing mode; and we must have a valid instruction after this 01609 // substitution, including the immediate field, if any. 01610 RewriteFactor = CheckForIVReuse(HaveCommonExprs, AllUsesAreAddresses, 01611 AllUsesAreOutsideLoop, 01612 Stride, ReuseIV, ReplacedTy, 01613 UsersToProcess); 01614 if (!RewriteFactor->isZero()) 01615 PrepareToStrengthReduceFromSmallerStride(UsersToProcess, CommonBaseV, 01616 ReuseIV, PreInsertPt); 01617 else { 01618 IVIncInsertPt = FindIVIncInsertPt(UsersToProcess, L); 01619 PrepareToStrengthReduceWithNewPhi(UsersToProcess, Stride, CommonExprs, 01620 CommonBaseV, IVIncInsertPt, 01621 L, PreheaderRewriter); 01622 } 01623 } 01624 01625 // Process all the users now, replacing their strided uses with 01626 // strength-reduced forms. This outer loop handles all bases, the inner 01627 // loop handles all users of a particular base. 01628 while (!UsersToProcess.empty()) { 01629 const SCEV *Base = UsersToProcess.back().Base; 01630 Instruction *Inst = UsersToProcess.back().Inst; 01631 01632 // Emit the code for Base into the preheader. 01633 Value *BaseV = 0; 01634 if (!Base->isZero()) { 01635 BaseV = PreheaderRewriter.expandCodeFor(Base, 0, PreInsertPt); 01636 01637 DOUT << " INSERTING code for BASE = " << *Base << ":"; 01638 if (BaseV->hasName()) 01639 DOUT << " Result value name = %" << BaseV->getNameStr(); 01640 DOUT << "\n"; 01641 01642 // If BaseV is a non-zero constant, make sure that it gets inserted into 01643 // the preheader, instead of being forward substituted into the uses. We 01644 // do this by forcing a BitCast (noop cast) to be inserted into the 01645 // preheader in this case. 01646 if (!fitsInAddressMode(Base, getAccessType(Inst), TLI, false) && 01647 isa<Constant>(BaseV)) { 01648 // We want this constant emitted into the preheader! This is just 01649 // using cast as a copy so BitCast (no-op cast) is appropriate 01650 BaseV = new BitCastInst(BaseV, BaseV->getType(), "preheaderinsert", 01651 PreInsertPt); 01652 } 01653 } 01654 01655 // Emit the code to add the immediate offset to the Phi value, just before 01656 // the instructions that we identified as using this stride and base. 01657 do { 01658 // FIXME: Use emitted users to emit other users. 01659 BasedUser &User = UsersToProcess.back(); 01660 01661 DOUT << " Examining "; 01662 if (User.isUseOfPostIncrementedValue) 01663 DOUT << "postinc"; 01664 else 01665 DOUT << "preinc"; 01666 DOUT << " use "; 01667 DEBUG(WriteAsOperand(*DOUT, UsersToProcess.back().OperandValToReplace, 01668 /*PrintType=*/false)); 01669 DOUT << " in Inst: " << *(User.Inst); 01670 01671 // If this instruction wants to use the post-incremented value, move it 01672 // after the post-inc and use its value instead of the PHI. 01673 Value *RewriteOp = User.Phi; 01674 if (User.isUseOfPostIncrementedValue) { 01675 RewriteOp = User.Phi->getIncomingValueForBlock(LatchBlock); 01676 // If this user is in the loop, make sure it is the last thing in the 01677 // loop to ensure it is dominated by the increment. In case it's the 01678 // only use of the iv, the increment instruction is already before the 01679 // use. 01680 if (L->contains(User.Inst->getParent()) && User.Inst != IVIncInsertPt) 01681 User.Inst->moveBefore(IVIncInsertPt); 01682 } 01683 01684 const SCEV *RewriteExpr = SE->getUnknown(RewriteOp); 01685 01686 if (SE->getEffectiveSCEVType(RewriteOp->getType()) != 01687 SE->getEffectiveSCEVType(ReplacedTy)) { 01688 assert(SE->getTypeSizeInBits(RewriteOp->getType()) > 01689 SE->getTypeSizeInBits(ReplacedTy) && 01690 "Unexpected widening cast!"); 01691 RewriteExpr = SE->getTruncateExpr(RewriteExpr, ReplacedTy); 01692 } 01693 01694 // If we had to insert new instructions for RewriteOp, we have to 01695 // consider that they may not have been able to end up immediately 01696 // next to RewriteOp, because non-PHI instructions may never precede 01697 // PHI instructions in a block. In this case, remember where the last 01698 // instruction was inserted so that if we're replacing a different 01699 // PHI node, we can use the later point to expand the final 01700 // RewriteExpr. 01701 Instruction *NewBasePt = dyn_cast<Instruction>(RewriteOp); 01702 if (RewriteOp == User.Phi) NewBasePt = 0; 01703 01704 // Clear the SCEVExpander's expression map so that we are guaranteed 01705 // to have the code emitted where we expect it. 01706 Rewriter.clear(); 01707 01708 // If we are reusing the iv, then it must be multiplied by a constant 01709 // factor to take advantage of the addressing mode scale component. 01710 if (!RewriteFactor->isZero()) { 01711 // If we're reusing an IV with a nonzero base (currently this happens 01712 // only when all reuses are outside the loop) subtract that base here. 01713 // The base has been used to initialize the PHI node but we don't want 01714 // it here. 01715 if (!ReuseIV.Base->isZero()) { 01716 const SCEV *typedBase = ReuseIV.Base; 01717 if (SE->getEffectiveSCEVType(RewriteExpr->getType()) != 01718 SE->getEffectiveSCEVType(ReuseIV.Base->getType())) { 01719 // It's possible the original IV is a larger type than the new IV, 01720 // in which case we have to truncate the Base. We checked in 01721 // RequiresTypeConversion that this is valid. 01722 assert(SE->getTypeSizeInBits(RewriteExpr->getType()) < 01723 SE->getTypeSizeInBits(ReuseIV.Base->getType()) && 01724 "Unexpected lengthening conversion!"); 01725 typedBase = SE->getTruncateExpr(ReuseIV.Base, 01726 RewriteExpr->getType()); 01727 } 01728 RewriteExpr = SE->getMinusSCEV(RewriteExpr, typedBase); 01729 } 01730 01731 // Multiply old variable, with base removed, by new scale factor. 01732 RewriteExpr = SE->getMulExpr(RewriteFactor, 01733 RewriteExpr); 01734 01735 // The common base is emitted in the loop preheader. But since we 01736 // are reusing an IV, it has not been used to initialize the PHI node. 01737 // Add it to the expression used to rewrite the uses. 01738 // When this use is outside the loop, we earlier subtracted the 01739 // common base, and are adding it back here. Use the same expression 01740 // as before, rather than CommonBaseV, so DAGCombiner will zap it. 01741 if (!CommonExprs->isZero()) { 01742 if (L->contains(User.Inst->getParent())) 01743 RewriteExpr = SE->getAddExpr(RewriteExpr, 01744 SE->getUnknown(CommonBaseV)); 01745 else 01746 RewriteExpr = SE->getAddExpr(RewriteExpr, CommonExprs); 01747 } 01748 } 01749 01750 // Now that we know what we need to do, insert code before User for the 01751 // immediate and any loop-variant expressions. 01752 if (BaseV) 01753 // Add BaseV to the PHI value if needed. 01754 RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV)); 01755 01756 User.RewriteInstructionToUseNewBase(RewriteExpr, NewBasePt, 01757 Rewriter, L, this, *LI, 01758 DeadInsts); 01759 01760 // Mark old value we replaced as possibly dead, so that it is eliminated 01761 // if we just replaced the last use of that value. 01762 DeadInsts.push_back(User.OperandValToReplace); 01763 01764 UsersToProcess.pop_back(); 01765 ++NumReduced; 01766 01767 // If there are any more users to process with the same base, process them 01768 // now. We sorted by base above, so we just have to check the last elt. 01769 } while (!UsersToProcess.empty() && UsersToProcess.back().Base == Base); 01770 // TODO: Next, find out which base index is the most common, pull it out. 01771 } 01772 01773 // IMPORTANT TODO: Figure out how to partition the IV's with this stride, but 01774 // different starting values, into different PHIs. 01775 } 01776 01777 /// FindIVUserForCond - If Cond has an operand that is an expression of an IV, 01778 /// set the IV user and stride information and return true, otherwise return 01779 /// false. 01780 bool LoopStrengthReduce::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse, 01781 const SCEV *const * &CondStride) { 01782 for (unsigned Stride = 0, e = IU->StrideOrder.size(); 01783 Stride != e && !CondUse; ++Stride) { 01784 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 01785 IU->IVUsesByStride.find(IU->StrideOrder[Stride]); 01786 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 01787 01788 for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(), 01789 E = SI->second->Users.end(); UI != E; ++UI) 01790 if (UI->getUser() == Cond) { 01791 // NOTE: we could handle setcc instructions with multiple uses here, but 01792 // InstCombine does it as well for simple uses, it's not clear that it 01793 // occurs enough in real life to handle. 01794 CondUse = UI; 01795 CondStride = &SI->first; 01796 return true; 01797 } 01798 } 01799 return false; 01800 } 01801 01802 namespace { 01803 // Constant strides come first which in turns are sorted by their absolute 01804 // values. If absolute values are the same, then positive strides comes first. 01805 // e.g. 01806 // 4, -1, X, 1, 2 ==> 1, -1, 2, 4, X 01807 struct StrideCompare { 01808 const ScalarEvolution *SE; 01809 explicit StrideCompare(const ScalarEvolution *se) : SE(se) {} 01810 01811 bool operator()(const SCEV *const &LHS, const SCEV *const &RHS) { 01812 const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS); 01813 const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS); 01814 if (LHSC && RHSC) { 01815 int64_t LV = LHSC->getValue()->getSExtValue(); 01816 int64_t RV = RHSC->getValue()->getSExtValue(); 01817 uint64_t ALV = (LV < 0) ? -LV : LV; 01818 uint64_t ARV = (RV < 0) ? -RV : RV; 01819 if (ALV == ARV) { 01820 if (LV != RV) 01821 return LV > RV; 01822 } else { 01823 return ALV < ARV; 01824 } 01825 01826 // If it's the same value but different type, sort by bit width so 01827 // that we emit larger induction variables before smaller 01828 // ones, letting the smaller be re-written in terms of larger ones. 01829 return SE->getTypeSizeInBits(RHS->getType()) < 01830 SE->getTypeSizeInBits(LHS->getType()); 01831 } 01832 return LHSC && !RHSC; 01833 } 01834 }; 01835 } 01836 01837 /// ChangeCompareStride - If a loop termination compare instruction is the 01838 /// only use of its stride, and the compaison is against a constant value, 01839 /// try eliminate the stride by moving the compare instruction to another 01840 /// stride and change its constant operand accordingly. e.g. 01841 /// 01842 /// loop: 01843 /// ... 01844 /// v1 = v1 + 3 01845 /// v2 = v2 + 1 01846 /// if (v2 < 10) goto loop 01847 /// => 01848 /// loop: 01849 /// ... 01850 /// v1 = v1 + 3 01851 /// if (v1 < 30) goto loop 01852 ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond, 01853 IVStrideUse* &CondUse, 01854 const SCEV *const* &CondStride) { 01855 // If there's only one stride in the loop, there's nothing to do here. 01856 if (IU->StrideOrder.size() < 2) 01857 return Cond; 01858 // If there are other users of the condition's stride, don't bother 01859 // trying to change the condition because the stride will still 01860 // remain. 01861 std::map<const SCEV *, IVUsersOfOneStride *>::iterator I = 01862 IU->IVUsesByStride.find(*CondStride); 01863 if (I == IU->IVUsesByStride.end() || 01864 I->second->Users.size() != 1) 01865 return Cond; 01866 // Only handle constant strides for now. 01867 const SCEVConstant *SC = dyn_cast<SCEVConstant>(*CondStride); 01868 if (!SC) return Cond; 01869 01870 ICmpInst::Predicate Predicate = Cond->getPredicate(); 01871 int64_t CmpSSInt = SC->getValue()->getSExtValue(); 01872 unsigned BitWidth = SE->getTypeSizeInBits((*CondStride)->getType()); 01873 uint64_t SignBit = 1ULL << (BitWidth-1); 01874 const Type *CmpTy = Cond->getOperand(0)->getType(); 01875 const Type *NewCmpTy = NULL; 01876 unsigned TyBits = SE->getTypeSizeInBits(CmpTy); 01877 unsigned NewTyBits = 0; 01878 const SCEV **NewStride = NULL; 01879 Value *NewCmpLHS = NULL; 01880 Value *NewCmpRHS = NULL; 01881 int64_t Scale = 1; 01882 const SCEV *NewOffset = SE->getIntegerSCEV(0, CmpTy); 01883 01884 if (ConstantInt *C = dyn_cast<ConstantInt>(Cond->getOperand(1))) { 01885 int64_t CmpVal = C->getValue().getSExtValue(); 01886 01887 // Check stride constant and the comparision constant signs to detect 01888 // overflow. 01889 if ((CmpVal & SignBit) != (CmpSSInt & SignBit)) 01890 return Cond; 01891 01892 // Look for a suitable stride / iv as replacement. 01893 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 01894 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 01895 IU->IVUsesByStride.find(IU->StrideOrder[i]); 01896 if (!isa<SCEVConstant>(SI->first)) 01897 continue; 01898 int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 01899 if (SSInt == CmpSSInt || 01900 abs64(SSInt) < abs64(CmpSSInt) || 01901 (SSInt % CmpSSInt) != 0) 01902 continue; 01903 01904 Scale = SSInt / CmpSSInt; 01905 int64_t NewCmpVal = CmpVal * Scale; 01906 APInt Mul = APInt(BitWidth*2, CmpVal, true); 01907 Mul = Mul * APInt(BitWidth*2, Scale, true); 01908 // Check for overflow. 01909 if (!Mul.isSignedIntN(BitWidth)) 01910 continue; 01911 // Check for overflow in the stride's type too. 01912 if (!Mul.isSignedIntN(SE->getTypeSizeInBits(SI->first->getType()))) 01913 continue; 01914 01915 // Watch out for overflow. 01916 if (ICmpInst::isSignedPredicate(Predicate) && 01917 (CmpVal & SignBit) != (NewCmpVal & SignBit)) 01918 continue; 01919 01920 if (NewCmpVal == CmpVal) 01921 continue; 01922 // Pick the best iv to use trying to avoid a cast. 01923 NewCmpLHS = NULL; 01924 for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(), 01925 E = SI->second->Users.end(); UI != E; ++UI) { 01926 Value *Op = UI->getOperandValToReplace(); 01927 01928 // If the IVStrideUse implies a cast, check for an actual cast which 01929 // can be used to find the original IV expression. 01930 if (SE->getEffectiveSCEVType(Op->getType()) != 01931 SE->getEffectiveSCEVType(SI->first->getType())) { 01932 CastInst *CI = dyn_cast<CastInst>(Op); 01933 // If it's not a simple cast, it's complicated. 01934 if (!CI) 01935 continue; 01936 // If it's a cast from a type other than the stride type, 01937 // it's complicated. 01938 if (CI->getOperand(0)->getType() != SI->first->getType()) 01939 continue; 01940 // Ok, we found the IV expression in the stride's type. 01941 Op = CI->getOperand(0); 01942 } 01943 01944 NewCmpLHS = Op; 01945 if (NewCmpLHS->getType() == CmpTy) 01946 break; 01947 } 01948 if (!NewCmpLHS) 01949 continue; 01950 01951 NewCmpTy = NewCmpLHS->getType(); 01952 NewTyBits = SE->getTypeSizeInBits(NewCmpTy); 01953 const Type *NewCmpIntTy = IntegerType::get(Cond->getContext(), NewTyBits); 01954 if (RequiresTypeConversion(NewCmpTy, CmpTy)) { 01955 // Check if it is possible to rewrite it using 01956 // an iv / stride of a smaller integer type. 01957 unsigned Bits = NewTyBits; 01958 if (ICmpInst::isSignedPredicate(Predicate)) 01959 --Bits; 01960 uint64_t Mask = (1ULL << Bits) - 1; 01961 if (((uint64_t)NewCmpVal & Mask) != (uint64_t)NewCmpVal) 01962 continue; 01963 } 01964 01965 // Don't rewrite if use offset is non-constant and the new type is 01966 // of a different type. 01967 // FIXME: too conservative? 01968 if (NewTyBits != TyBits && !isa<SCEVConstant>(CondUse->getOffset())) 01969 continue; 01970 01971 bool AllUsesAreAddresses = true; 01972 bool AllUsesAreOutsideLoop = true; 01973 std::vector<BasedUser> UsersToProcess; 01974 const SCEV *CommonExprs = CollectIVUsers(SI->first, *SI->second, L, 01975 AllUsesAreAddresses, 01976 AllUsesAreOutsideLoop, 01977 UsersToProcess); 01978 // Avoid rewriting the compare instruction with an iv of new stride 01979 // if it's likely the new stride uses will be rewritten using the 01980 // stride of the compare instruction. 01981 if (AllUsesAreAddresses && 01982 ValidScale(!CommonExprs->isZero(), Scale, UsersToProcess)) 01983 continue; 01984 01985 // Avoid rewriting the compare instruction with an iv which has 01986 // implicit extension or truncation built into it. 01987 // TODO: This is over-conservative. 01988 if (SE->getTypeSizeInBits(CondUse->getOffset()->getType()) != TyBits) 01989 continue; 01990 01991 // If scale is negative, use swapped predicate unless it's testing 01992 // for equality. 01993 if (Scale < 0 && !Cond->isEquality()) 01994 Predicate = ICmpInst::getSwappedPredicate(Predicate); 01995 01996 NewStride = &IU->StrideOrder[i]; 01997 if (!isa<PointerType>(NewCmpTy)) 01998 NewCmpRHS = ConstantInt::get(NewCmpTy, NewCmpVal); 01999 else { 02000 Constant *CI = ConstantInt::get(NewCmpIntTy, NewCmpVal); 02001 NewCmpRHS = ConstantExpr::getIntToPtr(CI, NewCmpTy); 02002 } 02003 NewOffset = TyBits == NewTyBits 02004 ? SE->getMulExpr(CondUse->getOffset(), 02005 SE->getConstant(CmpTy, Scale)) 02006 : SE->getConstant(NewCmpIntTy, 02007 cast<SCEVConstant>(CondUse->getOffset())->getValue() 02008 ->getSExtValue()*Scale); 02009 break; 02010 } 02011 } 02012 02013 // Forgo this transformation if it the increment happens to be 02014 // unfortunately positioned after the condition, and the condition 02015 // has multiple uses which prevent it from being moved immediately 02016 // before the branch. See 02017 // test/Transforms/LoopStrengthReduce/change-compare-stride-trickiness-*.ll 02018 // for an example of this situation. 02019 if (!Cond->hasOneUse()) { 02020 for (BasicBlock::iterator I = Cond, E = Cond->getParent()->end(); 02021 I != E; ++I) 02022 if (I == NewCmpLHS) 02023 return Cond; 02024 } 02025 02026 if (NewCmpRHS) { 02027 // Create a new compare instruction using new stride / iv. 02028 ICmpInst *OldCond = Cond; 02029 // Insert new compare instruction. 02030 Cond = new ICmpInst(OldCond, Predicate, NewCmpLHS, NewCmpRHS, 02031 L->getHeader()->getName() + ".termcond"); 02032 02033 // Remove the old compare instruction. The old indvar is probably dead too. 02034 DeadInsts.push_back(CondUse->getOperandValToReplace()); 02035 OldCond->replaceAllUsesWith(Cond); 02036 OldCond->eraseFromParent(); 02037 02038 IU->IVUsesByStride[*NewStride]->addUser(NewOffset, Cond, NewCmpLHS); 02039 CondUse = &IU->IVUsesByStride[*NewStride]->Users.back(); 02040 CondStride = NewStride; 02041 ++NumEliminated; 02042 Changed = true; 02043 } 02044 02045 return Cond; 02046 } 02047 02048 /// OptimizeMax - Rewrite the loop's terminating condition if it uses 02049 /// a max computation. 02050 /// 02051 /// This is a narrow solution to a specific, but acute, problem. For loops 02052 /// like this: 02053 /// 02054 /// i = 0; 02055 /// do { 02056 /// p[i] = 0.0; 02057 /// } while (++i < n); 02058 /// 02059 /// the trip count isn't just 'n', because 'n' might not be positive. And 02060 /// unfortunately this can come up even for loops where the user didn't use 02061 /// a C do-while loop. For example, seemingly well-behaved top-test loops 02062 /// will commonly be lowered like this: 02063 // 02064 /// if (n > 0) { 02065 /// i = 0; 02066 /// do { 02067 /// p[i] = 0.0; 02068 /// } while (++i < n); 02069 /// } 02070 /// 02071 /// and then it's possible for subsequent optimization to obscure the if 02072 /// test in such a way that indvars can't find it. 02073 /// 02074 /// When indvars can't find the if test in loops like this, it creates a 02075 /// max expression, which allows it to give the loop a canonical 02076 /// induction variable: 02077 /// 02078 /// i = 0; 02079 /// max = n < 1 ? 1 : n; 02080 /// do { 02081 /// p[i] = 0.0; 02082 /// } while (++i != max); 02083 /// 02084 /// Canonical induction variables are necessary because the loop passes 02085 /// are designed around them. The most obvious example of this is the 02086 /// LoopInfo analysis, which doesn't remember trip count values. It 02087 /// expects to be able to rediscover the trip count each time it is 02088 /// needed, and it does this using a simple analyis that only succeeds if 02089 /// the loop has a canonical induction variable. 02090 /// 02091 /// However, when it comes time to generate code, the maximum operation 02092 /// can be quite costly, especially if it's inside of an outer loop. 02093 /// 02094 /// This function solves this problem by detecting this type of loop and 02095 /// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting 02096 /// the instructions for the maximum computation. 02097 /// 02098 ICmpInst *LoopStrengthReduce::OptimizeMax(Loop *L, ICmpInst *Cond, 02099 IVStrideUse* &CondUse) { 02100 // Check that the loop matches the pattern we're looking for. 02101 if (Cond->getPredicate() != CmpInst::ICMP_EQ && 02102 Cond->getPredicate() != CmpInst::ICMP_NE) 02103 return Cond; 02104 02105 SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1)); 02106 if (!Sel || !Sel->hasOneUse()) return Cond; 02107 02108 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 02109 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 02110 return Cond; 02111 const SCEV *One = SE->getIntegerSCEV(1, BackedgeTakenCount->getType()); 02112 02113 // Add one to the backedge-taken count to get the trip count. 02114 const SCEV *IterationCount = SE->getAddExpr(BackedgeTakenCount, One); 02115 02116 // Check for a max calculation that matches the pattern. 02117 if (!isa<SCEVSMaxExpr>(IterationCount) && !isa<SCEVUMaxExpr>(IterationCount)) 02118 return Cond; 02119 const SCEVNAryExpr *Max = cast<SCEVNAryExpr>(IterationCount); 02120 if (Max != SE->getSCEV(Sel)) return Cond; 02121 02122 // To handle a max with more than two operands, this optimization would 02123 // require additional checking and setup. 02124 if (Max->getNumOperands() != 2) 02125 return Cond; 02126 02127 const SCEV *MaxLHS = Max->getOperand(0); 02128 const SCEV *MaxRHS = Max->getOperand(1); 02129 if (!MaxLHS || MaxLHS != One) return Cond; 02130 02131 // Check the relevant induction variable for conformance to 02132 // the pattern. 02133 const SCEV *IV = SE->getSCEV(Cond->getOperand(0)); 02134 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 02135 if (!AR || !AR->isAffine() || 02136 AR->getStart() != One || 02137 AR->getStepRecurrence(*SE) != One) 02138 return Cond; 02139 02140 assert(AR->getLoop() == L && 02141 "Loop condition operand is an addrec in a different loop!"); 02142 02143 // Check the right operand of the select, and remember it, as it will 02144 // be used in the new comparison instruction. 02145 Value *NewRHS = 0; 02146 if (SE->getSCEV(Sel->getOperand(1)) == MaxRHS) 02147 NewRHS = Sel->getOperand(1); 02148 else if (SE->getSCEV(Sel->getOperand(2)) == MaxRHS) 02149 NewRHS = Sel->getOperand(2); 02150 if (!NewRHS) return Cond; 02151 02152 // Determine the new comparison opcode. It may be signed or unsigned, 02153 // and the original comparison may be either equality or inequality. 02154 CmpInst::Predicate Pred = 02155 isa<SCEVSMaxExpr>(Max) ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; 02156 if (Cond->getPredicate() == CmpInst::ICMP_EQ) 02157 Pred = CmpInst::getInversePredicate(Pred); 02158 02159 // Ok, everything looks ok to change the condition into an SLT or SGE and 02160 // delete the max calculation. 02161 ICmpInst *NewCond = 02162 new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp"); 02163 02164 // Delete the max calculation instructions. 02165 Cond->replaceAllUsesWith(NewCond); 02166 CondUse->setUser(NewCond); 02167 Instruction *Cmp = cast<Instruction>(Sel->getOperand(0)); 02168 Cond->eraseFromParent(); 02169 Sel->eraseFromParent(); 02170 if (Cmp->use_empty()) 02171 Cmp->eraseFromParent(); 02172 return NewCond; 02173 } 02174 02175 /// OptimizeShadowIV - If IV is used in a int-to-float cast 02176 /// inside the loop then try to eliminate the cast opeation. 02177 void LoopStrengthReduce::OptimizeShadowIV(Loop *L) { 02178 02179 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 02180 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 02181 return; 02182 02183 for (unsigned Stride = 0, e = IU->StrideOrder.size(); Stride != e; 02184 ++Stride) { 02185 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 02186 IU->IVUsesByStride.find(IU->StrideOrder[Stride]); 02187 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 02188 if (!isa<SCEVConstant>(SI->first)) 02189 continue; 02190 02191 for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(), 02192 E = SI->second->Users.end(); UI != E; /* empty */) { 02193 ilist<IVStrideUse>::iterator CandidateUI = UI; 02194 ++UI; 02195 Instruction *ShadowUse = CandidateUI->getUser(); 02196 const Type *DestTy = NULL; 02197 02198 /* If shadow use is a int->float cast then insert a second IV 02199 to eliminate this cast. 02200 02201 for (unsigned i = 0; i < n; ++i) 02202 foo((double)i); 02203 02204 is transformed into 02205 02206 double d = 0.0; 02207 for (unsigned i = 0; i < n; ++i, ++d) 02208 foo(d); 02209 */ 02210 if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) 02211 DestTy = UCast->getDestTy(); 02212 else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) 02213 DestTy = SCast->getDestTy(); 02214 if (!DestTy) continue; 02215 02216 if (TLI) { 02217 // If target does not support DestTy natively then do not apply 02218 // this transformation. 02219 EVT DVT = TLI->getValueType(DestTy); 02220 if (!TLI->isTypeLegal(DVT)) continue; 02221 } 02222 02223 PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0)); 02224 if (!PH) continue; 02225 if (PH->getNumIncomingValues() != 2) continue; 02226 02227 const Type *SrcTy = PH->getType(); 02228 int Mantissa = DestTy->getFPMantissaWidth(); 02229 if (Mantissa == -1) continue; 02230 if ((int)SE->getTypeSizeInBits(SrcTy) > Mantissa) 02231 continue; 02232 02233 unsigned Entry, Latch; 02234 if (PH->getIncomingBlock(0) == L->getLoopPreheader()) { 02235 Entry = 0; 02236 Latch = 1; 02237 } else { 02238 Entry = 1; 02239 Latch = 0; 02240 } 02241 02242 ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry)); 02243 if (!Init) continue; 02244 Constant *NewInit = ConstantFP::get(DestTy, Init->getZExtValue()); 02245 02246 BinaryOperator *Incr = 02247 dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch)); 02248 if (!Incr) continue; 02249 if (Incr->getOpcode() != Instruction::Add 02250 && Incr->getOpcode() != Instruction::Sub) 02251 continue; 02252 02253 /* Initialize new IV, double d = 0.0 in above example. */ 02254 ConstantInt *C = NULL; 02255 if (Incr->getOperand(0) == PH) 02256 C = dyn_cast<ConstantInt>(Incr->getOperand(1)); 02257 else if (Incr->getOperand(1) == PH) 02258 C = dyn_cast<ConstantInt>(Incr->getOperand(0)); 02259 else 02260 continue; 02261 02262 if (!C) continue; 02263 02264 /* Add new PHINode. */ 02265 PHINode *NewPH = PHINode::Create(DestTy, "IV.S.", PH); 02266 02267 /* create new increment. '++d' in above example. */ 02268 Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue()); 02269 BinaryOperator *NewIncr = 02270 BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ? 02271 Instruction::FAdd : Instruction::FSub, 02272 NewPH, CFP, "IV.S.next.", Incr); 02273 02274 NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry)); 02275 NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch)); 02276 02277 /* Remove cast operation */ 02278 ShadowUse->replaceAllUsesWith(NewPH); 02279 ShadowUse->eraseFromParent(); 02280 NumShadow++; 02281 break; 02282 } 02283 } 02284 } 02285 02286 /// OptimizeIndvars - Now that IVUsesByStride is set up with all of the indvar 02287 /// uses in the loop, look to see if we can eliminate some, in favor of using 02288 /// common indvars for the different uses. 02289 void LoopStrengthReduce::OptimizeIndvars(Loop *L) { 02290 // TODO: implement optzns here. 02291 02292 OptimizeShadowIV(L); 02293 } 02294 02295 /// OptimizeLoopTermCond - Change loop terminating condition to use the 02296 /// postinc iv when possible. 02297 void LoopStrengthReduce::OptimizeLoopTermCond(Loop *L) { 02298 // Finally, get the terminating condition for the loop if possible. If we 02299 // can, we want to change it to use a post-incremented version of its 02300 // induction variable, to allow coalescing the live ranges for the IV into 02301 // one register value. 02302 BasicBlock *LatchBlock = L->getLoopLatch(); 02303 BasicBlock *ExitingBlock = L->getExitingBlock(); 02304 LLVMContext &Context = LatchBlock->getContext(); 02305 02306 if (!ExitingBlock) 02307 // Multiple exits, just look at the exit in the latch block if there is one. 02308 ExitingBlock = LatchBlock; 02309 BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 02310 if (!TermBr) 02311 return; 02312 if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition())) 02313 return; 02314 02315 // Search IVUsesByStride to find Cond's IVUse if there is one. 02316 IVStrideUse *CondUse = 0; 02317 const SCEV *const *CondStride = 0; 02318 ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition()); 02319 if (!FindIVUserForCond(Cond, CondUse, CondStride)) 02320 return; // setcc doesn't use the IV. 02321 02322 if (ExitingBlock != LatchBlock) { 02323 if (!Cond->hasOneUse()) 02324 // See below, we don't want the condition to be cloned. 02325 return; 02326 02327 // If exiting block is the latch block, we know it's safe and profitable to 02328 // transform the icmp to use post-inc iv. Otherwise do so only if it would 02329 // not reuse another iv and its iv would be reused by other uses. We are 02330 // optimizing for the case where the icmp is the only use of the iv. 02331 IVUsersOfOneStride &StrideUses = *IU->IVUsesByStride[*CondStride]; 02332 for (ilist<IVStrideUse>::iterator I = StrideUses.Users.begin(), 02333 E = StrideUses.Users.end(); I != E; ++I) { 02334 if (I->getUser() == Cond) 02335 continue; 02336 if (!I->isUseOfPostIncrementedValue()) 02337 return; 02338 } 02339 02340 // FIXME: This is expensive, and worse still ChangeCompareStride does a 02341 // similar check. Can we perform all the icmp related transformations after 02342 // StrengthReduceStridedIVUsers? 02343 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(*CondStride)) { 02344 int64_t SInt = SC->getValue()->getSExtValue(); 02345 for (unsigned NewStride = 0, ee = IU->StrideOrder.size(); NewStride != ee; 02346 ++NewStride) { 02347 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 02348 IU->IVUsesByStride.find(IU->StrideOrder[NewStride]); 02349 if (!isa<SCEVConstant>(SI->first) || SI->first == *CondStride) 02350 continue; 02351 int64_t SSInt = 02352 cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 02353 if (SSInt == SInt) 02354 return; // This can definitely be reused. 02355 if (unsigned(abs64(SSInt)) < SInt || (SSInt % SInt) != 0) 02356 continue; 02357 int64_t Scale = SSInt / SInt; 02358 bool AllUsesAreAddresses = true; 02359 bool AllUsesAreOutsideLoop = true; 02360 std::vector<BasedUser> UsersToProcess; 02361 const SCEV *CommonExprs = CollectIVUsers(SI->first, *SI->second, L, 02362 AllUsesAreAddresses, 02363 AllUsesAreOutsideLoop, 02364 UsersToProcess); 02365 // Avoid rewriting the compare instruction with an iv of new stride 02366 // if it's likely the new stride uses will be rewritten using the 02367 // stride of the compare instruction. 02368 if (AllUsesAreAddresses && 02369 ValidScale(!CommonExprs->isZero(), Scale, UsersToProcess)) 02370 return; 02371 } 02372 } 02373 02374 StrideNoReuse.insert(*CondStride); 02375 } 02376 02377 // If the trip count is computed in terms of a max (due to ScalarEvolution 02378 // being unable to find a sufficient guard, for example), change the loop 02379 // comparison to use SLT or ULT instead of NE. 02380 Cond = OptimizeMax(L, Cond, CondUse); 02381 02382 // If possible, change stride and operands of the compare instruction to 02383 // eliminate one stride. 02384 if (ExitingBlock == LatchBlock) 02385 Cond = ChangeCompareStride(L, Cond, CondUse, CondStride); 02386 02387 // It's possible for the setcc instruction to be anywhere in the loop, and 02388 // possible for it to have multiple users. If it is not immediately before 02389 // the latch block branch, move it. 02390 if (&*++BasicBlock::iterator(Cond) != (Instruction*)TermBr) { 02391 if (Cond->hasOneUse()) { // Condition has a single use, just move it. 02392 Cond->moveBefore(TermBr); 02393 } else { 02394 // Otherwise, clone the terminating condition and insert into the loopend. 02395 Cond = cast<ICmpInst>(Cond->clone(Context)); 02396 Cond->setName(L->getHeader()->getName() + ".termcond"); 02397 LatchBlock->getInstList().insert(TermBr, Cond); 02398 02399 // Clone the IVUse, as the old use still exists! 02400 IU->IVUsesByStride[*CondStride]->addUser(CondUse->getOffset(), Cond, 02401 CondUse->getOperandValToReplace()); 02402 CondUse = &IU->IVUsesByStride[*CondStride]->Users.back(); 02403 } 02404 } 02405 02406 // If we get to here, we know that we can transform the setcc instruction to 02407 // use the post-incremented version of the IV, allowing us to coalesce the 02408 // live ranges for the IV correctly. 02409 CondUse->setOffset(SE->getMinusSCEV(CondUse->getOffset(), *CondStride)); 02410 CondUse->setIsUseOfPostIncrementedValue(true); 02411 Changed = true; 02412 02413 ++NumLoopCond; 02414 } 02415 02416 /// OptimizeLoopCountIV - If, after all sharing of IVs, the IV used for deciding 02417 /// when to exit the loop is used only for that purpose, try to rearrange things 02418 /// so it counts down to a test against zero. 02419 void LoopStrengthReduce::OptimizeLoopCountIV(Loop *L) { 02420 02421 // If the number of times the loop is executed isn't computable, give up. 02422 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 02423 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 02424 return; 02425 02426 // Get the terminating condition for the loop if possible (this isn't 02427 // necessarily in the latch, or a block that's a predecessor of the header). 02428 if (!L->getExitBlock()) 02429 return; // More than one loop exit blocks. 02430 02431 // Okay, there is one exit block. Try to find the condition that causes the 02432 // loop to be exited. 02433 BasicBlock *ExitingBlock = L->getExitingBlock(); 02434 if (!ExitingBlock) 02435 return; // More than one block exiting! 02436 02437 // Okay, we've computed the exiting block. See what condition causes us to 02438 // exit. 02439 // 02440 // FIXME: we should be able to handle switch instructions (with a single exit) 02441 BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 02442 if (TermBr == 0) return; 02443 assert(TermBr->isConditional() && "If unconditional, it can't be in loop!"); 02444 if (!isa<ICmpInst>(TermBr->getCondition())) 02445 return; 02446 ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition()); 02447 02448 // Handle only tests for equality for the moment, and only stride 1. 02449 if (Cond->getPredicate() != CmpInst::ICMP_EQ) 02450 return; 02451 const SCEV *IV = SE->getSCEV(Cond->getOperand(0)); 02452 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 02453 const SCEV *One = SE->getIntegerSCEV(1, BackedgeTakenCount->getType()); 02454 if (!AR || !AR->isAffine() || AR->getStepRecurrence(*SE) != One) 02455 return; 02456 // If the RHS of the comparison is defined inside the loop, the rewrite 02457 // cannot be done. 02458 if (Instruction *CR = dyn_cast<Instruction>(Cond->getOperand(1))) 02459 if (L->contains(CR->getParent())) 02460 return; 02461 02462 // Make sure the IV is only used for counting. Value may be preinc or 02463 // postinc; 2 uses in either case. 02464 if (!Cond->getOperand(0)->hasNUses(2)) 02465 return; 02466 PHINode *phi = dyn_cast<PHINode>(Cond->getOperand(0)); 02467 Instruction *incr; 02468 if (phi && phi->getParent()==L->getHeader()) { 02469 // value tested is preinc. Find the increment. 02470 // A CmpInst is not a BinaryOperator; we depend on this. 02471 Instruction::use_iterator UI = phi->use_begin(); 02472 incr = dyn_cast<BinaryOperator>(UI); 02473 if (!incr) 02474 incr = dyn_cast<BinaryOperator>(++UI); 02475 // 1 use for postinc value, the phi. Unnecessarily conservative? 02476 if (!incr || !incr->hasOneUse() || incr->getOpcode()!=Instruction::Add) 02477 return; 02478 } else { 02479 // Value tested is postinc. Find the phi node. 02480 incr = dyn_cast<BinaryOperator>(Cond->getOperand(0)); 02481 if (!incr || incr->getOpcode()!=Instruction::Add) 02482 return; 02483 02484 Instruction::use_iterator UI = Cond->getOperand(0)->use_begin(); 02485 phi = dyn_cast<PHINode>(UI); 02486 if (!phi) 02487 phi = dyn_cast<PHINode>(++UI); 02488 // 1 use for preinc value, the increment. 02489 if (!phi || phi->getParent()!=L->getHeader() || !phi->hasOneUse()) 02490 return; 02491 } 02492 02493 // Replace the increment with a decrement. 02494 BinaryOperator *decr = 02495 BinaryOperator::Create(Instruction::Sub, incr->getOperand(0), 02496 incr->getOperand(1), "tmp", incr); 02497 incr->replaceAllUsesWith(decr); 02498 incr->eraseFromParent(); 02499 02500 // Substitute endval-startval for the original startval, and 0 for the 02501 // original endval. Since we're only testing for equality this is OK even 02502 // if the computation wraps around. 02503 BasicBlock *Preheader = L->getLoopPreheader(); 02504 Instruction *PreInsertPt = Preheader->getTerminator(); 02505 int inBlock = L->contains(phi->getIncomingBlock(0)) ? 1 : 0; 02506 Value *startVal = phi->getIncomingValue(inBlock); 02507 Value *endVal = Cond->getOperand(1); 02508 // FIXME check for case where both are constant 02509 Constant* Zero = ConstantInt::get(Cond->getOperand(1)->getType(), 0); 02510 BinaryOperator *NewStartVal = 02511 BinaryOperator::Create(Instruction::Sub, endVal, startVal, 02512 "tmp", PreInsertPt); 02513 phi->setIncomingValue(inBlock, NewStartVal); 02514 Cond->setOperand(1, Zero); 02515 02516 Changed = true; 02517 } 02518 02519 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) { 02520 02521 IU = &getAnalysis<IVUsers>(); 02522 LI = &getAnalysis<LoopInfo>(); 02523 DT = &getAnalysis<DominatorTree>(); 02524 SE = &getAnalysis<ScalarEvolution>(); 02525 Changed = false; 02526 02527 if (!IU->IVUsesByStride.empty()) { 02528 DEBUG(errs() << "\nLSR on \"" << L->getHeader()->getParent()->getName() 02529 << "\" "; 02530 L->dump()); 02531 02532 // Sort the StrideOrder so we process larger strides first. 02533 std::stable_sort(IU->StrideOrder.begin(), IU->StrideOrder.end(), 02534 StrideCompare(SE)); 02535 02536 // Optimize induction variables. Some indvar uses can be transformed to use 02537 // strides that will be needed for other purposes. A common example of this 02538 // is the exit test for the loop, which can often be rewritten to use the 02539 // computation of some other indvar to decide when to terminate the loop. 02540 OptimizeIndvars(L); 02541 02542 // Change loop terminating condition to use the postinc iv when possible 02543 // and optimize loop terminating compare. FIXME: Move this after 02544 // StrengthReduceStridedIVUsers? 02545 OptimizeLoopTermCond(L); 02546 02547 // FIXME: We can shrink overlarge IV's here. e.g. if the code has 02548 // computation in i64 values and the target doesn't support i64, demote 02549 // the computation to 32-bit if safe. 02550 02551 // FIXME: Attempt to reuse values across multiple IV's. In particular, we 02552 // could have something like "for(i) { foo(i*8); bar(i*16) }", which should 02553 // be codegened as "for (j = 0;; j+=8) { foo(j); bar(j+j); }" on X86/PPC. 02554 // Need to be careful that IV's are all the same type. Only works for 02555 // intptr_t indvars. 02556 02557 // IVsByStride keeps IVs for one particular loop. 02558 assert(IVsByStride.empty() && "Stale entries in IVsByStride?"); 02559 02560 // Note: this processes each stride/type pair individually. All users 02561 // passed into StrengthReduceStridedIVUsers have the same type AND stride. 02562 // Also, note that we iterate over IVUsesByStride indirectly by using 02563 // StrideOrder. This extra layer of indirection makes the ordering of 02564 // strides deterministic - not dependent on map order. 02565 for (unsigned Stride = 0, e = IU->StrideOrder.size(); 02566 Stride != e; ++Stride) { 02567 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 02568 IU->IVUsesByStride.find(IU->StrideOrder[Stride]); 02569 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 02570 // FIXME: Generalize to non-affine IV's. 02571 if (!SI->first->isLoopInvariant(L)) 02572 continue; 02573 StrengthReduceStridedIVUsers(SI->first, *SI->second, L); 02574 } 02575 } 02576 02577 // After all sharing is done, see if we can adjust the loop to test against 02578 // zero instead of counting up to a maximum. This is usually faster. 02579 OptimizeLoopCountIV(L); 02580 02581 // We're done analyzing this loop; release all the state we built up for it. 02582 IVsByStride.clear(); 02583 StrideNoReuse.clear(); 02584 02585 // Clean up after ourselves 02586 if (!DeadInsts.empty()) 02587 DeleteTriviallyDeadInstructions(); 02588 02589 // At this point, it is worth checking to see if any recurrence PHIs are also 02590 // dead, so that we can remove them as well. 02591 DeleteDeadPHIs(L->getHeader()); 02592 02593 return Changed; 02594 }