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