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 // Terminology note: this code has a lot of handling for "post-increment" or 21 // "post-inc" users. This is not talking about post-increment addressing modes; 22 // it is instead talking about code like this: 23 // 24 // %i = phi [ 0, %entry ], [ %i.next, %latch ] 25 // ... 26 // %i.next = add %i, 1 27 // %c = icmp eq %i.next, %n 28 // 29 // The SCEV for %i is {0,+,1}<%L>. The SCEV for %i.next is {1,+,1}<%L>, however 30 // it's useful to think about these as the same register, with some uses using 31 // the value of the register before the add and some using it after. In this 32 // example, the icmp is a post-increment user, since it uses %i.next, which is 33 // the value of the induction variable after the increment. The other common 34 // case of post-increment users is users outside the loop. 35 // 36 // TODO: More sophistication in the way Formulae are generated and filtered. 37 // 38 // TODO: Handle multiple loops at a time. 39 // 40 // TODO: Should the addressing mode BaseGV be changed to a ConstantExpr instead 41 // of a GlobalValue? 42 // 43 // TODO: When truncation is free, truncate ICmp users' operands to make it a 44 // smaller encoding (on x86 at least). 45 // 46 // TODO: When a negated register is used by an add (such as in a list of 47 // multiple base registers, or as the increment expression in an addrec), 48 // we may not actually need both reg and (-1 * reg) in registers; the 49 // negation can be implemented by using a sub instead of an add. The 50 // lack of support for taking this into consideration when making 51 // register pressure decisions is partly worked around by the "Special" 52 // use kind. 53 // 54 //===----------------------------------------------------------------------===// 55 56 #include "llvm/Transforms/Scalar.h" 57 #include "llvm/ADT/DenseSet.h" 58 #include "llvm/ADT/Hashing.h" 59 #include "llvm/ADT/STLExtras.h" 60 #include "llvm/ADT/SetVector.h" 61 #include "llvm/ADT/SmallBitVector.h" 62 #include "llvm/Analysis/IVUsers.h" 63 #include "llvm/Analysis/LoopPass.h" 64 #include "llvm/Analysis/ScalarEvolutionExpander.h" 65 #include "llvm/Analysis/TargetTransformInfo.h" 66 #include "llvm/IR/Constants.h" 67 #include "llvm/IR/DerivedTypes.h" 68 #include "llvm/IR/Dominators.h" 69 #include "llvm/IR/Instructions.h" 70 #include "llvm/IR/IntrinsicInst.h" 71 #include "llvm/IR/Module.h" 72 #include "llvm/IR/ValueHandle.h" 73 #include "llvm/Support/CommandLine.h" 74 #include "llvm/Support/Debug.h" 75 #include "llvm/Support/raw_ostream.h" 76 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 77 #include "llvm/Transforms/Utils/Local.h" 78 #include <algorithm> 79 using namespace llvm; 80 81 #define DEBUG_TYPE "loop-reduce" 82 83 /// MaxIVUsers is an arbitrary threshold that provides an early opportunitiy for 84 /// bail out. This threshold is far beyond the number of users that LSR can 85 /// conceivably solve, so it should not affect generated code, but catches the 86 /// worst cases before LSR burns too much compile time and stack space. 87 static const unsigned MaxIVUsers = 200; 88 89 // Temporary flag to cleanup congruent phis after LSR phi expansion. 90 // It's currently disabled until we can determine whether it's truly useful or 91 // not. The flag should be removed after the v3.0 release. 92 // This is now needed for ivchains. 93 static cl::opt<bool> EnablePhiElim( 94 "enable-lsr-phielim", cl::Hidden, cl::init(true), 95 cl::desc("Enable LSR phi elimination")); 96 97 #ifndef NDEBUG 98 // Stress test IV chain generation. 99 static cl::opt<bool> StressIVChain( 100 "stress-ivchain", cl::Hidden, cl::init(false), 101 cl::desc("Stress test LSR IV chains")); 102 #else 103 static bool StressIVChain = false; 104 #endif 105 106 namespace { 107 108 /// RegSortData - This class holds data which is used to order reuse candidates. 109 class RegSortData { 110 public: 111 /// UsedByIndices - This represents the set of LSRUse indices which reference 112 /// a particular register. 113 SmallBitVector UsedByIndices; 114 115 void print(raw_ostream &OS) const; 116 void dump() const; 117 }; 118 119 } 120 121 void RegSortData::print(raw_ostream &OS) const { 122 OS << "[NumUses=" << UsedByIndices.count() << ']'; 123 } 124 125 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 126 void RegSortData::dump() const { 127 print(errs()); errs() << '\n'; 128 } 129 #endif 130 131 namespace { 132 133 /// RegUseTracker - Map register candidates to information about how they are 134 /// used. 135 class RegUseTracker { 136 typedef DenseMap<const SCEV *, RegSortData> RegUsesTy; 137 138 RegUsesTy RegUsesMap; 139 SmallVector<const SCEV *, 16> RegSequence; 140 141 public: 142 void CountRegister(const SCEV *Reg, size_t LUIdx); 143 void DropRegister(const SCEV *Reg, size_t LUIdx); 144 void SwapAndDropUse(size_t LUIdx, size_t LastLUIdx); 145 146 bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const; 147 148 const SmallBitVector &getUsedByIndices(const SCEV *Reg) const; 149 150 void clear(); 151 152 typedef SmallVectorImpl<const SCEV *>::iterator iterator; 153 typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator; 154 iterator begin() { return RegSequence.begin(); } 155 iterator end() { return RegSequence.end(); } 156 const_iterator begin() const { return RegSequence.begin(); } 157 const_iterator end() const { return RegSequence.end(); } 158 }; 159 160 } 161 162 void 163 RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) { 164 std::pair<RegUsesTy::iterator, bool> Pair = 165 RegUsesMap.insert(std::make_pair(Reg, RegSortData())); 166 RegSortData &RSD = Pair.first->second; 167 if (Pair.second) 168 RegSequence.push_back(Reg); 169 RSD.UsedByIndices.resize(std::max(RSD.UsedByIndices.size(), LUIdx + 1)); 170 RSD.UsedByIndices.set(LUIdx); 171 } 172 173 void 174 RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) { 175 RegUsesTy::iterator It = RegUsesMap.find(Reg); 176 assert(It != RegUsesMap.end()); 177 RegSortData &RSD = It->second; 178 assert(RSD.UsedByIndices.size() > LUIdx); 179 RSD.UsedByIndices.reset(LUIdx); 180 } 181 182 void 183 RegUseTracker::SwapAndDropUse(size_t LUIdx, size_t LastLUIdx) { 184 assert(LUIdx <= LastLUIdx); 185 186 // Update RegUses. The data structure is not optimized for this purpose; 187 // we must iterate through it and update each of the bit vectors. 188 for (RegUsesTy::iterator I = RegUsesMap.begin(), E = RegUsesMap.end(); 189 I != E; ++I) { 190 SmallBitVector &UsedByIndices = I->second.UsedByIndices; 191 if (LUIdx < UsedByIndices.size()) 192 UsedByIndices[LUIdx] = 193 LastLUIdx < UsedByIndices.size() ? UsedByIndices[LastLUIdx] : 0; 194 UsedByIndices.resize(std::min(UsedByIndices.size(), LastLUIdx)); 195 } 196 } 197 198 bool 199 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const { 200 RegUsesTy::const_iterator I = RegUsesMap.find(Reg); 201 if (I == RegUsesMap.end()) 202 return false; 203 const SmallBitVector &UsedByIndices = I->second.UsedByIndices; 204 int i = UsedByIndices.find_first(); 205 if (i == -1) return false; 206 if ((size_t)i != LUIdx) return true; 207 return UsedByIndices.find_next(i) != -1; 208 } 209 210 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const { 211 RegUsesTy::const_iterator I = RegUsesMap.find(Reg); 212 assert(I != RegUsesMap.end() && "Unknown register!"); 213 return I->second.UsedByIndices; 214 } 215 216 void RegUseTracker::clear() { 217 RegUsesMap.clear(); 218 RegSequence.clear(); 219 } 220 221 namespace { 222 223 /// Formula - This class holds information that describes a formula for 224 /// computing satisfying a use. It may include broken-out immediates and scaled 225 /// registers. 226 struct Formula { 227 /// Global base address used for complex addressing. 228 GlobalValue *BaseGV; 229 230 /// Base offset for complex addressing. 231 int64_t BaseOffset; 232 233 /// Whether any complex addressing has a base register. 234 bool HasBaseReg; 235 236 /// The scale of any complex addressing. 237 int64_t Scale; 238 239 /// BaseRegs - The list of "base" registers for this use. When this is 240 /// non-empty. The canonical representation of a formula is 241 /// 1. BaseRegs.size > 1 implies ScaledReg != NULL and 242 /// 2. ScaledReg != NULL implies Scale != 1 || !BaseRegs.empty(). 243 /// #1 enforces that the scaled register is always used when at least two 244 /// registers are needed by the formula: e.g., reg1 + reg2 is reg1 + 1 * reg2. 245 /// #2 enforces that 1 * reg is reg. 246 /// This invariant can be temporarly broken while building a formula. 247 /// However, every formula inserted into the LSRInstance must be in canonical 248 /// form. 249 SmallVector<const SCEV *, 4> BaseRegs; 250 251 /// ScaledReg - The 'scaled' register for this use. This should be non-null 252 /// when Scale is not zero. 253 const SCEV *ScaledReg; 254 255 /// UnfoldedOffset - An additional constant offset which added near the 256 /// use. This requires a temporary register, but the offset itself can 257 /// live in an add immediate field rather than a register. 258 int64_t UnfoldedOffset; 259 260 Formula() 261 : BaseGV(nullptr), BaseOffset(0), HasBaseReg(false), Scale(0), 262 ScaledReg(nullptr), UnfoldedOffset(0) {} 263 264 void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE); 265 266 bool isCanonical() const; 267 268 void Canonicalize(); 269 270 bool Unscale(); 271 272 size_t getNumRegs() const; 273 Type *getType() const; 274 275 void DeleteBaseReg(const SCEV *&S); 276 277 bool referencesReg(const SCEV *S) const; 278 bool hasRegsUsedByUsesOtherThan(size_t LUIdx, 279 const RegUseTracker &RegUses) const; 280 281 void print(raw_ostream &OS) const; 282 void dump() const; 283 }; 284 285 } 286 287 /// DoInitialMatch - Recursion helper for InitialMatch. 288 static void DoInitialMatch(const SCEV *S, Loop *L, 289 SmallVectorImpl<const SCEV *> &Good, 290 SmallVectorImpl<const SCEV *> &Bad, 291 ScalarEvolution &SE) { 292 // Collect expressions which properly dominate the loop header. 293 if (SE.properlyDominates(S, L->getHeader())) { 294 Good.push_back(S); 295 return; 296 } 297 298 // Look at add operands. 299 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 300 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 301 I != E; ++I) 302 DoInitialMatch(*I, L, Good, Bad, SE); 303 return; 304 } 305 306 // Look at addrec operands. 307 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 308 if (!AR->getStart()->isZero()) { 309 DoInitialMatch(AR->getStart(), L, Good, Bad, SE); 310 DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0), 311 AR->getStepRecurrence(SE), 312 // FIXME: AR->getNoWrapFlags() 313 AR->getLoop(), SCEV::FlagAnyWrap), 314 L, Good, Bad, SE); 315 return; 316 } 317 318 // Handle a multiplication by -1 (negation) if it didn't fold. 319 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) 320 if (Mul->getOperand(0)->isAllOnesValue()) { 321 SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end()); 322 const SCEV *NewMul = SE.getMulExpr(Ops); 323 324 SmallVector<const SCEV *, 4> MyGood; 325 SmallVector<const SCEV *, 4> MyBad; 326 DoInitialMatch(NewMul, L, MyGood, MyBad, SE); 327 const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue( 328 SE.getEffectiveSCEVType(NewMul->getType()))); 329 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(), 330 E = MyGood.end(); I != E; ++I) 331 Good.push_back(SE.getMulExpr(NegOne, *I)); 332 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(), 333 E = MyBad.end(); I != E; ++I) 334 Bad.push_back(SE.getMulExpr(NegOne, *I)); 335 return; 336 } 337 338 // Ok, we can't do anything interesting. Just stuff the whole thing into a 339 // register and hope for the best. 340 Bad.push_back(S); 341 } 342 343 /// InitialMatch - Incorporate loop-variant parts of S into this Formula, 344 /// attempting to keep all loop-invariant and loop-computable values in a 345 /// single base register. 346 void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) { 347 SmallVector<const SCEV *, 4> Good; 348 SmallVector<const SCEV *, 4> Bad; 349 DoInitialMatch(S, L, Good, Bad, SE); 350 if (!Good.empty()) { 351 const SCEV *Sum = SE.getAddExpr(Good); 352 if (!Sum->isZero()) 353 BaseRegs.push_back(Sum); 354 HasBaseReg = true; 355 } 356 if (!Bad.empty()) { 357 const SCEV *Sum = SE.getAddExpr(Bad); 358 if (!Sum->isZero()) 359 BaseRegs.push_back(Sum); 360 HasBaseReg = true; 361 } 362 Canonicalize(); 363 } 364 365 /// \brief Check whether or not this formula statisfies the canonical 366 /// representation. 367 /// \see Formula::BaseRegs. 368 bool Formula::isCanonical() const { 369 if (ScaledReg) 370 return Scale != 1 || !BaseRegs.empty(); 371 return BaseRegs.size() <= 1; 372 } 373 374 /// \brief Helper method to morph a formula into its canonical representation. 375 /// \see Formula::BaseRegs. 376 /// Every formula having more than one base register, must use the ScaledReg 377 /// field. Otherwise, we would have to do special cases everywhere in LSR 378 /// to treat reg1 + reg2 + ... the same way as reg1 + 1*reg2 + ... 379 /// On the other hand, 1*reg should be canonicalized into reg. 380 void Formula::Canonicalize() { 381 if (isCanonical()) 382 return; 383 // So far we did not need this case. This is easy to implement but it is 384 // useless to maintain dead code. Beside it could hurt compile time. 385 assert(!BaseRegs.empty() && "1*reg => reg, should not be needed."); 386 // Keep the invariant sum in BaseRegs and one of the variant sum in ScaledReg. 387 ScaledReg = BaseRegs.back(); 388 BaseRegs.pop_back(); 389 Scale = 1; 390 size_t BaseRegsSize = BaseRegs.size(); 391 size_t Try = 0; 392 // If ScaledReg is an invariant, try to find a variant expression. 393 while (Try < BaseRegsSize && !isa<SCEVAddRecExpr>(ScaledReg)) 394 std::swap(ScaledReg, BaseRegs[Try++]); 395 } 396 397 /// \brief Get rid of the scale in the formula. 398 /// In other words, this method morphes reg1 + 1*reg2 into reg1 + reg2. 399 /// \return true if it was possible to get rid of the scale, false otherwise. 400 /// \note After this operation the formula may not be in the canonical form. 401 bool Formula::Unscale() { 402 if (Scale != 1) 403 return false; 404 Scale = 0; 405 BaseRegs.push_back(ScaledReg); 406 ScaledReg = nullptr; 407 return true; 408 } 409 410 /// getNumRegs - Return the total number of register operands used by this 411 /// formula. This does not include register uses implied by non-constant 412 /// addrec strides. 413 size_t Formula::getNumRegs() const { 414 return !!ScaledReg + BaseRegs.size(); 415 } 416 417 /// getType - Return the type of this formula, if it has one, or null 418 /// otherwise. This type is meaningless except for the bit size. 419 Type *Formula::getType() const { 420 return !BaseRegs.empty() ? BaseRegs.front()->getType() : 421 ScaledReg ? ScaledReg->getType() : 422 BaseGV ? BaseGV->getType() : 423 nullptr; 424 } 425 426 /// DeleteBaseReg - Delete the given base reg from the BaseRegs list. 427 void Formula::DeleteBaseReg(const SCEV *&S) { 428 if (&S != &BaseRegs.back()) 429 std::swap(S, BaseRegs.back()); 430 BaseRegs.pop_back(); 431 } 432 433 /// referencesReg - Test if this formula references the given register. 434 bool Formula::referencesReg(const SCEV *S) const { 435 return S == ScaledReg || 436 std::find(BaseRegs.begin(), BaseRegs.end(), S) != BaseRegs.end(); 437 } 438 439 /// hasRegsUsedByUsesOtherThan - Test whether this formula uses registers 440 /// which are used by uses other than the use with the given index. 441 bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx, 442 const RegUseTracker &RegUses) const { 443 if (ScaledReg) 444 if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx)) 445 return true; 446 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), 447 E = BaseRegs.end(); I != E; ++I) 448 if (RegUses.isRegUsedByUsesOtherThan(*I, LUIdx)) 449 return true; 450 return false; 451 } 452 453 void Formula::print(raw_ostream &OS) const { 454 bool First = true; 455 if (BaseGV) { 456 if (!First) OS << " + "; else First = false; 457 BaseGV->printAsOperand(OS, /*PrintType=*/false); 458 } 459 if (BaseOffset != 0) { 460 if (!First) OS << " + "; else First = false; 461 OS << BaseOffset; 462 } 463 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), 464 E = BaseRegs.end(); I != E; ++I) { 465 if (!First) OS << " + "; else First = false; 466 OS << "reg(" << **I << ')'; 467 } 468 if (HasBaseReg && BaseRegs.empty()) { 469 if (!First) OS << " + "; else First = false; 470 OS << "**error: HasBaseReg**"; 471 } else if (!HasBaseReg && !BaseRegs.empty()) { 472 if (!First) OS << " + "; else First = false; 473 OS << "**error: !HasBaseReg**"; 474 } 475 if (Scale != 0) { 476 if (!First) OS << " + "; else First = false; 477 OS << Scale << "*reg("; 478 if (ScaledReg) 479 OS << *ScaledReg; 480 else 481 OS << "<unknown>"; 482 OS << ')'; 483 } 484 if (UnfoldedOffset != 0) { 485 if (!First) OS << " + "; 486 OS << "imm(" << UnfoldedOffset << ')'; 487 } 488 } 489 490 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 491 void Formula::dump() const { 492 print(errs()); errs() << '\n'; 493 } 494 #endif 495 496 /// isAddRecSExtable - Return true if the given addrec can be sign-extended 497 /// without changing its value. 498 static bool isAddRecSExtable(const SCEVAddRecExpr *AR, ScalarEvolution &SE) { 499 Type *WideTy = 500 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(AR->getType()) + 1); 501 return isa<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy)); 502 } 503 504 /// isAddSExtable - Return true if the given add can be sign-extended 505 /// without changing its value. 506 static bool isAddSExtable(const SCEVAddExpr *A, ScalarEvolution &SE) { 507 Type *WideTy = 508 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(A->getType()) + 1); 509 return isa<SCEVAddExpr>(SE.getSignExtendExpr(A, WideTy)); 510 } 511 512 /// isMulSExtable - Return true if the given mul can be sign-extended 513 /// without changing its value. 514 static bool isMulSExtable(const SCEVMulExpr *M, ScalarEvolution &SE) { 515 Type *WideTy = 516 IntegerType::get(SE.getContext(), 517 SE.getTypeSizeInBits(M->getType()) * M->getNumOperands()); 518 return isa<SCEVMulExpr>(SE.getSignExtendExpr(M, WideTy)); 519 } 520 521 /// getExactSDiv - Return an expression for LHS /s RHS, if it can be determined 522 /// and if the remainder is known to be zero, or null otherwise. If 523 /// IgnoreSignificantBits is true, expressions like (X * Y) /s Y are simplified 524 /// to Y, ignoring that the multiplication may overflow, which is useful when 525 /// the result will be used in a context where the most significant bits are 526 /// ignored. 527 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS, 528 ScalarEvolution &SE, 529 bool IgnoreSignificantBits = false) { 530 // Handle the trivial case, which works for any SCEV type. 531 if (LHS == RHS) 532 return SE.getConstant(LHS->getType(), 1); 533 534 // Handle a few RHS special cases. 535 const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS); 536 if (RC) { 537 const APInt &RA = RC->getValue()->getValue(); 538 // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do 539 // some folding. 540 if (RA.isAllOnesValue()) 541 return SE.getMulExpr(LHS, RC); 542 // Handle x /s 1 as x. 543 if (RA == 1) 544 return LHS; 545 } 546 547 // Check for a division of a constant by a constant. 548 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) { 549 if (!RC) 550 return nullptr; 551 const APInt &LA = C->getValue()->getValue(); 552 const APInt &RA = RC->getValue()->getValue(); 553 if (LA.srem(RA) != 0) 554 return nullptr; 555 return SE.getConstant(LA.sdiv(RA)); 556 } 557 558 // Distribute the sdiv over addrec operands, if the addrec doesn't overflow. 559 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) { 560 if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) { 561 const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE, 562 IgnoreSignificantBits); 563 if (!Step) return nullptr; 564 const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE, 565 IgnoreSignificantBits); 566 if (!Start) return nullptr; 567 // FlagNW is independent of the start value, step direction, and is 568 // preserved with smaller magnitude steps. 569 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 570 return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap); 571 } 572 return nullptr; 573 } 574 575 // Distribute the sdiv over add operands, if the add doesn't overflow. 576 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) { 577 if (IgnoreSignificantBits || isAddSExtable(Add, SE)) { 578 SmallVector<const SCEV *, 8> Ops; 579 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 580 I != E; ++I) { 581 const SCEV *Op = getExactSDiv(*I, RHS, SE, 582 IgnoreSignificantBits); 583 if (!Op) return nullptr; 584 Ops.push_back(Op); 585 } 586 return SE.getAddExpr(Ops); 587 } 588 return nullptr; 589 } 590 591 // Check for a multiply operand that we can pull RHS out of. 592 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(LHS)) { 593 if (IgnoreSignificantBits || isMulSExtable(Mul, SE)) { 594 SmallVector<const SCEV *, 4> Ops; 595 bool Found = false; 596 for (SCEVMulExpr::op_iterator I = Mul->op_begin(), E = Mul->op_end(); 597 I != E; ++I) { 598 const SCEV *S = *I; 599 if (!Found) 600 if (const SCEV *Q = getExactSDiv(S, RHS, SE, 601 IgnoreSignificantBits)) { 602 S = Q; 603 Found = true; 604 } 605 Ops.push_back(S); 606 } 607 return Found ? SE.getMulExpr(Ops) : nullptr; 608 } 609 return nullptr; 610 } 611 612 // Otherwise we don't know. 613 return nullptr; 614 } 615 616 /// ExtractImmediate - If S involves the addition of a constant integer value, 617 /// return that integer value, and mutate S to point to a new SCEV with that 618 /// value excluded. 619 static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) { 620 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 621 if (C->getValue()->getValue().getMinSignedBits() <= 64) { 622 S = SE.getConstant(C->getType(), 0); 623 return C->getValue()->getSExtValue(); 624 } 625 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 626 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end()); 627 int64_t Result = ExtractImmediate(NewOps.front(), SE); 628 if (Result != 0) 629 S = SE.getAddExpr(NewOps); 630 return Result; 631 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 632 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end()); 633 int64_t Result = ExtractImmediate(NewOps.front(), SE); 634 if (Result != 0) 635 S = SE.getAddRecExpr(NewOps, AR->getLoop(), 636 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 637 SCEV::FlagAnyWrap); 638 return Result; 639 } 640 return 0; 641 } 642 643 /// ExtractSymbol - If S involves the addition of a GlobalValue address, 644 /// return that symbol, and mutate S to point to a new SCEV with that 645 /// value excluded. 646 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) { 647 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 648 if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) { 649 S = SE.getConstant(GV->getType(), 0); 650 return GV; 651 } 652 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 653 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end()); 654 GlobalValue *Result = ExtractSymbol(NewOps.back(), SE); 655 if (Result) 656 S = SE.getAddExpr(NewOps); 657 return Result; 658 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 659 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end()); 660 GlobalValue *Result = ExtractSymbol(NewOps.front(), SE); 661 if (Result) 662 S = SE.getAddRecExpr(NewOps, AR->getLoop(), 663 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 664 SCEV::FlagAnyWrap); 665 return Result; 666 } 667 return nullptr; 668 } 669 670 /// isAddressUse - Returns true if the specified instruction is using the 671 /// specified value as an address. 672 static bool isAddressUse(Instruction *Inst, Value *OperandVal) { 673 bool isAddress = isa<LoadInst>(Inst); 674 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 675 if (SI->getOperand(1) == OperandVal) 676 isAddress = true; 677 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 678 // Addressing modes can also be folded into prefetches and a variety 679 // of intrinsics. 680 switch (II->getIntrinsicID()) { 681 default: break; 682 case Intrinsic::prefetch: 683 case Intrinsic::x86_sse_storeu_ps: 684 case Intrinsic::x86_sse2_storeu_pd: 685 case Intrinsic::x86_sse2_storeu_dq: 686 case Intrinsic::x86_sse2_storel_dq: 687 if (II->getArgOperand(0) == OperandVal) 688 isAddress = true; 689 break; 690 } 691 } 692 return isAddress; 693 } 694 695 /// getAccessType - Return the type of the memory being accessed. 696 static Type *getAccessType(const Instruction *Inst) { 697 Type *AccessTy = Inst->getType(); 698 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) 699 AccessTy = SI->getOperand(0)->getType(); 700 else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 701 // Addressing modes can also be folded into prefetches and a variety 702 // of intrinsics. 703 switch (II->getIntrinsicID()) { 704 default: break; 705 case Intrinsic::x86_sse_storeu_ps: 706 case Intrinsic::x86_sse2_storeu_pd: 707 case Intrinsic::x86_sse2_storeu_dq: 708 case Intrinsic::x86_sse2_storel_dq: 709 AccessTy = II->getArgOperand(0)->getType(); 710 break; 711 } 712 } 713 714 // All pointers have the same requirements, so canonicalize them to an 715 // arbitrary pointer type to minimize variation. 716 if (PointerType *PTy = dyn_cast<PointerType>(AccessTy)) 717 AccessTy = PointerType::get(IntegerType::get(PTy->getContext(), 1), 718 PTy->getAddressSpace()); 719 720 return AccessTy; 721 } 722 723 /// isExistingPhi - Return true if this AddRec is already a phi in its loop. 724 static bool isExistingPhi(const SCEVAddRecExpr *AR, ScalarEvolution &SE) { 725 for (BasicBlock::iterator I = AR->getLoop()->getHeader()->begin(); 726 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 727 if (SE.isSCEVable(PN->getType()) && 728 (SE.getEffectiveSCEVType(PN->getType()) == 729 SE.getEffectiveSCEVType(AR->getType())) && 730 SE.getSCEV(PN) == AR) 731 return true; 732 } 733 return false; 734 } 735 736 /// Check if expanding this expression is likely to incur significant cost. This 737 /// is tricky because SCEV doesn't track which expressions are actually computed 738 /// by the current IR. 739 /// 740 /// We currently allow expansion of IV increments that involve adds, 741 /// multiplication by constants, and AddRecs from existing phis. 742 /// 743 /// TODO: Allow UDivExpr if we can find an existing IV increment that is an 744 /// obvious multiple of the UDivExpr. 745 static bool isHighCostExpansion(const SCEV *S, 746 SmallPtrSetImpl<const SCEV*> &Processed, 747 ScalarEvolution &SE) { 748 // Zero/One operand expressions 749 switch (S->getSCEVType()) { 750 case scUnknown: 751 case scConstant: 752 return false; 753 case scTruncate: 754 return isHighCostExpansion(cast<SCEVTruncateExpr>(S)->getOperand(), 755 Processed, SE); 756 case scZeroExtend: 757 return isHighCostExpansion(cast<SCEVZeroExtendExpr>(S)->getOperand(), 758 Processed, SE); 759 case scSignExtend: 760 return isHighCostExpansion(cast<SCEVSignExtendExpr>(S)->getOperand(), 761 Processed, SE); 762 } 763 764 if (!Processed.insert(S).second) 765 return false; 766 767 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 768 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 769 I != E; ++I) { 770 if (isHighCostExpansion(*I, Processed, SE)) 771 return true; 772 } 773 return false; 774 } 775 776 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 777 if (Mul->getNumOperands() == 2) { 778 // Multiplication by a constant is ok 779 if (isa<SCEVConstant>(Mul->getOperand(0))) 780 return isHighCostExpansion(Mul->getOperand(1), Processed, SE); 781 782 // If we have the value of one operand, check if an existing 783 // multiplication already generates this expression. 784 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Mul->getOperand(1))) { 785 Value *UVal = U->getValue(); 786 for (User *UR : UVal->users()) { 787 // If U is a constant, it may be used by a ConstantExpr. 788 Instruction *UI = dyn_cast<Instruction>(UR); 789 if (UI && UI->getOpcode() == Instruction::Mul && 790 SE.isSCEVable(UI->getType())) { 791 return SE.getSCEV(UI) == Mul; 792 } 793 } 794 } 795 } 796 } 797 798 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 799 if (isExistingPhi(AR, SE)) 800 return false; 801 } 802 803 // Fow now, consider any other type of expression (div/mul/min/max) high cost. 804 return true; 805 } 806 807 /// DeleteTriviallyDeadInstructions - If any of the instructions is the 808 /// specified set are trivially dead, delete them and see if this makes any of 809 /// their operands subsequently dead. 810 static bool 811 DeleteTriviallyDeadInstructions(SmallVectorImpl<WeakVH> &DeadInsts) { 812 bool Changed = false; 813 814 while (!DeadInsts.empty()) { 815 Value *V = DeadInsts.pop_back_val(); 816 Instruction *I = dyn_cast_or_null<Instruction>(V); 817 818 if (!I || !isInstructionTriviallyDead(I)) 819 continue; 820 821 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 822 if (Instruction *U = dyn_cast<Instruction>(*OI)) { 823 *OI = nullptr; 824 if (U->use_empty()) 825 DeadInsts.push_back(U); 826 } 827 828 I->eraseFromParent(); 829 Changed = true; 830 } 831 832 return Changed; 833 } 834 835 namespace { 836 class LSRUse; 837 } 838 839 /// \brief Check if the addressing mode defined by \p F is completely 840 /// folded in \p LU at isel time. 841 /// This includes address-mode folding and special icmp tricks. 842 /// This function returns true if \p LU can accommodate what \p F 843 /// defines and up to 1 base + 1 scaled + offset. 844 /// In other words, if \p F has several base registers, this function may 845 /// still return true. Therefore, users still need to account for 846 /// additional base registers and/or unfolded offsets to derive an 847 /// accurate cost model. 848 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 849 const LSRUse &LU, const Formula &F); 850 // Get the cost of the scaling factor used in F for LU. 851 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI, 852 const LSRUse &LU, const Formula &F); 853 854 namespace { 855 856 /// Cost - This class is used to measure and compare candidate formulae. 857 class Cost { 858 /// TODO: Some of these could be merged. Also, a lexical ordering 859 /// isn't always optimal. 860 unsigned NumRegs; 861 unsigned AddRecCost; 862 unsigned NumIVMuls; 863 unsigned NumBaseAdds; 864 unsigned ImmCost; 865 unsigned SetupCost; 866 unsigned ScaleCost; 867 868 public: 869 Cost() 870 : NumRegs(0), AddRecCost(0), NumIVMuls(0), NumBaseAdds(0), ImmCost(0), 871 SetupCost(0), ScaleCost(0) {} 872 873 bool operator<(const Cost &Other) const; 874 875 void Lose(); 876 877 #ifndef NDEBUG 878 // Once any of the metrics loses, they must all remain losers. 879 bool isValid() { 880 return ((NumRegs | AddRecCost | NumIVMuls | NumBaseAdds 881 | ImmCost | SetupCost | ScaleCost) != ~0u) 882 || ((NumRegs & AddRecCost & NumIVMuls & NumBaseAdds 883 & ImmCost & SetupCost & ScaleCost) == ~0u); 884 } 885 #endif 886 887 bool isLoser() { 888 assert(isValid() && "invalid cost"); 889 return NumRegs == ~0u; 890 } 891 892 void RateFormula(const TargetTransformInfo &TTI, 893 const Formula &F, 894 SmallPtrSetImpl<const SCEV *> &Regs, 895 const DenseSet<const SCEV *> &VisitedRegs, 896 const Loop *L, 897 const SmallVectorImpl<int64_t> &Offsets, 898 ScalarEvolution &SE, DominatorTree &DT, 899 const LSRUse &LU, 900 SmallPtrSetImpl<const SCEV *> *LoserRegs = nullptr); 901 902 void print(raw_ostream &OS) const; 903 void dump() const; 904 905 private: 906 void RateRegister(const SCEV *Reg, 907 SmallPtrSetImpl<const SCEV *> &Regs, 908 const Loop *L, 909 ScalarEvolution &SE, DominatorTree &DT); 910 void RatePrimaryRegister(const SCEV *Reg, 911 SmallPtrSetImpl<const SCEV *> &Regs, 912 const Loop *L, 913 ScalarEvolution &SE, DominatorTree &DT, 914 SmallPtrSetImpl<const SCEV *> *LoserRegs); 915 }; 916 917 } 918 919 /// RateRegister - Tally up interesting quantities from the given register. 920 void Cost::RateRegister(const SCEV *Reg, 921 SmallPtrSetImpl<const SCEV *> &Regs, 922 const Loop *L, 923 ScalarEvolution &SE, DominatorTree &DT) { 924 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Reg)) { 925 // If this is an addrec for another loop, don't second-guess its addrec phi 926 // nodes. LSR isn't currently smart enough to reason about more than one 927 // loop at a time. LSR has already run on inner loops, will not run on outer 928 // loops, and cannot be expected to change sibling loops. 929 if (AR->getLoop() != L) { 930 // If the AddRec exists, consider it's register free and leave it alone. 931 if (isExistingPhi(AR, SE)) 932 return; 933 934 // Otherwise, do not consider this formula at all. 935 Lose(); 936 return; 937 } 938 AddRecCost += 1; /// TODO: This should be a function of the stride. 939 940 // Add the step value register, if it needs one. 941 // TODO: The non-affine case isn't precisely modeled here. 942 if (!AR->isAffine() || !isa<SCEVConstant>(AR->getOperand(1))) { 943 if (!Regs.count(AR->getOperand(1))) { 944 RateRegister(AR->getOperand(1), Regs, L, SE, DT); 945 if (isLoser()) 946 return; 947 } 948 } 949 } 950 ++NumRegs; 951 952 // Rough heuristic; favor registers which don't require extra setup 953 // instructions in the preheader. 954 if (!isa<SCEVUnknown>(Reg) && 955 !isa<SCEVConstant>(Reg) && 956 !(isa<SCEVAddRecExpr>(Reg) && 957 (isa<SCEVUnknown>(cast<SCEVAddRecExpr>(Reg)->getStart()) || 958 isa<SCEVConstant>(cast<SCEVAddRecExpr>(Reg)->getStart())))) 959 ++SetupCost; 960 961 NumIVMuls += isa<SCEVMulExpr>(Reg) && 962 SE.hasComputableLoopEvolution(Reg, L); 963 } 964 965 /// RatePrimaryRegister - Record this register in the set. If we haven't seen it 966 /// before, rate it. Optional LoserRegs provides a way to declare any formula 967 /// that refers to one of those regs an instant loser. 968 void Cost::RatePrimaryRegister(const SCEV *Reg, 969 SmallPtrSetImpl<const SCEV *> &Regs, 970 const Loop *L, 971 ScalarEvolution &SE, DominatorTree &DT, 972 SmallPtrSetImpl<const SCEV *> *LoserRegs) { 973 if (LoserRegs && LoserRegs->count(Reg)) { 974 Lose(); 975 return; 976 } 977 if (Regs.insert(Reg).second) { 978 RateRegister(Reg, Regs, L, SE, DT); 979 if (LoserRegs && isLoser()) 980 LoserRegs->insert(Reg); 981 } 982 } 983 984 void Cost::RateFormula(const TargetTransformInfo &TTI, 985 const Formula &F, 986 SmallPtrSetImpl<const SCEV *> &Regs, 987 const DenseSet<const SCEV *> &VisitedRegs, 988 const Loop *L, 989 const SmallVectorImpl<int64_t> &Offsets, 990 ScalarEvolution &SE, DominatorTree &DT, 991 const LSRUse &LU, 992 SmallPtrSetImpl<const SCEV *> *LoserRegs) { 993 assert(F.isCanonical() && "Cost is accurate only for canonical formula"); 994 // Tally up the registers. 995 if (const SCEV *ScaledReg = F.ScaledReg) { 996 if (VisitedRegs.count(ScaledReg)) { 997 Lose(); 998 return; 999 } 1000 RatePrimaryRegister(ScaledReg, Regs, L, SE, DT, LoserRegs); 1001 if (isLoser()) 1002 return; 1003 } 1004 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 1005 E = F.BaseRegs.end(); I != E; ++I) { 1006 const SCEV *BaseReg = *I; 1007 if (VisitedRegs.count(BaseReg)) { 1008 Lose(); 1009 return; 1010 } 1011 RatePrimaryRegister(BaseReg, Regs, L, SE, DT, LoserRegs); 1012 if (isLoser()) 1013 return; 1014 } 1015 1016 // Determine how many (unfolded) adds we'll need inside the loop. 1017 size_t NumBaseParts = F.getNumRegs(); 1018 if (NumBaseParts > 1) 1019 // Do not count the base and a possible second register if the target 1020 // allows to fold 2 registers. 1021 NumBaseAdds += 1022 NumBaseParts - (1 + (F.Scale && isAMCompletelyFolded(TTI, LU, F))); 1023 NumBaseAdds += (F.UnfoldedOffset != 0); 1024 1025 // Accumulate non-free scaling amounts. 1026 ScaleCost += getScalingFactorCost(TTI, LU, F); 1027 1028 // Tally up the non-zero immediates. 1029 for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), 1030 E = Offsets.end(); I != E; ++I) { 1031 int64_t Offset = (uint64_t)*I + F.BaseOffset; 1032 if (F.BaseGV) 1033 ImmCost += 64; // Handle symbolic values conservatively. 1034 // TODO: This should probably be the pointer size. 1035 else if (Offset != 0) 1036 ImmCost += APInt(64, Offset, true).getMinSignedBits(); 1037 } 1038 assert(isValid() && "invalid cost"); 1039 } 1040 1041 /// Lose - Set this cost to a losing value. 1042 void Cost::Lose() { 1043 NumRegs = ~0u; 1044 AddRecCost = ~0u; 1045 NumIVMuls = ~0u; 1046 NumBaseAdds = ~0u; 1047 ImmCost = ~0u; 1048 SetupCost = ~0u; 1049 ScaleCost = ~0u; 1050 } 1051 1052 /// operator< - Choose the lower cost. 1053 bool Cost::operator<(const Cost &Other) const { 1054 return std::tie(NumRegs, AddRecCost, NumIVMuls, NumBaseAdds, ScaleCost, 1055 ImmCost, SetupCost) < 1056 std::tie(Other.NumRegs, Other.AddRecCost, Other.NumIVMuls, 1057 Other.NumBaseAdds, Other.ScaleCost, Other.ImmCost, 1058 Other.SetupCost); 1059 } 1060 1061 void Cost::print(raw_ostream &OS) const { 1062 OS << NumRegs << " reg" << (NumRegs == 1 ? "" : "s"); 1063 if (AddRecCost != 0) 1064 OS << ", with addrec cost " << AddRecCost; 1065 if (NumIVMuls != 0) 1066 OS << ", plus " << NumIVMuls << " IV mul" << (NumIVMuls == 1 ? "" : "s"); 1067 if (NumBaseAdds != 0) 1068 OS << ", plus " << NumBaseAdds << " base add" 1069 << (NumBaseAdds == 1 ? "" : "s"); 1070 if (ScaleCost != 0) 1071 OS << ", plus " << ScaleCost << " scale cost"; 1072 if (ImmCost != 0) 1073 OS << ", plus " << ImmCost << " imm cost"; 1074 if (SetupCost != 0) 1075 OS << ", plus " << SetupCost << " setup cost"; 1076 } 1077 1078 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1079 void Cost::dump() const { 1080 print(errs()); errs() << '\n'; 1081 } 1082 #endif 1083 1084 namespace { 1085 1086 /// LSRFixup - An operand value in an instruction which is to be replaced 1087 /// with some equivalent, possibly strength-reduced, replacement. 1088 struct LSRFixup { 1089 /// UserInst - The instruction which will be updated. 1090 Instruction *UserInst; 1091 1092 /// OperandValToReplace - The operand of the instruction which will 1093 /// be replaced. The operand may be used more than once; every instance 1094 /// will be replaced. 1095 Value *OperandValToReplace; 1096 1097 /// PostIncLoops - If this user is to use the post-incremented value of an 1098 /// induction variable, this variable is non-null and holds the loop 1099 /// associated with the induction variable. 1100 PostIncLoopSet PostIncLoops; 1101 1102 /// LUIdx - The index of the LSRUse describing the expression which 1103 /// this fixup needs, minus an offset (below). 1104 size_t LUIdx; 1105 1106 /// Offset - A constant offset to be added to the LSRUse expression. 1107 /// This allows multiple fixups to share the same LSRUse with different 1108 /// offsets, for example in an unrolled loop. 1109 int64_t Offset; 1110 1111 bool isUseFullyOutsideLoop(const Loop *L) const; 1112 1113 LSRFixup(); 1114 1115 void print(raw_ostream &OS) const; 1116 void dump() const; 1117 }; 1118 1119 } 1120 1121 LSRFixup::LSRFixup() 1122 : UserInst(nullptr), OperandValToReplace(nullptr), LUIdx(~size_t(0)), 1123 Offset(0) {} 1124 1125 /// isUseFullyOutsideLoop - Test whether this fixup always uses its 1126 /// value outside of the given loop. 1127 bool LSRFixup::isUseFullyOutsideLoop(const Loop *L) const { 1128 // PHI nodes use their value in their incoming blocks. 1129 if (const PHINode *PN = dyn_cast<PHINode>(UserInst)) { 1130 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1131 if (PN->getIncomingValue(i) == OperandValToReplace && 1132 L->contains(PN->getIncomingBlock(i))) 1133 return false; 1134 return true; 1135 } 1136 1137 return !L->contains(UserInst); 1138 } 1139 1140 void LSRFixup::print(raw_ostream &OS) const { 1141 OS << "UserInst="; 1142 // Store is common and interesting enough to be worth special-casing. 1143 if (StoreInst *Store = dyn_cast<StoreInst>(UserInst)) { 1144 OS << "store "; 1145 Store->getOperand(0)->printAsOperand(OS, /*PrintType=*/false); 1146 } else if (UserInst->getType()->isVoidTy()) 1147 OS << UserInst->getOpcodeName(); 1148 else 1149 UserInst->printAsOperand(OS, /*PrintType=*/false); 1150 1151 OS << ", OperandValToReplace="; 1152 OperandValToReplace->printAsOperand(OS, /*PrintType=*/false); 1153 1154 for (PostIncLoopSet::const_iterator I = PostIncLoops.begin(), 1155 E = PostIncLoops.end(); I != E; ++I) { 1156 OS << ", PostIncLoop="; 1157 (*I)->getHeader()->printAsOperand(OS, /*PrintType=*/false); 1158 } 1159 1160 if (LUIdx != ~size_t(0)) 1161 OS << ", LUIdx=" << LUIdx; 1162 1163 if (Offset != 0) 1164 OS << ", Offset=" << Offset; 1165 } 1166 1167 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1168 void LSRFixup::dump() const { 1169 print(errs()); errs() << '\n'; 1170 } 1171 #endif 1172 1173 namespace { 1174 1175 /// UniquifierDenseMapInfo - A DenseMapInfo implementation for holding 1176 /// DenseMaps and DenseSets of sorted SmallVectors of const SCEV*. 1177 struct UniquifierDenseMapInfo { 1178 static SmallVector<const SCEV *, 4> getEmptyKey() { 1179 SmallVector<const SCEV *, 4> V; 1180 V.push_back(reinterpret_cast<const SCEV *>(-1)); 1181 return V; 1182 } 1183 1184 static SmallVector<const SCEV *, 4> getTombstoneKey() { 1185 SmallVector<const SCEV *, 4> V; 1186 V.push_back(reinterpret_cast<const SCEV *>(-2)); 1187 return V; 1188 } 1189 1190 static unsigned getHashValue(const SmallVector<const SCEV *, 4> &V) { 1191 return static_cast<unsigned>(hash_combine_range(V.begin(), V.end())); 1192 } 1193 1194 static bool isEqual(const SmallVector<const SCEV *, 4> &LHS, 1195 const SmallVector<const SCEV *, 4> &RHS) { 1196 return LHS == RHS; 1197 } 1198 }; 1199 1200 /// LSRUse - This class holds the state that LSR keeps for each use in 1201 /// IVUsers, as well as uses invented by LSR itself. It includes information 1202 /// about what kinds of things can be folded into the user, information about 1203 /// the user itself, and information about how the use may be satisfied. 1204 /// TODO: Represent multiple users of the same expression in common? 1205 class LSRUse { 1206 DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier; 1207 1208 public: 1209 /// KindType - An enum for a kind of use, indicating what types of 1210 /// scaled and immediate operands it might support. 1211 enum KindType { 1212 Basic, ///< A normal use, with no folding. 1213 Special, ///< A special case of basic, allowing -1 scales. 1214 Address, ///< An address use; folding according to TargetLowering 1215 ICmpZero ///< An equality icmp with both operands folded into one. 1216 // TODO: Add a generic icmp too? 1217 }; 1218 1219 typedef PointerIntPair<const SCEV *, 2, KindType> SCEVUseKindPair; 1220 1221 KindType Kind; 1222 Type *AccessTy; 1223 1224 SmallVector<int64_t, 8> Offsets; 1225 int64_t MinOffset; 1226 int64_t MaxOffset; 1227 1228 /// AllFixupsOutsideLoop - This records whether all of the fixups using this 1229 /// LSRUse are outside of the loop, in which case some special-case heuristics 1230 /// may be used. 1231 bool AllFixupsOutsideLoop; 1232 1233 /// RigidFormula is set to true to guarantee that this use will be associated 1234 /// with a single formula--the one that initially matched. Some SCEV 1235 /// expressions cannot be expanded. This allows LSR to consider the registers 1236 /// used by those expressions without the need to expand them later after 1237 /// changing the formula. 1238 bool RigidFormula; 1239 1240 /// WidestFixupType - This records the widest use type for any fixup using 1241 /// this LSRUse. FindUseWithSimilarFormula can't consider uses with different 1242 /// max fixup widths to be equivalent, because the narrower one may be relying 1243 /// on the implicit truncation to truncate away bogus bits. 1244 Type *WidestFixupType; 1245 1246 /// Formulae - A list of ways to build a value that can satisfy this user. 1247 /// After the list is populated, one of these is selected heuristically and 1248 /// used to formulate a replacement for OperandValToReplace in UserInst. 1249 SmallVector<Formula, 12> Formulae; 1250 1251 /// Regs - The set of register candidates used by all formulae in this LSRUse. 1252 SmallPtrSet<const SCEV *, 4> Regs; 1253 1254 LSRUse(KindType K, Type *T) : Kind(K), AccessTy(T), 1255 MinOffset(INT64_MAX), 1256 MaxOffset(INT64_MIN), 1257 AllFixupsOutsideLoop(true), 1258 RigidFormula(false), 1259 WidestFixupType(nullptr) {} 1260 1261 bool HasFormulaWithSameRegs(const Formula &F) const; 1262 bool InsertFormula(const Formula &F); 1263 void DeleteFormula(Formula &F); 1264 void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses); 1265 1266 void print(raw_ostream &OS) const; 1267 void dump() const; 1268 }; 1269 1270 } 1271 1272 /// HasFormula - Test whether this use as a formula which has the same 1273 /// registers as the given formula. 1274 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const { 1275 SmallVector<const SCEV *, 4> Key = F.BaseRegs; 1276 if (F.ScaledReg) Key.push_back(F.ScaledReg); 1277 // Unstable sort by host order ok, because this is only used for uniquifying. 1278 std::sort(Key.begin(), Key.end()); 1279 return Uniquifier.count(Key); 1280 } 1281 1282 /// InsertFormula - If the given formula has not yet been inserted, add it to 1283 /// the list, and return true. Return false otherwise. 1284 /// The formula must be in canonical form. 1285 bool LSRUse::InsertFormula(const Formula &F) { 1286 assert(F.isCanonical() && "Invalid canonical representation"); 1287 1288 if (!Formulae.empty() && RigidFormula) 1289 return false; 1290 1291 SmallVector<const SCEV *, 4> Key = F.BaseRegs; 1292 if (F.ScaledReg) Key.push_back(F.ScaledReg); 1293 // Unstable sort by host order ok, because this is only used for uniquifying. 1294 std::sort(Key.begin(), Key.end()); 1295 1296 if (!Uniquifier.insert(Key).second) 1297 return false; 1298 1299 // Using a register to hold the value of 0 is not profitable. 1300 assert((!F.ScaledReg || !F.ScaledReg->isZero()) && 1301 "Zero allocated in a scaled register!"); 1302 #ifndef NDEBUG 1303 for (SmallVectorImpl<const SCEV *>::const_iterator I = 1304 F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) 1305 assert(!(*I)->isZero() && "Zero allocated in a base register!"); 1306 #endif 1307 1308 // Add the formula to the list. 1309 Formulae.push_back(F); 1310 1311 // Record registers now being used by this use. 1312 Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); 1313 if (F.ScaledReg) 1314 Regs.insert(F.ScaledReg); 1315 1316 return true; 1317 } 1318 1319 /// DeleteFormula - Remove the given formula from this use's list. 1320 void LSRUse::DeleteFormula(Formula &F) { 1321 if (&F != &Formulae.back()) 1322 std::swap(F, Formulae.back()); 1323 Formulae.pop_back(); 1324 } 1325 1326 /// RecomputeRegs - Recompute the Regs field, and update RegUses. 1327 void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) { 1328 // Now that we've filtered out some formulae, recompute the Regs set. 1329 SmallPtrSet<const SCEV *, 4> OldRegs = std::move(Regs); 1330 Regs.clear(); 1331 for (const Formula &F : Formulae) { 1332 if (F.ScaledReg) Regs.insert(F.ScaledReg); 1333 Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); 1334 } 1335 1336 // Update the RegTracker. 1337 for (const SCEV *S : OldRegs) 1338 if (!Regs.count(S)) 1339 RegUses.DropRegister(S, LUIdx); 1340 } 1341 1342 void LSRUse::print(raw_ostream &OS) const { 1343 OS << "LSR Use: Kind="; 1344 switch (Kind) { 1345 case Basic: OS << "Basic"; break; 1346 case Special: OS << "Special"; break; 1347 case ICmpZero: OS << "ICmpZero"; break; 1348 case Address: 1349 OS << "Address of "; 1350 if (AccessTy->isPointerTy()) 1351 OS << "pointer"; // the full pointer type could be really verbose 1352 else 1353 OS << *AccessTy; 1354 } 1355 1356 OS << ", Offsets={"; 1357 for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), 1358 E = Offsets.end(); I != E; ++I) { 1359 OS << *I; 1360 if (std::next(I) != E) 1361 OS << ','; 1362 } 1363 OS << '}'; 1364 1365 if (AllFixupsOutsideLoop) 1366 OS << ", all-fixups-outside-loop"; 1367 1368 if (WidestFixupType) 1369 OS << ", widest fixup type: " << *WidestFixupType; 1370 } 1371 1372 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1373 void LSRUse::dump() const { 1374 print(errs()); errs() << '\n'; 1375 } 1376 #endif 1377 1378 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1379 LSRUse::KindType Kind, Type *AccessTy, 1380 GlobalValue *BaseGV, int64_t BaseOffset, 1381 bool HasBaseReg, int64_t Scale) { 1382 switch (Kind) { 1383 case LSRUse::Address: 1384 return TTI.isLegalAddressingMode(AccessTy, BaseGV, BaseOffset, HasBaseReg, Scale); 1385 1386 // Otherwise, just guess that reg+reg addressing is legal. 1387 //return ; 1388 1389 case LSRUse::ICmpZero: 1390 // There's not even a target hook for querying whether it would be legal to 1391 // fold a GV into an ICmp. 1392 if (BaseGV) 1393 return false; 1394 1395 // ICmp only has two operands; don't allow more than two non-trivial parts. 1396 if (Scale != 0 && HasBaseReg && BaseOffset != 0) 1397 return false; 1398 1399 // ICmp only supports no scale or a -1 scale, as we can "fold" a -1 scale by 1400 // putting the scaled register in the other operand of the icmp. 1401 if (Scale != 0 && Scale != -1) 1402 return false; 1403 1404 // If we have low-level target information, ask the target if it can fold an 1405 // integer immediate on an icmp. 1406 if (BaseOffset != 0) { 1407 // We have one of: 1408 // ICmpZero BaseReg + BaseOffset => ICmp BaseReg, -BaseOffset 1409 // ICmpZero -1*ScaleReg + BaseOffset => ICmp ScaleReg, BaseOffset 1410 // Offs is the ICmp immediate. 1411 if (Scale == 0) 1412 // The cast does the right thing with INT64_MIN. 1413 BaseOffset = -(uint64_t)BaseOffset; 1414 return TTI.isLegalICmpImmediate(BaseOffset); 1415 } 1416 1417 // ICmpZero BaseReg + -1*ScaleReg => ICmp BaseReg, ScaleReg 1418 return true; 1419 1420 case LSRUse::Basic: 1421 // Only handle single-register values. 1422 return !BaseGV && Scale == 0 && BaseOffset == 0; 1423 1424 case LSRUse::Special: 1425 // Special case Basic to handle -1 scales. 1426 return !BaseGV && (Scale == 0 || Scale == -1) && BaseOffset == 0; 1427 } 1428 1429 llvm_unreachable("Invalid LSRUse Kind!"); 1430 } 1431 1432 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1433 int64_t MinOffset, int64_t MaxOffset, 1434 LSRUse::KindType Kind, Type *AccessTy, 1435 GlobalValue *BaseGV, int64_t BaseOffset, 1436 bool HasBaseReg, int64_t Scale) { 1437 // Check for overflow. 1438 if (((int64_t)((uint64_t)BaseOffset + MinOffset) > BaseOffset) != 1439 (MinOffset > 0)) 1440 return false; 1441 MinOffset = (uint64_t)BaseOffset + MinOffset; 1442 if (((int64_t)((uint64_t)BaseOffset + MaxOffset) > BaseOffset) != 1443 (MaxOffset > 0)) 1444 return false; 1445 MaxOffset = (uint64_t)BaseOffset + MaxOffset; 1446 1447 return isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, MinOffset, 1448 HasBaseReg, Scale) && 1449 isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, MaxOffset, 1450 HasBaseReg, Scale); 1451 } 1452 1453 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1454 int64_t MinOffset, int64_t MaxOffset, 1455 LSRUse::KindType Kind, Type *AccessTy, 1456 const Formula &F) { 1457 // For the purpose of isAMCompletelyFolded either having a canonical formula 1458 // or a scale not equal to zero is correct. 1459 // Problems may arise from non canonical formulae having a scale == 0. 1460 // Strictly speaking it would best to just rely on canonical formulae. 1461 // However, when we generate the scaled formulae, we first check that the 1462 // scaling factor is profitable before computing the actual ScaledReg for 1463 // compile time sake. 1464 assert((F.isCanonical() || F.Scale != 0)); 1465 return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, 1466 F.BaseGV, F.BaseOffset, F.HasBaseReg, F.Scale); 1467 } 1468 1469 /// isLegalUse - Test whether we know how to expand the current formula. 1470 static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset, 1471 int64_t MaxOffset, LSRUse::KindType Kind, Type *AccessTy, 1472 GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, 1473 int64_t Scale) { 1474 // We know how to expand completely foldable formulae. 1475 return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, BaseGV, 1476 BaseOffset, HasBaseReg, Scale) || 1477 // Or formulae that use a base register produced by a sum of base 1478 // registers. 1479 (Scale == 1 && 1480 isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, 1481 BaseGV, BaseOffset, true, 0)); 1482 } 1483 1484 static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset, 1485 int64_t MaxOffset, LSRUse::KindType Kind, Type *AccessTy, 1486 const Formula &F) { 1487 return isLegalUse(TTI, MinOffset, MaxOffset, Kind, AccessTy, F.BaseGV, 1488 F.BaseOffset, F.HasBaseReg, F.Scale); 1489 } 1490 1491 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1492 const LSRUse &LU, const Formula &F) { 1493 return isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, 1494 LU.AccessTy, F.BaseGV, F.BaseOffset, F.HasBaseReg, 1495 F.Scale); 1496 } 1497 1498 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI, 1499 const LSRUse &LU, const Formula &F) { 1500 if (!F.Scale) 1501 return 0; 1502 1503 // If the use is not completely folded in that instruction, we will have to 1504 // pay an extra cost only for scale != 1. 1505 if (!isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, 1506 LU.AccessTy, F)) 1507 return F.Scale != 1; 1508 1509 switch (LU.Kind) { 1510 case LSRUse::Address: { 1511 // Check the scaling factor cost with both the min and max offsets. 1512 int ScaleCostMinOffset = 1513 TTI.getScalingFactorCost(LU.AccessTy, F.BaseGV, 1514 F.BaseOffset + LU.MinOffset, 1515 F.HasBaseReg, F.Scale); 1516 int ScaleCostMaxOffset = 1517 TTI.getScalingFactorCost(LU.AccessTy, F.BaseGV, 1518 F.BaseOffset + LU.MaxOffset, 1519 F.HasBaseReg, F.Scale); 1520 1521 assert(ScaleCostMinOffset >= 0 && ScaleCostMaxOffset >= 0 && 1522 "Legal addressing mode has an illegal cost!"); 1523 return std::max(ScaleCostMinOffset, ScaleCostMaxOffset); 1524 } 1525 case LSRUse::ICmpZero: 1526 case LSRUse::Basic: 1527 case LSRUse::Special: 1528 // The use is completely folded, i.e., everything is folded into the 1529 // instruction. 1530 return 0; 1531 } 1532 1533 llvm_unreachable("Invalid LSRUse Kind!"); 1534 } 1535 1536 static bool isAlwaysFoldable(const TargetTransformInfo &TTI, 1537 LSRUse::KindType Kind, Type *AccessTy, 1538 GlobalValue *BaseGV, int64_t BaseOffset, 1539 bool HasBaseReg) { 1540 // Fast-path: zero is always foldable. 1541 if (BaseOffset == 0 && !BaseGV) return true; 1542 1543 // Conservatively, create an address with an immediate and a 1544 // base and a scale. 1545 int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1; 1546 1547 // Canonicalize a scale of 1 to a base register if the formula doesn't 1548 // already have a base register. 1549 if (!HasBaseReg && Scale == 1) { 1550 Scale = 0; 1551 HasBaseReg = true; 1552 } 1553 1554 return isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, BaseOffset, 1555 HasBaseReg, Scale); 1556 } 1557 1558 static bool isAlwaysFoldable(const TargetTransformInfo &TTI, 1559 ScalarEvolution &SE, int64_t MinOffset, 1560 int64_t MaxOffset, LSRUse::KindType Kind, 1561 Type *AccessTy, const SCEV *S, bool HasBaseReg) { 1562 // Fast-path: zero is always foldable. 1563 if (S->isZero()) return true; 1564 1565 // Conservatively, create an address with an immediate and a 1566 // base and a scale. 1567 int64_t BaseOffset = ExtractImmediate(S, SE); 1568 GlobalValue *BaseGV = ExtractSymbol(S, SE); 1569 1570 // If there's anything else involved, it's not foldable. 1571 if (!S->isZero()) return false; 1572 1573 // Fast-path: zero is always foldable. 1574 if (BaseOffset == 0 && !BaseGV) return true; 1575 1576 // Conservatively, create an address with an immediate and a 1577 // base and a scale. 1578 int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1; 1579 1580 return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, BaseGV, 1581 BaseOffset, HasBaseReg, Scale); 1582 } 1583 1584 namespace { 1585 1586 /// IVInc - An individual increment in a Chain of IV increments. 1587 /// Relate an IV user to an expression that computes the IV it uses from the IV 1588 /// used by the previous link in the Chain. 1589 /// 1590 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the 1591 /// original IVOperand. The head of the chain's IVOperand is only valid during 1592 /// chain collection, before LSR replaces IV users. During chain generation, 1593 /// IncExpr can be used to find the new IVOperand that computes the same 1594 /// expression. 1595 struct IVInc { 1596 Instruction *UserInst; 1597 Value* IVOperand; 1598 const SCEV *IncExpr; 1599 1600 IVInc(Instruction *U, Value *O, const SCEV *E): 1601 UserInst(U), IVOperand(O), IncExpr(E) {} 1602 }; 1603 1604 // IVChain - The list of IV increments in program order. 1605 // We typically add the head of a chain without finding subsequent links. 1606 struct IVChain { 1607 SmallVector<IVInc,1> Incs; 1608 const SCEV *ExprBase; 1609 1610 IVChain() : ExprBase(nullptr) {} 1611 1612 IVChain(const IVInc &Head, const SCEV *Base) 1613 : Incs(1, Head), ExprBase(Base) {} 1614 1615 typedef SmallVectorImpl<IVInc>::const_iterator const_iterator; 1616 1617 // begin - return the first increment in the chain. 1618 const_iterator begin() const { 1619 assert(!Incs.empty()); 1620 return std::next(Incs.begin()); 1621 } 1622 const_iterator end() const { 1623 return Incs.end(); 1624 } 1625 1626 // hasIncs - Returns true if this chain contains any increments. 1627 bool hasIncs() const { return Incs.size() >= 2; } 1628 1629 // add - Add an IVInc to the end of this chain. 1630 void add(const IVInc &X) { Incs.push_back(X); } 1631 1632 // tailUserInst - Returns the last UserInst in the chain. 1633 Instruction *tailUserInst() const { return Incs.back().UserInst; } 1634 1635 // isProfitableIncrement - Returns true if IncExpr can be profitably added to 1636 // this chain. 1637 bool isProfitableIncrement(const SCEV *OperExpr, 1638 const SCEV *IncExpr, 1639 ScalarEvolution&); 1640 }; 1641 1642 /// ChainUsers - Helper for CollectChains to track multiple IV increment uses. 1643 /// Distinguish between FarUsers that definitely cross IV increments and 1644 /// NearUsers that may be used between IV increments. 1645 struct ChainUsers { 1646 SmallPtrSet<Instruction*, 4> FarUsers; 1647 SmallPtrSet<Instruction*, 4> NearUsers; 1648 }; 1649 1650 /// LSRInstance - This class holds state for the main loop strength reduction 1651 /// logic. 1652 class LSRInstance { 1653 IVUsers &IU; 1654 ScalarEvolution &SE; 1655 DominatorTree &DT; 1656 LoopInfo &LI; 1657 const TargetTransformInfo &TTI; 1658 Loop *const L; 1659 bool Changed; 1660 1661 /// IVIncInsertPos - This is the insert position that the current loop's 1662 /// induction variable increment should be placed. In simple loops, this is 1663 /// the latch block's terminator. But in more complicated cases, this is a 1664 /// position which will dominate all the in-loop post-increment users. 1665 Instruction *IVIncInsertPos; 1666 1667 /// Factors - Interesting factors between use strides. 1668 SmallSetVector<int64_t, 8> Factors; 1669 1670 /// Types - Interesting use types, to facilitate truncation reuse. 1671 SmallSetVector<Type *, 4> Types; 1672 1673 /// Fixups - The list of operands which are to be replaced. 1674 SmallVector<LSRFixup, 16> Fixups; 1675 1676 /// Uses - The list of interesting uses. 1677 SmallVector<LSRUse, 16> Uses; 1678 1679 /// RegUses - Track which uses use which register candidates. 1680 RegUseTracker RegUses; 1681 1682 // Limit the number of chains to avoid quadratic behavior. We don't expect to 1683 // have more than a few IV increment chains in a loop. Missing a Chain falls 1684 // back to normal LSR behavior for those uses. 1685 static const unsigned MaxChains = 8; 1686 1687 /// IVChainVec - IV users can form a chain of IV increments. 1688 SmallVector<IVChain, MaxChains> IVChainVec; 1689 1690 /// IVIncSet - IV users that belong to profitable IVChains. 1691 SmallPtrSet<Use*, MaxChains> IVIncSet; 1692 1693 void OptimizeShadowIV(); 1694 bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse); 1695 ICmpInst *OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse); 1696 void OptimizeLoopTermCond(); 1697 1698 void ChainInstruction(Instruction *UserInst, Instruction *IVOper, 1699 SmallVectorImpl<ChainUsers> &ChainUsersVec); 1700 void FinalizeChain(IVChain &Chain); 1701 void CollectChains(); 1702 void GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, 1703 SmallVectorImpl<WeakVH> &DeadInsts); 1704 1705 void CollectInterestingTypesAndFactors(); 1706 void CollectFixupsAndInitialFormulae(); 1707 1708 LSRFixup &getNewFixup() { 1709 Fixups.push_back(LSRFixup()); 1710 return Fixups.back(); 1711 } 1712 1713 // Support for sharing of LSRUses between LSRFixups. 1714 typedef DenseMap<LSRUse::SCEVUseKindPair, size_t> UseMapTy; 1715 UseMapTy UseMap; 1716 1717 bool reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 1718 LSRUse::KindType Kind, Type *AccessTy); 1719 1720 std::pair<size_t, int64_t> getUse(const SCEV *&Expr, 1721 LSRUse::KindType Kind, 1722 Type *AccessTy); 1723 1724 void DeleteUse(LSRUse &LU, size_t LUIdx); 1725 1726 LSRUse *FindUseWithSimilarFormula(const Formula &F, const LSRUse &OrigLU); 1727 1728 void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx); 1729 void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx); 1730 void CountRegisters(const Formula &F, size_t LUIdx); 1731 bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F); 1732 1733 void CollectLoopInvariantFixupsAndFormulae(); 1734 1735 void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base, 1736 unsigned Depth = 0); 1737 1738 void GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx, 1739 const Formula &Base, unsigned Depth, 1740 size_t Idx, bool IsScaledReg = false); 1741 void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base); 1742 void GenerateSymbolicOffsetsImpl(LSRUse &LU, unsigned LUIdx, 1743 const Formula &Base, size_t Idx, 1744 bool IsScaledReg = false); 1745 void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base); 1746 void GenerateConstantOffsetsImpl(LSRUse &LU, unsigned LUIdx, 1747 const Formula &Base, 1748 const SmallVectorImpl<int64_t> &Worklist, 1749 size_t Idx, bool IsScaledReg = false); 1750 void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base); 1751 void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base); 1752 void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base); 1753 void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base); 1754 void GenerateCrossUseConstantOffsets(); 1755 void GenerateAllReuseFormulae(); 1756 1757 void FilterOutUndesirableDedicatedRegisters(); 1758 1759 size_t EstimateSearchSpaceComplexity() const; 1760 void NarrowSearchSpaceByDetectingSupersets(); 1761 void NarrowSearchSpaceByCollapsingUnrolledCode(); 1762 void NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters(); 1763 void NarrowSearchSpaceByPickingWinnerRegs(); 1764 void NarrowSearchSpaceUsingHeuristics(); 1765 1766 void SolveRecurse(SmallVectorImpl<const Formula *> &Solution, 1767 Cost &SolutionCost, 1768 SmallVectorImpl<const Formula *> &Workspace, 1769 const Cost &CurCost, 1770 const SmallPtrSet<const SCEV *, 16> &CurRegs, 1771 DenseSet<const SCEV *> &VisitedRegs) const; 1772 void Solve(SmallVectorImpl<const Formula *> &Solution) const; 1773 1774 BasicBlock::iterator 1775 HoistInsertPosition(BasicBlock::iterator IP, 1776 const SmallVectorImpl<Instruction *> &Inputs) const; 1777 BasicBlock::iterator 1778 AdjustInsertPositionForExpand(BasicBlock::iterator IP, 1779 const LSRFixup &LF, 1780 const LSRUse &LU, 1781 SCEVExpander &Rewriter) const; 1782 1783 Value *Expand(const LSRFixup &LF, 1784 const Formula &F, 1785 BasicBlock::iterator IP, 1786 SCEVExpander &Rewriter, 1787 SmallVectorImpl<WeakVH> &DeadInsts) const; 1788 void RewriteForPHI(PHINode *PN, const LSRFixup &LF, 1789 const Formula &F, 1790 SCEVExpander &Rewriter, 1791 SmallVectorImpl<WeakVH> &DeadInsts, 1792 Pass *P) const; 1793 void Rewrite(const LSRFixup &LF, 1794 const Formula &F, 1795 SCEVExpander &Rewriter, 1796 SmallVectorImpl<WeakVH> &DeadInsts, 1797 Pass *P) const; 1798 void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, 1799 Pass *P); 1800 1801 public: 1802 LSRInstance(Loop *L, Pass *P); 1803 1804 bool getChanged() const { return Changed; } 1805 1806 void print_factors_and_types(raw_ostream &OS) const; 1807 void print_fixups(raw_ostream &OS) const; 1808 void print_uses(raw_ostream &OS) const; 1809 void print(raw_ostream &OS) const; 1810 void dump() const; 1811 }; 1812 1813 } 1814 1815 /// OptimizeShadowIV - If IV is used in a int-to-float cast 1816 /// inside the loop then try to eliminate the cast operation. 1817 void LSRInstance::OptimizeShadowIV() { 1818 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L); 1819 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1820 return; 1821 1822 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); 1823 UI != E; /* empty */) { 1824 IVUsers::const_iterator CandidateUI = UI; 1825 ++UI; 1826 Instruction *ShadowUse = CandidateUI->getUser(); 1827 Type *DestTy = nullptr; 1828 bool IsSigned = false; 1829 1830 /* If shadow use is a int->float cast then insert a second IV 1831 to eliminate this cast. 1832 1833 for (unsigned i = 0; i < n; ++i) 1834 foo((double)i); 1835 1836 is transformed into 1837 1838 double d = 0.0; 1839 for (unsigned i = 0; i < n; ++i, ++d) 1840 foo(d); 1841 */ 1842 if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) { 1843 IsSigned = false; 1844 DestTy = UCast->getDestTy(); 1845 } 1846 else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) { 1847 IsSigned = true; 1848 DestTy = SCast->getDestTy(); 1849 } 1850 if (!DestTy) continue; 1851 1852 // If target does not support DestTy natively then do not apply 1853 // this transformation. 1854 if (!TTI.isTypeLegal(DestTy)) continue; 1855 1856 PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0)); 1857 if (!PH) continue; 1858 if (PH->getNumIncomingValues() != 2) continue; 1859 1860 Type *SrcTy = PH->getType(); 1861 int Mantissa = DestTy->getFPMantissaWidth(); 1862 if (Mantissa == -1) continue; 1863 if ((int)SE.getTypeSizeInBits(SrcTy) > Mantissa) 1864 continue; 1865 1866 unsigned Entry, Latch; 1867 if (PH->getIncomingBlock(0) == L->getLoopPreheader()) { 1868 Entry = 0; 1869 Latch = 1; 1870 } else { 1871 Entry = 1; 1872 Latch = 0; 1873 } 1874 1875 ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry)); 1876 if (!Init) continue; 1877 Constant *NewInit = ConstantFP::get(DestTy, IsSigned ? 1878 (double)Init->getSExtValue() : 1879 (double)Init->getZExtValue()); 1880 1881 BinaryOperator *Incr = 1882 dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch)); 1883 if (!Incr) continue; 1884 if (Incr->getOpcode() != Instruction::Add 1885 && Incr->getOpcode() != Instruction::Sub) 1886 continue; 1887 1888 /* Initialize new IV, double d = 0.0 in above example. */ 1889 ConstantInt *C = nullptr; 1890 if (Incr->getOperand(0) == PH) 1891 C = dyn_cast<ConstantInt>(Incr->getOperand(1)); 1892 else if (Incr->getOperand(1) == PH) 1893 C = dyn_cast<ConstantInt>(Incr->getOperand(0)); 1894 else 1895 continue; 1896 1897 if (!C) continue; 1898 1899 // Ignore negative constants, as the code below doesn't handle them 1900 // correctly. TODO: Remove this restriction. 1901 if (!C->getValue().isStrictlyPositive()) continue; 1902 1903 /* Add new PHINode. */ 1904 PHINode *NewPH = PHINode::Create(DestTy, 2, "IV.S.", PH); 1905 1906 /* create new increment. '++d' in above example. */ 1907 Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue()); 1908 BinaryOperator *NewIncr = 1909 BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ? 1910 Instruction::FAdd : Instruction::FSub, 1911 NewPH, CFP, "IV.S.next.", Incr); 1912 1913 NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry)); 1914 NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch)); 1915 1916 /* Remove cast operation */ 1917 ShadowUse->replaceAllUsesWith(NewPH); 1918 ShadowUse->eraseFromParent(); 1919 Changed = true; 1920 break; 1921 } 1922 } 1923 1924 /// FindIVUserForCond - If Cond has an operand that is an expression of an IV, 1925 /// set the IV user and stride information and return true, otherwise return 1926 /// false. 1927 bool LSRInstance::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse) { 1928 for (IVUsers::iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) 1929 if (UI->getUser() == Cond) { 1930 // NOTE: we could handle setcc instructions with multiple uses here, but 1931 // InstCombine does it as well for simple uses, it's not clear that it 1932 // occurs enough in real life to handle. 1933 CondUse = UI; 1934 return true; 1935 } 1936 return false; 1937 } 1938 1939 /// OptimizeMax - Rewrite the loop's terminating condition if it uses 1940 /// a max computation. 1941 /// 1942 /// This is a narrow solution to a specific, but acute, problem. For loops 1943 /// like this: 1944 /// 1945 /// i = 0; 1946 /// do { 1947 /// p[i] = 0.0; 1948 /// } while (++i < n); 1949 /// 1950 /// the trip count isn't just 'n', because 'n' might not be positive. And 1951 /// unfortunately this can come up even for loops where the user didn't use 1952 /// a C do-while loop. For example, seemingly well-behaved top-test loops 1953 /// will commonly be lowered like this: 1954 // 1955 /// if (n > 0) { 1956 /// i = 0; 1957 /// do { 1958 /// p[i] = 0.0; 1959 /// } while (++i < n); 1960 /// } 1961 /// 1962 /// and then it's possible for subsequent optimization to obscure the if 1963 /// test in such a way that indvars can't find it. 1964 /// 1965 /// When indvars can't find the if test in loops like this, it creates a 1966 /// max expression, which allows it to give the loop a canonical 1967 /// induction variable: 1968 /// 1969 /// i = 0; 1970 /// max = n < 1 ? 1 : n; 1971 /// do { 1972 /// p[i] = 0.0; 1973 /// } while (++i != max); 1974 /// 1975 /// Canonical induction variables are necessary because the loop passes 1976 /// are designed around them. The most obvious example of this is the 1977 /// LoopInfo analysis, which doesn't remember trip count values. It 1978 /// expects to be able to rediscover the trip count each time it is 1979 /// needed, and it does this using a simple analysis that only succeeds if 1980 /// the loop has a canonical induction variable. 1981 /// 1982 /// However, when it comes time to generate code, the maximum operation 1983 /// can be quite costly, especially if it's inside of an outer loop. 1984 /// 1985 /// This function solves this problem by detecting this type of loop and 1986 /// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting 1987 /// the instructions for the maximum computation. 1988 /// 1989 ICmpInst *LSRInstance::OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse) { 1990 // Check that the loop matches the pattern we're looking for. 1991 if (Cond->getPredicate() != CmpInst::ICMP_EQ && 1992 Cond->getPredicate() != CmpInst::ICMP_NE) 1993 return Cond; 1994 1995 SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1)); 1996 if (!Sel || !Sel->hasOneUse()) return Cond; 1997 1998 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L); 1999 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 2000 return Cond; 2001 const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1); 2002 2003 // Add one to the backedge-taken count to get the trip count. 2004 const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount); 2005 if (IterationCount != SE.getSCEV(Sel)) return Cond; 2006 2007 // Check for a max calculation that matches the pattern. There's no check 2008 // for ICMP_ULE here because the comparison would be with zero, which 2009 // isn't interesting. 2010 CmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE; 2011 const SCEVNAryExpr *Max = nullptr; 2012 if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(BackedgeTakenCount)) { 2013 Pred = ICmpInst::ICMP_SLE; 2014 Max = S; 2015 } else if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(IterationCount)) { 2016 Pred = ICmpInst::ICMP_SLT; 2017 Max = S; 2018 } else if (const SCEVUMaxExpr *U = dyn_cast<SCEVUMaxExpr>(IterationCount)) { 2019 Pred = ICmpInst::ICMP_ULT; 2020 Max = U; 2021 } else { 2022 // No match; bail. 2023 return Cond; 2024 } 2025 2026 // To handle a max with more than two operands, this optimization would 2027 // require additional checking and setup. 2028 if (Max->getNumOperands() != 2) 2029 return Cond; 2030 2031 const SCEV *MaxLHS = Max->getOperand(0); 2032 const SCEV *MaxRHS = Max->getOperand(1); 2033 2034 // ScalarEvolution canonicalizes constants to the left. For < and >, look 2035 // for a comparison with 1. For <= and >=, a comparison with zero. 2036 if (!MaxLHS || 2037 (ICmpInst::isTrueWhenEqual(Pred) ? !MaxLHS->isZero() : (MaxLHS != One))) 2038 return Cond; 2039 2040 // Check the relevant induction variable for conformance to 2041 // the pattern. 2042 const SCEV *IV = SE.getSCEV(Cond->getOperand(0)); 2043 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 2044 if (!AR || !AR->isAffine() || 2045 AR->getStart() != One || 2046 AR->getStepRecurrence(SE) != One) 2047 return Cond; 2048 2049 assert(AR->getLoop() == L && 2050 "Loop condition operand is an addrec in a different loop!"); 2051 2052 // Check the right operand of the select, and remember it, as it will 2053 // be used in the new comparison instruction. 2054 Value *NewRHS = nullptr; 2055 if (ICmpInst::isTrueWhenEqual(Pred)) { 2056 // Look for n+1, and grab n. 2057 if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(1))) 2058 if (ConstantInt *BO1 = dyn_cast<ConstantInt>(BO->getOperand(1))) 2059 if (BO1->isOne() && SE.getSCEV(BO->getOperand(0)) == MaxRHS) 2060 NewRHS = BO->getOperand(0); 2061 if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(2))) 2062 if (ConstantInt *BO1 = dyn_cast<ConstantInt>(BO->getOperand(1))) 2063 if (BO1->isOne() && SE.getSCEV(BO->getOperand(0)) == MaxRHS) 2064 NewRHS = BO->getOperand(0); 2065 if (!NewRHS) 2066 return Cond; 2067 } else if (SE.getSCEV(Sel->getOperand(1)) == MaxRHS) 2068 NewRHS = Sel->getOperand(1); 2069 else if (SE.getSCEV(Sel->getOperand(2)) == MaxRHS) 2070 NewRHS = Sel->getOperand(2); 2071 else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(MaxRHS)) 2072 NewRHS = SU->getValue(); 2073 else 2074 // Max doesn't match expected pattern. 2075 return Cond; 2076 2077 // Determine the new comparison opcode. It may be signed or unsigned, 2078 // and the original comparison may be either equality or inequality. 2079 if (Cond->getPredicate() == CmpInst::ICMP_EQ) 2080 Pred = CmpInst::getInversePredicate(Pred); 2081 2082 // Ok, everything looks ok to change the condition into an SLT or SGE and 2083 // delete the max calculation. 2084 ICmpInst *NewCond = 2085 new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp"); 2086 2087 // Delete the max calculation instructions. 2088 Cond->replaceAllUsesWith(NewCond); 2089 CondUse->setUser(NewCond); 2090 Instruction *Cmp = cast<Instruction>(Sel->getOperand(0)); 2091 Cond->eraseFromParent(); 2092 Sel->eraseFromParent(); 2093 if (Cmp->use_empty()) 2094 Cmp->eraseFromParent(); 2095 return NewCond; 2096 } 2097 2098 /// OptimizeLoopTermCond - Change loop terminating condition to use the 2099 /// postinc iv when possible. 2100 void 2101 LSRInstance::OptimizeLoopTermCond() { 2102 SmallPtrSet<Instruction *, 4> PostIncs; 2103 2104 BasicBlock *LatchBlock = L->getLoopLatch(); 2105 SmallVector<BasicBlock*, 8> ExitingBlocks; 2106 L->getExitingBlocks(ExitingBlocks); 2107 2108 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 2109 BasicBlock *ExitingBlock = ExitingBlocks[i]; 2110 2111 // Get the terminating condition for the loop if possible. If we 2112 // can, we want to change it to use a post-incremented version of its 2113 // induction variable, to allow coalescing the live ranges for the IV into 2114 // one register value. 2115 2116 BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2117 if (!TermBr) 2118 continue; 2119 // FIXME: Overly conservative, termination condition could be an 'or' etc.. 2120 if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition())) 2121 continue; 2122 2123 // Search IVUsesByStride to find Cond's IVUse if there is one. 2124 IVStrideUse *CondUse = nullptr; 2125 ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition()); 2126 if (!FindIVUserForCond(Cond, CondUse)) 2127 continue; 2128 2129 // If the trip count is computed in terms of a max (due to ScalarEvolution 2130 // being unable to find a sufficient guard, for example), change the loop 2131 // comparison to use SLT or ULT instead of NE. 2132 // One consequence of doing this now is that it disrupts the count-down 2133 // optimization. That's not always a bad thing though, because in such 2134 // cases it may still be worthwhile to avoid a max. 2135 Cond = OptimizeMax(Cond, CondUse); 2136 2137 // If this exiting block dominates the latch block, it may also use 2138 // the post-inc value if it won't be shared with other uses. 2139 // Check for dominance. 2140 if (!DT.dominates(ExitingBlock, LatchBlock)) 2141 continue; 2142 2143 // Conservatively avoid trying to use the post-inc value in non-latch 2144 // exits if there may be pre-inc users in intervening blocks. 2145 if (LatchBlock != ExitingBlock) 2146 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) 2147 // Test if the use is reachable from the exiting block. This dominator 2148 // query is a conservative approximation of reachability. 2149 if (&*UI != CondUse && 2150 !DT.properlyDominates(UI->getUser()->getParent(), ExitingBlock)) { 2151 // Conservatively assume there may be reuse if the quotient of their 2152 // strides could be a legal scale. 2153 const SCEV *A = IU.getStride(*CondUse, L); 2154 const SCEV *B = IU.getStride(*UI, L); 2155 if (!A || !B) continue; 2156 if (SE.getTypeSizeInBits(A->getType()) != 2157 SE.getTypeSizeInBits(B->getType())) { 2158 if (SE.getTypeSizeInBits(A->getType()) > 2159 SE.getTypeSizeInBits(B->getType())) 2160 B = SE.getSignExtendExpr(B, A->getType()); 2161 else 2162 A = SE.getSignExtendExpr(A, B->getType()); 2163 } 2164 if (const SCEVConstant *D = 2165 dyn_cast_or_null<SCEVConstant>(getExactSDiv(B, A, SE))) { 2166 const ConstantInt *C = D->getValue(); 2167 // Stride of one or negative one can have reuse with non-addresses. 2168 if (C->isOne() || C->isAllOnesValue()) 2169 goto decline_post_inc; 2170 // Avoid weird situations. 2171 if (C->getValue().getMinSignedBits() >= 64 || 2172 C->getValue().isMinSignedValue()) 2173 goto decline_post_inc; 2174 // Check for possible scaled-address reuse. 2175 Type *AccessTy = getAccessType(UI->getUser()); 2176 int64_t Scale = C->getSExtValue(); 2177 if (TTI.isLegalAddressingMode(AccessTy, /*BaseGV=*/ nullptr, 2178 /*BaseOffset=*/ 0, 2179 /*HasBaseReg=*/ false, Scale)) 2180 goto decline_post_inc; 2181 Scale = -Scale; 2182 if (TTI.isLegalAddressingMode(AccessTy, /*BaseGV=*/ nullptr, 2183 /*BaseOffset=*/ 0, 2184 /*HasBaseReg=*/ false, Scale)) 2185 goto decline_post_inc; 2186 } 2187 } 2188 2189 DEBUG(dbgs() << " Change loop exiting icmp to use postinc iv: " 2190 << *Cond << '\n'); 2191 2192 // It's possible for the setcc instruction to be anywhere in the loop, and 2193 // possible for it to have multiple users. If it is not immediately before 2194 // the exiting block branch, move it. 2195 if (&*++BasicBlock::iterator(Cond) != TermBr) { 2196 if (Cond->hasOneUse()) { 2197 Cond->moveBefore(TermBr); 2198 } else { 2199 // Clone the terminating condition and insert into the loopend. 2200 ICmpInst *OldCond = Cond; 2201 Cond = cast<ICmpInst>(Cond->clone()); 2202 Cond->setName(L->getHeader()->getName() + ".termcond"); 2203 ExitingBlock->getInstList().insert(TermBr, Cond); 2204 2205 // Clone the IVUse, as the old use still exists! 2206 CondUse = &IU.AddUser(Cond, CondUse->getOperandValToReplace()); 2207 TermBr->replaceUsesOfWith(OldCond, Cond); 2208 } 2209 } 2210 2211 // If we get to here, we know that we can transform the setcc instruction to 2212 // use the post-incremented version of the IV, allowing us to coalesce the 2213 // live ranges for the IV correctly. 2214 CondUse->transformToPostInc(L); 2215 Changed = true; 2216 2217 PostIncs.insert(Cond); 2218 decline_post_inc:; 2219 } 2220 2221 // Determine an insertion point for the loop induction variable increment. It 2222 // must dominate all the post-inc comparisons we just set up, and it must 2223 // dominate the loop latch edge. 2224 IVIncInsertPos = L->getLoopLatch()->getTerminator(); 2225 for (Instruction *Inst : PostIncs) { 2226 BasicBlock *BB = 2227 DT.findNearestCommonDominator(IVIncInsertPos->getParent(), 2228 Inst->getParent()); 2229 if (BB == Inst->getParent()) 2230 IVIncInsertPos = Inst; 2231 else if (BB != IVIncInsertPos->getParent()) 2232 IVIncInsertPos = BB->getTerminator(); 2233 } 2234 } 2235 2236 /// reconcileNewOffset - Determine if the given use can accommodate a fixup 2237 /// at the given offset and other details. If so, update the use and 2238 /// return true. 2239 bool 2240 LSRInstance::reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 2241 LSRUse::KindType Kind, Type *AccessTy) { 2242 int64_t NewMinOffset = LU.MinOffset; 2243 int64_t NewMaxOffset = LU.MaxOffset; 2244 Type *NewAccessTy = AccessTy; 2245 2246 // Check for a mismatched kind. It's tempting to collapse mismatched kinds to 2247 // something conservative, however this can pessimize in the case that one of 2248 // the uses will have all its uses outside the loop, for example. 2249 if (LU.Kind != Kind) 2250 return false; 2251 2252 // Check for a mismatched access type, and fall back conservatively as needed. 2253 // TODO: Be less conservative when the type is similar and can use the same 2254 // addressing modes. 2255 if (Kind == LSRUse::Address && AccessTy != LU.AccessTy) 2256 NewAccessTy = Type::getVoidTy(AccessTy->getContext()); 2257 2258 // Conservatively assume HasBaseReg is true for now. 2259 if (NewOffset < LU.MinOffset) { 2260 if (!isAlwaysFoldable(TTI, Kind, NewAccessTy, /*BaseGV=*/nullptr, 2261 LU.MaxOffset - NewOffset, HasBaseReg)) 2262 return false; 2263 NewMinOffset = NewOffset; 2264 } else if (NewOffset > LU.MaxOffset) { 2265 if (!isAlwaysFoldable(TTI, Kind, NewAccessTy, /*BaseGV=*/nullptr, 2266 NewOffset - LU.MinOffset, HasBaseReg)) 2267 return false; 2268 NewMaxOffset = NewOffset; 2269 } 2270 2271 // Update the use. 2272 LU.MinOffset = NewMinOffset; 2273 LU.MaxOffset = NewMaxOffset; 2274 LU.AccessTy = NewAccessTy; 2275 if (NewOffset != LU.Offsets.back()) 2276 LU.Offsets.push_back(NewOffset); 2277 return true; 2278 } 2279 2280 /// getUse - Return an LSRUse index and an offset value for a fixup which 2281 /// needs the given expression, with the given kind and optional access type. 2282 /// Either reuse an existing use or create a new one, as needed. 2283 std::pair<size_t, int64_t> 2284 LSRInstance::getUse(const SCEV *&Expr, 2285 LSRUse::KindType Kind, Type *AccessTy) { 2286 const SCEV *Copy = Expr; 2287 int64_t Offset = ExtractImmediate(Expr, SE); 2288 2289 // Basic uses can't accept any offset, for example. 2290 if (!isAlwaysFoldable(TTI, Kind, AccessTy, /*BaseGV=*/ nullptr, 2291 Offset, /*HasBaseReg=*/ true)) { 2292 Expr = Copy; 2293 Offset = 0; 2294 } 2295 2296 std::pair<UseMapTy::iterator, bool> P = 2297 UseMap.insert(std::make_pair(LSRUse::SCEVUseKindPair(Expr, Kind), 0)); 2298 if (!P.second) { 2299 // A use already existed with this base. 2300 size_t LUIdx = P.first->second; 2301 LSRUse &LU = Uses[LUIdx]; 2302 if (reconcileNewOffset(LU, Offset, /*HasBaseReg=*/true, Kind, AccessTy)) 2303 // Reuse this use. 2304 return std::make_pair(LUIdx, Offset); 2305 } 2306 2307 // Create a new use. 2308 size_t LUIdx = Uses.size(); 2309 P.first->second = LUIdx; 2310 Uses.push_back(LSRUse(Kind, AccessTy)); 2311 LSRUse &LU = Uses[LUIdx]; 2312 2313 // We don't need to track redundant offsets, but we don't need to go out 2314 // of our way here to avoid them. 2315 if (LU.Offsets.empty() || Offset != LU.Offsets.back()) 2316 LU.Offsets.push_back(Offset); 2317 2318 LU.MinOffset = Offset; 2319 LU.MaxOffset = Offset; 2320 return std::make_pair(LUIdx, Offset); 2321 } 2322 2323 /// DeleteUse - Delete the given use from the Uses list. 2324 void LSRInstance::DeleteUse(LSRUse &LU, size_t LUIdx) { 2325 if (&LU != &Uses.back()) 2326 std::swap(LU, Uses.back()); 2327 Uses.pop_back(); 2328 2329 // Update RegUses. 2330 RegUses.SwapAndDropUse(LUIdx, Uses.size()); 2331 } 2332 2333 /// FindUseWithFormula - Look for a use distinct from OrigLU which is has 2334 /// a formula that has the same registers as the given formula. 2335 LSRUse * 2336 LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF, 2337 const LSRUse &OrigLU) { 2338 // Search all uses for the formula. This could be more clever. 2339 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2340 LSRUse &LU = Uses[LUIdx]; 2341 // Check whether this use is close enough to OrigLU, to see whether it's 2342 // worthwhile looking through its formulae. 2343 // Ignore ICmpZero uses because they may contain formulae generated by 2344 // GenerateICmpZeroScales, in which case adding fixup offsets may 2345 // be invalid. 2346 if (&LU != &OrigLU && 2347 LU.Kind != LSRUse::ICmpZero && 2348 LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy && 2349 LU.WidestFixupType == OrigLU.WidestFixupType && 2350 LU.HasFormulaWithSameRegs(OrigF)) { 2351 // Scan through this use's formulae. 2352 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 2353 E = LU.Formulae.end(); I != E; ++I) { 2354 const Formula &F = *I; 2355 // Check to see if this formula has the same registers and symbols 2356 // as OrigF. 2357 if (F.BaseRegs == OrigF.BaseRegs && 2358 F.ScaledReg == OrigF.ScaledReg && 2359 F.BaseGV == OrigF.BaseGV && 2360 F.Scale == OrigF.Scale && 2361 F.UnfoldedOffset == OrigF.UnfoldedOffset) { 2362 if (F.BaseOffset == 0) 2363 return &LU; 2364 // This is the formula where all the registers and symbols matched; 2365 // there aren't going to be any others. Since we declined it, we 2366 // can skip the rest of the formulae and proceed to the next LSRUse. 2367 break; 2368 } 2369 } 2370 } 2371 } 2372 2373 // Nothing looked good. 2374 return nullptr; 2375 } 2376 2377 void LSRInstance::CollectInterestingTypesAndFactors() { 2378 SmallSetVector<const SCEV *, 4> Strides; 2379 2380 // Collect interesting types and strides. 2381 SmallVector<const SCEV *, 4> Worklist; 2382 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 2383 const SCEV *Expr = IU.getExpr(*UI); 2384 2385 // Collect interesting types. 2386 Types.insert(SE.getEffectiveSCEVType(Expr->getType())); 2387 2388 // Add strides for mentioned loops. 2389 Worklist.push_back(Expr); 2390 do { 2391 const SCEV *S = Worklist.pop_back_val(); 2392 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 2393 if (AR->getLoop() == L) 2394 Strides.insert(AR->getStepRecurrence(SE)); 2395 Worklist.push_back(AR->getStart()); 2396 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 2397 Worklist.append(Add->op_begin(), Add->op_end()); 2398 } 2399 } while (!Worklist.empty()); 2400 } 2401 2402 // Compute interesting factors from the set of interesting strides. 2403 for (SmallSetVector<const SCEV *, 4>::const_iterator 2404 I = Strides.begin(), E = Strides.end(); I != E; ++I) 2405 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter = 2406 std::next(I); NewStrideIter != E; ++NewStrideIter) { 2407 const SCEV *OldStride = *I; 2408 const SCEV *NewStride = *NewStrideIter; 2409 2410 if (SE.getTypeSizeInBits(OldStride->getType()) != 2411 SE.getTypeSizeInBits(NewStride->getType())) { 2412 if (SE.getTypeSizeInBits(OldStride->getType()) > 2413 SE.getTypeSizeInBits(NewStride->getType())) 2414 NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType()); 2415 else 2416 OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType()); 2417 } 2418 if (const SCEVConstant *Factor = 2419 dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride, 2420 SE, true))) { 2421 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 2422 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 2423 } else if (const SCEVConstant *Factor = 2424 dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride, 2425 NewStride, 2426 SE, true))) { 2427 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 2428 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 2429 } 2430 } 2431 2432 // If all uses use the same type, don't bother looking for truncation-based 2433 // reuse. 2434 if (Types.size() == 1) 2435 Types.clear(); 2436 2437 DEBUG(print_factors_and_types(dbgs())); 2438 } 2439 2440 /// findIVOperand - Helper for CollectChains that finds an IV operand (computed 2441 /// by an AddRec in this loop) within [OI,OE) or returns OE. If IVUsers mapped 2442 /// Instructions to IVStrideUses, we could partially skip this. 2443 static User::op_iterator 2444 findIVOperand(User::op_iterator OI, User::op_iterator OE, 2445 Loop *L, ScalarEvolution &SE) { 2446 for(; OI != OE; ++OI) { 2447 if (Instruction *Oper = dyn_cast<Instruction>(*OI)) { 2448 if (!SE.isSCEVable(Oper->getType())) 2449 continue; 2450 2451 if (const SCEVAddRecExpr *AR = 2452 dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Oper))) { 2453 if (AR->getLoop() == L) 2454 break; 2455 } 2456 } 2457 } 2458 return OI; 2459 } 2460 2461 /// getWideOperand - IVChain logic must consistenctly peek base TruncInst 2462 /// operands, so wrap it in a convenient helper. 2463 static Value *getWideOperand(Value *Oper) { 2464 if (TruncInst *Trunc = dyn_cast<TruncInst>(Oper)) 2465 return Trunc->getOperand(0); 2466 return Oper; 2467 } 2468 2469 /// isCompatibleIVType - Return true if we allow an IV chain to include both 2470 /// types. 2471 static bool isCompatibleIVType(Value *LVal, Value *RVal) { 2472 Type *LType = LVal->getType(); 2473 Type *RType = RVal->getType(); 2474 return (LType == RType) || (LType->isPointerTy() && RType->isPointerTy()); 2475 } 2476 2477 /// getExprBase - Return an approximation of this SCEV expression's "base", or 2478 /// NULL for any constant. Returning the expression itself is 2479 /// conservative. Returning a deeper subexpression is more precise and valid as 2480 /// long as it isn't less complex than another subexpression. For expressions 2481 /// involving multiple unscaled values, we need to return the pointer-type 2482 /// SCEVUnknown. This avoids forming chains across objects, such as: 2483 /// PrevOper==a[i], IVOper==b[i], IVInc==b-a. 2484 /// 2485 /// Since SCEVUnknown is the rightmost type, and pointers are the rightmost 2486 /// SCEVUnknown, we simply return the rightmost SCEV operand. 2487 static const SCEV *getExprBase(const SCEV *S) { 2488 switch (S->getSCEVType()) { 2489 default: // uncluding scUnknown. 2490 return S; 2491 case scConstant: 2492 return nullptr; 2493 case scTruncate: 2494 return getExprBase(cast<SCEVTruncateExpr>(S)->getOperand()); 2495 case scZeroExtend: 2496 return getExprBase(cast<SCEVZeroExtendExpr>(S)->getOperand()); 2497 case scSignExtend: 2498 return getExprBase(cast<SCEVSignExtendExpr>(S)->getOperand()); 2499 case scAddExpr: { 2500 // Skip over scaled operands (scMulExpr) to follow add operands as long as 2501 // there's nothing more complex. 2502 // FIXME: not sure if we want to recognize negation. 2503 const SCEVAddExpr *Add = cast<SCEVAddExpr>(S); 2504 for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(Add->op_end()), 2505 E(Add->op_begin()); I != E; ++I) { 2506 const SCEV *SubExpr = *I; 2507 if (SubExpr->getSCEVType() == scAddExpr) 2508 return getExprBase(SubExpr); 2509 2510 if (SubExpr->getSCEVType() != scMulExpr) 2511 return SubExpr; 2512 } 2513 return S; // all operands are scaled, be conservative. 2514 } 2515 case scAddRecExpr: 2516 return getExprBase(cast<SCEVAddRecExpr>(S)->getStart()); 2517 } 2518 } 2519 2520 /// Return true if the chain increment is profitable to expand into a loop 2521 /// invariant value, which may require its own register. A profitable chain 2522 /// increment will be an offset relative to the same base. We allow such offsets 2523 /// to potentially be used as chain increment as long as it's not obviously 2524 /// expensive to expand using real instructions. 2525 bool IVChain::isProfitableIncrement(const SCEV *OperExpr, 2526 const SCEV *IncExpr, 2527 ScalarEvolution &SE) { 2528 // Aggressively form chains when -stress-ivchain. 2529 if (StressIVChain) 2530 return true; 2531 2532 // Do not replace a constant offset from IV head with a nonconstant IV 2533 // increment. 2534 if (!isa<SCEVConstant>(IncExpr)) { 2535 const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Incs[0].IVOperand)); 2536 if (isa<SCEVConstant>(SE.getMinusSCEV(OperExpr, HeadExpr))) 2537 return 0; 2538 } 2539 2540 SmallPtrSet<const SCEV*, 8> Processed; 2541 return !isHighCostExpansion(IncExpr, Processed, SE); 2542 } 2543 2544 /// Return true if the number of registers needed for the chain is estimated to 2545 /// be less than the number required for the individual IV users. First prohibit 2546 /// any IV users that keep the IV live across increments (the Users set should 2547 /// be empty). Next count the number and type of increments in the chain. 2548 /// 2549 /// Chaining IVs can lead to considerable code bloat if ISEL doesn't 2550 /// effectively use postinc addressing modes. Only consider it profitable it the 2551 /// increments can be computed in fewer registers when chained. 2552 /// 2553 /// TODO: Consider IVInc free if it's already used in another chains. 2554 static bool 2555 isProfitableChain(IVChain &Chain, SmallPtrSetImpl<Instruction*> &Users, 2556 ScalarEvolution &SE, const TargetTransformInfo &TTI) { 2557 if (StressIVChain) 2558 return true; 2559 2560 if (!Chain.hasIncs()) 2561 return false; 2562 2563 if (!Users.empty()) { 2564 DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " users:\n"; 2565 for (Instruction *Inst : Users) { 2566 dbgs() << " " << *Inst << "\n"; 2567 }); 2568 return false; 2569 } 2570 assert(!Chain.Incs.empty() && "empty IV chains are not allowed"); 2571 2572 // The chain itself may require a register, so intialize cost to 1. 2573 int cost = 1; 2574 2575 // A complete chain likely eliminates the need for keeping the original IV in 2576 // a register. LSR does not currently know how to form a complete chain unless 2577 // the header phi already exists. 2578 if (isa<PHINode>(Chain.tailUserInst()) 2579 && SE.getSCEV(Chain.tailUserInst()) == Chain.Incs[0].IncExpr) { 2580 --cost; 2581 } 2582 const SCEV *LastIncExpr = nullptr; 2583 unsigned NumConstIncrements = 0; 2584 unsigned NumVarIncrements = 0; 2585 unsigned NumReusedIncrements = 0; 2586 for (IVChain::const_iterator I = Chain.begin(), E = Chain.end(); 2587 I != E; ++I) { 2588 2589 if (I->IncExpr->isZero()) 2590 continue; 2591 2592 // Incrementing by zero or some constant is neutral. We assume constants can 2593 // be folded into an addressing mode or an add's immediate operand. 2594 if (isa<SCEVConstant>(I->IncExpr)) { 2595 ++NumConstIncrements; 2596 continue; 2597 } 2598 2599 if (I->IncExpr == LastIncExpr) 2600 ++NumReusedIncrements; 2601 else 2602 ++NumVarIncrements; 2603 2604 LastIncExpr = I->IncExpr; 2605 } 2606 // An IV chain with a single increment is handled by LSR's postinc 2607 // uses. However, a chain with multiple increments requires keeping the IV's 2608 // value live longer than it needs to be if chained. 2609 if (NumConstIncrements > 1) 2610 --cost; 2611 2612 // Materializing increment expressions in the preheader that didn't exist in 2613 // the original code may cost a register. For example, sign-extended array 2614 // indices can produce ridiculous increments like this: 2615 // IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64))) 2616 cost += NumVarIncrements; 2617 2618 // Reusing variable increments likely saves a register to hold the multiple of 2619 // the stride. 2620 cost -= NumReusedIncrements; 2621 2622 DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " Cost: " << cost 2623 << "\n"); 2624 2625 return cost < 0; 2626 } 2627 2628 /// ChainInstruction - Add this IV user to an existing chain or make it the head 2629 /// of a new chain. 2630 void LSRInstance::ChainInstruction(Instruction *UserInst, Instruction *IVOper, 2631 SmallVectorImpl<ChainUsers> &ChainUsersVec) { 2632 // When IVs are used as types of varying widths, they are generally converted 2633 // to a wider type with some uses remaining narrow under a (free) trunc. 2634 Value *const NextIV = getWideOperand(IVOper); 2635 const SCEV *const OperExpr = SE.getSCEV(NextIV); 2636 const SCEV *const OperExprBase = getExprBase(OperExpr); 2637 2638 // Visit all existing chains. Check if its IVOper can be computed as a 2639 // profitable loop invariant increment from the last link in the Chain. 2640 unsigned ChainIdx = 0, NChains = IVChainVec.size(); 2641 const SCEV *LastIncExpr = nullptr; 2642 for (; ChainIdx < NChains; ++ChainIdx) { 2643 IVChain &Chain = IVChainVec[ChainIdx]; 2644 2645 // Prune the solution space aggressively by checking that both IV operands 2646 // are expressions that operate on the same unscaled SCEVUnknown. This 2647 // "base" will be canceled by the subsequent getMinusSCEV call. Checking 2648 // first avoids creating extra SCEV expressions. 2649 if (!StressIVChain && Chain.ExprBase != OperExprBase) 2650 continue; 2651 2652 Value *PrevIV = getWideOperand(Chain.Incs.back().IVOperand); 2653 if (!isCompatibleIVType(PrevIV, NextIV)) 2654 continue; 2655 2656 // A phi node terminates a chain. 2657 if (isa<PHINode>(UserInst) && isa<PHINode>(Chain.tailUserInst())) 2658 continue; 2659 2660 // The increment must be loop-invariant so it can be kept in a register. 2661 const SCEV *PrevExpr = SE.getSCEV(PrevIV); 2662 const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr); 2663 if (!SE.isLoopInvariant(IncExpr, L)) 2664 continue; 2665 2666 if (Chain.isProfitableIncrement(OperExpr, IncExpr, SE)) { 2667 LastIncExpr = IncExpr; 2668 break; 2669 } 2670 } 2671 // If we haven't found a chain, create a new one, unless we hit the max. Don't 2672 // bother for phi nodes, because they must be last in the chain. 2673 if (ChainIdx == NChains) { 2674 if (isa<PHINode>(UserInst)) 2675 return; 2676 if (NChains >= MaxChains && !StressIVChain) { 2677 DEBUG(dbgs() << "IV Chain Limit\n"); 2678 return; 2679 } 2680 LastIncExpr = OperExpr; 2681 // IVUsers may have skipped over sign/zero extensions. We don't currently 2682 // attempt to form chains involving extensions unless they can be hoisted 2683 // into this loop's AddRec. 2684 if (!isa<SCEVAddRecExpr>(LastIncExpr)) 2685 return; 2686 ++NChains; 2687 IVChainVec.push_back(IVChain(IVInc(UserInst, IVOper, LastIncExpr), 2688 OperExprBase)); 2689 ChainUsersVec.resize(NChains); 2690 DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Head: (" << *UserInst 2691 << ") IV=" << *LastIncExpr << "\n"); 2692 } else { 2693 DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Inc: (" << *UserInst 2694 << ") IV+" << *LastIncExpr << "\n"); 2695 // Add this IV user to the end of the chain. 2696 IVChainVec[ChainIdx].add(IVInc(UserInst, IVOper, LastIncExpr)); 2697 } 2698 IVChain &Chain = IVChainVec[ChainIdx]; 2699 2700 SmallPtrSet<Instruction*,4> &NearUsers = ChainUsersVec[ChainIdx].NearUsers; 2701 // This chain's NearUsers become FarUsers. 2702 if (!LastIncExpr->isZero()) { 2703 ChainUsersVec[ChainIdx].FarUsers.insert(NearUsers.begin(), 2704 NearUsers.end()); 2705 NearUsers.clear(); 2706 } 2707 2708 // All other uses of IVOperand become near uses of the chain. 2709 // We currently ignore intermediate values within SCEV expressions, assuming 2710 // they will eventually be used be the current chain, or can be computed 2711 // from one of the chain increments. To be more precise we could 2712 // transitively follow its user and only add leaf IV users to the set. 2713 for (User *U : IVOper->users()) { 2714 Instruction *OtherUse = dyn_cast<Instruction>(U); 2715 if (!OtherUse) 2716 continue; 2717 // Uses in the chain will no longer be uses if the chain is formed. 2718 // Include the head of the chain in this iteration (not Chain.begin()). 2719 IVChain::const_iterator IncIter = Chain.Incs.begin(); 2720 IVChain::const_iterator IncEnd = Chain.Incs.end(); 2721 for( ; IncIter != IncEnd; ++IncIter) { 2722 if (IncIter->UserInst == OtherUse) 2723 break; 2724 } 2725 if (IncIter != IncEnd) 2726 continue; 2727 2728 if (SE.isSCEVable(OtherUse->getType()) 2729 && !isa<SCEVUnknown>(SE.getSCEV(OtherUse)) 2730 && IU.isIVUserOrOperand(OtherUse)) { 2731 continue; 2732 } 2733 NearUsers.insert(OtherUse); 2734 } 2735 2736 // Since this user is part of the chain, it's no longer considered a use 2737 // of the chain. 2738 ChainUsersVec[ChainIdx].FarUsers.erase(UserInst); 2739 } 2740 2741 /// CollectChains - Populate the vector of Chains. 2742 /// 2743 /// This decreases ILP at the architecture level. Targets with ample registers, 2744 /// multiple memory ports, and no register renaming probably don't want 2745 /// this. However, such targets should probably disable LSR altogether. 2746 /// 2747 /// The job of LSR is to make a reasonable choice of induction variables across 2748 /// the loop. Subsequent passes can easily "unchain" computation exposing more 2749 /// ILP *within the loop* if the target wants it. 2750 /// 2751 /// Finding the best IV chain is potentially a scheduling problem. Since LSR 2752 /// will not reorder memory operations, it will recognize this as a chain, but 2753 /// will generate redundant IV increments. Ideally this would be corrected later 2754 /// by a smart scheduler: 2755 /// = A[i] 2756 /// = A[i+x] 2757 /// A[i] = 2758 /// A[i+x] = 2759 /// 2760 /// TODO: Walk the entire domtree within this loop, not just the path to the 2761 /// loop latch. This will discover chains on side paths, but requires 2762 /// maintaining multiple copies of the Chains state. 2763 void LSRInstance::CollectChains() { 2764 DEBUG(dbgs() << "Collecting IV Chains.\n"); 2765 SmallVector<ChainUsers, 8> ChainUsersVec; 2766 2767 SmallVector<BasicBlock *,8> LatchPath; 2768 BasicBlock *LoopHeader = L->getHeader(); 2769 for (DomTreeNode *Rung = DT.getNode(L->getLoopLatch()); 2770 Rung->getBlock() != LoopHeader; Rung = Rung->getIDom()) { 2771 LatchPath.push_back(Rung->getBlock()); 2772 } 2773 LatchPath.push_back(LoopHeader); 2774 2775 // Walk the instruction stream from the loop header to the loop latch. 2776 for (SmallVectorImpl<BasicBlock *>::reverse_iterator 2777 BBIter = LatchPath.rbegin(), BBEnd = LatchPath.rend(); 2778 BBIter != BBEnd; ++BBIter) { 2779 for (BasicBlock::iterator I = (*BBIter)->begin(), E = (*BBIter)->end(); 2780 I != E; ++I) { 2781 // Skip instructions that weren't seen by IVUsers analysis. 2782 if (isa<PHINode>(I) || !IU.isIVUserOrOperand(I)) 2783 continue; 2784 2785 // Ignore users that are part of a SCEV expression. This way we only 2786 // consider leaf IV Users. This effectively rediscovers a portion of 2787 // IVUsers analysis but in program order this time. 2788 if (SE.isSCEVable(I->getType()) && !isa<SCEVUnknown>(SE.getSCEV(I))) 2789 continue; 2790 2791 // Remove this instruction from any NearUsers set it may be in. 2792 for (unsigned ChainIdx = 0, NChains = IVChainVec.size(); 2793 ChainIdx < NChains; ++ChainIdx) { 2794 ChainUsersVec[ChainIdx].NearUsers.erase(I); 2795 } 2796 // Search for operands that can be chained. 2797 SmallPtrSet<Instruction*, 4> UniqueOperands; 2798 User::op_iterator IVOpEnd = I->op_end(); 2799 User::op_iterator IVOpIter = findIVOperand(I->op_begin(), IVOpEnd, L, SE); 2800 while (IVOpIter != IVOpEnd) { 2801 Instruction *IVOpInst = cast<Instruction>(*IVOpIter); 2802 if (UniqueOperands.insert(IVOpInst).second) 2803 ChainInstruction(I, IVOpInst, ChainUsersVec); 2804 IVOpIter = findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE); 2805 } 2806 } // Continue walking down the instructions. 2807 } // Continue walking down the domtree. 2808 // Visit phi backedges to determine if the chain can generate the IV postinc. 2809 for (BasicBlock::iterator I = L->getHeader()->begin(); 2810 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 2811 if (!SE.isSCEVable(PN->getType())) 2812 continue; 2813 2814 Instruction *IncV = 2815 dyn_cast<Instruction>(PN->getIncomingValueForBlock(L->getLoopLatch())); 2816 if (IncV) 2817 ChainInstruction(PN, IncV, ChainUsersVec); 2818 } 2819 // Remove any unprofitable chains. 2820 unsigned ChainIdx = 0; 2821 for (unsigned UsersIdx = 0, NChains = IVChainVec.size(); 2822 UsersIdx < NChains; ++UsersIdx) { 2823 if (!isProfitableChain(IVChainVec[UsersIdx], 2824 ChainUsersVec[UsersIdx].FarUsers, SE, TTI)) 2825 continue; 2826 // Preserve the chain at UsesIdx. 2827 if (ChainIdx != UsersIdx) 2828 IVChainVec[ChainIdx] = IVChainVec[UsersIdx]; 2829 FinalizeChain(IVChainVec[ChainIdx]); 2830 ++ChainIdx; 2831 } 2832 IVChainVec.resize(ChainIdx); 2833 } 2834 2835 void LSRInstance::FinalizeChain(IVChain &Chain) { 2836 assert(!Chain.Incs.empty() && "empty IV chains are not allowed"); 2837 DEBUG(dbgs() << "Final Chain: " << *Chain.Incs[0].UserInst << "\n"); 2838 2839 for (IVChain::const_iterator I = Chain.begin(), E = Chain.end(); 2840 I != E; ++I) { 2841 DEBUG(dbgs() << " Inc: " << *I->UserInst << "\n"); 2842 User::op_iterator UseI = 2843 std::find(I->UserInst->op_begin(), I->UserInst->op_end(), I->IVOperand); 2844 assert(UseI != I->UserInst->op_end() && "cannot find IV operand"); 2845 IVIncSet.insert(UseI); 2846 } 2847 } 2848 2849 /// Return true if the IVInc can be folded into an addressing mode. 2850 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst, 2851 Value *Operand, const TargetTransformInfo &TTI) { 2852 const SCEVConstant *IncConst = dyn_cast<SCEVConstant>(IncExpr); 2853 if (!IncConst || !isAddressUse(UserInst, Operand)) 2854 return false; 2855 2856 if (IncConst->getValue()->getValue().getMinSignedBits() > 64) 2857 return false; 2858 2859 int64_t IncOffset = IncConst->getValue()->getSExtValue(); 2860 if (!isAlwaysFoldable(TTI, LSRUse::Address, 2861 getAccessType(UserInst), /*BaseGV=*/ nullptr, 2862 IncOffset, /*HaseBaseReg=*/ false)) 2863 return false; 2864 2865 return true; 2866 } 2867 2868 /// GenerateIVChains - Generate an add or subtract for each IVInc in a chain to 2869 /// materialize the IV user's operand from the previous IV user's operand. 2870 void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, 2871 SmallVectorImpl<WeakVH> &DeadInsts) { 2872 // Find the new IVOperand for the head of the chain. It may have been replaced 2873 // by LSR. 2874 const IVInc &Head = Chain.Incs[0]; 2875 User::op_iterator IVOpEnd = Head.UserInst->op_end(); 2876 // findIVOperand returns IVOpEnd if it can no longer find a valid IV user. 2877 User::op_iterator IVOpIter = findIVOperand(Head.UserInst->op_begin(), 2878 IVOpEnd, L, SE); 2879 Value *IVSrc = nullptr; 2880 while (IVOpIter != IVOpEnd) { 2881 IVSrc = getWideOperand(*IVOpIter); 2882 2883 // If this operand computes the expression that the chain needs, we may use 2884 // it. (Check this after setting IVSrc which is used below.) 2885 // 2886 // Note that if Head.IncExpr is wider than IVSrc, then this phi is too 2887 // narrow for the chain, so we can no longer use it. We do allow using a 2888 // wider phi, assuming the LSR checked for free truncation. In that case we 2889 // should already have a truncate on this operand such that 2890 // getSCEV(IVSrc) == IncExpr. 2891 if (SE.getSCEV(*IVOpIter) == Head.IncExpr 2892 || SE.getSCEV(IVSrc) == Head.IncExpr) { 2893 break; 2894 } 2895 IVOpIter = findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE); 2896 } 2897 if (IVOpIter == IVOpEnd) { 2898 // Gracefully give up on this chain. 2899 DEBUG(dbgs() << "Concealed chain head: " << *Head.UserInst << "\n"); 2900 return; 2901 } 2902 2903 DEBUG(dbgs() << "Generate chain at: " << *IVSrc << "\n"); 2904 Type *IVTy = IVSrc->getType(); 2905 Type *IntTy = SE.getEffectiveSCEVType(IVTy); 2906 const SCEV *LeftOverExpr = nullptr; 2907 for (IVChain::const_iterator IncI = Chain.begin(), 2908 IncE = Chain.end(); IncI != IncE; ++IncI) { 2909 2910 Instruction *InsertPt = IncI->UserInst; 2911 if (isa<PHINode>(InsertPt)) 2912 InsertPt = L->getLoopLatch()->getTerminator(); 2913 2914 // IVOper will replace the current IV User's operand. IVSrc is the IV 2915 // value currently held in a register. 2916 Value *IVOper = IVSrc; 2917 if (!IncI->IncExpr->isZero()) { 2918 // IncExpr was the result of subtraction of two narrow values, so must 2919 // be signed. 2920 const SCEV *IncExpr = SE.getNoopOrSignExtend(IncI->IncExpr, IntTy); 2921 LeftOverExpr = LeftOverExpr ? 2922 SE.getAddExpr(LeftOverExpr, IncExpr) : IncExpr; 2923 } 2924 if (LeftOverExpr && !LeftOverExpr->isZero()) { 2925 // Expand the IV increment. 2926 Rewriter.clearPostInc(); 2927 Value *IncV = Rewriter.expandCodeFor(LeftOverExpr, IntTy, InsertPt); 2928 const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc), 2929 SE.getUnknown(IncV)); 2930 IVOper = Rewriter.expandCodeFor(IVOperExpr, IVTy, InsertPt); 2931 2932 // If an IV increment can't be folded, use it as the next IV value. 2933 if (!canFoldIVIncExpr(LeftOverExpr, IncI->UserInst, IncI->IVOperand, 2934 TTI)) { 2935 assert(IVTy == IVOper->getType() && "inconsistent IV increment type"); 2936 IVSrc = IVOper; 2937 LeftOverExpr = nullptr; 2938 } 2939 } 2940 Type *OperTy = IncI->IVOperand->getType(); 2941 if (IVTy != OperTy) { 2942 assert(SE.getTypeSizeInBits(IVTy) >= SE.getTypeSizeInBits(OperTy) && 2943 "cannot extend a chained IV"); 2944 IRBuilder<> Builder(InsertPt); 2945 IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy, "lsr.chain"); 2946 } 2947 IncI->UserInst->replaceUsesOfWith(IncI->IVOperand, IVOper); 2948 DeadInsts.push_back(IncI->IVOperand); 2949 } 2950 // If LSR created a new, wider phi, we may also replace its postinc. We only 2951 // do this if we also found a wide value for the head of the chain. 2952 if (isa<PHINode>(Chain.tailUserInst())) { 2953 for (BasicBlock::iterator I = L->getHeader()->begin(); 2954 PHINode *Phi = dyn_cast<PHINode>(I); ++I) { 2955 if (!isCompatibleIVType(Phi, IVSrc)) 2956 continue; 2957 Instruction *PostIncV = dyn_cast<Instruction>( 2958 Phi->getIncomingValueForBlock(L->getLoopLatch())); 2959 if (!PostIncV || (SE.getSCEV(PostIncV) != SE.getSCEV(IVSrc))) 2960 continue; 2961 Value *IVOper = IVSrc; 2962 Type *PostIncTy = PostIncV->getType(); 2963 if (IVTy != PostIncTy) { 2964 assert(PostIncTy->isPointerTy() && "mixing int/ptr IV types"); 2965 IRBuilder<> Builder(L->getLoopLatch()->getTerminator()); 2966 Builder.SetCurrentDebugLocation(PostIncV->getDebugLoc()); 2967 IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy, "lsr.chain"); 2968 } 2969 Phi->replaceUsesOfWith(PostIncV, IVOper); 2970 DeadInsts.push_back(PostIncV); 2971 } 2972 } 2973 } 2974 2975 void LSRInstance::CollectFixupsAndInitialFormulae() { 2976 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 2977 Instruction *UserInst = UI->getUser(); 2978 // Skip IV users that are part of profitable IV Chains. 2979 User::op_iterator UseI = std::find(UserInst->op_begin(), UserInst->op_end(), 2980 UI->getOperandValToReplace()); 2981 assert(UseI != UserInst->op_end() && "cannot find IV operand"); 2982 if (IVIncSet.count(UseI)) 2983 continue; 2984 2985 // Record the uses. 2986 LSRFixup &LF = getNewFixup(); 2987 LF.UserInst = UserInst; 2988 LF.OperandValToReplace = UI->getOperandValToReplace(); 2989 LF.PostIncLoops = UI->getPostIncLoops(); 2990 2991 LSRUse::KindType Kind = LSRUse::Basic; 2992 Type *AccessTy = nullptr; 2993 if (isAddressUse(LF.UserInst, LF.OperandValToReplace)) { 2994 Kind = LSRUse::Address; 2995 AccessTy = getAccessType(LF.UserInst); 2996 } 2997 2998 const SCEV *S = IU.getExpr(*UI); 2999 3000 // Equality (== and !=) ICmps are special. We can rewrite (i == N) as 3001 // (N - i == 0), and this allows (N - i) to be the expression that we work 3002 // with rather than just N or i, so we can consider the register 3003 // requirements for both N and i at the same time. Limiting this code to 3004 // equality icmps is not a problem because all interesting loops use 3005 // equality icmps, thanks to IndVarSimplify. 3006 if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst)) 3007 if (CI->isEquality()) { 3008 // Swap the operands if needed to put the OperandValToReplace on the 3009 // left, for consistency. 3010 Value *NV = CI->getOperand(1); 3011 if (NV == LF.OperandValToReplace) { 3012 CI->setOperand(1, CI->getOperand(0)); 3013 CI->setOperand(0, NV); 3014 NV = CI->getOperand(1); 3015 Changed = true; 3016 } 3017 3018 // x == y --> x - y == 0 3019 const SCEV *N = SE.getSCEV(NV); 3020 if (SE.isLoopInvariant(N, L) && isSafeToExpand(N, SE)) { 3021 // S is normalized, so normalize N before folding it into S 3022 // to keep the result normalized. 3023 N = TransformForPostIncUse(Normalize, N, CI, nullptr, 3024 LF.PostIncLoops, SE, DT); 3025 Kind = LSRUse::ICmpZero; 3026 S = SE.getMinusSCEV(N, S); 3027 } 3028 3029 // -1 and the negations of all interesting strides (except the negation 3030 // of -1) are now also interesting. 3031 for (size_t i = 0, e = Factors.size(); i != e; ++i) 3032 if (Factors[i] != -1) 3033 Factors.insert(-(uint64_t)Factors[i]); 3034 Factors.insert(-1); 3035 } 3036 3037 // Set up the initial formula for this use. 3038 std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy); 3039 LF.LUIdx = P.first; 3040 LF.Offset = P.second; 3041 LSRUse &LU = Uses[LF.LUIdx]; 3042 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 3043 if (!LU.WidestFixupType || 3044 SE.getTypeSizeInBits(LU.WidestFixupType) < 3045 SE.getTypeSizeInBits(LF.OperandValToReplace->getType())) 3046 LU.WidestFixupType = LF.OperandValToReplace->getType(); 3047 3048 // If this is the first use of this LSRUse, give it a formula. 3049 if (LU.Formulae.empty()) { 3050 InsertInitialFormula(S, LU, LF.LUIdx); 3051 CountRegisters(LU.Formulae.back(), LF.LUIdx); 3052 } 3053 } 3054 3055 DEBUG(print_fixups(dbgs())); 3056 } 3057 3058 /// InsertInitialFormula - Insert a formula for the given expression into 3059 /// the given use, separating out loop-variant portions from loop-invariant 3060 /// and loop-computable portions. 3061 void 3062 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) { 3063 // Mark uses whose expressions cannot be expanded. 3064 if (!isSafeToExpand(S, SE)) 3065 LU.RigidFormula = true; 3066 3067 Formula F; 3068 F.InitialMatch(S, L, SE); 3069 bool Inserted = InsertFormula(LU, LUIdx, F); 3070 assert(Inserted && "Initial formula already exists!"); (void)Inserted; 3071 } 3072 3073 /// InsertSupplementalFormula - Insert a simple single-register formula for 3074 /// the given expression into the given use. 3075 void 3076 LSRInstance::InsertSupplementalFormula(const SCEV *S, 3077 LSRUse &LU, size_t LUIdx) { 3078 Formula F; 3079 F.BaseRegs.push_back(S); 3080 F.HasBaseReg = true; 3081 bool Inserted = InsertFormula(LU, LUIdx, F); 3082 assert(Inserted && "Supplemental formula already exists!"); (void)Inserted; 3083 } 3084 3085 /// CountRegisters - Note which registers are used by the given formula, 3086 /// updating RegUses. 3087 void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) { 3088 if (F.ScaledReg) 3089 RegUses.CountRegister(F.ScaledReg, LUIdx); 3090 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 3091 E = F.BaseRegs.end(); I != E; ++I) 3092 RegUses.CountRegister(*I, LUIdx); 3093 } 3094 3095 /// InsertFormula - If the given formula has not yet been inserted, add it to 3096 /// the list, and return true. Return false otherwise. 3097 bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) { 3098 // Do not insert formula that we will not be able to expand. 3099 assert(isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F) && 3100 "Formula is illegal"); 3101 if (!LU.InsertFormula(F)) 3102 return false; 3103 3104 CountRegisters(F, LUIdx); 3105 return true; 3106 } 3107 3108 /// CollectLoopInvariantFixupsAndFormulae - Check for other uses of 3109 /// loop-invariant values which we're tracking. These other uses will pin these 3110 /// values in registers, making them less profitable for elimination. 3111 /// TODO: This currently misses non-constant addrec step registers. 3112 /// TODO: Should this give more weight to users inside the loop? 3113 void 3114 LSRInstance::CollectLoopInvariantFixupsAndFormulae() { 3115 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end()); 3116 SmallPtrSet<const SCEV *, 32> Visited; 3117 3118 while (!Worklist.empty()) { 3119 const SCEV *S = Worklist.pop_back_val(); 3120 3121 // Don't process the same SCEV twice 3122 if (!Visited.insert(S).second) 3123 continue; 3124 3125 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) 3126 Worklist.append(N->op_begin(), N->op_end()); 3127 else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 3128 Worklist.push_back(C->getOperand()); 3129 else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 3130 Worklist.push_back(D->getLHS()); 3131 Worklist.push_back(D->getRHS()); 3132 } else if (const SCEVUnknown *US = dyn_cast<SCEVUnknown>(S)) { 3133 const Value *V = US->getValue(); 3134 if (const Instruction *Inst = dyn_cast<Instruction>(V)) { 3135 // Look for instructions defined outside the loop. 3136 if (L->contains(Inst)) continue; 3137 } else if (isa<UndefValue>(V)) 3138 // Undef doesn't have a live range, so it doesn't matter. 3139 continue; 3140 for (const Use &U : V->uses()) { 3141 const Instruction *UserInst = dyn_cast<Instruction>(U.getUser()); 3142 // Ignore non-instructions. 3143 if (!UserInst) 3144 continue; 3145 // Ignore instructions in other functions (as can happen with 3146 // Constants). 3147 if (UserInst->getParent()->getParent() != L->getHeader()->getParent()) 3148 continue; 3149 // Ignore instructions not dominated by the loop. 3150 const BasicBlock *UseBB = !isa<PHINode>(UserInst) ? 3151 UserInst->getParent() : 3152 cast<PHINode>(UserInst)->getIncomingBlock( 3153 PHINode::getIncomingValueNumForOperand(U.getOperandNo())); 3154 if (!DT.dominates(L->getHeader(), UseBB)) 3155 continue; 3156 // Ignore uses which are part of other SCEV expressions, to avoid 3157 // analyzing them multiple times. 3158 if (SE.isSCEVable(UserInst->getType())) { 3159 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst)); 3160 // If the user is a no-op, look through to its uses. 3161 if (!isa<SCEVUnknown>(UserS)) 3162 continue; 3163 if (UserS == US) { 3164 Worklist.push_back( 3165 SE.getUnknown(const_cast<Instruction *>(UserInst))); 3166 continue; 3167 } 3168 } 3169 // Ignore icmp instructions which are already being analyzed. 3170 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UserInst)) { 3171 unsigned OtherIdx = !U.getOperandNo(); 3172 Value *OtherOp = const_cast<Value *>(ICI->getOperand(OtherIdx)); 3173 if (SE.hasComputableLoopEvolution(SE.getSCEV(OtherOp), L)) 3174 continue; 3175 } 3176 3177 LSRFixup &LF = getNewFixup(); 3178 LF.UserInst = const_cast<Instruction *>(UserInst); 3179 LF.OperandValToReplace = U; 3180 std::pair<size_t, int64_t> P = getUse(S, LSRUse::Basic, nullptr); 3181 LF.LUIdx = P.first; 3182 LF.Offset = P.second; 3183 LSRUse &LU = Uses[LF.LUIdx]; 3184 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 3185 if (!LU.WidestFixupType || 3186 SE.getTypeSizeInBits(LU.WidestFixupType) < 3187 SE.getTypeSizeInBits(LF.OperandValToReplace->getType())) 3188 LU.WidestFixupType = LF.OperandValToReplace->getType(); 3189 InsertSupplementalFormula(US, LU, LF.LUIdx); 3190 CountRegisters(LU.Formulae.back(), Uses.size() - 1); 3191 break; 3192 } 3193 } 3194 } 3195 } 3196 3197 /// CollectSubexprs - Split S into subexpressions which can be pulled out into 3198 /// separate registers. If C is non-null, multiply each subexpression by C. 3199 /// 3200 /// Return remainder expression after factoring the subexpressions captured by 3201 /// Ops. If Ops is complete, return NULL. 3202 static const SCEV *CollectSubexprs(const SCEV *S, const SCEVConstant *C, 3203 SmallVectorImpl<const SCEV *> &Ops, 3204 const Loop *L, 3205 ScalarEvolution &SE, 3206 unsigned Depth = 0) { 3207 // Arbitrarily cap recursion to protect compile time. 3208 if (Depth >= 3) 3209 return S; 3210 3211 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 3212 // Break out add operands. 3213 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 3214 I != E; ++I) { 3215 const SCEV *Remainder = CollectSubexprs(*I, C, Ops, L, SE, Depth+1); 3216 if (Remainder) 3217 Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder); 3218 } 3219 return nullptr; 3220 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 3221 // Split a non-zero base out of an addrec. 3222 if (AR->getStart()->isZero()) 3223 return S; 3224 3225 const SCEV *Remainder = CollectSubexprs(AR->getStart(), 3226 C, Ops, L, SE, Depth+1); 3227 // Split the non-zero AddRec unless it is part of a nested recurrence that 3228 // does not pertain to this loop. 3229 if (Remainder && (AR->getLoop() == L || !isa<SCEVAddRecExpr>(Remainder))) { 3230 Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder); 3231 Remainder = nullptr; 3232 } 3233 if (Remainder != AR->getStart()) { 3234 if (!Remainder) 3235 Remainder = SE.getConstant(AR->getType(), 0); 3236 return SE.getAddRecExpr(Remainder, 3237 AR->getStepRecurrence(SE), 3238 AR->getLoop(), 3239 //FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 3240 SCEV::FlagAnyWrap); 3241 } 3242 } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 3243 // Break (C * (a + b + c)) into C*a + C*b + C*c. 3244 if (Mul->getNumOperands() != 2) 3245 return S; 3246 if (const SCEVConstant *Op0 = 3247 dyn_cast<SCEVConstant>(Mul->getOperand(0))) { 3248 C = C ? cast<SCEVConstant>(SE.getMulExpr(C, Op0)) : Op0; 3249 const SCEV *Remainder = 3250 CollectSubexprs(Mul->getOperand(1), C, Ops, L, SE, Depth+1); 3251 if (Remainder) 3252 Ops.push_back(SE.getMulExpr(C, Remainder)); 3253 return nullptr; 3254 } 3255 } 3256 return S; 3257 } 3258 3259 /// \brief Helper function for LSRInstance::GenerateReassociations. 3260 void LSRInstance::GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx, 3261 const Formula &Base, 3262 unsigned Depth, size_t Idx, 3263 bool IsScaledReg) { 3264 const SCEV *BaseReg = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx]; 3265 SmallVector<const SCEV *, 8> AddOps; 3266 const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE); 3267 if (Remainder) 3268 AddOps.push_back(Remainder); 3269 3270 if (AddOps.size() == 1) 3271 return; 3272 3273 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(), 3274 JE = AddOps.end(); 3275 J != JE; ++J) { 3276 3277 // Loop-variant "unknown" values are uninteresting; we won't be able to 3278 // do anything meaningful with them. 3279 if (isa<SCEVUnknown>(*J) && !SE.isLoopInvariant(*J, L)) 3280 continue; 3281 3282 // Don't pull a constant into a register if the constant could be folded 3283 // into an immediate field. 3284 if (isAlwaysFoldable(TTI, SE, LU.MinOffset, LU.MaxOffset, LU.Kind, 3285 LU.AccessTy, *J, Base.getNumRegs() > 1)) 3286 continue; 3287 3288 // Collect all operands except *J. 3289 SmallVector<const SCEV *, 8> InnerAddOps( 3290 ((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J); 3291 InnerAddOps.append(std::next(J), 3292 ((const SmallVector<const SCEV *, 8> &)AddOps).end()); 3293 3294 // Don't leave just a constant behind in a register if the constant could 3295 // be folded into an immediate field. 3296 if (InnerAddOps.size() == 1 && 3297 isAlwaysFoldable(TTI, SE, LU.MinOffset, LU.MaxOffset, LU.Kind, 3298 LU.AccessTy, InnerAddOps[0], Base.getNumRegs() > 1)) 3299 continue; 3300 3301 const SCEV *InnerSum = SE.getAddExpr(InnerAddOps); 3302 if (InnerSum->isZero()) 3303 continue; 3304 Formula F = Base; 3305 3306 // Add the remaining pieces of the add back into the new formula. 3307 const SCEVConstant *InnerSumSC = dyn_cast<SCEVConstant>(InnerSum); 3308 if (InnerSumSC && SE.getTypeSizeInBits(InnerSumSC->getType()) <= 64 && 3309 TTI.isLegalAddImmediate((uint64_t)F.UnfoldedOffset + 3310 InnerSumSC->getValue()->getZExtValue())) { 3311 F.UnfoldedOffset = 3312 (uint64_t)F.UnfoldedOffset + InnerSumSC->getValue()->getZExtValue(); 3313 if (IsScaledReg) 3314 F.ScaledReg = nullptr; 3315 else 3316 F.BaseRegs.erase(F.BaseRegs.begin() + Idx); 3317 } else if (IsScaledReg) 3318 F.ScaledReg = InnerSum; 3319 else 3320 F.BaseRegs[Idx] = InnerSum; 3321 3322 // Add J as its own register, or an unfolded immediate. 3323 const SCEVConstant *SC = dyn_cast<SCEVConstant>(*J); 3324 if (SC && SE.getTypeSizeInBits(SC->getType()) <= 64 && 3325 TTI.isLegalAddImmediate((uint64_t)F.UnfoldedOffset + 3326 SC->getValue()->getZExtValue())) 3327 F.UnfoldedOffset = 3328 (uint64_t)F.UnfoldedOffset + SC->getValue()->getZExtValue(); 3329 else 3330 F.BaseRegs.push_back(*J); 3331 // We may have changed the number of register in base regs, adjust the 3332 // formula accordingly. 3333 F.Canonicalize(); 3334 3335 if (InsertFormula(LU, LUIdx, F)) 3336 // If that formula hadn't been seen before, recurse to find more like 3337 // it. 3338 GenerateReassociations(LU, LUIdx, LU.Formulae.back(), Depth + 1); 3339 } 3340 } 3341 3342 /// GenerateReassociations - Split out subexpressions from adds and the bases of 3343 /// addrecs. 3344 void LSRInstance::GenerateReassociations(LSRUse &LU, unsigned LUIdx, 3345 Formula Base, unsigned Depth) { 3346 assert(Base.isCanonical() && "Input must be in the canonical form"); 3347 // Arbitrarily cap recursion to protect compile time. 3348 if (Depth >= 3) 3349 return; 3350 3351 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) 3352 GenerateReassociationsImpl(LU, LUIdx, Base, Depth, i); 3353 3354 if (Base.Scale == 1) 3355 GenerateReassociationsImpl(LU, LUIdx, Base, Depth, 3356 /* Idx */ -1, /* IsScaledReg */ true); 3357 } 3358 3359 /// GenerateCombinations - Generate a formula consisting of all of the 3360 /// loop-dominating registers added into a single register. 3361 void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx, 3362 Formula Base) { 3363 // This method is only interesting on a plurality of registers. 3364 if (Base.BaseRegs.size() + (Base.Scale == 1) <= 1) 3365 return; 3366 3367 // Flatten the representation, i.e., reg1 + 1*reg2 => reg1 + reg2, before 3368 // processing the formula. 3369 Base.Unscale(); 3370 Formula F = Base; 3371 F.BaseRegs.clear(); 3372 SmallVector<const SCEV *, 4> Ops; 3373 for (SmallVectorImpl<const SCEV *>::const_iterator 3374 I = Base.BaseRegs.begin(), E = Base.BaseRegs.end(); I != E; ++I) { 3375 const SCEV *BaseReg = *I; 3376 if (SE.properlyDominates(BaseReg, L->getHeader()) && 3377 !SE.hasComputableLoopEvolution(BaseReg, L)) 3378 Ops.push_back(BaseReg); 3379 else 3380 F.BaseRegs.push_back(BaseReg); 3381 } 3382 if (Ops.size() > 1) { 3383 const SCEV *Sum = SE.getAddExpr(Ops); 3384 // TODO: If Sum is zero, it probably means ScalarEvolution missed an 3385 // opportunity to fold something. For now, just ignore such cases 3386 // rather than proceed with zero in a register. 3387 if (!Sum->isZero()) { 3388 F.BaseRegs.push_back(Sum); 3389 F.Canonicalize(); 3390 (void)InsertFormula(LU, LUIdx, F); 3391 } 3392 } 3393 } 3394 3395 /// \brief Helper function for LSRInstance::GenerateSymbolicOffsets. 3396 void LSRInstance::GenerateSymbolicOffsetsImpl(LSRUse &LU, unsigned LUIdx, 3397 const Formula &Base, size_t Idx, 3398 bool IsScaledReg) { 3399 const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx]; 3400 GlobalValue *GV = ExtractSymbol(G, SE); 3401 if (G->isZero() || !GV) 3402 return; 3403 Formula F = Base; 3404 F.BaseGV = GV; 3405 if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F)) 3406 return; 3407 if (IsScaledReg) 3408 F.ScaledReg = G; 3409 else 3410 F.BaseRegs[Idx] = G; 3411 (void)InsertFormula(LU, LUIdx, F); 3412 } 3413 3414 /// GenerateSymbolicOffsets - Generate reuse formulae using symbolic offsets. 3415 void LSRInstance::GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, 3416 Formula Base) { 3417 // We can't add a symbolic offset if the address already contains one. 3418 if (Base.BaseGV) return; 3419 3420 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) 3421 GenerateSymbolicOffsetsImpl(LU, LUIdx, Base, i); 3422 if (Base.Scale == 1) 3423 GenerateSymbolicOffsetsImpl(LU, LUIdx, Base, /* Idx */ -1, 3424 /* IsScaledReg */ true); 3425 } 3426 3427 /// \brief Helper function for LSRInstance::GenerateConstantOffsets. 3428 void LSRInstance::GenerateConstantOffsetsImpl( 3429 LSRUse &LU, unsigned LUIdx, const Formula &Base, 3430 const SmallVectorImpl<int64_t> &Worklist, size_t Idx, bool IsScaledReg) { 3431 const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx]; 3432 for (SmallVectorImpl<int64_t>::const_iterator I = Worklist.begin(), 3433 E = Worklist.end(); 3434 I != E; ++I) { 3435 Formula F = Base; 3436 F.BaseOffset = (uint64_t)Base.BaseOffset - *I; 3437 if (isLegalUse(TTI, LU.MinOffset - *I, LU.MaxOffset - *I, LU.Kind, 3438 LU.AccessTy, F)) { 3439 // Add the offset to the base register. 3440 const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), *I), G); 3441 // If it cancelled out, drop the base register, otherwise update it. 3442 if (NewG->isZero()) { 3443 if (IsScaledReg) { 3444 F.Scale = 0; 3445 F.ScaledReg = nullptr; 3446 } else 3447 F.DeleteBaseReg(F.BaseRegs[Idx]); 3448 F.Canonicalize(); 3449 } else if (IsScaledReg) 3450 F.ScaledReg = NewG; 3451 else 3452 F.BaseRegs[Idx] = NewG; 3453 3454 (void)InsertFormula(LU, LUIdx, F); 3455 } 3456 } 3457 3458 int64_t Imm = ExtractImmediate(G, SE); 3459 if (G->isZero() || Imm == 0) 3460 return; 3461 Formula F = Base; 3462 F.BaseOffset = (uint64_t)F.BaseOffset + Imm; 3463 if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F)) 3464 return; 3465 if (IsScaledReg) 3466 F.ScaledReg = G; 3467 else 3468 F.BaseRegs[Idx] = G; 3469 (void)InsertFormula(LU, LUIdx, F); 3470 } 3471 3472 /// GenerateConstantOffsets - Generate reuse formulae using symbolic offsets. 3473 void LSRInstance::GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, 3474 Formula Base) { 3475 // TODO: For now, just add the min and max offset, because it usually isn't 3476 // worthwhile looking at everything inbetween. 3477 SmallVector<int64_t, 2> Worklist; 3478 Worklist.push_back(LU.MinOffset); 3479 if (LU.MaxOffset != LU.MinOffset) 3480 Worklist.push_back(LU.MaxOffset); 3481 3482 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) 3483 GenerateConstantOffsetsImpl(LU, LUIdx, Base, Worklist, i); 3484 if (Base.Scale == 1) 3485 GenerateConstantOffsetsImpl(LU, LUIdx, Base, Worklist, /* Idx */ -1, 3486 /* IsScaledReg */ true); 3487 } 3488 3489 /// GenerateICmpZeroScales - For ICmpZero, check to see if we can scale up 3490 /// the comparison. For example, x == y -> x*c == y*c. 3491 void LSRInstance::GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, 3492 Formula Base) { 3493 if (LU.Kind != LSRUse::ICmpZero) return; 3494 3495 // Determine the integer type for the base formula. 3496 Type *IntTy = Base.getType(); 3497 if (!IntTy) return; 3498 if (SE.getTypeSizeInBits(IntTy) > 64) return; 3499 3500 // Don't do this if there is more than one offset. 3501 if (LU.MinOffset != LU.MaxOffset) return; 3502 3503 assert(!Base.BaseGV && "ICmpZero use is not legal!"); 3504 3505 // Check each interesting stride. 3506 for (SmallSetVector<int64_t, 8>::const_iterator 3507 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 3508 int64_t Factor = *I; 3509 3510 // Check that the multiplication doesn't overflow. 3511 if (Base.BaseOffset == INT64_MIN && Factor == -1) 3512 continue; 3513 int64_t NewBaseOffset = (uint64_t)Base.BaseOffset * Factor; 3514 if (NewBaseOffset / Factor != Base.BaseOffset) 3515 continue; 3516 // If the offset will be truncated at this use, check that it is in bounds. 3517 if (!IntTy->isPointerTy() && 3518 !ConstantInt::isValueValidForType(IntTy, NewBaseOffset)) 3519 continue; 3520 3521 // Check that multiplying with the use offset doesn't overflow. 3522 int64_t Offset = LU.MinOffset; 3523 if (Offset == INT64_MIN && Factor == -1) 3524 continue; 3525 Offset = (uint64_t)Offset * Factor; 3526 if (Offset / Factor != LU.MinOffset) 3527 continue; 3528 // If the offset will be truncated at this use, check that it is in bounds. 3529 if (!IntTy->isPointerTy() && 3530 !ConstantInt::isValueValidForType(IntTy, Offset)) 3531 continue; 3532 3533 Formula F = Base; 3534 F.BaseOffset = NewBaseOffset; 3535 3536 // Check that this scale is legal. 3537 if (!isLegalUse(TTI, Offset, Offset, LU.Kind, LU.AccessTy, F)) 3538 continue; 3539 3540 // Compensate for the use having MinOffset built into it. 3541 F.BaseOffset = (uint64_t)F.BaseOffset + Offset - LU.MinOffset; 3542 3543 const SCEV *FactorS = SE.getConstant(IntTy, Factor); 3544 3545 // Check that multiplying with each base register doesn't overflow. 3546 for (size_t i = 0, e = F.BaseRegs.size(); i != e; ++i) { 3547 F.BaseRegs[i] = SE.getMulExpr(F.BaseRegs[i], FactorS); 3548 if (getExactSDiv(F.BaseRegs[i], FactorS, SE) != Base.BaseRegs[i]) 3549 goto next; 3550 } 3551 3552 // Check that multiplying with the scaled register doesn't overflow. 3553 if (F.ScaledReg) { 3554 F.ScaledReg = SE.getMulExpr(F.ScaledReg, FactorS); 3555 if (getExactSDiv(F.ScaledReg, FactorS, SE) != Base.ScaledReg) 3556 continue; 3557 } 3558 3559 // Check that multiplying with the unfolded offset doesn't overflow. 3560 if (F.UnfoldedOffset != 0) { 3561 if (F.UnfoldedOffset == INT64_MIN && Factor == -1) 3562 continue; 3563 F.UnfoldedOffset = (uint64_t)F.UnfoldedOffset * Factor; 3564 if (F.UnfoldedOffset / Factor != Base.UnfoldedOffset) 3565 continue; 3566 // If the offset will be truncated, check that it is in bounds. 3567 if (!IntTy->isPointerTy() && 3568 !ConstantInt::isValueValidForType(IntTy, F.UnfoldedOffset)) 3569 continue; 3570 } 3571 3572 // If we make it here and it's legal, add it. 3573 (void)InsertFormula(LU, LUIdx, F); 3574 next:; 3575 } 3576 } 3577 3578 /// GenerateScales - Generate stride factor reuse formulae by making use of 3579 /// scaled-offset address modes, for example. 3580 void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) { 3581 // Determine the integer type for the base formula. 3582 Type *IntTy = Base.getType(); 3583 if (!IntTy) return; 3584 3585 // If this Formula already has a scaled register, we can't add another one. 3586 // Try to unscale the formula to generate a better scale. 3587 if (Base.Scale != 0 && !Base.Unscale()) 3588 return; 3589 3590 assert(Base.Scale == 0 && "Unscale did not did its job!"); 3591 3592 // Check each interesting stride. 3593 for (SmallSetVector<int64_t, 8>::const_iterator 3594 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 3595 int64_t Factor = *I; 3596 3597 Base.Scale = Factor; 3598 Base.HasBaseReg = Base.BaseRegs.size() > 1; 3599 // Check whether this scale is going to be legal. 3600 if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, 3601 Base)) { 3602 // As a special-case, handle special out-of-loop Basic users specially. 3603 // TODO: Reconsider this special case. 3604 if (LU.Kind == LSRUse::Basic && 3605 isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LSRUse::Special, 3606 LU.AccessTy, Base) && 3607 LU.AllFixupsOutsideLoop) 3608 LU.Kind = LSRUse::Special; 3609 else 3610 continue; 3611 } 3612 // For an ICmpZero, negating a solitary base register won't lead to 3613 // new solutions. 3614 if (LU.Kind == LSRUse::ICmpZero && 3615 !Base.HasBaseReg && Base.BaseOffset == 0 && !Base.BaseGV) 3616 continue; 3617 // For each addrec base reg, apply the scale, if possible. 3618 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) 3619 if (const SCEVAddRecExpr *AR = 3620 dyn_cast<SCEVAddRecExpr>(Base.BaseRegs[i])) { 3621 const SCEV *FactorS = SE.getConstant(IntTy, Factor); 3622 if (FactorS->isZero()) 3623 continue; 3624 // Divide out the factor, ignoring high bits, since we'll be 3625 // scaling the value back up in the end. 3626 if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) { 3627 // TODO: This could be optimized to avoid all the copying. 3628 Formula F = Base; 3629 F.ScaledReg = Quotient; 3630 F.DeleteBaseReg(F.BaseRegs[i]); 3631 // The canonical representation of 1*reg is reg, which is already in 3632 // Base. In that case, do not try to insert the formula, it will be 3633 // rejected anyway. 3634 if (F.Scale == 1 && F.BaseRegs.empty()) 3635 continue; 3636 (void)InsertFormula(LU, LUIdx, F); 3637 } 3638 } 3639 } 3640 } 3641 3642 /// GenerateTruncates - Generate reuse formulae from different IV types. 3643 void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) { 3644 // Don't bother truncating symbolic values. 3645 if (Base.BaseGV) return; 3646 3647 // Determine the integer type for the base formula. 3648 Type *DstTy = Base.getType(); 3649 if (!DstTy) return; 3650 DstTy = SE.getEffectiveSCEVType(DstTy); 3651 3652 for (SmallSetVector<Type *, 4>::const_iterator 3653 I = Types.begin(), E = Types.end(); I != E; ++I) { 3654 Type *SrcTy = *I; 3655 if (SrcTy != DstTy && TTI.isTruncateFree(SrcTy, DstTy)) { 3656 Formula F = Base; 3657 3658 if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, *I); 3659 for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(), 3660 JE = F.BaseRegs.end(); J != JE; ++J) 3661 *J = SE.getAnyExtendExpr(*J, SrcTy); 3662 3663 // TODO: This assumes we've done basic processing on all uses and 3664 // have an idea what the register usage is. 3665 if (!F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses)) 3666 continue; 3667 3668 (void)InsertFormula(LU, LUIdx, F); 3669 } 3670 } 3671 } 3672 3673 namespace { 3674 3675 /// WorkItem - Helper class for GenerateCrossUseConstantOffsets. It's used to 3676 /// defer modifications so that the search phase doesn't have to worry about 3677 /// the data structures moving underneath it. 3678 struct WorkItem { 3679 size_t LUIdx; 3680 int64_t Imm; 3681 const SCEV *OrigReg; 3682 3683 WorkItem(size_t LI, int64_t I, const SCEV *R) 3684 : LUIdx(LI), Imm(I), OrigReg(R) {} 3685 3686 void print(raw_ostream &OS) const; 3687 void dump() const; 3688 }; 3689 3690 } 3691 3692 void WorkItem::print(raw_ostream &OS) const { 3693 OS << "in formulae referencing " << *OrigReg << " in use " << LUIdx 3694 << " , add offset " << Imm; 3695 } 3696 3697 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 3698 void WorkItem::dump() const { 3699 print(errs()); errs() << '\n'; 3700 } 3701 #endif 3702 3703 /// GenerateCrossUseConstantOffsets - Look for registers which are a constant 3704 /// distance apart and try to form reuse opportunities between them. 3705 void LSRInstance::GenerateCrossUseConstantOffsets() { 3706 // Group the registers by their value without any added constant offset. 3707 typedef std::map<int64_t, const SCEV *> ImmMapTy; 3708 typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy; 3709 RegMapTy Map; 3710 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap; 3711 SmallVector<const SCEV *, 8> Sequence; 3712 for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); 3713 I != E; ++I) { 3714 const SCEV *Reg = *I; 3715 int64_t Imm = ExtractImmediate(Reg, SE); 3716 std::pair<RegMapTy::iterator, bool> Pair = 3717 Map.insert(std::make_pair(Reg, ImmMapTy())); 3718 if (Pair.second) 3719 Sequence.push_back(Reg); 3720 Pair.first->second.insert(std::make_pair(Imm, *I)); 3721 UsedByIndicesMap[Reg] |= RegUses.getUsedByIndices(*I); 3722 } 3723 3724 // Now examine each set of registers with the same base value. Build up 3725 // a list of work to do and do the work in a separate step so that we're 3726 // not adding formulae and register counts while we're searching. 3727 SmallVector<WorkItem, 32> WorkItems; 3728 SmallSet<std::pair<size_t, int64_t>, 32> UniqueItems; 3729 for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(), 3730 E = Sequence.end(); I != E; ++I) { 3731 const SCEV *Reg = *I; 3732 const ImmMapTy &Imms = Map.find(Reg)->second; 3733 3734 // It's not worthwhile looking for reuse if there's only one offset. 3735 if (Imms.size() == 1) 3736 continue; 3737 3738 DEBUG(dbgs() << "Generating cross-use offsets for " << *Reg << ':'; 3739 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); 3740 J != JE; ++J) 3741 dbgs() << ' ' << J->first; 3742 dbgs() << '\n'); 3743 3744 // Examine each offset. 3745 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); 3746 J != JE; ++J) { 3747 const SCEV *OrigReg = J->second; 3748 3749 int64_t JImm = J->first; 3750 const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(OrigReg); 3751 3752 if (!isa<SCEVConstant>(OrigReg) && 3753 UsedByIndicesMap[Reg].count() == 1) { 3754 DEBUG(dbgs() << "Skipping cross-use reuse for " << *OrigReg << '\n'); 3755 continue; 3756 } 3757 3758 // Conservatively examine offsets between this orig reg a few selected 3759 // other orig regs. 3760 ImmMapTy::const_iterator OtherImms[] = { 3761 Imms.begin(), std::prev(Imms.end()), 3762 Imms.lower_bound((Imms.begin()->first + std::prev(Imms.end())->first) / 3763 2) 3764 }; 3765 for (size_t i = 0, e = array_lengthof(OtherImms); i != e; ++i) { 3766 ImmMapTy::const_iterator M = OtherImms[i]; 3767 if (M == J || M == JE) continue; 3768 3769 // Compute the difference between the two. 3770 int64_t Imm = (uint64_t)JImm - M->first; 3771 for (int LUIdx = UsedByIndices.find_first(); LUIdx != -1; 3772 LUIdx = UsedByIndices.find_next(LUIdx)) 3773 // Make a memo of this use, offset, and register tuple. 3774 if (UniqueItems.insert(std::make_pair(LUIdx, Imm)).second) 3775 WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg)); 3776 } 3777 } 3778 } 3779 3780 Map.clear(); 3781 Sequence.clear(); 3782 UsedByIndicesMap.clear(); 3783 UniqueItems.clear(); 3784 3785 // Now iterate through the worklist and add new formulae. 3786 for (SmallVectorImpl<WorkItem>::const_iterator I = WorkItems.begin(), 3787 E = WorkItems.end(); I != E; ++I) { 3788 const WorkItem &WI = *I; 3789 size_t LUIdx = WI.LUIdx; 3790 LSRUse &LU = Uses[LUIdx]; 3791 int64_t Imm = WI.Imm; 3792 const SCEV *OrigReg = WI.OrigReg; 3793 3794 Type *IntTy = SE.getEffectiveSCEVType(OrigReg->getType()); 3795 const SCEV *NegImmS = SE.getSCEV(ConstantInt::get(IntTy, -(uint64_t)Imm)); 3796 unsigned BitWidth = SE.getTypeSizeInBits(IntTy); 3797 3798 // TODO: Use a more targeted data structure. 3799 for (size_t L = 0, LE = LU.Formulae.size(); L != LE; ++L) { 3800 Formula F = LU.Formulae[L]; 3801 // FIXME: The code for the scaled and unscaled registers looks 3802 // very similar but slightly different. Investigate if they 3803 // could be merged. That way, we would not have to unscale the 3804 // Formula. 3805 F.Unscale(); 3806 // Use the immediate in the scaled register. 3807 if (F.ScaledReg == OrigReg) { 3808 int64_t Offset = (uint64_t)F.BaseOffset + Imm * (uint64_t)F.Scale; 3809 // Don't create 50 + reg(-50). 3810 if (F.referencesReg(SE.getSCEV( 3811 ConstantInt::get(IntTy, -(uint64_t)Offset)))) 3812 continue; 3813 Formula NewF = F; 3814 NewF.BaseOffset = Offset; 3815 if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, 3816 NewF)) 3817 continue; 3818 NewF.ScaledReg = SE.getAddExpr(NegImmS, NewF.ScaledReg); 3819 3820 // If the new scale is a constant in a register, and adding the constant 3821 // value to the immediate would produce a value closer to zero than the 3822 // immediate itself, then the formula isn't worthwhile. 3823 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(NewF.ScaledReg)) 3824 if (C->getValue()->isNegative() != 3825 (NewF.BaseOffset < 0) && 3826 (C->getValue()->getValue().abs() * APInt(BitWidth, F.Scale)) 3827 .ule(std::abs(NewF.BaseOffset))) 3828 continue; 3829 3830 // OK, looks good. 3831 NewF.Canonicalize(); 3832 (void)InsertFormula(LU, LUIdx, NewF); 3833 } else { 3834 // Use the immediate in a base register. 3835 for (size_t N = 0, NE = F.BaseRegs.size(); N != NE; ++N) { 3836 const SCEV *BaseReg = F.BaseRegs[N]; 3837 if (BaseReg != OrigReg) 3838 continue; 3839 Formula NewF = F; 3840 NewF.BaseOffset = (uint64_t)NewF.BaseOffset + Imm; 3841 if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, 3842 LU.Kind, LU.AccessTy, NewF)) { 3843 if (!TTI.isLegalAddImmediate((uint64_t)NewF.UnfoldedOffset + Imm)) 3844 continue; 3845 NewF = F; 3846 NewF.UnfoldedOffset = (uint64_t)NewF.UnfoldedOffset + Imm; 3847 } 3848 NewF.BaseRegs[N] = SE.getAddExpr(NegImmS, BaseReg); 3849 3850 // If the new formula has a constant in a register, and adding the 3851 // constant value to the immediate would produce a value closer to 3852 // zero than the immediate itself, then the formula isn't worthwhile. 3853 for (SmallVectorImpl<const SCEV *>::const_iterator 3854 J = NewF.BaseRegs.begin(), JE = NewF.BaseRegs.end(); 3855 J != JE; ++J) 3856 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*J)) 3857 if ((C->getValue()->getValue() + NewF.BaseOffset).abs().slt( 3858 std::abs(NewF.BaseOffset)) && 3859 (C->getValue()->getValue() + 3860 NewF.BaseOffset).countTrailingZeros() >= 3861 countTrailingZeros<uint64_t>(NewF.BaseOffset)) 3862 goto skip_formula; 3863 3864 // Ok, looks good. 3865 NewF.Canonicalize(); 3866 (void)InsertFormula(LU, LUIdx, NewF); 3867 break; 3868 skip_formula:; 3869 } 3870 } 3871 } 3872 } 3873 } 3874 3875 /// GenerateAllReuseFormulae - Generate formulae for each use. 3876 void 3877 LSRInstance::GenerateAllReuseFormulae() { 3878 // This is split into multiple loops so that hasRegsUsedByUsesOtherThan 3879 // queries are more precise. 3880 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 3881 LSRUse &LU = Uses[LUIdx]; 3882 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3883 GenerateReassociations(LU, LUIdx, LU.Formulae[i]); 3884 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3885 GenerateCombinations(LU, LUIdx, LU.Formulae[i]); 3886 } 3887 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 3888 LSRUse &LU = Uses[LUIdx]; 3889 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3890 GenerateSymbolicOffsets(LU, LUIdx, LU.Formulae[i]); 3891 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3892 GenerateConstantOffsets(LU, LUIdx, LU.Formulae[i]); 3893 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3894 GenerateICmpZeroScales(LU, LUIdx, LU.Formulae[i]); 3895 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3896 GenerateScales(LU, LUIdx, LU.Formulae[i]); 3897 } 3898 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 3899 LSRUse &LU = Uses[LUIdx]; 3900 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 3901 GenerateTruncates(LU, LUIdx, LU.Formulae[i]); 3902 } 3903 3904 GenerateCrossUseConstantOffsets(); 3905 3906 DEBUG(dbgs() << "\n" 3907 "After generating reuse formulae:\n"; 3908 print_uses(dbgs())); 3909 } 3910 3911 /// If there are multiple formulae with the same set of registers used 3912 /// by other uses, pick the best one and delete the others. 3913 void LSRInstance::FilterOutUndesirableDedicatedRegisters() { 3914 DenseSet<const SCEV *> VisitedRegs; 3915 SmallPtrSet<const SCEV *, 16> Regs; 3916 SmallPtrSet<const SCEV *, 16> LoserRegs; 3917 #ifndef NDEBUG 3918 bool ChangedFormulae = false; 3919 #endif 3920 3921 // Collect the best formula for each unique set of shared registers. This 3922 // is reset for each use. 3923 typedef DenseMap<SmallVector<const SCEV *, 4>, size_t, UniquifierDenseMapInfo> 3924 BestFormulaeTy; 3925 BestFormulaeTy BestFormulae; 3926 3927 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 3928 LSRUse &LU = Uses[LUIdx]; 3929 DEBUG(dbgs() << "Filtering for use "; LU.print(dbgs()); dbgs() << '\n'); 3930 3931 bool Any = false; 3932 for (size_t FIdx = 0, NumForms = LU.Formulae.size(); 3933 FIdx != NumForms; ++FIdx) { 3934 Formula &F = LU.Formulae[FIdx]; 3935 3936 // Some formulas are instant losers. For example, they may depend on 3937 // nonexistent AddRecs from other loops. These need to be filtered 3938 // immediately, otherwise heuristics could choose them over others leading 3939 // to an unsatisfactory solution. Passing LoserRegs into RateFormula here 3940 // avoids the need to recompute this information across formulae using the 3941 // same bad AddRec. Passing LoserRegs is also essential unless we remove 3942 // the corresponding bad register from the Regs set. 3943 Cost CostF; 3944 Regs.clear(); 3945 CostF.RateFormula(TTI, F, Regs, VisitedRegs, L, LU.Offsets, SE, DT, LU, 3946 &LoserRegs); 3947 if (CostF.isLoser()) { 3948 // During initial formula generation, undesirable formulae are generated 3949 // by uses within other loops that have some non-trivial address mode or 3950 // use the postinc form of the IV. LSR needs to provide these formulae 3951 // as the basis of rediscovering the desired formula that uses an AddRec 3952 // corresponding to the existing phi. Once all formulae have been 3953 // generated, these initial losers may be pruned. 3954 DEBUG(dbgs() << " Filtering loser "; F.print(dbgs()); 3955 dbgs() << "\n"); 3956 } 3957 else { 3958 SmallVector<const SCEV *, 4> Key; 3959 for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(), 3960 JE = F.BaseRegs.end(); J != JE; ++J) { 3961 const SCEV *Reg = *J; 3962 if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx)) 3963 Key.push_back(Reg); 3964 } 3965 if (F.ScaledReg && 3966 RegUses.isRegUsedByUsesOtherThan(F.ScaledReg, LUIdx)) 3967 Key.push_back(F.ScaledReg); 3968 // Unstable sort by host order ok, because this is only used for 3969 // uniquifying. 3970 std::sort(Key.begin(), Key.end()); 3971 3972 std::pair<BestFormulaeTy::const_iterator, bool> P = 3973 BestFormulae.insert(std::make_pair(Key, FIdx)); 3974 if (P.second) 3975 continue; 3976 3977 Formula &Best = LU.Formulae[P.first->second]; 3978 3979 Cost CostBest; 3980 Regs.clear(); 3981 CostBest.RateFormula(TTI, Best, Regs, VisitedRegs, L, LU.Offsets, SE, 3982 DT, LU); 3983 if (CostF < CostBest) 3984 std::swap(F, Best); 3985 DEBUG(dbgs() << " Filtering out formula "; F.print(dbgs()); 3986 dbgs() << "\n" 3987 " in favor of formula "; Best.print(dbgs()); 3988 dbgs() << '\n'); 3989 } 3990 #ifndef NDEBUG 3991 ChangedFormulae = true; 3992 #endif 3993 LU.DeleteFormula(F); 3994 --FIdx; 3995 --NumForms; 3996 Any = true; 3997 } 3998 3999 // Now that we've filtered out some formulae, recompute the Regs set. 4000 if (Any) 4001 LU.RecomputeRegs(LUIdx, RegUses); 4002 4003 // Reset this to prepare for the next use. 4004 BestFormulae.clear(); 4005 } 4006 4007 DEBUG(if (ChangedFormulae) { 4008 dbgs() << "\n" 4009 "After filtering out undesirable candidates:\n"; 4010 print_uses(dbgs()); 4011 }); 4012 } 4013 4014 // This is a rough guess that seems to work fairly well. 4015 static const size_t ComplexityLimit = UINT16_MAX; 4016 4017 /// EstimateSearchSpaceComplexity - Estimate the worst-case number of 4018 /// solutions the solver might have to consider. It almost never considers 4019 /// this many solutions because it prune the search space, but the pruning 4020 /// isn't always sufficient. 4021 size_t LSRInstance::EstimateSearchSpaceComplexity() const { 4022 size_t Power = 1; 4023 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 4024 E = Uses.end(); I != E; ++I) { 4025 size_t FSize = I->Formulae.size(); 4026 if (FSize >= ComplexityLimit) { 4027 Power = ComplexityLimit; 4028 break; 4029 } 4030 Power *= FSize; 4031 if (Power >= ComplexityLimit) 4032 break; 4033 } 4034 return Power; 4035 } 4036 4037 /// NarrowSearchSpaceByDetectingSupersets - When one formula uses a superset 4038 /// of the registers of another formula, it won't help reduce register 4039 /// pressure (though it may not necessarily hurt register pressure); remove 4040 /// it to simplify the system. 4041 void LSRInstance::NarrowSearchSpaceByDetectingSupersets() { 4042 if (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 4043 DEBUG(dbgs() << "The search space is too complex.\n"); 4044 4045 DEBUG(dbgs() << "Narrowing the search space by eliminating formulae " 4046 "which use a superset of registers used by other " 4047 "formulae.\n"); 4048 4049 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 4050 LSRUse &LU = Uses[LUIdx]; 4051 bool Any = false; 4052 for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) { 4053 Formula &F = LU.Formulae[i]; 4054 // Look for a formula with a constant or GV in a register. If the use 4055 // also has a formula with that same value in an immediate field, 4056 // delete the one that uses a register. 4057 for (SmallVectorImpl<const SCEV *>::const_iterator 4058 I = F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) { 4059 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*I)) { 4060 Formula NewF = F; 4061 NewF.BaseOffset += C->getValue()->getSExtValue(); 4062 NewF.BaseRegs.erase(NewF.BaseRegs.begin() + 4063 (I - F.BaseRegs.begin())); 4064 if (LU.HasFormulaWithSameRegs(NewF)) { 4065 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); dbgs() << '\n'); 4066 LU.DeleteFormula(F); 4067 --i; 4068 --e; 4069 Any = true; 4070 break; 4071 } 4072 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(*I)) { 4073 if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) 4074 if (!F.BaseGV) { 4075 Formula NewF = F; 4076 NewF.BaseGV = GV; 4077 NewF.BaseRegs.erase(NewF.BaseRegs.begin() + 4078 (I - F.BaseRegs.begin())); 4079 if (LU.HasFormulaWithSameRegs(NewF)) { 4080 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); 4081 dbgs() << '\n'); 4082 LU.DeleteFormula(F); 4083 --i; 4084 --e; 4085 Any = true; 4086 break; 4087 } 4088 } 4089 } 4090 } 4091 } 4092 if (Any) 4093 LU.RecomputeRegs(LUIdx, RegUses); 4094 } 4095 4096 DEBUG(dbgs() << "After pre-selection:\n"; 4097 print_uses(dbgs())); 4098 } 4099 } 4100 4101 /// NarrowSearchSpaceByCollapsingUnrolledCode - When there are many registers 4102 /// for expressions like A, A+1, A+2, etc., allocate a single register for 4103 /// them. 4104 void LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode() { 4105 if (EstimateSearchSpaceComplexity() < ComplexityLimit) 4106 return; 4107 4108 DEBUG(dbgs() << "The search space is too complex.\n" 4109 "Narrowing the search space by assuming that uses separated " 4110 "by a constant offset will use the same registers.\n"); 4111 4112 // This is especially useful for unrolled loops. 4113 4114 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 4115 LSRUse &LU = Uses[LUIdx]; 4116 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 4117 E = LU.Formulae.end(); I != E; ++I) { 4118 const Formula &F = *I; 4119 if (F.BaseOffset == 0 || (F.Scale != 0 && F.Scale != 1)) 4120 continue; 4121 4122 LSRUse *LUThatHas = FindUseWithSimilarFormula(F, LU); 4123 if (!LUThatHas) 4124 continue; 4125 4126 if (!reconcileNewOffset(*LUThatHas, F.BaseOffset, /*HasBaseReg=*/ false, 4127 LU.Kind, LU.AccessTy)) 4128 continue; 4129 4130 DEBUG(dbgs() << " Deleting use "; LU.print(dbgs()); dbgs() << '\n'); 4131 4132 LUThatHas->AllFixupsOutsideLoop &= LU.AllFixupsOutsideLoop; 4133 4134 // Update the relocs to reference the new use. 4135 for (SmallVectorImpl<LSRFixup>::iterator I = Fixups.begin(), 4136 E = Fixups.end(); I != E; ++I) { 4137 LSRFixup &Fixup = *I; 4138 if (Fixup.LUIdx == LUIdx) { 4139 Fixup.LUIdx = LUThatHas - &Uses.front(); 4140 Fixup.Offset += F.BaseOffset; 4141 // Add the new offset to LUThatHas' offset list. 4142 if (LUThatHas->Offsets.back() != Fixup.Offset) { 4143 LUThatHas->Offsets.push_back(Fixup.Offset); 4144 if (Fixup.Offset > LUThatHas->MaxOffset) 4145 LUThatHas->MaxOffset = Fixup.Offset; 4146 if (Fixup.Offset < LUThatHas->MinOffset) 4147 LUThatHas->MinOffset = Fixup.Offset; 4148 } 4149 DEBUG(dbgs() << "New fixup has offset " << Fixup.Offset << '\n'); 4150 } 4151 if (Fixup.LUIdx == NumUses-1) 4152 Fixup.LUIdx = LUIdx; 4153 } 4154 4155 // Delete formulae from the new use which are no longer legal. 4156 bool Any = false; 4157 for (size_t i = 0, e = LUThatHas->Formulae.size(); i != e; ++i) { 4158 Formula &F = LUThatHas->Formulae[i]; 4159 if (!isLegalUse(TTI, LUThatHas->MinOffset, LUThatHas->MaxOffset, 4160 LUThatHas->Kind, LUThatHas->AccessTy, F)) { 4161 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); 4162 dbgs() << '\n'); 4163 LUThatHas->DeleteFormula(F); 4164 --i; 4165 --e; 4166 Any = true; 4167 } 4168 } 4169 4170 if (Any) 4171 LUThatHas->RecomputeRegs(LUThatHas - &Uses.front(), RegUses); 4172 4173 // Delete the old use. 4174 DeleteUse(LU, LUIdx); 4175 --LUIdx; 4176 --NumUses; 4177 break; 4178 } 4179 } 4180 4181 DEBUG(dbgs() << "After pre-selection:\n"; print_uses(dbgs())); 4182 } 4183 4184 /// NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters - Call 4185 /// FilterOutUndesirableDedicatedRegisters again, if necessary, now that 4186 /// we've done more filtering, as it may be able to find more formulae to 4187 /// eliminate. 4188 void LSRInstance::NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters(){ 4189 if (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 4190 DEBUG(dbgs() << "The search space is too complex.\n"); 4191 4192 DEBUG(dbgs() << "Narrowing the search space by re-filtering out " 4193 "undesirable dedicated registers.\n"); 4194 4195 FilterOutUndesirableDedicatedRegisters(); 4196 4197 DEBUG(dbgs() << "After pre-selection:\n"; 4198 print_uses(dbgs())); 4199 } 4200 } 4201 4202 /// NarrowSearchSpaceByPickingWinnerRegs - Pick a register which seems likely 4203 /// to be profitable, and then in any use which has any reference to that 4204 /// register, delete all formulae which do not reference that register. 4205 void LSRInstance::NarrowSearchSpaceByPickingWinnerRegs() { 4206 // With all other options exhausted, loop until the system is simple 4207 // enough to handle. 4208 SmallPtrSet<const SCEV *, 4> Taken; 4209 while (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 4210 // Ok, we have too many of formulae on our hands to conveniently handle. 4211 // Use a rough heuristic to thin out the list. 4212 DEBUG(dbgs() << "The search space is too complex.\n"); 4213 4214 // Pick the register which is used by the most LSRUses, which is likely 4215 // to be a good reuse register candidate. 4216 const SCEV *Best = nullptr; 4217 unsigned BestNum = 0; 4218 for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); 4219 I != E; ++I) { 4220 const SCEV *Reg = *I; 4221 if (Taken.count(Reg)) 4222 continue; 4223 if (!Best) 4224 Best = Reg; 4225 else { 4226 unsigned Count = RegUses.getUsedByIndices(Reg).count(); 4227 if (Count > BestNum) { 4228 Best = Reg; 4229 BestNum = Count; 4230 } 4231 } 4232 } 4233 4234 DEBUG(dbgs() << "Narrowing the search space by assuming " << *Best 4235 << " will yield profitable reuse.\n"); 4236 Taken.insert(Best); 4237 4238 // In any use with formulae which references this register, delete formulae 4239 // which don't reference it. 4240 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 4241 LSRUse &LU = Uses[LUIdx]; 4242 if (!LU.Regs.count(Best)) continue; 4243 4244 bool Any = false; 4245 for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) { 4246 Formula &F = LU.Formulae[i]; 4247 if (!F.referencesReg(Best)) { 4248 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); dbgs() << '\n'); 4249 LU.DeleteFormula(F); 4250 --e; 4251 --i; 4252 Any = true; 4253 assert(e != 0 && "Use has no formulae left! Is Regs inconsistent?"); 4254 continue; 4255 } 4256 } 4257 4258 if (Any) 4259 LU.RecomputeRegs(LUIdx, RegUses); 4260 } 4261 4262 DEBUG(dbgs() << "After pre-selection:\n"; 4263 print_uses(dbgs())); 4264 } 4265 } 4266 4267 /// NarrowSearchSpaceUsingHeuristics - If there are an extraordinary number of 4268 /// formulae to choose from, use some rough heuristics to prune down the number 4269 /// of formulae. This keeps the main solver from taking an extraordinary amount 4270 /// of time in some worst-case scenarios. 4271 void LSRInstance::NarrowSearchSpaceUsingHeuristics() { 4272 NarrowSearchSpaceByDetectingSupersets(); 4273 NarrowSearchSpaceByCollapsingUnrolledCode(); 4274 NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters(); 4275 NarrowSearchSpaceByPickingWinnerRegs(); 4276 } 4277 4278 /// SolveRecurse - This is the recursive solver. 4279 void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution, 4280 Cost &SolutionCost, 4281 SmallVectorImpl<const Formula *> &Workspace, 4282 const Cost &CurCost, 4283 const SmallPtrSet<const SCEV *, 16> &CurRegs, 4284 DenseSet<const SCEV *> &VisitedRegs) const { 4285 // Some ideas: 4286 // - prune more: 4287 // - use more aggressive filtering 4288 // - sort the formula so that the most profitable solutions are found first 4289 // - sort the uses too 4290 // - search faster: 4291 // - don't compute a cost, and then compare. compare while computing a cost 4292 // and bail early. 4293 // - track register sets with SmallBitVector 4294 4295 const LSRUse &LU = Uses[Workspace.size()]; 4296 4297 // If this use references any register that's already a part of the 4298 // in-progress solution, consider it a requirement that a formula must 4299 // reference that register in order to be considered. This prunes out 4300 // unprofitable searching. 4301 SmallSetVector<const SCEV *, 4> ReqRegs; 4302 for (const SCEV *S : CurRegs) 4303 if (LU.Regs.count(S)) 4304 ReqRegs.insert(S); 4305 4306 SmallPtrSet<const SCEV *, 16> NewRegs; 4307 Cost NewCost; 4308 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 4309 E = LU.Formulae.end(); I != E; ++I) { 4310 const Formula &F = *I; 4311 4312 // Ignore formulae which may not be ideal in terms of register reuse of 4313 // ReqRegs. The formula should use all required registers before 4314 // introducing new ones. 4315 int NumReqRegsToFind = std::min(F.getNumRegs(), ReqRegs.size()); 4316 for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(), 4317 JE = ReqRegs.end(); J != JE; ++J) { 4318 const SCEV *Reg = *J; 4319 if ((F.ScaledReg && F.ScaledReg == Reg) || 4320 std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) != 4321 F.BaseRegs.end()) { 4322 --NumReqRegsToFind; 4323 if (NumReqRegsToFind == 0) 4324 break; 4325 } 4326 } 4327 if (NumReqRegsToFind != 0) { 4328 // If none of the formulae satisfied the required registers, then we could 4329 // clear ReqRegs and try again. Currently, we simply give up in this case. 4330 continue; 4331 } 4332 4333 // Evaluate the cost of the current formula. If it's already worse than 4334 // the current best, prune the search at that point. 4335 NewCost = CurCost; 4336 NewRegs = CurRegs; 4337 NewCost.RateFormula(TTI, F, NewRegs, VisitedRegs, L, LU.Offsets, SE, DT, 4338 LU); 4339 if (NewCost < SolutionCost) { 4340 Workspace.push_back(&F); 4341 if (Workspace.size() != Uses.size()) { 4342 SolveRecurse(Solution, SolutionCost, Workspace, NewCost, 4343 NewRegs, VisitedRegs); 4344 if (F.getNumRegs() == 1 && Workspace.size() == 1) 4345 VisitedRegs.insert(F.ScaledReg ? F.ScaledReg : F.BaseRegs[0]); 4346 } else { 4347 DEBUG(dbgs() << "New best at "; NewCost.print(dbgs()); 4348 dbgs() << ".\n Regs:"; 4349 for (const SCEV *S : NewRegs) 4350 dbgs() << ' ' << *S; 4351 dbgs() << '\n'); 4352 4353 SolutionCost = NewCost; 4354 Solution = Workspace; 4355 } 4356 Workspace.pop_back(); 4357 } 4358 } 4359 } 4360 4361 /// Solve - Choose one formula from each use. Return the results in the given 4362 /// Solution vector. 4363 void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const { 4364 SmallVector<const Formula *, 8> Workspace; 4365 Cost SolutionCost; 4366 SolutionCost.Lose(); 4367 Cost CurCost; 4368 SmallPtrSet<const SCEV *, 16> CurRegs; 4369 DenseSet<const SCEV *> VisitedRegs; 4370 Workspace.reserve(Uses.size()); 4371 4372 // SolveRecurse does all the work. 4373 SolveRecurse(Solution, SolutionCost, Workspace, CurCost, 4374 CurRegs, VisitedRegs); 4375 if (Solution.empty()) { 4376 DEBUG(dbgs() << "\nNo Satisfactory Solution\n"); 4377 return; 4378 } 4379 4380 // Ok, we've now made all our decisions. 4381 DEBUG(dbgs() << "\n" 4382 "The chosen solution requires "; SolutionCost.print(dbgs()); 4383 dbgs() << ":\n"; 4384 for (size_t i = 0, e = Uses.size(); i != e; ++i) { 4385 dbgs() << " "; 4386 Uses[i].print(dbgs()); 4387 dbgs() << "\n" 4388 " "; 4389 Solution[i]->print(dbgs()); 4390 dbgs() << '\n'; 4391 }); 4392 4393 assert(Solution.size() == Uses.size() && "Malformed solution!"); 4394 } 4395 4396 /// HoistInsertPosition - Helper for AdjustInsertPositionForExpand. Climb up 4397 /// the dominator tree far as we can go while still being dominated by the 4398 /// input positions. This helps canonicalize the insert position, which 4399 /// encourages sharing. 4400 BasicBlock::iterator 4401 LSRInstance::HoistInsertPosition(BasicBlock::iterator IP, 4402 const SmallVectorImpl<Instruction *> &Inputs) 4403 const { 4404 for (;;) { 4405 const Loop *IPLoop = LI.getLoopFor(IP->getParent()); 4406 unsigned IPLoopDepth = IPLoop ? IPLoop->getLoopDepth() : 0; 4407 4408 BasicBlock *IDom; 4409 for (DomTreeNode *Rung = DT.getNode(IP->getParent()); ; ) { 4410 if (!Rung) return IP; 4411 Rung = Rung->getIDom(); 4412 if (!Rung) return IP; 4413 IDom = Rung->getBlock(); 4414 4415 // Don't climb into a loop though. 4416 const Loop *IDomLoop = LI.getLoopFor(IDom); 4417 unsigned IDomDepth = IDomLoop ? IDomLoop->getLoopDepth() : 0; 4418 if (IDomDepth <= IPLoopDepth && 4419 (IDomDepth != IPLoopDepth || IDomLoop == IPLoop)) 4420 break; 4421 } 4422 4423 bool AllDominate = true; 4424 Instruction *BetterPos = nullptr; 4425 Instruction *Tentative = IDom->getTerminator(); 4426 for (SmallVectorImpl<Instruction *>::const_iterator I = Inputs.begin(), 4427 E = Inputs.end(); I != E; ++I) { 4428 Instruction *Inst = *I; 4429 if (Inst == Tentative || !DT.dominates(Inst, Tentative)) { 4430 AllDominate = false; 4431 break; 4432 } 4433 // Attempt to find an insert position in the middle of the block, 4434 // instead of at the end, so that it can be used for other expansions. 4435 if (IDom == Inst->getParent() && 4436 (!BetterPos || !DT.dominates(Inst, BetterPos))) 4437 BetterPos = std::next(BasicBlock::iterator(Inst)); 4438 } 4439 if (!AllDominate) 4440 break; 4441 if (BetterPos) 4442 IP = BetterPos; 4443 else 4444 IP = Tentative; 4445 } 4446 4447 return IP; 4448 } 4449 4450 /// AdjustInsertPositionForExpand - Determine an input position which will be 4451 /// dominated by the operands and which will dominate the result. 4452 BasicBlock::iterator 4453 LSRInstance::AdjustInsertPositionForExpand(BasicBlock::iterator LowestIP, 4454 const LSRFixup &LF, 4455 const LSRUse &LU, 4456 SCEVExpander &Rewriter) const { 4457 // Collect some instructions which must be dominated by the 4458 // expanding replacement. These must be dominated by any operands that 4459 // will be required in the expansion. 4460 SmallVector<Instruction *, 4> Inputs; 4461 if (Instruction *I = dyn_cast<Instruction>(LF.OperandValToReplace)) 4462 Inputs.push_back(I); 4463 if (LU.Kind == LSRUse::ICmpZero) 4464 if (Instruction *I = 4465 dyn_cast<Instruction>(cast<ICmpInst>(LF.UserInst)->getOperand(1))) 4466 Inputs.push_back(I); 4467 if (LF.PostIncLoops.count(L)) { 4468 if (LF.isUseFullyOutsideLoop(L)) 4469 Inputs.push_back(L->getLoopLatch()->getTerminator()); 4470 else 4471 Inputs.push_back(IVIncInsertPos); 4472 } 4473 // The expansion must also be dominated by the increment positions of any 4474 // loops it for which it is using post-inc mode. 4475 for (PostIncLoopSet::const_iterator I = LF.PostIncLoops.begin(), 4476 E = LF.PostIncLoops.end(); I != E; ++I) { 4477 const Loop *PIL = *I; 4478 if (PIL == L) continue; 4479 4480 // Be dominated by the loop exit. 4481 SmallVector<BasicBlock *, 4> ExitingBlocks; 4482 PIL->getExitingBlocks(ExitingBlocks); 4483 if (!ExitingBlocks.empty()) { 4484 BasicBlock *BB = ExitingBlocks[0]; 4485 for (unsigned i = 1, e = ExitingBlocks.size(); i != e; ++i) 4486 BB = DT.findNearestCommonDominator(BB, ExitingBlocks[i]); 4487 Inputs.push_back(BB->getTerminator()); 4488 } 4489 } 4490 4491 assert(!isa<PHINode>(LowestIP) && !isa<LandingPadInst>(LowestIP) 4492 && !isa<DbgInfoIntrinsic>(LowestIP) && 4493 "Insertion point must be a normal instruction"); 4494 4495 // Then, climb up the immediate dominator tree as far as we can go while 4496 // still being dominated by the input positions. 4497 BasicBlock::iterator IP = HoistInsertPosition(LowestIP, Inputs); 4498 4499 // Don't insert instructions before PHI nodes. 4500 while (isa<PHINode>(IP)) ++IP; 4501 4502 // Ignore landingpad instructions. 4503 while (isa<LandingPadInst>(IP)) ++IP; 4504 4505 // Ignore debug intrinsics. 4506 while (isa<DbgInfoIntrinsic>(IP)) ++IP; 4507 4508 // Set IP below instructions recently inserted by SCEVExpander. This keeps the 4509 // IP consistent across expansions and allows the previously inserted 4510 // instructions to be reused by subsequent expansion. 4511 while (Rewriter.isInsertedInstruction(IP) && IP != LowestIP) ++IP; 4512 4513 return IP; 4514 } 4515 4516 /// Expand - Emit instructions for the leading candidate expression for this 4517 /// LSRUse (this is called "expanding"). 4518 Value *LSRInstance::Expand(const LSRFixup &LF, 4519 const Formula &F, 4520 BasicBlock::iterator IP, 4521 SCEVExpander &Rewriter, 4522 SmallVectorImpl<WeakVH> &DeadInsts) const { 4523 const LSRUse &LU = Uses[LF.LUIdx]; 4524 if (LU.RigidFormula) 4525 return LF.OperandValToReplace; 4526 4527 // Determine an input position which will be dominated by the operands and 4528 // which will dominate the result. 4529 IP = AdjustInsertPositionForExpand(IP, LF, LU, Rewriter); 4530 4531 // Inform the Rewriter if we have a post-increment use, so that it can 4532 // perform an advantageous expansion. 4533 Rewriter.setPostInc(LF.PostIncLoops); 4534 4535 // This is the type that the user actually needs. 4536 Type *OpTy = LF.OperandValToReplace->getType(); 4537 // This will be the type that we'll initially expand to. 4538 Type *Ty = F.getType(); 4539 if (!Ty) 4540 // No type known; just expand directly to the ultimate type. 4541 Ty = OpTy; 4542 else if (SE.getEffectiveSCEVType(Ty) == SE.getEffectiveSCEVType(OpTy)) 4543 // Expand directly to the ultimate type if it's the right size. 4544 Ty = OpTy; 4545 // This is the type to do integer arithmetic in. 4546 Type *IntTy = SE.getEffectiveSCEVType(Ty); 4547 4548 // Build up a list of operands to add together to form the full base. 4549 SmallVector<const SCEV *, 8> Ops; 4550 4551 // Expand the BaseRegs portion. 4552 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 4553 E = F.BaseRegs.end(); I != E; ++I) { 4554 const SCEV *Reg = *I; 4555 assert(!Reg->isZero() && "Zero allocated in a base register!"); 4556 4557 // If we're expanding for a post-inc user, make the post-inc adjustment. 4558 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops); 4559 Reg = TransformForPostIncUse(Denormalize, Reg, 4560 LF.UserInst, LF.OperandValToReplace, 4561 Loops, SE, DT); 4562 4563 Ops.push_back(SE.getUnknown(Rewriter.expandCodeFor(Reg, nullptr, IP))); 4564 } 4565 4566 // Expand the ScaledReg portion. 4567 Value *ICmpScaledV = nullptr; 4568 if (F.Scale != 0) { 4569 const SCEV *ScaledS = F.ScaledReg; 4570 4571 // If we're expanding for a post-inc user, make the post-inc adjustment. 4572 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops); 4573 ScaledS = TransformForPostIncUse(Denormalize, ScaledS, 4574 LF.UserInst, LF.OperandValToReplace, 4575 Loops, SE, DT); 4576 4577 if (LU.Kind == LSRUse::ICmpZero) { 4578 // Expand ScaleReg as if it was part of the base regs. 4579 if (F.Scale == 1) 4580 Ops.push_back( 4581 SE.getUnknown(Rewriter.expandCodeFor(ScaledS, nullptr, IP))); 4582 else { 4583 // An interesting way of "folding" with an icmp is to use a negated 4584 // scale, which we'll implement by inserting it into the other operand 4585 // of the icmp. 4586 assert(F.Scale == -1 && 4587 "The only scale supported by ICmpZero uses is -1!"); 4588 ICmpScaledV = Rewriter.expandCodeFor(ScaledS, nullptr, IP); 4589 } 4590 } else { 4591 // Otherwise just expand the scaled register and an explicit scale, 4592 // which is expected to be matched as part of the address. 4593 4594 // Flush the operand list to suppress SCEVExpander hoisting address modes. 4595 // Unless the addressing mode will not be folded. 4596 if (!Ops.empty() && LU.Kind == LSRUse::Address && 4597 isAMCompletelyFolded(TTI, LU, F)) { 4598 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 4599 Ops.clear(); 4600 Ops.push_back(SE.getUnknown(FullV)); 4601 } 4602 ScaledS = SE.getUnknown(Rewriter.expandCodeFor(ScaledS, nullptr, IP)); 4603 if (F.Scale != 1) 4604 ScaledS = 4605 SE.getMulExpr(ScaledS, SE.getConstant(ScaledS->getType(), F.Scale)); 4606 Ops.push_back(ScaledS); 4607 } 4608 } 4609 4610 // Expand the GV portion. 4611 if (F.BaseGV) { 4612 // Flush the operand list to suppress SCEVExpander hoisting. 4613 if (!Ops.empty()) { 4614 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 4615 Ops.clear(); 4616 Ops.push_back(SE.getUnknown(FullV)); 4617 } 4618 Ops.push_back(SE.getUnknown(F.BaseGV)); 4619 } 4620 4621 // Flush the operand list to suppress SCEVExpander hoisting of both folded and 4622 // unfolded offsets. LSR assumes they both live next to their uses. 4623 if (!Ops.empty()) { 4624 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 4625 Ops.clear(); 4626 Ops.push_back(SE.getUnknown(FullV)); 4627 } 4628 4629 // Expand the immediate portion. 4630 int64_t Offset = (uint64_t)F.BaseOffset + LF.Offset; 4631 if (Offset != 0) { 4632 if (LU.Kind == LSRUse::ICmpZero) { 4633 // The other interesting way of "folding" with an ICmpZero is to use a 4634 // negated immediate. 4635 if (!ICmpScaledV) 4636 ICmpScaledV = ConstantInt::get(IntTy, -(uint64_t)Offset); 4637 else { 4638 Ops.push_back(SE.getUnknown(ICmpScaledV)); 4639 ICmpScaledV = ConstantInt::get(IntTy, Offset); 4640 } 4641 } else { 4642 // Just add the immediate values. These again are expected to be matched 4643 // as part of the address. 4644 Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy, Offset))); 4645 } 4646 } 4647 4648 // Expand the unfolded offset portion. 4649 int64_t UnfoldedOffset = F.UnfoldedOffset; 4650 if (UnfoldedOffset != 0) { 4651 // Just add the immediate values. 4652 Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy, 4653 UnfoldedOffset))); 4654 } 4655 4656 // Emit instructions summing all the operands. 4657 const SCEV *FullS = Ops.empty() ? 4658 SE.getConstant(IntTy, 0) : 4659 SE.getAddExpr(Ops); 4660 Value *FullV = Rewriter.expandCodeFor(FullS, Ty, IP); 4661 4662 // We're done expanding now, so reset the rewriter. 4663 Rewriter.clearPostInc(); 4664 4665 // An ICmpZero Formula represents an ICmp which we're handling as a 4666 // comparison against zero. Now that we've expanded an expression for that 4667 // form, update the ICmp's other operand. 4668 if (LU.Kind == LSRUse::ICmpZero) { 4669 ICmpInst *CI = cast<ICmpInst>(LF.UserInst); 4670 DeadInsts.push_back(CI->getOperand(1)); 4671 assert(!F.BaseGV && "ICmp does not support folding a global value and " 4672 "a scale at the same time!"); 4673 if (F.Scale == -1) { 4674 if (ICmpScaledV->getType() != OpTy) { 4675 Instruction *Cast = 4676 CastInst::Create(CastInst::getCastOpcode(ICmpScaledV, false, 4677 OpTy, false), 4678 ICmpScaledV, OpTy, "tmp", CI); 4679 ICmpScaledV = Cast; 4680 } 4681 CI->setOperand(1, ICmpScaledV); 4682 } else { 4683 // A scale of 1 means that the scale has been expanded as part of the 4684 // base regs. 4685 assert((F.Scale == 0 || F.Scale == 1) && 4686 "ICmp does not support folding a global value and " 4687 "a scale at the same time!"); 4688 Constant *C = ConstantInt::getSigned(SE.getEffectiveSCEVType(OpTy), 4689 -(uint64_t)Offset); 4690 if (C->getType() != OpTy) 4691 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 4692 OpTy, false), 4693 C, OpTy); 4694 4695 CI->setOperand(1, C); 4696 } 4697 } 4698 4699 return FullV; 4700 } 4701 4702 /// RewriteForPHI - Helper for Rewrite. PHI nodes are special because the use 4703 /// of their operands effectively happens in their predecessor blocks, so the 4704 /// expression may need to be expanded in multiple places. 4705 void LSRInstance::RewriteForPHI(PHINode *PN, 4706 const LSRFixup &LF, 4707 const Formula &F, 4708 SCEVExpander &Rewriter, 4709 SmallVectorImpl<WeakVH> &DeadInsts, 4710 Pass *P) const { 4711 DenseMap<BasicBlock *, Value *> Inserted; 4712 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 4713 if (PN->getIncomingValue(i) == LF.OperandValToReplace) { 4714 BasicBlock *BB = PN->getIncomingBlock(i); 4715 4716 // If this is a critical edge, split the edge so that we do not insert 4717 // the code on all predecessor/successor paths. We do this unless this 4718 // is the canonical backedge for this loop, which complicates post-inc 4719 // users. 4720 if (e != 1 && BB->getTerminator()->getNumSuccessors() > 1 && 4721 !isa<IndirectBrInst>(BB->getTerminator())) { 4722 BasicBlock *Parent = PN->getParent(); 4723 Loop *PNLoop = LI.getLoopFor(Parent); 4724 if (!PNLoop || Parent != PNLoop->getHeader()) { 4725 // Split the critical edge. 4726 BasicBlock *NewBB = nullptr; 4727 if (!Parent->isLandingPad()) { 4728 NewBB = SplitCriticalEdge(BB, Parent, 4729 CriticalEdgeSplittingOptions(&DT, &LI) 4730 .setMergeIdenticalEdges() 4731 .setDontDeleteUselessPHIs()); 4732 } else { 4733 SmallVector<BasicBlock*, 2> NewBBs; 4734 SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, 4735 /*AliasAnalysis*/ nullptr, &DT, &LI); 4736 NewBB = NewBBs[0]; 4737 } 4738 // If NewBB==NULL, then SplitCriticalEdge refused to split because all 4739 // phi predecessors are identical. The simple thing to do is skip 4740 // splitting in this case rather than complicate the API. 4741 if (NewBB) { 4742 // If PN is outside of the loop and BB is in the loop, we want to 4743 // move the block to be immediately before the PHI block, not 4744 // immediately after BB. 4745 if (L->contains(BB) && !L->contains(PN)) 4746 NewBB->moveBefore(PN->getParent()); 4747 4748 // Splitting the edge can reduce the number of PHI entries we have. 4749 e = PN->getNumIncomingValues(); 4750 BB = NewBB; 4751 i = PN->getBasicBlockIndex(BB); 4752 } 4753 } 4754 } 4755 4756 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> Pair = 4757 Inserted.insert(std::make_pair(BB, static_cast<Value *>(nullptr))); 4758 if (!Pair.second) 4759 PN->setIncomingValue(i, Pair.first->second); 4760 else { 4761 Value *FullV = Expand(LF, F, BB->getTerminator(), Rewriter, DeadInsts); 4762 4763 // If this is reuse-by-noop-cast, insert the noop cast. 4764 Type *OpTy = LF.OperandValToReplace->getType(); 4765 if (FullV->getType() != OpTy) 4766 FullV = 4767 CastInst::Create(CastInst::getCastOpcode(FullV, false, 4768 OpTy, false), 4769 FullV, LF.OperandValToReplace->getType(), 4770 "tmp", BB->getTerminator()); 4771 4772 PN->setIncomingValue(i, FullV); 4773 Pair.first->second = FullV; 4774 } 4775 } 4776 } 4777 4778 /// Rewrite - Emit instructions for the leading candidate expression for this 4779 /// LSRUse (this is called "expanding"), and update the UserInst to reference 4780 /// the newly expanded value. 4781 void LSRInstance::Rewrite(const LSRFixup &LF, 4782 const Formula &F, 4783 SCEVExpander &Rewriter, 4784 SmallVectorImpl<WeakVH> &DeadInsts, 4785 Pass *P) const { 4786 // First, find an insertion point that dominates UserInst. For PHI nodes, 4787 // find the nearest block which dominates all the relevant uses. 4788 if (PHINode *PN = dyn_cast<PHINode>(LF.UserInst)) { 4789 RewriteForPHI(PN, LF, F, Rewriter, DeadInsts, P); 4790 } else { 4791 Value *FullV = Expand(LF, F, LF.UserInst, Rewriter, DeadInsts); 4792 4793 // If this is reuse-by-noop-cast, insert the noop cast. 4794 Type *OpTy = LF.OperandValToReplace->getType(); 4795 if (FullV->getType() != OpTy) { 4796 Instruction *Cast = 4797 CastInst::Create(CastInst::getCastOpcode(FullV, false, OpTy, false), 4798 FullV, OpTy, "tmp", LF.UserInst); 4799 FullV = Cast; 4800 } 4801 4802 // Update the user. ICmpZero is handled specially here (for now) because 4803 // Expand may have updated one of the operands of the icmp already, and 4804 // its new value may happen to be equal to LF.OperandValToReplace, in 4805 // which case doing replaceUsesOfWith leads to replacing both operands 4806 // with the same value. TODO: Reorganize this. 4807 if (Uses[LF.LUIdx].Kind == LSRUse::ICmpZero) 4808 LF.UserInst->setOperand(0, FullV); 4809 else 4810 LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV); 4811 } 4812 4813 DeadInsts.push_back(LF.OperandValToReplace); 4814 } 4815 4816 /// ImplementSolution - Rewrite all the fixup locations with new values, 4817 /// following the chosen solution. 4818 void 4819 LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, 4820 Pass *P) { 4821 // Keep track of instructions we may have made dead, so that 4822 // we can remove them after we are done working. 4823 SmallVector<WeakVH, 16> DeadInsts; 4824 4825 SCEVExpander Rewriter(SE, L->getHeader()->getModule()->getDataLayout(), 4826 "lsr"); 4827 #ifndef NDEBUG 4828 Rewriter.setDebugType(DEBUG_TYPE); 4829 #endif 4830 Rewriter.disableCanonicalMode(); 4831 Rewriter.enableLSRMode(); 4832 Rewriter.setIVIncInsertPos(L, IVIncInsertPos); 4833 4834 // Mark phi nodes that terminate chains so the expander tries to reuse them. 4835 for (SmallVectorImpl<IVChain>::const_iterator ChainI = IVChainVec.begin(), 4836 ChainE = IVChainVec.end(); ChainI != ChainE; ++ChainI) { 4837 if (PHINode *PN = dyn_cast<PHINode>(ChainI->tailUserInst())) 4838 Rewriter.setChainedPhi(PN); 4839 } 4840 4841 // Expand the new value definitions and update the users. 4842 for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), 4843 E = Fixups.end(); I != E; ++I) { 4844 const LSRFixup &Fixup = *I; 4845 4846 Rewrite(Fixup, *Solution[Fixup.LUIdx], Rewriter, DeadInsts, P); 4847 4848 Changed = true; 4849 } 4850 4851 for (SmallVectorImpl<IVChain>::const_iterator ChainI = IVChainVec.begin(), 4852 ChainE = IVChainVec.end(); ChainI != ChainE; ++ChainI) { 4853 GenerateIVChain(*ChainI, Rewriter, DeadInsts); 4854 Changed = true; 4855 } 4856 // Clean up after ourselves. This must be done before deleting any 4857 // instructions. 4858 Rewriter.clear(); 4859 4860 Changed |= DeleteTriviallyDeadInstructions(DeadInsts); 4861 } 4862 4863 LSRInstance::LSRInstance(Loop *L, Pass *P) 4864 : IU(P->getAnalysis<IVUsers>()), SE(P->getAnalysis<ScalarEvolution>()), 4865 DT(P->getAnalysis<DominatorTreeWrapperPass>().getDomTree()), 4866 LI(P->getAnalysis<LoopInfoWrapperPass>().getLoopInfo()), 4867 TTI(P->getAnalysis<TargetTransformInfoWrapperPass>().getTTI( 4868 *L->getHeader()->getParent())), 4869 L(L), Changed(false), IVIncInsertPos(nullptr) { 4870 // If LoopSimplify form is not available, stay out of trouble. 4871 if (!L->isLoopSimplifyForm()) 4872 return; 4873 4874 // If there's no interesting work to be done, bail early. 4875 if (IU.empty()) return; 4876 4877 // If there's too much analysis to be done, bail early. We won't be able to 4878 // model the problem anyway. 4879 unsigned NumUsers = 0; 4880 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 4881 if (++NumUsers > MaxIVUsers) { 4882 DEBUG(dbgs() << "LSR skipping loop, too many IV Users in " << *L 4883 << "\n"); 4884 return; 4885 } 4886 } 4887 4888 #ifndef NDEBUG 4889 // All dominating loops must have preheaders, or SCEVExpander may not be able 4890 // to materialize an AddRecExpr whose Start is an outer AddRecExpr. 4891 // 4892 // IVUsers analysis should only create users that are dominated by simple loop 4893 // headers. Since this loop should dominate all of its users, its user list 4894 // should be empty if this loop itself is not within a simple loop nest. 4895 for (DomTreeNode *Rung = DT.getNode(L->getLoopPreheader()); 4896 Rung; Rung = Rung->getIDom()) { 4897 BasicBlock *BB = Rung->getBlock(); 4898 const Loop *DomLoop = LI.getLoopFor(BB); 4899 if (DomLoop && DomLoop->getHeader() == BB) { 4900 assert(DomLoop->getLoopPreheader() && "LSR needs a simplified loop nest"); 4901 } 4902 } 4903 #endif // DEBUG 4904 4905 DEBUG(dbgs() << "\nLSR on loop "; 4906 L->getHeader()->printAsOperand(dbgs(), /*PrintType=*/false); 4907 dbgs() << ":\n"); 4908 4909 // First, perform some low-level loop optimizations. 4910 OptimizeShadowIV(); 4911 OptimizeLoopTermCond(); 4912 4913 // If loop preparation eliminates all interesting IV users, bail. 4914 if (IU.empty()) return; 4915 4916 // Skip nested loops until we can model them better with formulae. 4917 if (!L->empty()) { 4918 DEBUG(dbgs() << "LSR skipping outer loop " << *L << "\n"); 4919 return; 4920 } 4921 4922 // Start collecting data and preparing for the solver. 4923 CollectChains(); 4924 CollectInterestingTypesAndFactors(); 4925 CollectFixupsAndInitialFormulae(); 4926 CollectLoopInvariantFixupsAndFormulae(); 4927 4928 assert(!Uses.empty() && "IVUsers reported at least one use"); 4929 DEBUG(dbgs() << "LSR found " << Uses.size() << " uses:\n"; 4930 print_uses(dbgs())); 4931 4932 // Now use the reuse data to generate a bunch of interesting ways 4933 // to formulate the values needed for the uses. 4934 GenerateAllReuseFormulae(); 4935 4936 FilterOutUndesirableDedicatedRegisters(); 4937 NarrowSearchSpaceUsingHeuristics(); 4938 4939 SmallVector<const Formula *, 8> Solution; 4940 Solve(Solution); 4941 4942 // Release memory that is no longer needed. 4943 Factors.clear(); 4944 Types.clear(); 4945 RegUses.clear(); 4946 4947 if (Solution.empty()) 4948 return; 4949 4950 #ifndef NDEBUG 4951 // Formulae should be legal. 4952 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), E = Uses.end(); 4953 I != E; ++I) { 4954 const LSRUse &LU = *I; 4955 for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), 4956 JE = LU.Formulae.end(); 4957 J != JE; ++J) 4958 assert(isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, 4959 *J) && "Illegal formula generated!"); 4960 }; 4961 #endif 4962 4963 // Now that we've decided what we want, make it so. 4964 ImplementSolution(Solution, P); 4965 } 4966 4967 void LSRInstance::print_factors_and_types(raw_ostream &OS) const { 4968 if (Factors.empty() && Types.empty()) return; 4969 4970 OS << "LSR has identified the following interesting factors and types: "; 4971 bool First = true; 4972 4973 for (SmallSetVector<int64_t, 8>::const_iterator 4974 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 4975 if (!First) OS << ", "; 4976 First = false; 4977 OS << '*' << *I; 4978 } 4979 4980 for (SmallSetVector<Type *, 4>::const_iterator 4981 I = Types.begin(), E = Types.end(); I != E; ++I) { 4982 if (!First) OS << ", "; 4983 First = false; 4984 OS << '(' << **I << ')'; 4985 } 4986 OS << '\n'; 4987 } 4988 4989 void LSRInstance::print_fixups(raw_ostream &OS) const { 4990 OS << "LSR is examining the following fixup sites:\n"; 4991 for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), 4992 E = Fixups.end(); I != E; ++I) { 4993 dbgs() << " "; 4994 I->print(OS); 4995 OS << '\n'; 4996 } 4997 } 4998 4999 void LSRInstance::print_uses(raw_ostream &OS) const { 5000 OS << "LSR is examining the following uses:\n"; 5001 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 5002 E = Uses.end(); I != E; ++I) { 5003 const LSRUse &LU = *I; 5004 dbgs() << " "; 5005 LU.print(OS); 5006 OS << '\n'; 5007 for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), 5008 JE = LU.Formulae.end(); J != JE; ++J) { 5009 OS << " "; 5010 J->print(OS); 5011 OS << '\n'; 5012 } 5013 } 5014 } 5015 5016 void LSRInstance::print(raw_ostream &OS) const { 5017 print_factors_and_types(OS); 5018 print_fixups(OS); 5019 print_uses(OS); 5020 } 5021 5022 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 5023 void LSRInstance::dump() const { 5024 print(errs()); errs() << '\n'; 5025 } 5026 #endif 5027 5028 namespace { 5029 5030 class LoopStrengthReduce : public LoopPass { 5031 public: 5032 static char ID; // Pass ID, replacement for typeid 5033 LoopStrengthReduce(); 5034 5035 private: 5036 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 5037 void getAnalysisUsage(AnalysisUsage &AU) const override; 5038 }; 5039 5040 } 5041 5042 char LoopStrengthReduce::ID = 0; 5043 INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce", 5044 "Loop Strength Reduction", false, false) 5045 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 5046 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 5047 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 5048 INITIALIZE_PASS_DEPENDENCY(IVUsers) 5049 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 5050 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 5051 INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce", 5052 "Loop Strength Reduction", false, false) 5053 5054 5055 Pass *llvm::createLoopStrengthReducePass() { 5056 return new LoopStrengthReduce(); 5057 } 5058 5059 LoopStrengthReduce::LoopStrengthReduce() : LoopPass(ID) { 5060 initializeLoopStrengthReducePass(*PassRegistry::getPassRegistry()); 5061 } 5062 5063 void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { 5064 // We split critical edges, so we change the CFG. However, we do update 5065 // many analyses if they are around. 5066 AU.addPreservedID(LoopSimplifyID); 5067 5068 AU.addRequired<LoopInfoWrapperPass>(); 5069 AU.addPreserved<LoopInfoWrapperPass>(); 5070 AU.addRequiredID(LoopSimplifyID); 5071 AU.addRequired<DominatorTreeWrapperPass>(); 5072 AU.addPreserved<DominatorTreeWrapperPass>(); 5073 AU.addRequired<ScalarEvolution>(); 5074 AU.addPreserved<ScalarEvolution>(); 5075 // Requiring LoopSimplify a second time here prevents IVUsers from running 5076 // twice, since LoopSimplify was invalidated by running ScalarEvolution. 5077 AU.addRequiredID(LoopSimplifyID); 5078 AU.addRequired<IVUsers>(); 5079 AU.addPreserved<IVUsers>(); 5080 AU.addRequired<TargetTransformInfoWrapperPass>(); 5081 } 5082 5083 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { 5084 if (skipOptnoneFunction(L)) 5085 return false; 5086 5087 bool Changed = false; 5088 5089 // Run the main LSR transformation. 5090 Changed |= LSRInstance(L, this).getChanged(); 5091 5092 // Remove any extra phis created by processing inner loops. 5093 Changed |= DeleteDeadPHIs(L->getHeader()); 5094 if (EnablePhiElim && L->isLoopSimplifyForm()) { 5095 SmallVector<WeakVH, 16> DeadInsts; 5096 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 5097 SCEVExpander Rewriter(getAnalysis<ScalarEvolution>(), DL, "lsr"); 5098 #ifndef NDEBUG 5099 Rewriter.setDebugType(DEBUG_TYPE); 5100 #endif 5101 unsigned numFolded = Rewriter.replaceCongruentIVs( 5102 L, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(), DeadInsts, 5103 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI( 5104 *L->getHeader()->getParent())); 5105 if (numFolded) { 5106 Changed = true; 5107 DeleteTriviallyDeadInstructions(DeadInsts); 5108 DeleteDeadPHIs(L->getHeader()); 5109 } 5110 } 5111 return Changed; 5112 } 5113