LoopStrengthReduce.cpp revision 208599
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 TargetLowering::AddrMode::BaseGV be changed to a ConstantExpr 41// instead 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#define DEBUG_TYPE "loop-reduce" 57#include "llvm/Transforms/Scalar.h" 58#include "llvm/Constants.h" 59#include "llvm/Instructions.h" 60#include "llvm/IntrinsicInst.h" 61#include "llvm/DerivedTypes.h" 62#include "llvm/Analysis/IVUsers.h" 63#include "llvm/Analysis/Dominators.h" 64#include "llvm/Analysis/LoopPass.h" 65#include "llvm/Analysis/ScalarEvolutionExpander.h" 66#include "llvm/Transforms/Utils/BasicBlockUtils.h" 67#include "llvm/Transforms/Utils/Local.h" 68#include "llvm/ADT/SmallBitVector.h" 69#include "llvm/ADT/SetVector.h" 70#include "llvm/ADT/DenseSet.h" 71#include "llvm/Support/Debug.h" 72#include "llvm/Support/ValueHandle.h" 73#include "llvm/Support/raw_ostream.h" 74#include "llvm/Target/TargetLowering.h" 75#include <algorithm> 76using namespace llvm; 77 78namespace { 79 80/// RegSortData - This class holds data which is used to order reuse candidates. 81class RegSortData { 82public: 83 /// UsedByIndices - This represents the set of LSRUse indices which reference 84 /// a particular register. 85 SmallBitVector UsedByIndices; 86 87 RegSortData() {} 88 89 void print(raw_ostream &OS) const; 90 void dump() const; 91}; 92 93} 94 95void RegSortData::print(raw_ostream &OS) const { 96 OS << "[NumUses=" << UsedByIndices.count() << ']'; 97} 98 99void RegSortData::dump() const { 100 print(errs()); errs() << '\n'; 101} 102 103namespace { 104 105/// RegUseTracker - Map register candidates to information about how they are 106/// used. 107class RegUseTracker { 108 typedef DenseMap<const SCEV *, RegSortData> RegUsesTy; 109 110 RegUsesTy RegUsesMap; 111 SmallVector<const SCEV *, 16> RegSequence; 112 113public: 114 void CountRegister(const SCEV *Reg, size_t LUIdx); 115 void DropRegister(const SCEV *Reg, size_t LUIdx); 116 void DropUse(size_t LUIdx); 117 118 bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const; 119 120 const SmallBitVector &getUsedByIndices(const SCEV *Reg) const; 121 122 void clear(); 123 124 typedef SmallVectorImpl<const SCEV *>::iterator iterator; 125 typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator; 126 iterator begin() { return RegSequence.begin(); } 127 iterator end() { return RegSequence.end(); } 128 const_iterator begin() const { return RegSequence.begin(); } 129 const_iterator end() const { return RegSequence.end(); } 130}; 131 132} 133 134void 135RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) { 136 std::pair<RegUsesTy::iterator, bool> Pair = 137 RegUsesMap.insert(std::make_pair(Reg, RegSortData())); 138 RegSortData &RSD = Pair.first->second; 139 if (Pair.second) 140 RegSequence.push_back(Reg); 141 RSD.UsedByIndices.resize(std::max(RSD.UsedByIndices.size(), LUIdx + 1)); 142 RSD.UsedByIndices.set(LUIdx); 143} 144 145void 146RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) { 147 RegUsesTy::iterator It = RegUsesMap.find(Reg); 148 assert(It != RegUsesMap.end()); 149 RegSortData &RSD = It->second; 150 assert(RSD.UsedByIndices.size() > LUIdx); 151 RSD.UsedByIndices.reset(LUIdx); 152} 153 154void 155RegUseTracker::DropUse(size_t LUIdx) { 156 // Remove the use index from every register's use list. 157 for (RegUsesTy::iterator I = RegUsesMap.begin(), E = RegUsesMap.end(); 158 I != E; ++I) 159 I->second.UsedByIndices.reset(LUIdx); 160} 161 162bool 163RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const { 164 if (!RegUsesMap.count(Reg)) return false; 165 const SmallBitVector &UsedByIndices = 166 RegUsesMap.find(Reg)->second.UsedByIndices; 167 int i = UsedByIndices.find_first(); 168 if (i == -1) return false; 169 if ((size_t)i != LUIdx) return true; 170 return UsedByIndices.find_next(i) != -1; 171} 172 173const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const { 174 RegUsesTy::const_iterator I = RegUsesMap.find(Reg); 175 assert(I != RegUsesMap.end() && "Unknown register!"); 176 return I->second.UsedByIndices; 177} 178 179void RegUseTracker::clear() { 180 RegUsesMap.clear(); 181 RegSequence.clear(); 182} 183 184namespace { 185 186/// Formula - This class holds information that describes a formula for 187/// computing satisfying a use. It may include broken-out immediates and scaled 188/// registers. 189struct Formula { 190 /// AM - This is used to represent complex addressing, as well as other kinds 191 /// of interesting uses. 192 TargetLowering::AddrMode AM; 193 194 /// BaseRegs - The list of "base" registers for this use. When this is 195 /// non-empty, AM.HasBaseReg should be set to true. 196 SmallVector<const SCEV *, 2> BaseRegs; 197 198 /// ScaledReg - The 'scaled' register for this use. This should be non-null 199 /// when AM.Scale is not zero. 200 const SCEV *ScaledReg; 201 202 Formula() : ScaledReg(0) {} 203 204 void InitialMatch(const SCEV *S, Loop *L, 205 ScalarEvolution &SE, DominatorTree &DT); 206 207 unsigned getNumRegs() const; 208 const Type *getType() const; 209 210 void DeleteBaseReg(const SCEV *&S); 211 212 bool referencesReg(const SCEV *S) const; 213 bool hasRegsUsedByUsesOtherThan(size_t LUIdx, 214 const RegUseTracker &RegUses) const; 215 216 void print(raw_ostream &OS) const; 217 void dump() const; 218}; 219 220} 221 222/// DoInitialMatch - Recursion helper for InitialMatch. 223static void DoInitialMatch(const SCEV *S, Loop *L, 224 SmallVectorImpl<const SCEV *> &Good, 225 SmallVectorImpl<const SCEV *> &Bad, 226 ScalarEvolution &SE, DominatorTree &DT) { 227 // Collect expressions which properly dominate the loop header. 228 if (S->properlyDominates(L->getHeader(), &DT)) { 229 Good.push_back(S); 230 return; 231 } 232 233 // Look at add operands. 234 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 235 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 236 I != E; ++I) 237 DoInitialMatch(*I, L, Good, Bad, SE, DT); 238 return; 239 } 240 241 // Look at addrec operands. 242 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) 243 if (!AR->getStart()->isZero()) { 244 DoInitialMatch(AR->getStart(), L, Good, Bad, SE, DT); 245 DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0), 246 AR->getStepRecurrence(SE), 247 AR->getLoop()), 248 L, Good, Bad, SE, DT); 249 return; 250 } 251 252 // Handle a multiplication by -1 (negation) if it didn't fold. 253 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) 254 if (Mul->getOperand(0)->isAllOnesValue()) { 255 SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end()); 256 const SCEV *NewMul = SE.getMulExpr(Ops); 257 258 SmallVector<const SCEV *, 4> MyGood; 259 SmallVector<const SCEV *, 4> MyBad; 260 DoInitialMatch(NewMul, L, MyGood, MyBad, SE, DT); 261 const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue( 262 SE.getEffectiveSCEVType(NewMul->getType()))); 263 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(), 264 E = MyGood.end(); I != E; ++I) 265 Good.push_back(SE.getMulExpr(NegOne, *I)); 266 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(), 267 E = MyBad.end(); I != E; ++I) 268 Bad.push_back(SE.getMulExpr(NegOne, *I)); 269 return; 270 } 271 272 // Ok, we can't do anything interesting. Just stuff the whole thing into a 273 // register and hope for the best. 274 Bad.push_back(S); 275} 276 277/// InitialMatch - Incorporate loop-variant parts of S into this Formula, 278/// attempting to keep all loop-invariant and loop-computable values in a 279/// single base register. 280void Formula::InitialMatch(const SCEV *S, Loop *L, 281 ScalarEvolution &SE, DominatorTree &DT) { 282 SmallVector<const SCEV *, 4> Good; 283 SmallVector<const SCEV *, 4> Bad; 284 DoInitialMatch(S, L, Good, Bad, SE, DT); 285 if (!Good.empty()) { 286 const SCEV *Sum = SE.getAddExpr(Good); 287 if (!Sum->isZero()) 288 BaseRegs.push_back(Sum); 289 AM.HasBaseReg = true; 290 } 291 if (!Bad.empty()) { 292 const SCEV *Sum = SE.getAddExpr(Bad); 293 if (!Sum->isZero()) 294 BaseRegs.push_back(Sum); 295 AM.HasBaseReg = true; 296 } 297} 298 299/// getNumRegs - Return the total number of register operands used by this 300/// formula. This does not include register uses implied by non-constant 301/// addrec strides. 302unsigned Formula::getNumRegs() const { 303 return !!ScaledReg + BaseRegs.size(); 304} 305 306/// getType - Return the type of this formula, if it has one, or null 307/// otherwise. This type is meaningless except for the bit size. 308const Type *Formula::getType() const { 309 return !BaseRegs.empty() ? BaseRegs.front()->getType() : 310 ScaledReg ? ScaledReg->getType() : 311 AM.BaseGV ? AM.BaseGV->getType() : 312 0; 313} 314 315/// DeleteBaseReg - Delete the given base reg from the BaseRegs list. 316void Formula::DeleteBaseReg(const SCEV *&S) { 317 if (&S != &BaseRegs.back()) 318 std::swap(S, BaseRegs.back()); 319 BaseRegs.pop_back(); 320} 321 322/// referencesReg - Test if this formula references the given register. 323bool Formula::referencesReg(const SCEV *S) const { 324 return S == ScaledReg || 325 std::find(BaseRegs.begin(), BaseRegs.end(), S) != BaseRegs.end(); 326} 327 328/// hasRegsUsedByUsesOtherThan - Test whether this formula uses registers 329/// which are used by uses other than the use with the given index. 330bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx, 331 const RegUseTracker &RegUses) const { 332 if (ScaledReg) 333 if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx)) 334 return true; 335 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), 336 E = BaseRegs.end(); I != E; ++I) 337 if (RegUses.isRegUsedByUsesOtherThan(*I, LUIdx)) 338 return true; 339 return false; 340} 341 342void Formula::print(raw_ostream &OS) const { 343 bool First = true; 344 if (AM.BaseGV) { 345 if (!First) OS << " + "; else First = false; 346 WriteAsOperand(OS, AM.BaseGV, /*PrintType=*/false); 347 } 348 if (AM.BaseOffs != 0) { 349 if (!First) OS << " + "; else First = false; 350 OS << AM.BaseOffs; 351 } 352 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(), 353 E = BaseRegs.end(); I != E; ++I) { 354 if (!First) OS << " + "; else First = false; 355 OS << "reg(" << **I << ')'; 356 } 357 if (AM.HasBaseReg && BaseRegs.empty()) { 358 if (!First) OS << " + "; else First = false; 359 OS << "**error: HasBaseReg**"; 360 } else if (!AM.HasBaseReg && !BaseRegs.empty()) { 361 if (!First) OS << " + "; else First = false; 362 OS << "**error: !HasBaseReg**"; 363 } 364 if (AM.Scale != 0) { 365 if (!First) OS << " + "; else First = false; 366 OS << AM.Scale << "*reg("; 367 if (ScaledReg) 368 OS << *ScaledReg; 369 else 370 OS << "<unknown>"; 371 OS << ')'; 372 } 373} 374 375void Formula::dump() const { 376 print(errs()); errs() << '\n'; 377} 378 379/// isAddRecSExtable - Return true if the given addrec can be sign-extended 380/// without changing its value. 381static bool isAddRecSExtable(const SCEVAddRecExpr *AR, ScalarEvolution &SE) { 382 const Type *WideTy = 383 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(AR->getType()) + 1); 384 return isa<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy)); 385} 386 387/// isAddSExtable - Return true if the given add can be sign-extended 388/// without changing its value. 389static bool isAddSExtable(const SCEVAddExpr *A, ScalarEvolution &SE) { 390 const Type *WideTy = 391 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(A->getType()) + 1); 392 return isa<SCEVAddExpr>(SE.getSignExtendExpr(A, WideTy)); 393} 394 395/// isMulSExtable - Return true if the given add can be sign-extended 396/// without changing its value. 397static bool isMulSExtable(const SCEVMulExpr *A, ScalarEvolution &SE) { 398 const Type *WideTy = 399 IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(A->getType()) + 1); 400 return isa<SCEVMulExpr>(SE.getSignExtendExpr(A, WideTy)); 401} 402 403/// getExactSDiv - Return an expression for LHS /s RHS, if it can be determined 404/// and if the remainder is known to be zero, or null otherwise. If 405/// IgnoreSignificantBits is true, expressions like (X * Y) /s Y are simplified 406/// to Y, ignoring that the multiplication may overflow, which is useful when 407/// the result will be used in a context where the most significant bits are 408/// ignored. 409static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS, 410 ScalarEvolution &SE, 411 bool IgnoreSignificantBits = false) { 412 // Handle the trivial case, which works for any SCEV type. 413 if (LHS == RHS) 414 return SE.getConstant(LHS->getType(), 1); 415 416 // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do some 417 // folding. 418 if (RHS->isAllOnesValue()) 419 return SE.getMulExpr(LHS, RHS); 420 421 // Check for a division of a constant by a constant. 422 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) { 423 const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS); 424 if (!RC) 425 return 0; 426 if (C->getValue()->getValue().srem(RC->getValue()->getValue()) != 0) 427 return 0; 428 return SE.getConstant(C->getValue()->getValue() 429 .sdiv(RC->getValue()->getValue())); 430 } 431 432 // Distribute the sdiv over addrec operands, if the addrec doesn't overflow. 433 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) { 434 if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) { 435 const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE, 436 IgnoreSignificantBits); 437 if (!Start) return 0; 438 const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE, 439 IgnoreSignificantBits); 440 if (!Step) return 0; 441 return SE.getAddRecExpr(Start, Step, AR->getLoop()); 442 } 443 } 444 445 // Distribute the sdiv over add operands, if the add doesn't overflow. 446 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) { 447 if (IgnoreSignificantBits || isAddSExtable(Add, SE)) { 448 SmallVector<const SCEV *, 8> Ops; 449 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 450 I != E; ++I) { 451 const SCEV *Op = getExactSDiv(*I, RHS, SE, 452 IgnoreSignificantBits); 453 if (!Op) return 0; 454 Ops.push_back(Op); 455 } 456 return SE.getAddExpr(Ops); 457 } 458 } 459 460 // Check for a multiply operand that we can pull RHS out of. 461 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(LHS)) 462 if (IgnoreSignificantBits || isMulSExtable(Mul, SE)) { 463 SmallVector<const SCEV *, 4> Ops; 464 bool Found = false; 465 for (SCEVMulExpr::op_iterator I = Mul->op_begin(), E = Mul->op_end(); 466 I != E; ++I) { 467 const SCEV *S = *I; 468 if (!Found) 469 if (const SCEV *Q = getExactSDiv(S, RHS, SE, 470 IgnoreSignificantBits)) { 471 S = Q; 472 Found = true; 473 } 474 Ops.push_back(S); 475 } 476 return Found ? SE.getMulExpr(Ops) : 0; 477 } 478 479 // Otherwise we don't know. 480 return 0; 481} 482 483/// ExtractImmediate - If S involves the addition of a constant integer value, 484/// return that integer value, and mutate S to point to a new SCEV with that 485/// value excluded. 486static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) { 487 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 488 if (C->getValue()->getValue().getMinSignedBits() <= 64) { 489 S = SE.getConstant(C->getType(), 0); 490 return C->getValue()->getSExtValue(); 491 } 492 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 493 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end()); 494 int64_t Result = ExtractImmediate(NewOps.front(), SE); 495 S = SE.getAddExpr(NewOps); 496 return Result; 497 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 498 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end()); 499 int64_t Result = ExtractImmediate(NewOps.front(), SE); 500 S = SE.getAddRecExpr(NewOps, AR->getLoop()); 501 return Result; 502 } 503 return 0; 504} 505 506/// ExtractSymbol - If S involves the addition of a GlobalValue address, 507/// return that symbol, and mutate S to point to a new SCEV with that 508/// value excluded. 509static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) { 510 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 511 if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) { 512 S = SE.getConstant(GV->getType(), 0); 513 return GV; 514 } 515 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 516 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end()); 517 GlobalValue *Result = ExtractSymbol(NewOps.back(), SE); 518 S = SE.getAddExpr(NewOps); 519 return Result; 520 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 521 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end()); 522 GlobalValue *Result = ExtractSymbol(NewOps.front(), SE); 523 S = SE.getAddRecExpr(NewOps, AR->getLoop()); 524 return Result; 525 } 526 return 0; 527} 528 529/// isAddressUse - Returns true if the specified instruction is using the 530/// specified value as an address. 531static bool isAddressUse(Instruction *Inst, Value *OperandVal) { 532 bool isAddress = isa<LoadInst>(Inst); 533 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 534 if (SI->getOperand(1) == OperandVal) 535 isAddress = true; 536 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 537 // Addressing modes can also be folded into prefetches and a variety 538 // of intrinsics. 539 switch (II->getIntrinsicID()) { 540 default: break; 541 case Intrinsic::prefetch: 542 case Intrinsic::x86_sse2_loadu_dq: 543 case Intrinsic::x86_sse2_loadu_pd: 544 case Intrinsic::x86_sse_loadu_ps: 545 case Intrinsic::x86_sse_storeu_ps: 546 case Intrinsic::x86_sse2_storeu_pd: 547 case Intrinsic::x86_sse2_storeu_dq: 548 case Intrinsic::x86_sse2_storel_dq: 549 if (II->getOperand(1) == OperandVal) 550 isAddress = true; 551 break; 552 } 553 } 554 return isAddress; 555} 556 557/// getAccessType - Return the type of the memory being accessed. 558static const Type *getAccessType(const Instruction *Inst) { 559 const Type *AccessTy = Inst->getType(); 560 if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) 561 AccessTy = SI->getOperand(0)->getType(); 562 else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 563 // Addressing modes can also be folded into prefetches and a variety 564 // of intrinsics. 565 switch (II->getIntrinsicID()) { 566 default: break; 567 case Intrinsic::x86_sse_storeu_ps: 568 case Intrinsic::x86_sse2_storeu_pd: 569 case Intrinsic::x86_sse2_storeu_dq: 570 case Intrinsic::x86_sse2_storel_dq: 571 AccessTy = II->getOperand(1)->getType(); 572 break; 573 } 574 } 575 576 // All pointers have the same requirements, so canonicalize them to an 577 // arbitrary pointer type to minimize variation. 578 if (const PointerType *PTy = dyn_cast<PointerType>(AccessTy)) 579 AccessTy = PointerType::get(IntegerType::get(PTy->getContext(), 1), 580 PTy->getAddressSpace()); 581 582 return AccessTy; 583} 584 585/// DeleteTriviallyDeadInstructions - If any of the instructions is the 586/// specified set are trivially dead, delete them and see if this makes any of 587/// their operands subsequently dead. 588static bool 589DeleteTriviallyDeadInstructions(SmallVectorImpl<WeakVH> &DeadInsts) { 590 bool Changed = false; 591 592 while (!DeadInsts.empty()) { 593 Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()); 594 595 if (I == 0 || !isInstructionTriviallyDead(I)) 596 continue; 597 598 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 599 if (Instruction *U = dyn_cast<Instruction>(*OI)) { 600 *OI = 0; 601 if (U->use_empty()) 602 DeadInsts.push_back(U); 603 } 604 605 I->eraseFromParent(); 606 Changed = true; 607 } 608 609 return Changed; 610} 611 612namespace { 613 614/// Cost - This class is used to measure and compare candidate formulae. 615class Cost { 616 /// TODO: Some of these could be merged. Also, a lexical ordering 617 /// isn't always optimal. 618 unsigned NumRegs; 619 unsigned AddRecCost; 620 unsigned NumIVMuls; 621 unsigned NumBaseAdds; 622 unsigned ImmCost; 623 unsigned SetupCost; 624 625public: 626 Cost() 627 : NumRegs(0), AddRecCost(0), NumIVMuls(0), NumBaseAdds(0), ImmCost(0), 628 SetupCost(0) {} 629 630 unsigned getNumRegs() const { return NumRegs; } 631 632 bool operator<(const Cost &Other) const; 633 634 void Loose(); 635 636 void RateFormula(const Formula &F, 637 SmallPtrSet<const SCEV *, 16> &Regs, 638 const DenseSet<const SCEV *> &VisitedRegs, 639 const Loop *L, 640 const SmallVectorImpl<int64_t> &Offsets, 641 ScalarEvolution &SE, DominatorTree &DT); 642 643 void print(raw_ostream &OS) const; 644 void dump() const; 645 646private: 647 void RateRegister(const SCEV *Reg, 648 SmallPtrSet<const SCEV *, 16> &Regs, 649 const Loop *L, 650 ScalarEvolution &SE, DominatorTree &DT); 651 void RatePrimaryRegister(const SCEV *Reg, 652 SmallPtrSet<const SCEV *, 16> &Regs, 653 const Loop *L, 654 ScalarEvolution &SE, DominatorTree &DT); 655}; 656 657} 658 659/// RateRegister - Tally up interesting quantities from the given register. 660void Cost::RateRegister(const SCEV *Reg, 661 SmallPtrSet<const SCEV *, 16> &Regs, 662 const Loop *L, 663 ScalarEvolution &SE, DominatorTree &DT) { 664 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Reg)) { 665 if (AR->getLoop() == L) 666 AddRecCost += 1; /// TODO: This should be a function of the stride. 667 668 // If this is an addrec for a loop that's already been visited by LSR, 669 // don't second-guess its addrec phi nodes. LSR isn't currently smart 670 // enough to reason about more than one loop at a time. Consider these 671 // registers free and leave them alone. 672 else if (L->contains(AR->getLoop()) || 673 (!AR->getLoop()->contains(L) && 674 DT.dominates(L->getHeader(), AR->getLoop()->getHeader()))) { 675 for (BasicBlock::iterator I = AR->getLoop()->getHeader()->begin(); 676 PHINode *PN = dyn_cast<PHINode>(I); ++I) 677 if (SE.isSCEVable(PN->getType()) && 678 (SE.getEffectiveSCEVType(PN->getType()) == 679 SE.getEffectiveSCEVType(AR->getType())) && 680 SE.getSCEV(PN) == AR) 681 return; 682 683 // If this isn't one of the addrecs that the loop already has, it 684 // would require a costly new phi and add. TODO: This isn't 685 // precisely modeled right now. 686 ++NumBaseAdds; 687 if (!Regs.count(AR->getStart())) 688 RateRegister(AR->getStart(), Regs, L, SE, DT); 689 } 690 691 // Add the step value register, if it needs one. 692 // TODO: The non-affine case isn't precisely modeled here. 693 if (!AR->isAffine() || !isa<SCEVConstant>(AR->getOperand(1))) 694 if (!Regs.count(AR->getStart())) 695 RateRegister(AR->getOperand(1), Regs, L, SE, DT); 696 } 697 ++NumRegs; 698 699 // Rough heuristic; favor registers which don't require extra setup 700 // instructions in the preheader. 701 if (!isa<SCEVUnknown>(Reg) && 702 !isa<SCEVConstant>(Reg) && 703 !(isa<SCEVAddRecExpr>(Reg) && 704 (isa<SCEVUnknown>(cast<SCEVAddRecExpr>(Reg)->getStart()) || 705 isa<SCEVConstant>(cast<SCEVAddRecExpr>(Reg)->getStart())))) 706 ++SetupCost; 707} 708 709/// RatePrimaryRegister - Record this register in the set. If we haven't seen it 710/// before, rate it. 711void Cost::RatePrimaryRegister(const SCEV *Reg, 712 SmallPtrSet<const SCEV *, 16> &Regs, 713 const Loop *L, 714 ScalarEvolution &SE, DominatorTree &DT) { 715 if (Regs.insert(Reg)) 716 RateRegister(Reg, Regs, L, SE, DT); 717} 718 719void Cost::RateFormula(const Formula &F, 720 SmallPtrSet<const SCEV *, 16> &Regs, 721 const DenseSet<const SCEV *> &VisitedRegs, 722 const Loop *L, 723 const SmallVectorImpl<int64_t> &Offsets, 724 ScalarEvolution &SE, DominatorTree &DT) { 725 // Tally up the registers. 726 if (const SCEV *ScaledReg = F.ScaledReg) { 727 if (VisitedRegs.count(ScaledReg)) { 728 Loose(); 729 return; 730 } 731 RatePrimaryRegister(ScaledReg, Regs, L, SE, DT); 732 } 733 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 734 E = F.BaseRegs.end(); I != E; ++I) { 735 const SCEV *BaseReg = *I; 736 if (VisitedRegs.count(BaseReg)) { 737 Loose(); 738 return; 739 } 740 RatePrimaryRegister(BaseReg, Regs, L, SE, DT); 741 742 NumIVMuls += isa<SCEVMulExpr>(BaseReg) && 743 BaseReg->hasComputableLoopEvolution(L); 744 } 745 746 if (F.BaseRegs.size() > 1) 747 NumBaseAdds += F.BaseRegs.size() - 1; 748 749 // Tally up the non-zero immediates. 750 for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), 751 E = Offsets.end(); I != E; ++I) { 752 int64_t Offset = (uint64_t)*I + F.AM.BaseOffs; 753 if (F.AM.BaseGV) 754 ImmCost += 64; // Handle symbolic values conservatively. 755 // TODO: This should probably be the pointer size. 756 else if (Offset != 0) 757 ImmCost += APInt(64, Offset, true).getMinSignedBits(); 758 } 759} 760 761/// Loose - Set this cost to a loosing value. 762void Cost::Loose() { 763 NumRegs = ~0u; 764 AddRecCost = ~0u; 765 NumIVMuls = ~0u; 766 NumBaseAdds = ~0u; 767 ImmCost = ~0u; 768 SetupCost = ~0u; 769} 770 771/// operator< - Choose the lower cost. 772bool Cost::operator<(const Cost &Other) const { 773 if (NumRegs != Other.NumRegs) 774 return NumRegs < Other.NumRegs; 775 if (AddRecCost != Other.AddRecCost) 776 return AddRecCost < Other.AddRecCost; 777 if (NumIVMuls != Other.NumIVMuls) 778 return NumIVMuls < Other.NumIVMuls; 779 if (NumBaseAdds != Other.NumBaseAdds) 780 return NumBaseAdds < Other.NumBaseAdds; 781 if (ImmCost != Other.ImmCost) 782 return ImmCost < Other.ImmCost; 783 if (SetupCost != Other.SetupCost) 784 return SetupCost < Other.SetupCost; 785 return false; 786} 787 788void Cost::print(raw_ostream &OS) const { 789 OS << NumRegs << " reg" << (NumRegs == 1 ? "" : "s"); 790 if (AddRecCost != 0) 791 OS << ", with addrec cost " << AddRecCost; 792 if (NumIVMuls != 0) 793 OS << ", plus " << NumIVMuls << " IV mul" << (NumIVMuls == 1 ? "" : "s"); 794 if (NumBaseAdds != 0) 795 OS << ", plus " << NumBaseAdds << " base add" 796 << (NumBaseAdds == 1 ? "" : "s"); 797 if (ImmCost != 0) 798 OS << ", plus " << ImmCost << " imm cost"; 799 if (SetupCost != 0) 800 OS << ", plus " << SetupCost << " setup cost"; 801} 802 803void Cost::dump() const { 804 print(errs()); errs() << '\n'; 805} 806 807namespace { 808 809/// LSRFixup - An operand value in an instruction which is to be replaced 810/// with some equivalent, possibly strength-reduced, replacement. 811struct LSRFixup { 812 /// UserInst - The instruction which will be updated. 813 Instruction *UserInst; 814 815 /// OperandValToReplace - The operand of the instruction which will 816 /// be replaced. The operand may be used more than once; every instance 817 /// will be replaced. 818 Value *OperandValToReplace; 819 820 /// PostIncLoops - If this user is to use the post-incremented value of an 821 /// induction variable, this variable is non-null and holds the loop 822 /// associated with the induction variable. 823 PostIncLoopSet PostIncLoops; 824 825 /// LUIdx - The index of the LSRUse describing the expression which 826 /// this fixup needs, minus an offset (below). 827 size_t LUIdx; 828 829 /// Offset - A constant offset to be added to the LSRUse expression. 830 /// This allows multiple fixups to share the same LSRUse with different 831 /// offsets, for example in an unrolled loop. 832 int64_t Offset; 833 834 bool isUseFullyOutsideLoop(const Loop *L) const; 835 836 LSRFixup(); 837 838 void print(raw_ostream &OS) const; 839 void dump() const; 840}; 841 842} 843 844LSRFixup::LSRFixup() 845 : UserInst(0), OperandValToReplace(0), LUIdx(~size_t(0)), Offset(0) {} 846 847/// isUseFullyOutsideLoop - Test whether this fixup always uses its 848/// value outside of the given loop. 849bool LSRFixup::isUseFullyOutsideLoop(const Loop *L) const { 850 // PHI nodes use their value in their incoming blocks. 851 if (const PHINode *PN = dyn_cast<PHINode>(UserInst)) { 852 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 853 if (PN->getIncomingValue(i) == OperandValToReplace && 854 L->contains(PN->getIncomingBlock(i))) 855 return false; 856 return true; 857 } 858 859 return !L->contains(UserInst); 860} 861 862void LSRFixup::print(raw_ostream &OS) const { 863 OS << "UserInst="; 864 // Store is common and interesting enough to be worth special-casing. 865 if (StoreInst *Store = dyn_cast<StoreInst>(UserInst)) { 866 OS << "store "; 867 WriteAsOperand(OS, Store->getOperand(0), /*PrintType=*/false); 868 } else if (UserInst->getType()->isVoidTy()) 869 OS << UserInst->getOpcodeName(); 870 else 871 WriteAsOperand(OS, UserInst, /*PrintType=*/false); 872 873 OS << ", OperandValToReplace="; 874 WriteAsOperand(OS, OperandValToReplace, /*PrintType=*/false); 875 876 for (PostIncLoopSet::const_iterator I = PostIncLoops.begin(), 877 E = PostIncLoops.end(); I != E; ++I) { 878 OS << ", PostIncLoop="; 879 WriteAsOperand(OS, (*I)->getHeader(), /*PrintType=*/false); 880 } 881 882 if (LUIdx != ~size_t(0)) 883 OS << ", LUIdx=" << LUIdx; 884 885 if (Offset != 0) 886 OS << ", Offset=" << Offset; 887} 888 889void LSRFixup::dump() const { 890 print(errs()); errs() << '\n'; 891} 892 893namespace { 894 895/// UniquifierDenseMapInfo - A DenseMapInfo implementation for holding 896/// DenseMaps and DenseSets of sorted SmallVectors of const SCEV*. 897struct UniquifierDenseMapInfo { 898 static SmallVector<const SCEV *, 2> getEmptyKey() { 899 SmallVector<const SCEV *, 2> V; 900 V.push_back(reinterpret_cast<const SCEV *>(-1)); 901 return V; 902 } 903 904 static SmallVector<const SCEV *, 2> getTombstoneKey() { 905 SmallVector<const SCEV *, 2> V; 906 V.push_back(reinterpret_cast<const SCEV *>(-2)); 907 return V; 908 } 909 910 static unsigned getHashValue(const SmallVector<const SCEV *, 2> &V) { 911 unsigned Result = 0; 912 for (SmallVectorImpl<const SCEV *>::const_iterator I = V.begin(), 913 E = V.end(); I != E; ++I) 914 Result ^= DenseMapInfo<const SCEV *>::getHashValue(*I); 915 return Result; 916 } 917 918 static bool isEqual(const SmallVector<const SCEV *, 2> &LHS, 919 const SmallVector<const SCEV *, 2> &RHS) { 920 return LHS == RHS; 921 } 922}; 923 924/// LSRUse - This class holds the state that LSR keeps for each use in 925/// IVUsers, as well as uses invented by LSR itself. It includes information 926/// about what kinds of things can be folded into the user, information about 927/// the user itself, and information about how the use may be satisfied. 928/// TODO: Represent multiple users of the same expression in common? 929class LSRUse { 930 DenseSet<SmallVector<const SCEV *, 2>, UniquifierDenseMapInfo> Uniquifier; 931 932public: 933 /// KindType - An enum for a kind of use, indicating what types of 934 /// scaled and immediate operands it might support. 935 enum KindType { 936 Basic, ///< A normal use, with no folding. 937 Special, ///< A special case of basic, allowing -1 scales. 938 Address, ///< An address use; folding according to TargetLowering 939 ICmpZero ///< An equality icmp with both operands folded into one. 940 // TODO: Add a generic icmp too? 941 }; 942 943 KindType Kind; 944 const Type *AccessTy; 945 946 SmallVector<int64_t, 8> Offsets; 947 int64_t MinOffset; 948 int64_t MaxOffset; 949 950 /// AllFixupsOutsideLoop - This records whether all of the fixups using this 951 /// LSRUse are outside of the loop, in which case some special-case heuristics 952 /// may be used. 953 bool AllFixupsOutsideLoop; 954 955 /// Formulae - A list of ways to build a value that can satisfy this user. 956 /// After the list is populated, one of these is selected heuristically and 957 /// used to formulate a replacement for OperandValToReplace in UserInst. 958 SmallVector<Formula, 12> Formulae; 959 960 /// Regs - The set of register candidates used by all formulae in this LSRUse. 961 SmallPtrSet<const SCEV *, 4> Regs; 962 963 LSRUse(KindType K, const Type *T) : Kind(K), AccessTy(T), 964 MinOffset(INT64_MAX), 965 MaxOffset(INT64_MIN), 966 AllFixupsOutsideLoop(true) {} 967 968 bool HasFormulaWithSameRegs(const Formula &F) const; 969 bool InsertFormula(const Formula &F); 970 void DeleteFormula(Formula &F); 971 void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses); 972 973 void check() const; 974 975 void print(raw_ostream &OS) const; 976 void dump() const; 977}; 978 979/// HasFormula - Test whether this use as a formula which has the same 980/// registers as the given formula. 981bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const { 982 SmallVector<const SCEV *, 2> Key = F.BaseRegs; 983 if (F.ScaledReg) Key.push_back(F.ScaledReg); 984 // Unstable sort by host order ok, because this is only used for uniquifying. 985 std::sort(Key.begin(), Key.end()); 986 return Uniquifier.count(Key); 987} 988 989/// InsertFormula - If the given formula has not yet been inserted, add it to 990/// the list, and return true. Return false otherwise. 991bool LSRUse::InsertFormula(const Formula &F) { 992 SmallVector<const SCEV *, 2> Key = F.BaseRegs; 993 if (F.ScaledReg) Key.push_back(F.ScaledReg); 994 // Unstable sort by host order ok, because this is only used for uniquifying. 995 std::sort(Key.begin(), Key.end()); 996 997 if (!Uniquifier.insert(Key).second) 998 return false; 999 1000 // Using a register to hold the value of 0 is not profitable. 1001 assert((!F.ScaledReg || !F.ScaledReg->isZero()) && 1002 "Zero allocated in a scaled register!"); 1003#ifndef NDEBUG 1004 for (SmallVectorImpl<const SCEV *>::const_iterator I = 1005 F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) 1006 assert(!(*I)->isZero() && "Zero allocated in a base register!"); 1007#endif 1008 1009 // Add the formula to the list. 1010 Formulae.push_back(F); 1011 1012 // Record registers now being used by this use. 1013 if (F.ScaledReg) Regs.insert(F.ScaledReg); 1014 Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); 1015 1016 return true; 1017} 1018 1019/// DeleteFormula - Remove the given formula from this use's list. 1020void LSRUse::DeleteFormula(Formula &F) { 1021 if (&F != &Formulae.back()) 1022 std::swap(F, Formulae.back()); 1023 Formulae.pop_back(); 1024 assert(!Formulae.empty() && "LSRUse has no formulae left!"); 1025} 1026 1027/// RecomputeRegs - Recompute the Regs field, and update RegUses. 1028void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) { 1029 // Now that we've filtered out some formulae, recompute the Regs set. 1030 SmallPtrSet<const SCEV *, 4> OldRegs = Regs; 1031 Regs.clear(); 1032 for (SmallVectorImpl<Formula>::const_iterator I = Formulae.begin(), 1033 E = Formulae.end(); I != E; ++I) { 1034 const Formula &F = *I; 1035 if (F.ScaledReg) Regs.insert(F.ScaledReg); 1036 Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end()); 1037 } 1038 1039 // Update the RegTracker. 1040 for (SmallPtrSet<const SCEV *, 4>::iterator I = OldRegs.begin(), 1041 E = OldRegs.end(); I != E; ++I) 1042 if (!Regs.count(*I)) 1043 RegUses.DropRegister(*I, LUIdx); 1044} 1045 1046void LSRUse::print(raw_ostream &OS) const { 1047 OS << "LSR Use: Kind="; 1048 switch (Kind) { 1049 case Basic: OS << "Basic"; break; 1050 case Special: OS << "Special"; break; 1051 case ICmpZero: OS << "ICmpZero"; break; 1052 case Address: 1053 OS << "Address of "; 1054 if (AccessTy->isPointerTy()) 1055 OS << "pointer"; // the full pointer type could be really verbose 1056 else 1057 OS << *AccessTy; 1058 } 1059 1060 OS << ", Offsets={"; 1061 for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(), 1062 E = Offsets.end(); I != E; ++I) { 1063 OS << *I; 1064 if (next(I) != E) 1065 OS << ','; 1066 } 1067 OS << '}'; 1068 1069 if (AllFixupsOutsideLoop) 1070 OS << ", all-fixups-outside-loop"; 1071} 1072 1073void LSRUse::dump() const { 1074 print(errs()); errs() << '\n'; 1075} 1076 1077/// isLegalUse - Test whether the use described by AM is "legal", meaning it can 1078/// be completely folded into the user instruction at isel time. This includes 1079/// address-mode folding and special icmp tricks. 1080static bool isLegalUse(const TargetLowering::AddrMode &AM, 1081 LSRUse::KindType Kind, const Type *AccessTy, 1082 const TargetLowering *TLI) { 1083 switch (Kind) { 1084 case LSRUse::Address: 1085 // If we have low-level target information, ask the target if it can 1086 // completely fold this address. 1087 if (TLI) return TLI->isLegalAddressingMode(AM, AccessTy); 1088 1089 // Otherwise, just guess that reg+reg addressing is legal. 1090 return !AM.BaseGV && AM.BaseOffs == 0 && AM.Scale <= 1; 1091 1092 case LSRUse::ICmpZero: 1093 // There's not even a target hook for querying whether it would be legal to 1094 // fold a GV into an ICmp. 1095 if (AM.BaseGV) 1096 return false; 1097 1098 // ICmp only has two operands; don't allow more than two non-trivial parts. 1099 if (AM.Scale != 0 && AM.HasBaseReg && AM.BaseOffs != 0) 1100 return false; 1101 1102 // ICmp only supports no scale or a -1 scale, as we can "fold" a -1 scale by 1103 // putting the scaled register in the other operand of the icmp. 1104 if (AM.Scale != 0 && AM.Scale != -1) 1105 return false; 1106 1107 // If we have low-level target information, ask the target if it can fold an 1108 // integer immediate on an icmp. 1109 if (AM.BaseOffs != 0) { 1110 if (TLI) return TLI->isLegalICmpImmediate(-AM.BaseOffs); 1111 return false; 1112 } 1113 1114 return true; 1115 1116 case LSRUse::Basic: 1117 // Only handle single-register values. 1118 return !AM.BaseGV && AM.Scale == 0 && AM.BaseOffs == 0; 1119 1120 case LSRUse::Special: 1121 // Only handle -1 scales, or no scale. 1122 return AM.Scale == 0 || AM.Scale == -1; 1123 } 1124 1125 return false; 1126} 1127 1128static bool isLegalUse(TargetLowering::AddrMode AM, 1129 int64_t MinOffset, int64_t MaxOffset, 1130 LSRUse::KindType Kind, const Type *AccessTy, 1131 const TargetLowering *TLI) { 1132 // Check for overflow. 1133 if (((int64_t)((uint64_t)AM.BaseOffs + MinOffset) > AM.BaseOffs) != 1134 (MinOffset > 0)) 1135 return false; 1136 AM.BaseOffs = (uint64_t)AM.BaseOffs + MinOffset; 1137 if (isLegalUse(AM, Kind, AccessTy, TLI)) { 1138 AM.BaseOffs = (uint64_t)AM.BaseOffs - MinOffset; 1139 // Check for overflow. 1140 if (((int64_t)((uint64_t)AM.BaseOffs + MaxOffset) > AM.BaseOffs) != 1141 (MaxOffset > 0)) 1142 return false; 1143 AM.BaseOffs = (uint64_t)AM.BaseOffs + MaxOffset; 1144 return isLegalUse(AM, Kind, AccessTy, TLI); 1145 } 1146 return false; 1147} 1148 1149static bool isAlwaysFoldable(int64_t BaseOffs, 1150 GlobalValue *BaseGV, 1151 bool HasBaseReg, 1152 LSRUse::KindType Kind, const Type *AccessTy, 1153 const TargetLowering *TLI) { 1154 // Fast-path: zero is always foldable. 1155 if (BaseOffs == 0 && !BaseGV) return true; 1156 1157 // Conservatively, create an address with an immediate and a 1158 // base and a scale. 1159 TargetLowering::AddrMode AM; 1160 AM.BaseOffs = BaseOffs; 1161 AM.BaseGV = BaseGV; 1162 AM.HasBaseReg = HasBaseReg; 1163 AM.Scale = Kind == LSRUse::ICmpZero ? -1 : 1; 1164 1165 // Canonicalize a scale of 1 to a base register if the formula doesn't 1166 // already have a base register. 1167 if (!AM.HasBaseReg && AM.Scale == 1) { 1168 AM.Scale = 0; 1169 AM.HasBaseReg = true; 1170 } 1171 1172 return isLegalUse(AM, Kind, AccessTy, TLI); 1173} 1174 1175static bool isAlwaysFoldable(const SCEV *S, 1176 int64_t MinOffset, int64_t MaxOffset, 1177 bool HasBaseReg, 1178 LSRUse::KindType Kind, const Type *AccessTy, 1179 const TargetLowering *TLI, 1180 ScalarEvolution &SE) { 1181 // Fast-path: zero is always foldable. 1182 if (S->isZero()) return true; 1183 1184 // Conservatively, create an address with an immediate and a 1185 // base and a scale. 1186 int64_t BaseOffs = ExtractImmediate(S, SE); 1187 GlobalValue *BaseGV = ExtractSymbol(S, SE); 1188 1189 // If there's anything else involved, it's not foldable. 1190 if (!S->isZero()) return false; 1191 1192 // Fast-path: zero is always foldable. 1193 if (BaseOffs == 0 && !BaseGV) return true; 1194 1195 // Conservatively, create an address with an immediate and a 1196 // base and a scale. 1197 TargetLowering::AddrMode AM; 1198 AM.BaseOffs = BaseOffs; 1199 AM.BaseGV = BaseGV; 1200 AM.HasBaseReg = HasBaseReg; 1201 AM.Scale = Kind == LSRUse::ICmpZero ? -1 : 1; 1202 1203 return isLegalUse(AM, MinOffset, MaxOffset, Kind, AccessTy, TLI); 1204} 1205 1206/// FormulaSorter - This class implements an ordering for formulae which sorts 1207/// the by their standalone cost. 1208class FormulaSorter { 1209 /// These two sets are kept empty, so that we compute standalone costs. 1210 DenseSet<const SCEV *> VisitedRegs; 1211 SmallPtrSet<const SCEV *, 16> Regs; 1212 Loop *L; 1213 LSRUse *LU; 1214 ScalarEvolution &SE; 1215 DominatorTree &DT; 1216 1217public: 1218 FormulaSorter(Loop *l, LSRUse &lu, ScalarEvolution &se, DominatorTree &dt) 1219 : L(l), LU(&lu), SE(se), DT(dt) {} 1220 1221 bool operator()(const Formula &A, const Formula &B) { 1222 Cost CostA; 1223 CostA.RateFormula(A, Regs, VisitedRegs, L, LU->Offsets, SE, DT); 1224 Regs.clear(); 1225 Cost CostB; 1226 CostB.RateFormula(B, Regs, VisitedRegs, L, LU->Offsets, SE, DT); 1227 Regs.clear(); 1228 return CostA < CostB; 1229 } 1230}; 1231 1232/// LSRInstance - This class holds state for the main loop strength reduction 1233/// logic. 1234class LSRInstance { 1235 IVUsers &IU; 1236 ScalarEvolution &SE; 1237 DominatorTree &DT; 1238 LoopInfo &LI; 1239 const TargetLowering *const TLI; 1240 Loop *const L; 1241 bool Changed; 1242 1243 /// IVIncInsertPos - This is the insert position that the current loop's 1244 /// induction variable increment should be placed. In simple loops, this is 1245 /// the latch block's terminator. But in more complicated cases, this is a 1246 /// position which will dominate all the in-loop post-increment users. 1247 Instruction *IVIncInsertPos; 1248 1249 /// Factors - Interesting factors between use strides. 1250 SmallSetVector<int64_t, 8> Factors; 1251 1252 /// Types - Interesting use types, to facilitate truncation reuse. 1253 SmallSetVector<const Type *, 4> Types; 1254 1255 /// Fixups - The list of operands which are to be replaced. 1256 SmallVector<LSRFixup, 16> Fixups; 1257 1258 /// Uses - The list of interesting uses. 1259 SmallVector<LSRUse, 16> Uses; 1260 1261 /// RegUses - Track which uses use which register candidates. 1262 RegUseTracker RegUses; 1263 1264 void OptimizeShadowIV(); 1265 bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse); 1266 ICmpInst *OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse); 1267 void OptimizeLoopTermCond(); 1268 1269 void CollectInterestingTypesAndFactors(); 1270 void CollectFixupsAndInitialFormulae(); 1271 1272 LSRFixup &getNewFixup() { 1273 Fixups.push_back(LSRFixup()); 1274 return Fixups.back(); 1275 } 1276 1277 // Support for sharing of LSRUses between LSRFixups. 1278 typedef DenseMap<const SCEV *, size_t> UseMapTy; 1279 UseMapTy UseMap; 1280 1281 bool reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 1282 LSRUse::KindType Kind, const Type *AccessTy); 1283 1284 std::pair<size_t, int64_t> getUse(const SCEV *&Expr, 1285 LSRUse::KindType Kind, 1286 const Type *AccessTy); 1287 1288 void DeleteUse(LSRUse &LU); 1289 1290 LSRUse *FindUseWithSimilarFormula(const Formula &F, const LSRUse &OrigLU); 1291 1292public: 1293 void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx); 1294 void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx); 1295 void CountRegisters(const Formula &F, size_t LUIdx); 1296 bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F); 1297 1298 void CollectLoopInvariantFixupsAndFormulae(); 1299 1300 void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base, 1301 unsigned Depth = 0); 1302 void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base); 1303 void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base); 1304 void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base); 1305 void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base); 1306 void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base); 1307 void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base); 1308 void GenerateCrossUseConstantOffsets(); 1309 void GenerateAllReuseFormulae(); 1310 1311 void FilterOutUndesirableDedicatedRegisters(); 1312 1313 size_t EstimateSearchSpaceComplexity() const; 1314 void NarrowSearchSpaceUsingHeuristics(); 1315 1316 void SolveRecurse(SmallVectorImpl<const Formula *> &Solution, 1317 Cost &SolutionCost, 1318 SmallVectorImpl<const Formula *> &Workspace, 1319 const Cost &CurCost, 1320 const SmallPtrSet<const SCEV *, 16> &CurRegs, 1321 DenseSet<const SCEV *> &VisitedRegs) const; 1322 void Solve(SmallVectorImpl<const Formula *> &Solution) const; 1323 1324 BasicBlock::iterator 1325 HoistInsertPosition(BasicBlock::iterator IP, 1326 const SmallVectorImpl<Instruction *> &Inputs) const; 1327 BasicBlock::iterator AdjustInsertPositionForExpand(BasicBlock::iterator IP, 1328 const LSRFixup &LF, 1329 const LSRUse &LU) const; 1330 1331 Value *Expand(const LSRFixup &LF, 1332 const Formula &F, 1333 BasicBlock::iterator IP, 1334 SCEVExpander &Rewriter, 1335 SmallVectorImpl<WeakVH> &DeadInsts) const; 1336 void RewriteForPHI(PHINode *PN, const LSRFixup &LF, 1337 const Formula &F, 1338 SCEVExpander &Rewriter, 1339 SmallVectorImpl<WeakVH> &DeadInsts, 1340 Pass *P) const; 1341 void Rewrite(const LSRFixup &LF, 1342 const Formula &F, 1343 SCEVExpander &Rewriter, 1344 SmallVectorImpl<WeakVH> &DeadInsts, 1345 Pass *P) const; 1346 void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, 1347 Pass *P); 1348 1349 LSRInstance(const TargetLowering *tli, Loop *l, Pass *P); 1350 1351 bool getChanged() const { return Changed; } 1352 1353 void print_factors_and_types(raw_ostream &OS) const; 1354 void print_fixups(raw_ostream &OS) const; 1355 void print_uses(raw_ostream &OS) const; 1356 void print(raw_ostream &OS) const; 1357 void dump() const; 1358}; 1359 1360} 1361 1362/// OptimizeShadowIV - If IV is used in a int-to-float cast 1363/// inside the loop then try to eliminate the cast operation. 1364void LSRInstance::OptimizeShadowIV() { 1365 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L); 1366 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1367 return; 1368 1369 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); 1370 UI != E; /* empty */) { 1371 IVUsers::const_iterator CandidateUI = UI; 1372 ++UI; 1373 Instruction *ShadowUse = CandidateUI->getUser(); 1374 const Type *DestTy = NULL; 1375 1376 /* If shadow use is a int->float cast then insert a second IV 1377 to eliminate this cast. 1378 1379 for (unsigned i = 0; i < n; ++i) 1380 foo((double)i); 1381 1382 is transformed into 1383 1384 double d = 0.0; 1385 for (unsigned i = 0; i < n; ++i, ++d) 1386 foo(d); 1387 */ 1388 if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) 1389 DestTy = UCast->getDestTy(); 1390 else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) 1391 DestTy = SCast->getDestTy(); 1392 if (!DestTy) continue; 1393 1394 if (TLI) { 1395 // If target does not support DestTy natively then do not apply 1396 // this transformation. 1397 EVT DVT = TLI->getValueType(DestTy); 1398 if (!TLI->isTypeLegal(DVT)) continue; 1399 } 1400 1401 PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0)); 1402 if (!PH) continue; 1403 if (PH->getNumIncomingValues() != 2) continue; 1404 1405 const Type *SrcTy = PH->getType(); 1406 int Mantissa = DestTy->getFPMantissaWidth(); 1407 if (Mantissa == -1) continue; 1408 if ((int)SE.getTypeSizeInBits(SrcTy) > Mantissa) 1409 continue; 1410 1411 unsigned Entry, Latch; 1412 if (PH->getIncomingBlock(0) == L->getLoopPreheader()) { 1413 Entry = 0; 1414 Latch = 1; 1415 } else { 1416 Entry = 1; 1417 Latch = 0; 1418 } 1419 1420 ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry)); 1421 if (!Init) continue; 1422 Constant *NewInit = ConstantFP::get(DestTy, Init->getZExtValue()); 1423 1424 BinaryOperator *Incr = 1425 dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch)); 1426 if (!Incr) continue; 1427 if (Incr->getOpcode() != Instruction::Add 1428 && Incr->getOpcode() != Instruction::Sub) 1429 continue; 1430 1431 /* Initialize new IV, double d = 0.0 in above example. */ 1432 ConstantInt *C = NULL; 1433 if (Incr->getOperand(0) == PH) 1434 C = dyn_cast<ConstantInt>(Incr->getOperand(1)); 1435 else if (Incr->getOperand(1) == PH) 1436 C = dyn_cast<ConstantInt>(Incr->getOperand(0)); 1437 else 1438 continue; 1439 1440 if (!C) continue; 1441 1442 // Ignore negative constants, as the code below doesn't handle them 1443 // correctly. TODO: Remove this restriction. 1444 if (!C->getValue().isStrictlyPositive()) continue; 1445 1446 /* Add new PHINode. */ 1447 PHINode *NewPH = PHINode::Create(DestTy, "IV.S.", PH); 1448 1449 /* create new increment. '++d' in above example. */ 1450 Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue()); 1451 BinaryOperator *NewIncr = 1452 BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ? 1453 Instruction::FAdd : Instruction::FSub, 1454 NewPH, CFP, "IV.S.next.", Incr); 1455 1456 NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry)); 1457 NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch)); 1458 1459 /* Remove cast operation */ 1460 ShadowUse->replaceAllUsesWith(NewPH); 1461 ShadowUse->eraseFromParent(); 1462 Changed = true; 1463 break; 1464 } 1465} 1466 1467/// FindIVUserForCond - If Cond has an operand that is an expression of an IV, 1468/// set the IV user and stride information and return true, otherwise return 1469/// false. 1470bool LSRInstance::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse) { 1471 for (IVUsers::iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) 1472 if (UI->getUser() == Cond) { 1473 // NOTE: we could handle setcc instructions with multiple uses here, but 1474 // InstCombine does it as well for simple uses, it's not clear that it 1475 // occurs enough in real life to handle. 1476 CondUse = UI; 1477 return true; 1478 } 1479 return false; 1480} 1481 1482/// OptimizeMax - Rewrite the loop's terminating condition if it uses 1483/// a max computation. 1484/// 1485/// This is a narrow solution to a specific, but acute, problem. For loops 1486/// like this: 1487/// 1488/// i = 0; 1489/// do { 1490/// p[i] = 0.0; 1491/// } while (++i < n); 1492/// 1493/// the trip count isn't just 'n', because 'n' might not be positive. And 1494/// unfortunately this can come up even for loops where the user didn't use 1495/// a C do-while loop. For example, seemingly well-behaved top-test loops 1496/// will commonly be lowered like this: 1497// 1498/// if (n > 0) { 1499/// i = 0; 1500/// do { 1501/// p[i] = 0.0; 1502/// } while (++i < n); 1503/// } 1504/// 1505/// and then it's possible for subsequent optimization to obscure the if 1506/// test in such a way that indvars can't find it. 1507/// 1508/// When indvars can't find the if test in loops like this, it creates a 1509/// max expression, which allows it to give the loop a canonical 1510/// induction variable: 1511/// 1512/// i = 0; 1513/// max = n < 1 ? 1 : n; 1514/// do { 1515/// p[i] = 0.0; 1516/// } while (++i != max); 1517/// 1518/// Canonical induction variables are necessary because the loop passes 1519/// are designed around them. The most obvious example of this is the 1520/// LoopInfo analysis, which doesn't remember trip count values. It 1521/// expects to be able to rediscover the trip count each time it is 1522/// needed, and it does this using a simple analysis that only succeeds if 1523/// the loop has a canonical induction variable. 1524/// 1525/// However, when it comes time to generate code, the maximum operation 1526/// can be quite costly, especially if it's inside of an outer loop. 1527/// 1528/// This function solves this problem by detecting this type of loop and 1529/// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting 1530/// the instructions for the maximum computation. 1531/// 1532ICmpInst *LSRInstance::OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse) { 1533 // Check that the loop matches the pattern we're looking for. 1534 if (Cond->getPredicate() != CmpInst::ICMP_EQ && 1535 Cond->getPredicate() != CmpInst::ICMP_NE) 1536 return Cond; 1537 1538 SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1)); 1539 if (!Sel || !Sel->hasOneUse()) return Cond; 1540 1541 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L); 1542 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1543 return Cond; 1544 const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1); 1545 1546 // Add one to the backedge-taken count to get the trip count. 1547 const SCEV *IterationCount = SE.getAddExpr(BackedgeTakenCount, One); 1548 if (IterationCount != SE.getSCEV(Sel)) return Cond; 1549 1550 // Check for a max calculation that matches the pattern. There's no check 1551 // for ICMP_ULE here because the comparison would be with zero, which 1552 // isn't interesting. 1553 CmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE; 1554 const SCEVNAryExpr *Max = 0; 1555 if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(BackedgeTakenCount)) { 1556 Pred = ICmpInst::ICMP_SLE; 1557 Max = S; 1558 } else if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(IterationCount)) { 1559 Pred = ICmpInst::ICMP_SLT; 1560 Max = S; 1561 } else if (const SCEVUMaxExpr *U = dyn_cast<SCEVUMaxExpr>(IterationCount)) { 1562 Pred = ICmpInst::ICMP_ULT; 1563 Max = U; 1564 } else { 1565 // No match; bail. 1566 return Cond; 1567 } 1568 1569 // To handle a max with more than two operands, this optimization would 1570 // require additional checking and setup. 1571 if (Max->getNumOperands() != 2) 1572 return Cond; 1573 1574 const SCEV *MaxLHS = Max->getOperand(0); 1575 const SCEV *MaxRHS = Max->getOperand(1); 1576 1577 // ScalarEvolution canonicalizes constants to the left. For < and >, look 1578 // for a comparison with 1. For <= and >=, a comparison with zero. 1579 if (!MaxLHS || 1580 (ICmpInst::isTrueWhenEqual(Pred) ? !MaxLHS->isZero() : (MaxLHS != One))) 1581 return Cond; 1582 1583 // Check the relevant induction variable for conformance to 1584 // the pattern. 1585 const SCEV *IV = SE.getSCEV(Cond->getOperand(0)); 1586 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV); 1587 if (!AR || !AR->isAffine() || 1588 AR->getStart() != One || 1589 AR->getStepRecurrence(SE) != One) 1590 return Cond; 1591 1592 assert(AR->getLoop() == L && 1593 "Loop condition operand is an addrec in a different loop!"); 1594 1595 // Check the right operand of the select, and remember it, as it will 1596 // be used in the new comparison instruction. 1597 Value *NewRHS = 0; 1598 if (ICmpInst::isTrueWhenEqual(Pred)) { 1599 // Look for n+1, and grab n. 1600 if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(1))) 1601 if (isa<ConstantInt>(BO->getOperand(1)) && 1602 cast<ConstantInt>(BO->getOperand(1))->isOne() && 1603 SE.getSCEV(BO->getOperand(0)) == MaxRHS) 1604 NewRHS = BO->getOperand(0); 1605 if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(2))) 1606 if (isa<ConstantInt>(BO->getOperand(1)) && 1607 cast<ConstantInt>(BO->getOperand(1))->isOne() && 1608 SE.getSCEV(BO->getOperand(0)) == MaxRHS) 1609 NewRHS = BO->getOperand(0); 1610 if (!NewRHS) 1611 return Cond; 1612 } else if (SE.getSCEV(Sel->getOperand(1)) == MaxRHS) 1613 NewRHS = Sel->getOperand(1); 1614 else if (SE.getSCEV(Sel->getOperand(2)) == MaxRHS) 1615 NewRHS = Sel->getOperand(2); 1616 else 1617 llvm_unreachable("Max doesn't match expected pattern!"); 1618 1619 // Determine the new comparison opcode. It may be signed or unsigned, 1620 // and the original comparison may be either equality or inequality. 1621 if (Cond->getPredicate() == CmpInst::ICMP_EQ) 1622 Pred = CmpInst::getInversePredicate(Pred); 1623 1624 // Ok, everything looks ok to change the condition into an SLT or SGE and 1625 // delete the max calculation. 1626 ICmpInst *NewCond = 1627 new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp"); 1628 1629 // Delete the max calculation instructions. 1630 Cond->replaceAllUsesWith(NewCond); 1631 CondUse->setUser(NewCond); 1632 Instruction *Cmp = cast<Instruction>(Sel->getOperand(0)); 1633 Cond->eraseFromParent(); 1634 Sel->eraseFromParent(); 1635 if (Cmp->use_empty()) 1636 Cmp->eraseFromParent(); 1637 return NewCond; 1638} 1639 1640/// OptimizeLoopTermCond - Change loop terminating condition to use the 1641/// postinc iv when possible. 1642void 1643LSRInstance::OptimizeLoopTermCond() { 1644 SmallPtrSet<Instruction *, 4> PostIncs; 1645 1646 BasicBlock *LatchBlock = L->getLoopLatch(); 1647 SmallVector<BasicBlock*, 8> ExitingBlocks; 1648 L->getExitingBlocks(ExitingBlocks); 1649 1650 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 1651 BasicBlock *ExitingBlock = ExitingBlocks[i]; 1652 1653 // Get the terminating condition for the loop if possible. If we 1654 // can, we want to change it to use a post-incremented version of its 1655 // induction variable, to allow coalescing the live ranges for the IV into 1656 // one register value. 1657 1658 BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 1659 if (!TermBr) 1660 continue; 1661 // FIXME: Overly conservative, termination condition could be an 'or' etc.. 1662 if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition())) 1663 continue; 1664 1665 // Search IVUsesByStride to find Cond's IVUse if there is one. 1666 IVStrideUse *CondUse = 0; 1667 ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition()); 1668 if (!FindIVUserForCond(Cond, CondUse)) 1669 continue; 1670 1671 // If the trip count is computed in terms of a max (due to ScalarEvolution 1672 // being unable to find a sufficient guard, for example), change the loop 1673 // comparison to use SLT or ULT instead of NE. 1674 // One consequence of doing this now is that it disrupts the count-down 1675 // optimization. That's not always a bad thing though, because in such 1676 // cases it may still be worthwhile to avoid a max. 1677 Cond = OptimizeMax(Cond, CondUse); 1678 1679 // If this exiting block dominates the latch block, it may also use 1680 // the post-inc value if it won't be shared with other uses. 1681 // Check for dominance. 1682 if (!DT.dominates(ExitingBlock, LatchBlock)) 1683 continue; 1684 1685 // Conservatively avoid trying to use the post-inc value in non-latch 1686 // exits if there may be pre-inc users in intervening blocks. 1687 if (LatchBlock != ExitingBlock) 1688 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) 1689 // Test if the use is reachable from the exiting block. This dominator 1690 // query is a conservative approximation of reachability. 1691 if (&*UI != CondUse && 1692 !DT.properlyDominates(UI->getUser()->getParent(), ExitingBlock)) { 1693 // Conservatively assume there may be reuse if the quotient of their 1694 // strides could be a legal scale. 1695 const SCEV *A = IU.getStride(*CondUse, L); 1696 const SCEV *B = IU.getStride(*UI, L); 1697 if (!A || !B) continue; 1698 if (SE.getTypeSizeInBits(A->getType()) != 1699 SE.getTypeSizeInBits(B->getType())) { 1700 if (SE.getTypeSizeInBits(A->getType()) > 1701 SE.getTypeSizeInBits(B->getType())) 1702 B = SE.getSignExtendExpr(B, A->getType()); 1703 else 1704 A = SE.getSignExtendExpr(A, B->getType()); 1705 } 1706 if (const SCEVConstant *D = 1707 dyn_cast_or_null<SCEVConstant>(getExactSDiv(B, A, SE))) { 1708 const ConstantInt *C = D->getValue(); 1709 // Stride of one or negative one can have reuse with non-addresses. 1710 if (C->isOne() || C->isAllOnesValue()) 1711 goto decline_post_inc; 1712 // Avoid weird situations. 1713 if (C->getValue().getMinSignedBits() >= 64 || 1714 C->getValue().isMinSignedValue()) 1715 goto decline_post_inc; 1716 // Without TLI, assume that any stride might be valid, and so any 1717 // use might be shared. 1718 if (!TLI) 1719 goto decline_post_inc; 1720 // Check for possible scaled-address reuse. 1721 const Type *AccessTy = getAccessType(UI->getUser()); 1722 TargetLowering::AddrMode AM; 1723 AM.Scale = C->getSExtValue(); 1724 if (TLI->isLegalAddressingMode(AM, AccessTy)) 1725 goto decline_post_inc; 1726 AM.Scale = -AM.Scale; 1727 if (TLI->isLegalAddressingMode(AM, AccessTy)) 1728 goto decline_post_inc; 1729 } 1730 } 1731 1732 DEBUG(dbgs() << " Change loop exiting icmp to use postinc iv: " 1733 << *Cond << '\n'); 1734 1735 // It's possible for the setcc instruction to be anywhere in the loop, and 1736 // possible for it to have multiple users. If it is not immediately before 1737 // the exiting block branch, move it. 1738 if (&*++BasicBlock::iterator(Cond) != TermBr) { 1739 if (Cond->hasOneUse()) { 1740 Cond->moveBefore(TermBr); 1741 } else { 1742 // Clone the terminating condition and insert into the loopend. 1743 ICmpInst *OldCond = Cond; 1744 Cond = cast<ICmpInst>(Cond->clone()); 1745 Cond->setName(L->getHeader()->getName() + ".termcond"); 1746 ExitingBlock->getInstList().insert(TermBr, Cond); 1747 1748 // Clone the IVUse, as the old use still exists! 1749 CondUse = &IU.AddUser(Cond, CondUse->getOperandValToReplace()); 1750 TermBr->replaceUsesOfWith(OldCond, Cond); 1751 } 1752 } 1753 1754 // If we get to here, we know that we can transform the setcc instruction to 1755 // use the post-incremented version of the IV, allowing us to coalesce the 1756 // live ranges for the IV correctly. 1757 CondUse->transformToPostInc(L); 1758 Changed = true; 1759 1760 PostIncs.insert(Cond); 1761 decline_post_inc:; 1762 } 1763 1764 // Determine an insertion point for the loop induction variable increment. It 1765 // must dominate all the post-inc comparisons we just set up, and it must 1766 // dominate the loop latch edge. 1767 IVIncInsertPos = L->getLoopLatch()->getTerminator(); 1768 for (SmallPtrSet<Instruction *, 4>::const_iterator I = PostIncs.begin(), 1769 E = PostIncs.end(); I != E; ++I) { 1770 BasicBlock *BB = 1771 DT.findNearestCommonDominator(IVIncInsertPos->getParent(), 1772 (*I)->getParent()); 1773 if (BB == (*I)->getParent()) 1774 IVIncInsertPos = *I; 1775 else if (BB != IVIncInsertPos->getParent()) 1776 IVIncInsertPos = BB->getTerminator(); 1777 } 1778} 1779 1780/// reconcileNewOffset - Determine if the given use can accomodate a fixup 1781/// at the given offset and other details. If so, update the use and 1782/// return true. 1783bool 1784LSRInstance::reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 1785 LSRUse::KindType Kind, const Type *AccessTy) { 1786 int64_t NewMinOffset = LU.MinOffset; 1787 int64_t NewMaxOffset = LU.MaxOffset; 1788 const Type *NewAccessTy = AccessTy; 1789 1790 // Check for a mismatched kind. It's tempting to collapse mismatched kinds to 1791 // something conservative, however this can pessimize in the case that one of 1792 // the uses will have all its uses outside the loop, for example. 1793 if (LU.Kind != Kind) 1794 return false; 1795 // Conservatively assume HasBaseReg is true for now. 1796 if (NewOffset < LU.MinOffset) { 1797 if (!isAlwaysFoldable(LU.MaxOffset - NewOffset, 0, HasBaseReg, 1798 Kind, AccessTy, TLI)) 1799 return false; 1800 NewMinOffset = NewOffset; 1801 } else if (NewOffset > LU.MaxOffset) { 1802 if (!isAlwaysFoldable(NewOffset - LU.MinOffset, 0, HasBaseReg, 1803 Kind, AccessTy, TLI)) 1804 return false; 1805 NewMaxOffset = NewOffset; 1806 } 1807 // Check for a mismatched access type, and fall back conservatively as needed. 1808 if (Kind == LSRUse::Address && AccessTy != LU.AccessTy) 1809 NewAccessTy = Type::getVoidTy(AccessTy->getContext()); 1810 1811 // Update the use. 1812 LU.MinOffset = NewMinOffset; 1813 LU.MaxOffset = NewMaxOffset; 1814 LU.AccessTy = NewAccessTy; 1815 if (NewOffset != LU.Offsets.back()) 1816 LU.Offsets.push_back(NewOffset); 1817 return true; 1818} 1819 1820/// getUse - Return an LSRUse index and an offset value for a fixup which 1821/// needs the given expression, with the given kind and optional access type. 1822/// Either reuse an existing use or create a new one, as needed. 1823std::pair<size_t, int64_t> 1824LSRInstance::getUse(const SCEV *&Expr, 1825 LSRUse::KindType Kind, const Type *AccessTy) { 1826 const SCEV *Copy = Expr; 1827 int64_t Offset = ExtractImmediate(Expr, SE); 1828 1829 // Basic uses can't accept any offset, for example. 1830 if (!isAlwaysFoldable(Offset, 0, /*HasBaseReg=*/true, Kind, AccessTy, TLI)) { 1831 Expr = Copy; 1832 Offset = 0; 1833 } 1834 1835 std::pair<UseMapTy::iterator, bool> P = 1836 UseMap.insert(std::make_pair(Expr, 0)); 1837 if (!P.second) { 1838 // A use already existed with this base. 1839 size_t LUIdx = P.first->second; 1840 LSRUse &LU = Uses[LUIdx]; 1841 if (reconcileNewOffset(LU, Offset, /*HasBaseReg=*/true, Kind, AccessTy)) 1842 // Reuse this use. 1843 return std::make_pair(LUIdx, Offset); 1844 } 1845 1846 // Create a new use. 1847 size_t LUIdx = Uses.size(); 1848 P.first->second = LUIdx; 1849 Uses.push_back(LSRUse(Kind, AccessTy)); 1850 LSRUse &LU = Uses[LUIdx]; 1851 1852 // We don't need to track redundant offsets, but we don't need to go out 1853 // of our way here to avoid them. 1854 if (LU.Offsets.empty() || Offset != LU.Offsets.back()) 1855 LU.Offsets.push_back(Offset); 1856 1857 LU.MinOffset = Offset; 1858 LU.MaxOffset = Offset; 1859 return std::make_pair(LUIdx, Offset); 1860} 1861 1862/// DeleteUse - Delete the given use from the Uses list. 1863void LSRInstance::DeleteUse(LSRUse &LU) { 1864 if (&LU != &Uses.back()) 1865 std::swap(LU, Uses.back()); 1866 Uses.pop_back(); 1867} 1868 1869/// FindUseWithFormula - Look for a use distinct from OrigLU which is has 1870/// a formula that has the same registers as the given formula. 1871LSRUse * 1872LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF, 1873 const LSRUse &OrigLU) { 1874 // Search all uses for the formula. This could be more clever. Ignore 1875 // ICmpZero uses because they may contain formulae generated by 1876 // GenerateICmpZeroScales, in which case adding fixup offsets may 1877 // be invalid. 1878 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 1879 LSRUse &LU = Uses[LUIdx]; 1880 if (&LU != &OrigLU && 1881 LU.Kind != LSRUse::ICmpZero && 1882 LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy && 1883 LU.HasFormulaWithSameRegs(OrigF)) { 1884 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 1885 E = LU.Formulae.end(); I != E; ++I) { 1886 const Formula &F = *I; 1887 if (F.BaseRegs == OrigF.BaseRegs && 1888 F.ScaledReg == OrigF.ScaledReg && 1889 F.AM.BaseGV == OrigF.AM.BaseGV && 1890 F.AM.Scale == OrigF.AM.Scale && 1891 LU.Kind) { 1892 if (F.AM.BaseOffs == 0) 1893 return &LU; 1894 break; 1895 } 1896 } 1897 } 1898 } 1899 1900 return 0; 1901} 1902 1903void LSRInstance::CollectInterestingTypesAndFactors() { 1904 SmallSetVector<const SCEV *, 4> Strides; 1905 1906 // Collect interesting types and strides. 1907 SmallVector<const SCEV *, 4> Worklist; 1908 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 1909 const SCEV *Expr = IU.getExpr(*UI); 1910 1911 // Collect interesting types. 1912 Types.insert(SE.getEffectiveSCEVType(Expr->getType())); 1913 1914 // Add strides for mentioned loops. 1915 Worklist.push_back(Expr); 1916 do { 1917 const SCEV *S = Worklist.pop_back_val(); 1918 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 1919 Strides.insert(AR->getStepRecurrence(SE)); 1920 Worklist.push_back(AR->getStart()); 1921 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 1922 Worklist.insert(Worklist.end(), Add->op_begin(), Add->op_end()); 1923 } 1924 } while (!Worklist.empty()); 1925 } 1926 1927 // Compute interesting factors from the set of interesting strides. 1928 for (SmallSetVector<const SCEV *, 4>::const_iterator 1929 I = Strides.begin(), E = Strides.end(); I != E; ++I) 1930 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter = 1931 next(I); NewStrideIter != E; ++NewStrideIter) { 1932 const SCEV *OldStride = *I; 1933 const SCEV *NewStride = *NewStrideIter; 1934 1935 if (SE.getTypeSizeInBits(OldStride->getType()) != 1936 SE.getTypeSizeInBits(NewStride->getType())) { 1937 if (SE.getTypeSizeInBits(OldStride->getType()) > 1938 SE.getTypeSizeInBits(NewStride->getType())) 1939 NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType()); 1940 else 1941 OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType()); 1942 } 1943 if (const SCEVConstant *Factor = 1944 dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride, 1945 SE, true))) { 1946 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 1947 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 1948 } else if (const SCEVConstant *Factor = 1949 dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride, 1950 NewStride, 1951 SE, true))) { 1952 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 1953 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 1954 } 1955 } 1956 1957 // If all uses use the same type, don't bother looking for truncation-based 1958 // reuse. 1959 if (Types.size() == 1) 1960 Types.clear(); 1961 1962 DEBUG(print_factors_and_types(dbgs())); 1963} 1964 1965void LSRInstance::CollectFixupsAndInitialFormulae() { 1966 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 1967 // Record the uses. 1968 LSRFixup &LF = getNewFixup(); 1969 LF.UserInst = UI->getUser(); 1970 LF.OperandValToReplace = UI->getOperandValToReplace(); 1971 LF.PostIncLoops = UI->getPostIncLoops(); 1972 1973 LSRUse::KindType Kind = LSRUse::Basic; 1974 const Type *AccessTy = 0; 1975 if (isAddressUse(LF.UserInst, LF.OperandValToReplace)) { 1976 Kind = LSRUse::Address; 1977 AccessTy = getAccessType(LF.UserInst); 1978 } 1979 1980 const SCEV *S = IU.getExpr(*UI); 1981 1982 // Equality (== and !=) ICmps are special. We can rewrite (i == N) as 1983 // (N - i == 0), and this allows (N - i) to be the expression that we work 1984 // with rather than just N or i, so we can consider the register 1985 // requirements for both N and i at the same time. Limiting this code to 1986 // equality icmps is not a problem because all interesting loops use 1987 // equality icmps, thanks to IndVarSimplify. 1988 if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst)) 1989 if (CI->isEquality()) { 1990 // Swap the operands if needed to put the OperandValToReplace on the 1991 // left, for consistency. 1992 Value *NV = CI->getOperand(1); 1993 if (NV == LF.OperandValToReplace) { 1994 CI->setOperand(1, CI->getOperand(0)); 1995 CI->setOperand(0, NV); 1996 NV = CI->getOperand(1); 1997 Changed = true; 1998 } 1999 2000 // x == y --> x - y == 0 2001 const SCEV *N = SE.getSCEV(NV); 2002 if (N->isLoopInvariant(L)) { 2003 Kind = LSRUse::ICmpZero; 2004 S = SE.getMinusSCEV(N, S); 2005 } 2006 2007 // -1 and the negations of all interesting strides (except the negation 2008 // of -1) are now also interesting. 2009 for (size_t i = 0, e = Factors.size(); i != e; ++i) 2010 if (Factors[i] != -1) 2011 Factors.insert(-(uint64_t)Factors[i]); 2012 Factors.insert(-1); 2013 } 2014 2015 // Set up the initial formula for this use. 2016 std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy); 2017 LF.LUIdx = P.first; 2018 LF.Offset = P.second; 2019 LSRUse &LU = Uses[LF.LUIdx]; 2020 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 2021 2022 // If this is the first use of this LSRUse, give it a formula. 2023 if (LU.Formulae.empty()) { 2024 InsertInitialFormula(S, LU, LF.LUIdx); 2025 CountRegisters(LU.Formulae.back(), LF.LUIdx); 2026 } 2027 } 2028 2029 DEBUG(print_fixups(dbgs())); 2030} 2031 2032/// InsertInitialFormula - Insert a formula for the given expression into 2033/// the given use, separating out loop-variant portions from loop-invariant 2034/// and loop-computable portions. 2035void 2036LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) { 2037 Formula F; 2038 F.InitialMatch(S, L, SE, DT); 2039 bool Inserted = InsertFormula(LU, LUIdx, F); 2040 assert(Inserted && "Initial formula already exists!"); (void)Inserted; 2041} 2042 2043/// InsertSupplementalFormula - Insert a simple single-register formula for 2044/// the given expression into the given use. 2045void 2046LSRInstance::InsertSupplementalFormula(const SCEV *S, 2047 LSRUse &LU, size_t LUIdx) { 2048 Formula F; 2049 F.BaseRegs.push_back(S); 2050 F.AM.HasBaseReg = true; 2051 bool Inserted = InsertFormula(LU, LUIdx, F); 2052 assert(Inserted && "Supplemental formula already exists!"); (void)Inserted; 2053} 2054 2055/// CountRegisters - Note which registers are used by the given formula, 2056/// updating RegUses. 2057void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) { 2058 if (F.ScaledReg) 2059 RegUses.CountRegister(F.ScaledReg, LUIdx); 2060 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 2061 E = F.BaseRegs.end(); I != E; ++I) 2062 RegUses.CountRegister(*I, LUIdx); 2063} 2064 2065/// InsertFormula - If the given formula has not yet been inserted, add it to 2066/// the list, and return true. Return false otherwise. 2067bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) { 2068 if (!LU.InsertFormula(F)) 2069 return false; 2070 2071 CountRegisters(F, LUIdx); 2072 return true; 2073} 2074 2075/// CollectLoopInvariantFixupsAndFormulae - Check for other uses of 2076/// loop-invariant values which we're tracking. These other uses will pin these 2077/// values in registers, making them less profitable for elimination. 2078/// TODO: This currently misses non-constant addrec step registers. 2079/// TODO: Should this give more weight to users inside the loop? 2080void 2081LSRInstance::CollectLoopInvariantFixupsAndFormulae() { 2082 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end()); 2083 SmallPtrSet<const SCEV *, 8> Inserted; 2084 2085 while (!Worklist.empty()) { 2086 const SCEV *S = Worklist.pop_back_val(); 2087 2088 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) 2089 Worklist.insert(Worklist.end(), N->op_begin(), N->op_end()); 2090 else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 2091 Worklist.push_back(C->getOperand()); 2092 else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 2093 Worklist.push_back(D->getLHS()); 2094 Worklist.push_back(D->getRHS()); 2095 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 2096 if (!Inserted.insert(U)) continue; 2097 const Value *V = U->getValue(); 2098 if (const Instruction *Inst = dyn_cast<Instruction>(V)) 2099 if (L->contains(Inst)) continue; 2100 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 2101 UI != UE; ++UI) { 2102 const Instruction *UserInst = dyn_cast<Instruction>(*UI); 2103 // Ignore non-instructions. 2104 if (!UserInst) 2105 continue; 2106 // Ignore instructions in other functions (as can happen with 2107 // Constants). 2108 if (UserInst->getParent()->getParent() != L->getHeader()->getParent()) 2109 continue; 2110 // Ignore instructions not dominated by the loop. 2111 const BasicBlock *UseBB = !isa<PHINode>(UserInst) ? 2112 UserInst->getParent() : 2113 cast<PHINode>(UserInst)->getIncomingBlock( 2114 PHINode::getIncomingValueNumForOperand(UI.getOperandNo())); 2115 if (!DT.dominates(L->getHeader(), UseBB)) 2116 continue; 2117 // Ignore uses which are part of other SCEV expressions, to avoid 2118 // analyzing them multiple times. 2119 if (SE.isSCEVable(UserInst->getType())) { 2120 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst)); 2121 // If the user is a no-op, look through to its uses. 2122 if (!isa<SCEVUnknown>(UserS)) 2123 continue; 2124 if (UserS == U) { 2125 Worklist.push_back( 2126 SE.getUnknown(const_cast<Instruction *>(UserInst))); 2127 continue; 2128 } 2129 } 2130 // Ignore icmp instructions which are already being analyzed. 2131 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UserInst)) { 2132 unsigned OtherIdx = !UI.getOperandNo(); 2133 Value *OtherOp = const_cast<Value *>(ICI->getOperand(OtherIdx)); 2134 if (SE.getSCEV(OtherOp)->hasComputableLoopEvolution(L)) 2135 continue; 2136 } 2137 2138 LSRFixup &LF = getNewFixup(); 2139 LF.UserInst = const_cast<Instruction *>(UserInst); 2140 LF.OperandValToReplace = UI.getUse(); 2141 std::pair<size_t, int64_t> P = getUse(S, LSRUse::Basic, 0); 2142 LF.LUIdx = P.first; 2143 LF.Offset = P.second; 2144 LSRUse &LU = Uses[LF.LUIdx]; 2145 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 2146 InsertSupplementalFormula(U, LU, LF.LUIdx); 2147 CountRegisters(LU.Formulae.back(), Uses.size() - 1); 2148 break; 2149 } 2150 } 2151 } 2152} 2153 2154/// CollectSubexprs - Split S into subexpressions which can be pulled out into 2155/// separate registers. If C is non-null, multiply each subexpression by C. 2156static void CollectSubexprs(const SCEV *S, const SCEVConstant *C, 2157 SmallVectorImpl<const SCEV *> &Ops, 2158 ScalarEvolution &SE) { 2159 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 2160 // Break out add operands. 2161 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 2162 I != E; ++I) 2163 CollectSubexprs(*I, C, Ops, SE); 2164 return; 2165 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 2166 // Split a non-zero base out of an addrec. 2167 if (!AR->getStart()->isZero()) { 2168 CollectSubexprs(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0), 2169 AR->getStepRecurrence(SE), 2170 AR->getLoop()), C, Ops, SE); 2171 CollectSubexprs(AR->getStart(), C, Ops, SE); 2172 return; 2173 } 2174 } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 2175 // Break (C * (a + b + c)) into C*a + C*b + C*c. 2176 if (Mul->getNumOperands() == 2) 2177 if (const SCEVConstant *Op0 = 2178 dyn_cast<SCEVConstant>(Mul->getOperand(0))) { 2179 CollectSubexprs(Mul->getOperand(1), 2180 C ? cast<SCEVConstant>(SE.getMulExpr(C, Op0)) : Op0, 2181 Ops, SE); 2182 return; 2183 } 2184 } 2185 2186 // Otherwise use the value itself. 2187 Ops.push_back(C ? SE.getMulExpr(C, S) : S); 2188} 2189 2190/// GenerateReassociations - Split out subexpressions from adds and the bases of 2191/// addrecs. 2192void LSRInstance::GenerateReassociations(LSRUse &LU, unsigned LUIdx, 2193 Formula Base, 2194 unsigned Depth) { 2195 // Arbitrarily cap recursion to protect compile time. 2196 if (Depth >= 3) return; 2197 2198 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) { 2199 const SCEV *BaseReg = Base.BaseRegs[i]; 2200 2201 SmallVector<const SCEV *, 8> AddOps; 2202 CollectSubexprs(BaseReg, 0, AddOps, SE); 2203 if (AddOps.size() == 1) continue; 2204 2205 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(), 2206 JE = AddOps.end(); J != JE; ++J) { 2207 // Don't pull a constant into a register if the constant could be folded 2208 // into an immediate field. 2209 if (isAlwaysFoldable(*J, LU.MinOffset, LU.MaxOffset, 2210 Base.getNumRegs() > 1, 2211 LU.Kind, LU.AccessTy, TLI, SE)) 2212 continue; 2213 2214 // Collect all operands except *J. 2215 SmallVector<const SCEV *, 8> InnerAddOps; 2216 for (SmallVectorImpl<const SCEV *>::const_iterator K = AddOps.begin(), 2217 KE = AddOps.end(); K != KE; ++K) 2218 if (K != J) 2219 InnerAddOps.push_back(*K); 2220 2221 // Don't leave just a constant behind in a register if the constant could 2222 // be folded into an immediate field. 2223 if (InnerAddOps.size() == 1 && 2224 isAlwaysFoldable(InnerAddOps[0], LU.MinOffset, LU.MaxOffset, 2225 Base.getNumRegs() > 1, 2226 LU.Kind, LU.AccessTy, TLI, SE)) 2227 continue; 2228 2229 const SCEV *InnerSum = SE.getAddExpr(InnerAddOps); 2230 if (InnerSum->isZero()) 2231 continue; 2232 Formula F = Base; 2233 F.BaseRegs[i] = InnerSum; 2234 F.BaseRegs.push_back(*J); 2235 if (InsertFormula(LU, LUIdx, F)) 2236 // If that formula hadn't been seen before, recurse to find more like 2237 // it. 2238 GenerateReassociations(LU, LUIdx, LU.Formulae.back(), Depth+1); 2239 } 2240 } 2241} 2242 2243/// GenerateCombinations - Generate a formula consisting of all of the 2244/// loop-dominating registers added into a single register. 2245void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx, 2246 Formula Base) { 2247 // This method is only interesting on a plurality of registers. 2248 if (Base.BaseRegs.size() <= 1) return; 2249 2250 Formula F = Base; 2251 F.BaseRegs.clear(); 2252 SmallVector<const SCEV *, 4> Ops; 2253 for (SmallVectorImpl<const SCEV *>::const_iterator 2254 I = Base.BaseRegs.begin(), E = Base.BaseRegs.end(); I != E; ++I) { 2255 const SCEV *BaseReg = *I; 2256 if (BaseReg->properlyDominates(L->getHeader(), &DT) && 2257 !BaseReg->hasComputableLoopEvolution(L)) 2258 Ops.push_back(BaseReg); 2259 else 2260 F.BaseRegs.push_back(BaseReg); 2261 } 2262 if (Ops.size() > 1) { 2263 const SCEV *Sum = SE.getAddExpr(Ops); 2264 // TODO: If Sum is zero, it probably means ScalarEvolution missed an 2265 // opportunity to fold something. For now, just ignore such cases 2266 // rather than proceed with zero in a register. 2267 if (!Sum->isZero()) { 2268 F.BaseRegs.push_back(Sum); 2269 (void)InsertFormula(LU, LUIdx, F); 2270 } 2271 } 2272} 2273 2274/// GenerateSymbolicOffsets - Generate reuse formulae using symbolic offsets. 2275void LSRInstance::GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, 2276 Formula Base) { 2277 // We can't add a symbolic offset if the address already contains one. 2278 if (Base.AM.BaseGV) return; 2279 2280 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) { 2281 const SCEV *G = Base.BaseRegs[i]; 2282 GlobalValue *GV = ExtractSymbol(G, SE); 2283 if (G->isZero() || !GV) 2284 continue; 2285 Formula F = Base; 2286 F.AM.BaseGV = GV; 2287 if (!isLegalUse(F.AM, LU.MinOffset, LU.MaxOffset, 2288 LU.Kind, LU.AccessTy, TLI)) 2289 continue; 2290 F.BaseRegs[i] = G; 2291 (void)InsertFormula(LU, LUIdx, F); 2292 } 2293} 2294 2295/// GenerateConstantOffsets - Generate reuse formulae using symbolic offsets. 2296void LSRInstance::GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, 2297 Formula Base) { 2298 // TODO: For now, just add the min and max offset, because it usually isn't 2299 // worthwhile looking at everything inbetween. 2300 SmallVector<int64_t, 4> Worklist; 2301 Worklist.push_back(LU.MinOffset); 2302 if (LU.MaxOffset != LU.MinOffset) 2303 Worklist.push_back(LU.MaxOffset); 2304 2305 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) { 2306 const SCEV *G = Base.BaseRegs[i]; 2307 2308 for (SmallVectorImpl<int64_t>::const_iterator I = Worklist.begin(), 2309 E = Worklist.end(); I != E; ++I) { 2310 Formula F = Base; 2311 F.AM.BaseOffs = (uint64_t)Base.AM.BaseOffs - *I; 2312 if (isLegalUse(F.AM, LU.MinOffset - *I, LU.MaxOffset - *I, 2313 LU.Kind, LU.AccessTy, TLI)) { 2314 F.BaseRegs[i] = SE.getAddExpr(G, SE.getConstant(G->getType(), *I)); 2315 2316 (void)InsertFormula(LU, LUIdx, F); 2317 } 2318 } 2319 2320 int64_t Imm = ExtractImmediate(G, SE); 2321 if (G->isZero() || Imm == 0) 2322 continue; 2323 Formula F = Base; 2324 F.AM.BaseOffs = (uint64_t)F.AM.BaseOffs + Imm; 2325 if (!isLegalUse(F.AM, LU.MinOffset, LU.MaxOffset, 2326 LU.Kind, LU.AccessTy, TLI)) 2327 continue; 2328 F.BaseRegs[i] = G; 2329 (void)InsertFormula(LU, LUIdx, F); 2330 } 2331} 2332 2333/// GenerateICmpZeroScales - For ICmpZero, check to see if we can scale up 2334/// the comparison. For example, x == y -> x*c == y*c. 2335void LSRInstance::GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, 2336 Formula Base) { 2337 if (LU.Kind != LSRUse::ICmpZero) return; 2338 2339 // Determine the integer type for the base formula. 2340 const Type *IntTy = Base.getType(); 2341 if (!IntTy) return; 2342 if (SE.getTypeSizeInBits(IntTy) > 64) return; 2343 2344 // Don't do this if there is more than one offset. 2345 if (LU.MinOffset != LU.MaxOffset) return; 2346 2347 assert(!Base.AM.BaseGV && "ICmpZero use is not legal!"); 2348 2349 // Check each interesting stride. 2350 for (SmallSetVector<int64_t, 8>::const_iterator 2351 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 2352 int64_t Factor = *I; 2353 Formula F = Base; 2354 2355 // Check that the multiplication doesn't overflow. 2356 if (F.AM.BaseOffs == INT64_MIN && Factor == -1) 2357 continue; 2358 F.AM.BaseOffs = (uint64_t)Base.AM.BaseOffs * Factor; 2359 if (F.AM.BaseOffs / Factor != Base.AM.BaseOffs) 2360 continue; 2361 2362 // Check that multiplying with the use offset doesn't overflow. 2363 int64_t Offset = LU.MinOffset; 2364 if (Offset == INT64_MIN && Factor == -1) 2365 continue; 2366 Offset = (uint64_t)Offset * Factor; 2367 if (Offset / Factor != LU.MinOffset) 2368 continue; 2369 2370 // Check that this scale is legal. 2371 if (!isLegalUse(F.AM, Offset, Offset, LU.Kind, LU.AccessTy, TLI)) 2372 continue; 2373 2374 // Compensate for the use having MinOffset built into it. 2375 F.AM.BaseOffs = (uint64_t)F.AM.BaseOffs + Offset - LU.MinOffset; 2376 2377 const SCEV *FactorS = SE.getConstant(IntTy, Factor); 2378 2379 // Check that multiplying with each base register doesn't overflow. 2380 for (size_t i = 0, e = F.BaseRegs.size(); i != e; ++i) { 2381 F.BaseRegs[i] = SE.getMulExpr(F.BaseRegs[i], FactorS); 2382 if (getExactSDiv(F.BaseRegs[i], FactorS, SE) != Base.BaseRegs[i]) 2383 goto next; 2384 } 2385 2386 // Check that multiplying with the scaled register doesn't overflow. 2387 if (F.ScaledReg) { 2388 F.ScaledReg = SE.getMulExpr(F.ScaledReg, FactorS); 2389 if (getExactSDiv(F.ScaledReg, FactorS, SE) != Base.ScaledReg) 2390 continue; 2391 } 2392 2393 // If we make it here and it's legal, add it. 2394 (void)InsertFormula(LU, LUIdx, F); 2395 next:; 2396 } 2397} 2398 2399/// GenerateScales - Generate stride factor reuse formulae by making use of 2400/// scaled-offset address modes, for example. 2401void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) { 2402 // Determine the integer type for the base formula. 2403 const Type *IntTy = Base.getType(); 2404 if (!IntTy) return; 2405 2406 // If this Formula already has a scaled register, we can't add another one. 2407 if (Base.AM.Scale != 0) return; 2408 2409 // Check each interesting stride. 2410 for (SmallSetVector<int64_t, 8>::const_iterator 2411 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 2412 int64_t Factor = *I; 2413 2414 Base.AM.Scale = Factor; 2415 Base.AM.HasBaseReg = Base.BaseRegs.size() > 1; 2416 // Check whether this scale is going to be legal. 2417 if (!isLegalUse(Base.AM, LU.MinOffset, LU.MaxOffset, 2418 LU.Kind, LU.AccessTy, TLI)) { 2419 // As a special-case, handle special out-of-loop Basic users specially. 2420 // TODO: Reconsider this special case. 2421 if (LU.Kind == LSRUse::Basic && 2422 isLegalUse(Base.AM, LU.MinOffset, LU.MaxOffset, 2423 LSRUse::Special, LU.AccessTy, TLI) && 2424 LU.AllFixupsOutsideLoop) 2425 LU.Kind = LSRUse::Special; 2426 else 2427 continue; 2428 } 2429 // For an ICmpZero, negating a solitary base register won't lead to 2430 // new solutions. 2431 if (LU.Kind == LSRUse::ICmpZero && 2432 !Base.AM.HasBaseReg && Base.AM.BaseOffs == 0 && !Base.AM.BaseGV) 2433 continue; 2434 // For each addrec base reg, apply the scale, if possible. 2435 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) 2436 if (const SCEVAddRecExpr *AR = 2437 dyn_cast<SCEVAddRecExpr>(Base.BaseRegs[i])) { 2438 const SCEV *FactorS = SE.getConstant(IntTy, Factor); 2439 if (FactorS->isZero()) 2440 continue; 2441 // Divide out the factor, ignoring high bits, since we'll be 2442 // scaling the value back up in the end. 2443 if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) { 2444 // TODO: This could be optimized to avoid all the copying. 2445 Formula F = Base; 2446 F.ScaledReg = Quotient; 2447 F.DeleteBaseReg(F.BaseRegs[i]); 2448 (void)InsertFormula(LU, LUIdx, F); 2449 } 2450 } 2451 } 2452} 2453 2454/// GenerateTruncates - Generate reuse formulae from different IV types. 2455void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) { 2456 // This requires TargetLowering to tell us which truncates are free. 2457 if (!TLI) return; 2458 2459 // Don't bother truncating symbolic values. 2460 if (Base.AM.BaseGV) return; 2461 2462 // Determine the integer type for the base formula. 2463 const Type *DstTy = Base.getType(); 2464 if (!DstTy) return; 2465 DstTy = SE.getEffectiveSCEVType(DstTy); 2466 2467 for (SmallSetVector<const Type *, 4>::const_iterator 2468 I = Types.begin(), E = Types.end(); I != E; ++I) { 2469 const Type *SrcTy = *I; 2470 if (SrcTy != DstTy && TLI->isTruncateFree(SrcTy, DstTy)) { 2471 Formula F = Base; 2472 2473 if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, *I); 2474 for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(), 2475 JE = F.BaseRegs.end(); J != JE; ++J) 2476 *J = SE.getAnyExtendExpr(*J, SrcTy); 2477 2478 // TODO: This assumes we've done basic processing on all uses and 2479 // have an idea what the register usage is. 2480 if (!F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses)) 2481 continue; 2482 2483 (void)InsertFormula(LU, LUIdx, F); 2484 } 2485 } 2486} 2487 2488namespace { 2489 2490/// WorkItem - Helper class for GenerateCrossUseConstantOffsets. It's used to 2491/// defer modifications so that the search phase doesn't have to worry about 2492/// the data structures moving underneath it. 2493struct WorkItem { 2494 size_t LUIdx; 2495 int64_t Imm; 2496 const SCEV *OrigReg; 2497 2498 WorkItem(size_t LI, int64_t I, const SCEV *R) 2499 : LUIdx(LI), Imm(I), OrigReg(R) {} 2500 2501 void print(raw_ostream &OS) const; 2502 void dump() const; 2503}; 2504 2505} 2506 2507void WorkItem::print(raw_ostream &OS) const { 2508 OS << "in formulae referencing " << *OrigReg << " in use " << LUIdx 2509 << " , add offset " << Imm; 2510} 2511 2512void WorkItem::dump() const { 2513 print(errs()); errs() << '\n'; 2514} 2515 2516/// GenerateCrossUseConstantOffsets - Look for registers which are a constant 2517/// distance apart and try to form reuse opportunities between them. 2518void LSRInstance::GenerateCrossUseConstantOffsets() { 2519 // Group the registers by their value without any added constant offset. 2520 typedef std::map<int64_t, const SCEV *> ImmMapTy; 2521 typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy; 2522 RegMapTy Map; 2523 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap; 2524 SmallVector<const SCEV *, 8> Sequence; 2525 for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); 2526 I != E; ++I) { 2527 const SCEV *Reg = *I; 2528 int64_t Imm = ExtractImmediate(Reg, SE); 2529 std::pair<RegMapTy::iterator, bool> Pair = 2530 Map.insert(std::make_pair(Reg, ImmMapTy())); 2531 if (Pair.second) 2532 Sequence.push_back(Reg); 2533 Pair.first->second.insert(std::make_pair(Imm, *I)); 2534 UsedByIndicesMap[Reg] |= RegUses.getUsedByIndices(*I); 2535 } 2536 2537 // Now examine each set of registers with the same base value. Build up 2538 // a list of work to do and do the work in a separate step so that we're 2539 // not adding formulae and register counts while we're searching. 2540 SmallVector<WorkItem, 32> WorkItems; 2541 SmallSet<std::pair<size_t, int64_t>, 32> UniqueItems; 2542 for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(), 2543 E = Sequence.end(); I != E; ++I) { 2544 const SCEV *Reg = *I; 2545 const ImmMapTy &Imms = Map.find(Reg)->second; 2546 2547 // It's not worthwhile looking for reuse if there's only one offset. 2548 if (Imms.size() == 1) 2549 continue; 2550 2551 DEBUG(dbgs() << "Generating cross-use offsets for " << *Reg << ':'; 2552 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); 2553 J != JE; ++J) 2554 dbgs() << ' ' << J->first; 2555 dbgs() << '\n'); 2556 2557 // Examine each offset. 2558 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); 2559 J != JE; ++J) { 2560 const SCEV *OrigReg = J->second; 2561 2562 int64_t JImm = J->first; 2563 const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(OrigReg); 2564 2565 if (!isa<SCEVConstant>(OrigReg) && 2566 UsedByIndicesMap[Reg].count() == 1) { 2567 DEBUG(dbgs() << "Skipping cross-use reuse for " << *OrigReg << '\n'); 2568 continue; 2569 } 2570 2571 // Conservatively examine offsets between this orig reg a few selected 2572 // other orig regs. 2573 ImmMapTy::const_iterator OtherImms[] = { 2574 Imms.begin(), prior(Imms.end()), 2575 Imms.upper_bound((Imms.begin()->first + prior(Imms.end())->first) / 2) 2576 }; 2577 for (size_t i = 0, e = array_lengthof(OtherImms); i != e; ++i) { 2578 ImmMapTy::const_iterator M = OtherImms[i]; 2579 if (M == J || M == JE) continue; 2580 2581 // Compute the difference between the two. 2582 int64_t Imm = (uint64_t)JImm - M->first; 2583 for (int LUIdx = UsedByIndices.find_first(); LUIdx != -1; 2584 LUIdx = UsedByIndices.find_next(LUIdx)) 2585 // Make a memo of this use, offset, and register tuple. 2586 if (UniqueItems.insert(std::make_pair(LUIdx, Imm))) 2587 WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg)); 2588 } 2589 } 2590 } 2591 2592 Map.clear(); 2593 Sequence.clear(); 2594 UsedByIndicesMap.clear(); 2595 UniqueItems.clear(); 2596 2597 // Now iterate through the worklist and add new formulae. 2598 for (SmallVectorImpl<WorkItem>::const_iterator I = WorkItems.begin(), 2599 E = WorkItems.end(); I != E; ++I) { 2600 const WorkItem &WI = *I; 2601 size_t LUIdx = WI.LUIdx; 2602 LSRUse &LU = Uses[LUIdx]; 2603 int64_t Imm = WI.Imm; 2604 const SCEV *OrigReg = WI.OrigReg; 2605 2606 const Type *IntTy = SE.getEffectiveSCEVType(OrigReg->getType()); 2607 const SCEV *NegImmS = SE.getSCEV(ConstantInt::get(IntTy, -(uint64_t)Imm)); 2608 unsigned BitWidth = SE.getTypeSizeInBits(IntTy); 2609 2610 // TODO: Use a more targeted data structure. 2611 for (size_t L = 0, LE = LU.Formulae.size(); L != LE; ++L) { 2612 const Formula &F = LU.Formulae[L]; 2613 // Use the immediate in the scaled register. 2614 if (F.ScaledReg == OrigReg) { 2615 int64_t Offs = (uint64_t)F.AM.BaseOffs + 2616 Imm * (uint64_t)F.AM.Scale; 2617 // Don't create 50 + reg(-50). 2618 if (F.referencesReg(SE.getSCEV( 2619 ConstantInt::get(IntTy, -(uint64_t)Offs)))) 2620 continue; 2621 Formula NewF = F; 2622 NewF.AM.BaseOffs = Offs; 2623 if (!isLegalUse(NewF.AM, LU.MinOffset, LU.MaxOffset, 2624 LU.Kind, LU.AccessTy, TLI)) 2625 continue; 2626 NewF.ScaledReg = SE.getAddExpr(NegImmS, NewF.ScaledReg); 2627 2628 // If the new scale is a constant in a register, and adding the constant 2629 // value to the immediate would produce a value closer to zero than the 2630 // immediate itself, then the formula isn't worthwhile. 2631 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(NewF.ScaledReg)) 2632 if (C->getValue()->getValue().isNegative() != 2633 (NewF.AM.BaseOffs < 0) && 2634 (C->getValue()->getValue().abs() * APInt(BitWidth, F.AM.Scale)) 2635 .ule(abs64(NewF.AM.BaseOffs))) 2636 continue; 2637 2638 // OK, looks good. 2639 (void)InsertFormula(LU, LUIdx, NewF); 2640 } else { 2641 // Use the immediate in a base register. 2642 for (size_t N = 0, NE = F.BaseRegs.size(); N != NE; ++N) { 2643 const SCEV *BaseReg = F.BaseRegs[N]; 2644 if (BaseReg != OrigReg) 2645 continue; 2646 Formula NewF = F; 2647 NewF.AM.BaseOffs = (uint64_t)NewF.AM.BaseOffs + Imm; 2648 if (!isLegalUse(NewF.AM, LU.MinOffset, LU.MaxOffset, 2649 LU.Kind, LU.AccessTy, TLI)) 2650 continue; 2651 NewF.BaseRegs[N] = SE.getAddExpr(NegImmS, BaseReg); 2652 2653 // If the new formula has a constant in a register, and adding the 2654 // constant value to the immediate would produce a value closer to 2655 // zero than the immediate itself, then the formula isn't worthwhile. 2656 for (SmallVectorImpl<const SCEV *>::const_iterator 2657 J = NewF.BaseRegs.begin(), JE = NewF.BaseRegs.end(); 2658 J != JE; ++J) 2659 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*J)) 2660 if ((C->getValue()->getValue() + NewF.AM.BaseOffs).abs().slt( 2661 abs64(NewF.AM.BaseOffs)) && 2662 (C->getValue()->getValue() + 2663 NewF.AM.BaseOffs).countTrailingZeros() >= 2664 CountTrailingZeros_64(NewF.AM.BaseOffs)) 2665 goto skip_formula; 2666 2667 // Ok, looks good. 2668 (void)InsertFormula(LU, LUIdx, NewF); 2669 break; 2670 skip_formula:; 2671 } 2672 } 2673 } 2674 } 2675} 2676 2677/// GenerateAllReuseFormulae - Generate formulae for each use. 2678void 2679LSRInstance::GenerateAllReuseFormulae() { 2680 // This is split into multiple loops so that hasRegsUsedByUsesOtherThan 2681 // queries are more precise. 2682 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2683 LSRUse &LU = Uses[LUIdx]; 2684 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2685 GenerateReassociations(LU, LUIdx, LU.Formulae[i]); 2686 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2687 GenerateCombinations(LU, LUIdx, LU.Formulae[i]); 2688 } 2689 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2690 LSRUse &LU = Uses[LUIdx]; 2691 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2692 GenerateSymbolicOffsets(LU, LUIdx, LU.Formulae[i]); 2693 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2694 GenerateConstantOffsets(LU, LUIdx, LU.Formulae[i]); 2695 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2696 GenerateICmpZeroScales(LU, LUIdx, LU.Formulae[i]); 2697 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2698 GenerateScales(LU, LUIdx, LU.Formulae[i]); 2699 } 2700 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2701 LSRUse &LU = Uses[LUIdx]; 2702 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2703 GenerateTruncates(LU, LUIdx, LU.Formulae[i]); 2704 } 2705 2706 GenerateCrossUseConstantOffsets(); 2707} 2708 2709/// If their are multiple formulae with the same set of registers used 2710/// by other uses, pick the best one and delete the others. 2711void LSRInstance::FilterOutUndesirableDedicatedRegisters() { 2712#ifndef NDEBUG 2713 bool ChangedFormulae = false; 2714#endif 2715 2716 // Collect the best formula for each unique set of shared registers. This 2717 // is reset for each use. 2718 typedef DenseMap<SmallVector<const SCEV *, 2>, size_t, UniquifierDenseMapInfo> 2719 BestFormulaeTy; 2720 BestFormulaeTy BestFormulae; 2721 2722 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2723 LSRUse &LU = Uses[LUIdx]; 2724 FormulaSorter Sorter(L, LU, SE, DT); 2725 DEBUG(dbgs() << "Filtering for use "; LU.print(dbgs()); dbgs() << '\n'); 2726 2727 bool Any = false; 2728 for (size_t FIdx = 0, NumForms = LU.Formulae.size(); 2729 FIdx != NumForms; ++FIdx) { 2730 Formula &F = LU.Formulae[FIdx]; 2731 2732 SmallVector<const SCEV *, 2> Key; 2733 for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(), 2734 JE = F.BaseRegs.end(); J != JE; ++J) { 2735 const SCEV *Reg = *J; 2736 if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx)) 2737 Key.push_back(Reg); 2738 } 2739 if (F.ScaledReg && 2740 RegUses.isRegUsedByUsesOtherThan(F.ScaledReg, LUIdx)) 2741 Key.push_back(F.ScaledReg); 2742 // Unstable sort by host order ok, because this is only used for 2743 // uniquifying. 2744 std::sort(Key.begin(), Key.end()); 2745 2746 std::pair<BestFormulaeTy::const_iterator, bool> P = 2747 BestFormulae.insert(std::make_pair(Key, FIdx)); 2748 if (!P.second) { 2749 Formula &Best = LU.Formulae[P.first->second]; 2750 if (Sorter.operator()(F, Best)) 2751 std::swap(F, Best); 2752 DEBUG(dbgs() << " Filtering out formula "; F.print(dbgs()); 2753 dbgs() << "\n" 2754 " in favor of formula "; Best.print(dbgs()); 2755 dbgs() << '\n'); 2756#ifndef NDEBUG 2757 ChangedFormulae = true; 2758#endif 2759 LU.DeleteFormula(F); 2760 --FIdx; 2761 --NumForms; 2762 Any = true; 2763 continue; 2764 } 2765 } 2766 2767 // Now that we've filtered out some formulae, recompute the Regs set. 2768 if (Any) 2769 LU.RecomputeRegs(LUIdx, RegUses); 2770 2771 // Reset this to prepare for the next use. 2772 BestFormulae.clear(); 2773 } 2774 2775 DEBUG(if (ChangedFormulae) { 2776 dbgs() << "\n" 2777 "After filtering out undesirable candidates:\n"; 2778 print_uses(dbgs()); 2779 }); 2780} 2781 2782// This is a rough guess that seems to work fairly well. 2783static const size_t ComplexityLimit = UINT16_MAX; 2784 2785/// EstimateSearchSpaceComplexity - Estimate the worst-case number of 2786/// solutions the solver might have to consider. It almost never considers 2787/// this many solutions because it prune the search space, but the pruning 2788/// isn't always sufficient. 2789size_t LSRInstance::EstimateSearchSpaceComplexity() const { 2790 uint32_t Power = 1; 2791 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 2792 E = Uses.end(); I != E; ++I) { 2793 size_t FSize = I->Formulae.size(); 2794 if (FSize >= ComplexityLimit) { 2795 Power = ComplexityLimit; 2796 break; 2797 } 2798 Power *= FSize; 2799 if (Power >= ComplexityLimit) 2800 break; 2801 } 2802 return Power; 2803} 2804 2805/// NarrowSearchSpaceUsingHeuristics - If there are an extraordinary number of 2806/// formulae to choose from, use some rough heuristics to prune down the number 2807/// of formulae. This keeps the main solver from taking an extraordinary amount 2808/// of time in some worst-case scenarios. 2809void LSRInstance::NarrowSearchSpaceUsingHeuristics() { 2810 if (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 2811 DEBUG(dbgs() << "The search space is too complex.\n"); 2812 2813 DEBUG(dbgs() << "Narrowing the search space by eliminating formulae " 2814 "which use a superset of registers used by other " 2815 "formulae.\n"); 2816 2817 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2818 LSRUse &LU = Uses[LUIdx]; 2819 bool Any = false; 2820 for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) { 2821 Formula &F = LU.Formulae[i]; 2822 // Look for a formula with a constant or GV in a register. If the use 2823 // also has a formula with that same value in an immediate field, 2824 // delete the one that uses a register. 2825 for (SmallVectorImpl<const SCEV *>::const_iterator 2826 I = F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) { 2827 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*I)) { 2828 Formula NewF = F; 2829 NewF.AM.BaseOffs += C->getValue()->getSExtValue(); 2830 NewF.BaseRegs.erase(NewF.BaseRegs.begin() + 2831 (I - F.BaseRegs.begin())); 2832 if (LU.HasFormulaWithSameRegs(NewF)) { 2833 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); dbgs() << '\n'); 2834 LU.DeleteFormula(F); 2835 --i; 2836 --e; 2837 Any = true; 2838 break; 2839 } 2840 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(*I)) { 2841 if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) 2842 if (!F.AM.BaseGV) { 2843 Formula NewF = F; 2844 NewF.AM.BaseGV = GV; 2845 NewF.BaseRegs.erase(NewF.BaseRegs.begin() + 2846 (I - F.BaseRegs.begin())); 2847 if (LU.HasFormulaWithSameRegs(NewF)) { 2848 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); 2849 dbgs() << '\n'); 2850 LU.DeleteFormula(F); 2851 --i; 2852 --e; 2853 Any = true; 2854 break; 2855 } 2856 } 2857 } 2858 } 2859 } 2860 if (Any) 2861 LU.RecomputeRegs(LUIdx, RegUses); 2862 } 2863 2864 DEBUG(dbgs() << "After pre-selection:\n"; 2865 print_uses(dbgs())); 2866 } 2867 2868 if (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 2869 DEBUG(dbgs() << "The search space is too complex.\n"); 2870 2871 DEBUG(dbgs() << "Narrowing the search space by assuming that uses " 2872 "separated by a constant offset will use the same " 2873 "registers.\n"); 2874 2875 // This is especially useful for unrolled loops. 2876 2877 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2878 LSRUse &LU = Uses[LUIdx]; 2879 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 2880 E = LU.Formulae.end(); I != E; ++I) { 2881 const Formula &F = *I; 2882 if (F.AM.BaseOffs != 0 && F.AM.Scale == 0) { 2883 if (LSRUse *LUThatHas = FindUseWithSimilarFormula(F, LU)) { 2884 if (reconcileNewOffset(*LUThatHas, F.AM.BaseOffs, 2885 /*HasBaseReg=*/false, 2886 LU.Kind, LU.AccessTy)) { 2887 DEBUG(dbgs() << " Deleting use "; LU.print(dbgs()); 2888 dbgs() << '\n'); 2889 2890 LUThatHas->AllFixupsOutsideLoop &= LU.AllFixupsOutsideLoop; 2891 2892 // Delete formulae from the new use which are no longer legal. 2893 bool Any = false; 2894 for (size_t i = 0, e = LUThatHas->Formulae.size(); i != e; ++i) { 2895 Formula &F = LUThatHas->Formulae[i]; 2896 if (!isLegalUse(F.AM, 2897 LUThatHas->MinOffset, LUThatHas->MaxOffset, 2898 LUThatHas->Kind, LUThatHas->AccessTy, TLI)) { 2899 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); 2900 dbgs() << '\n'); 2901 LUThatHas->DeleteFormula(F); 2902 --i; 2903 --e; 2904 Any = true; 2905 } 2906 } 2907 if (Any) 2908 LUThatHas->RecomputeRegs(LUThatHas - &Uses.front(), RegUses); 2909 2910 // Update the relocs to reference the new use. 2911 for (SmallVectorImpl<LSRFixup>::iterator I = Fixups.begin(), 2912 E = Fixups.end(); I != E; ++I) { 2913 LSRFixup &Fixup = *I; 2914 if (Fixup.LUIdx == LUIdx) { 2915 Fixup.LUIdx = LUThatHas - &Uses.front(); 2916 Fixup.Offset += F.AM.BaseOffs; 2917 DEBUG(errs() << "New fixup has offset " 2918 << Fixup.Offset << '\n'); 2919 } 2920 if (Fixup.LUIdx == NumUses-1) 2921 Fixup.LUIdx = LUIdx; 2922 } 2923 2924 // Delete the old use. 2925 DeleteUse(LU); 2926 --LUIdx; 2927 --NumUses; 2928 break; 2929 } 2930 } 2931 } 2932 } 2933 } 2934 2935 DEBUG(dbgs() << "After pre-selection:\n"; 2936 print_uses(dbgs())); 2937 } 2938 2939 // With all other options exhausted, loop until the system is simple 2940 // enough to handle. 2941 SmallPtrSet<const SCEV *, 4> Taken; 2942 while (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 2943 // Ok, we have too many of formulae on our hands to conveniently handle. 2944 // Use a rough heuristic to thin out the list. 2945 DEBUG(dbgs() << "The search space is too complex.\n"); 2946 2947 // Pick the register which is used by the most LSRUses, which is likely 2948 // to be a good reuse register candidate. 2949 const SCEV *Best = 0; 2950 unsigned BestNum = 0; 2951 for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); 2952 I != E; ++I) { 2953 const SCEV *Reg = *I; 2954 if (Taken.count(Reg)) 2955 continue; 2956 if (!Best) 2957 Best = Reg; 2958 else { 2959 unsigned Count = RegUses.getUsedByIndices(Reg).count(); 2960 if (Count > BestNum) { 2961 Best = Reg; 2962 BestNum = Count; 2963 } 2964 } 2965 } 2966 2967 DEBUG(dbgs() << "Narrowing the search space by assuming " << *Best 2968 << " will yield profitable reuse.\n"); 2969 Taken.insert(Best); 2970 2971 // In any use with formulae which references this register, delete formulae 2972 // which don't reference it. 2973 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2974 LSRUse &LU = Uses[LUIdx]; 2975 if (!LU.Regs.count(Best)) continue; 2976 2977 bool Any = false; 2978 for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) { 2979 Formula &F = LU.Formulae[i]; 2980 if (!F.referencesReg(Best)) { 2981 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); dbgs() << '\n'); 2982 LU.DeleteFormula(F); 2983 --e; 2984 --i; 2985 Any = true; 2986 assert(e != 0 && "Use has no formulae left! Is Regs inconsistent?"); 2987 continue; 2988 } 2989 } 2990 2991 if (Any) 2992 LU.RecomputeRegs(LUIdx, RegUses); 2993 } 2994 2995 DEBUG(dbgs() << "After pre-selection:\n"; 2996 print_uses(dbgs())); 2997 } 2998} 2999 3000/// SolveRecurse - This is the recursive solver. 3001void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution, 3002 Cost &SolutionCost, 3003 SmallVectorImpl<const Formula *> &Workspace, 3004 const Cost &CurCost, 3005 const SmallPtrSet<const SCEV *, 16> &CurRegs, 3006 DenseSet<const SCEV *> &VisitedRegs) const { 3007 // Some ideas: 3008 // - prune more: 3009 // - use more aggressive filtering 3010 // - sort the formula so that the most profitable solutions are found first 3011 // - sort the uses too 3012 // - search faster: 3013 // - don't compute a cost, and then compare. compare while computing a cost 3014 // and bail early. 3015 // - track register sets with SmallBitVector 3016 3017 const LSRUse &LU = Uses[Workspace.size()]; 3018 3019 // If this use references any register that's already a part of the 3020 // in-progress solution, consider it a requirement that a formula must 3021 // reference that register in order to be considered. This prunes out 3022 // unprofitable searching. 3023 SmallSetVector<const SCEV *, 4> ReqRegs; 3024 for (SmallPtrSet<const SCEV *, 16>::const_iterator I = CurRegs.begin(), 3025 E = CurRegs.end(); I != E; ++I) 3026 if (LU.Regs.count(*I)) 3027 ReqRegs.insert(*I); 3028 3029 bool AnySatisfiedReqRegs = false; 3030 SmallPtrSet<const SCEV *, 16> NewRegs; 3031 Cost NewCost; 3032retry: 3033 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 3034 E = LU.Formulae.end(); I != E; ++I) { 3035 const Formula &F = *I; 3036 3037 // Ignore formulae which do not use any of the required registers. 3038 for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(), 3039 JE = ReqRegs.end(); J != JE; ++J) { 3040 const SCEV *Reg = *J; 3041 if ((!F.ScaledReg || F.ScaledReg != Reg) && 3042 std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) == 3043 F.BaseRegs.end()) 3044 goto skip; 3045 } 3046 AnySatisfiedReqRegs = true; 3047 3048 // Evaluate the cost of the current formula. If it's already worse than 3049 // the current best, prune the search at that point. 3050 NewCost = CurCost; 3051 NewRegs = CurRegs; 3052 NewCost.RateFormula(F, NewRegs, VisitedRegs, L, LU.Offsets, SE, DT); 3053 if (NewCost < SolutionCost) { 3054 Workspace.push_back(&F); 3055 if (Workspace.size() != Uses.size()) { 3056 SolveRecurse(Solution, SolutionCost, Workspace, NewCost, 3057 NewRegs, VisitedRegs); 3058 if (F.getNumRegs() == 1 && Workspace.size() == 1) 3059 VisitedRegs.insert(F.ScaledReg ? F.ScaledReg : F.BaseRegs[0]); 3060 } else { 3061 DEBUG(dbgs() << "New best at "; NewCost.print(dbgs()); 3062 dbgs() << ". Regs:"; 3063 for (SmallPtrSet<const SCEV *, 16>::const_iterator 3064 I = NewRegs.begin(), E = NewRegs.end(); I != E; ++I) 3065 dbgs() << ' ' << **I; 3066 dbgs() << '\n'); 3067 3068 SolutionCost = NewCost; 3069 Solution = Workspace; 3070 } 3071 Workspace.pop_back(); 3072 } 3073 skip:; 3074 } 3075 3076 // If none of the formulae had all of the required registers, relax the 3077 // constraint so that we don't exclude all formulae. 3078 if (!AnySatisfiedReqRegs) { 3079 assert(!ReqRegs.empty() && "Solver failed even without required registers"); 3080 ReqRegs.clear(); 3081 goto retry; 3082 } 3083} 3084 3085/// Solve - Choose one formula from each use. Return the results in the given 3086/// Solution vector. 3087void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const { 3088 SmallVector<const Formula *, 8> Workspace; 3089 Cost SolutionCost; 3090 SolutionCost.Loose(); 3091 Cost CurCost; 3092 SmallPtrSet<const SCEV *, 16> CurRegs; 3093 DenseSet<const SCEV *> VisitedRegs; 3094 Workspace.reserve(Uses.size()); 3095 3096 // SolveRecurse does all the work. 3097 SolveRecurse(Solution, SolutionCost, Workspace, CurCost, 3098 CurRegs, VisitedRegs); 3099 3100 // Ok, we've now made all our decisions. 3101 DEBUG(dbgs() << "\n" 3102 "The chosen solution requires "; SolutionCost.print(dbgs()); 3103 dbgs() << ":\n"; 3104 for (size_t i = 0, e = Uses.size(); i != e; ++i) { 3105 dbgs() << " "; 3106 Uses[i].print(dbgs()); 3107 dbgs() << "\n" 3108 " "; 3109 Solution[i]->print(dbgs()); 3110 dbgs() << '\n'; 3111 }); 3112 3113 assert(Solution.size() == Uses.size() && "Malformed solution!"); 3114} 3115 3116/// HoistInsertPosition - Helper for AdjustInsertPositionForExpand. Climb up 3117/// the dominator tree far as we can go while still being dominated by the 3118/// input positions. This helps canonicalize the insert position, which 3119/// encourages sharing. 3120BasicBlock::iterator 3121LSRInstance::HoistInsertPosition(BasicBlock::iterator IP, 3122 const SmallVectorImpl<Instruction *> &Inputs) 3123 const { 3124 for (;;) { 3125 const Loop *IPLoop = LI.getLoopFor(IP->getParent()); 3126 unsigned IPLoopDepth = IPLoop ? IPLoop->getLoopDepth() : 0; 3127 3128 BasicBlock *IDom; 3129 for (DomTreeNode *Rung = DT.getNode(IP->getParent()); ; ) { 3130 if (!Rung) return IP; 3131 Rung = Rung->getIDom(); 3132 if (!Rung) return IP; 3133 IDom = Rung->getBlock(); 3134 3135 // Don't climb into a loop though. 3136 const Loop *IDomLoop = LI.getLoopFor(IDom); 3137 unsigned IDomDepth = IDomLoop ? IDomLoop->getLoopDepth() : 0; 3138 if (IDomDepth <= IPLoopDepth && 3139 (IDomDepth != IPLoopDepth || IDomLoop == IPLoop)) 3140 break; 3141 } 3142 3143 bool AllDominate = true; 3144 Instruction *BetterPos = 0; 3145 Instruction *Tentative = IDom->getTerminator(); 3146 for (SmallVectorImpl<Instruction *>::const_iterator I = Inputs.begin(), 3147 E = Inputs.end(); I != E; ++I) { 3148 Instruction *Inst = *I; 3149 if (Inst == Tentative || !DT.dominates(Inst, Tentative)) { 3150 AllDominate = false; 3151 break; 3152 } 3153 // Attempt to find an insert position in the middle of the block, 3154 // instead of at the end, so that it can be used for other expansions. 3155 if (IDom == Inst->getParent() && 3156 (!BetterPos || DT.dominates(BetterPos, Inst))) 3157 BetterPos = llvm::next(BasicBlock::iterator(Inst)); 3158 } 3159 if (!AllDominate) 3160 break; 3161 if (BetterPos) 3162 IP = BetterPos; 3163 else 3164 IP = Tentative; 3165 } 3166 3167 return IP; 3168} 3169 3170/// AdjustInsertPositionForExpand - Determine an input position which will be 3171/// dominated by the operands and which will dominate the result. 3172BasicBlock::iterator 3173LSRInstance::AdjustInsertPositionForExpand(BasicBlock::iterator IP, 3174 const LSRFixup &LF, 3175 const LSRUse &LU) const { 3176 // Collect some instructions which must be dominated by the 3177 // expanding replacement. These must be dominated by any operands that 3178 // will be required in the expansion. 3179 SmallVector<Instruction *, 4> Inputs; 3180 if (Instruction *I = dyn_cast<Instruction>(LF.OperandValToReplace)) 3181 Inputs.push_back(I); 3182 if (LU.Kind == LSRUse::ICmpZero) 3183 if (Instruction *I = 3184 dyn_cast<Instruction>(cast<ICmpInst>(LF.UserInst)->getOperand(1))) 3185 Inputs.push_back(I); 3186 if (LF.PostIncLoops.count(L)) { 3187 if (LF.isUseFullyOutsideLoop(L)) 3188 Inputs.push_back(L->getLoopLatch()->getTerminator()); 3189 else 3190 Inputs.push_back(IVIncInsertPos); 3191 } 3192 // The expansion must also be dominated by the increment positions of any 3193 // loops it for which it is using post-inc mode. 3194 for (PostIncLoopSet::const_iterator I = LF.PostIncLoops.begin(), 3195 E = LF.PostIncLoops.end(); I != E; ++I) { 3196 const Loop *PIL = *I; 3197 if (PIL == L) continue; 3198 3199 // Be dominated by the loop exit. 3200 SmallVector<BasicBlock *, 4> ExitingBlocks; 3201 PIL->getExitingBlocks(ExitingBlocks); 3202 if (!ExitingBlocks.empty()) { 3203 BasicBlock *BB = ExitingBlocks[0]; 3204 for (unsigned i = 1, e = ExitingBlocks.size(); i != e; ++i) 3205 BB = DT.findNearestCommonDominator(BB, ExitingBlocks[i]); 3206 Inputs.push_back(BB->getTerminator()); 3207 } 3208 } 3209 3210 // Then, climb up the immediate dominator tree as far as we can go while 3211 // still being dominated by the input positions. 3212 IP = HoistInsertPosition(IP, Inputs); 3213 3214 // Don't insert instructions before PHI nodes. 3215 while (isa<PHINode>(IP)) ++IP; 3216 3217 // Ignore debug intrinsics. 3218 while (isa<DbgInfoIntrinsic>(IP)) ++IP; 3219 3220 return IP; 3221} 3222 3223/// Expand - Emit instructions for the leading candidate expression for this 3224/// LSRUse (this is called "expanding"). 3225Value *LSRInstance::Expand(const LSRFixup &LF, 3226 const Formula &F, 3227 BasicBlock::iterator IP, 3228 SCEVExpander &Rewriter, 3229 SmallVectorImpl<WeakVH> &DeadInsts) const { 3230 const LSRUse &LU = Uses[LF.LUIdx]; 3231 3232 // Determine an input position which will be dominated by the operands and 3233 // which will dominate the result. 3234 IP = AdjustInsertPositionForExpand(IP, LF, LU); 3235 3236 // Inform the Rewriter if we have a post-increment use, so that it can 3237 // perform an advantageous expansion. 3238 Rewriter.setPostInc(LF.PostIncLoops); 3239 3240 // This is the type that the user actually needs. 3241 const Type *OpTy = LF.OperandValToReplace->getType(); 3242 // This will be the type that we'll initially expand to. 3243 const Type *Ty = F.getType(); 3244 if (!Ty) 3245 // No type known; just expand directly to the ultimate type. 3246 Ty = OpTy; 3247 else if (SE.getEffectiveSCEVType(Ty) == SE.getEffectiveSCEVType(OpTy)) 3248 // Expand directly to the ultimate type if it's the right size. 3249 Ty = OpTy; 3250 // This is the type to do integer arithmetic in. 3251 const Type *IntTy = SE.getEffectiveSCEVType(Ty); 3252 3253 // Build up a list of operands to add together to form the full base. 3254 SmallVector<const SCEV *, 8> Ops; 3255 3256 // Expand the BaseRegs portion. 3257 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 3258 E = F.BaseRegs.end(); I != E; ++I) { 3259 const SCEV *Reg = *I; 3260 assert(!Reg->isZero() && "Zero allocated in a base register!"); 3261 3262 // If we're expanding for a post-inc user, make the post-inc adjustment. 3263 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops); 3264 Reg = TransformForPostIncUse(Denormalize, Reg, 3265 LF.UserInst, LF.OperandValToReplace, 3266 Loops, SE, DT); 3267 3268 Ops.push_back(SE.getUnknown(Rewriter.expandCodeFor(Reg, 0, IP))); 3269 } 3270 3271 // Flush the operand list to suppress SCEVExpander hoisting. 3272 if (!Ops.empty()) { 3273 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 3274 Ops.clear(); 3275 Ops.push_back(SE.getUnknown(FullV)); 3276 } 3277 3278 // Expand the ScaledReg portion. 3279 Value *ICmpScaledV = 0; 3280 if (F.AM.Scale != 0) { 3281 const SCEV *ScaledS = F.ScaledReg; 3282 3283 // If we're expanding for a post-inc user, make the post-inc adjustment. 3284 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops); 3285 ScaledS = TransformForPostIncUse(Denormalize, ScaledS, 3286 LF.UserInst, LF.OperandValToReplace, 3287 Loops, SE, DT); 3288 3289 if (LU.Kind == LSRUse::ICmpZero) { 3290 // An interesting way of "folding" with an icmp is to use a negated 3291 // scale, which we'll implement by inserting it into the other operand 3292 // of the icmp. 3293 assert(F.AM.Scale == -1 && 3294 "The only scale supported by ICmpZero uses is -1!"); 3295 ICmpScaledV = Rewriter.expandCodeFor(ScaledS, 0, IP); 3296 } else { 3297 // Otherwise just expand the scaled register and an explicit scale, 3298 // which is expected to be matched as part of the address. 3299 ScaledS = SE.getUnknown(Rewriter.expandCodeFor(ScaledS, 0, IP)); 3300 ScaledS = SE.getMulExpr(ScaledS, 3301 SE.getConstant(ScaledS->getType(), F.AM.Scale)); 3302 Ops.push_back(ScaledS); 3303 3304 // Flush the operand list to suppress SCEVExpander hoisting. 3305 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 3306 Ops.clear(); 3307 Ops.push_back(SE.getUnknown(FullV)); 3308 } 3309 } 3310 3311 // Expand the GV portion. 3312 if (F.AM.BaseGV) { 3313 Ops.push_back(SE.getUnknown(F.AM.BaseGV)); 3314 3315 // Flush the operand list to suppress SCEVExpander hoisting. 3316 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 3317 Ops.clear(); 3318 Ops.push_back(SE.getUnknown(FullV)); 3319 } 3320 3321 // Expand the immediate portion. 3322 int64_t Offset = (uint64_t)F.AM.BaseOffs + LF.Offset; 3323 if (Offset != 0) { 3324 if (LU.Kind == LSRUse::ICmpZero) { 3325 // The other interesting way of "folding" with an ICmpZero is to use a 3326 // negated immediate. 3327 if (!ICmpScaledV) 3328 ICmpScaledV = ConstantInt::get(IntTy, -Offset); 3329 else { 3330 Ops.push_back(SE.getUnknown(ICmpScaledV)); 3331 ICmpScaledV = ConstantInt::get(IntTy, Offset); 3332 } 3333 } else { 3334 // Just add the immediate values. These again are expected to be matched 3335 // as part of the address. 3336 Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy, Offset))); 3337 } 3338 } 3339 3340 // Emit instructions summing all the operands. 3341 const SCEV *FullS = Ops.empty() ? 3342 SE.getConstant(IntTy, 0) : 3343 SE.getAddExpr(Ops); 3344 Value *FullV = Rewriter.expandCodeFor(FullS, Ty, IP); 3345 3346 // We're done expanding now, so reset the rewriter. 3347 Rewriter.clearPostInc(); 3348 3349 // An ICmpZero Formula represents an ICmp which we're handling as a 3350 // comparison against zero. Now that we've expanded an expression for that 3351 // form, update the ICmp's other operand. 3352 if (LU.Kind == LSRUse::ICmpZero) { 3353 ICmpInst *CI = cast<ICmpInst>(LF.UserInst); 3354 DeadInsts.push_back(CI->getOperand(1)); 3355 assert(!F.AM.BaseGV && "ICmp does not support folding a global value and " 3356 "a scale at the same time!"); 3357 if (F.AM.Scale == -1) { 3358 if (ICmpScaledV->getType() != OpTy) { 3359 Instruction *Cast = 3360 CastInst::Create(CastInst::getCastOpcode(ICmpScaledV, false, 3361 OpTy, false), 3362 ICmpScaledV, OpTy, "tmp", CI); 3363 ICmpScaledV = Cast; 3364 } 3365 CI->setOperand(1, ICmpScaledV); 3366 } else { 3367 assert(F.AM.Scale == 0 && 3368 "ICmp does not support folding a global value and " 3369 "a scale at the same time!"); 3370 Constant *C = ConstantInt::getSigned(SE.getEffectiveSCEVType(OpTy), 3371 -(uint64_t)Offset); 3372 if (C->getType() != OpTy) 3373 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 3374 OpTy, false), 3375 C, OpTy); 3376 3377 CI->setOperand(1, C); 3378 } 3379 } 3380 3381 return FullV; 3382} 3383 3384/// RewriteForPHI - Helper for Rewrite. PHI nodes are special because the use 3385/// of their operands effectively happens in their predecessor blocks, so the 3386/// expression may need to be expanded in multiple places. 3387void LSRInstance::RewriteForPHI(PHINode *PN, 3388 const LSRFixup &LF, 3389 const Formula &F, 3390 SCEVExpander &Rewriter, 3391 SmallVectorImpl<WeakVH> &DeadInsts, 3392 Pass *P) const { 3393 DenseMap<BasicBlock *, Value *> Inserted; 3394 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 3395 if (PN->getIncomingValue(i) == LF.OperandValToReplace) { 3396 BasicBlock *BB = PN->getIncomingBlock(i); 3397 3398 // If this is a critical edge, split the edge so that we do not insert 3399 // the code on all predecessor/successor paths. We do this unless this 3400 // is the canonical backedge for this loop, which complicates post-inc 3401 // users. 3402 if (e != 1 && BB->getTerminator()->getNumSuccessors() > 1 && 3403 !isa<IndirectBrInst>(BB->getTerminator()) && 3404 (PN->getParent() != L->getHeader() || !L->contains(BB))) { 3405 // Split the critical edge. 3406 BasicBlock *NewBB = SplitCriticalEdge(BB, PN->getParent(), P); 3407 3408 // If PN is outside of the loop and BB is in the loop, we want to 3409 // move the block to be immediately before the PHI block, not 3410 // immediately after BB. 3411 if (L->contains(BB) && !L->contains(PN)) 3412 NewBB->moveBefore(PN->getParent()); 3413 3414 // Splitting the edge can reduce the number of PHI entries we have. 3415 e = PN->getNumIncomingValues(); 3416 BB = NewBB; 3417 i = PN->getBasicBlockIndex(BB); 3418 } 3419 3420 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> Pair = 3421 Inserted.insert(std::make_pair(BB, static_cast<Value *>(0))); 3422 if (!Pair.second) 3423 PN->setIncomingValue(i, Pair.first->second); 3424 else { 3425 Value *FullV = Expand(LF, F, BB->getTerminator(), Rewriter, DeadInsts); 3426 3427 // If this is reuse-by-noop-cast, insert the noop cast. 3428 const Type *OpTy = LF.OperandValToReplace->getType(); 3429 if (FullV->getType() != OpTy) 3430 FullV = 3431 CastInst::Create(CastInst::getCastOpcode(FullV, false, 3432 OpTy, false), 3433 FullV, LF.OperandValToReplace->getType(), 3434 "tmp", BB->getTerminator()); 3435 3436 PN->setIncomingValue(i, FullV); 3437 Pair.first->second = FullV; 3438 } 3439 } 3440} 3441 3442/// Rewrite - Emit instructions for the leading candidate expression for this 3443/// LSRUse (this is called "expanding"), and update the UserInst to reference 3444/// the newly expanded value. 3445void LSRInstance::Rewrite(const LSRFixup &LF, 3446 const Formula &F, 3447 SCEVExpander &Rewriter, 3448 SmallVectorImpl<WeakVH> &DeadInsts, 3449 Pass *P) const { 3450 // First, find an insertion point that dominates UserInst. For PHI nodes, 3451 // find the nearest block which dominates all the relevant uses. 3452 if (PHINode *PN = dyn_cast<PHINode>(LF.UserInst)) { 3453 RewriteForPHI(PN, LF, F, Rewriter, DeadInsts, P); 3454 } else { 3455 Value *FullV = Expand(LF, F, LF.UserInst, Rewriter, DeadInsts); 3456 3457 // If this is reuse-by-noop-cast, insert the noop cast. 3458 const Type *OpTy = LF.OperandValToReplace->getType(); 3459 if (FullV->getType() != OpTy) { 3460 Instruction *Cast = 3461 CastInst::Create(CastInst::getCastOpcode(FullV, false, OpTy, false), 3462 FullV, OpTy, "tmp", LF.UserInst); 3463 FullV = Cast; 3464 } 3465 3466 // Update the user. ICmpZero is handled specially here (for now) because 3467 // Expand may have updated one of the operands of the icmp already, and 3468 // its new value may happen to be equal to LF.OperandValToReplace, in 3469 // which case doing replaceUsesOfWith leads to replacing both operands 3470 // with the same value. TODO: Reorganize this. 3471 if (Uses[LF.LUIdx].Kind == LSRUse::ICmpZero) 3472 LF.UserInst->setOperand(0, FullV); 3473 else 3474 LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV); 3475 } 3476 3477 DeadInsts.push_back(LF.OperandValToReplace); 3478} 3479 3480/// ImplementSolution - Rewrite all the fixup locations with new values, 3481/// following the chosen solution. 3482void 3483LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, 3484 Pass *P) { 3485 // Keep track of instructions we may have made dead, so that 3486 // we can remove them after we are done working. 3487 SmallVector<WeakVH, 16> DeadInsts; 3488 3489 SCEVExpander Rewriter(SE); 3490 Rewriter.disableCanonicalMode(); 3491 Rewriter.setIVIncInsertPos(L, IVIncInsertPos); 3492 3493 // Expand the new value definitions and update the users. 3494 for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), 3495 E = Fixups.end(); I != E; ++I) { 3496 const LSRFixup &Fixup = *I; 3497 3498 Rewrite(Fixup, *Solution[Fixup.LUIdx], Rewriter, DeadInsts, P); 3499 3500 Changed = true; 3501 } 3502 3503 // Clean up after ourselves. This must be done before deleting any 3504 // instructions. 3505 Rewriter.clear(); 3506 3507 Changed |= DeleteTriviallyDeadInstructions(DeadInsts); 3508} 3509 3510LSRInstance::LSRInstance(const TargetLowering *tli, Loop *l, Pass *P) 3511 : IU(P->getAnalysis<IVUsers>()), 3512 SE(P->getAnalysis<ScalarEvolution>()), 3513 DT(P->getAnalysis<DominatorTree>()), 3514 LI(P->getAnalysis<LoopInfo>()), 3515 TLI(tli), L(l), Changed(false), IVIncInsertPos(0) { 3516 3517 // If LoopSimplify form is not available, stay out of trouble. 3518 if (!L->isLoopSimplifyForm()) return; 3519 3520 // If there's no interesting work to be done, bail early. 3521 if (IU.empty()) return; 3522 3523 DEBUG(dbgs() << "\nLSR on loop "; 3524 WriteAsOperand(dbgs(), L->getHeader(), /*PrintType=*/false); 3525 dbgs() << ":\n"); 3526 3527 // First, perform some low-level loop optimizations. 3528 OptimizeShadowIV(); 3529 OptimizeLoopTermCond(); 3530 3531 // Start collecting data and preparing for the solver. 3532 CollectInterestingTypesAndFactors(); 3533 CollectFixupsAndInitialFormulae(); 3534 CollectLoopInvariantFixupsAndFormulae(); 3535 3536 DEBUG(dbgs() << "LSR found " << Uses.size() << " uses:\n"; 3537 print_uses(dbgs())); 3538 3539 // Now use the reuse data to generate a bunch of interesting ways 3540 // to formulate the values needed for the uses. 3541 GenerateAllReuseFormulae(); 3542 3543 DEBUG(dbgs() << "\n" 3544 "After generating reuse formulae:\n"; 3545 print_uses(dbgs())); 3546 3547 FilterOutUndesirableDedicatedRegisters(); 3548 NarrowSearchSpaceUsingHeuristics(); 3549 3550 SmallVector<const Formula *, 8> Solution; 3551 Solve(Solution); 3552 3553 // Release memory that is no longer needed. 3554 Factors.clear(); 3555 Types.clear(); 3556 RegUses.clear(); 3557 3558#ifndef NDEBUG 3559 // Formulae should be legal. 3560 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 3561 E = Uses.end(); I != E; ++I) { 3562 const LSRUse &LU = *I; 3563 for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), 3564 JE = LU.Formulae.end(); J != JE; ++J) 3565 assert(isLegalUse(J->AM, LU.MinOffset, LU.MaxOffset, 3566 LU.Kind, LU.AccessTy, TLI) && 3567 "Illegal formula generated!"); 3568 }; 3569#endif 3570 3571 // Now that we've decided what we want, make it so. 3572 ImplementSolution(Solution, P); 3573} 3574 3575void LSRInstance::print_factors_and_types(raw_ostream &OS) const { 3576 if (Factors.empty() && Types.empty()) return; 3577 3578 OS << "LSR has identified the following interesting factors and types: "; 3579 bool First = true; 3580 3581 for (SmallSetVector<int64_t, 8>::const_iterator 3582 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 3583 if (!First) OS << ", "; 3584 First = false; 3585 OS << '*' << *I; 3586 } 3587 3588 for (SmallSetVector<const Type *, 4>::const_iterator 3589 I = Types.begin(), E = Types.end(); I != E; ++I) { 3590 if (!First) OS << ", "; 3591 First = false; 3592 OS << '(' << **I << ')'; 3593 } 3594 OS << '\n'; 3595} 3596 3597void LSRInstance::print_fixups(raw_ostream &OS) const { 3598 OS << "LSR is examining the following fixup sites:\n"; 3599 for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), 3600 E = Fixups.end(); I != E; ++I) { 3601 dbgs() << " "; 3602 I->print(OS); 3603 OS << '\n'; 3604 } 3605} 3606 3607void LSRInstance::print_uses(raw_ostream &OS) const { 3608 OS << "LSR is examining the following uses:\n"; 3609 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 3610 E = Uses.end(); I != E; ++I) { 3611 const LSRUse &LU = *I; 3612 dbgs() << " "; 3613 LU.print(OS); 3614 OS << '\n'; 3615 for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), 3616 JE = LU.Formulae.end(); J != JE; ++J) { 3617 OS << " "; 3618 J->print(OS); 3619 OS << '\n'; 3620 } 3621 } 3622} 3623 3624void LSRInstance::print(raw_ostream &OS) const { 3625 print_factors_and_types(OS); 3626 print_fixups(OS); 3627 print_uses(OS); 3628} 3629 3630void LSRInstance::dump() const { 3631 print(errs()); errs() << '\n'; 3632} 3633 3634namespace { 3635 3636class LoopStrengthReduce : public LoopPass { 3637 /// TLI - Keep a pointer of a TargetLowering to consult for determining 3638 /// transformation profitability. 3639 const TargetLowering *const TLI; 3640 3641public: 3642 static char ID; // Pass ID, replacement for typeid 3643 explicit LoopStrengthReduce(const TargetLowering *tli = 0); 3644 3645private: 3646 bool runOnLoop(Loop *L, LPPassManager &LPM); 3647 void getAnalysisUsage(AnalysisUsage &AU) const; 3648}; 3649 3650} 3651 3652char LoopStrengthReduce::ID = 0; 3653static RegisterPass<LoopStrengthReduce> 3654X("loop-reduce", "Loop Strength Reduction"); 3655 3656Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) { 3657 return new LoopStrengthReduce(TLI); 3658} 3659 3660LoopStrengthReduce::LoopStrengthReduce(const TargetLowering *tli) 3661 : LoopPass(&ID), TLI(tli) {} 3662 3663void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { 3664 // We split critical edges, so we change the CFG. However, we do update 3665 // many analyses if they are around. 3666 AU.addPreservedID(LoopSimplifyID); 3667 AU.addPreserved("domfrontier"); 3668 3669 AU.addRequired<LoopInfo>(); 3670 AU.addPreserved<LoopInfo>(); 3671 AU.addRequiredID(LoopSimplifyID); 3672 AU.addRequired<DominatorTree>(); 3673 AU.addPreserved<DominatorTree>(); 3674 AU.addRequired<ScalarEvolution>(); 3675 AU.addPreserved<ScalarEvolution>(); 3676 AU.addRequired<IVUsers>(); 3677 AU.addPreserved<IVUsers>(); 3678} 3679 3680bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { 3681 bool Changed = false; 3682 3683 // Run the main LSR transformation. 3684 Changed |= LSRInstance(TLI, L, this).getChanged(); 3685 3686 // At this point, it is worth checking to see if any recurrence PHIs are also 3687 // dead, so that we can remove them as well. 3688 Changed |= DeleteDeadPHIs(L->getHeader()); 3689 3690 return Changed; 3691} 3692