LoopStrengthReduce.cpp revision 199481
1//===- LoopStrengthReduce.cpp - Strength Reduce IVs in Loops --------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This transformation analyzes and transforms the induction variables (and 11// computations derived from them) into forms suitable for efficient execution 12// on the target. 13// 14// This pass performs a strength reduction on array references inside loops that 15// have as one or more of their components the loop induction variable, it 16// rewrites expressions to take advantage of scaled-index addressing modes 17// available on the target, and it performs a variety of other optimizations 18// related to loop induction variables. 19// 20//===----------------------------------------------------------------------===// 21 22#define DEBUG_TYPE "loop-reduce" 23#include "llvm/Transforms/Scalar.h" 24#include "llvm/Constants.h" 25#include "llvm/Instructions.h" 26#include "llvm/IntrinsicInst.h" 27#include "llvm/Type.h" 28#include "llvm/DerivedTypes.h" 29#include "llvm/Analysis/Dominators.h" 30#include "llvm/Analysis/IVUsers.h" 31#include "llvm/Analysis/LoopInfo.h" 32#include "llvm/Analysis/LoopPass.h" 33#include "llvm/Analysis/ScalarEvolutionExpander.h" 34#include "llvm/Transforms/Utils/AddrModeMatcher.h" 35#include "llvm/Transforms/Utils/BasicBlockUtils.h" 36#include "llvm/Transforms/Utils/Local.h" 37#include "llvm/ADT/Statistic.h" 38#include "llvm/Support/CFG.h" 39#include "llvm/Support/Debug.h" 40#include "llvm/Support/CommandLine.h" 41#include "llvm/Support/ValueHandle.h" 42#include "llvm/Support/raw_ostream.h" 43#include "llvm/Target/TargetLowering.h" 44#include <algorithm> 45using namespace llvm; 46 47STATISTIC(NumReduced , "Number of IV uses strength reduced"); 48STATISTIC(NumInserted, "Number of PHIs inserted"); 49STATISTIC(NumVariable, "Number of PHIs with variable strides"); 50STATISTIC(NumEliminated, "Number of strides eliminated"); 51STATISTIC(NumShadow, "Number of Shadow IVs optimized"); 52STATISTIC(NumImmSunk, "Number of common expr immediates sunk into uses"); 53STATISTIC(NumLoopCond, "Number of loop terminating conds optimized"); 54STATISTIC(NumCountZero, "Number of count iv optimized to count toward zero"); 55 56static cl::opt<bool> EnableFullLSRMode("enable-full-lsr", 57 cl::init(false), 58 cl::Hidden); 59 60namespace { 61 62 struct BasedUser; 63 64 /// IVInfo - This structure keeps track of one IV expression inserted during 65 /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as 66 /// well as the PHI node and increment value created for rewrite. 67 struct IVExpr { 68 const SCEV *Stride; 69 const SCEV *Base; 70 PHINode *PHI; 71 72 IVExpr(const SCEV *const stride, const SCEV *const base, PHINode *phi) 73 : Stride(stride), Base(base), PHI(phi) {} 74 }; 75 76 /// IVsOfOneStride - This structure keeps track of all IV expression inserted 77 /// during StrengthReduceStridedIVUsers for a particular stride of the IV. 78 struct IVsOfOneStride { 79 std::vector<IVExpr> IVs; 80 81 void addIV(const SCEV *const Stride, const SCEV *const Base, PHINode *PHI) { 82 IVs.push_back(IVExpr(Stride, Base, PHI)); 83 } 84 }; 85 86 class LoopStrengthReduce : public LoopPass { 87 IVUsers *IU; 88 LoopInfo *LI; 89 DominatorTree *DT; 90 ScalarEvolution *SE; 91 bool Changed; 92 93 /// IVsByStride - Keep track of all IVs that have been inserted for a 94 /// particular stride. 95 std::map<const SCEV *, IVsOfOneStride> IVsByStride; 96 97 /// StrideNoReuse - Keep track of all the strides whose ivs cannot be 98 /// reused (nor should they be rewritten to reuse other strides). 99 SmallSet<const SCEV *, 4> StrideNoReuse; 100 101 /// DeadInsts - Keep track of instructions we may have made dead, so that 102 /// we can remove them after we are done working. 103 SmallVector<WeakVH, 16> DeadInsts; 104 105 /// TLI - Keep a pointer of a TargetLowering to consult for determining 106 /// transformation profitability. 107 const TargetLowering *TLI; 108 109 public: 110 static char ID; // Pass ID, replacement for typeid 111 explicit LoopStrengthReduce(const TargetLowering *tli = NULL) : 112 LoopPass(&ID), TLI(tli) { 113 } 114 115 bool runOnLoop(Loop *L, LPPassManager &LPM); 116 117 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 118 // We split critical edges, so we change the CFG. However, we do update 119 // many analyses if they are around. 120 AU.addPreservedID(LoopSimplifyID); 121 AU.addPreserved<LoopInfo>(); 122 AU.addPreserved<DominanceFrontier>(); 123 AU.addPreserved<DominatorTree>(); 124 125 AU.addRequiredID(LoopSimplifyID); 126 AU.addRequired<LoopInfo>(); 127 AU.addRequired<DominatorTree>(); 128 AU.addRequired<ScalarEvolution>(); 129 AU.addPreserved<ScalarEvolution>(); 130 AU.addRequired<IVUsers>(); 131 AU.addPreserved<IVUsers>(); 132 } 133 134 private: 135 void OptimizeIndvars(Loop *L); 136 137 /// OptimizeLoopTermCond - Change loop terminating condition to use the 138 /// postinc iv when possible. 139 void OptimizeLoopTermCond(Loop *L); 140 141 /// OptimizeShadowIV - If IV is used in a int-to-float cast 142 /// inside the loop then try to eliminate the cast opeation. 143 void OptimizeShadowIV(Loop *L); 144 145 /// OptimizeMax - Rewrite the loop's terminating condition 146 /// if it uses a max computation. 147 ICmpInst *OptimizeMax(Loop *L, ICmpInst *Cond, 148 IVStrideUse* &CondUse); 149 150 /// OptimizeLoopCountIV - If, after all sharing of IVs, the IV used for 151 /// deciding when to exit the loop is used only for that purpose, try to 152 /// rearrange things so it counts down to a test against zero. 153 bool OptimizeLoopCountIV(Loop *L); 154 bool OptimizeLoopCountIVOfStride(const SCEV* &Stride, 155 IVStrideUse* &CondUse, Loop *L); 156 157 /// StrengthReduceIVUsersOfStride - Strength reduce all of the users of a 158 /// single stride of IV. All of the users may have different starting 159 /// values, and this may not be the only stride. 160 void StrengthReduceIVUsersOfStride(const SCEV *const &Stride, 161 IVUsersOfOneStride &Uses, 162 Loop *L); 163 void StrengthReduceIVUsers(Loop *L); 164 165 ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond, 166 IVStrideUse* &CondUse, 167 const SCEV* &CondStride, 168 bool PostPass = false); 169 170 bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse, 171 const SCEV* &CondStride); 172 bool RequiresTypeConversion(const Type *Ty, const Type *NewTy); 173 const SCEV *CheckForIVReuse(bool, bool, bool, const SCEV *const&, 174 IVExpr&, const Type*, 175 const std::vector<BasedUser>& UsersToProcess); 176 bool ValidScale(bool, int64_t, 177 const std::vector<BasedUser>& UsersToProcess); 178 bool ValidOffset(bool, int64_t, int64_t, 179 const std::vector<BasedUser>& UsersToProcess); 180 const SCEV *CollectIVUsers(const SCEV *const &Stride, 181 IVUsersOfOneStride &Uses, 182 Loop *L, 183 bool &AllUsesAreAddresses, 184 bool &AllUsesAreOutsideLoop, 185 std::vector<BasedUser> &UsersToProcess); 186 bool StrideMightBeShared(const SCEV *Stride, Loop *L, bool CheckPreInc); 187 bool ShouldUseFullStrengthReductionMode( 188 const std::vector<BasedUser> &UsersToProcess, 189 const Loop *L, 190 bool AllUsesAreAddresses, 191 const SCEV *Stride); 192 void PrepareToStrengthReduceFully( 193 std::vector<BasedUser> &UsersToProcess, 194 const SCEV *Stride, 195 const SCEV *CommonExprs, 196 const Loop *L, 197 SCEVExpander &PreheaderRewriter); 198 void PrepareToStrengthReduceFromSmallerStride( 199 std::vector<BasedUser> &UsersToProcess, 200 Value *CommonBaseV, 201 const IVExpr &ReuseIV, 202 Instruction *PreInsertPt); 203 void PrepareToStrengthReduceWithNewPhi( 204 std::vector<BasedUser> &UsersToProcess, 205 const SCEV *Stride, 206 const SCEV *CommonExprs, 207 Value *CommonBaseV, 208 Instruction *IVIncInsertPt, 209 const Loop *L, 210 SCEVExpander &PreheaderRewriter); 211 212 void DeleteTriviallyDeadInstructions(); 213 }; 214} 215 216char LoopStrengthReduce::ID = 0; 217static RegisterPass<LoopStrengthReduce> 218X("loop-reduce", "Loop Strength Reduction"); 219 220Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) { 221 return new LoopStrengthReduce(TLI); 222} 223 224/// DeleteTriviallyDeadInstructions - If any of the instructions is the 225/// specified set are trivially dead, delete them and see if this makes any of 226/// their operands subsequently dead. 227void LoopStrengthReduce::DeleteTriviallyDeadInstructions() { 228 if (DeadInsts.empty()) return; 229 230 while (!DeadInsts.empty()) { 231 Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.back()); 232 DeadInsts.pop_back(); 233 234 if (I == 0 || !isInstructionTriviallyDead(I)) 235 continue; 236 237 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) { 238 if (Instruction *U = dyn_cast<Instruction>(*OI)) { 239 *OI = 0; 240 if (U->use_empty()) 241 DeadInsts.push_back(U); 242 } 243 } 244 245 I->eraseFromParent(); 246 Changed = true; 247 } 248} 249 250/// containsAddRecFromDifferentLoop - Determine whether expression S involves a 251/// subexpression that is an AddRec from a loop other than L. An outer loop 252/// of L is OK, but not an inner loop nor a disjoint loop. 253static bool containsAddRecFromDifferentLoop(const SCEV *S, Loop *L) { 254 // This is very common, put it first. 255 if (isa<SCEVConstant>(S)) 256 return false; 257 if (const SCEVCommutativeExpr *AE = dyn_cast<SCEVCommutativeExpr>(S)) { 258 for (unsigned int i=0; i< AE->getNumOperands(); i++) 259 if (containsAddRecFromDifferentLoop(AE->getOperand(i), L)) 260 return true; 261 return false; 262 } 263 if (const SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) { 264 if (const Loop *newLoop = AE->getLoop()) { 265 if (newLoop == L) 266 return false; 267 // if newLoop is an outer loop of L, this is OK. 268 if (!LoopInfo::isNotAlreadyContainedIn(L, newLoop)) 269 return false; 270 } 271 return true; 272 } 273 if (const SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S)) 274 return containsAddRecFromDifferentLoop(DE->getLHS(), L) || 275 containsAddRecFromDifferentLoop(DE->getRHS(), L); 276#if 0 277 // SCEVSDivExpr has been backed out temporarily, but will be back; we'll 278 // need this when it is. 279 if (const SCEVSDivExpr *DE = dyn_cast<SCEVSDivExpr>(S)) 280 return containsAddRecFromDifferentLoop(DE->getLHS(), L) || 281 containsAddRecFromDifferentLoop(DE->getRHS(), L); 282#endif 283 if (const SCEVCastExpr *CE = dyn_cast<SCEVCastExpr>(S)) 284 return containsAddRecFromDifferentLoop(CE->getOperand(), L); 285 return false; 286} 287 288/// isAddressUse - Returns true if the specified instruction is using the 289/// specified value as an address. 290static bool isAddressUse(Instruction *Inst, Value *OperandVal) { 291 bool isAddress = isa<LoadInst>(Inst); 292 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 293 if (SI->getOperand(1) == OperandVal) 294 isAddress = true; 295 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 296 // Addressing modes can also be folded into prefetches and a variety 297 // of intrinsics. 298 switch (II->getIntrinsicID()) { 299 default: break; 300 case Intrinsic::prefetch: 301 case Intrinsic::x86_sse2_loadu_dq: 302 case Intrinsic::x86_sse2_loadu_pd: 303 case Intrinsic::x86_sse_loadu_ps: 304 case Intrinsic::x86_sse_storeu_ps: 305 case Intrinsic::x86_sse2_storeu_pd: 306 case Intrinsic::x86_sse2_storeu_dq: 307 case Intrinsic::x86_sse2_storel_dq: 308 if (II->getOperand(1) == OperandVal) 309 isAddress = true; 310 break; 311 } 312 } 313 return isAddress; 314} 315 316/// getAccessType - Return the type of the memory being accessed. 317static const Type *getAccessType(const Instruction *Inst) { 318 const Type *AccessTy = Inst->getType(); 319 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) 320 AccessTy = SI->getOperand(0)->getType(); 321 else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 322 // Addressing modes can also be folded into prefetches and a variety 323 // of intrinsics. 324 switch (II->getIntrinsicID()) { 325 default: break; 326 case Intrinsic::x86_sse_storeu_ps: 327 case Intrinsic::x86_sse2_storeu_pd: 328 case Intrinsic::x86_sse2_storeu_dq: 329 case Intrinsic::x86_sse2_storel_dq: 330 AccessTy = II->getOperand(1)->getType(); 331 break; 332 } 333 } 334 return AccessTy; 335} 336 337namespace { 338 /// BasedUser - For a particular base value, keep information about how we've 339 /// partitioned the expression so far. 340 struct BasedUser { 341 /// SE - The current ScalarEvolution object. 342 ScalarEvolution *SE; 343 344 /// Base - The Base value for the PHI node that needs to be inserted for 345 /// this use. As the use is processed, information gets moved from this 346 /// field to the Imm field (below). BasedUser values are sorted by this 347 /// field. 348 const SCEV *Base; 349 350 /// Inst - The instruction using the induction variable. 351 Instruction *Inst; 352 353 /// OperandValToReplace - The operand value of Inst to replace with the 354 /// EmittedBase. 355 Value *OperandValToReplace; 356 357 /// Imm - The immediate value that should be added to the base immediately 358 /// before Inst, because it will be folded into the imm field of the 359 /// instruction. This is also sometimes used for loop-variant values that 360 /// must be added inside the loop. 361 const SCEV *Imm; 362 363 /// Phi - The induction variable that performs the striding that 364 /// should be used for this user. 365 PHINode *Phi; 366 367 // isUseOfPostIncrementedValue - True if this should use the 368 // post-incremented version of this IV, not the preincremented version. 369 // This can only be set in special cases, such as the terminating setcc 370 // instruction for a loop and uses outside the loop that are dominated by 371 // the loop. 372 bool isUseOfPostIncrementedValue; 373 374 BasedUser(IVStrideUse &IVSU, ScalarEvolution *se) 375 : SE(se), Base(IVSU.getOffset()), Inst(IVSU.getUser()), 376 OperandValToReplace(IVSU.getOperandValToReplace()), 377 Imm(SE->getIntegerSCEV(0, Base->getType())), 378 isUseOfPostIncrementedValue(IVSU.isUseOfPostIncrementedValue()) {} 379 380 // Once we rewrite the code to insert the new IVs we want, update the 381 // operands of Inst to use the new expression 'NewBase', with 'Imm' added 382 // to it. 383 void RewriteInstructionToUseNewBase(const SCEV *const &NewBase, 384 Instruction *InsertPt, 385 SCEVExpander &Rewriter, Loop *L, Pass *P, 386 LoopInfo &LI, 387 SmallVectorImpl<WeakVH> &DeadInsts); 388 389 Value *InsertCodeForBaseAtPosition(const SCEV *const &NewBase, 390 const Type *Ty, 391 SCEVExpander &Rewriter, 392 Instruction *IP, Loop *L, 393 LoopInfo &LI); 394 void dump() const; 395 }; 396} 397 398void BasedUser::dump() const { 399 errs() << " Base=" << *Base; 400 errs() << " Imm=" << *Imm; 401 errs() << " Inst: " << *Inst; 402} 403 404Value *BasedUser::InsertCodeForBaseAtPosition(const SCEV *const &NewBase, 405 const Type *Ty, 406 SCEVExpander &Rewriter, 407 Instruction *IP, Loop *L, 408 LoopInfo &LI) { 409 // Figure out where we *really* want to insert this code. In particular, if 410 // the user is inside of a loop that is nested inside of L, we really don't 411 // want to insert this expression before the user, we'd rather pull it out as 412 // many loops as possible. 413 Instruction *BaseInsertPt = IP; 414 415 // Figure out the most-nested loop that IP is in. 416 Loop *InsertLoop = LI.getLoopFor(IP->getParent()); 417 418 // If InsertLoop is not L, and InsertLoop is nested inside of L, figure out 419 // the preheader of the outer-most loop where NewBase is not loop invariant. 420 if (L->contains(IP->getParent())) 421 while (InsertLoop && NewBase->isLoopInvariant(InsertLoop)) { 422 BaseInsertPt = InsertLoop->getLoopPreheader()->getTerminator(); 423 InsertLoop = InsertLoop->getParentLoop(); 424 } 425 426 Value *Base = Rewriter.expandCodeFor(NewBase, 0, BaseInsertPt); 427 428 const SCEV *NewValSCEV = SE->getUnknown(Base); 429 430 // Always emit the immediate into the same block as the user. 431 NewValSCEV = SE->getAddExpr(NewValSCEV, Imm); 432 433 return Rewriter.expandCodeFor(NewValSCEV, Ty, IP); 434} 435 436 437// Once we rewrite the code to insert the new IVs we want, update the 438// operands of Inst to use the new expression 'NewBase', with 'Imm' added 439// to it. NewBasePt is the last instruction which contributes to the 440// value of NewBase in the case that it's a diffferent instruction from 441// the PHI that NewBase is computed from, or null otherwise. 442// 443void BasedUser::RewriteInstructionToUseNewBase(const SCEV *const &NewBase, 444 Instruction *NewBasePt, 445 SCEVExpander &Rewriter, Loop *L, Pass *P, 446 LoopInfo &LI, 447 SmallVectorImpl<WeakVH> &DeadInsts) { 448 if (!isa<PHINode>(Inst)) { 449 // By default, insert code at the user instruction. 450 BasicBlock::iterator InsertPt = Inst; 451 452 // However, if the Operand is itself an instruction, the (potentially 453 // complex) inserted code may be shared by many users. Because of this, we 454 // want to emit code for the computation of the operand right before its old 455 // computation. This is usually safe, because we obviously used to use the 456 // computation when it was computed in its current block. However, in some 457 // cases (e.g. use of a post-incremented induction variable) the NewBase 458 // value will be pinned to live somewhere after the original computation. 459 // In this case, we have to back off. 460 // 461 // If this is a use outside the loop (which means after, since it is based 462 // on a loop indvar) we use the post-incremented value, so that we don't 463 // artificially make the preinc value live out the bottom of the loop. 464 if (!isUseOfPostIncrementedValue && L->contains(Inst->getParent())) { 465 if (NewBasePt && isa<PHINode>(OperandValToReplace)) { 466 InsertPt = NewBasePt; 467 ++InsertPt; 468 } else if (Instruction *OpInst 469 = dyn_cast<Instruction>(OperandValToReplace)) { 470 InsertPt = OpInst; 471 while (isa<PHINode>(InsertPt)) ++InsertPt; 472 } 473 } 474 Value *NewVal = InsertCodeForBaseAtPosition(NewBase, 475 OperandValToReplace->getType(), 476 Rewriter, InsertPt, L, LI); 477 // Replace the use of the operand Value with the new Phi we just created. 478 Inst->replaceUsesOfWith(OperandValToReplace, NewVal); 479 480 DEBUG(errs() << " Replacing with "); 481 DEBUG(WriteAsOperand(errs(), NewVal, /*PrintType=*/false)); 482 DEBUG(errs() << ", which has value " << *NewBase << " plus IMM " 483 << *Imm << "\n"); 484 return; 485 } 486 487 // PHI nodes are more complex. We have to insert one copy of the NewBase+Imm 488 // expression into each operand block that uses it. Note that PHI nodes can 489 // have multiple entries for the same predecessor. We use a map to make sure 490 // that a PHI node only has a single Value* for each predecessor (which also 491 // prevents us from inserting duplicate code in some blocks). 492 DenseMap<BasicBlock*, Value*> InsertedCode; 493 PHINode *PN = cast<PHINode>(Inst); 494 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 495 if (PN->getIncomingValue(i) == OperandValToReplace) { 496 // If the original expression is outside the loop, put the replacement 497 // code in the same place as the original expression, 498 // which need not be an immediate predecessor of this PHI. This way we 499 // need only one copy of it even if it is referenced multiple times in 500 // the PHI. We don't do this when the original expression is inside the 501 // loop because multiple copies sometimes do useful sinking of code in 502 // that case(?). 503 Instruction *OldLoc = dyn_cast<Instruction>(OperandValToReplace); 504 BasicBlock *PHIPred = PN->getIncomingBlock(i); 505 if (L->contains(OldLoc->getParent())) { 506 // If this is a critical edge, split the edge so that we do not insert 507 // the code on all predecessor/successor paths. We do this unless this 508 // is the canonical backedge for this loop, as this can make some 509 // inserted code be in an illegal position. 510 if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 && 511 !isa<IndirectBrInst>(PHIPred->getTerminator()) && 512 (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) { 513 514 // First step, split the critical edge. 515 BasicBlock *NewBB = SplitCriticalEdge(PHIPred, PN->getParent(), 516 P, false); 517 518 // Next step: move the basic block. In particular, if the PHI node 519 // is outside of the loop, and PredTI is in the loop, we want to 520 // move the block to be immediately before the PHI block, not 521 // immediately after PredTI. 522 if (L->contains(PHIPred) && !L->contains(PN->getParent())) 523 NewBB->moveBefore(PN->getParent()); 524 525 // Splitting the edge can reduce the number of PHI entries we have. 526 e = PN->getNumIncomingValues(); 527 PHIPred = NewBB; 528 i = PN->getBasicBlockIndex(PHIPred); 529 } 530 } 531 Value *&Code = InsertedCode[PHIPred]; 532 if (!Code) { 533 // Insert the code into the end of the predecessor block. 534 Instruction *InsertPt = (L->contains(OldLoc->getParent())) ? 535 PHIPred->getTerminator() : 536 OldLoc->getParent()->getTerminator(); 537 Code = InsertCodeForBaseAtPosition(NewBase, PN->getType(), 538 Rewriter, InsertPt, L, LI); 539 540 DEBUG(errs() << " Changing PHI use to "); 541 DEBUG(WriteAsOperand(errs(), Code, /*PrintType=*/false)); 542 DEBUG(errs() << ", which has value " << *NewBase << " plus IMM " 543 << *Imm << "\n"); 544 } 545 546 // Replace the use of the operand Value with the new Phi we just created. 547 PN->setIncomingValue(i, Code); 548 Rewriter.clear(); 549 } 550 } 551 552 // PHI node might have become a constant value after SplitCriticalEdge. 553 DeadInsts.push_back(Inst); 554} 555 556 557/// fitsInAddressMode - Return true if V can be subsumed within an addressing 558/// mode, and does not need to be put in a register first. 559static bool fitsInAddressMode(const SCEV *const &V, const Type *AccessTy, 560 const TargetLowering *TLI, bool HasBaseReg) { 561 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) { 562 int64_t VC = SC->getValue()->getSExtValue(); 563 if (TLI) { 564 TargetLowering::AddrMode AM; 565 AM.BaseOffs = VC; 566 AM.HasBaseReg = HasBaseReg; 567 return TLI->isLegalAddressingMode(AM, AccessTy); 568 } else { 569 // Defaults to PPC. PPC allows a sign-extended 16-bit immediate field. 570 return (VC > -(1 << 16) && VC < (1 << 16)-1); 571 } 572 } 573 574 if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) 575 if (GlobalValue *GV = dyn_cast<GlobalValue>(SU->getValue())) { 576 if (TLI) { 577 TargetLowering::AddrMode AM; 578 AM.BaseGV = GV; 579 AM.HasBaseReg = HasBaseReg; 580 return TLI->isLegalAddressingMode(AM, AccessTy); 581 } else { 582 // Default: assume global addresses are not legal. 583 } 584 } 585 586 return false; 587} 588 589/// MoveLoopVariantsToImmediateField - Move any subexpressions from Val that are 590/// loop varying to the Imm operand. 591static void MoveLoopVariantsToImmediateField(const SCEV *&Val, const SCEV *&Imm, 592 Loop *L, ScalarEvolution *SE) { 593 if (Val->isLoopInvariant(L)) return; // Nothing to do. 594 595 if (const SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) { 596 SmallVector<const SCEV *, 4> NewOps; 597 NewOps.reserve(SAE->getNumOperands()); 598 599 for (unsigned i = 0; i != SAE->getNumOperands(); ++i) 600 if (!SAE->getOperand(i)->isLoopInvariant(L)) { 601 // If this is a loop-variant expression, it must stay in the immediate 602 // field of the expression. 603 Imm = SE->getAddExpr(Imm, SAE->getOperand(i)); 604 } else { 605 NewOps.push_back(SAE->getOperand(i)); 606 } 607 608 if (NewOps.empty()) 609 Val = SE->getIntegerSCEV(0, Val->getType()); 610 else 611 Val = SE->getAddExpr(NewOps); 612 } else if (const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) { 613 // Try to pull immediates out of the start value of nested addrec's. 614 const SCEV *Start = SARE->getStart(); 615 MoveLoopVariantsToImmediateField(Start, Imm, L, SE); 616 617 SmallVector<const SCEV *, 4> Ops(SARE->op_begin(), SARE->op_end()); 618 Ops[0] = Start; 619 Val = SE->getAddRecExpr(Ops, SARE->getLoop()); 620 } else { 621 // Otherwise, all of Val is variant, move the whole thing over. 622 Imm = SE->getAddExpr(Imm, Val); 623 Val = SE->getIntegerSCEV(0, Val->getType()); 624 } 625} 626 627 628/// MoveImmediateValues - Look at Val, and pull out any additions of constants 629/// that can fit into the immediate field of instructions in the target. 630/// Accumulate these immediate values into the Imm value. 631static void MoveImmediateValues(const TargetLowering *TLI, 632 const Type *AccessTy, 633 const SCEV *&Val, const SCEV *&Imm, 634 bool isAddress, Loop *L, 635 ScalarEvolution *SE) { 636 if (const SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) { 637 SmallVector<const SCEV *, 4> NewOps; 638 NewOps.reserve(SAE->getNumOperands()); 639 640 for (unsigned i = 0; i != SAE->getNumOperands(); ++i) { 641 const SCEV *NewOp = SAE->getOperand(i); 642 MoveImmediateValues(TLI, AccessTy, NewOp, Imm, isAddress, L, SE); 643 644 if (!NewOp->isLoopInvariant(L)) { 645 // If this is a loop-variant expression, it must stay in the immediate 646 // field of the expression. 647 Imm = SE->getAddExpr(Imm, NewOp); 648 } else { 649 NewOps.push_back(NewOp); 650 } 651 } 652 653 if (NewOps.empty()) 654 Val = SE->getIntegerSCEV(0, Val->getType()); 655 else 656 Val = SE->getAddExpr(NewOps); 657 return; 658 } else if (const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) { 659 // Try to pull immediates out of the start value of nested addrec's. 660 const SCEV *Start = SARE->getStart(); 661 MoveImmediateValues(TLI, AccessTy, Start, Imm, isAddress, L, SE); 662 663 if (Start != SARE->getStart()) { 664 SmallVector<const SCEV *, 4> Ops(SARE->op_begin(), SARE->op_end()); 665 Ops[0] = Start; 666 Val = SE->getAddRecExpr(Ops, SARE->getLoop()); 667 } 668 return; 669 } else if (const SCEVMulExpr *SME = dyn_cast<SCEVMulExpr>(Val)) { 670 // Transform "8 * (4 + v)" -> "32 + 8*V" if "32" fits in the immed field. 671 if (isAddress && 672 fitsInAddressMode(SME->getOperand(0), AccessTy, TLI, false) && 673 SME->getNumOperands() == 2 && SME->isLoopInvariant(L)) { 674 675 const SCEV *SubImm = SE->getIntegerSCEV(0, Val->getType()); 676 const SCEV *NewOp = SME->getOperand(1); 677 MoveImmediateValues(TLI, AccessTy, NewOp, SubImm, isAddress, L, SE); 678 679 // If we extracted something out of the subexpressions, see if we can 680 // simplify this! 681 if (NewOp != SME->getOperand(1)) { 682 // Scale SubImm up by "8". If the result is a target constant, we are 683 // good. 684 SubImm = SE->getMulExpr(SubImm, SME->getOperand(0)); 685 if (fitsInAddressMode(SubImm, AccessTy, TLI, false)) { 686 // Accumulate the immediate. 687 Imm = SE->getAddExpr(Imm, SubImm); 688 689 // Update what is left of 'Val'. 690 Val = SE->getMulExpr(SME->getOperand(0), NewOp); 691 return; 692 } 693 } 694 } 695 } 696 697 // Loop-variant expressions must stay in the immediate field of the 698 // expression. 699 if ((isAddress && fitsInAddressMode(Val, AccessTy, TLI, false)) || 700 !Val->isLoopInvariant(L)) { 701 Imm = SE->getAddExpr(Imm, Val); 702 Val = SE->getIntegerSCEV(0, Val->getType()); 703 return; 704 } 705 706 // Otherwise, no immediates to move. 707} 708 709static void MoveImmediateValues(const TargetLowering *TLI, 710 Instruction *User, 711 const SCEV *&Val, const SCEV *&Imm, 712 bool isAddress, Loop *L, 713 ScalarEvolution *SE) { 714 const Type *AccessTy = getAccessType(User); 715 MoveImmediateValues(TLI, AccessTy, Val, Imm, isAddress, L, SE); 716} 717 718/// SeparateSubExprs - Decompose Expr into all of the subexpressions that are 719/// added together. This is used to reassociate common addition subexprs 720/// together for maximal sharing when rewriting bases. 721static void SeparateSubExprs(SmallVector<const SCEV *, 16> &SubExprs, 722 const SCEV *Expr, 723 ScalarEvolution *SE) { 724 if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(Expr)) { 725 for (unsigned j = 0, e = AE->getNumOperands(); j != e; ++j) 726 SeparateSubExprs(SubExprs, AE->getOperand(j), SE); 727 } else if (const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Expr)) { 728 const SCEV *Zero = SE->getIntegerSCEV(0, Expr->getType()); 729 if (SARE->getOperand(0) == Zero) { 730 SubExprs.push_back(Expr); 731 } else { 732 // Compute the addrec with zero as its base. 733 SmallVector<const SCEV *, 4> Ops(SARE->op_begin(), SARE->op_end()); 734 Ops[0] = Zero; // Start with zero base. 735 SubExprs.push_back(SE->getAddRecExpr(Ops, SARE->getLoop())); 736 737 738 SeparateSubExprs(SubExprs, SARE->getOperand(0), SE); 739 } 740 } else if (!Expr->isZero()) { 741 // Do not add zero. 742 SubExprs.push_back(Expr); 743 } 744} 745 746// This is logically local to the following function, but C++ says we have 747// to make it file scope. 748struct SubExprUseData { unsigned Count; bool notAllUsesAreFree; }; 749 750/// RemoveCommonExpressionsFromUseBases - Look through all of the Bases of all 751/// the Uses, removing any common subexpressions, except that if all such 752/// subexpressions can be folded into an addressing mode for all uses inside 753/// the loop (this case is referred to as "free" in comments herein) we do 754/// not remove anything. This looks for things like (a+b+c) and 755/// (a+c+d) and computes the common (a+c) subexpression. The common expression 756/// is *removed* from the Bases and returned. 757static const SCEV * 758RemoveCommonExpressionsFromUseBases(std::vector<BasedUser> &Uses, 759 ScalarEvolution *SE, Loop *L, 760 const TargetLowering *TLI) { 761 unsigned NumUses = Uses.size(); 762 763 // Only one use? This is a very common case, so we handle it specially and 764 // cheaply. 765 const SCEV *Zero = SE->getIntegerSCEV(0, Uses[0].Base->getType()); 766 const SCEV *Result = Zero; 767 const SCEV *FreeResult = Zero; 768 if (NumUses == 1) { 769 // If the use is inside the loop, use its base, regardless of what it is: 770 // it is clearly shared across all the IV's. If the use is outside the loop 771 // (which means after it) we don't want to factor anything *into* the loop, 772 // so just use 0 as the base. 773 if (L->contains(Uses[0].Inst->getParent())) 774 std::swap(Result, Uses[0].Base); 775 return Result; 776 } 777 778 // To find common subexpressions, count how many of Uses use each expression. 779 // If any subexpressions are used Uses.size() times, they are common. 780 // Also track whether all uses of each expression can be moved into an 781 // an addressing mode "for free"; such expressions are left within the loop. 782 // struct SubExprUseData { unsigned Count; bool notAllUsesAreFree; }; 783 std::map<const SCEV *, SubExprUseData> SubExpressionUseData; 784 785 // UniqueSubExprs - Keep track of all of the subexpressions we see in the 786 // order we see them. 787 SmallVector<const SCEV *, 16> UniqueSubExprs; 788 789 SmallVector<const SCEV *, 16> SubExprs; 790 unsigned NumUsesInsideLoop = 0; 791 for (unsigned i = 0; i != NumUses; ++i) { 792 // If the user is outside the loop, just ignore it for base computation. 793 // Since the user is outside the loop, it must be *after* the loop (if it 794 // were before, it could not be based on the loop IV). We don't want users 795 // after the loop to affect base computation of values *inside* the loop, 796 // because we can always add their offsets to the result IV after the loop 797 // is done, ensuring we get good code inside the loop. 798 if (!L->contains(Uses[i].Inst->getParent())) 799 continue; 800 NumUsesInsideLoop++; 801 802 // If the base is zero (which is common), return zero now, there are no 803 // CSEs we can find. 804 if (Uses[i].Base == Zero) return Zero; 805 806 // If this use is as an address we may be able to put CSEs in the addressing 807 // mode rather than hoisting them. 808 bool isAddrUse = isAddressUse(Uses[i].Inst, Uses[i].OperandValToReplace); 809 // We may need the AccessTy below, but only when isAddrUse, so compute it 810 // only in that case. 811 const Type *AccessTy = 0; 812 if (isAddrUse) 813 AccessTy = getAccessType(Uses[i].Inst); 814 815 // Split the expression into subexprs. 816 SeparateSubExprs(SubExprs, Uses[i].Base, SE); 817 // Add one to SubExpressionUseData.Count for each subexpr present, and 818 // if the subexpr is not a valid immediate within an addressing mode use, 819 // set SubExpressionUseData.notAllUsesAreFree. We definitely want to 820 // hoist these out of the loop (if they are common to all uses). 821 for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) { 822 if (++SubExpressionUseData[SubExprs[j]].Count == 1) 823 UniqueSubExprs.push_back(SubExprs[j]); 824 if (!isAddrUse || !fitsInAddressMode(SubExprs[j], AccessTy, TLI, false)) 825 SubExpressionUseData[SubExprs[j]].notAllUsesAreFree = true; 826 } 827 SubExprs.clear(); 828 } 829 830 // Now that we know how many times each is used, build Result. Iterate over 831 // UniqueSubexprs so that we have a stable ordering. 832 for (unsigned i = 0, e = UniqueSubExprs.size(); i != e; ++i) { 833 std::map<const SCEV *, SubExprUseData>::iterator I = 834 SubExpressionUseData.find(UniqueSubExprs[i]); 835 assert(I != SubExpressionUseData.end() && "Entry not found?"); 836 if (I->second.Count == NumUsesInsideLoop) { // Found CSE! 837 if (I->second.notAllUsesAreFree) 838 Result = SE->getAddExpr(Result, I->first); 839 else 840 FreeResult = SE->getAddExpr(FreeResult, I->first); 841 } else 842 // Remove non-cse's from SubExpressionUseData. 843 SubExpressionUseData.erase(I); 844 } 845 846 if (FreeResult != Zero) { 847 // We have some subexpressions that can be subsumed into addressing 848 // modes in every use inside the loop. However, it's possible that 849 // there are so many of them that the combined FreeResult cannot 850 // be subsumed, or that the target cannot handle both a FreeResult 851 // and a Result in the same instruction (for example because it would 852 // require too many registers). Check this. 853 for (unsigned i=0; i<NumUses; ++i) { 854 if (!L->contains(Uses[i].Inst->getParent())) 855 continue; 856 // We know this is an addressing mode use; if there are any uses that 857 // are not, FreeResult would be Zero. 858 const Type *AccessTy = getAccessType(Uses[i].Inst); 859 if (!fitsInAddressMode(FreeResult, AccessTy, TLI, Result!=Zero)) { 860 // FIXME: could split up FreeResult into pieces here, some hoisted 861 // and some not. There is no obvious advantage to this. 862 Result = SE->getAddExpr(Result, FreeResult); 863 FreeResult = Zero; 864 break; 865 } 866 } 867 } 868 869 // If we found no CSE's, return now. 870 if (Result == Zero) return Result; 871 872 // If we still have a FreeResult, remove its subexpressions from 873 // SubExpressionUseData. This means they will remain in the use Bases. 874 if (FreeResult != Zero) { 875 SeparateSubExprs(SubExprs, FreeResult, SE); 876 for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) { 877 std::map<const SCEV *, SubExprUseData>::iterator I = 878 SubExpressionUseData.find(SubExprs[j]); 879 SubExpressionUseData.erase(I); 880 } 881 SubExprs.clear(); 882 } 883 884 // Otherwise, remove all of the CSE's we found from each of the base values. 885 for (unsigned i = 0; i != NumUses; ++i) { 886 // Uses outside the loop don't necessarily include the common base, but 887 // the final IV value coming into those uses does. Instead of trying to 888 // remove the pieces of the common base, which might not be there, 889 // subtract off the base to compensate for this. 890 if (!L->contains(Uses[i].Inst->getParent())) { 891 Uses[i].Base = SE->getMinusSCEV(Uses[i].Base, Result); 892 continue; 893 } 894 895 // Split the expression into subexprs. 896 SeparateSubExprs(SubExprs, Uses[i].Base, SE); 897 898 // Remove any common subexpressions. 899 for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) 900 if (SubExpressionUseData.count(SubExprs[j])) { 901 SubExprs.erase(SubExprs.begin()+j); 902 --j; --e; 903 } 904 905 // Finally, add the non-shared expressions together. 906 if (SubExprs.empty()) 907 Uses[i].Base = Zero; 908 else 909 Uses[i].Base = SE->getAddExpr(SubExprs); 910 SubExprs.clear(); 911 } 912 913 return Result; 914} 915 916/// ValidScale - Check whether the given Scale is valid for all loads and 917/// stores in UsersToProcess. 918/// 919bool LoopStrengthReduce::ValidScale(bool HasBaseReg, int64_t Scale, 920 const std::vector<BasedUser>& UsersToProcess) { 921 if (!TLI) 922 return true; 923 924 for (unsigned i = 0, e = UsersToProcess.size(); i!=e; ++i) { 925 // If this is a load or other access, pass the type of the access in. 926 const Type *AccessTy = 927 Type::getVoidTy(UsersToProcess[i].Inst->getContext()); 928 if (isAddressUse(UsersToProcess[i].Inst, 929 UsersToProcess[i].OperandValToReplace)) 930 AccessTy = getAccessType(UsersToProcess[i].Inst); 931 else if (isa<PHINode>(UsersToProcess[i].Inst)) 932 continue; 933 934 TargetLowering::AddrMode AM; 935 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm)) 936 AM.BaseOffs = SC->getValue()->getSExtValue(); 937 AM.HasBaseReg = HasBaseReg || !UsersToProcess[i].Base->isZero(); 938 AM.Scale = Scale; 939 940 // If load[imm+r*scale] is illegal, bail out. 941 if (!TLI->isLegalAddressingMode(AM, AccessTy)) 942 return false; 943 } 944 return true; 945} 946 947/// ValidOffset - Check whether the given Offset is valid for all loads and 948/// stores in UsersToProcess. 949/// 950bool LoopStrengthReduce::ValidOffset(bool HasBaseReg, 951 int64_t Offset, 952 int64_t Scale, 953 const std::vector<BasedUser>& UsersToProcess) { 954 if (!TLI) 955 return true; 956 957 for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) { 958 // If this is a load or other access, pass the type of the access in. 959 const Type *AccessTy = 960 Type::getVoidTy(UsersToProcess[i].Inst->getContext()); 961 if (isAddressUse(UsersToProcess[i].Inst, 962 UsersToProcess[i].OperandValToReplace)) 963 AccessTy = getAccessType(UsersToProcess[i].Inst); 964 else if (isa<PHINode>(UsersToProcess[i].Inst)) 965 continue; 966 967 TargetLowering::AddrMode AM; 968 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm)) 969 AM.BaseOffs = SC->getValue()->getSExtValue(); 970 AM.BaseOffs = (uint64_t)AM.BaseOffs + (uint64_t)Offset; 971 AM.HasBaseReg = HasBaseReg || !UsersToProcess[i].Base->isZero(); 972 AM.Scale = Scale; 973 974 // If load[imm+r*scale] is illegal, bail out. 975 if (!TLI->isLegalAddressingMode(AM, AccessTy)) 976 return false; 977 } 978 return true; 979} 980 981/// RequiresTypeConversion - Returns true if converting Ty1 to Ty2 is not 982/// a nop. 983bool LoopStrengthReduce::RequiresTypeConversion(const Type *Ty1, 984 const Type *Ty2) { 985 if (Ty1 == Ty2) 986 return false; 987 Ty1 = SE->getEffectiveSCEVType(Ty1); 988 Ty2 = SE->getEffectiveSCEVType(Ty2); 989 if (Ty1 == Ty2) 990 return false; 991 if (Ty1->canLosslesslyBitCastTo(Ty2)) 992 return false; 993 if (TLI && TLI->isTruncateFree(Ty1, Ty2)) 994 return false; 995 return true; 996} 997 998/// CheckForIVReuse - Returns the multiple if the stride is the multiple 999/// of a previous stride and it is a legal value for the target addressing 1000/// mode scale component and optional base reg. This allows the users of 1001/// this stride to be rewritten as prev iv * factor. It returns 0 if no 1002/// reuse is possible. Factors can be negative on same targets, e.g. ARM. 1003/// 1004/// If all uses are outside the loop, we don't require that all multiplies 1005/// be folded into the addressing mode, nor even that the factor be constant; 1006/// a multiply (executed once) outside the loop is better than another IV 1007/// within. Well, usually. 1008const SCEV *LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg, 1009 bool AllUsesAreAddresses, 1010 bool AllUsesAreOutsideLoop, 1011 const SCEV *const &Stride, 1012 IVExpr &IV, const Type *Ty, 1013 const std::vector<BasedUser>& UsersToProcess) { 1014 if (StrideNoReuse.count(Stride)) 1015 return SE->getIntegerSCEV(0, Stride->getType()); 1016 1017 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) { 1018 int64_t SInt = SC->getValue()->getSExtValue(); 1019 for (unsigned NewStride = 0, e = IU->StrideOrder.size(); 1020 NewStride != e; ++NewStride) { 1021 std::map<const SCEV *, IVsOfOneStride>::iterator SI = 1022 IVsByStride.find(IU->StrideOrder[NewStride]); 1023 if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first) || 1024 StrideNoReuse.count(SI->first)) 1025 continue; 1026 // The other stride has no uses, don't reuse it. 1027 std::map<const SCEV *, IVUsersOfOneStride *>::iterator UI = 1028 IU->IVUsesByStride.find(IU->StrideOrder[NewStride]); 1029 if (UI->second->Users.empty()) 1030 continue; 1031 int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 1032 if (SI->first != Stride && 1033 (unsigned(abs64(SInt)) < SSInt || (SInt % SSInt) != 0)) 1034 continue; 1035 int64_t Scale = SInt / SSInt; 1036 // Check that this stride is valid for all the types used for loads and 1037 // stores; if it can be used for some and not others, we might as well use 1038 // the original stride everywhere, since we have to create the IV for it 1039 // anyway. If the scale is 1, then we don't need to worry about folding 1040 // multiplications. 1041 if (Scale == 1 || 1042 (AllUsesAreAddresses && 1043 ValidScale(HasBaseReg, Scale, UsersToProcess))) { 1044 // Prefer to reuse an IV with a base of zero. 1045 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 1046 IE = SI->second.IVs.end(); II != IE; ++II) 1047 // Only reuse previous IV if it would not require a type conversion 1048 // and if the base difference can be folded. 1049 if (II->Base->isZero() && 1050 !RequiresTypeConversion(II->Base->getType(), Ty)) { 1051 IV = *II; 1052 return SE->getIntegerSCEV(Scale, Stride->getType()); 1053 } 1054 // Otherwise, settle for an IV with a foldable base. 1055 if (AllUsesAreAddresses) 1056 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 1057 IE = SI->second.IVs.end(); II != IE; ++II) 1058 // Only reuse previous IV if it would not require a type conversion 1059 // and if the base difference can be folded. 1060 if (SE->getEffectiveSCEVType(II->Base->getType()) == 1061 SE->getEffectiveSCEVType(Ty) && 1062 isa<SCEVConstant>(II->Base)) { 1063 int64_t Base = 1064 cast<SCEVConstant>(II->Base)->getValue()->getSExtValue(); 1065 if (Base > INT32_MIN && Base <= INT32_MAX && 1066 ValidOffset(HasBaseReg, -Base * Scale, 1067 Scale, UsersToProcess)) { 1068 IV = *II; 1069 return SE->getIntegerSCEV(Scale, Stride->getType()); 1070 } 1071 } 1072 } 1073 } 1074 } else if (AllUsesAreOutsideLoop) { 1075 // Accept nonconstant strides here; it is really really right to substitute 1076 // an existing IV if we can. 1077 for (unsigned NewStride = 0, e = IU->StrideOrder.size(); 1078 NewStride != e; ++NewStride) { 1079 std::map<const SCEV *, IVsOfOneStride>::iterator SI = 1080 IVsByStride.find(IU->StrideOrder[NewStride]); 1081 if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first)) 1082 continue; 1083 int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 1084 if (SI->first != Stride && SSInt != 1) 1085 continue; 1086 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 1087 IE = SI->second.IVs.end(); II != IE; ++II) 1088 // Accept nonzero base here. 1089 // Only reuse previous IV if it would not require a type conversion. 1090 if (!RequiresTypeConversion(II->Base->getType(), Ty)) { 1091 IV = *II; 1092 return Stride; 1093 } 1094 } 1095 // Special case, old IV is -1*x and this one is x. Can treat this one as 1096 // -1*old. 1097 for (unsigned NewStride = 0, e = IU->StrideOrder.size(); 1098 NewStride != e; ++NewStride) { 1099 std::map<const SCEV *, IVsOfOneStride>::iterator SI = 1100 IVsByStride.find(IU->StrideOrder[NewStride]); 1101 if (SI == IVsByStride.end()) 1102 continue; 1103 if (const SCEVMulExpr *ME = dyn_cast<SCEVMulExpr>(SI->first)) 1104 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(ME->getOperand(0))) 1105 if (Stride == ME->getOperand(1) && 1106 SC->getValue()->getSExtValue() == -1LL) 1107 for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(), 1108 IE = SI->second.IVs.end(); II != IE; ++II) 1109 // Accept nonzero base here. 1110 // Only reuse previous IV if it would not require type conversion. 1111 if (!RequiresTypeConversion(II->Base->getType(), Ty)) { 1112 IV = *II; 1113 return SE->getIntegerSCEV(-1LL, Stride->getType()); 1114 } 1115 } 1116 } 1117 return SE->getIntegerSCEV(0, Stride->getType()); 1118} 1119 1120/// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that 1121/// returns true if Val's isUseOfPostIncrementedValue is true. 1122static bool PartitionByIsUseOfPostIncrementedValue(const BasedUser &Val) { 1123 return Val.isUseOfPostIncrementedValue; 1124} 1125 1126/// isNonConstantNegative - Return true if the specified scev is negated, but 1127/// not a constant. 1128static bool isNonConstantNegative(const SCEV *const &Expr) { 1129 const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Expr); 1130 if (!Mul) return false; 1131 1132 // If there is a constant factor, it will be first. 1133 const SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0)); 1134 if (!SC) return false; 1135 1136 // Return true if the value is negative, this matches things like (-42 * V). 1137 return SC->getValue()->getValue().isNegative(); 1138} 1139 1140/// CollectIVUsers - Transform our list of users and offsets to a bit more 1141/// complex table. In this new vector, each 'BasedUser' contains 'Base', the 1142/// base of the strided accesses, as well as the old information from Uses. We 1143/// progressively move information from the Base field to the Imm field, until 1144/// we eventually have the full access expression to rewrite the use. 1145const SCEV *LoopStrengthReduce::CollectIVUsers(const SCEV *const &Stride, 1146 IVUsersOfOneStride &Uses, 1147 Loop *L, 1148 bool &AllUsesAreAddresses, 1149 bool &AllUsesAreOutsideLoop, 1150 std::vector<BasedUser> &UsersToProcess) { 1151 // FIXME: Generalize to non-affine IV's. 1152 if (!Stride->isLoopInvariant(L)) 1153 return SE->getIntegerSCEV(0, Stride->getType()); 1154 1155 UsersToProcess.reserve(Uses.Users.size()); 1156 for (ilist<IVStrideUse>::iterator I = Uses.Users.begin(), 1157 E = Uses.Users.end(); I != E; ++I) { 1158 UsersToProcess.push_back(BasedUser(*I, SE)); 1159 1160 // Move any loop variant operands from the offset field to the immediate 1161 // field of the use, so that we don't try to use something before it is 1162 // computed. 1163 MoveLoopVariantsToImmediateField(UsersToProcess.back().Base, 1164 UsersToProcess.back().Imm, L, SE); 1165 assert(UsersToProcess.back().Base->isLoopInvariant(L) && 1166 "Base value is not loop invariant!"); 1167 } 1168 1169 // We now have a whole bunch of uses of like-strided induction variables, but 1170 // they might all have different bases. We want to emit one PHI node for this 1171 // stride which we fold as many common expressions (between the IVs) into as 1172 // possible. Start by identifying the common expressions in the base values 1173 // for the strides (e.g. if we have "A+C+B" and "A+B+D" as our bases, find 1174 // "A+B"), emit it to the preheader, then remove the expression from the 1175 // UsersToProcess base values. 1176 const SCEV *CommonExprs = 1177 RemoveCommonExpressionsFromUseBases(UsersToProcess, SE, L, TLI); 1178 1179 // Next, figure out what we can represent in the immediate fields of 1180 // instructions. If we can represent anything there, move it to the imm 1181 // fields of the BasedUsers. We do this so that it increases the commonality 1182 // of the remaining uses. 1183 unsigned NumPHI = 0; 1184 bool HasAddress = false; 1185 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) { 1186 // If the user is not in the current loop, this means it is using the exit 1187 // value of the IV. Do not put anything in the base, make sure it's all in 1188 // the immediate field to allow as much factoring as possible. 1189 if (!L->contains(UsersToProcess[i].Inst->getParent())) { 1190 UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm, 1191 UsersToProcess[i].Base); 1192 UsersToProcess[i].Base = 1193 SE->getIntegerSCEV(0, UsersToProcess[i].Base->getType()); 1194 } else { 1195 // Not all uses are outside the loop. 1196 AllUsesAreOutsideLoop = false; 1197 1198 // Addressing modes can be folded into loads and stores. Be careful that 1199 // the store is through the expression, not of the expression though. 1200 bool isPHI = false; 1201 bool isAddress = isAddressUse(UsersToProcess[i].Inst, 1202 UsersToProcess[i].OperandValToReplace); 1203 if (isa<PHINode>(UsersToProcess[i].Inst)) { 1204 isPHI = true; 1205 ++NumPHI; 1206 } 1207 1208 if (isAddress) 1209 HasAddress = true; 1210 1211 // If this use isn't an address, then not all uses are addresses. 1212 if (!isAddress && !isPHI) 1213 AllUsesAreAddresses = false; 1214 1215 MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base, 1216 UsersToProcess[i].Imm, isAddress, L, SE); 1217 } 1218 } 1219 1220 // If one of the use is a PHI node and all other uses are addresses, still 1221 // allow iv reuse. Essentially we are trading one constant multiplication 1222 // for one fewer iv. 1223 if (NumPHI > 1) 1224 AllUsesAreAddresses = false; 1225 1226 // There are no in-loop address uses. 1227 if (AllUsesAreAddresses && (!HasAddress && !AllUsesAreOutsideLoop)) 1228 AllUsesAreAddresses = false; 1229 1230 return CommonExprs; 1231} 1232 1233/// ShouldUseFullStrengthReductionMode - Test whether full strength-reduction 1234/// is valid and profitable for the given set of users of a stride. In 1235/// full strength-reduction mode, all addresses at the current stride are 1236/// strength-reduced all the way down to pointer arithmetic. 1237/// 1238bool LoopStrengthReduce::ShouldUseFullStrengthReductionMode( 1239 const std::vector<BasedUser> &UsersToProcess, 1240 const Loop *L, 1241 bool AllUsesAreAddresses, 1242 const SCEV *Stride) { 1243 if (!EnableFullLSRMode) 1244 return false; 1245 1246 // The heuristics below aim to avoid increasing register pressure, but 1247 // fully strength-reducing all the addresses increases the number of 1248 // add instructions, so don't do this when optimizing for size. 1249 // TODO: If the loop is large, the savings due to simpler addresses 1250 // may oughtweight the costs of the extra increment instructions. 1251 if (L->getHeader()->getParent()->hasFnAttr(Attribute::OptimizeForSize)) 1252 return false; 1253 1254 // TODO: For now, don't do full strength reduction if there could 1255 // potentially be greater-stride multiples of the current stride 1256 // which could reuse the current stride IV. 1257 if (IU->StrideOrder.back() != Stride) 1258 return false; 1259 1260 // Iterate through the uses to find conditions that automatically rule out 1261 // full-lsr mode. 1262 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ) { 1263 const SCEV *Base = UsersToProcess[i].Base; 1264 const SCEV *Imm = UsersToProcess[i].Imm; 1265 // If any users have a loop-variant component, they can't be fully 1266 // strength-reduced. 1267 if (Imm && !Imm->isLoopInvariant(L)) 1268 return false; 1269 // If there are to users with the same base and the difference between 1270 // the two Imm values can't be folded into the address, full 1271 // strength reduction would increase register pressure. 1272 do { 1273 const SCEV *CurImm = UsersToProcess[i].Imm; 1274 if ((CurImm || Imm) && CurImm != Imm) { 1275 if (!CurImm) CurImm = SE->getIntegerSCEV(0, Stride->getType()); 1276 if (!Imm) Imm = SE->getIntegerSCEV(0, Stride->getType()); 1277 const Instruction *Inst = UsersToProcess[i].Inst; 1278 const Type *AccessTy = getAccessType(Inst); 1279 const SCEV *Diff = SE->getMinusSCEV(UsersToProcess[i].Imm, Imm); 1280 if (!Diff->isZero() && 1281 (!AllUsesAreAddresses || 1282 !fitsInAddressMode(Diff, AccessTy, TLI, /*HasBaseReg=*/true))) 1283 return false; 1284 } 1285 } while (++i != e && Base == UsersToProcess[i].Base); 1286 } 1287 1288 // If there's exactly one user in this stride, fully strength-reducing it 1289 // won't increase register pressure. If it's starting from a non-zero base, 1290 // it'll be simpler this way. 1291 if (UsersToProcess.size() == 1 && !UsersToProcess[0].Base->isZero()) 1292 return true; 1293 1294 // Otherwise, if there are any users in this stride that don't require 1295 // a register for their base, full strength-reduction will increase 1296 // register pressure. 1297 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 1298 if (UsersToProcess[i].Base->isZero()) 1299 return false; 1300 1301 // Otherwise, go for it. 1302 return true; 1303} 1304 1305/// InsertAffinePhi Create and insert a PHI node for an induction variable 1306/// with the specified start and step values in the specified loop. 1307/// 1308/// If NegateStride is true, the stride should be negated by using a 1309/// subtract instead of an add. 1310/// 1311/// Return the created phi node. 1312/// 1313static PHINode *InsertAffinePhi(const SCEV *Start, const SCEV *Step, 1314 Instruction *IVIncInsertPt, 1315 const Loop *L, 1316 SCEVExpander &Rewriter) { 1317 assert(Start->isLoopInvariant(L) && "New PHI start is not loop invariant!"); 1318 assert(Step->isLoopInvariant(L) && "New PHI stride is not loop invariant!"); 1319 1320 BasicBlock *Header = L->getHeader(); 1321 BasicBlock *Preheader = L->getLoopPreheader(); 1322 BasicBlock *LatchBlock = L->getLoopLatch(); 1323 const Type *Ty = Start->getType(); 1324 Ty = Rewriter.SE.getEffectiveSCEVType(Ty); 1325 1326 PHINode *PN = PHINode::Create(Ty, "lsr.iv", Header->begin()); 1327 PN->addIncoming(Rewriter.expandCodeFor(Start, Ty, Preheader->getTerminator()), 1328 Preheader); 1329 1330 // If the stride is negative, insert a sub instead of an add for the 1331 // increment. 1332 bool isNegative = isNonConstantNegative(Step); 1333 const SCEV *IncAmount = Step; 1334 if (isNegative) 1335 IncAmount = Rewriter.SE.getNegativeSCEV(Step); 1336 1337 // Insert an add instruction right before the terminator corresponding 1338 // to the back-edge or just before the only use. The location is determined 1339 // by the caller and passed in as IVIncInsertPt. 1340 Value *StepV = Rewriter.expandCodeFor(IncAmount, Ty, 1341 Preheader->getTerminator()); 1342 Instruction *IncV; 1343 if (isNegative) { 1344 IncV = BinaryOperator::CreateSub(PN, StepV, "lsr.iv.next", 1345 IVIncInsertPt); 1346 } else { 1347 IncV = BinaryOperator::CreateAdd(PN, StepV, "lsr.iv.next", 1348 IVIncInsertPt); 1349 } 1350 if (!isa<ConstantInt>(StepV)) ++NumVariable; 1351 1352 PN->addIncoming(IncV, LatchBlock); 1353 1354 ++NumInserted; 1355 return PN; 1356} 1357 1358static void SortUsersToProcess(std::vector<BasedUser> &UsersToProcess) { 1359 // We want to emit code for users inside the loop first. To do this, we 1360 // rearrange BasedUser so that the entries at the end have 1361 // isUseOfPostIncrementedValue = false, because we pop off the end of the 1362 // vector (so we handle them first). 1363 std::partition(UsersToProcess.begin(), UsersToProcess.end(), 1364 PartitionByIsUseOfPostIncrementedValue); 1365 1366 // Sort this by base, so that things with the same base are handled 1367 // together. By partitioning first and stable-sorting later, we are 1368 // guaranteed that within each base we will pop off users from within the 1369 // loop before users outside of the loop with a particular base. 1370 // 1371 // We would like to use stable_sort here, but we can't. The problem is that 1372 // const SCEV *'s don't have a deterministic ordering w.r.t to each other, so 1373 // we don't have anything to do a '<' comparison on. Because we think the 1374 // number of uses is small, do a horrible bubble sort which just relies on 1375 // ==. 1376 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) { 1377 // Get a base value. 1378 const SCEV *Base = UsersToProcess[i].Base; 1379 1380 // Compact everything with this base to be consecutive with this one. 1381 for (unsigned j = i+1; j != e; ++j) { 1382 if (UsersToProcess[j].Base == Base) { 1383 std::swap(UsersToProcess[i+1], UsersToProcess[j]); 1384 ++i; 1385 } 1386 } 1387 } 1388} 1389 1390/// PrepareToStrengthReduceFully - Prepare to fully strength-reduce 1391/// UsersToProcess, meaning lowering addresses all the way down to direct 1392/// pointer arithmetic. 1393/// 1394void 1395LoopStrengthReduce::PrepareToStrengthReduceFully( 1396 std::vector<BasedUser> &UsersToProcess, 1397 const SCEV *Stride, 1398 const SCEV *CommonExprs, 1399 const Loop *L, 1400 SCEVExpander &PreheaderRewriter) { 1401 DEBUG(errs() << " Fully reducing all users\n"); 1402 1403 // Rewrite the UsersToProcess records, creating a separate PHI for each 1404 // unique Base value. 1405 Instruction *IVIncInsertPt = L->getLoopLatch()->getTerminator(); 1406 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ) { 1407 // TODO: The uses are grouped by base, but not sorted. We arbitrarily 1408 // pick the first Imm value here to start with, and adjust it for the 1409 // other uses. 1410 const SCEV *Imm = UsersToProcess[i].Imm; 1411 const SCEV *Base = UsersToProcess[i].Base; 1412 const SCEV *Start = SE->getAddExpr(CommonExprs, Base, Imm); 1413 PHINode *Phi = InsertAffinePhi(Start, Stride, IVIncInsertPt, L, 1414 PreheaderRewriter); 1415 // Loop over all the users with the same base. 1416 do { 1417 UsersToProcess[i].Base = SE->getIntegerSCEV(0, Stride->getType()); 1418 UsersToProcess[i].Imm = SE->getMinusSCEV(UsersToProcess[i].Imm, Imm); 1419 UsersToProcess[i].Phi = Phi; 1420 assert(UsersToProcess[i].Imm->isLoopInvariant(L) && 1421 "ShouldUseFullStrengthReductionMode should reject this!"); 1422 } while (++i != e && Base == UsersToProcess[i].Base); 1423 } 1424} 1425 1426/// FindIVIncInsertPt - Return the location to insert the increment instruction. 1427/// If the only use if a use of postinc value, (must be the loop termination 1428/// condition), then insert it just before the use. 1429static Instruction *FindIVIncInsertPt(std::vector<BasedUser> &UsersToProcess, 1430 const Loop *L) { 1431 if (UsersToProcess.size() == 1 && 1432 UsersToProcess[0].isUseOfPostIncrementedValue && 1433 L->contains(UsersToProcess[0].Inst->getParent())) 1434 return UsersToProcess[0].Inst; 1435 return L->getLoopLatch()->getTerminator(); 1436} 1437 1438/// PrepareToStrengthReduceWithNewPhi - Insert a new induction variable for the 1439/// given users to share. 1440/// 1441void 1442LoopStrengthReduce::PrepareToStrengthReduceWithNewPhi( 1443 std::vector<BasedUser> &UsersToProcess, 1444 const SCEV *Stride, 1445 const SCEV *CommonExprs, 1446 Value *CommonBaseV, 1447 Instruction *IVIncInsertPt, 1448 const Loop *L, 1449 SCEVExpander &PreheaderRewriter) { 1450 DEBUG(errs() << " Inserting new PHI:\n"); 1451 1452 PHINode *Phi = InsertAffinePhi(SE->getUnknown(CommonBaseV), 1453 Stride, IVIncInsertPt, L, 1454 PreheaderRewriter); 1455 1456 // Remember this in case a later stride is multiple of this. 1457 IVsByStride[Stride].addIV(Stride, CommonExprs, Phi); 1458 1459 // All the users will share this new IV. 1460 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 1461 UsersToProcess[i].Phi = Phi; 1462 1463 DEBUG(errs() << " IV="); 1464 DEBUG(WriteAsOperand(errs(), Phi, /*PrintType=*/false)); 1465 DEBUG(errs() << "\n"); 1466} 1467 1468/// PrepareToStrengthReduceFromSmallerStride - Prepare for the given users to 1469/// reuse an induction variable with a stride that is a factor of the current 1470/// induction variable. 1471/// 1472void 1473LoopStrengthReduce::PrepareToStrengthReduceFromSmallerStride( 1474 std::vector<BasedUser> &UsersToProcess, 1475 Value *CommonBaseV, 1476 const IVExpr &ReuseIV, 1477 Instruction *PreInsertPt) { 1478 DEBUG(errs() << " Rewriting in terms of existing IV of STRIDE " 1479 << *ReuseIV.Stride << " and BASE " << *ReuseIV.Base << "\n"); 1480 1481 // All the users will share the reused IV. 1482 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 1483 UsersToProcess[i].Phi = ReuseIV.PHI; 1484 1485 Constant *C = dyn_cast<Constant>(CommonBaseV); 1486 if (C && 1487 (!C->isNullValue() && 1488 !fitsInAddressMode(SE->getUnknown(CommonBaseV), CommonBaseV->getType(), 1489 TLI, false))) 1490 // We want the common base emitted into the preheader! This is just 1491 // using cast as a copy so BitCast (no-op cast) is appropriate 1492 CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV->getType(), 1493 "commonbase", PreInsertPt); 1494} 1495 1496static bool IsImmFoldedIntoAddrMode(GlobalValue *GV, int64_t Offset, 1497 const Type *AccessTy, 1498 std::vector<BasedUser> &UsersToProcess, 1499 const TargetLowering *TLI) { 1500 SmallVector<Instruction*, 16> AddrModeInsts; 1501 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) { 1502 if (UsersToProcess[i].isUseOfPostIncrementedValue) 1503 continue; 1504 ExtAddrMode AddrMode = 1505 AddressingModeMatcher::Match(UsersToProcess[i].OperandValToReplace, 1506 AccessTy, UsersToProcess[i].Inst, 1507 AddrModeInsts, *TLI); 1508 if (GV && GV != AddrMode.BaseGV) 1509 return false; 1510 if (Offset && !AddrMode.BaseOffs) 1511 // FIXME: How to accurate check it's immediate offset is folded. 1512 return false; 1513 AddrModeInsts.clear(); 1514 } 1515 return true; 1516} 1517 1518/// StrengthReduceIVUsersOfStride - Strength reduce all of the users of a single 1519/// stride of IV. All of the users may have different starting values, and this 1520/// may not be the only stride. 1521void 1522LoopStrengthReduce::StrengthReduceIVUsersOfStride(const SCEV *const &Stride, 1523 IVUsersOfOneStride &Uses, 1524 Loop *L) { 1525 // If all the users are moved to another stride, then there is nothing to do. 1526 if (Uses.Users.empty()) 1527 return; 1528 1529 // Keep track if every use in UsersToProcess is an address. If they all are, 1530 // we may be able to rewrite the entire collection of them in terms of a 1531 // smaller-stride IV. 1532 bool AllUsesAreAddresses = true; 1533 1534 // Keep track if every use of a single stride is outside the loop. If so, 1535 // we want to be more aggressive about reusing a smaller-stride IV; a 1536 // multiply outside the loop is better than another IV inside. Well, usually. 1537 bool AllUsesAreOutsideLoop = true; 1538 1539 // Transform our list of users and offsets to a bit more complex table. In 1540 // this new vector, each 'BasedUser' contains 'Base' the base of the 1541 // strided accessas well as the old information from Uses. We progressively 1542 // move information from the Base field to the Imm field, until we eventually 1543 // have the full access expression to rewrite the use. 1544 std::vector<BasedUser> UsersToProcess; 1545 const SCEV *CommonExprs = CollectIVUsers(Stride, Uses, L, AllUsesAreAddresses, 1546 AllUsesAreOutsideLoop, 1547 UsersToProcess); 1548 1549 // Sort the UsersToProcess array so that users with common bases are 1550 // next to each other. 1551 SortUsersToProcess(UsersToProcess); 1552 1553 // If we managed to find some expressions in common, we'll need to carry 1554 // their value in a register and add it in for each use. This will take up 1555 // a register operand, which potentially restricts what stride values are 1556 // valid. 1557 bool HaveCommonExprs = !CommonExprs->isZero(); 1558 const Type *ReplacedTy = CommonExprs->getType(); 1559 1560 // If all uses are addresses, consider sinking the immediate part of the 1561 // common expression back into uses if they can fit in the immediate fields. 1562 if (TLI && HaveCommonExprs && AllUsesAreAddresses) { 1563 const SCEV *NewCommon = CommonExprs; 1564 const SCEV *Imm = SE->getIntegerSCEV(0, ReplacedTy); 1565 MoveImmediateValues(TLI, Type::getVoidTy( 1566 L->getLoopPreheader()->getContext()), 1567 NewCommon, Imm, true, L, SE); 1568 if (!Imm->isZero()) { 1569 bool DoSink = true; 1570 1571 // If the immediate part of the common expression is a GV, check if it's 1572 // possible to fold it into the target addressing mode. 1573 GlobalValue *GV = 0; 1574 if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(Imm)) 1575 GV = dyn_cast<GlobalValue>(SU->getValue()); 1576 int64_t Offset = 0; 1577 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Imm)) 1578 Offset = SC->getValue()->getSExtValue(); 1579 if (GV || Offset) 1580 // Pass VoidTy as the AccessTy to be conservative, because 1581 // there could be multiple access types among all the uses. 1582 DoSink = IsImmFoldedIntoAddrMode(GV, Offset, 1583 Type::getVoidTy(L->getLoopPreheader()->getContext()), 1584 UsersToProcess, TLI); 1585 1586 if (DoSink) { 1587 DEBUG(errs() << " Sinking " << *Imm << " back down into uses\n"); 1588 for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) 1589 UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm, Imm); 1590 CommonExprs = NewCommon; 1591 HaveCommonExprs = !CommonExprs->isZero(); 1592 ++NumImmSunk; 1593 } 1594 } 1595 } 1596 1597 // Now that we know what we need to do, insert the PHI node itself. 1598 // 1599 DEBUG(errs() << "LSR: Examining IVs of TYPE " << *ReplacedTy << " of STRIDE " 1600 << *Stride << ":\n" 1601 << " Common base: " << *CommonExprs << "\n"); 1602 1603 SCEVExpander Rewriter(*SE); 1604 SCEVExpander PreheaderRewriter(*SE); 1605 1606 BasicBlock *Preheader = L->getLoopPreheader(); 1607 Instruction *PreInsertPt = Preheader->getTerminator(); 1608 BasicBlock *LatchBlock = L->getLoopLatch(); 1609 Instruction *IVIncInsertPt = LatchBlock->getTerminator(); 1610 1611 Value *CommonBaseV = Constant::getNullValue(ReplacedTy); 1612 1613 const SCEV *RewriteFactor = SE->getIntegerSCEV(0, ReplacedTy); 1614 IVExpr ReuseIV(SE->getIntegerSCEV(0, 1615 Type::getInt32Ty(Preheader->getContext())), 1616 SE->getIntegerSCEV(0, 1617 Type::getInt32Ty(Preheader->getContext())), 1618 0); 1619 1620 // Choose a strength-reduction strategy and prepare for it by creating 1621 // the necessary PHIs and adjusting the bookkeeping. 1622 if (ShouldUseFullStrengthReductionMode(UsersToProcess, L, 1623 AllUsesAreAddresses, Stride)) { 1624 PrepareToStrengthReduceFully(UsersToProcess, Stride, CommonExprs, L, 1625 PreheaderRewriter); 1626 } else { 1627 // Emit the initial base value into the loop preheader. 1628 CommonBaseV = PreheaderRewriter.expandCodeFor(CommonExprs, ReplacedTy, 1629 PreInsertPt); 1630 1631 // If all uses are addresses, check if it is possible to reuse an IV. The 1632 // new IV must have a stride that is a multiple of the old stride; the 1633 // multiple must be a number that can be encoded in the scale field of the 1634 // target addressing mode; and we must have a valid instruction after this 1635 // substitution, including the immediate field, if any. 1636 RewriteFactor = CheckForIVReuse(HaveCommonExprs, AllUsesAreAddresses, 1637 AllUsesAreOutsideLoop, 1638 Stride, ReuseIV, ReplacedTy, 1639 UsersToProcess); 1640 if (!RewriteFactor->isZero()) 1641 PrepareToStrengthReduceFromSmallerStride(UsersToProcess, CommonBaseV, 1642 ReuseIV, PreInsertPt); 1643 else { 1644 IVIncInsertPt = FindIVIncInsertPt(UsersToProcess, L); 1645 PrepareToStrengthReduceWithNewPhi(UsersToProcess, Stride, CommonExprs, 1646 CommonBaseV, IVIncInsertPt, 1647 L, PreheaderRewriter); 1648 } 1649 } 1650 1651 // Process all the users now, replacing their strided uses with 1652 // strength-reduced forms. This outer loop handles all bases, the inner 1653 // loop handles all users of a particular base. 1654 while (!UsersToProcess.empty()) { 1655 const SCEV *Base = UsersToProcess.back().Base; 1656 Instruction *Inst = UsersToProcess.back().Inst; 1657 1658 // Emit the code for Base into the preheader. 1659 Value *BaseV = 0; 1660 if (!Base->isZero()) { 1661 BaseV = PreheaderRewriter.expandCodeFor(Base, 0, PreInsertPt); 1662 1663 DEBUG(errs() << " INSERTING code for BASE = " << *Base << ":"); 1664 if (BaseV->hasName()) 1665 DEBUG(errs() << " Result value name = %" << BaseV->getName()); 1666 DEBUG(errs() << "\n"); 1667 1668 // If BaseV is a non-zero constant, make sure that it gets inserted into 1669 // the preheader, instead of being forward substituted into the uses. We 1670 // do this by forcing a BitCast (noop cast) to be inserted into the 1671 // preheader in this case. 1672 if (!fitsInAddressMode(Base, getAccessType(Inst), TLI, false) && 1673 isa<Constant>(BaseV)) { 1674 // We want this constant emitted into the preheader! This is just 1675 // using cast as a copy so BitCast (no-op cast) is appropriate 1676 BaseV = new BitCastInst(BaseV, BaseV->getType(), "preheaderinsert", 1677 PreInsertPt); 1678 } 1679 } 1680 1681 // Emit the code to add the immediate offset to the Phi value, just before 1682 // the instructions that we identified as using this stride and base. 1683 do { 1684 // FIXME: Use emitted users to emit other users. 1685 BasedUser &User = UsersToProcess.back(); 1686 1687 DEBUG(errs() << " Examining "); 1688 if (User.isUseOfPostIncrementedValue) 1689 DEBUG(errs() << "postinc"); 1690 else 1691 DEBUG(errs() << "preinc"); 1692 DEBUG(errs() << " use "); 1693 DEBUG(WriteAsOperand(errs(), UsersToProcess.back().OperandValToReplace, 1694 /*PrintType=*/false)); 1695 DEBUG(errs() << " in Inst: " << *User.Inst); 1696 1697 // If this instruction wants to use the post-incremented value, move it 1698 // after the post-inc and use its value instead of the PHI. 1699 Value *RewriteOp = User.Phi; 1700 if (User.isUseOfPostIncrementedValue) { 1701 RewriteOp = User.Phi->getIncomingValueForBlock(LatchBlock); 1702 // If this user is in the loop, make sure it is the last thing in the 1703 // loop to ensure it is dominated by the increment. In case it's the 1704 // only use of the iv, the increment instruction is already before the 1705 // use. 1706 if (L->contains(User.Inst->getParent()) && User.Inst != IVIncInsertPt) 1707 User.Inst->moveBefore(IVIncInsertPt); 1708 } 1709 1710 const SCEV *RewriteExpr = SE->getUnknown(RewriteOp); 1711 1712 if (SE->getEffectiveSCEVType(RewriteOp->getType()) != 1713 SE->getEffectiveSCEVType(ReplacedTy)) { 1714 assert(SE->getTypeSizeInBits(RewriteOp->getType()) > 1715 SE->getTypeSizeInBits(ReplacedTy) && 1716 "Unexpected widening cast!"); 1717 RewriteExpr = SE->getTruncateExpr(RewriteExpr, ReplacedTy); 1718 } 1719 1720 // If we had to insert new instructions for RewriteOp, we have to 1721 // consider that they may not have been able to end up immediately 1722 // next to RewriteOp, because non-PHI instructions may never precede 1723 // PHI instructions in a block. In this case, remember where the last 1724 // instruction was inserted so that if we're replacing a different 1725 // PHI node, we can use the later point to expand the final 1726 // RewriteExpr. 1727 Instruction *NewBasePt = dyn_cast<Instruction>(RewriteOp); 1728 if (RewriteOp == User.Phi) NewBasePt = 0; 1729 1730 // Clear the SCEVExpander's expression map so that we are guaranteed 1731 // to have the code emitted where we expect it. 1732 Rewriter.clear(); 1733 1734 // If we are reusing the iv, then it must be multiplied by a constant 1735 // factor to take advantage of the addressing mode scale component. 1736 if (!RewriteFactor->isZero()) { 1737 // If we're reusing an IV with a nonzero base (currently this happens 1738 // only when all reuses are outside the loop) subtract that base here. 1739 // The base has been used to initialize the PHI node but we don't want 1740 // it here. 1741 if (!ReuseIV.Base->isZero()) { 1742 const SCEV *typedBase = ReuseIV.Base; 1743 if (SE->getEffectiveSCEVType(RewriteExpr->getType()) != 1744 SE->getEffectiveSCEVType(ReuseIV.Base->getType())) { 1745 // It's possible the original IV is a larger type than the new IV, 1746 // in which case we have to truncate the Base. We checked in 1747 // RequiresTypeConversion that this is valid. 1748 assert(SE->getTypeSizeInBits(RewriteExpr->getType()) < 1749 SE->getTypeSizeInBits(ReuseIV.Base->getType()) && 1750 "Unexpected lengthening conversion!"); 1751 typedBase = SE->getTruncateExpr(ReuseIV.Base, 1752 RewriteExpr->getType()); 1753 } 1754 RewriteExpr = SE->getMinusSCEV(RewriteExpr, typedBase); 1755 } 1756 1757 // Multiply old variable, with base removed, by new scale factor. 1758 RewriteExpr = SE->getMulExpr(RewriteFactor, 1759 RewriteExpr); 1760 1761 // The common base is emitted in the loop preheader. But since we 1762 // are reusing an IV, it has not been used to initialize the PHI node. 1763 // Add it to the expression used to rewrite the uses. 1764 // When this use is outside the loop, we earlier subtracted the 1765 // common base, and are adding it back here. Use the same expression 1766 // as before, rather than CommonBaseV, so DAGCombiner will zap it. 1767 if (!CommonExprs->isZero()) { 1768 if (L->contains(User.Inst->getParent())) 1769 RewriteExpr = SE->getAddExpr(RewriteExpr, 1770 SE->getUnknown(CommonBaseV)); 1771 else 1772 RewriteExpr = SE->getAddExpr(RewriteExpr, CommonExprs); 1773 } 1774 } 1775 1776 // Now that we know what we need to do, insert code before User for the 1777 // immediate and any loop-variant expressions. 1778 if (BaseV) 1779 // Add BaseV to the PHI value if needed. 1780 RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV)); 1781 1782 User.RewriteInstructionToUseNewBase(RewriteExpr, NewBasePt, 1783 Rewriter, L, this, *LI, 1784 DeadInsts); 1785 1786 // Mark old value we replaced as possibly dead, so that it is eliminated 1787 // if we just replaced the last use of that value. 1788 DeadInsts.push_back(User.OperandValToReplace); 1789 1790 UsersToProcess.pop_back(); 1791 ++NumReduced; 1792 1793 // If there are any more users to process with the same base, process them 1794 // now. We sorted by base above, so we just have to check the last elt. 1795 } while (!UsersToProcess.empty() && UsersToProcess.back().Base == Base); 1796 // TODO: Next, find out which base index is the most common, pull it out. 1797 } 1798 1799 // IMPORTANT TODO: Figure out how to partition the IV's with this stride, but 1800 // different starting values, into different PHIs. 1801} 1802 1803void LoopStrengthReduce::StrengthReduceIVUsers(Loop *L) { 1804 // Note: this processes each stride/type pair individually. All users 1805 // passed into StrengthReduceIVUsersOfStride have the same type AND stride. 1806 // Also, note that we iterate over IVUsesByStride indirectly by using 1807 // StrideOrder. This extra layer of indirection makes the ordering of 1808 // strides deterministic - not dependent on map order. 1809 for (unsigned Stride = 0, e = IU->StrideOrder.size(); Stride != e; ++Stride) { 1810 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 1811 IU->IVUsesByStride.find(IU->StrideOrder[Stride]); 1812 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 1813 // FIXME: Generalize to non-affine IV's. 1814 if (!SI->first->isLoopInvariant(L)) 1815 continue; 1816 StrengthReduceIVUsersOfStride(SI->first, *SI->second, L); 1817 } 1818} 1819 1820/// FindIVUserForCond - If Cond has an operand that is an expression of an IV, 1821/// set the IV user and stride information and return true, otherwise return 1822/// false. 1823bool LoopStrengthReduce::FindIVUserForCond(ICmpInst *Cond, 1824 IVStrideUse *&CondUse, 1825 const SCEV* &CondStride) { 1826 for (unsigned Stride = 0, e = IU->StrideOrder.size(); 1827 Stride != e && !CondUse; ++Stride) { 1828 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 1829 IU->IVUsesByStride.find(IU->StrideOrder[Stride]); 1830 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 1831 1832 for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(), 1833 E = SI->second->Users.end(); UI != E; ++UI) 1834 if (UI->getUser() == Cond) { 1835 // NOTE: we could handle setcc instructions with multiple uses here, but 1836 // InstCombine does it as well for simple uses, it's not clear that it 1837 // occurs enough in real life to handle. 1838 CondUse = UI; 1839 CondStride = SI->first; 1840 return true; 1841 } 1842 } 1843 return false; 1844} 1845 1846namespace { 1847 // Constant strides come first which in turns are sorted by their absolute 1848 // values. If absolute values are the same, then positive strides comes first. 1849 // e.g. 1850 // 4, -1, X, 1, 2 ==> 1, -1, 2, 4, X 1851 struct StrideCompare { 1852 const ScalarEvolution *SE; 1853 explicit StrideCompare(const ScalarEvolution *se) : SE(se) {} 1854 1855 bool operator()(const SCEV *const &LHS, const SCEV *const &RHS) { 1856 const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS); 1857 const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS); 1858 if (LHSC && RHSC) { 1859 int64_t LV = LHSC->getValue()->getSExtValue(); 1860 int64_t RV = RHSC->getValue()->getSExtValue(); 1861 uint64_t ALV = (LV < 0) ? -LV : LV; 1862 uint64_t ARV = (RV < 0) ? -RV : RV; 1863 if (ALV == ARV) { 1864 if (LV != RV) 1865 return LV > RV; 1866 } else { 1867 return ALV < ARV; 1868 } 1869 1870 // If it's the same value but different type, sort by bit width so 1871 // that we emit larger induction variables before smaller 1872 // ones, letting the smaller be re-written in terms of larger ones. 1873 return SE->getTypeSizeInBits(RHS->getType()) < 1874 SE->getTypeSizeInBits(LHS->getType()); 1875 } 1876 return LHSC && !RHSC; 1877 } 1878 }; 1879} 1880 1881/// ChangeCompareStride - If a loop termination compare instruction is the 1882/// only use of its stride, and the compaison is against a constant value, 1883/// try eliminate the stride by moving the compare instruction to another 1884/// stride and change its constant operand accordingly. e.g. 1885/// 1886/// loop: 1887/// ... 1888/// v1 = v1 + 3 1889/// v2 = v2 + 1 1890/// if (v2 < 10) goto loop 1891/// => 1892/// loop: 1893/// ... 1894/// v1 = v1 + 3 1895/// if (v1 < 30) goto loop 1896ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond, 1897 IVStrideUse* &CondUse, 1898 const SCEV* &CondStride, 1899 bool PostPass) { 1900 // If there's only one stride in the loop, there's nothing to do here. 1901 if (IU->StrideOrder.size() < 2) 1902 return Cond; 1903 // If there are other users of the condition's stride, don't bother 1904 // trying to change the condition because the stride will still 1905 // remain. 1906 std::map<const SCEV *, IVUsersOfOneStride *>::iterator I = 1907 IU->IVUsesByStride.find(CondStride); 1908 if (I == IU->IVUsesByStride.end()) 1909 return Cond; 1910 if (I->second->Users.size() > 1) { 1911 for (ilist<IVStrideUse>::iterator II = I->second->Users.begin(), 1912 EE = I->second->Users.end(); II != EE; ++II) { 1913 if (II->getUser() == Cond) 1914 continue; 1915 if (!isInstructionTriviallyDead(II->getUser())) 1916 return Cond; 1917 } 1918 } 1919 // Only handle constant strides for now. 1920 const SCEVConstant *SC = dyn_cast<SCEVConstant>(CondStride); 1921 if (!SC) return Cond; 1922 1923 ICmpInst::Predicate Predicate = Cond->getPredicate(); 1924 int64_t CmpSSInt = SC->getValue()->getSExtValue(); 1925 unsigned BitWidth = SE->getTypeSizeInBits(CondStride->getType()); 1926 uint64_t SignBit = 1ULL << (BitWidth-1); 1927 const Type *CmpTy = Cond->getOperand(0)->getType(); 1928 const Type *NewCmpTy = NULL; 1929 unsigned TyBits = SE->getTypeSizeInBits(CmpTy); 1930 unsigned NewTyBits = 0; 1931 const SCEV *NewStride = NULL; 1932 Value *NewCmpLHS = NULL; 1933 Value *NewCmpRHS = NULL; 1934 int64_t Scale = 1; 1935 const SCEV *NewOffset = SE->getIntegerSCEV(0, CmpTy); 1936 1937 if (ConstantInt *C = dyn_cast<ConstantInt>(Cond->getOperand(1))) { 1938 int64_t CmpVal = C->getValue().getSExtValue(); 1939 1940 // Check the relevant induction variable for conformance to 1941 // the pattern. 1942 const SCEV *IV = SE->getSCEV(Cond->getOperand(0)); 1943 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 1944 if (!AR || !AR->isAffine()) 1945 return Cond; 1946 1947 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart()); 1948 // Check stride constant and the comparision constant signs to detect 1949 // overflow. 1950 if (StartC) { 1951 if ((StartC->getValue()->getSExtValue() < CmpVal && CmpSSInt < 0) || 1952 (StartC->getValue()->getSExtValue() > CmpVal && CmpSSInt > 0)) 1953 return Cond; 1954 } else { 1955 // More restrictive check for the other cases. 1956 if ((CmpVal & SignBit) != (CmpSSInt & SignBit)) 1957 return Cond; 1958 } 1959 1960 // Look for a suitable stride / iv as replacement. 1961 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 1962 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 1963 IU->IVUsesByStride.find(IU->StrideOrder[i]); 1964 if (!isa<SCEVConstant>(SI->first) || SI->second->Users.empty()) 1965 continue; 1966 int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue(); 1967 if (SSInt == CmpSSInt || 1968 abs64(SSInt) < abs64(CmpSSInt) || 1969 (SSInt % CmpSSInt) != 0) 1970 continue; 1971 1972 Scale = SSInt / CmpSSInt; 1973 int64_t NewCmpVal = CmpVal * Scale; 1974 1975 // If old icmp value fits in icmp immediate field, but the new one doesn't 1976 // try something else. 1977 if (TLI && 1978 TLI->isLegalICmpImmediate(CmpVal) && 1979 !TLI->isLegalICmpImmediate(NewCmpVal)) 1980 continue; 1981 1982 APInt Mul = APInt(BitWidth*2, CmpVal, true); 1983 Mul = Mul * APInt(BitWidth*2, Scale, true); 1984 // Check for overflow. 1985 if (!Mul.isSignedIntN(BitWidth)) 1986 continue; 1987 // Check for overflow in the stride's type too. 1988 if (!Mul.isSignedIntN(SE->getTypeSizeInBits(SI->first->getType()))) 1989 continue; 1990 1991 // Watch out for overflow. 1992 if (ICmpInst::isSigned(Predicate) && 1993 (CmpVal & SignBit) != (NewCmpVal & SignBit)) 1994 continue; 1995 1996 // Pick the best iv to use trying to avoid a cast. 1997 NewCmpLHS = NULL; 1998 for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(), 1999 E = SI->second->Users.end(); UI != E; ++UI) { 2000 Value *Op = UI->getOperandValToReplace(); 2001 2002 // If the IVStrideUse implies a cast, check for an actual cast which 2003 // can be used to find the original IV expression. 2004 if (SE->getEffectiveSCEVType(Op->getType()) != 2005 SE->getEffectiveSCEVType(SI->first->getType())) { 2006 CastInst *CI = dyn_cast<CastInst>(Op); 2007 // If it's not a simple cast, it's complicated. 2008 if (!CI) 2009 continue; 2010 // If it's a cast from a type other than the stride type, 2011 // it's complicated. 2012 if (CI->getOperand(0)->getType() != SI->first->getType()) 2013 continue; 2014 // Ok, we found the IV expression in the stride's type. 2015 Op = CI->getOperand(0); 2016 } 2017 2018 NewCmpLHS = Op; 2019 if (NewCmpLHS->getType() == CmpTy) 2020 break; 2021 } 2022 if (!NewCmpLHS) 2023 continue; 2024 2025 NewCmpTy = NewCmpLHS->getType(); 2026 NewTyBits = SE->getTypeSizeInBits(NewCmpTy); 2027 const Type *NewCmpIntTy = IntegerType::get(Cond->getContext(), NewTyBits); 2028 if (RequiresTypeConversion(NewCmpTy, CmpTy)) { 2029 // Check if it is possible to rewrite it using 2030 // an iv / stride of a smaller integer type. 2031 unsigned Bits = NewTyBits; 2032 if (ICmpInst::isSigned(Predicate)) 2033 --Bits; 2034 uint64_t Mask = (1ULL << Bits) - 1; 2035 if (((uint64_t)NewCmpVal & Mask) != (uint64_t)NewCmpVal) 2036 continue; 2037 } 2038 2039 // Don't rewrite if use offset is non-constant and the new type is 2040 // of a different type. 2041 // FIXME: too conservative? 2042 if (NewTyBits != TyBits && !isa<SCEVConstant>(CondUse->getOffset())) 2043 continue; 2044 2045 if (!PostPass) { 2046 bool AllUsesAreAddresses = true; 2047 bool AllUsesAreOutsideLoop = true; 2048 std::vector<BasedUser> UsersToProcess; 2049 const SCEV *CommonExprs = CollectIVUsers(SI->first, *SI->second, L, 2050 AllUsesAreAddresses, 2051 AllUsesAreOutsideLoop, 2052 UsersToProcess); 2053 // Avoid rewriting the compare instruction with an iv of new stride 2054 // if it's likely the new stride uses will be rewritten using the 2055 // stride of the compare instruction. 2056 if (AllUsesAreAddresses && 2057 ValidScale(!CommonExprs->isZero(), Scale, UsersToProcess)) 2058 continue; 2059 } 2060 2061 // Avoid rewriting the compare instruction with an iv which has 2062 // implicit extension or truncation built into it. 2063 // TODO: This is over-conservative. 2064 if (SE->getTypeSizeInBits(CondUse->getOffset()->getType()) != TyBits) 2065 continue; 2066 2067 // If scale is negative, use swapped predicate unless it's testing 2068 // for equality. 2069 if (Scale < 0 && !Cond->isEquality()) 2070 Predicate = ICmpInst::getSwappedPredicate(Predicate); 2071 2072 NewStride = IU->StrideOrder[i]; 2073 if (!isa<PointerType>(NewCmpTy)) 2074 NewCmpRHS = ConstantInt::get(NewCmpTy, NewCmpVal); 2075 else { 2076 Constant *CI = ConstantInt::get(NewCmpIntTy, NewCmpVal); 2077 NewCmpRHS = ConstantExpr::getIntToPtr(CI, NewCmpTy); 2078 } 2079 NewOffset = TyBits == NewTyBits 2080 ? SE->getMulExpr(CondUse->getOffset(), 2081 SE->getConstant(CmpTy, Scale)) 2082 : SE->getConstant(NewCmpIntTy, 2083 cast<SCEVConstant>(CondUse->getOffset())->getValue() 2084 ->getSExtValue()*Scale); 2085 break; 2086 } 2087 } 2088 2089 // Forgo this transformation if it the increment happens to be 2090 // unfortunately positioned after the condition, and the condition 2091 // has multiple uses which prevent it from being moved immediately 2092 // before the branch. See 2093 // test/Transforms/LoopStrengthReduce/change-compare-stride-trickiness-*.ll 2094 // for an example of this situation. 2095 if (!Cond->hasOneUse()) { 2096 for (BasicBlock::iterator I = Cond, E = Cond->getParent()->end(); 2097 I != E; ++I) 2098 if (I == NewCmpLHS) 2099 return Cond; 2100 } 2101 2102 if (NewCmpRHS) { 2103 // Create a new compare instruction using new stride / iv. 2104 ICmpInst *OldCond = Cond; 2105 // Insert new compare instruction. 2106 Cond = new ICmpInst(OldCond, Predicate, NewCmpLHS, NewCmpRHS, 2107 L->getHeader()->getName() + ".termcond"); 2108 2109 DEBUG(errs() << " Change compare stride in Inst " << *OldCond); 2110 DEBUG(errs() << " to " << *Cond << '\n'); 2111 2112 // Remove the old compare instruction. The old indvar is probably dead too. 2113 DeadInsts.push_back(CondUse->getOperandValToReplace()); 2114 OldCond->replaceAllUsesWith(Cond); 2115 OldCond->eraseFromParent(); 2116 2117 IU->IVUsesByStride[NewStride]->addUser(NewOffset, Cond, NewCmpLHS); 2118 CondUse = &IU->IVUsesByStride[NewStride]->Users.back(); 2119 CondStride = NewStride; 2120 ++NumEliminated; 2121 Changed = true; 2122 } 2123 2124 return Cond; 2125} 2126 2127/// OptimizeMax - Rewrite the loop's terminating condition if it uses 2128/// a max computation. 2129/// 2130/// This is a narrow solution to a specific, but acute, problem. For loops 2131/// like this: 2132/// 2133/// i = 0; 2134/// do { 2135/// p[i] = 0.0; 2136/// } while (++i < n); 2137/// 2138/// the trip count isn't just 'n', because 'n' might not be positive. And 2139/// unfortunately this can come up even for loops where the user didn't use 2140/// a C do-while loop. For example, seemingly well-behaved top-test loops 2141/// will commonly be lowered like this: 2142// 2143/// if (n > 0) { 2144/// i = 0; 2145/// do { 2146/// p[i] = 0.0; 2147/// } while (++i < n); 2148/// } 2149/// 2150/// and then it's possible for subsequent optimization to obscure the if 2151/// test in such a way that indvars can't find it. 2152/// 2153/// When indvars can't find the if test in loops like this, it creates a 2154/// max expression, which allows it to give the loop a canonical 2155/// induction variable: 2156/// 2157/// i = 0; 2158/// max = n < 1 ? 1 : n; 2159/// do { 2160/// p[i] = 0.0; 2161/// } while (++i != max); 2162/// 2163/// Canonical induction variables are necessary because the loop passes 2164/// are designed around them. The most obvious example of this is the 2165/// LoopInfo analysis, which doesn't remember trip count values. It 2166/// expects to be able to rediscover the trip count each time it is 2167/// needed, and it does this using a simple analyis that only succeeds if 2168/// the loop has a canonical induction variable. 2169/// 2170/// However, when it comes time to generate code, the maximum operation 2171/// can be quite costly, especially if it's inside of an outer loop. 2172/// 2173/// This function solves this problem by detecting this type of loop and 2174/// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting 2175/// the instructions for the maximum computation. 2176/// 2177ICmpInst *LoopStrengthReduce::OptimizeMax(Loop *L, ICmpInst *Cond, 2178 IVStrideUse* &CondUse) { 2179 // Check that the loop matches the pattern we're looking for. 2180 if (Cond->getPredicate() != CmpInst::ICMP_EQ && 2181 Cond->getPredicate() != CmpInst::ICMP_NE) 2182 return Cond; 2183 2184 SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1)); 2185 if (!Sel || !Sel->hasOneUse()) return Cond; 2186 2187 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 2188 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 2189 return Cond; 2190 const SCEV *One = SE->getIntegerSCEV(1, BackedgeTakenCount->getType()); 2191 2192 // Add one to the backedge-taken count to get the trip count. 2193 const SCEV *IterationCount = SE->getAddExpr(BackedgeTakenCount, One); 2194 2195 // Check for a max calculation that matches the pattern. 2196 if (!isa<SCEVSMaxExpr>(IterationCount) && !isa<SCEVUMaxExpr>(IterationCount)) 2197 return Cond; 2198 const SCEVNAryExpr *Max = cast<SCEVNAryExpr>(IterationCount); 2199 if (Max != SE->getSCEV(Sel)) return Cond; 2200 2201 // To handle a max with more than two operands, this optimization would 2202 // require additional checking and setup. 2203 if (Max->getNumOperands() != 2) 2204 return Cond; 2205 2206 const SCEV *MaxLHS = Max->getOperand(0); 2207 const SCEV *MaxRHS = Max->getOperand(1); 2208 if (!MaxLHS || MaxLHS != One) return Cond; 2209 2210 // Check the relevant induction variable for conformance to 2211 // the pattern. 2212 const SCEV *IV = SE->getSCEV(Cond->getOperand(0)); 2213 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 2214 if (!AR || !AR->isAffine() || 2215 AR->getStart() != One || 2216 AR->getStepRecurrence(*SE) != One) 2217 return Cond; 2218 2219 assert(AR->getLoop() == L && 2220 "Loop condition operand is an addrec in a different loop!"); 2221 2222 // Check the right operand of the select, and remember it, as it will 2223 // be used in the new comparison instruction. 2224 Value *NewRHS = 0; 2225 if (SE->getSCEV(Sel->getOperand(1)) == MaxRHS) 2226 NewRHS = Sel->getOperand(1); 2227 else if (SE->getSCEV(Sel->getOperand(2)) == MaxRHS) 2228 NewRHS = Sel->getOperand(2); 2229 if (!NewRHS) return Cond; 2230 2231 // Determine the new comparison opcode. It may be signed or unsigned, 2232 // and the original comparison may be either equality or inequality. 2233 CmpInst::Predicate Pred = 2234 isa<SCEVSMaxExpr>(Max) ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; 2235 if (Cond->getPredicate() == CmpInst::ICMP_EQ) 2236 Pred = CmpInst::getInversePredicate(Pred); 2237 2238 // Ok, everything looks ok to change the condition into an SLT or SGE and 2239 // delete the max calculation. 2240 ICmpInst *NewCond = 2241 new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp"); 2242 2243 // Delete the max calculation instructions. 2244 Cond->replaceAllUsesWith(NewCond); 2245 CondUse->setUser(NewCond); 2246 Instruction *Cmp = cast<Instruction>(Sel->getOperand(0)); 2247 Cond->eraseFromParent(); 2248 Sel->eraseFromParent(); 2249 if (Cmp->use_empty()) 2250 Cmp->eraseFromParent(); 2251 return NewCond; 2252} 2253 2254/// OptimizeShadowIV - If IV is used in a int-to-float cast 2255/// inside the loop then try to eliminate the cast opeation. 2256void LoopStrengthReduce::OptimizeShadowIV(Loop *L) { 2257 2258 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 2259 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 2260 return; 2261 2262 for (unsigned Stride = 0, e = IU->StrideOrder.size(); Stride != e; 2263 ++Stride) { 2264 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 2265 IU->IVUsesByStride.find(IU->StrideOrder[Stride]); 2266 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 2267 if (!isa<SCEVConstant>(SI->first)) 2268 continue; 2269 2270 for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(), 2271 E = SI->second->Users.end(); UI != E; /* empty */) { 2272 ilist<IVStrideUse>::iterator CandidateUI = UI; 2273 ++UI; 2274 Instruction *ShadowUse = CandidateUI->getUser(); 2275 const Type *DestTy = NULL; 2276 2277 /* If shadow use is a int->float cast then insert a second IV 2278 to eliminate this cast. 2279 2280 for (unsigned i = 0; i < n; ++i) 2281 foo((double)i); 2282 2283 is transformed into 2284 2285 double d = 0.0; 2286 for (unsigned i = 0; i < n; ++i, ++d) 2287 foo(d); 2288 */ 2289 if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) 2290 DestTy = UCast->getDestTy(); 2291 else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) 2292 DestTy = SCast->getDestTy(); 2293 if (!DestTy) continue; 2294 2295 if (TLI) { 2296 // If target does not support DestTy natively then do not apply 2297 // this transformation. 2298 EVT DVT = TLI->getValueType(DestTy); 2299 if (!TLI->isTypeLegal(DVT)) continue; 2300 } 2301 2302 PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0)); 2303 if (!PH) continue; 2304 if (PH->getNumIncomingValues() != 2) continue; 2305 2306 const Type *SrcTy = PH->getType(); 2307 int Mantissa = DestTy->getFPMantissaWidth(); 2308 if (Mantissa == -1) continue; 2309 if ((int)SE->getTypeSizeInBits(SrcTy) > Mantissa) 2310 continue; 2311 2312 unsigned Entry, Latch; 2313 if (PH->getIncomingBlock(0) == L->getLoopPreheader()) { 2314 Entry = 0; 2315 Latch = 1; 2316 } else { 2317 Entry = 1; 2318 Latch = 0; 2319 } 2320 2321 ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry)); 2322 if (!Init) continue; 2323 Constant *NewInit = ConstantFP::get(DestTy, Init->getZExtValue()); 2324 2325 BinaryOperator *Incr = 2326 dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch)); 2327 if (!Incr) continue; 2328 if (Incr->getOpcode() != Instruction::Add 2329 && Incr->getOpcode() != Instruction::Sub) 2330 continue; 2331 2332 /* Initialize new IV, double d = 0.0 in above example. */ 2333 ConstantInt *C = NULL; 2334 if (Incr->getOperand(0) == PH) 2335 C = dyn_cast<ConstantInt>(Incr->getOperand(1)); 2336 else if (Incr->getOperand(1) == PH) 2337 C = dyn_cast<ConstantInt>(Incr->getOperand(0)); 2338 else 2339 continue; 2340 2341 if (!C) continue; 2342 2343 // Ignore negative constants, as the code below doesn't handle them 2344 // correctly. TODO: Remove this restriction. 2345 if (!C->getValue().isStrictlyPositive()) continue; 2346 2347 /* Add new PHINode. */ 2348 PHINode *NewPH = PHINode::Create(DestTy, "IV.S.", PH); 2349 2350 /* create new increment. '++d' in above example. */ 2351 Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue()); 2352 BinaryOperator *NewIncr = 2353 BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ? 2354 Instruction::FAdd : Instruction::FSub, 2355 NewPH, CFP, "IV.S.next.", Incr); 2356 2357 NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry)); 2358 NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch)); 2359 2360 /* Remove cast operation */ 2361 ShadowUse->replaceAllUsesWith(NewPH); 2362 ShadowUse->eraseFromParent(); 2363 NumShadow++; 2364 break; 2365 } 2366 } 2367} 2368 2369/// OptimizeIndvars - Now that IVUsesByStride is set up with all of the indvar 2370/// uses in the loop, look to see if we can eliminate some, in favor of using 2371/// common indvars for the different uses. 2372void LoopStrengthReduce::OptimizeIndvars(Loop *L) { 2373 // TODO: implement optzns here. 2374 2375 OptimizeShadowIV(L); 2376} 2377 2378bool LoopStrengthReduce::StrideMightBeShared(const SCEV* Stride, Loop *L, 2379 bool CheckPreInc) { 2380 int64_t SInt = cast<SCEVConstant>(Stride)->getValue()->getSExtValue(); 2381 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 2382 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 2383 IU->IVUsesByStride.find(IU->StrideOrder[i]); 2384 const SCEV *Share = SI->first; 2385 if (!isa<SCEVConstant>(SI->first) || Share == Stride) 2386 continue; 2387 int64_t SSInt = cast<SCEVConstant>(Share)->getValue()->getSExtValue(); 2388 if (SSInt == SInt) 2389 return true; // This can definitely be reused. 2390 if (unsigned(abs64(SSInt)) < SInt || (SSInt % SInt) != 0) 2391 continue; 2392 int64_t Scale = SSInt / SInt; 2393 bool AllUsesAreAddresses = true; 2394 bool AllUsesAreOutsideLoop = true; 2395 std::vector<BasedUser> UsersToProcess; 2396 const SCEV *CommonExprs = CollectIVUsers(SI->first, *SI->second, L, 2397 AllUsesAreAddresses, 2398 AllUsesAreOutsideLoop, 2399 UsersToProcess); 2400 if (AllUsesAreAddresses && 2401 ValidScale(!CommonExprs->isZero(), Scale, UsersToProcess)) { 2402 if (!CheckPreInc) 2403 return true; 2404 // Any pre-inc iv use? 2405 IVUsersOfOneStride &StrideUses = *IU->IVUsesByStride[Share]; 2406 for (ilist<IVStrideUse>::iterator I = StrideUses.Users.begin(), 2407 E = StrideUses.Users.end(); I != E; ++I) { 2408 if (!I->isUseOfPostIncrementedValue()) 2409 return true; 2410 } 2411 } 2412 } 2413 return false; 2414} 2415 2416/// isUsedByExitBranch - Return true if icmp is used by a loop terminating 2417/// conditional branch or it's and / or with other conditions before being used 2418/// as the condition. 2419static bool isUsedByExitBranch(ICmpInst *Cond, Loop *L) { 2420 BasicBlock *CondBB = Cond->getParent(); 2421 if (!L->isLoopExiting(CondBB)) 2422 return false; 2423 BranchInst *TermBr = dyn_cast<BranchInst>(CondBB->getTerminator()); 2424 if (!TermBr || !TermBr->isConditional()) 2425 return false; 2426 2427 Value *User = *Cond->use_begin(); 2428 Instruction *UserInst = dyn_cast<Instruction>(User); 2429 while (UserInst && 2430 (UserInst->getOpcode() == Instruction::And || 2431 UserInst->getOpcode() == Instruction::Or)) { 2432 if (!UserInst->hasOneUse() || UserInst->getParent() != CondBB) 2433 return false; 2434 User = *User->use_begin(); 2435 UserInst = dyn_cast<Instruction>(User); 2436 } 2437 return User == TermBr; 2438} 2439 2440static bool ShouldCountToZero(ICmpInst *Cond, IVStrideUse* &CondUse, 2441 ScalarEvolution *SE, Loop *L, 2442 const TargetLowering *TLI = 0) { 2443 if (!L->contains(Cond->getParent())) 2444 return false; 2445 2446 if (!isa<SCEVConstant>(CondUse->getOffset())) 2447 return false; 2448 2449 // Handle only tests for equality for the moment. 2450 if (!Cond->isEquality() || !Cond->hasOneUse()) 2451 return false; 2452 if (!isUsedByExitBranch(Cond, L)) 2453 return false; 2454 2455 Value *CondOp0 = Cond->getOperand(0); 2456 const SCEV *IV = SE->getSCEV(CondOp0); 2457 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 2458 if (!AR || !AR->isAffine()) 2459 return false; 2460 2461 const SCEVConstant *SC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 2462 if (!SC || SC->getValue()->getSExtValue() < 0) 2463 // If it's already counting down, don't do anything. 2464 return false; 2465 2466 // If the RHS of the comparison is not an loop invariant, the rewrite 2467 // cannot be done. Also bail out if it's already comparing against a zero. 2468 // If we are checking this before cmp stride optimization, check if it's 2469 // comparing against a already legal immediate. 2470 Value *RHS = Cond->getOperand(1); 2471 ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS); 2472 if (!L->isLoopInvariant(RHS) || 2473 (RHSC && RHSC->isZero()) || 2474 (RHSC && TLI && TLI->isLegalICmpImmediate(RHSC->getSExtValue()))) 2475 return false; 2476 2477 // Make sure the IV is only used for counting. Value may be preinc or 2478 // postinc; 2 uses in either case. 2479 if (!CondOp0->hasNUses(2)) 2480 return false; 2481 2482 return true; 2483} 2484 2485/// OptimizeLoopTermCond - Change loop terminating condition to use the 2486/// postinc iv when possible. 2487void LoopStrengthReduce::OptimizeLoopTermCond(Loop *L) { 2488 BasicBlock *LatchBlock = L->getLoopLatch(); 2489 bool LatchExit = L->isLoopExiting(LatchBlock); 2490 SmallVector<BasicBlock*, 8> ExitingBlocks; 2491 L->getExitingBlocks(ExitingBlocks); 2492 2493 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 2494 BasicBlock *ExitingBlock = ExitingBlocks[i]; 2495 2496 // Finally, get the terminating condition for the loop if possible. If we 2497 // can, we want to change it to use a post-incremented version of its 2498 // induction variable, to allow coalescing the live ranges for the IV into 2499 // one register value. 2500 2501 BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2502 if (!TermBr) 2503 continue; 2504 // FIXME: Overly conservative, termination condition could be an 'or' etc.. 2505 if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition())) 2506 continue; 2507 2508 // Search IVUsesByStride to find Cond's IVUse if there is one. 2509 IVStrideUse *CondUse = 0; 2510 const SCEV *CondStride = 0; 2511 ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition()); 2512 if (!FindIVUserForCond(Cond, CondUse, CondStride)) 2513 continue; 2514 2515 // If the latch block is exiting and it's not a single block loop, it's 2516 // not safe to use postinc iv in other exiting blocks. FIXME: overly 2517 // conservative? How about icmp stride optimization? 2518 bool UsePostInc = !(e > 1 && LatchExit && ExitingBlock != LatchBlock); 2519 if (UsePostInc && ExitingBlock != LatchBlock) { 2520 if (!Cond->hasOneUse()) 2521 // See below, we don't want the condition to be cloned. 2522 UsePostInc = false; 2523 else { 2524 // If exiting block is the latch block, we know it's safe and profitable 2525 // to transform the icmp to use post-inc iv. Otherwise do so only if it 2526 // would not reuse another iv and its iv would be reused by other uses. 2527 // We are optimizing for the case where the icmp is the only use of the 2528 // iv. 2529 IVUsersOfOneStride &StrideUses = *IU->IVUsesByStride[CondStride]; 2530 for (ilist<IVStrideUse>::iterator I = StrideUses.Users.begin(), 2531 E = StrideUses.Users.end(); I != E; ++I) { 2532 if (I->getUser() == Cond) 2533 continue; 2534 if (!I->isUseOfPostIncrementedValue()) { 2535 UsePostInc = false; 2536 break; 2537 } 2538 } 2539 } 2540 2541 // If iv for the stride might be shared and any of the users use pre-inc 2542 // iv might be used, then it's not safe to use post-inc iv. 2543 if (UsePostInc && 2544 isa<SCEVConstant>(CondStride) && 2545 StrideMightBeShared(CondStride, L, true)) 2546 UsePostInc = false; 2547 } 2548 2549 // If the trip count is computed in terms of a max (due to ScalarEvolution 2550 // being unable to find a sufficient guard, for example), change the loop 2551 // comparison to use SLT or ULT instead of NE. 2552 Cond = OptimizeMax(L, Cond, CondUse); 2553 2554 // If possible, change stride and operands of the compare instruction to 2555 // eliminate one stride. However, avoid rewriting the compare instruction 2556 // with an iv of new stride if it's likely the new stride uses will be 2557 // rewritten using the stride of the compare instruction. 2558 if (ExitingBlock == LatchBlock && isa<SCEVConstant>(CondStride)) { 2559 // If the condition stride is a constant and it's the only use, we might 2560 // want to optimize it first by turning it to count toward zero. 2561 if (!StrideMightBeShared(CondStride, L, false) && 2562 !ShouldCountToZero(Cond, CondUse, SE, L, TLI)) 2563 Cond = ChangeCompareStride(L, Cond, CondUse, CondStride); 2564 } 2565 2566 if (!UsePostInc) 2567 continue; 2568 2569 DEBUG(errs() << " Change loop exiting icmp to use postinc iv: " 2570 << *Cond << '\n'); 2571 2572 // It's possible for the setcc instruction to be anywhere in the loop, and 2573 // possible for it to have multiple users. If it is not immediately before 2574 // the exiting block branch, move it. 2575 if (&*++BasicBlock::iterator(Cond) != (Instruction*)TermBr) { 2576 if (Cond->hasOneUse()) { // Condition has a single use, just move it. 2577 Cond->moveBefore(TermBr); 2578 } else { 2579 // Otherwise, clone the terminating condition and insert into the 2580 // loopend. 2581 Cond = cast<ICmpInst>(Cond->clone()); 2582 Cond->setName(L->getHeader()->getName() + ".termcond"); 2583 ExitingBlock->getInstList().insert(TermBr, Cond); 2584 2585 // Clone the IVUse, as the old use still exists! 2586 IU->IVUsesByStride[CondStride]->addUser(CondUse->getOffset(), Cond, 2587 CondUse->getOperandValToReplace()); 2588 CondUse = &IU->IVUsesByStride[CondStride]->Users.back(); 2589 } 2590 } 2591 2592 // If we get to here, we know that we can transform the setcc instruction to 2593 // use the post-incremented version of the IV, allowing us to coalesce the 2594 // live ranges for the IV correctly. 2595 CondUse->setOffset(SE->getMinusSCEV(CondUse->getOffset(), CondStride)); 2596 CondUse->setIsUseOfPostIncrementedValue(true); 2597 Changed = true; 2598 2599 ++NumLoopCond; 2600 } 2601} 2602 2603bool LoopStrengthReduce::OptimizeLoopCountIVOfStride(const SCEV* &Stride, 2604 IVStrideUse* &CondUse, 2605 Loop *L) { 2606 // If the only use is an icmp of a loop exiting conditional branch, then 2607 // attempt the optimization. 2608 BasedUser User = BasedUser(*CondUse, SE); 2609 assert(isa<ICmpInst>(User.Inst) && "Expecting an ICMPInst!"); 2610 ICmpInst *Cond = cast<ICmpInst>(User.Inst); 2611 2612 // Less strict check now that compare stride optimization is done. 2613 if (!ShouldCountToZero(Cond, CondUse, SE, L)) 2614 return false; 2615 2616 Value *CondOp0 = Cond->getOperand(0); 2617 PHINode *PHIExpr = dyn_cast<PHINode>(CondOp0); 2618 Instruction *Incr; 2619 if (!PHIExpr) { 2620 // Value tested is postinc. Find the phi node. 2621 Incr = dyn_cast<BinaryOperator>(CondOp0); 2622 // FIXME: Just use User.OperandValToReplace here? 2623 if (!Incr || Incr->getOpcode() != Instruction::Add) 2624 return false; 2625 2626 PHIExpr = dyn_cast<PHINode>(Incr->getOperand(0)); 2627 if (!PHIExpr) 2628 return false; 2629 // 1 use for preinc value, the increment. 2630 if (!PHIExpr->hasOneUse()) 2631 return false; 2632 } else { 2633 assert(isa<PHINode>(CondOp0) && 2634 "Unexpected loop exiting counting instruction sequence!"); 2635 PHIExpr = cast<PHINode>(CondOp0); 2636 // Value tested is preinc. Find the increment. 2637 // A CmpInst is not a BinaryOperator; we depend on this. 2638 Instruction::use_iterator UI = PHIExpr->use_begin(); 2639 Incr = dyn_cast<BinaryOperator>(UI); 2640 if (!Incr) 2641 Incr = dyn_cast<BinaryOperator>(++UI); 2642 // One use for postinc value, the phi. Unnecessarily conservative? 2643 if (!Incr || !Incr->hasOneUse() || Incr->getOpcode() != Instruction::Add) 2644 return false; 2645 } 2646 2647 // Replace the increment with a decrement. 2648 DEBUG(errs() << "LSR: Examining use "); 2649 DEBUG(WriteAsOperand(errs(), CondOp0, /*PrintType=*/false)); 2650 DEBUG(errs() << " in Inst: " << *Cond << '\n'); 2651 BinaryOperator *Decr = BinaryOperator::Create(Instruction::Sub, 2652 Incr->getOperand(0), Incr->getOperand(1), "tmp", Incr); 2653 Incr->replaceAllUsesWith(Decr); 2654 Incr->eraseFromParent(); 2655 2656 // Substitute endval-startval for the original startval, and 0 for the 2657 // original endval. Since we're only testing for equality this is OK even 2658 // if the computation wraps around. 2659 BasicBlock *Preheader = L->getLoopPreheader(); 2660 Instruction *PreInsertPt = Preheader->getTerminator(); 2661 unsigned InBlock = L->contains(PHIExpr->getIncomingBlock(0)) ? 1 : 0; 2662 Value *StartVal = PHIExpr->getIncomingValue(InBlock); 2663 Value *EndVal = Cond->getOperand(1); 2664 DEBUG(errs() << " Optimize loop counting iv to count down [" 2665 << *EndVal << " .. " << *StartVal << "]\n"); 2666 2667 // FIXME: check for case where both are constant. 2668 Constant* Zero = ConstantInt::get(Cond->getOperand(1)->getType(), 0); 2669 BinaryOperator *NewStartVal = BinaryOperator::Create(Instruction::Sub, 2670 EndVal, StartVal, "tmp", PreInsertPt); 2671 PHIExpr->setIncomingValue(InBlock, NewStartVal); 2672 Cond->setOperand(1, Zero); 2673 DEBUG(errs() << " New icmp: " << *Cond << "\n"); 2674 2675 int64_t SInt = cast<SCEVConstant>(Stride)->getValue()->getSExtValue(); 2676 const SCEV *NewStride = 0; 2677 bool Found = false; 2678 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 2679 const SCEV *OldStride = IU->StrideOrder[i]; 2680 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OldStride)) 2681 if (SC->getValue()->getSExtValue() == -SInt) { 2682 Found = true; 2683 NewStride = OldStride; 2684 break; 2685 } 2686 } 2687 2688 if (!Found) 2689 NewStride = SE->getIntegerSCEV(-SInt, Stride->getType()); 2690 IU->AddUser(NewStride, CondUse->getOffset(), Cond, Cond->getOperand(0)); 2691 IU->IVUsesByStride[Stride]->removeUser(CondUse); 2692 2693 CondUse = &IU->IVUsesByStride[NewStride]->Users.back(); 2694 Stride = NewStride; 2695 2696 ++NumCountZero; 2697 2698 return true; 2699} 2700 2701/// OptimizeLoopCountIV - If, after all sharing of IVs, the IV used for deciding 2702/// when to exit the loop is used only for that purpose, try to rearrange things 2703/// so it counts down to a test against zero. 2704bool LoopStrengthReduce::OptimizeLoopCountIV(Loop *L) { 2705 bool ThisChanged = false; 2706 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 2707 const SCEV *Stride = IU->StrideOrder[i]; 2708 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 2709 IU->IVUsesByStride.find(Stride); 2710 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 2711 // FIXME: Generalize to non-affine IV's. 2712 if (!SI->first->isLoopInvariant(L)) 2713 continue; 2714 // If stride is a constant and it has an icmpinst use, check if we can 2715 // optimize the loop to count down. 2716 if (isa<SCEVConstant>(Stride) && SI->second->Users.size() == 1) { 2717 Instruction *User = SI->second->Users.begin()->getUser(); 2718 if (!isa<ICmpInst>(User)) 2719 continue; 2720 const SCEV *CondStride = Stride; 2721 IVStrideUse *Use = &*SI->second->Users.begin(); 2722 if (!OptimizeLoopCountIVOfStride(CondStride, Use, L)) 2723 continue; 2724 ThisChanged = true; 2725 2726 // Now check if it's possible to reuse this iv for other stride uses. 2727 for (unsigned j = 0, ee = IU->StrideOrder.size(); j != ee; ++j) { 2728 const SCEV *SStride = IU->StrideOrder[j]; 2729 if (SStride == CondStride) 2730 continue; 2731 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SII = 2732 IU->IVUsesByStride.find(SStride); 2733 assert(SII != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 2734 // FIXME: Generalize to non-affine IV's. 2735 if (!SII->first->isLoopInvariant(L)) 2736 continue; 2737 // FIXME: Rewrite other stride using CondStride. 2738 } 2739 } 2740 } 2741 2742 Changed |= ThisChanged; 2743 return ThisChanged; 2744} 2745 2746bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) { 2747 IU = &getAnalysis<IVUsers>(); 2748 LI = &getAnalysis<LoopInfo>(); 2749 DT = &getAnalysis<DominatorTree>(); 2750 SE = &getAnalysis<ScalarEvolution>(); 2751 Changed = false; 2752 2753 // If LoopSimplify form is not available, stay out of trouble. 2754 if (!L->getLoopPreheader() || !L->getLoopLatch()) 2755 return false; 2756 2757 if (!IU->IVUsesByStride.empty()) { 2758 DEBUG(errs() << "\nLSR on \"" << L->getHeader()->getParent()->getName() 2759 << "\" "; 2760 L->dump()); 2761 2762 // Sort the StrideOrder so we process larger strides first. 2763 std::stable_sort(IU->StrideOrder.begin(), IU->StrideOrder.end(), 2764 StrideCompare(SE)); 2765 2766 // Optimize induction variables. Some indvar uses can be transformed to use 2767 // strides that will be needed for other purposes. A common example of this 2768 // is the exit test for the loop, which can often be rewritten to use the 2769 // computation of some other indvar to decide when to terminate the loop. 2770 OptimizeIndvars(L); 2771 2772 // Change loop terminating condition to use the postinc iv when possible 2773 // and optimize loop terminating compare. FIXME: Move this after 2774 // StrengthReduceIVUsersOfStride? 2775 OptimizeLoopTermCond(L); 2776 2777 // FIXME: We can shrink overlarge IV's here. e.g. if the code has 2778 // computation in i64 values and the target doesn't support i64, demote 2779 // the computation to 32-bit if safe. 2780 2781 // FIXME: Attempt to reuse values across multiple IV's. In particular, we 2782 // could have something like "for(i) { foo(i*8); bar(i*16) }", which should 2783 // be codegened as "for (j = 0;; j+=8) { foo(j); bar(j+j); }" on X86/PPC. 2784 // Need to be careful that IV's are all the same type. Only works for 2785 // intptr_t indvars. 2786 2787 // IVsByStride keeps IVs for one particular loop. 2788 assert(IVsByStride.empty() && "Stale entries in IVsByStride?"); 2789 2790 StrengthReduceIVUsers(L); 2791 2792 // After all sharing is done, see if we can adjust the loop to test against 2793 // zero instead of counting up to a maximum. This is usually faster. 2794 OptimizeLoopCountIV(L); 2795 } 2796 2797 // We're done analyzing this loop; release all the state we built up for it. 2798 IVsByStride.clear(); 2799 StrideNoReuse.clear(); 2800 2801 // Clean up after ourselves 2802 if (!DeadInsts.empty()) 2803 DeleteTriviallyDeadInstructions(); 2804 2805 // At this point, it is worth checking to see if any recurrence PHIs are also 2806 // dead, so that we can remove them as well. 2807 DeleteDeadPHIs(L->getHeader()); 2808 2809 return Changed; 2810} 2811