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/ValueHandle.h" 72 #include "llvm/Support/CommandLine.h" 73 #include "llvm/Support/Debug.h" 74 #include "llvm/Support/raw_ostream.h" 75 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 76 #include "llvm/Transforms/Utils/Local.h" 77 #include <algorithm> 78 using namespace llvm; 79 80 #define DEBUG_TYPE "loop-reduce" 81 82 /// MaxIVUsers is an arbitrary threshold that provides an early opportunitiy for 83 /// bail out. This threshold is far beyond the number of users that LSR can 84 /// conceivably solve, so it should not affect generated code, but catches the 85 /// worst cases before LSR burns too much compile time and stack space. 86 static const unsigned MaxIVUsers = 200; 87 88 // Temporary flag to cleanup congruent phis after LSR phi expansion. 89 // It's currently disabled until we can determine whether it's truly useful or 90 // not. The flag should be removed after the v3.0 release. 91 // This is now needed for ivchains. 92 static cl::opt<bool> EnablePhiElim( 93 "enable-lsr-phielim", cl::Hidden, cl::init(true), 94 cl::desc("Enable LSR phi elimination")); 95 96 #ifndef NDEBUG 97 // Stress test IV chain generation. 98 static cl::opt<bool> StressIVChain( 99 "stress-ivchain", cl::Hidden, cl::init(false), 100 cl::desc("Stress test LSR IV chains")); 101 #else 102 static bool StressIVChain = false; 103 #endif 104 105 namespace { 106 107 /// RegSortData - This class holds data which is used to order reuse candidates. 108 class RegSortData { 109 public: 110 /// UsedByIndices - This represents the set of LSRUse indices which reference 111 /// a particular register. 112 SmallBitVector UsedByIndices; 113 114 RegSortData() {} 115 116 void print(raw_ostream &OS) const; 117 void dump() const; 118 }; 119 120 } 121 122 void RegSortData::print(raw_ostream &OS) const { 123 OS << "[NumUses=" << UsedByIndices.count() << ']'; 124 } 125 126 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 127 void RegSortData::dump() const { 128 print(errs()); errs() << '\n'; 129 } 130 #endif 131 132 namespace { 133 134 /// RegUseTracker - Map register candidates to information about how they are 135 /// used. 136 class RegUseTracker { 137 typedef DenseMap<const SCEV *, RegSortData> RegUsesTy; 138 139 RegUsesTy RegUsesMap; 140 SmallVector<const SCEV *, 16> RegSequence; 141 142 public: 143 void CountRegister(const SCEV *Reg, size_t LUIdx); 144 void DropRegister(const SCEV *Reg, size_t LUIdx); 145 void SwapAndDropUse(size_t LUIdx, size_t LastLUIdx); 146 147 bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const; 148 149 const SmallBitVector &getUsedByIndices(const SCEV *Reg) const; 150 151 void clear(); 152 153 typedef SmallVectorImpl<const SCEV *>::iterator iterator; 154 typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator; 155 iterator begin() { return RegSequence.begin(); } 156 iterator end() { return RegSequence.end(); } 157 const_iterator begin() const { return RegSequence.begin(); } 158 const_iterator end() const { return RegSequence.end(); } 159 }; 160 161 } 162 163 void 164 RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) { 165 std::pair<RegUsesTy::iterator, bool> Pair = 166 RegUsesMap.insert(std::make_pair(Reg, RegSortData())); 167 RegSortData &RSD = Pair.first->second; 168 if (Pair.second) 169 RegSequence.push_back(Reg); 170 RSD.UsedByIndices.resize(std::max(RSD.UsedByIndices.size(), LUIdx + 1)); 171 RSD.UsedByIndices.set(LUIdx); 172 } 173 174 void 175 RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) { 176 RegUsesTy::iterator It = RegUsesMap.find(Reg); 177 assert(It != RegUsesMap.end()); 178 RegSortData &RSD = It->second; 179 assert(RSD.UsedByIndices.size() > LUIdx); 180 RSD.UsedByIndices.reset(LUIdx); 181 } 182 183 void 184 RegUseTracker::SwapAndDropUse(size_t LUIdx, size_t LastLUIdx) { 185 assert(LUIdx <= LastLUIdx); 186 187 // Update RegUses. The data structure is not optimized for this purpose; 188 // we must iterate through it and update each of the bit vectors. 189 for (RegUsesTy::iterator I = RegUsesMap.begin(), E = RegUsesMap.end(); 190 I != E; ++I) { 191 SmallBitVector &UsedByIndices = I->second.UsedByIndices; 192 if (LUIdx < UsedByIndices.size()) 193 UsedByIndices[LUIdx] = 194 LastLUIdx < UsedByIndices.size() ? UsedByIndices[LastLUIdx] : 0; 195 UsedByIndices.resize(std::min(UsedByIndices.size(), LastLUIdx)); 196 } 197 } 198 199 bool 200 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const { 201 RegUsesTy::const_iterator I = RegUsesMap.find(Reg); 202 if (I == RegUsesMap.end()) 203 return false; 204 const SmallBitVector &UsedByIndices = I->second.UsedByIndices; 205 int i = UsedByIndices.find_first(); 206 if (i == -1) return false; 207 if ((size_t)i != LUIdx) return true; 208 return UsedByIndices.find_next(i) != -1; 209 } 210 211 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const { 212 RegUsesTy::const_iterator I = RegUsesMap.find(Reg); 213 assert(I != RegUsesMap.end() && "Unknown register!"); 214 return I->second.UsedByIndices; 215 } 216 217 void RegUseTracker::clear() { 218 RegUsesMap.clear(); 219 RegSequence.clear(); 220 } 221 222 namespace { 223 224 /// Formula - This class holds information that describes a formula for 225 /// computing satisfying a use. It may include broken-out immediates and scaled 226 /// registers. 227 struct Formula { 228 /// Global base address used for complex addressing. 229 GlobalValue *BaseGV; 230 231 /// Base offset for complex addressing. 232 int64_t BaseOffset; 233 234 /// Whether any complex addressing has a base register. 235 bool HasBaseReg; 236 237 /// The scale of any complex addressing. 238 int64_t Scale; 239 240 /// BaseRegs - The list of "base" registers for this use. When this is 241 /// non-empty. The canonical representation of a formula is 242 /// 1. BaseRegs.size > 1 implies ScaledReg != NULL and 243 /// 2. ScaledReg != NULL implies Scale != 1 || !BaseRegs.empty(). 244 /// #1 enforces that the scaled register is always used when at least two 245 /// registers are needed by the formula: e.g., reg1 + reg2 is reg1 + 1 * reg2. 246 /// #2 enforces that 1 * reg is reg. 247 /// This invariant can be temporarly broken while building a formula. 248 /// However, every formula inserted into the LSRInstance must be in canonical 249 /// form. 250 SmallVector<const SCEV *, 4> BaseRegs; 251 252 /// ScaledReg - The 'scaled' register for this use. This should be non-null 253 /// when Scale is not zero. 254 const SCEV *ScaledReg; 255 256 /// UnfoldedOffset - An additional constant offset which added near the 257 /// use. This requires a temporary register, but the offset itself can 258 /// live in an add immediate field rather than a register. 259 int64_t UnfoldedOffset; 260 261 Formula() 262 : BaseGV(nullptr), BaseOffset(0), HasBaseReg(false), Scale(0), 263 ScaledReg(nullptr), UnfoldedOffset(0) {} 264 265 void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE); 266 267 bool isCanonical() const; 268 269 void Canonicalize(); 270 271 bool Unscale(); 272 273 size_t getNumRegs() const; 274 Type *getType() const; 275 276 void DeleteBaseReg(const SCEV *&S); 277 278 bool referencesReg(const SCEV *S) const; 279 bool hasRegsUsedByUsesOtherThan(size_t LUIdx, 280 const RegUseTracker &RegUses) const; 281 282 void print(raw_ostream &OS) const; 283 void dump() const; 284 }; 285 286 } 287 288 /// DoInitialMatch - Recursion helper for InitialMatch. 289 static void DoInitialMatch(const SCEV *S, Loop *L, 290 SmallVectorImpl<const SCEV *> &Good, 291 SmallVectorImpl<const SCEV *> &Bad, 292 ScalarEvolution &SE) { 293 // Collect expressions which properly dominate the loop header. 294 if (SE.properlyDominates(S, L->getHeader())) { 295 Good.push_back(S); 296 return; 297 } 298 299 // Look at add operands. 300 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 301 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 302 I != E; ++I) 303 DoInitialMatch(*I, L, Good, Bad, SE); 304 return; 305 } 306 307 // Look at addrec operands. 308 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 309 if (!AR->getStart()->isZero()) { 310 DoInitialMatch(AR->getStart(), L, Good, Bad, SE); 311 DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0), 312 AR->getStepRecurrence(SE), 313 // FIXME: AR->getNoWrapFlags() 314 AR->getLoop(), SCEV::FlagAnyWrap), 315 L, Good, Bad, SE); 316 return; 317 } 318 319 // Handle a multiplication by -1 (negation) if it didn't fold. 320 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) 321 if (Mul->getOperand(0)->isAllOnesValue()) { 322 SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end()); 323 const SCEV *NewMul = SE.getMulExpr(Ops); 324 325 SmallVector<const SCEV *, 4> MyGood; 326 SmallVector<const SCEV *, 4> MyBad; 327 DoInitialMatch(NewMul, L, MyGood, MyBad, SE); 328 const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue( 329 SE.getEffectiveSCEVType(NewMul->getType()))); 330 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(), 331 E = MyGood.end(); I != E; ++I) 332 Good.push_back(SE.getMulExpr(NegOne, *I)); 333 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(), 334 E = MyBad.end(); I != E; ++I) 335 Bad.push_back(SE.getMulExpr(NegOne, *I)); 336 return; 337 } 338 339 // Ok, we can't do anything interesting. Just stuff the whole thing into a 340 // register and hope for the best. 341 Bad.push_back(S); 342 } 343 344 /// InitialMatch - Incorporate loop-variant parts of S into this Formula, 345 /// attempting to keep all loop-invariant and loop-computable values in a 346 /// single base register. 347 void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) { 348 SmallVector<const SCEV *, 4> Good; 349 SmallVector<const SCEV *, 4> Bad; 350 DoInitialMatch(S, L, Good, Bad, SE); 351 if (!Good.empty()) { 352 const SCEV *Sum = SE.getAddExpr(Good); 353 if (!Sum->isZero()) 354 BaseRegs.push_back(Sum); 355 HasBaseReg = true; 356 } 357 if (!Bad.empty()) { 358 const SCEV *Sum = SE.getAddExpr(Bad); 359 if (!Sum->isZero()) 360 BaseRegs.push_back(Sum); 361 HasBaseReg = true; 362 } 363 Canonicalize(); 364 } 365 366 /// \brief Check whether or not this formula statisfies the canonical 367 /// representation. 368 /// \see Formula::BaseRegs. 369 bool Formula::isCanonical() const { 370 if (ScaledReg) 371 return Scale != 1 || !BaseRegs.empty(); 372 return BaseRegs.size() <= 1; 373 } 374 375 /// \brief Helper method to morph a formula into its canonical representation. 376 /// \see Formula::BaseRegs. 377 /// Every formula having more than one base register, must use the ScaledReg 378 /// field. Otherwise, we would have to do special cases everywhere in LSR 379 /// to treat reg1 + reg2 + ... the same way as reg1 + 1*reg2 + ... 380 /// On the other hand, 1*reg should be canonicalized into reg. 381 void Formula::Canonicalize() { 382 if (isCanonical()) 383 return; 384 // So far we did not need this case. This is easy to implement but it is 385 // useless to maintain dead code. Beside it could hurt compile time. 386 assert(!BaseRegs.empty() && "1*reg => reg, should not be needed."); 387 // Keep the invariant sum in BaseRegs and one of the variant sum in ScaledReg. 388 ScaledReg = BaseRegs.back(); 389 BaseRegs.pop_back(); 390 Scale = 1; 391 size_t BaseRegsSize = BaseRegs.size(); 392 size_t Try = 0; 393 // If ScaledReg is an invariant, try to find a variant expression. 394 while (Try < BaseRegsSize && !isa<SCEVAddRecExpr>(ScaledReg)) 395 std::swap(ScaledReg, BaseRegs[Try++]); 396 } 397 398 /// \brief Get rid of the scale in the formula. 399 /// In other words, this method morphes reg1 + 1*reg2 into reg1 + reg2. 400 /// \return true if it was possible to get rid of the scale, false otherwise. 401 /// \note After this operation the formula may not be in the canonical form. 402 bool Formula::Unscale() { 403 if (Scale != 1) 404 return false; 405 Scale = 0; 406 BaseRegs.push_back(ScaledReg); 407 ScaledReg = nullptr; 408 return true; 409 } 410 411 /// getNumRegs - Return the total number of register operands used by this 412 /// formula. This does not include register uses implied by non-constant 413 /// addrec strides. 414 size_t Formula::getNumRegs() const { 415 return !!ScaledReg + BaseRegs.size(); 416 } 417 418 /// getType - Return the type of this formula, if it has one, or null 419 /// otherwise. This type is meaningless except for the bit size. 420 Type *Formula::getType() const { 421 return !BaseRegs.empty() ? BaseRegs.front()->getType() : 422 ScaledReg ? ScaledReg->getType() : 423 BaseGV ? BaseGV->getType() : 424 nullptr; 425 } 426 427 /// DeleteBaseReg - Delete the given base reg from the BaseRegs list. 428 void Formula::DeleteBaseReg(const SCEV *&S) { 429 if (&S != &BaseRegs.back()) 430 std::swap(S, BaseRegs.back()); 431 BaseRegs.pop_back(); 432 } 433 434 /// referencesReg - Test if this formula references the given register. 435 bool Formula::referencesReg(const SCEV *S) const { 436 return S == ScaledReg || 437 std::find(BaseRegs.begin(), BaseRegs.end(), S) != BaseRegs.end(); 438 } 439 440 /// hasRegsUsedByUsesOtherThan - Test whether this formula uses registers 441 /// which are used by uses other than the use with the given index. 442 bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx, 443 const RegUseTracker &RegUses) const { 444 if (ScaledReg) 445 if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx)) 446 return true; 447 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), 448 E = BaseRegs.end(); I != E; ++I) 449 if (RegUses.isRegUsedByUsesOtherThan(*I, LUIdx)) 450 return true; 451 return false; 452 } 453 454 void Formula::print(raw_ostream &OS) const { 455 bool First = true; 456 if (BaseGV) { 457 if (!First) OS << " + "; else First = false; 458 BaseGV->printAsOperand(OS, /*PrintType=*/false); 459 } 460 if (BaseOffset != 0) { 461 if (!First) OS << " + "; else First = false; 462 OS << BaseOffset; 463 } 464 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), 465 E = BaseRegs.end(); I != E; ++I) { 466 if (!First) OS << " + "; else First = false; 467 OS << "reg(" << **I << ')'; 468 } 469 if (HasBaseReg && BaseRegs.empty()) { 470 if (!First) OS << " + "; else First = false; 471 OS << "**error: HasBaseReg**"; 472 } else if (!HasBaseReg && !BaseRegs.empty()) { 473 if (!First) OS << " + "; else First = false; 474 OS << "**error: !HasBaseReg**"; 475 } 476 if (Scale != 0) { 477 if (!First) OS << " + "; else First = false; 478 OS << Scale << "*reg("; 479 if (ScaledReg) 480 OS << *ScaledReg; 481 else 482 OS << "<unknown>"; 483 OS << ')'; 484 } 485 if (UnfoldedOffset != 0) { 486 if (!First) OS << " + "; 487 OS << "imm(" << UnfoldedOffset << ')'; 488 } 489 } 490 491 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 492 void Formula::dump() const { 493 print(errs()); errs() << '\n'; 494 } 495 #endif 496 497 /// isAddRecSExtable - Return true if the given addrec can be sign-extended 498 /// without changing its value. 499 static bool isAddRecSExtable(const SCEVAddRecExpr *AR, ScalarEvolution &SE) { 500 Type *WideTy = 501 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(AR->getType()) + 1); 502 return isa<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy)); 503 } 504 505 /// isAddSExtable - Return true if the given add can be sign-extended 506 /// without changing its value. 507 static bool isAddSExtable(const SCEVAddExpr *A, ScalarEvolution &SE) { 508 Type *WideTy = 509 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(A->getType()) + 1); 510 return isa<SCEVAddExpr>(SE.getSignExtendExpr(A, WideTy)); 511 } 512 513 /// isMulSExtable - Return true if the given mul can be sign-extended 514 /// without changing its value. 515 static bool isMulSExtable(const SCEVMulExpr *M, ScalarEvolution &SE) { 516 Type *WideTy = 517 IntegerType::get(SE.getContext(), 518 SE.getTypeSizeInBits(M->getType()) * M->getNumOperands()); 519 return isa<SCEVMulExpr>(SE.getSignExtendExpr(M, WideTy)); 520 } 521 522 /// getExactSDiv - Return an expression for LHS /s RHS, if it can be determined 523 /// and if the remainder is known to be zero, or null otherwise. If 524 /// IgnoreSignificantBits is true, expressions like (X * Y) /s Y are simplified 525 /// to Y, ignoring that the multiplication may overflow, which is useful when 526 /// the result will be used in a context where the most significant bits are 527 /// ignored. 528 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS, 529 ScalarEvolution &SE, 530 bool IgnoreSignificantBits = false) { 531 // Handle the trivial case, which works for any SCEV type. 532 if (LHS == RHS) 533 return SE.getConstant(LHS->getType(), 1); 534 535 // Handle a few RHS special cases. 536 const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS); 537 if (RC) { 538 const APInt &RA = RC->getValue()->getValue(); 539 // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do 540 // some folding. 541 if (RA.isAllOnesValue()) 542 return SE.getMulExpr(LHS, RC); 543 // Handle x /s 1 as x. 544 if (RA == 1) 545 return LHS; 546 } 547 548 // Check for a division of a constant by a constant. 549 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) { 550 if (!RC) 551 return nullptr; 552 const APInt &LA = C->getValue()->getValue(); 553 const APInt &RA = RC->getValue()->getValue(); 554 if (LA.srem(RA) != 0) 555 return nullptr; 556 return SE.getConstant(LA.sdiv(RA)); 557 } 558 559 // Distribute the sdiv over addrec operands, if the addrec doesn't overflow. 560 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) { 561 if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) { 562 const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE, 563 IgnoreSignificantBits); 564 if (!Step) return nullptr; 565 const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE, 566 IgnoreSignificantBits); 567 if (!Start) return nullptr; 568 // FlagNW is independent of the start value, step direction, and is 569 // preserved with smaller magnitude steps. 570 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 571 return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap); 572 } 573 return nullptr; 574 } 575 576 // Distribute the sdiv over add operands, if the add doesn't overflow. 577 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) { 578 if (IgnoreSignificantBits || isAddSExtable(Add, SE)) { 579 SmallVector<const SCEV *, 8> Ops; 580 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 581 I != E; ++I) { 582 const SCEV *Op = getExactSDiv(*I, RHS, SE, 583 IgnoreSignificantBits); 584 if (!Op) return nullptr; 585 Ops.push_back(Op); 586 } 587 return SE.getAddExpr(Ops); 588 } 589 return nullptr; 590 } 591 592 // Check for a multiply operand that we can pull RHS out of. 593 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(LHS)) { 594 if (IgnoreSignificantBits || isMulSExtable(Mul, SE)) { 595 SmallVector<const SCEV *, 4> Ops; 596 bool Found = false; 597 for (SCEVMulExpr::op_iterator I = Mul->op_begin(), E = Mul->op_end(); 598 I != E; ++I) { 599 const SCEV *S = *I; 600 if (!Found) 601 if (const SCEV *Q = getExactSDiv(S, RHS, SE, 602 IgnoreSignificantBits)) { 603 S = Q; 604 Found = true; 605 } 606 Ops.push_back(S); 607 } 608 return Found ? SE.getMulExpr(Ops) : nullptr; 609 } 610 return nullptr; 611 } 612 613 // Otherwise we don't know. 614 return nullptr; 615 } 616 617 /// ExtractImmediate - If S involves the addition of a constant integer value, 618 /// return that integer value, and mutate S to point to a new SCEV with that 619 /// value excluded. 620 static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) { 621 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 622 if (C->getValue()->getValue().getMinSignedBits() <= 64) { 623 S = SE.getConstant(C->getType(), 0); 624 return C->getValue()->getSExtValue(); 625 } 626 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 627 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end()); 628 int64_t Result = ExtractImmediate(NewOps.front(), SE); 629 if (Result != 0) 630 S = SE.getAddExpr(NewOps); 631 return Result; 632 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 633 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end()); 634 int64_t Result = ExtractImmediate(NewOps.front(), SE); 635 if (Result != 0) 636 S = SE.getAddRecExpr(NewOps, AR->getLoop(), 637 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 638 SCEV::FlagAnyWrap); 639 return Result; 640 } 641 return 0; 642 } 643 644 /// ExtractSymbol - If S involves the addition of a GlobalValue address, 645 /// return that symbol, and mutate S to point to a new SCEV with that 646 /// value excluded. 647 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) { 648 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 649 if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) { 650 S = SE.getConstant(GV->getType(), 0); 651 return GV; 652 } 653 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 654 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end()); 655 GlobalValue *Result = ExtractSymbol(NewOps.back(), SE); 656 if (Result) 657 S = SE.getAddExpr(NewOps); 658 return Result; 659 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 660 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end()); 661 GlobalValue *Result = ExtractSymbol(NewOps.front(), SE); 662 if (Result) 663 S = SE.getAddRecExpr(NewOps, AR->getLoop(), 664 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 665 SCEV::FlagAnyWrap); 666 return Result; 667 } 668 return nullptr; 669 } 670 671 /// isAddressUse - Returns true if the specified instruction is using the 672 /// specified value as an address. 673 static bool isAddressUse(Instruction *Inst, Value *OperandVal) { 674 bool isAddress = isa<LoadInst>(Inst); 675 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 676 if (SI->getOperand(1) == OperandVal) 677 isAddress = true; 678 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 679 // Addressing modes can also be folded into prefetches and a variety 680 // of intrinsics. 681 switch (II->getIntrinsicID()) { 682 default: break; 683 case Intrinsic::prefetch: 684 case Intrinsic::x86_sse_storeu_ps: 685 case Intrinsic::x86_sse2_storeu_pd: 686 case Intrinsic::x86_sse2_storeu_dq: 687 case Intrinsic::x86_sse2_storel_dq: 688 if (II->getArgOperand(0) == OperandVal) 689 isAddress = true; 690 break; 691 } 692 } 693 return isAddress; 694 } 695 696 /// getAccessType - Return the type of the memory being accessed. 697 static Type *getAccessType(const Instruction *Inst) { 698 Type *AccessTy = Inst->getType(); 699 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) 700 AccessTy = SI->getOperand(0)->getType(); 701 else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 702 // Addressing modes can also be folded into prefetches and a variety 703 // of intrinsics. 704 switch (II->getIntrinsicID()) { 705 default: break; 706 case Intrinsic::x86_sse_storeu_ps: 707 case Intrinsic::x86_sse2_storeu_pd: 708 case Intrinsic::x86_sse2_storeu_dq: 709 case Intrinsic::x86_sse2_storel_dq: 710 AccessTy = II->getArgOperand(0)->getType(); 711 break; 712 } 713 } 714 715 // All pointers have the same requirements, so canonicalize them to an 716 // arbitrary pointer type to minimize variation. 717 if (PointerType *PTy = dyn_cast<PointerType>(AccessTy)) 718 AccessTy = PointerType::get(IntegerType::get(PTy->getContext(), 1), 719 PTy->getAddressSpace()); 720 721 return AccessTy; 722 } 723 724 /// isExistingPhi - Return true if this AddRec is already a phi in its loop. 725 static bool isExistingPhi(const SCEVAddRecExpr *AR, ScalarEvolution &SE) { 726 for (BasicBlock::iterator I = AR->getLoop()->getHeader()->begin(); 727 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 728 if (SE.isSCEVable(PN->getType()) && 729 (SE.getEffectiveSCEVType(PN->getType()) == 730 SE.getEffectiveSCEVType(AR->getType())) && 731 SE.getSCEV(PN) == AR) 732 return true; 733 } 734 return false; 735 } 736 737 /// Check if expanding this expression is likely to incur significant cost. This 738 /// is tricky because SCEV doesn't track which expressions are actually computed 739 /// by the current IR. 740 /// 741 /// We currently allow expansion of IV increments that involve adds, 742 /// multiplication by constants, and AddRecs from existing phis. 743 /// 744 /// TODO: Allow UDivExpr if we can find an existing IV increment that is an 745 /// obvious multiple of the UDivExpr. 746 static bool isHighCostExpansion(const SCEV *S, 747 SmallPtrSet<const SCEV*, 8> &Processed, 748 ScalarEvolution &SE) { 749 // Zero/One operand expressions 750 switch (S->getSCEVType()) { 751 case scUnknown: 752 case scConstant: 753 return false; 754 case scTruncate: 755 return isHighCostExpansion(cast<SCEVTruncateExpr>(S)->getOperand(), 756 Processed, SE); 757 case scZeroExtend: 758 return isHighCostExpansion(cast<SCEVZeroExtendExpr>(S)->getOperand(), 759 Processed, SE); 760 case scSignExtend: 761 return isHighCostExpansion(cast<SCEVSignExtendExpr>(S)->getOperand(), 762 Processed, SE); 763 } 764 765 if (!Processed.insert(S)) 766 return false; 767 768 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 769 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 770 I != E; ++I) { 771 if (isHighCostExpansion(*I, Processed, SE)) 772 return true; 773 } 774 return false; 775 } 776 777 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 778 if (Mul->getNumOperands() == 2) { 779 // Multiplication by a constant is ok 780 if (isa<SCEVConstant>(Mul->getOperand(0))) 781 return isHighCostExpansion(Mul->getOperand(1), Processed, SE); 782 783 // If we have the value of one operand, check if an existing 784 // multiplication already generates this expression. 785 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Mul->getOperand(1))) { 786 Value *UVal = U->getValue(); 787 for (User *UR : UVal->users()) { 788 // If U is a constant, it may be used by a ConstantExpr. 789 Instruction *UI = dyn_cast<Instruction>(UR); 790 if (UI && UI->getOpcode() == Instruction::Mul && 791 SE.isSCEVable(UI->getType())) { 792 return SE.getSCEV(UI) == Mul; 793 } 794 } 795 } 796 } 797 } 798 799 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 800 if (isExistingPhi(AR, SE)) 801 return false; 802 } 803 804 // Fow now, consider any other type of expression (div/mul/min/max) high cost. 805 return true; 806 } 807 808 /// DeleteTriviallyDeadInstructions - If any of the instructions is the 809 /// specified set are trivially dead, delete them and see if this makes any of 810 /// their operands subsequently dead. 811 static bool 812 DeleteTriviallyDeadInstructions(SmallVectorImpl<WeakVH> &DeadInsts) { 813 bool Changed = false; 814 815 while (!DeadInsts.empty()) { 816 Value *V = DeadInsts.pop_back_val(); 817 Instruction *I = dyn_cast_or_null<Instruction>(V); 818 819 if (!I || !isInstructionTriviallyDead(I)) 820 continue; 821 822 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 823 if (Instruction *U = dyn_cast<Instruction>(*OI)) { 824 *OI = nullptr; 825 if (U->use_empty()) 826 DeadInsts.push_back(U); 827 } 828 829 I->eraseFromParent(); 830 Changed = true; 831 } 832 833 return Changed; 834 } 835 836 namespace { 837 class LSRUse; 838 } 839 840 /// \brief Check if the addressing mode defined by \p F is completely 841 /// folded in \p LU at isel time. 842 /// This includes address-mode folding and special icmp tricks. 843 /// This function returns true if \p LU can accommodate what \p F 844 /// defines and up to 1 base + 1 scaled + offset. 845 /// In other words, if \p F has several base registers, this function may 846 /// still return true. Therefore, users still need to account for 847 /// additional base registers and/or unfolded offsets to derive an 848 /// accurate cost model. 849 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 850 const LSRUse &LU, const Formula &F); 851 // Get the cost of the scaling factor used in F for LU. 852 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI, 853 const LSRUse &LU, const Formula &F); 854 855 namespace { 856 857 /// Cost - This class is used to measure and compare candidate formulae. 858 class Cost { 859 /// TODO: Some of these could be merged. Also, a lexical ordering 860 /// isn't always optimal. 861 unsigned NumRegs; 862 unsigned AddRecCost; 863 unsigned NumIVMuls; 864 unsigned NumBaseAdds; 865 unsigned ImmCost; 866 unsigned SetupCost; 867 unsigned ScaleCost; 868 869 public: 870 Cost() 871 : NumRegs(0), AddRecCost(0), NumIVMuls(0), NumBaseAdds(0), ImmCost(0), 872 SetupCost(0), ScaleCost(0) {} 873 874 bool operator<(const Cost &Other) const; 875 876 void Lose(); 877 878 #ifndef NDEBUG 879 // Once any of the metrics loses, they must all remain losers. 880 bool isValid() { 881 return ((NumRegs | AddRecCost | NumIVMuls | NumBaseAdds 882 | ImmCost | SetupCost | ScaleCost) != ~0u) 883 || ((NumRegs & AddRecCost & NumIVMuls & NumBaseAdds 884 & ImmCost & SetupCost & ScaleCost) == ~0u); 885 } 886 #endif 887 888 bool isLoser() { 889 assert(isValid() && "invalid cost"); 890 return NumRegs == ~0u; 891 } 892 893 void RateFormula(const TargetTransformInfo &TTI, 894 const Formula &F, 895 SmallPtrSet<const SCEV *, 16> &Regs, 896 const DenseSet<const SCEV *> &VisitedRegs, 897 const Loop *L, 898 const SmallVectorImpl<int64_t> &Offsets, 899 ScalarEvolution &SE, DominatorTree &DT, 900 const LSRUse &LU, 901 SmallPtrSet<const SCEV *, 16> *LoserRegs = nullptr); 902 903 void print(raw_ostream &OS) const; 904 void dump() const; 905 906 private: 907 void RateRegister(const SCEV *Reg, 908 SmallPtrSet<const SCEV *, 16> &Regs, 909 const Loop *L, 910 ScalarEvolution &SE, DominatorTree &DT); 911 void RatePrimaryRegister(const SCEV *Reg, 912 SmallPtrSet<const SCEV *, 16> &Regs, 913 const Loop *L, 914 ScalarEvolution &SE, DominatorTree &DT, 915 SmallPtrSet<const SCEV *, 16> *LoserRegs); 916 }; 917 918 } 919 920 /// RateRegister - Tally up interesting quantities from the given register. 921 void Cost::RateRegister(const SCEV *Reg, 922 SmallPtrSet<const SCEV *, 16> &Regs, 923 const Loop *L, 924 ScalarEvolution &SE, DominatorTree &DT) { 925 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Reg)) { 926 // If this is an addrec for another loop, don't second-guess its addrec phi 927 // nodes. LSR isn't currently smart enough to reason about more than one 928 // loop at a time. LSR has already run on inner loops, will not run on outer 929 // loops, and cannot be expected to change sibling loops. 930 if (AR->getLoop() != L) { 931 // If the AddRec exists, consider it's register free and leave it alone. 932 if (isExistingPhi(AR, SE)) 933 return; 934 935 // Otherwise, do not consider this formula at all. 936 Lose(); 937 return; 938 } 939 AddRecCost += 1; /// TODO: This should be a function of the stride. 940 941 // Add the step value register, if it needs one. 942 // TODO: The non-affine case isn't precisely modeled here. 943 if (!AR->isAffine() || !isa<SCEVConstant>(AR->getOperand(1))) { 944 if (!Regs.count(AR->getOperand(1))) { 945 RateRegister(AR->getOperand(1), Regs, L, SE, DT); 946 if (isLoser()) 947 return; 948 } 949 } 950 } 951 ++NumRegs; 952 953 // Rough heuristic; favor registers which don't require extra setup 954 // instructions in the preheader. 955 if (!isa<SCEVUnknown>(Reg) && 956 !isa<SCEVConstant>(Reg) && 957 !(isa<SCEVAddRecExpr>(Reg) && 958 (isa<SCEVUnknown>(cast<SCEVAddRecExpr>(Reg)->getStart()) || 959 isa<SCEVConstant>(cast<SCEVAddRecExpr>(Reg)->getStart())))) 960 ++SetupCost; 961 962 NumIVMuls += isa<SCEVMulExpr>(Reg) && 963 SE.hasComputableLoopEvolution(Reg, L); 964 } 965 966 /// RatePrimaryRegister - Record this register in the set. If we haven't seen it 967 /// before, rate it. Optional LoserRegs provides a way to declare any formula 968 /// that refers to one of those regs an instant loser. 969 void Cost::RatePrimaryRegister(const SCEV *Reg, 970 SmallPtrSet<const SCEV *, 16> &Regs, 971 const Loop *L, 972 ScalarEvolution &SE, DominatorTree &DT, 973 SmallPtrSet<const SCEV *, 16> *LoserRegs) { 974 if (LoserRegs && LoserRegs->count(Reg)) { 975 Lose(); 976 return; 977 } 978 if (Regs.insert(Reg)) { 979 RateRegister(Reg, Regs, L, SE, DT); 980 if (LoserRegs && isLoser()) 981 LoserRegs->insert(Reg); 982 } 983 } 984 985 void Cost::RateFormula(const TargetTransformInfo &TTI, 986 const Formula &F, 987 SmallPtrSet<const SCEV *, 16> &Regs, 988 const DenseSet<const SCEV *> &VisitedRegs, 989 const Loop *L, 990 const SmallVectorImpl<int64_t> &Offsets, 991 ScalarEvolution &SE, DominatorTree &DT, 992 const LSRUse &LU, 993 SmallPtrSet<const SCEV *, 16> *LoserRegs) { 994 assert(F.isCanonical() && "Cost is accurate only for canonical formula"); 995 // Tally up the registers. 996 if (const SCEV *ScaledReg = F.ScaledReg) { 997 if (VisitedRegs.count(ScaledReg)) { 998 Lose(); 999 return; 1000 } 1001 RatePrimaryRegister(ScaledReg, Regs, L, SE, DT, LoserRegs); 1002 if (isLoser()) 1003 return; 1004 } 1005 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 1006 E = F.BaseRegs.end(); I != E; ++I) { 1007 const SCEV *BaseReg = *I; 1008 if (VisitedRegs.count(BaseReg)) { 1009 Lose(); 1010 return; 1011 } 1012 RatePrimaryRegister(BaseReg, Regs, L, SE, DT, LoserRegs); 1013 if (isLoser()) 1014 return; 1015 } 1016 1017 // Determine how many (unfolded) adds we'll need inside the loop. 1018 size_t NumBaseParts = F.getNumRegs(); 1019 if (NumBaseParts > 1) 1020 // Do not count the base and a possible second register if the target 1021 // allows to fold 2 registers. 1022 NumBaseAdds += 1023 NumBaseParts - (1 + (F.Scale && isAMCompletelyFolded(TTI, LU, F))); 1024 NumBaseAdds += (F.UnfoldedOffset != 0); 1025 1026 // Accumulate non-free scaling amounts. 1027 ScaleCost += getScalingFactorCost(TTI, LU, F); 1028 1029 // Tally up the non-zero immediates. 1030 for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), 1031 E = Offsets.end(); I != E; ++I) { 1032 int64_t Offset = (uint64_t)*I + F.BaseOffset; 1033 if (F.BaseGV) 1034 ImmCost += 64; // Handle symbolic values conservatively. 1035 // TODO: This should probably be the pointer size. 1036 else if (Offset != 0) 1037 ImmCost += APInt(64, Offset, true).getMinSignedBits(); 1038 } 1039 assert(isValid() && "invalid cost"); 1040 } 1041 1042 /// Lose - Set this cost to a losing value. 1043 void Cost::Lose() { 1044 NumRegs = ~0u; 1045 AddRecCost = ~0u; 1046 NumIVMuls = ~0u; 1047 NumBaseAdds = ~0u; 1048 ImmCost = ~0u; 1049 SetupCost = ~0u; 1050 ScaleCost = ~0u; 1051 } 1052 1053 /// operator< - Choose the lower cost. 1054 bool Cost::operator<(const Cost &Other) const { 1055 return std::tie(NumRegs, AddRecCost, NumIVMuls, NumBaseAdds, ScaleCost, 1056 ImmCost, SetupCost) < 1057 std::tie(Other.NumRegs, Other.AddRecCost, Other.NumIVMuls, 1058 Other.NumBaseAdds, Other.ScaleCost, Other.ImmCost, 1059 Other.SetupCost); 1060 } 1061 1062 void Cost::print(raw_ostream &OS) const { 1063 OS << NumRegs << " reg" << (NumRegs == 1 ? "" : "s"); 1064 if (AddRecCost != 0) 1065 OS << ", with addrec cost " << AddRecCost; 1066 if (NumIVMuls != 0) 1067 OS << ", plus " << NumIVMuls << " IV mul" << (NumIVMuls == 1 ? "" : "s"); 1068 if (NumBaseAdds != 0) 1069 OS << ", plus " << NumBaseAdds << " base add" 1070 << (NumBaseAdds == 1 ? "" : "s"); 1071 if (ScaleCost != 0) 1072 OS << ", plus " << ScaleCost << " scale cost"; 1073 if (ImmCost != 0) 1074 OS << ", plus " << ImmCost << " imm cost"; 1075 if (SetupCost != 0) 1076 OS << ", plus " << SetupCost << " setup cost"; 1077 } 1078 1079 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1080 void Cost::dump() const { 1081 print(errs()); errs() << '\n'; 1082 } 1083 #endif 1084 1085 namespace { 1086 1087 /// LSRFixup - An operand value in an instruction which is to be replaced 1088 /// with some equivalent, possibly strength-reduced, replacement. 1089 struct LSRFixup { 1090 /// UserInst - The instruction which will be updated. 1091 Instruction *UserInst; 1092 1093 /// OperandValToReplace - The operand of the instruction which will 1094 /// be replaced. The operand may be used more than once; every instance 1095 /// will be replaced. 1096 Value *OperandValToReplace; 1097 1098 /// PostIncLoops - If this user is to use the post-incremented value of an 1099 /// induction variable, this variable is non-null and holds the loop 1100 /// associated with the induction variable. 1101 PostIncLoopSet PostIncLoops; 1102 1103 /// LUIdx - The index of the LSRUse describing the expression which 1104 /// this fixup needs, minus an offset (below). 1105 size_t LUIdx; 1106 1107 /// Offset - A constant offset to be added to the LSRUse expression. 1108 /// This allows multiple fixups to share the same LSRUse with different 1109 /// offsets, for example in an unrolled loop. 1110 int64_t Offset; 1111 1112 bool isUseFullyOutsideLoop(const Loop *L) const; 1113 1114 LSRFixup(); 1115 1116 void print(raw_ostream &OS) const; 1117 void dump() const; 1118 }; 1119 1120 } 1121 1122 LSRFixup::LSRFixup() 1123 : UserInst(nullptr), OperandValToReplace(nullptr), LUIdx(~size_t(0)), 1124 Offset(0) {} 1125 1126 /// isUseFullyOutsideLoop - Test whether this fixup always uses its 1127 /// value outside of the given loop. 1128 bool LSRFixup::isUseFullyOutsideLoop(const Loop *L) const { 1129 // PHI nodes use their value in their incoming blocks. 1130 if (const PHINode *PN = dyn_cast<PHINode>(UserInst)) { 1131 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1132 if (PN->getIncomingValue(i) == OperandValToReplace && 1133 L->contains(PN->getIncomingBlock(i))) 1134 return false; 1135 return true; 1136 } 1137 1138 return !L->contains(UserInst); 1139 } 1140 1141 void LSRFixup::print(raw_ostream &OS) const { 1142 OS << "UserInst="; 1143 // Store is common and interesting enough to be worth special-casing. 1144 if (StoreInst *Store = dyn_cast<StoreInst>(UserInst)) { 1145 OS << "store "; 1146 Store->getOperand(0)->printAsOperand(OS, /*PrintType=*/false); 1147 } else if (UserInst->getType()->isVoidTy()) 1148 OS << UserInst->getOpcodeName(); 1149 else 1150 UserInst->printAsOperand(OS, /*PrintType=*/false); 1151 1152 OS << ", OperandValToReplace="; 1153 OperandValToReplace->printAsOperand(OS, /*PrintType=*/false); 1154 1155 for (PostIncLoopSet::const_iterator I = PostIncLoops.begin(), 1156 E = PostIncLoops.end(); I != E; ++I) { 1157 OS << ", PostIncLoop="; 1158 (*I)->getHeader()->printAsOperand(OS, /*PrintType=*/false); 1159 } 1160 1161 if (LUIdx != ~size_t(0)) 1162 OS << ", LUIdx=" << LUIdx; 1163 1164 if (Offset != 0) 1165 OS << ", Offset=" << Offset; 1166 } 1167 1168 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1169 void LSRFixup::dump() const { 1170 print(errs()); errs() << '\n'; 1171 } 1172 #endif 1173 1174 namespace { 1175 1176 /// UniquifierDenseMapInfo - A DenseMapInfo implementation for holding 1177 /// DenseMaps and DenseSets of sorted SmallVectors of const SCEV*. 1178 struct UniquifierDenseMapInfo { 1179 static SmallVector<const SCEV *, 4> getEmptyKey() { 1180 SmallVector<const SCEV *, 4> V; 1181 V.push_back(reinterpret_cast<const SCEV *>(-1)); 1182 return V; 1183 } 1184 1185 static SmallVector<const SCEV *, 4> getTombstoneKey() { 1186 SmallVector<const SCEV *, 4> V; 1187 V.push_back(reinterpret_cast<const SCEV *>(-2)); 1188 return V; 1189 } 1190 1191 static unsigned getHashValue(const SmallVector<const SCEV *, 4> &V) { 1192 return static_cast<unsigned>(hash_combine_range(V.begin(), V.end())); 1193 } 1194 1195 static bool isEqual(const SmallVector<const SCEV *, 4> &LHS, 1196 const SmallVector<const SCEV *, 4> &RHS) { 1197 return LHS == RHS; 1198 } 1199 }; 1200 1201 /// LSRUse - This class holds the state that LSR keeps for each use in 1202 /// IVUsers, as well as uses invented by LSR itself. It includes information 1203 /// about what kinds of things can be folded into the user, information about 1204 /// the user itself, and information about how the use may be satisfied. 1205 /// TODO: Represent multiple users of the same expression in common? 1206 class LSRUse { 1207 DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier; 1208 1209 public: 1210 /// KindType - An enum for a kind of use, indicating what types of 1211 /// scaled and immediate operands it might support. 1212 enum KindType { 1213 Basic, ///< A normal use, with no folding. 1214 Special, ///< A special case of basic, allowing -1 scales. 1215 Address, ///< An address use; folding according to TargetLowering 1216 ICmpZero ///< An equality icmp with both operands folded into one. 1217 // TODO: Add a generic icmp too? 1218 }; 1219 1220 typedef PointerIntPair<const SCEV *, 2, KindType> SCEVUseKindPair; 1221 1222 KindType Kind; 1223 Type *AccessTy; 1224 1225 SmallVector<int64_t, 8> Offsets; 1226 int64_t MinOffset; 1227 int64_t MaxOffset; 1228 1229 /// AllFixupsOutsideLoop - This records whether all of the fixups using this 1230 /// LSRUse are outside of the loop, in which case some special-case heuristics 1231 /// may be used. 1232 bool AllFixupsOutsideLoop; 1233 1234 /// RigidFormula is set to true to guarantee that this use will be associated 1235 /// with a single formula--the one that initially matched. Some SCEV 1236 /// expressions cannot be expanded. This allows LSR to consider the registers 1237 /// used by those expressions without the need to expand them later after 1238 /// changing the formula. 1239 bool RigidFormula; 1240 1241 /// WidestFixupType - This records the widest use type for any fixup using 1242 /// this LSRUse. FindUseWithSimilarFormula can't consider uses with different 1243 /// max fixup widths to be equivalent, because the narrower one may be relying 1244 /// on the implicit truncation to truncate away bogus bits. 1245 Type *WidestFixupType; 1246 1247 /// Formulae - A list of ways to build a value that can satisfy this user. 1248 /// After the list is populated, one of these is selected heuristically and 1249 /// used to formulate a replacement for OperandValToReplace in UserInst. 1250 SmallVector<Formula, 12> Formulae; 1251 1252 /// Regs - The set of register candidates used by all formulae in this LSRUse. 1253 SmallPtrSet<const SCEV *, 4> Regs; 1254 1255 LSRUse(KindType K, Type *T) : Kind(K), AccessTy(T), 1256 MinOffset(INT64_MAX), 1257 MaxOffset(INT64_MIN), 1258 AllFixupsOutsideLoop(true), 1259 RigidFormula(false), 1260 WidestFixupType(nullptr) {} 1261 1262 bool HasFormulaWithSameRegs(const Formula &F) const; 1263 bool InsertFormula(const Formula &F); 1264 void DeleteFormula(Formula &F); 1265 void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses); 1266 1267 void print(raw_ostream &OS) const; 1268 void dump() const; 1269 }; 1270 1271 } 1272 1273 /// HasFormula - Test whether this use as a formula which has the same 1274 /// registers as the given formula. 1275 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const { 1276 SmallVector<const SCEV *, 4> Key = F.BaseRegs; 1277 if (F.ScaledReg) Key.push_back(F.ScaledReg); 1278 // Unstable sort by host order ok, because this is only used for uniquifying. 1279 std::sort(Key.begin(), Key.end()); 1280 return Uniquifier.count(Key); 1281 } 1282 1283 /// InsertFormula - If the given formula has not yet been inserted, add it to 1284 /// the list, and return true. Return false otherwise. 1285 /// The formula must be in canonical form. 1286 bool LSRUse::InsertFormula(const Formula &F) { 1287 assert(F.isCanonical() && "Invalid canonical representation"); 1288 1289 if (!Formulae.empty() && RigidFormula) 1290 return false; 1291 1292 SmallVector<const SCEV *, 4> Key = F.BaseRegs; 1293 if (F.ScaledReg) Key.push_back(F.ScaledReg); 1294 // Unstable sort by host order ok, because this is only used for uniquifying. 1295 std::sort(Key.begin(), Key.end()); 1296 1297 if (!Uniquifier.insert(Key).second) 1298 return false; 1299 1300 // Using a register to hold the value of 0 is not profitable. 1301 assert((!F.ScaledReg || !F.ScaledReg->isZero()) && 1302 "Zero allocated in a scaled register!"); 1303 #ifndef NDEBUG 1304 for (SmallVectorImpl<const SCEV *>::const_iterator I = 1305 F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) 1306 assert(!(*I)->isZero() && "Zero allocated in a base register!"); 1307 #endif 1308 1309 // Add the formula to the list. 1310 Formulae.push_back(F); 1311 1312 // Record registers now being used by this use. 1313 Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); 1314 if (F.ScaledReg) 1315 Regs.insert(F.ScaledReg); 1316 1317 return true; 1318 } 1319 1320 /// DeleteFormula - Remove the given formula from this use's list. 1321 void LSRUse::DeleteFormula(Formula &F) { 1322 if (&F != &Formulae.back()) 1323 std::swap(F, Formulae.back()); 1324 Formulae.pop_back(); 1325 } 1326 1327 /// RecomputeRegs - Recompute the Regs field, and update RegUses. 1328 void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) { 1329 // Now that we've filtered out some formulae, recompute the Regs set. 1330 SmallPtrSet<const SCEV *, 4> OldRegs = Regs; 1331 Regs.clear(); 1332 for (SmallVectorImpl<Formula>::const_iterator I = Formulae.begin(), 1333 E = Formulae.end(); I != E; ++I) { 1334 const Formula &F = *I; 1335 if (F.ScaledReg) Regs.insert(F.ScaledReg); 1336 Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); 1337 } 1338 1339 // Update the RegTracker. 1340 for (SmallPtrSet<const SCEV *, 4>::iterator I = OldRegs.begin(), 1341 E = OldRegs.end(); I != E; ++I) 1342 if (!Regs.count(*I)) 1343 RegUses.DropRegister(*I, LUIdx); 1344 } 1345 1346 void LSRUse::print(raw_ostream &OS) const { 1347 OS << "LSR Use: Kind="; 1348 switch (Kind) { 1349 case Basic: OS << "Basic"; break; 1350 case Special: OS << "Special"; break; 1351 case ICmpZero: OS << "ICmpZero"; break; 1352 case Address: 1353 OS << "Address of "; 1354 if (AccessTy->isPointerTy()) 1355 OS << "pointer"; // the full pointer type could be really verbose 1356 else 1357 OS << *AccessTy; 1358 } 1359 1360 OS << ", Offsets={"; 1361 for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), 1362 E = Offsets.end(); I != E; ++I) { 1363 OS << *I; 1364 if (std::next(I) != E) 1365 OS << ','; 1366 } 1367 OS << '}'; 1368 1369 if (AllFixupsOutsideLoop) 1370 OS << ", all-fixups-outside-loop"; 1371 1372 if (WidestFixupType) 1373 OS << ", widest fixup type: " << *WidestFixupType; 1374 } 1375 1376 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1377 void LSRUse::dump() const { 1378 print(errs()); errs() << '\n'; 1379 } 1380 #endif 1381 1382 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1383 LSRUse::KindType Kind, Type *AccessTy, 1384 GlobalValue *BaseGV, int64_t BaseOffset, 1385 bool HasBaseReg, int64_t Scale) { 1386 switch (Kind) { 1387 case LSRUse::Address: 1388 return TTI.isLegalAddressingMode(AccessTy, BaseGV, BaseOffset, HasBaseReg, Scale); 1389 1390 // Otherwise, just guess that reg+reg addressing is legal. 1391 //return ; 1392 1393 case LSRUse::ICmpZero: 1394 // There's not even a target hook for querying whether it would be legal to 1395 // fold a GV into an ICmp. 1396 if (BaseGV) 1397 return false; 1398 1399 // ICmp only has two operands; don't allow more than two non-trivial parts. 1400 if (Scale != 0 && HasBaseReg && BaseOffset != 0) 1401 return false; 1402 1403 // ICmp only supports no scale or a -1 scale, as we can "fold" a -1 scale by 1404 // putting the scaled register in the other operand of the icmp. 1405 if (Scale != 0 && Scale != -1) 1406 return false; 1407 1408 // If we have low-level target information, ask the target if it can fold an 1409 // integer immediate on an icmp. 1410 if (BaseOffset != 0) { 1411 // We have one of: 1412 // ICmpZero BaseReg + BaseOffset => ICmp BaseReg, -BaseOffset 1413 // ICmpZero -1*ScaleReg + BaseOffset => ICmp ScaleReg, BaseOffset 1414 // Offs is the ICmp immediate. 1415 if (Scale == 0) 1416 // The cast does the right thing with INT64_MIN. 1417 BaseOffset = -(uint64_t)BaseOffset; 1418 return TTI.isLegalICmpImmediate(BaseOffset); 1419 } 1420 1421 // ICmpZero BaseReg + -1*ScaleReg => ICmp BaseReg, ScaleReg 1422 return true; 1423 1424 case LSRUse::Basic: 1425 // Only handle single-register values. 1426 return !BaseGV && Scale == 0 && BaseOffset == 0; 1427 1428 case LSRUse::Special: 1429 // Special case Basic to handle -1 scales. 1430 return !BaseGV && (Scale == 0 || Scale == -1) && BaseOffset == 0; 1431 } 1432 1433 llvm_unreachable("Invalid LSRUse Kind!"); 1434 } 1435 1436 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1437 int64_t MinOffset, int64_t MaxOffset, 1438 LSRUse::KindType Kind, Type *AccessTy, 1439 GlobalValue *BaseGV, int64_t BaseOffset, 1440 bool HasBaseReg, int64_t Scale) { 1441 // Check for overflow. 1442 if (((int64_t)((uint64_t)BaseOffset + MinOffset) > BaseOffset) != 1443 (MinOffset > 0)) 1444 return false; 1445 MinOffset = (uint64_t)BaseOffset + MinOffset; 1446 if (((int64_t)((uint64_t)BaseOffset + MaxOffset) > BaseOffset) != 1447 (MaxOffset > 0)) 1448 return false; 1449 MaxOffset = (uint64_t)BaseOffset + MaxOffset; 1450 1451 return isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, MinOffset, 1452 HasBaseReg, Scale) && 1453 isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, MaxOffset, 1454 HasBaseReg, Scale); 1455 } 1456 1457 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1458 int64_t MinOffset, int64_t MaxOffset, 1459 LSRUse::KindType Kind, Type *AccessTy, 1460 const Formula &F) { 1461 // For the purpose of isAMCompletelyFolded either having a canonical formula 1462 // or a scale not equal to zero is correct. 1463 // Problems may arise from non canonical formulae having a scale == 0. 1464 // Strictly speaking it would best to just rely on canonical formulae. 1465 // However, when we generate the scaled formulae, we first check that the 1466 // scaling factor is profitable before computing the actual ScaledReg for 1467 // compile time sake. 1468 assert((F.isCanonical() || F.Scale != 0)); 1469 return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, 1470 F.BaseGV, F.BaseOffset, F.HasBaseReg, F.Scale); 1471 } 1472 1473 /// isLegalUse - Test whether we know how to expand the current formula. 1474 static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset, 1475 int64_t MaxOffset, LSRUse::KindType Kind, Type *AccessTy, 1476 GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, 1477 int64_t Scale) { 1478 // We know how to expand completely foldable formulae. 1479 return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, BaseGV, 1480 BaseOffset, HasBaseReg, Scale) || 1481 // Or formulae that use a base register produced by a sum of base 1482 // registers. 1483 (Scale == 1 && 1484 isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, 1485 BaseGV, BaseOffset, true, 0)); 1486 } 1487 1488 static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset, 1489 int64_t MaxOffset, LSRUse::KindType Kind, Type *AccessTy, 1490 const Formula &F) { 1491 return isLegalUse(TTI, MinOffset, MaxOffset, Kind, AccessTy, F.BaseGV, 1492 F.BaseOffset, F.HasBaseReg, F.Scale); 1493 } 1494 1495 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI, 1496 const LSRUse &LU, const Formula &F) { 1497 return isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, 1498 LU.AccessTy, F.BaseGV, F.BaseOffset, F.HasBaseReg, 1499 F.Scale); 1500 } 1501 1502 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI, 1503 const LSRUse &LU, const Formula &F) { 1504 if (!F.Scale) 1505 return 0; 1506 1507 // If the use is not completely folded in that instruction, we will have to 1508 // pay an extra cost only for scale != 1. 1509 if (!isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, 1510 LU.AccessTy, F)) 1511 return F.Scale != 1; 1512 1513 switch (LU.Kind) { 1514 case LSRUse::Address: { 1515 // Check the scaling factor cost with both the min and max offsets. 1516 int ScaleCostMinOffset = 1517 TTI.getScalingFactorCost(LU.AccessTy, F.BaseGV, 1518 F.BaseOffset + LU.MinOffset, 1519 F.HasBaseReg, F.Scale); 1520 int ScaleCostMaxOffset = 1521 TTI.getScalingFactorCost(LU.AccessTy, F.BaseGV, 1522 F.BaseOffset + LU.MaxOffset, 1523 F.HasBaseReg, F.Scale); 1524 1525 assert(ScaleCostMinOffset >= 0 && ScaleCostMaxOffset >= 0 && 1526 "Legal addressing mode has an illegal cost!"); 1527 return std::max(ScaleCostMinOffset, ScaleCostMaxOffset); 1528 } 1529 case LSRUse::ICmpZero: 1530 case LSRUse::Basic: 1531 case LSRUse::Special: 1532 // The use is completely folded, i.e., everything is folded into the 1533 // instruction. 1534 return 0; 1535 } 1536 1537 llvm_unreachable("Invalid LSRUse Kind!"); 1538 } 1539 1540 static bool isAlwaysFoldable(const TargetTransformInfo &TTI, 1541 LSRUse::KindType Kind, Type *AccessTy, 1542 GlobalValue *BaseGV, int64_t BaseOffset, 1543 bool HasBaseReg) { 1544 // Fast-path: zero is always foldable. 1545 if (BaseOffset == 0 && !BaseGV) return true; 1546 1547 // Conservatively, create an address with an immediate and a 1548 // base and a scale. 1549 int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1; 1550 1551 // Canonicalize a scale of 1 to a base register if the formula doesn't 1552 // already have a base register. 1553 if (!HasBaseReg && Scale == 1) { 1554 Scale = 0; 1555 HasBaseReg = true; 1556 } 1557 1558 return isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, BaseOffset, 1559 HasBaseReg, Scale); 1560 } 1561 1562 static bool isAlwaysFoldable(const TargetTransformInfo &TTI, 1563 ScalarEvolution &SE, int64_t MinOffset, 1564 int64_t MaxOffset, LSRUse::KindType Kind, 1565 Type *AccessTy, const SCEV *S, bool HasBaseReg) { 1566 // Fast-path: zero is always foldable. 1567 if (S->isZero()) return true; 1568 1569 // Conservatively, create an address with an immediate and a 1570 // base and a scale. 1571 int64_t BaseOffset = ExtractImmediate(S, SE); 1572 GlobalValue *BaseGV = ExtractSymbol(S, SE); 1573 1574 // If there's anything else involved, it's not foldable. 1575 if (!S->isZero()) return false; 1576 1577 // Fast-path: zero is always foldable. 1578 if (BaseOffset == 0 && !BaseGV) return true; 1579 1580 // Conservatively, create an address with an immediate and a 1581 // base and a scale. 1582 int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1; 1583 1584 return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, BaseGV, 1585 BaseOffset, HasBaseReg, Scale); 1586 } 1587 1588 namespace { 1589 1590 /// IVInc - An individual increment in a Chain of IV increments. 1591 /// Relate an IV user to an expression that computes the IV it uses from the IV 1592 /// used by the previous link in the Chain. 1593 /// 1594 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the 1595 /// original IVOperand. The head of the chain's IVOperand is only valid during 1596 /// chain collection, before LSR replaces IV users. During chain generation, 1597 /// IncExpr can be used to find the new IVOperand that computes the same 1598 /// expression. 1599 struct IVInc { 1600 Instruction *UserInst; 1601 Value* IVOperand; 1602 const SCEV *IncExpr; 1603 1604 IVInc(Instruction *U, Value *O, const SCEV *E): 1605 UserInst(U), IVOperand(O), IncExpr(E) {} 1606 }; 1607 1608 // IVChain - The list of IV increments in program order. 1609 // We typically add the head of a chain without finding subsequent links. 1610 struct IVChain { 1611 SmallVector<IVInc,1> Incs; 1612 const SCEV *ExprBase; 1613 1614 IVChain() : ExprBase(nullptr) {} 1615 1616 IVChain(const IVInc &Head, const SCEV *Base) 1617 : Incs(1, Head), ExprBase(Base) {} 1618 1619 typedef SmallVectorImpl<IVInc>::const_iterator const_iterator; 1620 1621 // begin - return the first increment in the chain. 1622 const_iterator begin() const { 1623 assert(!Incs.empty()); 1624 return std::next(Incs.begin()); 1625 } 1626 const_iterator end() const { 1627 return Incs.end(); 1628 } 1629 1630 // hasIncs - Returns true if this chain contains any increments. 1631 bool hasIncs() const { return Incs.size() >= 2; } 1632 1633 // add - Add an IVInc to the end of this chain. 1634 void add(const IVInc &X) { Incs.push_back(X); } 1635 1636 // tailUserInst - Returns the last UserInst in the chain. 1637 Instruction *tailUserInst() const { return Incs.back().UserInst; } 1638 1639 // isProfitableIncrement - Returns true if IncExpr can be profitably added to 1640 // this chain. 1641 bool isProfitableIncrement(const SCEV *OperExpr, 1642 const SCEV *IncExpr, 1643 ScalarEvolution&); 1644 }; 1645 1646 /// ChainUsers - Helper for CollectChains to track multiple IV increment uses. 1647 /// Distinguish between FarUsers that definitely cross IV increments and 1648 /// NearUsers that may be used between IV increments. 1649 struct ChainUsers { 1650 SmallPtrSet<Instruction*, 4> FarUsers; 1651 SmallPtrSet<Instruction*, 4> NearUsers; 1652 }; 1653 1654 /// LSRInstance - This class holds state for the main loop strength reduction 1655 /// logic. 1656 class LSRInstance { 1657 IVUsers &IU; 1658 ScalarEvolution &SE; 1659 DominatorTree &DT; 1660 LoopInfo &LI; 1661 const TargetTransformInfo &TTI; 1662 Loop *const L; 1663 bool Changed; 1664 1665 /// IVIncInsertPos - This is the insert position that the current loop's 1666 /// induction variable increment should be placed. In simple loops, this is 1667 /// the latch block's terminator. But in more complicated cases, this is a 1668 /// position which will dominate all the in-loop post-increment users. 1669 Instruction *IVIncInsertPos; 1670 1671 /// Factors - Interesting factors between use strides. 1672 SmallSetVector<int64_t, 8> Factors; 1673 1674 /// Types - Interesting use types, to facilitate truncation reuse. 1675 SmallSetVector<Type *, 4> Types; 1676 1677 /// Fixups - The list of operands which are to be replaced. 1678 SmallVector<LSRFixup, 16> Fixups; 1679 1680 /// Uses - The list of interesting uses. 1681 SmallVector<LSRUse, 16> Uses; 1682 1683 /// RegUses - Track which uses use which register candidates. 1684 RegUseTracker RegUses; 1685 1686 // Limit the number of chains to avoid quadratic behavior. We don't expect to 1687 // have more than a few IV increment chains in a loop. Missing a Chain falls 1688 // back to normal LSR behavior for those uses. 1689 static const unsigned MaxChains = 8; 1690 1691 /// IVChainVec - IV users can form a chain of IV increments. 1692 SmallVector<IVChain, MaxChains> IVChainVec; 1693 1694 /// IVIncSet - IV users that belong to profitable IVChains. 1695 SmallPtrSet<Use*, MaxChains> IVIncSet; 1696 1697 void OptimizeShadowIV(); 1698 bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse); 1699 ICmpInst *OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse); 1700 void OptimizeLoopTermCond(); 1701 1702 void ChainInstruction(Instruction *UserInst, Instruction *IVOper, 1703 SmallVectorImpl<ChainUsers> &ChainUsersVec); 1704 void FinalizeChain(IVChain &Chain); 1705 void CollectChains(); 1706 void GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, 1707 SmallVectorImpl<WeakVH> &DeadInsts); 1708 1709 void CollectInterestingTypesAndFactors(); 1710 void CollectFixupsAndInitialFormulae(); 1711 1712 LSRFixup &getNewFixup() { 1713 Fixups.push_back(LSRFixup()); 1714 return Fixups.back(); 1715 } 1716 1717 // Support for sharing of LSRUses between LSRFixups. 1718 typedef DenseMap<LSRUse::SCEVUseKindPair, size_t> UseMapTy; 1719 UseMapTy UseMap; 1720 1721 bool reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 1722 LSRUse::KindType Kind, Type *AccessTy); 1723 1724 std::pair<size_t, int64_t> getUse(const SCEV *&Expr, 1725 LSRUse::KindType Kind, 1726 Type *AccessTy); 1727 1728 void DeleteUse(LSRUse &LU, size_t LUIdx); 1729 1730 LSRUse *FindUseWithSimilarFormula(const Formula &F, const LSRUse &OrigLU); 1731 1732 void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx); 1733 void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx); 1734 void CountRegisters(const Formula &F, size_t LUIdx); 1735 bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F); 1736 1737 void CollectLoopInvariantFixupsAndFormulae(); 1738 1739 void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base, 1740 unsigned Depth = 0); 1741 1742 void GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx, 1743 const Formula &Base, unsigned Depth, 1744 size_t Idx, bool IsScaledReg = false); 1745 void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base); 1746 void GenerateSymbolicOffsetsImpl(LSRUse &LU, unsigned LUIdx, 1747 const Formula &Base, size_t Idx, 1748 bool IsScaledReg = false); 1749 void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base); 1750 void GenerateConstantOffsetsImpl(LSRUse &LU, unsigned LUIdx, 1751 const Formula &Base, 1752 const SmallVectorImpl<int64_t> &Worklist, 1753 size_t Idx, bool IsScaledReg = false); 1754 void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base); 1755 void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base); 1756 void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base); 1757 void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base); 1758 void GenerateCrossUseConstantOffsets(); 1759 void GenerateAllReuseFormulae(); 1760 1761 void FilterOutUndesirableDedicatedRegisters(); 1762 1763 size_t EstimateSearchSpaceComplexity() const; 1764 void NarrowSearchSpaceByDetectingSupersets(); 1765 void NarrowSearchSpaceByCollapsingUnrolledCode(); 1766 void NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters(); 1767 void NarrowSearchSpaceByPickingWinnerRegs(); 1768 void NarrowSearchSpaceUsingHeuristics(); 1769 1770 void SolveRecurse(SmallVectorImpl<const Formula *> &Solution, 1771 Cost &SolutionCost, 1772 SmallVectorImpl<const Formula *> &Workspace, 1773 const Cost &CurCost, 1774 const SmallPtrSet<const SCEV *, 16> &CurRegs, 1775 DenseSet<const SCEV *> &VisitedRegs) const; 1776 void Solve(SmallVectorImpl<const Formula *> &Solution) const; 1777 1778 BasicBlock::iterator 1779 HoistInsertPosition(BasicBlock::iterator IP, 1780 const SmallVectorImpl<Instruction *> &Inputs) const; 1781 BasicBlock::iterator 1782 AdjustInsertPositionForExpand(BasicBlock::iterator IP, 1783 const LSRFixup &LF, 1784 const LSRUse &LU, 1785 SCEVExpander &Rewriter) const; 1786 1787 Value *Expand(const LSRFixup &LF, 1788 const Formula &F, 1789 BasicBlock::iterator IP, 1790 SCEVExpander &Rewriter, 1791 SmallVectorImpl<WeakVH> &DeadInsts) const; 1792 void RewriteForPHI(PHINode *PN, const LSRFixup &LF, 1793 const Formula &F, 1794 SCEVExpander &Rewriter, 1795 SmallVectorImpl<WeakVH> &DeadInsts, 1796 Pass *P) const; 1797 void Rewrite(const LSRFixup &LF, 1798 const Formula &F, 1799 SCEVExpander &Rewriter, 1800 SmallVectorImpl<WeakVH> &DeadInsts, 1801 Pass *P) const; 1802 void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, 1803 Pass *P); 1804 1805 public: 1806 LSRInstance(Loop *L, Pass *P); 1807 1808 bool getChanged() const { return Changed; } 1809 1810 void print_factors_and_types(raw_ostream &OS) const; 1811 void print_fixups(raw_ostream &OS) const; 1812 void print_uses(raw_ostream &OS) const; 1813 void print(raw_ostream &OS) const; 1814 void dump() const; 1815 }; 1816 1817 } 1818 1819 /// OptimizeShadowIV - If IV is used in a int-to-float cast 1820 /// inside the loop then try to eliminate the cast operation. 1821 void LSRInstance::OptimizeShadowIV() { 1822 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L); 1823 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1824 return; 1825 1826 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); 1827 UI != E; /* empty */) { 1828 IVUsers::const_iterator CandidateUI = UI; 1829 ++UI; 1830 Instruction *ShadowUse = CandidateUI->getUser(); 1831 Type *DestTy = nullptr; 1832 bool IsSigned = false; 1833 1834 /* If shadow use is a int->float cast then insert a second IV 1835 to eliminate this cast. 1836 1837 for (unsigned i = 0; i < n; ++i) 1838 foo((double)i); 1839 1840 is transformed into 1841 1842 double d = 0.0; 1843 for (unsigned i = 0; i < n; ++i, ++d) 1844 foo(d); 1845 */ 1846 if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) { 1847 IsSigned = false; 1848 DestTy = UCast->getDestTy(); 1849 } 1850 else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) { 1851 IsSigned = true; 1852 DestTy = SCast->getDestTy(); 1853 } 1854 if (!DestTy) continue; 1855 1856 // If target does not support DestTy natively then do not apply 1857 // this transformation. 1858 if (!TTI.isTypeLegal(DestTy)) continue; 1859 1860 PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0)); 1861 if (!PH) continue; 1862 if (PH->getNumIncomingValues() != 2) continue; 1863 1864 Type *SrcTy = PH->getType(); 1865 int Mantissa = DestTy->getFPMantissaWidth(); 1866 if (Mantissa == -1) continue; 1867 if ((int)SE.getTypeSizeInBits(SrcTy) > Mantissa) 1868 continue; 1869 1870 unsigned Entry, Latch; 1871 if (PH->getIncomingBlock(0) == L->getLoopPreheader()) { 1872 Entry = 0; 1873 Latch = 1; 1874 } else { 1875 Entry = 1; 1876 Latch = 0; 1877 } 1878 1879 ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry)); 1880 if (!Init) continue; 1881 Constant *NewInit = ConstantFP::get(DestTy, IsSigned ? 1882 (double)Init->getSExtValue() : 1883 (double)Init->getZExtValue()); 1884 1885 BinaryOperator *Incr = 1886 dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch)); 1887 if (!Incr) continue; 1888 if (Incr->getOpcode() != Instruction::Add 1889 && Incr->getOpcode() != Instruction::Sub) 1890 continue; 1891 1892 /* Initialize new IV, double d = 0.0 in above example. */ 1893 ConstantInt *C = nullptr; 1894 if (Incr->getOperand(0) == PH) 1895 C = dyn_cast<ConstantInt>(Incr->getOperand(1)); 1896 else if (Incr->getOperand(1) == PH) 1897 C = dyn_cast<ConstantInt>(Incr->getOperand(0)); 1898 else 1899 continue; 1900 1901 if (!C) continue; 1902 1903 // Ignore negative constants, as the code below doesn't handle them 1904 // correctly. TODO: Remove this restriction. 1905 if (!C->getValue().isStrictlyPositive()) continue; 1906 1907 /* Add new PHINode. */ 1908 PHINode *NewPH = PHINode::Create(DestTy, 2, "IV.S.", PH); 1909 1910 /* create new increment. '++d' in above example. */ 1911 Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue()); 1912 BinaryOperator *NewIncr = 1913 BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ? 1914 Instruction::FAdd : Instruction::FSub, 1915 NewPH, CFP, "IV.S.next.", Incr); 1916 1917 NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry)); 1918 NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch)); 1919 1920 /* Remove cast operation */ 1921 ShadowUse->replaceAllUsesWith(NewPH); 1922 ShadowUse->eraseFromParent(); 1923 Changed = true; 1924 break; 1925 } 1926 } 1927 1928 /// FindIVUserForCond - If Cond has an operand that is an expression of an IV, 1929 /// set the IV user and stride information and return true, otherwise return 1930 /// false. 1931 bool LSRInstance::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse) { 1932 for (IVUsers::iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) 1933 if (UI->getUser() == Cond) { 1934 // NOTE: we could handle setcc instructions with multiple uses here, but 1935 // InstCombine does it as well for simple uses, it's not clear that it 1936 // occurs enough in real life to handle. 1937 CondUse = UI; 1938 return true; 1939 } 1940 return false; 1941 } 1942 1943 /// OptimizeMax - Rewrite the loop's terminating condition if it uses 1944 /// a max computation. 1945 /// 1946 /// This is a narrow solution to a specific, but acute, problem. For loops 1947 /// like this: 1948 /// 1949 /// i = 0; 1950 /// do { 1951 /// p[i] = 0.0; 1952 /// } while (++i < n); 1953 /// 1954 /// the trip count isn't just 'n', because 'n' might not be positive. And 1955 /// unfortunately this can come up even for loops where the user didn't use 1956 /// a C do-while loop. For example, seemingly well-behaved top-test loops 1957 /// will commonly be lowered like this: 1958 // 1959 /// if (n > 0) { 1960 /// i = 0; 1961 /// do { 1962 /// p[i] = 0.0; 1963 /// } while (++i < n); 1964 /// } 1965 /// 1966 /// and then it's possible for subsequent optimization to obscure the if 1967 /// test in such a way that indvars can't find it. 1968 /// 1969 /// When indvars can't find the if test in loops like this, it creates a 1970 /// max expression, which allows it to give the loop a canonical 1971 /// induction variable: 1972 /// 1973 /// i = 0; 1974 /// max = n < 1 ? 1 : n; 1975 /// do { 1976 /// p[i] = 0.0; 1977 /// } while (++i != max); 1978 /// 1979 /// Canonical induction variables are necessary because the loop passes 1980 /// are designed around them. The most obvious example of this is the 1981 /// LoopInfo analysis, which doesn't remember trip count values. It 1982 /// expects to be able to rediscover the trip count each time it is 1983 /// needed, and it does this using a simple analysis that only succeeds if 1984 /// the loop has a canonical induction variable. 1985 /// 1986 /// However, when it comes time to generate code, the maximum operation 1987 /// can be quite costly, especially if it's inside of an outer loop. 1988 /// 1989 /// This function solves this problem by detecting this type of loop and 1990 /// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting 1991 /// the instructions for the maximum computation. 1992 /// 1993 ICmpInst *LSRInstance::OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse) { 1994 // Check that the loop matches the pattern we're looking for. 1995 if (Cond->getPredicate() != CmpInst::ICMP_EQ && 1996 Cond->getPredicate() != CmpInst::ICMP_NE) 1997 return Cond; 1998 1999 SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1)); 2000 if (!Sel || !Sel->hasOneUse()) return Cond; 2001 2002 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L); 2003 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 2004 return Cond; 2005 const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1); 2006 2007 // Add one to the backedge-taken count to get the trip count. 2008 const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount); 2009 if (IterationCount != SE.getSCEV(Sel)) return Cond; 2010 2011 // Check for a max calculation that matches the pattern. There's no check 2012 // for ICMP_ULE here because the comparison would be with zero, which 2013 // isn't interesting. 2014 CmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE; 2015 const SCEVNAryExpr *Max = nullptr; 2016 if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(BackedgeTakenCount)) { 2017 Pred = ICmpInst::ICMP_SLE; 2018 Max = S; 2019 } else if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(IterationCount)) { 2020 Pred = ICmpInst::ICMP_SLT; 2021 Max = S; 2022 } else if (const SCEVUMaxExpr *U = dyn_cast<SCEVUMaxExpr>(IterationCount)) { 2023 Pred = ICmpInst::ICMP_ULT; 2024 Max = U; 2025 } else { 2026 // No match; bail. 2027 return Cond; 2028 } 2029 2030 // To handle a max with more than two operands, this optimization would 2031 // require additional checking and setup. 2032 if (Max->getNumOperands() != 2) 2033 return Cond; 2034 2035 const SCEV *MaxLHS = Max->getOperand(0); 2036 const SCEV *MaxRHS = Max->getOperand(1); 2037 2038 // ScalarEvolution canonicalizes constants to the left. For < and >, look 2039 // for a comparison with 1. For <= and >=, a comparison with zero. 2040 if (!MaxLHS || 2041 (ICmpInst::isTrueWhenEqual(Pred) ? !MaxLHS->isZero() : (MaxLHS != One))) 2042 return Cond; 2043 2044 // Check the relevant induction variable for conformance to 2045 // the pattern. 2046 const SCEV *IV = SE.getSCEV(Cond->getOperand(0)); 2047 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 2048 if (!AR || !AR->isAffine() || 2049 AR->getStart() != One || 2050 AR->getStepRecurrence(SE) != One) 2051 return Cond; 2052 2053 assert(AR->getLoop() == L && 2054 "Loop condition operand is an addrec in a different loop!"); 2055 2056 // Check the right operand of the select, and remember it, as it will 2057 // be used in the new comparison instruction. 2058 Value *NewRHS = nullptr; 2059 if (ICmpInst::isTrueWhenEqual(Pred)) { 2060 // Look for n+1, and grab n. 2061 if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(1))) 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 (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(2))) 2066 if (ConstantInt *BO1 = dyn_cast<ConstantInt>(BO->getOperand(1))) 2067 if (BO1->isOne() && SE.getSCEV(BO->getOperand(0)) == MaxRHS) 2068 NewRHS = BO->getOperand(0); 2069 if (!NewRHS) 2070 return Cond; 2071 } else if (SE.getSCEV(Sel->getOperand(1)) == MaxRHS) 2072 NewRHS = Sel->getOperand(1); 2073 else if (SE.getSCEV(Sel->getOperand(2)) == MaxRHS) 2074 NewRHS = Sel->getOperand(2); 2075 else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(MaxRHS)) 2076 NewRHS = SU->getValue(); 2077 else 2078 // Max doesn't match expected pattern. 2079 return Cond; 2080 2081 // Determine the new comparison opcode. It may be signed or unsigned, 2082 // and the original comparison may be either equality or inequality. 2083 if (Cond->getPredicate() == CmpInst::ICMP_EQ) 2084 Pred = CmpInst::getInversePredicate(Pred); 2085 2086 // Ok, everything looks ok to change the condition into an SLT or SGE and 2087 // delete the max calculation. 2088 ICmpInst *NewCond = 2089 new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp"); 2090 2091 // Delete the max calculation instructions. 2092 Cond->replaceAllUsesWith(NewCond); 2093 CondUse->setUser(NewCond); 2094 Instruction *Cmp = cast<Instruction>(Sel->getOperand(0)); 2095 Cond->eraseFromParent(); 2096 Sel->eraseFromParent(); 2097 if (Cmp->use_empty()) 2098 Cmp->eraseFromParent(); 2099 return NewCond; 2100 } 2101 2102 /// OptimizeLoopTermCond - Change loop terminating condition to use the 2103 /// postinc iv when possible. 2104 void 2105 LSRInstance::OptimizeLoopTermCond() { 2106 SmallPtrSet<Instruction *, 4> PostIncs; 2107 2108 BasicBlock *LatchBlock = L->getLoopLatch(); 2109 SmallVector<BasicBlock*, 8> ExitingBlocks; 2110 L->getExitingBlocks(ExitingBlocks); 2111 2112 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 2113 BasicBlock *ExitingBlock = ExitingBlocks[i]; 2114 2115 // Get the terminating condition for the loop if possible. If we 2116 // can, we want to change it to use a post-incremented version of its 2117 // induction variable, to allow coalescing the live ranges for the IV into 2118 // one register value. 2119 2120 BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 2121 if (!TermBr) 2122 continue; 2123 // FIXME: Overly conservative, termination condition could be an 'or' etc.. 2124 if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition())) 2125 continue; 2126 2127 // Search IVUsesByStride to find Cond's IVUse if there is one. 2128 IVStrideUse *CondUse = nullptr; 2129 ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition()); 2130 if (!FindIVUserForCond(Cond, CondUse)) 2131 continue; 2132 2133 // If the trip count is computed in terms of a max (due to ScalarEvolution 2134 // being unable to find a sufficient guard, for example), change the loop 2135 // comparison to use SLT or ULT instead of NE. 2136 // One consequence of doing this now is that it disrupts the count-down 2137 // optimization. That's not always a bad thing though, because in such 2138 // cases it may still be worthwhile to avoid a max. 2139 Cond = OptimizeMax(Cond, CondUse); 2140 2141 // If this exiting block dominates the latch block, it may also use 2142 // the post-inc value if it won't be shared with other uses. 2143 // Check for dominance. 2144 if (!DT.dominates(ExitingBlock, LatchBlock)) 2145 continue; 2146 2147 // Conservatively avoid trying to use the post-inc value in non-latch 2148 // exits if there may be pre-inc users in intervening blocks. 2149 if (LatchBlock != ExitingBlock) 2150 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) 2151 // Test if the use is reachable from the exiting block. This dominator 2152 // query is a conservative approximation of reachability. 2153 if (&*UI != CondUse && 2154 !DT.properlyDominates(UI->getUser()->getParent(), ExitingBlock)) { 2155 // Conservatively assume there may be reuse if the quotient of their 2156 // strides could be a legal scale. 2157 const SCEV *A = IU.getStride(*CondUse, L); 2158 const SCEV *B = IU.getStride(*UI, L); 2159 if (!A || !B) continue; 2160 if (SE.getTypeSizeInBits(A->getType()) != 2161 SE.getTypeSizeInBits(B->getType())) { 2162 if (SE.getTypeSizeInBits(A->getType()) > 2163 SE.getTypeSizeInBits(B->getType())) 2164 B = SE.getSignExtendExpr(B, A->getType()); 2165 else 2166 A = SE.getSignExtendExpr(A, B->getType()); 2167 } 2168 if (const SCEVConstant *D = 2169 dyn_cast_or_null<SCEVConstant>(getExactSDiv(B, A, SE))) { 2170 const ConstantInt *C = D->getValue(); 2171 // Stride of one or negative one can have reuse with non-addresses. 2172 if (C->isOne() || C->isAllOnesValue()) 2173 goto decline_post_inc; 2174 // Avoid weird situations. 2175 if (C->getValue().getMinSignedBits() >= 64 || 2176 C->getValue().isMinSignedValue()) 2177 goto decline_post_inc; 2178 // Check for possible scaled-address reuse. 2179 Type *AccessTy = getAccessType(UI->getUser()); 2180 int64_t Scale = C->getSExtValue(); 2181 if (TTI.isLegalAddressingMode(AccessTy, /*BaseGV=*/ nullptr, 2182 /*BaseOffset=*/ 0, 2183 /*HasBaseReg=*/ false, Scale)) 2184 goto decline_post_inc; 2185 Scale = -Scale; 2186 if (TTI.isLegalAddressingMode(AccessTy, /*BaseGV=*/ nullptr, 2187 /*BaseOffset=*/ 0, 2188 /*HasBaseReg=*/ false, Scale)) 2189 goto decline_post_inc; 2190 } 2191 } 2192 2193 DEBUG(dbgs() << " Change loop exiting icmp to use postinc iv: " 2194 << *Cond << '\n'); 2195 2196 // It's possible for the setcc instruction to be anywhere in the loop, and 2197 // possible for it to have multiple users. If it is not immediately before 2198 // the exiting block branch, move it. 2199 if (&*++BasicBlock::iterator(Cond) != TermBr) { 2200 if (Cond->hasOneUse()) { 2201 Cond->moveBefore(TermBr); 2202 } else { 2203 // Clone the terminating condition and insert into the loopend. 2204 ICmpInst *OldCond = Cond; 2205 Cond = cast<ICmpInst>(Cond->clone()); 2206 Cond->setName(L->getHeader()->getName() + ".termcond"); 2207 ExitingBlock->getInstList().insert(TermBr, Cond); 2208 2209 // Clone the IVUse, as the old use still exists! 2210 CondUse = &IU.AddUser(Cond, CondUse->getOperandValToReplace()); 2211 TermBr->replaceUsesOfWith(OldCond, Cond); 2212 } 2213 } 2214 2215 // If we get to here, we know that we can transform the setcc instruction to 2216 // use the post-incremented version of the IV, allowing us to coalesce the 2217 // live ranges for the IV correctly. 2218 CondUse->transformToPostInc(L); 2219 Changed = true; 2220 2221 PostIncs.insert(Cond); 2222 decline_post_inc:; 2223 } 2224 2225 // Determine an insertion point for the loop induction variable increment. It 2226 // must dominate all the post-inc comparisons we just set up, and it must 2227 // dominate the loop latch edge. 2228 IVIncInsertPos = L->getLoopLatch()->getTerminator(); 2229 for (SmallPtrSet<Instruction *, 4>::const_iterator I = PostIncs.begin(), 2230 E = PostIncs.end(); I != E; ++I) { 2231 BasicBlock *BB = 2232 DT.findNearestCommonDominator(IVIncInsertPos->getParent(), 2233 (*I)->getParent()); 2234 if (BB == (*I)->getParent()) 2235 IVIncInsertPos = *I; 2236 else if (BB != IVIncInsertPos->getParent()) 2237 IVIncInsertPos = BB->getTerminator(); 2238 } 2239 } 2240 2241 /// reconcileNewOffset - Determine if the given use can accommodate a fixup 2242 /// at the given offset and other details. If so, update the use and 2243 /// return true. 2244 bool 2245 LSRInstance::reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 2246 LSRUse::KindType Kind, Type *AccessTy) { 2247 int64_t NewMinOffset = LU.MinOffset; 2248 int64_t NewMaxOffset = LU.MaxOffset; 2249 Type *NewAccessTy = AccessTy; 2250 2251 // Check for a mismatched kind. It's tempting to collapse mismatched kinds to 2252 // something conservative, however this can pessimize in the case that one of 2253 // the uses will have all its uses outside the loop, for example. 2254 if (LU.Kind != Kind) 2255 return false; 2256 2257 // Check for a mismatched access type, and fall back conservatively as needed. 2258 // TODO: Be less conservative when the type is similar and can use the same 2259 // addressing modes. 2260 if (Kind == LSRUse::Address && AccessTy != LU.AccessTy) 2261 NewAccessTy = Type::getVoidTy(AccessTy->getContext()); 2262 2263 // Conservatively assume HasBaseReg is true for now. 2264 if (NewOffset < LU.MinOffset) { 2265 if (!isAlwaysFoldable(TTI, Kind, NewAccessTy, /*BaseGV=*/nullptr, 2266 LU.MaxOffset - NewOffset, HasBaseReg)) 2267 return false; 2268 NewMinOffset = NewOffset; 2269 } else if (NewOffset > LU.MaxOffset) { 2270 if (!isAlwaysFoldable(TTI, Kind, NewAccessTy, /*BaseGV=*/nullptr, 2271 NewOffset - LU.MinOffset, HasBaseReg)) 2272 return false; 2273 NewMaxOffset = NewOffset; 2274 } 2275 2276 // Update the use. 2277 LU.MinOffset = NewMinOffset; 2278 LU.MaxOffset = NewMaxOffset; 2279 LU.AccessTy = NewAccessTy; 2280 if (NewOffset != LU.Offsets.back()) 2281 LU.Offsets.push_back(NewOffset); 2282 return true; 2283 } 2284 2285 /// getUse - Return an LSRUse index and an offset value for a fixup which 2286 /// needs the given expression, with the given kind and optional access type. 2287 /// Either reuse an existing use or create a new one, as needed. 2288 std::pair<size_t, int64_t> 2289 LSRInstance::getUse(const SCEV *&Expr, 2290 LSRUse::KindType Kind, Type *AccessTy) { 2291 const SCEV *Copy = Expr; 2292 int64_t Offset = ExtractImmediate(Expr, SE); 2293 2294 // Basic uses can't accept any offset, for example. 2295 if (!isAlwaysFoldable(TTI, Kind, AccessTy, /*BaseGV=*/ nullptr, 2296 Offset, /*HasBaseReg=*/ true)) { 2297 Expr = Copy; 2298 Offset = 0; 2299 } 2300 2301 std::pair<UseMapTy::iterator, bool> P = 2302 UseMap.insert(std::make_pair(LSRUse::SCEVUseKindPair(Expr, Kind), 0)); 2303 if (!P.second) { 2304 // A use already existed with this base. 2305 size_t LUIdx = P.first->second; 2306 LSRUse &LU = Uses[LUIdx]; 2307 if (reconcileNewOffset(LU, Offset, /*HasBaseReg=*/true, Kind, AccessTy)) 2308 // Reuse this use. 2309 return std::make_pair(LUIdx, Offset); 2310 } 2311 2312 // Create a new use. 2313 size_t LUIdx = Uses.size(); 2314 P.first->second = LUIdx; 2315 Uses.push_back(LSRUse(Kind, AccessTy)); 2316 LSRUse &LU = Uses[LUIdx]; 2317 2318 // We don't need to track redundant offsets, but we don't need to go out 2319 // of our way here to avoid them. 2320 if (LU.Offsets.empty() || Offset != LU.Offsets.back()) 2321 LU.Offsets.push_back(Offset); 2322 2323 LU.MinOffset = Offset; 2324 LU.MaxOffset = Offset; 2325 return std::make_pair(LUIdx, Offset); 2326 } 2327 2328 /// DeleteUse - Delete the given use from the Uses list. 2329 void LSRInstance::DeleteUse(LSRUse &LU, size_t LUIdx) { 2330 if (&LU != &Uses.back()) 2331 std::swap(LU, Uses.back()); 2332 Uses.pop_back(); 2333 2334 // Update RegUses. 2335 RegUses.SwapAndDropUse(LUIdx, Uses.size()); 2336 } 2337 2338 /// FindUseWithFormula - Look for a use distinct from OrigLU which is has 2339 /// a formula that has the same registers as the given formula. 2340 LSRUse * 2341 LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF, 2342 const LSRUse &OrigLU) { 2343 // Search all uses for the formula. This could be more clever. 2344 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2345 LSRUse &LU = Uses[LUIdx]; 2346 // Check whether this use is close enough to OrigLU, to see whether it's 2347 // worthwhile looking through its formulae. 2348 // Ignore ICmpZero uses because they may contain formulae generated by 2349 // GenerateICmpZeroScales, in which case adding fixup offsets may 2350 // be invalid. 2351 if (&LU != &OrigLU && 2352 LU.Kind != LSRUse::ICmpZero && 2353 LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy && 2354 LU.WidestFixupType == OrigLU.WidestFixupType && 2355 LU.HasFormulaWithSameRegs(OrigF)) { 2356 // Scan through this use's formulae. 2357 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 2358 E = LU.Formulae.end(); I != E; ++I) { 2359 const Formula &F = *I; 2360 // Check to see if this formula has the same registers and symbols 2361 // as OrigF. 2362 if (F.BaseRegs == OrigF.BaseRegs && 2363 F.ScaledReg == OrigF.ScaledReg && 2364 F.BaseGV == OrigF.BaseGV && 2365 F.Scale == OrigF.Scale && 2366 F.UnfoldedOffset == OrigF.UnfoldedOffset) { 2367 if (F.BaseOffset == 0) 2368 return &LU; 2369 // This is the formula where all the registers and symbols matched; 2370 // there aren't going to be any others. Since we declined it, we 2371 // can skip the rest of the formulae and proceed to the next LSRUse. 2372 break; 2373 } 2374 } 2375 } 2376 } 2377 2378 // Nothing looked good. 2379 return nullptr; 2380 } 2381 2382 void LSRInstance::CollectInterestingTypesAndFactors() { 2383 SmallSetVector<const SCEV *, 4> Strides; 2384 2385 // Collect interesting types and strides. 2386 SmallVector<const SCEV *, 4> Worklist; 2387 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 2388 const SCEV *Expr = IU.getExpr(*UI); 2389 2390 // Collect interesting types. 2391 Types.insert(SE.getEffectiveSCEVType(Expr->getType())); 2392 2393 // Add strides for mentioned loops. 2394 Worklist.push_back(Expr); 2395 do { 2396 const SCEV *S = Worklist.pop_back_val(); 2397 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 2398 if (AR->getLoop() == L) 2399 Strides.insert(AR->getStepRecurrence(SE)); 2400 Worklist.push_back(AR->getStart()); 2401 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 2402 Worklist.append(Add->op_begin(), Add->op_end()); 2403 } 2404 } while (!Worklist.empty()); 2405 } 2406 2407 // Compute interesting factors from the set of interesting strides. 2408 for (SmallSetVector<const SCEV *, 4>::const_iterator 2409 I = Strides.begin(), E = Strides.end(); I != E; ++I) 2410 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter = 2411 std::next(I); NewStrideIter != E; ++NewStrideIter) { 2412 const SCEV *OldStride = *I; 2413 const SCEV *NewStride = *NewStrideIter; 2414 2415 if (SE.getTypeSizeInBits(OldStride->getType()) != 2416 SE.getTypeSizeInBits(NewStride->getType())) { 2417 if (SE.getTypeSizeInBits(OldStride->getType()) > 2418 SE.getTypeSizeInBits(NewStride->getType())) 2419 NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType()); 2420 else 2421 OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType()); 2422 } 2423 if (const SCEVConstant *Factor = 2424 dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride, 2425 SE, true))) { 2426 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 2427 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 2428 } else if (const SCEVConstant *Factor = 2429 dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride, 2430 NewStride, 2431 SE, true))) { 2432 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 2433 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 2434 } 2435 } 2436 2437 // If all uses use the same type, don't bother looking for truncation-based 2438 // reuse. 2439 if (Types.size() == 1) 2440 Types.clear(); 2441 2442 DEBUG(print_factors_and_types(dbgs())); 2443 } 2444 2445 /// findIVOperand - Helper for CollectChains that finds an IV operand (computed 2446 /// by an AddRec in this loop) within [OI,OE) or returns OE. If IVUsers mapped 2447 /// Instructions to IVStrideUses, we could partially skip this. 2448 static User::op_iterator 2449 findIVOperand(User::op_iterator OI, User::op_iterator OE, 2450 Loop *L, ScalarEvolution &SE) { 2451 for(; OI != OE; ++OI) { 2452 if (Instruction *Oper = dyn_cast<Instruction>(*OI)) { 2453 if (!SE.isSCEVable(Oper->getType())) 2454 continue; 2455 2456 if (const SCEVAddRecExpr *AR = 2457 dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Oper))) { 2458 if (AR->getLoop() == L) 2459 break; 2460 } 2461 } 2462 } 2463 return OI; 2464 } 2465 2466 /// getWideOperand - IVChain logic must consistenctly peek base TruncInst 2467 /// operands, so wrap it in a convenient helper. 2468 static Value *getWideOperand(Value *Oper) { 2469 if (TruncInst *Trunc = dyn_cast<TruncInst>(Oper)) 2470 return Trunc->getOperand(0); 2471 return Oper; 2472 } 2473 2474 /// isCompatibleIVType - Return true if we allow an IV chain to include both 2475 /// types. 2476 static bool isCompatibleIVType(Value *LVal, Value *RVal) { 2477 Type *LType = LVal->getType(); 2478 Type *RType = RVal->getType(); 2479 return (LType == RType) || (LType->isPointerTy() && RType->isPointerTy()); 2480 } 2481 2482 /// getExprBase - Return an approximation of this SCEV expression's "base", or 2483 /// NULL for any constant. Returning the expression itself is 2484 /// conservative. Returning a deeper subexpression is more precise and valid as 2485 /// long as it isn't less complex than another subexpression. For expressions 2486 /// involving multiple unscaled values, we need to return the pointer-type 2487 /// SCEVUnknown. This avoids forming chains across objects, such as: 2488 /// PrevOper==a[i], IVOper==b[i], IVInc==b-a. 2489 /// 2490 /// Since SCEVUnknown is the rightmost type, and pointers are the rightmost 2491 /// SCEVUnknown, we simply return the rightmost SCEV operand. 2492 static const SCEV *getExprBase(const SCEV *S) { 2493 switch (S->getSCEVType()) { 2494 default: // uncluding scUnknown. 2495 return S; 2496 case scConstant: 2497 return nullptr; 2498 case scTruncate: 2499 return getExprBase(cast<SCEVTruncateExpr>(S)->getOperand()); 2500 case scZeroExtend: 2501 return getExprBase(cast<SCEVZeroExtendExpr>(S)->getOperand()); 2502 case scSignExtend: 2503 return getExprBase(cast<SCEVSignExtendExpr>(S)->getOperand()); 2504 case scAddExpr: { 2505 // Skip over scaled operands (scMulExpr) to follow add operands as long as 2506 // there's nothing more complex. 2507 // FIXME: not sure if we want to recognize negation. 2508 const SCEVAddExpr *Add = cast<SCEVAddExpr>(S); 2509 for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(Add->op_end()), 2510 E(Add->op_begin()); I != E; ++I) { 2511 const SCEV *SubExpr = *I; 2512 if (SubExpr->getSCEVType() == scAddExpr) 2513 return getExprBase(SubExpr); 2514 2515 if (SubExpr->getSCEVType() != scMulExpr) 2516 return SubExpr; 2517 } 2518 return S; // all operands are scaled, be conservative. 2519 } 2520 case scAddRecExpr: 2521 return getExprBase(cast<SCEVAddRecExpr>(S)->getStart()); 2522 } 2523 } 2524 2525 /// Return true if the chain increment is profitable to expand into a loop 2526 /// invariant value, which may require its own register. A profitable chain 2527 /// increment will be an offset relative to the same base. We allow such offsets 2528 /// to potentially be used as chain increment as long as it's not obviously 2529 /// expensive to expand using real instructions. 2530 bool IVChain::isProfitableIncrement(const SCEV *OperExpr, 2531 const SCEV *IncExpr, 2532 ScalarEvolution &SE) { 2533 // Aggressively form chains when -stress-ivchain. 2534 if (StressIVChain) 2535 return true; 2536 2537 // Do not replace a constant offset from IV head with a nonconstant IV 2538 // increment. 2539 if (!isa<SCEVConstant>(IncExpr)) { 2540 const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Incs[0].IVOperand)); 2541 if (isa<SCEVConstant>(SE.getMinusSCEV(OperExpr, HeadExpr))) 2542 return 0; 2543 } 2544 2545 SmallPtrSet<const SCEV*, 8> Processed; 2546 return !isHighCostExpansion(IncExpr, Processed, SE); 2547 } 2548 2549 /// Return true if the number of registers needed for the chain is estimated to 2550 /// be less than the number required for the individual IV users. First prohibit 2551 /// any IV users that keep the IV live across increments (the Users set should 2552 /// be empty). Next count the number and type of increments in the chain. 2553 /// 2554 /// Chaining IVs can lead to considerable code bloat if ISEL doesn't 2555 /// effectively use postinc addressing modes. Only consider it profitable it the 2556 /// increments can be computed in fewer registers when chained. 2557 /// 2558 /// TODO: Consider IVInc free if it's already used in another chains. 2559 static bool 2560 isProfitableChain(IVChain &Chain, SmallPtrSet<Instruction*, 4> &Users, 2561 ScalarEvolution &SE, const TargetTransformInfo &TTI) { 2562 if (StressIVChain) 2563 return true; 2564 2565 if (!Chain.hasIncs()) 2566 return false; 2567 2568 if (!Users.empty()) { 2569 DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " users:\n"; 2570 for (SmallPtrSet<Instruction*, 4>::const_iterator I = Users.begin(), 2571 E = Users.end(); I != E; ++I) { 2572 dbgs() << " " << **I << "\n"; 2573 }); 2574 return false; 2575 } 2576 assert(!Chain.Incs.empty() && "empty IV chains are not allowed"); 2577 2578 // The chain itself may require a register, so intialize cost to 1. 2579 int cost = 1; 2580 2581 // A complete chain likely eliminates the need for keeping the original IV in 2582 // a register. LSR does not currently know how to form a complete chain unless 2583 // the header phi already exists. 2584 if (isa<PHINode>(Chain.tailUserInst()) 2585 && SE.getSCEV(Chain.tailUserInst()) == Chain.Incs[0].IncExpr) { 2586 --cost; 2587 } 2588 const SCEV *LastIncExpr = nullptr; 2589 unsigned NumConstIncrements = 0; 2590 unsigned NumVarIncrements = 0; 2591 unsigned NumReusedIncrements = 0; 2592 for (IVChain::const_iterator I = Chain.begin(), E = Chain.end(); 2593 I != E; ++I) { 2594 2595 if (I->IncExpr->isZero()) 2596 continue; 2597 2598 // Incrementing by zero or some constant is neutral. We assume constants can 2599 // be folded into an addressing mode or an add's immediate operand. 2600 if (isa<SCEVConstant>(I->IncExpr)) { 2601 ++NumConstIncrements; 2602 continue; 2603 } 2604 2605 if (I->IncExpr == LastIncExpr) 2606 ++NumReusedIncrements; 2607 else 2608 ++NumVarIncrements; 2609 2610 LastIncExpr = I->IncExpr; 2611 } 2612 // An IV chain with a single increment is handled by LSR's postinc 2613 // uses. However, a chain with multiple increments requires keeping the IV's 2614 // value live longer than it needs to be if chained. 2615 if (NumConstIncrements > 1) 2616 --cost; 2617 2618 // Materializing increment expressions in the preheader that didn't exist in 2619 // the original code may cost a register. For example, sign-extended array 2620 // indices can produce ridiculous increments like this: 2621 // IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64))) 2622 cost += NumVarIncrements; 2623 2624 // Reusing variable increments likely saves a register to hold the multiple of 2625 // the stride. 2626 cost -= NumReusedIncrements; 2627 2628 DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " Cost: " << cost 2629 << "\n"); 2630 2631 return cost < 0; 2632 } 2633 2634 /// ChainInstruction - Add this IV user to an existing chain or make it the head 2635 /// of a new chain. 2636 void LSRInstance::ChainInstruction(Instruction *UserInst, Instruction *IVOper, 2637 SmallVectorImpl<ChainUsers> &ChainUsersVec) { 2638 // When IVs are used as types of varying widths, they are generally converted 2639 // to a wider type with some uses remaining narrow under a (free) trunc. 2640 Value *const NextIV = getWideOperand(IVOper); 2641 const SCEV *const OperExpr = SE.getSCEV(NextIV); 2642 const SCEV *const OperExprBase = getExprBase(OperExpr); 2643 2644 // Visit all existing chains. Check if its IVOper can be computed as a 2645 // profitable loop invariant increment from the last link in the Chain. 2646 unsigned ChainIdx = 0, NChains = IVChainVec.size(); 2647 const SCEV *LastIncExpr = nullptr; 2648 for (; ChainIdx < NChains; ++ChainIdx) { 2649 IVChain &Chain = IVChainVec[ChainIdx]; 2650 2651 // Prune the solution space aggressively by checking that both IV operands 2652 // are expressions that operate on the same unscaled SCEVUnknown. This 2653 // "base" will be canceled by the subsequent getMinusSCEV call. Checking 2654 // first avoids creating extra SCEV expressions. 2655 if (!StressIVChain && Chain.ExprBase != OperExprBase) 2656 continue; 2657 2658 Value *PrevIV = getWideOperand(Chain.Incs.back().IVOperand); 2659 if (!isCompatibleIVType(PrevIV, NextIV)) 2660 continue; 2661 2662 // A phi node terminates a chain. 2663 if (isa<PHINode>(UserInst) && isa<PHINode>(Chain.tailUserInst())) 2664 continue; 2665 2666 // The increment must be loop-invariant so it can be kept in a register. 2667 const SCEV *PrevExpr = SE.getSCEV(PrevIV); 2668 const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr); 2669 if (!SE.isLoopInvariant(IncExpr, L)) 2670 continue; 2671 2672 if (Chain.isProfitableIncrement(OperExpr, IncExpr, SE)) { 2673 LastIncExpr = IncExpr; 2674 break; 2675 } 2676 } 2677 // If we haven't found a chain, create a new one, unless we hit the max. Don't 2678 // bother for phi nodes, because they must be last in the chain. 2679 if (ChainIdx == NChains) { 2680 if (isa<PHINode>(UserInst)) 2681 return; 2682 if (NChains >= MaxChains && !StressIVChain) { 2683 DEBUG(dbgs() << "IV Chain Limit\n"); 2684 return; 2685 } 2686 LastIncExpr = OperExpr; 2687 // IVUsers may have skipped over sign/zero extensions. We don't currently 2688 // attempt to form chains involving extensions unless they can be hoisted 2689 // into this loop's AddRec. 2690 if (!isa<SCEVAddRecExpr>(LastIncExpr)) 2691 return; 2692 ++NChains; 2693 IVChainVec.push_back(IVChain(IVInc(UserInst, IVOper, LastIncExpr), 2694 OperExprBase)); 2695 ChainUsersVec.resize(NChains); 2696 DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Head: (" << *UserInst 2697 << ") IV=" << *LastIncExpr << "\n"); 2698 } else { 2699 DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Inc: (" << *UserInst 2700 << ") IV+" << *LastIncExpr << "\n"); 2701 // Add this IV user to the end of the chain. 2702 IVChainVec[ChainIdx].add(IVInc(UserInst, IVOper, LastIncExpr)); 2703 } 2704 IVChain &Chain = IVChainVec[ChainIdx]; 2705 2706 SmallPtrSet<Instruction*,4> &NearUsers = ChainUsersVec[ChainIdx].NearUsers; 2707 // This chain's NearUsers become FarUsers. 2708 if (!LastIncExpr->isZero()) { 2709 ChainUsersVec[ChainIdx].FarUsers.insert(NearUsers.begin(), 2710 NearUsers.end()); 2711 NearUsers.clear(); 2712 } 2713 2714 // All other uses of IVOperand become near uses of the chain. 2715 // We currently ignore intermediate values within SCEV expressions, assuming 2716 // they will eventually be used be the current chain, or can be computed 2717 // from one of the chain increments. To be more precise we could 2718 // transitively follow its user and only add leaf IV users to the set. 2719 for (User *U : IVOper->users()) { 2720 Instruction *OtherUse = dyn_cast<Instruction>(U); 2721 if (!OtherUse) 2722 continue; 2723 // Uses in the chain will no longer be uses if the chain is formed. 2724 // Include the head of the chain in this iteration (not Chain.begin()). 2725 IVChain::const_iterator IncIter = Chain.Incs.begin(); 2726 IVChain::const_iterator IncEnd = Chain.Incs.end(); 2727 for( ; IncIter != IncEnd; ++IncIter) { 2728 if (IncIter->UserInst == OtherUse) 2729 break; 2730 } 2731 if (IncIter != IncEnd) 2732 continue; 2733 2734 if (SE.isSCEVable(OtherUse->getType()) 2735 && !isa<SCEVUnknown>(SE.getSCEV(OtherUse)) 2736 && IU.isIVUserOrOperand(OtherUse)) { 2737 continue; 2738 } 2739 NearUsers.insert(OtherUse); 2740 } 2741 2742 // Since this user is part of the chain, it's no longer considered a use 2743 // of the chain. 2744 ChainUsersVec[ChainIdx].FarUsers.erase(UserInst); 2745 } 2746 2747 /// CollectChains - Populate the vector of Chains. 2748 /// 2749 /// This decreases ILP at the architecture level. Targets with ample registers, 2750 /// multiple memory ports, and no register renaming probably don't want 2751 /// this. However, such targets should probably disable LSR altogether. 2752 /// 2753 /// The job of LSR is to make a reasonable choice of induction variables across 2754 /// the loop. Subsequent passes can easily "unchain" computation exposing more 2755 /// ILP *within the loop* if the target wants it. 2756 /// 2757 /// Finding the best IV chain is potentially a scheduling problem. Since LSR 2758 /// will not reorder memory operations, it will recognize this as a chain, but 2759 /// will generate redundant IV increments. Ideally this would be corrected later 2760 /// by a smart scheduler: 2761 /// = A[i] 2762 /// = A[i+x] 2763 /// A[i] = 2764 /// A[i+x] = 2765 /// 2766 /// TODO: Walk the entire domtree within this loop, not just the path to the 2767 /// loop latch. This will discover chains on side paths, but requires 2768 /// maintaining multiple copies of the Chains state. 2769 void LSRInstance::CollectChains() { 2770 DEBUG(dbgs() << "Collecting IV Chains.\n"); 2771 SmallVector<ChainUsers, 8> ChainUsersVec; 2772 2773 SmallVector<BasicBlock *,8> LatchPath; 2774 BasicBlock *LoopHeader = L->getHeader(); 2775 for (DomTreeNode *Rung = DT.getNode(L->getLoopLatch()); 2776 Rung->getBlock() != LoopHeader; Rung = Rung->getIDom()) { 2777 LatchPath.push_back(Rung->getBlock()); 2778 } 2779 LatchPath.push_back(LoopHeader); 2780 2781 // Walk the instruction stream from the loop header to the loop latch. 2782 for (SmallVectorImpl<BasicBlock *>::reverse_iterator 2783 BBIter = LatchPath.rbegin(), BBEnd = LatchPath.rend(); 2784 BBIter != BBEnd; ++BBIter) { 2785 for (BasicBlock::iterator I = (*BBIter)->begin(), E = (*BBIter)->end(); 2786 I != E; ++I) { 2787 // Skip instructions that weren't seen by IVUsers analysis. 2788 if (isa<PHINode>(I) || !IU.isIVUserOrOperand(I)) 2789 continue; 2790 2791 // Ignore users that are part of a SCEV expression. This way we only 2792 // consider leaf IV Users. This effectively rediscovers a portion of 2793 // IVUsers analysis but in program order this time. 2794 if (SE.isSCEVable(I->getType()) && !isa<SCEVUnknown>(SE.getSCEV(I))) 2795 continue; 2796 2797 // Remove this instruction from any NearUsers set it may be in. 2798 for (unsigned ChainIdx = 0, NChains = IVChainVec.size(); 2799 ChainIdx < NChains; ++ChainIdx) { 2800 ChainUsersVec[ChainIdx].NearUsers.erase(I); 2801 } 2802 // Search for operands that can be chained. 2803 SmallPtrSet<Instruction*, 4> UniqueOperands; 2804 User::op_iterator IVOpEnd = I->op_end(); 2805 User::op_iterator IVOpIter = findIVOperand(I->op_begin(), IVOpEnd, L, SE); 2806 while (IVOpIter != IVOpEnd) { 2807 Instruction *IVOpInst = cast<Instruction>(*IVOpIter); 2808 if (UniqueOperands.insert(IVOpInst)) 2809 ChainInstruction(I, IVOpInst, ChainUsersVec); 2810 IVOpIter = findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE); 2811 } 2812 } // Continue walking down the instructions. 2813 } // Continue walking down the domtree. 2814 // Visit phi backedges to determine if the chain can generate the IV postinc. 2815 for (BasicBlock::iterator I = L->getHeader()->begin(); 2816 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 2817 if (!SE.isSCEVable(PN->getType())) 2818 continue; 2819 2820 Instruction *IncV = 2821 dyn_cast<Instruction>(PN->getIncomingValueForBlock(L->getLoopLatch())); 2822 if (IncV) 2823 ChainInstruction(PN, IncV, ChainUsersVec); 2824 } 2825 // Remove any unprofitable chains. 2826 unsigned ChainIdx = 0; 2827 for (unsigned UsersIdx = 0, NChains = IVChainVec.size(); 2828 UsersIdx < NChains; ++UsersIdx) { 2829 if (!isProfitableChain(IVChainVec[UsersIdx], 2830 ChainUsersVec[UsersIdx].FarUsers, SE, TTI)) 2831 continue; 2832 // Preserve the chain at UsesIdx. 2833 if (ChainIdx != UsersIdx) 2834 IVChainVec[ChainIdx] = IVChainVec[UsersIdx]; 2835 FinalizeChain(IVChainVec[ChainIdx]); 2836 ++ChainIdx; 2837 } 2838 IVChainVec.resize(ChainIdx); 2839 } 2840 2841 void LSRInstance::FinalizeChain(IVChain &Chain) { 2842 assert(!Chain.Incs.empty() && "empty IV chains are not allowed"); 2843 DEBUG(dbgs() << "Final Chain: " << *Chain.Incs[0].UserInst << "\n"); 2844 2845 for (IVChain::const_iterator I = Chain.begin(), E = Chain.end(); 2846 I != E; ++I) { 2847 DEBUG(dbgs() << " Inc: " << *I->UserInst << "\n"); 2848 User::op_iterator UseI = 2849 std::find(I->UserInst->op_begin(), I->UserInst->op_end(), I->IVOperand); 2850 assert(UseI != I->UserInst->op_end() && "cannot find IV operand"); 2851 IVIncSet.insert(UseI); 2852 } 2853 } 2854 2855 /// Return true if the IVInc can be folded into an addressing mode. 2856 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst, 2857 Value *Operand, const TargetTransformInfo &TTI) { 2858 const SCEVConstant *IncConst = dyn_cast<SCEVConstant>(IncExpr); 2859 if (!IncConst || !isAddressUse(UserInst, Operand)) 2860 return false; 2861 2862 if (IncConst->getValue()->getValue().getMinSignedBits() > 64) 2863 return false; 2864 2865 int64_t IncOffset = IncConst->getValue()->getSExtValue(); 2866 if (!isAlwaysFoldable(TTI, LSRUse::Address, 2867 getAccessType(UserInst), /*BaseGV=*/ nullptr, 2868 IncOffset, /*HaseBaseReg=*/ false)) 2869 return false; 2870 2871 return true; 2872 } 2873 2874 /// GenerateIVChains - Generate an add or subtract for each IVInc in a chain to 2875 /// materialize the IV user's operand from the previous IV user's operand. 2876 void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter, 2877 SmallVectorImpl<WeakVH> &DeadInsts) { 2878 // Find the new IVOperand for the head of the chain. It may have been replaced 2879 // by LSR. 2880 const IVInc &Head = Chain.Incs[0]; 2881 User::op_iterator IVOpEnd = Head.UserInst->op_end(); 2882 // findIVOperand returns IVOpEnd if it can no longer find a valid IV user. 2883 User::op_iterator IVOpIter = findIVOperand(Head.UserInst->op_begin(), 2884 IVOpEnd, L, SE); 2885 Value *IVSrc = nullptr; 2886 while (IVOpIter != IVOpEnd) { 2887 IVSrc = getWideOperand(*IVOpIter); 2888 2889 // If this operand computes the expression that the chain needs, we may use 2890 // it. (Check this after setting IVSrc which is used below.) 2891 // 2892 // Note that if Head.IncExpr is wider than IVSrc, then this phi is too 2893 // narrow for the chain, so we can no longer use it. We do allow using a 2894 // wider phi, assuming the LSR checked for free truncation. In that case we 2895 // should already have a truncate on this operand such that 2896 // getSCEV(IVSrc) == IncExpr. 2897 if (SE.getSCEV(*IVOpIter) == Head.IncExpr 2898 || SE.getSCEV(IVSrc) == Head.IncExpr) { 2899 break; 2900 } 2901 IVOpIter = findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE); 2902 } 2903 if (IVOpIter == IVOpEnd) { 2904 // Gracefully give up on this chain. 2905 DEBUG(dbgs() << "Concealed chain head: " << *Head.UserInst << "\n"); 2906 return; 2907 } 2908 2909 DEBUG(dbgs() << "Generate chain at: " << *IVSrc << "\n"); 2910 Type *IVTy = IVSrc->getType(); 2911 Type *IntTy = SE.getEffectiveSCEVType(IVTy); 2912 const SCEV *LeftOverExpr = nullptr; 2913 for (IVChain::const_iterator IncI = Chain.begin(), 2914 IncE = Chain.end(); IncI != IncE; ++IncI) { 2915 2916 Instruction *InsertPt = IncI->UserInst; 2917 if (isa<PHINode>(InsertPt)) 2918 InsertPt = L->getLoopLatch()->getTerminator(); 2919 2920 // IVOper will replace the current IV User's operand. IVSrc is the IV 2921 // value currently held in a register. 2922 Value *IVOper = IVSrc; 2923 if (!IncI->IncExpr->isZero()) { 2924 // IncExpr was the result of subtraction of two narrow values, so must 2925 // be signed. 2926 const SCEV *IncExpr = SE.getNoopOrSignExtend(IncI->IncExpr, IntTy); 2927 LeftOverExpr = LeftOverExpr ? 2928 SE.getAddExpr(LeftOverExpr, IncExpr) : IncExpr; 2929 } 2930 if (LeftOverExpr && !LeftOverExpr->isZero()) { 2931 // Expand the IV increment. 2932 Rewriter.clearPostInc(); 2933 Value *IncV = Rewriter.expandCodeFor(LeftOverExpr, IntTy, InsertPt); 2934 const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc), 2935 SE.getUnknown(IncV)); 2936 IVOper = Rewriter.expandCodeFor(IVOperExpr, IVTy, InsertPt); 2937 2938 // If an IV increment can't be folded, use it as the next IV value. 2939 if (!canFoldIVIncExpr(LeftOverExpr, IncI->UserInst, IncI->IVOperand, 2940 TTI)) { 2941 assert(IVTy == IVOper->getType() && "inconsistent IV increment type"); 2942 IVSrc = IVOper; 2943 LeftOverExpr = nullptr; 2944 } 2945 } 2946 Type *OperTy = IncI->IVOperand->getType(); 2947 if (IVTy != OperTy) { 2948 assert(SE.getTypeSizeInBits(IVTy) >= SE.getTypeSizeInBits(OperTy) && 2949 "cannot extend a chained IV"); 2950 IRBuilder<> Builder(InsertPt); 2951 IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy, "lsr.chain"); 2952 } 2953 IncI->UserInst->replaceUsesOfWith(IncI->IVOperand, IVOper); 2954 DeadInsts.push_back(IncI->IVOperand); 2955 } 2956 // If LSR created a new, wider phi, we may also replace its postinc. We only 2957 // do this if we also found a wide value for the head of the chain. 2958 if (isa<PHINode>(Chain.tailUserInst())) { 2959 for (BasicBlock::iterator I = L->getHeader()->begin(); 2960 PHINode *Phi = dyn_cast<PHINode>(I); ++I) { 2961 if (!isCompatibleIVType(Phi, IVSrc)) 2962 continue; 2963 Instruction *PostIncV = dyn_cast<Instruction>( 2964 Phi->getIncomingValueForBlock(L->getLoopLatch())); 2965 if (!PostIncV || (SE.getSCEV(PostIncV) != SE.getSCEV(IVSrc))) 2966 continue; 2967 Value *IVOper = IVSrc; 2968 Type *PostIncTy = PostIncV->getType(); 2969 if (IVTy != PostIncTy) { 2970 assert(PostIncTy->isPointerTy() && "mixing int/ptr IV types"); 2971 IRBuilder<> Builder(L->getLoopLatch()->getTerminator()); 2972 Builder.SetCurrentDebugLocation(PostIncV->getDebugLoc()); 2973 IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy, "lsr.chain"); 2974 } 2975 Phi->replaceUsesOfWith(PostIncV, IVOper); 2976 DeadInsts.push_back(PostIncV); 2977 } 2978 } 2979 } 2980 2981 void LSRInstance::CollectFixupsAndInitialFormulae() { 2982 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 2983 Instruction *UserInst = UI->getUser(); 2984 // Skip IV users that are part of profitable IV Chains. 2985 User::op_iterator UseI = std::find(UserInst->op_begin(), UserInst->op_end(), 2986 UI->getOperandValToReplace()); 2987 assert(UseI != UserInst->op_end() && "cannot find IV operand"); 2988 if (IVIncSet.count(UseI)) 2989 continue; 2990 2991 // Record the uses. 2992 LSRFixup &LF = getNewFixup(); 2993 LF.UserInst = UserInst; 2994 LF.OperandValToReplace = UI->getOperandValToReplace(); 2995 LF.PostIncLoops = UI->getPostIncLoops(); 2996 2997 LSRUse::KindType Kind = LSRUse::Basic; 2998 Type *AccessTy = nullptr; 2999 if (isAddressUse(LF.UserInst, LF.OperandValToReplace)) { 3000 Kind = LSRUse::Address; 3001 AccessTy = getAccessType(LF.UserInst); 3002 } 3003 3004 const SCEV *S = IU.getExpr(*UI); 3005 3006 // Equality (== and !=) ICmps are special. We can rewrite (i == N) as 3007 // (N - i == 0), and this allows (N - i) to be the expression that we work 3008 // with rather than just N or i, so we can consider the register 3009 // requirements for both N and i at the same time. Limiting this code to 3010 // equality icmps is not a problem because all interesting loops use 3011 // equality icmps, thanks to IndVarSimplify. 3012 if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst)) 3013 if (CI->isEquality()) { 3014 // Swap the operands if needed to put the OperandValToReplace on the 3015 // left, for consistency. 3016 Value *NV = CI->getOperand(1); 3017 if (NV == LF.OperandValToReplace) { 3018 CI->setOperand(1, CI->getOperand(0)); 3019 CI->setOperand(0, NV); 3020 NV = CI->getOperand(1); 3021 Changed = true; 3022 } 3023 3024 // x == y --> x - y == 0 3025 const SCEV *N = SE.getSCEV(NV); 3026 if (SE.isLoopInvariant(N, L) && isSafeToExpand(N, SE)) { 3027 // S is normalized, so normalize N before folding it into S 3028 // to keep the result normalized. 3029 N = TransformForPostIncUse(Normalize, N, CI, nullptr, 3030 LF.PostIncLoops, SE, DT); 3031 Kind = LSRUse::ICmpZero; 3032 S = SE.getMinusSCEV(N, S); 3033 } 3034 3035 // -1 and the negations of all interesting strides (except the negation 3036 // of -1) are now also interesting. 3037 for (size_t i = 0, e = Factors.size(); i != e; ++i) 3038 if (Factors[i] != -1) 3039 Factors.insert(-(uint64_t)Factors[i]); 3040 Factors.insert(-1); 3041 } 3042 3043 // Set up the initial formula for this use. 3044 std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy); 3045 LF.LUIdx = P.first; 3046 LF.Offset = P.second; 3047 LSRUse &LU = Uses[LF.LUIdx]; 3048 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 3049 if (!LU.WidestFixupType || 3050 SE.getTypeSizeInBits(LU.WidestFixupType) < 3051 SE.getTypeSizeInBits(LF.OperandValToReplace->getType())) 3052 LU.WidestFixupType = LF.OperandValToReplace->getType(); 3053 3054 // If this is the first use of this LSRUse, give it a formula. 3055 if (LU.Formulae.empty()) { 3056 InsertInitialFormula(S, LU, LF.LUIdx); 3057 CountRegisters(LU.Formulae.back(), LF.LUIdx); 3058 } 3059 } 3060 3061 DEBUG(print_fixups(dbgs())); 3062 } 3063 3064 /// InsertInitialFormula - Insert a formula for the given expression into 3065 /// the given use, separating out loop-variant portions from loop-invariant 3066 /// and loop-computable portions. 3067 void 3068 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) { 3069 // Mark uses whose expressions cannot be expanded. 3070 if (!isSafeToExpand(S, SE)) 3071 LU.RigidFormula = true; 3072 3073 Formula F; 3074 F.InitialMatch(S, L, SE); 3075 bool Inserted = InsertFormula(LU, LUIdx, F); 3076 assert(Inserted && "Initial formula already exists!"); (void)Inserted; 3077 } 3078 3079 /// InsertSupplementalFormula - Insert a simple single-register formula for 3080 /// the given expression into the given use. 3081 void 3082 LSRInstance::InsertSupplementalFormula(const SCEV *S, 3083 LSRUse &LU, size_t LUIdx) { 3084 Formula F; 3085 F.BaseRegs.push_back(S); 3086 F.HasBaseReg = true; 3087 bool Inserted = InsertFormula(LU, LUIdx, F); 3088 assert(Inserted && "Supplemental formula already exists!"); (void)Inserted; 3089 } 3090 3091 /// CountRegisters - Note which registers are used by the given formula, 3092 /// updating RegUses. 3093 void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) { 3094 if (F.ScaledReg) 3095 RegUses.CountRegister(F.ScaledReg, LUIdx); 3096 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 3097 E = F.BaseRegs.end(); I != E; ++I) 3098 RegUses.CountRegister(*I, LUIdx); 3099 } 3100 3101 /// InsertFormula - If the given formula has not yet been inserted, add it to 3102 /// the list, and return true. Return false otherwise. 3103 bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) { 3104 // Do not insert formula that we will not be able to expand. 3105 assert(isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F) && 3106 "Formula is illegal"); 3107 if (!LU.InsertFormula(F)) 3108 return false; 3109 3110 CountRegisters(F, LUIdx); 3111 return true; 3112 } 3113 3114 /// CollectLoopInvariantFixupsAndFormulae - Check for other uses of 3115 /// loop-invariant values which we're tracking. These other uses will pin these 3116 /// values in registers, making them less profitable for elimination. 3117 /// TODO: This currently misses non-constant addrec step registers. 3118 /// TODO: Should this give more weight to users inside the loop? 3119 void 3120 LSRInstance::CollectLoopInvariantFixupsAndFormulae() { 3121 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end()); 3122 SmallPtrSet<const SCEV *, 8> Inserted; 3123 3124 while (!Worklist.empty()) { 3125 const SCEV *S = Worklist.pop_back_val(); 3126 3127 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) 3128 Worklist.append(N->op_begin(), N->op_end()); 3129 else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 3130 Worklist.push_back(C->getOperand()); 3131 else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 3132 Worklist.push_back(D->getLHS()); 3133 Worklist.push_back(D->getRHS()); 3134 } else if (const SCEVUnknown *US = dyn_cast<SCEVUnknown>(S)) { 3135 if (!Inserted.insert(US)) continue; 3136 const Value *V = US->getValue(); 3137 if (const Instruction *Inst = dyn_cast<Instruction>(V)) { 3138 // Look for instructions defined outside the loop. 3139 if (L->contains(Inst)) continue; 3140 } else if (isa<UndefValue>(V)) 3141 // Undef doesn't have a live range, so it doesn't matter. 3142 continue; 3143 for (const Use &U : V->uses()) { 3144 const Instruction *UserInst = dyn_cast<Instruction>(U.getUser()); 3145 // Ignore non-instructions. 3146 if (!UserInst) 3147 continue; 3148 // Ignore instructions in other functions (as can happen with 3149 // Constants). 3150 if (UserInst->getParent()->getParent() != L->getHeader()->getParent()) 3151 continue; 3152 // Ignore instructions not dominated by the loop. 3153 const BasicBlock *UseBB = !isa<PHINode>(UserInst) ? 3154 UserInst->getParent() : 3155 cast<PHINode>(UserInst)->getIncomingBlock( 3156 PHINode::getIncomingValueNumForOperand(U.getOperandNo())); 3157 if (!DT.dominates(L->getHeader(), UseBB)) 3158 continue; 3159 // Ignore uses which are part of other SCEV expressions, to avoid 3160 // analyzing them multiple times. 3161 if (SE.isSCEVable(UserInst->getType())) { 3162 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst)); 3163 // If the user is a no-op, look through to its uses. 3164 if (!isa<SCEVUnknown>(UserS)) 3165 continue; 3166 if (UserS == US) { 3167 Worklist.push_back( 3168 SE.getUnknown(const_cast<Instruction *>(UserInst))); 3169 continue; 3170 } 3171 } 3172 // Ignore icmp instructions which are already being analyzed. 3173 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UserInst)) { 3174 unsigned OtherIdx = !U.getOperandNo(); 3175 Value *OtherOp = const_cast<Value *>(ICI->getOperand(OtherIdx)); 3176 if (SE.hasComputableLoopEvolution(SE.getSCEV(OtherOp), L)) 3177 continue; 3178 } 3179 3180 LSRFixup &LF = getNewFixup(); 3181 LF.UserInst = const_cast<Instruction *>(UserInst); 3182 LF.OperandValToReplace = U; 3183 std::pair<size_t, int64_t> P = getUse(S, LSRUse::Basic, nullptr); 3184 LF.LUIdx = P.first; 3185 LF.Offset = P.second; 3186 LSRUse &LU = Uses[LF.LUIdx]; 3187 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 3188 if (!LU.WidestFixupType || 3189 SE.getTypeSizeInBits(LU.WidestFixupType) < 3190 SE.getTypeSizeInBits(LF.OperandValToReplace->getType())) 3191 LU.WidestFixupType = LF.OperandValToReplace->getType(); 3192 InsertSupplementalFormula(US, LU, LF.LUIdx); 3193 CountRegisters(LU.Formulae.back(), Uses.size() - 1); 3194 break; 3195 } 3196 } 3197 } 3198 } 3199 3200 /// CollectSubexprs - Split S into subexpressions which can be pulled out into 3201 /// separate registers. If C is non-null, multiply each subexpression by C. 3202 /// 3203 /// Return remainder expression after factoring the subexpressions captured by 3204 /// Ops. If Ops is complete, return NULL. 3205 static const SCEV *CollectSubexprs(const SCEV *S, const SCEVConstant *C, 3206 SmallVectorImpl<const SCEV *> &Ops, 3207 const Loop *L, 3208 ScalarEvolution &SE, 3209 unsigned Depth = 0) { 3210 // Arbitrarily cap recursion to protect compile time. 3211 if (Depth >= 3) 3212 return S; 3213 3214 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 3215 // Break out add operands. 3216 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 3217 I != E; ++I) { 3218 const SCEV *Remainder = CollectSubexprs(*I, C, Ops, L, SE, Depth+1); 3219 if (Remainder) 3220 Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder); 3221 } 3222 return nullptr; 3223 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 3224 // Split a non-zero base out of an addrec. 3225 if (AR->getStart()->isZero()) 3226 return S; 3227 3228 const SCEV *Remainder = CollectSubexprs(AR->getStart(), 3229 C, Ops, L, SE, Depth+1); 3230 // Split the non-zero AddRec unless it is part of a nested recurrence that 3231 // does not pertain to this loop. 3232 if (Remainder && (AR->getLoop() == L || !isa<SCEVAddRecExpr>(Remainder))) { 3233 Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder); 3234 Remainder = nullptr; 3235 } 3236 if (Remainder != AR->getStart()) { 3237 if (!Remainder) 3238 Remainder = SE.getConstant(AR->getType(), 0); 3239 return SE.getAddRecExpr(Remainder, 3240 AR->getStepRecurrence(SE), 3241 AR->getLoop(), 3242 //FIXME: AR->getNoWrapFlags(SCEV::FlagNW) 3243 SCEV::FlagAnyWrap); 3244 } 3245 } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 3246 // Break (C * (a + b + c)) into C*a + C*b + C*c. 3247 if (Mul->getNumOperands() != 2) 3248 return S; 3249 if (const SCEVConstant *Op0 = 3250 dyn_cast<SCEVConstant>(Mul->getOperand(0))) { 3251 C = C ? cast<SCEVConstant>(SE.getMulExpr(C, Op0)) : Op0; 3252 const SCEV *Remainder = 3253 CollectSubexprs(Mul->getOperand(1), C, Ops, L, SE, Depth+1); 3254 if (Remainder) 3255 Ops.push_back(SE.getMulExpr(C, Remainder)); 3256 return nullptr; 3257 } 3258 } 3259 return S; 3260 } 3261 3262 /// \brief Helper function for LSRInstance::GenerateReassociations. 3263 void LSRInstance::GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx, 3264 const Formula &Base, 3265 unsigned Depth, size_t Idx, 3266 bool IsScaledReg) { 3267 const SCEV *BaseReg = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx]; 3268 SmallVector<const SCEV *, 8> AddOps; 3269 const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE); 3270 if (Remainder) 3271 AddOps.push_back(Remainder); 3272 3273 if (AddOps.size() == 1) 3274 return; 3275 3276 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(), 3277 JE = AddOps.end(); 3278 J != JE; ++J) { 3279 3280 // Loop-variant "unknown" values are uninteresting; we won't be able to 3281 // do anything meaningful with them. 3282 if (isa<SCEVUnknown>(*J) && !SE.isLoopInvariant(*J, L)) 3283 continue; 3284 3285 // Don't pull a constant into a register if the constant could be folded 3286 // into an immediate field. 3287 if (isAlwaysFoldable(TTI, SE, LU.MinOffset, LU.MaxOffset, LU.Kind, 3288 LU.AccessTy, *J, Base.getNumRegs() > 1)) 3289 continue; 3290 3291 // Collect all operands except *J. 3292 SmallVector<const SCEV *, 8> InnerAddOps( 3293 ((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J); 3294 InnerAddOps.append(std::next(J), 3295