LoopStrengthReduce.cpp revision 402d43529c18d662d1964d70dbf55bc135a8b473
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 // Stride of one or negative one can have reuse with non-addresses. 1709 if (D->getValue()->isOne() || 1710 D->getValue()->isAllOnesValue()) 1711 goto decline_post_inc; 1712 // Avoid weird situations. 1713 if (D->getValue()->getValue().getMinSignedBits() >= 64 || 1714 D->getValue()->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 = D->getValue()->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 1780bool 1781LSRInstance::reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg, 1782 LSRUse::KindType Kind, const Type *AccessTy) { 1783 int64_t NewMinOffset = LU.MinOffset; 1784 int64_t NewMaxOffset = LU.MaxOffset; 1785 const Type *NewAccessTy = AccessTy; 1786 1787 // Check for a mismatched kind. It's tempting to collapse mismatched kinds to 1788 // something conservative, however this can pessimize in the case that one of 1789 // the uses will have all its uses outside the loop, for example. 1790 if (LU.Kind != Kind) 1791 return false; 1792 // Conservatively assume HasBaseReg is true for now. 1793 if (NewOffset < LU.MinOffset) { 1794 if (!isAlwaysFoldable(LU.MaxOffset - NewOffset, 0, HasBaseReg, 1795 Kind, AccessTy, TLI)) 1796 return false; 1797 NewMinOffset = NewOffset; 1798 } else if (NewOffset > LU.MaxOffset) { 1799 if (!isAlwaysFoldable(NewOffset - LU.MinOffset, 0, HasBaseReg, 1800 Kind, AccessTy, TLI)) 1801 return false; 1802 NewMaxOffset = NewOffset; 1803 } 1804 // Check for a mismatched access type, and fall back conservatively as needed. 1805 if (Kind == LSRUse::Address && AccessTy != LU.AccessTy) 1806 NewAccessTy = Type::getVoidTy(AccessTy->getContext()); 1807 1808 // Update the use. 1809 LU.MinOffset = NewMinOffset; 1810 LU.MaxOffset = NewMaxOffset; 1811 LU.AccessTy = NewAccessTy; 1812 if (NewOffset != LU.Offsets.back()) 1813 LU.Offsets.push_back(NewOffset); 1814 return true; 1815} 1816 1817/// getUse - Return an LSRUse index and an offset value for a fixup which 1818/// needs the given expression, with the given kind and optional access type. 1819/// Either reuse an existing use or create a new one, as needed. 1820std::pair<size_t, int64_t> 1821LSRInstance::getUse(const SCEV *&Expr, 1822 LSRUse::KindType Kind, const Type *AccessTy) { 1823 const SCEV *Copy = Expr; 1824 int64_t Offset = ExtractImmediate(Expr, SE); 1825 1826 // Basic uses can't accept any offset, for example. 1827 if (!isAlwaysFoldable(Offset, 0, /*HasBaseReg=*/true, Kind, AccessTy, TLI)) { 1828 Expr = Copy; 1829 Offset = 0; 1830 } 1831 1832 std::pair<UseMapTy::iterator, bool> P = 1833 UseMap.insert(std::make_pair(Expr, 0)); 1834 if (!P.second) { 1835 // A use already existed with this base. 1836 size_t LUIdx = P.first->second; 1837 LSRUse &LU = Uses[LUIdx]; 1838 if (reconcileNewOffset(LU, Offset, /*HasBaseReg=*/true, Kind, AccessTy)) 1839 // Reuse this use. 1840 return std::make_pair(LUIdx, Offset); 1841 } 1842 1843 // Create a new use. 1844 size_t LUIdx = Uses.size(); 1845 P.first->second = LUIdx; 1846 Uses.push_back(LSRUse(Kind, AccessTy)); 1847 LSRUse &LU = Uses[LUIdx]; 1848 1849 // We don't need to track redundant offsets, but we don't need to go out 1850 // of our way here to avoid them. 1851 if (LU.Offsets.empty() || Offset != LU.Offsets.back()) 1852 LU.Offsets.push_back(Offset); 1853 1854 LU.MinOffset = Offset; 1855 LU.MaxOffset = Offset; 1856 return std::make_pair(LUIdx, Offset); 1857} 1858 1859/// DeleteUse - Delete the given use from the Uses list. 1860void LSRInstance::DeleteUse(LSRUse &LU) { 1861 if (&LU != &Uses.back()) 1862 std::swap(LU, Uses.back()); 1863 Uses.pop_back(); 1864} 1865 1866/// FindUseWithFormula - Look for a use distinct from OrigLU which is has 1867/// a formula that has the same registers as the given formula. 1868LSRUse * 1869LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF, 1870 const LSRUse &OrigLU) { 1871 // Search all uses for the formula. This could be more clever. Ignore 1872 // ICmpZero uses because they may contain formulae generated by 1873 // GenerateICmpZeroScales, in which case adding fixup offsets may 1874 // be invalid. 1875 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 1876 LSRUse &LU = Uses[LUIdx]; 1877 if (&LU != &OrigLU && 1878 LU.Kind != LSRUse::ICmpZero && 1879 LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy && 1880 LU.HasFormulaWithSameRegs(OrigF)) { 1881 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 1882 E = LU.Formulae.end(); I != E; ++I) { 1883 const Formula &F = *I; 1884 if (F.BaseRegs == OrigF.BaseRegs && 1885 F.ScaledReg == OrigF.ScaledReg && 1886 F.AM.BaseGV == OrigF.AM.BaseGV && 1887 F.AM.Scale == OrigF.AM.Scale && 1888 LU.Kind) { 1889 if (F.AM.BaseOffs == 0) 1890 return &LU; 1891 break; 1892 } 1893 } 1894 } 1895 } 1896 1897 return 0; 1898} 1899 1900void LSRInstance::CollectInterestingTypesAndFactors() { 1901 SmallSetVector<const SCEV *, 4> Strides; 1902 1903 // Collect interesting types and strides. 1904 SmallVector<const SCEV *, 4> Worklist; 1905 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 1906 const SCEV *Expr = IU.getExpr(*UI); 1907 1908 // Collect interesting types. 1909 Types.insert(SE.getEffectiveSCEVType(Expr->getType())); 1910 1911 // Add strides for mentioned loops. 1912 Worklist.push_back(Expr); 1913 do { 1914 const SCEV *S = Worklist.pop_back_val(); 1915 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 1916 Strides.insert(AR->getStepRecurrence(SE)); 1917 Worklist.push_back(AR->getStart()); 1918 } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 1919 Worklist.insert(Worklist.end(), Add->op_begin(), Add->op_end()); 1920 } 1921 } while (!Worklist.empty()); 1922 } 1923 1924 // Compute interesting factors from the set of interesting strides. 1925 for (SmallSetVector<const SCEV *, 4>::const_iterator 1926 I = Strides.begin(), E = Strides.end(); I != E; ++I) 1927 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter = 1928 next(I); NewStrideIter != E; ++NewStrideIter) { 1929 const SCEV *OldStride = *I; 1930 const SCEV *NewStride = *NewStrideIter; 1931 1932 if (SE.getTypeSizeInBits(OldStride->getType()) != 1933 SE.getTypeSizeInBits(NewStride->getType())) { 1934 if (SE.getTypeSizeInBits(OldStride->getType()) > 1935 SE.getTypeSizeInBits(NewStride->getType())) 1936 NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType()); 1937 else 1938 OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType()); 1939 } 1940 if (const SCEVConstant *Factor = 1941 dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride, 1942 SE, true))) { 1943 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 1944 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 1945 } else if (const SCEVConstant *Factor = 1946 dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride, 1947 NewStride, 1948 SE, true))) { 1949 if (Factor->getValue()->getValue().getMinSignedBits() <= 64) 1950 Factors.insert(Factor->getValue()->getValue().getSExtValue()); 1951 } 1952 } 1953 1954 // If all uses use the same type, don't bother looking for truncation-based 1955 // reuse. 1956 if (Types.size() == 1) 1957 Types.clear(); 1958 1959 DEBUG(print_factors_and_types(dbgs())); 1960} 1961 1962void LSRInstance::CollectFixupsAndInitialFormulae() { 1963 for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) { 1964 // Record the uses. 1965 LSRFixup &LF = getNewFixup(); 1966 LF.UserInst = UI->getUser(); 1967 LF.OperandValToReplace = UI->getOperandValToReplace(); 1968 LF.PostIncLoops = UI->getPostIncLoops(); 1969 1970 LSRUse::KindType Kind = LSRUse::Basic; 1971 const Type *AccessTy = 0; 1972 if (isAddressUse(LF.UserInst, LF.OperandValToReplace)) { 1973 Kind = LSRUse::Address; 1974 AccessTy = getAccessType(LF.UserInst); 1975 } 1976 1977 const SCEV *S = IU.getExpr(*UI); 1978 1979 // Equality (== and !=) ICmps are special. We can rewrite (i == N) as 1980 // (N - i == 0), and this allows (N - i) to be the expression that we work 1981 // with rather than just N or i, so we can consider the register 1982 // requirements for both N and i at the same time. Limiting this code to 1983 // equality icmps is not a problem because all interesting loops use 1984 // equality icmps, thanks to IndVarSimplify. 1985 if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst)) 1986 if (CI->isEquality()) { 1987 // Swap the operands if needed to put the OperandValToReplace on the 1988 // left, for consistency. 1989 Value *NV = CI->getOperand(1); 1990 if (NV == LF.OperandValToReplace) { 1991 CI->setOperand(1, CI->getOperand(0)); 1992 CI->setOperand(0, NV); 1993 NV = CI->getOperand(1); 1994 Changed = true; 1995 } 1996 1997 // x == y --> x - y == 0 1998 const SCEV *N = SE.getSCEV(NV); 1999 if (N->isLoopInvariant(L)) { 2000 Kind = LSRUse::ICmpZero; 2001 S = SE.getMinusSCEV(N, S); 2002 } 2003 2004 // -1 and the negations of all interesting strides (except the negation 2005 // of -1) are now also interesting. 2006 for (size_t i = 0, e = Factors.size(); i != e; ++i) 2007 if (Factors[i] != -1) 2008 Factors.insert(-(uint64_t)Factors[i]); 2009 Factors.insert(-1); 2010 } 2011 2012 // Set up the initial formula for this use. 2013 std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy); 2014 LF.LUIdx = P.first; 2015 LF.Offset = P.second; 2016 LSRUse &LU = Uses[LF.LUIdx]; 2017 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 2018 2019 // If this is the first use of this LSRUse, give it a formula. 2020 if (LU.Formulae.empty()) { 2021 InsertInitialFormula(S, LU, LF.LUIdx); 2022 CountRegisters(LU.Formulae.back(), LF.LUIdx); 2023 } 2024 } 2025 2026 DEBUG(print_fixups(dbgs())); 2027} 2028 2029void 2030LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) { 2031 Formula F; 2032 F.InitialMatch(S, L, SE, DT); 2033 bool Inserted = InsertFormula(LU, LUIdx, F); 2034 assert(Inserted && "Initial formula already exists!"); (void)Inserted; 2035} 2036 2037void 2038LSRInstance::InsertSupplementalFormula(const SCEV *S, 2039 LSRUse &LU, size_t LUIdx) { 2040 Formula F; 2041 F.BaseRegs.push_back(S); 2042 F.AM.HasBaseReg = true; 2043 bool Inserted = InsertFormula(LU, LUIdx, F); 2044 assert(Inserted && "Supplemental formula already exists!"); (void)Inserted; 2045} 2046 2047/// CountRegisters - Note which registers are used by the given formula, 2048/// updating RegUses. 2049void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) { 2050 if (F.ScaledReg) 2051 RegUses.CountRegister(F.ScaledReg, LUIdx); 2052 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 2053 E = F.BaseRegs.end(); I != E; ++I) 2054 RegUses.CountRegister(*I, LUIdx); 2055} 2056 2057/// InsertFormula - If the given formula has not yet been inserted, add it to 2058/// the list, and return true. Return false otherwise. 2059bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) { 2060 if (!LU.InsertFormula(F)) 2061 return false; 2062 2063 CountRegisters(F, LUIdx); 2064 return true; 2065} 2066 2067/// CollectLoopInvariantFixupsAndFormulae - Check for other uses of 2068/// loop-invariant values which we're tracking. These other uses will pin these 2069/// values in registers, making them less profitable for elimination. 2070/// TODO: This currently misses non-constant addrec step registers. 2071/// TODO: Should this give more weight to users inside the loop? 2072void 2073LSRInstance::CollectLoopInvariantFixupsAndFormulae() { 2074 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end()); 2075 SmallPtrSet<const SCEV *, 8> Inserted; 2076 2077 while (!Worklist.empty()) { 2078 const SCEV *S = Worklist.pop_back_val(); 2079 2080 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) 2081 Worklist.insert(Worklist.end(), N->op_begin(), N->op_end()); 2082 else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) 2083 Worklist.push_back(C->getOperand()); 2084 else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) { 2085 Worklist.push_back(D->getLHS()); 2086 Worklist.push_back(D->getRHS()); 2087 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 2088 if (!Inserted.insert(U)) continue; 2089 const Value *V = U->getValue(); 2090 if (const Instruction *Inst = dyn_cast<Instruction>(V)) 2091 if (L->contains(Inst)) continue; 2092 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 2093 UI != UE; ++UI) { 2094 const Instruction *UserInst = dyn_cast<Instruction>(*UI); 2095 // Ignore non-instructions. 2096 if (!UserInst) 2097 continue; 2098 // Ignore instructions in other functions (as can happen with 2099 // Constants). 2100 if (UserInst->getParent()->getParent() != L->getHeader()->getParent()) 2101 continue; 2102 // Ignore instructions not dominated by the loop. 2103 const BasicBlock *UseBB = !isa<PHINode>(UserInst) ? 2104 UserInst->getParent() : 2105 cast<PHINode>(UserInst)->getIncomingBlock( 2106 PHINode::getIncomingValueNumForOperand(UI.getOperandNo())); 2107 if (!DT.dominates(L->getHeader(), UseBB)) 2108 continue; 2109 // Ignore uses which are part of other SCEV expressions, to avoid 2110 // analyzing them multiple times. 2111 if (SE.isSCEVable(UserInst->getType())) { 2112 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst)); 2113 // If the user is a no-op, look through to its uses. 2114 if (!isa<SCEVUnknown>(UserS)) 2115 continue; 2116 if (UserS == U) { 2117 Worklist.push_back( 2118 SE.getUnknown(const_cast<Instruction *>(UserInst))); 2119 continue; 2120 } 2121 } 2122 // Ignore icmp instructions which are already being analyzed. 2123 if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UserInst)) { 2124 unsigned OtherIdx = !UI.getOperandNo(); 2125 Value *OtherOp = const_cast<Value *>(ICI->getOperand(OtherIdx)); 2126 if (SE.getSCEV(OtherOp)->hasComputableLoopEvolution(L)) 2127 continue; 2128 } 2129 2130 LSRFixup &LF = getNewFixup(); 2131 LF.UserInst = const_cast<Instruction *>(UserInst); 2132 LF.OperandValToReplace = UI.getUse(); 2133 std::pair<size_t, int64_t> P = getUse(S, LSRUse::Basic, 0); 2134 LF.LUIdx = P.first; 2135 LF.Offset = P.second; 2136 LSRUse &LU = Uses[LF.LUIdx]; 2137 LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L); 2138 InsertSupplementalFormula(U, LU, LF.LUIdx); 2139 CountRegisters(LU.Formulae.back(), Uses.size() - 1); 2140 break; 2141 } 2142 } 2143 } 2144} 2145 2146/// CollectSubexprs - Split S into subexpressions which can be pulled out into 2147/// separate registers. If C is non-null, multiply each subexpression by C. 2148static void CollectSubexprs(const SCEV *S, const SCEVConstant *C, 2149 SmallVectorImpl<const SCEV *> &Ops, 2150 ScalarEvolution &SE) { 2151 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 2152 // Break out add operands. 2153 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 2154 I != E; ++I) 2155 CollectSubexprs(*I, C, Ops, SE); 2156 return; 2157 } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 2158 // Split a non-zero base out of an addrec. 2159 if (!AR->getStart()->isZero()) { 2160 CollectSubexprs(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0), 2161 AR->getStepRecurrence(SE), 2162 AR->getLoop()), C, Ops, SE); 2163 CollectSubexprs(AR->getStart(), C, Ops, SE); 2164 return; 2165 } 2166 } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 2167 // Break (C * (a + b + c)) into C*a + C*b + C*c. 2168 if (Mul->getNumOperands() == 2) 2169 if (const SCEVConstant *Op0 = 2170 dyn_cast<SCEVConstant>(Mul->getOperand(0))) { 2171 CollectSubexprs(Mul->getOperand(1), 2172 C ? cast<SCEVConstant>(SE.getMulExpr(C, Op0)) : Op0, 2173 Ops, SE); 2174 return; 2175 } 2176 } 2177 2178 // Otherwise use the value itself. 2179 Ops.push_back(C ? SE.getMulExpr(C, S) : S); 2180} 2181 2182/// GenerateReassociations - Split out subexpressions from adds and the bases of 2183/// addrecs. 2184void LSRInstance::GenerateReassociations(LSRUse &LU, unsigned LUIdx, 2185 Formula Base, 2186 unsigned Depth) { 2187 // Arbitrarily cap recursion to protect compile time. 2188 if (Depth >= 3) return; 2189 2190 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) { 2191 const SCEV *BaseReg = Base.BaseRegs[i]; 2192 2193 SmallVector<const SCEV *, 8> AddOps; 2194 CollectSubexprs(BaseReg, 0, AddOps, SE); 2195 if (AddOps.size() == 1) continue; 2196 2197 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(), 2198 JE = AddOps.end(); J != JE; ++J) { 2199 // Don't pull a constant into a register if the constant could be folded 2200 // into an immediate field. 2201 if (isAlwaysFoldable(*J, LU.MinOffset, LU.MaxOffset, 2202 Base.getNumRegs() > 1, 2203 LU.Kind, LU.AccessTy, TLI, SE)) 2204 continue; 2205 2206 // Collect all operands except *J. 2207 SmallVector<const SCEV *, 8> InnerAddOps; 2208 for (SmallVectorImpl<const SCEV *>::const_iterator K = AddOps.begin(), 2209 KE = AddOps.end(); K != KE; ++K) 2210 if (K != J) 2211 InnerAddOps.push_back(*K); 2212 2213 // Don't leave just a constant behind in a register if the constant could 2214 // be folded into an immediate field. 2215 if (InnerAddOps.size() == 1 && 2216 isAlwaysFoldable(InnerAddOps[0], LU.MinOffset, LU.MaxOffset, 2217 Base.getNumRegs() > 1, 2218 LU.Kind, LU.AccessTy, TLI, SE)) 2219 continue; 2220 2221 const SCEV *InnerSum = SE.getAddExpr(InnerAddOps); 2222 if (InnerSum->isZero()) 2223 continue; 2224 Formula F = Base; 2225 F.BaseRegs[i] = InnerSum; 2226 F.BaseRegs.push_back(*J); 2227 if (InsertFormula(LU, LUIdx, F)) 2228 // If that formula hadn't been seen before, recurse to find more like 2229 // it. 2230 GenerateReassociations(LU, LUIdx, LU.Formulae.back(), Depth+1); 2231 } 2232 } 2233} 2234 2235/// GenerateCombinations - Generate a formula consisting of all of the 2236/// loop-dominating registers added into a single register. 2237void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx, 2238 Formula Base) { 2239 // This method is only interesting on a plurality of registers. 2240 if (Base.BaseRegs.size() <= 1) return; 2241 2242 Formula F = Base; 2243 F.BaseRegs.clear(); 2244 SmallVector<const SCEV *, 4> Ops; 2245 for (SmallVectorImpl<const SCEV *>::const_iterator 2246 I = Base.BaseRegs.begin(), E = Base.BaseRegs.end(); I != E; ++I) { 2247 const SCEV *BaseReg = *I; 2248 if (BaseReg->properlyDominates(L->getHeader(), &DT) && 2249 !BaseReg->hasComputableLoopEvolution(L)) 2250 Ops.push_back(BaseReg); 2251 else 2252 F.BaseRegs.push_back(BaseReg); 2253 } 2254 if (Ops.size() > 1) { 2255 const SCEV *Sum = SE.getAddExpr(Ops); 2256 // TODO: If Sum is zero, it probably means ScalarEvolution missed an 2257 // opportunity to fold something. For now, just ignore such cases 2258 // rather than proceed with zero in a register. 2259 if (!Sum->isZero()) { 2260 F.BaseRegs.push_back(Sum); 2261 (void)InsertFormula(LU, LUIdx, F); 2262 } 2263 } 2264} 2265 2266/// GenerateSymbolicOffsets - Generate reuse formulae using symbolic offsets. 2267void LSRInstance::GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, 2268 Formula Base) { 2269 // We can't add a symbolic offset if the address already contains one. 2270 if (Base.AM.BaseGV) return; 2271 2272 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) { 2273 const SCEV *G = Base.BaseRegs[i]; 2274 GlobalValue *GV = ExtractSymbol(G, SE); 2275 if (G->isZero() || !GV) 2276 continue; 2277 Formula F = Base; 2278 F.AM.BaseGV = GV; 2279 if (!isLegalUse(F.AM, LU.MinOffset, LU.MaxOffset, 2280 LU.Kind, LU.AccessTy, TLI)) 2281 continue; 2282 F.BaseRegs[i] = G; 2283 (void)InsertFormula(LU, LUIdx, F); 2284 } 2285} 2286 2287/// GenerateConstantOffsets - Generate reuse formulae using symbolic offsets. 2288void LSRInstance::GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, 2289 Formula Base) { 2290 // TODO: For now, just add the min and max offset, because it usually isn't 2291 // worthwhile looking at everything inbetween. 2292 SmallVector<int64_t, 4> Worklist; 2293 Worklist.push_back(LU.MinOffset); 2294 if (LU.MaxOffset != LU.MinOffset) 2295 Worklist.push_back(LU.MaxOffset); 2296 2297 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) { 2298 const SCEV *G = Base.BaseRegs[i]; 2299 2300 for (SmallVectorImpl<int64_t>::const_iterator I = Worklist.begin(), 2301 E = Worklist.end(); I != E; ++I) { 2302 Formula F = Base; 2303 F.AM.BaseOffs = (uint64_t)Base.AM.BaseOffs - *I; 2304 if (isLegalUse(F.AM, LU.MinOffset - *I, LU.MaxOffset - *I, 2305 LU.Kind, LU.AccessTy, TLI)) { 2306 F.BaseRegs[i] = SE.getAddExpr(G, SE.getConstant(G->getType(), *I)); 2307 2308 (void)InsertFormula(LU, LUIdx, F); 2309 } 2310 } 2311 2312 int64_t Imm = ExtractImmediate(G, SE); 2313 if (G->isZero() || Imm == 0) 2314 continue; 2315 Formula F = Base; 2316 F.AM.BaseOffs = (uint64_t)F.AM.BaseOffs + Imm; 2317 if (!isLegalUse(F.AM, LU.MinOffset, LU.MaxOffset, 2318 LU.Kind, LU.AccessTy, TLI)) 2319 continue; 2320 F.BaseRegs[i] = G; 2321 (void)InsertFormula(LU, LUIdx, F); 2322 } 2323} 2324 2325/// GenerateICmpZeroScales - For ICmpZero, check to see if we can scale up 2326/// the comparison. For example, x == y -> x*c == y*c. 2327void LSRInstance::GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, 2328 Formula Base) { 2329 if (LU.Kind != LSRUse::ICmpZero) return; 2330 2331 // Determine the integer type for the base formula. 2332 const Type *IntTy = Base.getType(); 2333 if (!IntTy) return; 2334 if (SE.getTypeSizeInBits(IntTy) > 64) return; 2335 2336 // Don't do this if there is more than one offset. 2337 if (LU.MinOffset != LU.MaxOffset) return; 2338 2339 assert(!Base.AM.BaseGV && "ICmpZero use is not legal!"); 2340 2341 // Check each interesting stride. 2342 for (SmallSetVector<int64_t, 8>::const_iterator 2343 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 2344 int64_t Factor = *I; 2345 Formula F = Base; 2346 2347 // Check that the multiplication doesn't overflow. 2348 if (F.AM.BaseOffs == INT64_MIN && Factor == -1) 2349 continue; 2350 F.AM.BaseOffs = (uint64_t)Base.AM.BaseOffs * Factor; 2351 if (F.AM.BaseOffs / Factor != Base.AM.BaseOffs) 2352 continue; 2353 2354 // Check that multiplying with the use offset doesn't overflow. 2355 int64_t Offset = LU.MinOffset; 2356 if (Offset == INT64_MIN && Factor == -1) 2357 continue; 2358 Offset = (uint64_t)Offset * Factor; 2359 if (Offset / Factor != LU.MinOffset) 2360 continue; 2361 2362 // Check that this scale is legal. 2363 if (!isLegalUse(F.AM, Offset, Offset, LU.Kind, LU.AccessTy, TLI)) 2364 continue; 2365 2366 // Compensate for the use having MinOffset built into it. 2367 F.AM.BaseOffs = (uint64_t)F.AM.BaseOffs + Offset - LU.MinOffset; 2368 2369 const SCEV *FactorS = SE.getConstant(IntTy, Factor); 2370 2371 // Check that multiplying with each base register doesn't overflow. 2372 for (size_t i = 0, e = F.BaseRegs.size(); i != e; ++i) { 2373 F.BaseRegs[i] = SE.getMulExpr(F.BaseRegs[i], FactorS); 2374 if (getExactSDiv(F.BaseRegs[i], FactorS, SE) != Base.BaseRegs[i]) 2375 goto next; 2376 } 2377 2378 // Check that multiplying with the scaled register doesn't overflow. 2379 if (F.ScaledReg) { 2380 F.ScaledReg = SE.getMulExpr(F.ScaledReg, FactorS); 2381 if (getExactSDiv(F.ScaledReg, FactorS, SE) != Base.ScaledReg) 2382 continue; 2383 } 2384 2385 // If we make it here and it's legal, add it. 2386 (void)InsertFormula(LU, LUIdx, F); 2387 next:; 2388 } 2389} 2390 2391/// GenerateScales - Generate stride factor reuse formulae by making use of 2392/// scaled-offset address modes, for example. 2393void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) { 2394 // Determine the integer type for the base formula. 2395 const Type *IntTy = Base.getType(); 2396 if (!IntTy) return; 2397 2398 // If this Formula already has a scaled register, we can't add another one. 2399 if (Base.AM.Scale != 0) return; 2400 2401 // Check each interesting stride. 2402 for (SmallSetVector<int64_t, 8>::const_iterator 2403 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 2404 int64_t Factor = *I; 2405 2406 Base.AM.Scale = Factor; 2407 Base.AM.HasBaseReg = Base.BaseRegs.size() > 1; 2408 // Check whether this scale is going to be legal. 2409 if (!isLegalUse(Base.AM, LU.MinOffset, LU.MaxOffset, 2410 LU.Kind, LU.AccessTy, TLI)) { 2411 // As a special-case, handle special out-of-loop Basic users specially. 2412 // TODO: Reconsider this special case. 2413 if (LU.Kind == LSRUse::Basic && 2414 isLegalUse(Base.AM, LU.MinOffset, LU.MaxOffset, 2415 LSRUse::Special, LU.AccessTy, TLI) && 2416 LU.AllFixupsOutsideLoop) 2417 LU.Kind = LSRUse::Special; 2418 else 2419 continue; 2420 } 2421 // For an ICmpZero, negating a solitary base register won't lead to 2422 // new solutions. 2423 if (LU.Kind == LSRUse::ICmpZero && 2424 !Base.AM.HasBaseReg && Base.AM.BaseOffs == 0 && !Base.AM.BaseGV) 2425 continue; 2426 // For each addrec base reg, apply the scale, if possible. 2427 for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) 2428 if (const SCEVAddRecExpr *AR = 2429 dyn_cast<SCEVAddRecExpr>(Base.BaseRegs[i])) { 2430 const SCEV *FactorS = SE.getConstant(IntTy, Factor); 2431 if (FactorS->isZero()) 2432 continue; 2433 // Divide out the factor, ignoring high bits, since we'll be 2434 // scaling the value back up in the end. 2435 if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) { 2436 // TODO: This could be optimized to avoid all the copying. 2437 Formula F = Base; 2438 F.ScaledReg = Quotient; 2439 F.DeleteBaseReg(F.BaseRegs[i]); 2440 (void)InsertFormula(LU, LUIdx, F); 2441 } 2442 } 2443 } 2444} 2445 2446/// GenerateTruncates - Generate reuse formulae from different IV types. 2447void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) { 2448 // This requires TargetLowering to tell us which truncates are free. 2449 if (!TLI) return; 2450 2451 // Don't bother truncating symbolic values. 2452 if (Base.AM.BaseGV) return; 2453 2454 // Determine the integer type for the base formula. 2455 const Type *DstTy = Base.getType(); 2456 if (!DstTy) return; 2457 DstTy = SE.getEffectiveSCEVType(DstTy); 2458 2459 for (SmallSetVector<const Type *, 4>::const_iterator 2460 I = Types.begin(), E = Types.end(); I != E; ++I) { 2461 const Type *SrcTy = *I; 2462 if (SrcTy != DstTy && TLI->isTruncateFree(SrcTy, DstTy)) { 2463 Formula F = Base; 2464 2465 if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, *I); 2466 for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(), 2467 JE = F.BaseRegs.end(); J != JE; ++J) 2468 *J = SE.getAnyExtendExpr(*J, SrcTy); 2469 2470 // TODO: This assumes we've done basic processing on all uses and 2471 // have an idea what the register usage is. 2472 if (!F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses)) 2473 continue; 2474 2475 (void)InsertFormula(LU, LUIdx, F); 2476 } 2477 } 2478} 2479 2480namespace { 2481 2482/// WorkItem - Helper class for GenerateCrossUseConstantOffsets. It's used to 2483/// defer modifications so that the search phase doesn't have to worry about 2484/// the data structures moving underneath it. 2485struct WorkItem { 2486 size_t LUIdx; 2487 int64_t Imm; 2488 const SCEV *OrigReg; 2489 2490 WorkItem(size_t LI, int64_t I, const SCEV *R) 2491 : LUIdx(LI), Imm(I), OrigReg(R) {} 2492 2493 void print(raw_ostream &OS) const; 2494 void dump() const; 2495}; 2496 2497} 2498 2499void WorkItem::print(raw_ostream &OS) const { 2500 OS << "in formulae referencing " << *OrigReg << " in use " << LUIdx 2501 << " , add offset " << Imm; 2502} 2503 2504void WorkItem::dump() const { 2505 print(errs()); errs() << '\n'; 2506} 2507 2508/// GenerateCrossUseConstantOffsets - Look for registers which are a constant 2509/// distance apart and try to form reuse opportunities between them. 2510void LSRInstance::GenerateCrossUseConstantOffsets() { 2511 // Group the registers by their value without any added constant offset. 2512 typedef std::map<int64_t, const SCEV *> ImmMapTy; 2513 typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy; 2514 RegMapTy Map; 2515 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap; 2516 SmallVector<const SCEV *, 8> Sequence; 2517 for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); 2518 I != E; ++I) { 2519 const SCEV *Reg = *I; 2520 int64_t Imm = ExtractImmediate(Reg, SE); 2521 std::pair<RegMapTy::iterator, bool> Pair = 2522 Map.insert(std::make_pair(Reg, ImmMapTy())); 2523 if (Pair.second) 2524 Sequence.push_back(Reg); 2525 Pair.first->second.insert(std::make_pair(Imm, *I)); 2526 UsedByIndicesMap[Reg] |= RegUses.getUsedByIndices(*I); 2527 } 2528 2529 // Now examine each set of registers with the same base value. Build up 2530 // a list of work to do and do the work in a separate step so that we're 2531 // not adding formulae and register counts while we're searching. 2532 SmallVector<WorkItem, 32> WorkItems; 2533 SmallSet<std::pair<size_t, int64_t>, 32> UniqueItems; 2534 for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(), 2535 E = Sequence.end(); I != E; ++I) { 2536 const SCEV *Reg = *I; 2537 const ImmMapTy &Imms = Map.find(Reg)->second; 2538 2539 // It's not worthwhile looking for reuse if there's only one offset. 2540 if (Imms.size() == 1) 2541 continue; 2542 2543 DEBUG(dbgs() << "Generating cross-use offsets for " << *Reg << ':'; 2544 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); 2545 J != JE; ++J) 2546 dbgs() << ' ' << J->first; 2547 dbgs() << '\n'); 2548 2549 // Examine each offset. 2550 for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end(); 2551 J != JE; ++J) { 2552 const SCEV *OrigReg = J->second; 2553 2554 int64_t JImm = J->first; 2555 const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(OrigReg); 2556 2557 if (!isa<SCEVConstant>(OrigReg) && 2558 UsedByIndicesMap[Reg].count() == 1) { 2559 DEBUG(dbgs() << "Skipping cross-use reuse for " << *OrigReg << '\n'); 2560 continue; 2561 } 2562 2563 // Conservatively examine offsets between this orig reg a few selected 2564 // other orig regs. 2565 ImmMapTy::const_iterator OtherImms[] = { 2566 Imms.begin(), prior(Imms.end()), 2567 Imms.upper_bound((Imms.begin()->first + prior(Imms.end())->first) / 2) 2568 }; 2569 for (size_t i = 0, e = array_lengthof(OtherImms); i != e; ++i) { 2570 ImmMapTy::const_iterator M = OtherImms[i]; 2571 if (M == J || M == JE) continue; 2572 2573 // Compute the difference between the two. 2574 int64_t Imm = (uint64_t)JImm - M->first; 2575 for (int LUIdx = UsedByIndices.find_first(); LUIdx != -1; 2576 LUIdx = UsedByIndices.find_next(LUIdx)) 2577 // Make a memo of this use, offset, and register tuple. 2578 if (UniqueItems.insert(std::make_pair(LUIdx, Imm))) 2579 WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg)); 2580 } 2581 } 2582 } 2583 2584 Map.clear(); 2585 Sequence.clear(); 2586 UsedByIndicesMap.clear(); 2587 UniqueItems.clear(); 2588 2589 // Now iterate through the worklist and add new formulae. 2590 for (SmallVectorImpl<WorkItem>::const_iterator I = WorkItems.begin(), 2591 E = WorkItems.end(); I != E; ++I) { 2592 const WorkItem &WI = *I; 2593 size_t LUIdx = WI.LUIdx; 2594 LSRUse &LU = Uses[LUIdx]; 2595 int64_t Imm = WI.Imm; 2596 const SCEV *OrigReg = WI.OrigReg; 2597 2598 const Type *IntTy = SE.getEffectiveSCEVType(OrigReg->getType()); 2599 const SCEV *NegImmS = SE.getSCEV(ConstantInt::get(IntTy, -(uint64_t)Imm)); 2600 unsigned BitWidth = SE.getTypeSizeInBits(IntTy); 2601 2602 // TODO: Use a more targeted data structure. 2603 for (size_t L = 0, LE = LU.Formulae.size(); L != LE; ++L) { 2604 Formula F = LU.Formulae[L]; 2605 // Use the immediate in the scaled register. 2606 if (F.ScaledReg == OrigReg) { 2607 int64_t Offs = (uint64_t)F.AM.BaseOffs + 2608 Imm * (uint64_t)F.AM.Scale; 2609 // Don't create 50 + reg(-50). 2610 if (F.referencesReg(SE.getSCEV( 2611 ConstantInt::get(IntTy, -(uint64_t)Offs)))) 2612 continue; 2613 Formula NewF = F; 2614 NewF.AM.BaseOffs = Offs; 2615 if (!isLegalUse(NewF.AM, LU.MinOffset, LU.MaxOffset, 2616 LU.Kind, LU.AccessTy, TLI)) 2617 continue; 2618 NewF.ScaledReg = SE.getAddExpr(NegImmS, NewF.ScaledReg); 2619 2620 // If the new scale is a constant in a register, and adding the constant 2621 // value to the immediate would produce a value closer to zero than the 2622 // immediate itself, then the formula isn't worthwhile. 2623 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(NewF.ScaledReg)) 2624 if (C->getValue()->getValue().isNegative() != 2625 (NewF.AM.BaseOffs < 0) && 2626 (C->getValue()->getValue().abs() * APInt(BitWidth, F.AM.Scale)) 2627 .ule(abs64(NewF.AM.BaseOffs))) 2628 continue; 2629 2630 // OK, looks good. 2631 (void)InsertFormula(LU, LUIdx, NewF); 2632 } else { 2633 // Use the immediate in a base register. 2634 for (size_t N = 0, NE = F.BaseRegs.size(); N != NE; ++N) { 2635 const SCEV *BaseReg = F.BaseRegs[N]; 2636 if (BaseReg != OrigReg) 2637 continue; 2638 Formula NewF = F; 2639 NewF.AM.BaseOffs = (uint64_t)NewF.AM.BaseOffs + Imm; 2640 if (!isLegalUse(NewF.AM, LU.MinOffset, LU.MaxOffset, 2641 LU.Kind, LU.AccessTy, TLI)) 2642 continue; 2643 NewF.BaseRegs[N] = SE.getAddExpr(NegImmS, BaseReg); 2644 2645 // If the new formula has a constant in a register, and adding the 2646 // constant value to the immediate would produce a value closer to 2647 // zero than the immediate itself, then the formula isn't worthwhile. 2648 for (SmallVectorImpl<const SCEV *>::const_iterator 2649 J = NewF.BaseRegs.begin(), JE = NewF.BaseRegs.end(); 2650 J != JE; ++J) 2651 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*J)) 2652 if ((C->getValue()->getValue() + NewF.AM.BaseOffs).abs().slt( 2653 abs64(NewF.AM.BaseOffs)) && 2654 (C->getValue()->getValue() + 2655 NewF.AM.BaseOffs).countTrailingZeros() >= 2656 CountTrailingZeros_64(NewF.AM.BaseOffs)) 2657 goto skip_formula; 2658 2659 // Ok, looks good. 2660 (void)InsertFormula(LU, LUIdx, NewF); 2661 break; 2662 skip_formula:; 2663 } 2664 } 2665 } 2666 } 2667} 2668 2669/// GenerateAllReuseFormulae - Generate formulae for each use. 2670void 2671LSRInstance::GenerateAllReuseFormulae() { 2672 // This is split into multiple loops so that hasRegsUsedByUsesOtherThan 2673 // queries are more precise. 2674 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2675 LSRUse &LU = Uses[LUIdx]; 2676 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2677 GenerateReassociations(LU, LUIdx, LU.Formulae[i]); 2678 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2679 GenerateCombinations(LU, LUIdx, LU.Formulae[i]); 2680 } 2681 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2682 LSRUse &LU = Uses[LUIdx]; 2683 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2684 GenerateSymbolicOffsets(LU, LUIdx, LU.Formulae[i]); 2685 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2686 GenerateConstantOffsets(LU, LUIdx, LU.Formulae[i]); 2687 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2688 GenerateICmpZeroScales(LU, LUIdx, LU.Formulae[i]); 2689 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2690 GenerateScales(LU, LUIdx, LU.Formulae[i]); 2691 } 2692 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2693 LSRUse &LU = Uses[LUIdx]; 2694 for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i) 2695 GenerateTruncates(LU, LUIdx, LU.Formulae[i]); 2696 } 2697 2698 GenerateCrossUseConstantOffsets(); 2699} 2700 2701/// If their are multiple formulae with the same set of registers used 2702/// by other uses, pick the best one and delete the others. 2703void LSRInstance::FilterOutUndesirableDedicatedRegisters() { 2704#ifndef NDEBUG 2705 bool ChangedFormulae = false; 2706#endif 2707 2708 // Collect the best formula for each unique set of shared registers. This 2709 // is reset for each use. 2710 typedef DenseMap<SmallVector<const SCEV *, 2>, size_t, UniquifierDenseMapInfo> 2711 BestFormulaeTy; 2712 BestFormulaeTy BestFormulae; 2713 2714 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2715 LSRUse &LU = Uses[LUIdx]; 2716 FormulaSorter Sorter(L, LU, SE, DT); 2717 DEBUG(dbgs() << "Filtering for use "; LU.print(dbgs()); dbgs() << '\n'); 2718 2719 bool Any = false; 2720 for (size_t FIdx = 0, NumForms = LU.Formulae.size(); 2721 FIdx != NumForms; ++FIdx) { 2722 Formula &F = LU.Formulae[FIdx]; 2723 2724 SmallVector<const SCEV *, 2> Key; 2725 for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(), 2726 JE = F.BaseRegs.end(); J != JE; ++J) { 2727 const SCEV *Reg = *J; 2728 if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx)) 2729 Key.push_back(Reg); 2730 } 2731 if (F.ScaledReg && 2732 RegUses.isRegUsedByUsesOtherThan(F.ScaledReg, LUIdx)) 2733 Key.push_back(F.ScaledReg); 2734 // Unstable sort by host order ok, because this is only used for 2735 // uniquifying. 2736 std::sort(Key.begin(), Key.end()); 2737 2738 std::pair<BestFormulaeTy::const_iterator, bool> P = 2739 BestFormulae.insert(std::make_pair(Key, FIdx)); 2740 if (!P.second) { 2741 Formula &Best = LU.Formulae[P.first->second]; 2742 if (Sorter.operator()(F, Best)) 2743 std::swap(F, Best); 2744 DEBUG(dbgs() << " Filtering out formula "; F.print(dbgs()); 2745 dbgs() << "\n" 2746 " in favor of formula "; Best.print(dbgs()); 2747 dbgs() << '\n'); 2748#ifndef NDEBUG 2749 ChangedFormulae = true; 2750#endif 2751 LU.DeleteFormula(F); 2752 --FIdx; 2753 --NumForms; 2754 Any = true; 2755 continue; 2756 } 2757 } 2758 2759 // Now that we've filtered out some formulae, recompute the Regs set. 2760 if (Any) 2761 LU.RecomputeRegs(LUIdx, RegUses); 2762 2763 // Reset this to prepare for the next use. 2764 BestFormulae.clear(); 2765 } 2766 2767 DEBUG(if (ChangedFormulae) { 2768 dbgs() << "\n" 2769 "After filtering out undesirable candidates:\n"; 2770 print_uses(dbgs()); 2771 }); 2772} 2773 2774// This is a rough guess that seems to work fairly well. 2775static const size_t ComplexityLimit = UINT16_MAX; 2776 2777/// EstimateSearchSpaceComplexity - Estimate the worst-case number of 2778/// solutions the solver might have to consider. It almost never considers 2779/// this many solutions because it prune the search space, but the pruning 2780/// isn't always sufficient. 2781size_t LSRInstance::EstimateSearchSpaceComplexity() const { 2782 uint32_t Power = 1; 2783 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 2784 E = Uses.end(); I != E; ++I) { 2785 size_t FSize = I->Formulae.size(); 2786 if (FSize >= ComplexityLimit) { 2787 Power = ComplexityLimit; 2788 break; 2789 } 2790 Power *= FSize; 2791 if (Power >= ComplexityLimit) 2792 break; 2793 } 2794 return Power; 2795} 2796 2797/// NarrowSearchSpaceUsingHeuristics - If there are an extraordinary number of 2798/// formulae to choose from, use some rough heuristics to prune down the number 2799/// of formulae. This keeps the main solver from taking an extraordinary amount 2800/// of time in some worst-case scenarios. 2801void LSRInstance::NarrowSearchSpaceUsingHeuristics() { 2802 if (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 2803 DEBUG(dbgs() << "The search space is too complex.\n"); 2804 2805 DEBUG(dbgs() << "Narrowing the search space by eliminating formulae " 2806 "which use a superset of registers used by other " 2807 "formulae.\n"); 2808 2809 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2810 LSRUse &LU = Uses[LUIdx]; 2811 bool Any = false; 2812 for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) { 2813 Formula &F = LU.Formulae[i]; 2814 // Look for a formula with a constant or GV in a register. If the use 2815 // also has a formula with that same value in an immediate field, 2816 // delete the one that uses a register. 2817 for (SmallVectorImpl<const SCEV *>::const_iterator 2818 I = F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) { 2819 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*I)) { 2820 Formula NewF = F; 2821 NewF.AM.BaseOffs += C->getValue()->getSExtValue(); 2822 NewF.BaseRegs.erase(NewF.BaseRegs.begin() + 2823 (I - F.BaseRegs.begin())); 2824 if (LU.HasFormulaWithSameRegs(NewF)) { 2825 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); dbgs() << '\n'); 2826 LU.DeleteFormula(F); 2827 --i; 2828 --e; 2829 Any = true; 2830 break; 2831 } 2832 } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(*I)) { 2833 if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) 2834 if (!F.AM.BaseGV) { 2835 Formula NewF = F; 2836 NewF.AM.BaseGV = GV; 2837 NewF.BaseRegs.erase(NewF.BaseRegs.begin() + 2838 (I - F.BaseRegs.begin())); 2839 if (LU.HasFormulaWithSameRegs(NewF)) { 2840 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); 2841 dbgs() << '\n'); 2842 LU.DeleteFormula(F); 2843 --i; 2844 --e; 2845 Any = true; 2846 break; 2847 } 2848 } 2849 } 2850 } 2851 } 2852 if (Any) 2853 LU.RecomputeRegs(LUIdx, RegUses); 2854 } 2855 2856 DEBUG(dbgs() << "After pre-selection:\n"; 2857 print_uses(dbgs())); 2858 } 2859 2860 if (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 2861 DEBUG(dbgs() << "The search space is too complex.\n"); 2862 2863 DEBUG(dbgs() << "Narrowing the search space by assuming that uses " 2864 "separated by a constant offset will use the same " 2865 "registers.\n"); 2866 2867 // This is especially useful for unrolled loops. 2868 2869 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2870 LSRUse &LU = Uses[LUIdx]; 2871 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 2872 E = LU.Formulae.end(); I != E; ++I) { 2873 const Formula &F = *I; 2874 if (F.AM.BaseOffs != 0 && F.AM.Scale == 0) { 2875 if (LSRUse *LUThatHas = FindUseWithSimilarFormula(F, LU)) { 2876 if (reconcileNewOffset(*LUThatHas, F.AM.BaseOffs, 2877 /*HasBaseReg=*/false, 2878 LU.Kind, LU.AccessTy)) { 2879 DEBUG(dbgs() << " Deleting use "; LU.print(dbgs()); 2880 dbgs() << '\n'); 2881 2882 LUThatHas->AllFixupsOutsideLoop &= LU.AllFixupsOutsideLoop; 2883 2884 // Delete formulae from the new use which are no longer legal. 2885 bool Any = false; 2886 for (size_t i = 0, e = LUThatHas->Formulae.size(); i != e; ++i) { 2887 Formula &F = LUThatHas->Formulae[i]; 2888 if (!isLegalUse(F.AM, 2889 LUThatHas->MinOffset, LUThatHas->MaxOffset, 2890 LUThatHas->Kind, LUThatHas->AccessTy, TLI)) { 2891 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); 2892 dbgs() << '\n'); 2893 LUThatHas->DeleteFormula(F); 2894 --i; 2895 --e; 2896 Any = true; 2897 } 2898 } 2899 if (Any) 2900 LUThatHas->RecomputeRegs(LUThatHas - &Uses.front(), RegUses); 2901 2902 // Update the relocs to reference the new use. 2903 for (SmallVectorImpl<LSRFixup>::iterator I = Fixups.begin(), 2904 E = Fixups.end(); I != E; ++I) { 2905 LSRFixup &Fixup = *I; 2906 if (Fixup.LUIdx == LUIdx) { 2907 Fixup.LUIdx = LUThatHas - &Uses.front(); 2908 Fixup.Offset += F.AM.BaseOffs; 2909 DEBUG(errs() << "New fixup has offset " 2910 << Fixup.Offset << '\n'); 2911 } 2912 if (Fixup.LUIdx == NumUses-1) 2913 Fixup.LUIdx = LUIdx; 2914 } 2915 2916 // Delete the old use. 2917 DeleteUse(LU); 2918 --LUIdx; 2919 --NumUses; 2920 break; 2921 } 2922 } 2923 } 2924 } 2925 } 2926 2927 DEBUG(dbgs() << "After pre-selection:\n"; 2928 print_uses(dbgs())); 2929 } 2930 2931 SmallPtrSet<const SCEV *, 4> Taken; 2932 while (EstimateSearchSpaceComplexity() >= ComplexityLimit) { 2933 // Ok, we have too many of formulae on our hands to conveniently handle. 2934 // Use a rough heuristic to thin out the list. 2935 DEBUG(dbgs() << "The search space is too complex.\n"); 2936 2937 // Pick the register which is used by the most LSRUses, which is likely 2938 // to be a good reuse register candidate. 2939 const SCEV *Best = 0; 2940 unsigned BestNum = 0; 2941 for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end(); 2942 I != E; ++I) { 2943 const SCEV *Reg = *I; 2944 if (Taken.count(Reg)) 2945 continue; 2946 if (!Best) 2947 Best = Reg; 2948 else { 2949 unsigned Count = RegUses.getUsedByIndices(Reg).count(); 2950 if (Count > BestNum) { 2951 Best = Reg; 2952 BestNum = Count; 2953 } 2954 } 2955 } 2956 2957 DEBUG(dbgs() << "Narrowing the search space by assuming " << *Best 2958 << " will yield profitable reuse.\n"); 2959 Taken.insert(Best); 2960 2961 // In any use with formulae which references this register, delete formulae 2962 // which don't reference it. 2963 for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) { 2964 LSRUse &LU = Uses[LUIdx]; 2965 if (!LU.Regs.count(Best)) continue; 2966 2967 bool Any = false; 2968 for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) { 2969 Formula &F = LU.Formulae[i]; 2970 if (!F.referencesReg(Best)) { 2971 DEBUG(dbgs() << " Deleting "; F.print(dbgs()); dbgs() << '\n'); 2972 LU.DeleteFormula(F); 2973 --e; 2974 --i; 2975 Any = true; 2976 assert(e != 0 && "Use has no formulae left! Is Regs inconsistent?"); 2977 continue; 2978 } 2979 } 2980 2981 if (Any) 2982 LU.RecomputeRegs(LUIdx, RegUses); 2983 } 2984 2985 DEBUG(dbgs() << "After pre-selection:\n"; 2986 print_uses(dbgs())); 2987 } 2988} 2989 2990/// SolveRecurse - This is the recursive solver. 2991void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution, 2992 Cost &SolutionCost, 2993 SmallVectorImpl<const Formula *> &Workspace, 2994 const Cost &CurCost, 2995 const SmallPtrSet<const SCEV *, 16> &CurRegs, 2996 DenseSet<const SCEV *> &VisitedRegs) const { 2997 // Some ideas: 2998 // - prune more: 2999 // - use more aggressive filtering 3000 // - sort the formula so that the most profitable solutions are found first 3001 // - sort the uses too 3002 // - search faster: 3003 // - don't compute a cost, and then compare. compare while computing a cost 3004 // and bail early. 3005 // - track register sets with SmallBitVector 3006 3007 const LSRUse &LU = Uses[Workspace.size()]; 3008 3009 // If this use references any register that's already a part of the 3010 // in-progress solution, consider it a requirement that a formula must 3011 // reference that register in order to be considered. This prunes out 3012 // unprofitable searching. 3013 SmallSetVector<const SCEV *, 4> ReqRegs; 3014 for (SmallPtrSet<const SCEV *, 16>::const_iterator I = CurRegs.begin(), 3015 E = CurRegs.end(); I != E; ++I) 3016 if (LU.Regs.count(*I)) 3017 ReqRegs.insert(*I); 3018 3019 bool AnySatisfiedReqRegs = false; 3020 SmallPtrSet<const SCEV *, 16> NewRegs; 3021 Cost NewCost; 3022retry: 3023 for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(), 3024 E = LU.Formulae.end(); I != E; ++I) { 3025 const Formula &F = *I; 3026 3027 // Ignore formulae which do not use any of the required registers. 3028 for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(), 3029 JE = ReqRegs.end(); J != JE; ++J) { 3030 const SCEV *Reg = *J; 3031 if ((!F.ScaledReg || F.ScaledReg != Reg) && 3032 std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) == 3033 F.BaseRegs.end()) 3034 goto skip; 3035 } 3036 AnySatisfiedReqRegs = true; 3037 3038 // Evaluate the cost of the current formula. If it's already worse than 3039 // the current best, prune the search at that point. 3040 NewCost = CurCost; 3041 NewRegs = CurRegs; 3042 NewCost.RateFormula(F, NewRegs, VisitedRegs, L, LU.Offsets, SE, DT); 3043 if (NewCost < SolutionCost) { 3044 Workspace.push_back(&F); 3045 if (Workspace.size() != Uses.size()) { 3046 SolveRecurse(Solution, SolutionCost, Workspace, NewCost, 3047 NewRegs, VisitedRegs); 3048 if (F.getNumRegs() == 1 && Workspace.size() == 1) 3049 VisitedRegs.insert(F.ScaledReg ? F.ScaledReg : F.BaseRegs[0]); 3050 } else { 3051 DEBUG(dbgs() << "New best at "; NewCost.print(dbgs()); 3052 dbgs() << ". Regs:"; 3053 for (SmallPtrSet<const SCEV *, 16>::const_iterator 3054 I = NewRegs.begin(), E = NewRegs.end(); I != E; ++I) 3055 dbgs() << ' ' << **I; 3056 dbgs() << '\n'); 3057 3058 SolutionCost = NewCost; 3059 Solution = Workspace; 3060 } 3061 Workspace.pop_back(); 3062 } 3063 skip:; 3064 } 3065 3066 // If none of the formulae had all of the required registers, relax the 3067 // constraint so that we don't exclude all formulae. 3068 if (!AnySatisfiedReqRegs) { 3069 assert(!ReqRegs.empty() && "Solver failed even without required registers"); 3070 ReqRegs.clear(); 3071 goto retry; 3072 } 3073} 3074 3075void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const { 3076 SmallVector<const Formula *, 8> Workspace; 3077 Cost SolutionCost; 3078 SolutionCost.Loose(); 3079 Cost CurCost; 3080 SmallPtrSet<const SCEV *, 16> CurRegs; 3081 DenseSet<const SCEV *> VisitedRegs; 3082 Workspace.reserve(Uses.size()); 3083 3084 // SolveRecurse does all the work. 3085 SolveRecurse(Solution, SolutionCost, Workspace, CurCost, 3086 CurRegs, VisitedRegs); 3087 3088 // Ok, we've now made all our decisions. 3089 DEBUG(dbgs() << "\n" 3090 "The chosen solution requires "; SolutionCost.print(dbgs()); 3091 dbgs() << ":\n"; 3092 for (size_t i = 0, e = Uses.size(); i != e; ++i) { 3093 dbgs() << " "; 3094 Uses[i].print(dbgs()); 3095 dbgs() << "\n" 3096 " "; 3097 Solution[i]->print(dbgs()); 3098 dbgs() << '\n'; 3099 }); 3100} 3101 3102/// HoistInsertPosition - Helper for AdjustInsertPositionForExpand. Climb up 3103/// the dominator tree far as we can go while still being dominated by the 3104/// input positions. This helps canonicalize the insert position, which 3105/// encourages sharing. 3106BasicBlock::iterator 3107LSRInstance::HoistInsertPosition(BasicBlock::iterator IP, 3108 const SmallVectorImpl<Instruction *> &Inputs) 3109 const { 3110 for (;;) { 3111 const Loop *IPLoop = LI.getLoopFor(IP->getParent()); 3112 unsigned IPLoopDepth = IPLoop ? IPLoop->getLoopDepth() : 0; 3113 3114 BasicBlock *IDom; 3115 for (DomTreeNode *Rung = DT.getNode(IP->getParent()); ; ) { 3116 assert(Rung && "Block has no DomTreeNode!"); 3117 Rung = Rung->getIDom(); 3118 if (!Rung) return IP; 3119 IDom = Rung->getBlock(); 3120 3121 // Don't climb into a loop though. 3122 const Loop *IDomLoop = LI.getLoopFor(IDom); 3123 unsigned IDomDepth = IDomLoop ? IDomLoop->getLoopDepth() : 0; 3124 if (IDomDepth <= IPLoopDepth && 3125 (IDomDepth != IPLoopDepth || IDomLoop == IPLoop)) 3126 break; 3127 } 3128 3129 bool AllDominate = true; 3130 Instruction *BetterPos = 0; 3131 Instruction *Tentative = IDom->getTerminator(); 3132 for (SmallVectorImpl<Instruction *>::const_iterator I = Inputs.begin(), 3133 E = Inputs.end(); I != E; ++I) { 3134 Instruction *Inst = *I; 3135 if (Inst == Tentative || !DT.dominates(Inst, Tentative)) { 3136 AllDominate = false; 3137 break; 3138 } 3139 // Attempt to find an insert position in the middle of the block, 3140 // instead of at the end, so that it can be used for other expansions. 3141 if (IDom == Inst->getParent() && 3142 (!BetterPos || DT.dominates(BetterPos, Inst))) 3143 BetterPos = llvm::next(BasicBlock::iterator(Inst)); 3144 } 3145 if (!AllDominate) 3146 break; 3147 if (BetterPos) 3148 IP = BetterPos; 3149 else 3150 IP = Tentative; 3151 } 3152 3153 return IP; 3154} 3155 3156/// AdjustInsertPositionForExpand - Determine an input position which will be 3157/// dominated by the operands and which will dominate the result. 3158BasicBlock::iterator 3159LSRInstance::AdjustInsertPositionForExpand(BasicBlock::iterator IP, 3160 const LSRFixup &LF, 3161 const LSRUse &LU) const { 3162 // Collect some instructions which must be dominated by the 3163 // expanding replacement. These must be dominated by any operands that 3164 // will be required in the expansion. 3165 SmallVector<Instruction *, 4> Inputs; 3166 if (Instruction *I = dyn_cast<Instruction>(LF.OperandValToReplace)) 3167 Inputs.push_back(I); 3168 if (LU.Kind == LSRUse::ICmpZero) 3169 if (Instruction *I = 3170 dyn_cast<Instruction>(cast<ICmpInst>(LF.UserInst)->getOperand(1))) 3171 Inputs.push_back(I); 3172 if (LF.PostIncLoops.count(L)) { 3173 if (LF.isUseFullyOutsideLoop(L)) 3174 Inputs.push_back(L->getLoopLatch()->getTerminator()); 3175 else 3176 Inputs.push_back(IVIncInsertPos); 3177 } 3178 // The expansion must also be dominated by the increment positions of any 3179 // loops it for which it is using post-inc mode. 3180 for (PostIncLoopSet::const_iterator I = LF.PostIncLoops.begin(), 3181 E = LF.PostIncLoops.end(); I != E; ++I) { 3182 const Loop *PIL = *I; 3183 if (PIL == L) continue; 3184 3185 // Be dominated by the loop exit. 3186 SmallVector<BasicBlock *, 4> ExitingBlocks; 3187 PIL->getExitingBlocks(ExitingBlocks); 3188 if (!ExitingBlocks.empty()) { 3189 BasicBlock *BB = ExitingBlocks[0]; 3190 for (unsigned i = 1, e = ExitingBlocks.size(); i != e; ++i) 3191 BB = DT.findNearestCommonDominator(BB, ExitingBlocks[i]); 3192 Inputs.push_back(BB->getTerminator()); 3193 } 3194 } 3195 3196 // Then, climb up the immediate dominator tree as far as we can go while 3197 // still being dominated by the input positions. 3198 IP = HoistInsertPosition(IP, Inputs); 3199 3200 // Don't insert instructions before PHI nodes. 3201 while (isa<PHINode>(IP)) ++IP; 3202 3203 // Ignore debug intrinsics. 3204 while (isa<DbgInfoIntrinsic>(IP)) ++IP; 3205 3206 return IP; 3207} 3208 3209Value *LSRInstance::Expand(const LSRFixup &LF, 3210 const Formula &F, 3211 BasicBlock::iterator IP, 3212 SCEVExpander &Rewriter, 3213 SmallVectorImpl<WeakVH> &DeadInsts) const { 3214 const LSRUse &LU = Uses[LF.LUIdx]; 3215 3216 // Determine an input position which will be dominated by the operands and 3217 // which will dominate the result. 3218 IP = AdjustInsertPositionForExpand(IP, LF, LU); 3219 3220 // Inform the Rewriter if we have a post-increment use, so that it can 3221 // perform an advantageous expansion. 3222 Rewriter.setPostInc(LF.PostIncLoops); 3223 3224 // This is the type that the user actually needs. 3225 const Type *OpTy = LF.OperandValToReplace->getType(); 3226 // This will be the type that we'll initially expand to. 3227 const Type *Ty = F.getType(); 3228 if (!Ty) 3229 // No type known; just expand directly to the ultimate type. 3230 Ty = OpTy; 3231 else if (SE.getEffectiveSCEVType(Ty) == SE.getEffectiveSCEVType(OpTy)) 3232 // Expand directly to the ultimate type if it's the right size. 3233 Ty = OpTy; 3234 // This is the type to do integer arithmetic in. 3235 const Type *IntTy = SE.getEffectiveSCEVType(Ty); 3236 3237 // Build up a list of operands to add together to form the full base. 3238 SmallVector<const SCEV *, 8> Ops; 3239 3240 // Expand the BaseRegs portion. 3241 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(), 3242 E = F.BaseRegs.end(); I != E; ++I) { 3243 const SCEV *Reg = *I; 3244 assert(!Reg->isZero() && "Zero allocated in a base register!"); 3245 3246 // If we're expanding for a post-inc user, make the post-inc adjustment. 3247 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops); 3248 Reg = TransformForPostIncUse(Denormalize, Reg, 3249 LF.UserInst, LF.OperandValToReplace, 3250 Loops, SE, DT); 3251 3252 Ops.push_back(SE.getUnknown(Rewriter.expandCodeFor(Reg, 0, IP))); 3253 } 3254 3255 // Flush the operand list to suppress SCEVExpander hoisting. 3256 if (!Ops.empty()) { 3257 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 3258 Ops.clear(); 3259 Ops.push_back(SE.getUnknown(FullV)); 3260 } 3261 3262 // Expand the ScaledReg portion. 3263 Value *ICmpScaledV = 0; 3264 if (F.AM.Scale != 0) { 3265 const SCEV *ScaledS = F.ScaledReg; 3266 3267 // If we're expanding for a post-inc user, make the post-inc adjustment. 3268 PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops); 3269 ScaledS = TransformForPostIncUse(Denormalize, ScaledS, 3270 LF.UserInst, LF.OperandValToReplace, 3271 Loops, SE, DT); 3272 3273 if (LU.Kind == LSRUse::ICmpZero) { 3274 // An interesting way of "folding" with an icmp is to use a negated 3275 // scale, which we'll implement by inserting it into the other operand 3276 // of the icmp. 3277 assert(F.AM.Scale == -1 && 3278 "The only scale supported by ICmpZero uses is -1!"); 3279 ICmpScaledV = Rewriter.expandCodeFor(ScaledS, 0, IP); 3280 } else { 3281 // Otherwise just expand the scaled register and an explicit scale, 3282 // which is expected to be matched as part of the address. 3283 ScaledS = SE.getUnknown(Rewriter.expandCodeFor(ScaledS, 0, IP)); 3284 ScaledS = SE.getMulExpr(ScaledS, 3285 SE.getConstant(ScaledS->getType(), F.AM.Scale)); 3286 Ops.push_back(ScaledS); 3287 3288 // Flush the operand list to suppress SCEVExpander hoisting. 3289 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 3290 Ops.clear(); 3291 Ops.push_back(SE.getUnknown(FullV)); 3292 } 3293 } 3294 3295 // Expand the GV portion. 3296 if (F.AM.BaseGV) { 3297 Ops.push_back(SE.getUnknown(F.AM.BaseGV)); 3298 3299 // Flush the operand list to suppress SCEVExpander hoisting. 3300 Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP); 3301 Ops.clear(); 3302 Ops.push_back(SE.getUnknown(FullV)); 3303 } 3304 3305 // Expand the immediate portion. 3306 int64_t Offset = (uint64_t)F.AM.BaseOffs + LF.Offset; 3307 if (Offset != 0) { 3308 if (LU.Kind == LSRUse::ICmpZero) { 3309 // The other interesting way of "folding" with an ICmpZero is to use a 3310 // negated immediate. 3311 if (!ICmpScaledV) 3312 ICmpScaledV = ConstantInt::get(IntTy, -Offset); 3313 else { 3314 Ops.push_back(SE.getUnknown(ICmpScaledV)); 3315 ICmpScaledV = ConstantInt::get(IntTy, Offset); 3316 } 3317 } else { 3318 // Just add the immediate values. These again are expected to be matched 3319 // as part of the address. 3320 Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy, Offset))); 3321 } 3322 } 3323 3324 // Emit instructions summing all the operands. 3325 const SCEV *FullS = Ops.empty() ? 3326 SE.getConstant(IntTy, 0) : 3327 SE.getAddExpr(Ops); 3328 Value *FullV = Rewriter.expandCodeFor(FullS, Ty, IP); 3329 3330 // We're done expanding now, so reset the rewriter. 3331 Rewriter.clearPostInc(); 3332 3333 // An ICmpZero Formula represents an ICmp which we're handling as a 3334 // comparison against zero. Now that we've expanded an expression for that 3335 // form, update the ICmp's other operand. 3336 if (LU.Kind == LSRUse::ICmpZero) { 3337 ICmpInst *CI = cast<ICmpInst>(LF.UserInst); 3338 DeadInsts.push_back(CI->getOperand(1)); 3339 assert(!F.AM.BaseGV && "ICmp does not support folding a global value and " 3340 "a scale at the same time!"); 3341 if (F.AM.Scale == -1) { 3342 if (ICmpScaledV->getType() != OpTy) { 3343 Instruction *Cast = 3344 CastInst::Create(CastInst::getCastOpcode(ICmpScaledV, false, 3345 OpTy, false), 3346 ICmpScaledV, OpTy, "tmp", CI); 3347 ICmpScaledV = Cast; 3348 } 3349 CI->setOperand(1, ICmpScaledV); 3350 } else { 3351 assert(F.AM.Scale == 0 && 3352 "ICmp does not support folding a global value and " 3353 "a scale at the same time!"); 3354 Constant *C = ConstantInt::getSigned(SE.getEffectiveSCEVType(OpTy), 3355 -(uint64_t)Offset); 3356 if (C->getType() != OpTy) 3357 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 3358 OpTy, false), 3359 C, OpTy); 3360 3361 CI->setOperand(1, C); 3362 } 3363 } 3364 3365 return FullV; 3366} 3367 3368/// RewriteForPHI - Helper for Rewrite. PHI nodes are special because the use 3369/// of their operands effectively happens in their predecessor blocks, so the 3370/// expression may need to be expanded in multiple places. 3371void LSRInstance::RewriteForPHI(PHINode *PN, 3372 const LSRFixup &LF, 3373 const Formula &F, 3374 SCEVExpander &Rewriter, 3375 SmallVectorImpl<WeakVH> &DeadInsts, 3376 Pass *P) const { 3377 DenseMap<BasicBlock *, Value *> Inserted; 3378 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 3379 if (PN->getIncomingValue(i) == LF.OperandValToReplace) { 3380 BasicBlock *BB = PN->getIncomingBlock(i); 3381 3382 // If this is a critical edge, split the edge so that we do not insert 3383 // the code on all predecessor/successor paths. We do this unless this 3384 // is the canonical backedge for this loop, which complicates post-inc 3385 // users. 3386 if (e != 1 && BB->getTerminator()->getNumSuccessors() > 1 && 3387 !isa<IndirectBrInst>(BB->getTerminator()) && 3388 (PN->getParent() != L->getHeader() || !L->contains(BB))) { 3389 // Split the critical edge. 3390 BasicBlock *NewBB = SplitCriticalEdge(BB, PN->getParent(), P); 3391 3392 // If PN is outside of the loop and BB is in the loop, we want to 3393 // move the block to be immediately before the PHI block, not 3394 // immediately after BB. 3395 if (L->contains(BB) && !L->contains(PN)) 3396 NewBB->moveBefore(PN->getParent()); 3397 3398 // Splitting the edge can reduce the number of PHI entries we have. 3399 e = PN->getNumIncomingValues(); 3400 BB = NewBB; 3401 i = PN->getBasicBlockIndex(BB); 3402 } 3403 3404 std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> Pair = 3405 Inserted.insert(std::make_pair(BB, static_cast<Value *>(0))); 3406 if (!Pair.second) 3407 PN->setIncomingValue(i, Pair.first->second); 3408 else { 3409 Value *FullV = Expand(LF, F, BB->getTerminator(), Rewriter, DeadInsts); 3410 3411 // If this is reuse-by-noop-cast, insert the noop cast. 3412 const Type *OpTy = LF.OperandValToReplace->getType(); 3413 if (FullV->getType() != OpTy) 3414 FullV = 3415 CastInst::Create(CastInst::getCastOpcode(FullV, false, 3416 OpTy, false), 3417 FullV, LF.OperandValToReplace->getType(), 3418 "tmp", BB->getTerminator()); 3419 3420 PN->setIncomingValue(i, FullV); 3421 Pair.first->second = FullV; 3422 } 3423 } 3424} 3425 3426/// Rewrite - Emit instructions for the leading candidate expression for this 3427/// LSRUse (this is called "expanding"), and update the UserInst to reference 3428/// the newly expanded value. 3429void LSRInstance::Rewrite(const LSRFixup &LF, 3430 const Formula &F, 3431 SCEVExpander &Rewriter, 3432 SmallVectorImpl<WeakVH> &DeadInsts, 3433 Pass *P) const { 3434 // First, find an insertion point that dominates UserInst. For PHI nodes, 3435 // find the nearest block which dominates all the relevant uses. 3436 if (PHINode *PN = dyn_cast<PHINode>(LF.UserInst)) { 3437 RewriteForPHI(PN, LF, F, Rewriter, DeadInsts, P); 3438 } else { 3439 Value *FullV = Expand(LF, F, LF.UserInst, Rewriter, DeadInsts); 3440 3441 // If this is reuse-by-noop-cast, insert the noop cast. 3442 const Type *OpTy = LF.OperandValToReplace->getType(); 3443 if (FullV->getType() != OpTy) { 3444 Instruction *Cast = 3445 CastInst::Create(CastInst::getCastOpcode(FullV, false, OpTy, false), 3446 FullV, OpTy, "tmp", LF.UserInst); 3447 FullV = Cast; 3448 } 3449 3450 // Update the user. ICmpZero is handled specially here (for now) because 3451 // Expand may have updated one of the operands of the icmp already, and 3452 // its new value may happen to be equal to LF.OperandValToReplace, in 3453 // which case doing replaceUsesOfWith leads to replacing both operands 3454 // with the same value. TODO: Reorganize this. 3455 if (Uses[LF.LUIdx].Kind == LSRUse::ICmpZero) 3456 LF.UserInst->setOperand(0, FullV); 3457 else 3458 LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV); 3459 } 3460 3461 DeadInsts.push_back(LF.OperandValToReplace); 3462} 3463 3464void 3465LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution, 3466 Pass *P) { 3467 // Keep track of instructions we may have made dead, so that 3468 // we can remove them after we are done working. 3469 SmallVector<WeakVH, 16> DeadInsts; 3470 3471 SCEVExpander Rewriter(SE); 3472 Rewriter.disableCanonicalMode(); 3473 Rewriter.setIVIncInsertPos(L, IVIncInsertPos); 3474 3475 // Expand the new value definitions and update the users. 3476 for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), 3477 E = Fixups.end(); I != E; ++I) { 3478 const LSRFixup &Fixup = *I; 3479 3480 Rewrite(Fixup, *Solution[Fixup.LUIdx], Rewriter, DeadInsts, P); 3481 3482 Changed = true; 3483 } 3484 3485 // Clean up after ourselves. This must be done before deleting any 3486 // instructions. 3487 Rewriter.clear(); 3488 3489 Changed |= DeleteTriviallyDeadInstructions(DeadInsts); 3490} 3491 3492LSRInstance::LSRInstance(const TargetLowering *tli, Loop *l, Pass *P) 3493 : IU(P->getAnalysis<IVUsers>()), 3494 SE(P->getAnalysis<ScalarEvolution>()), 3495 DT(P->getAnalysis<DominatorTree>()), 3496 LI(P->getAnalysis<LoopInfo>()), 3497 TLI(tli), L(l), Changed(false), IVIncInsertPos(0) { 3498 3499 // If LoopSimplify form is not available, stay out of trouble. 3500 if (!L->isLoopSimplifyForm()) return; 3501 3502 // If there's no interesting work to be done, bail early. 3503 if (IU.empty()) return; 3504 3505 DEBUG(dbgs() << "\nLSR on loop "; 3506 WriteAsOperand(dbgs(), L->getHeader(), /*PrintType=*/false); 3507 dbgs() << ":\n"); 3508 3509 // First, perform some low-level loop optimizations. 3510 OptimizeShadowIV(); 3511 OptimizeLoopTermCond(); 3512 3513 // Start collecting data and preparing for the solver. 3514 CollectInterestingTypesAndFactors(); 3515 CollectFixupsAndInitialFormulae(); 3516 CollectLoopInvariantFixupsAndFormulae(); 3517 3518 DEBUG(dbgs() << "LSR found " << Uses.size() << " uses:\n"; 3519 print_uses(dbgs())); 3520 3521 // Now use the reuse data to generate a bunch of interesting ways 3522 // to formulate the values needed for the uses. 3523 GenerateAllReuseFormulae(); 3524 3525 DEBUG(dbgs() << "\n" 3526 "After generating reuse formulae:\n"; 3527 print_uses(dbgs())); 3528 3529 FilterOutUndesirableDedicatedRegisters(); 3530 NarrowSearchSpaceUsingHeuristics(); 3531 3532 SmallVector<const Formula *, 8> Solution; 3533 Solve(Solution); 3534 assert(Solution.size() == Uses.size() && "Malformed solution!"); 3535 3536 // Release memory that is no longer needed. 3537 Factors.clear(); 3538 Types.clear(); 3539 RegUses.clear(); 3540 3541#ifndef NDEBUG 3542 // Formulae should be legal. 3543 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 3544 E = Uses.end(); I != E; ++I) { 3545 const LSRUse &LU = *I; 3546 for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), 3547 JE = LU.Formulae.end(); J != JE; ++J) 3548 assert(isLegalUse(J->AM, LU.MinOffset, LU.MaxOffset, 3549 LU.Kind, LU.AccessTy, TLI) && 3550 "Illegal formula generated!"); 3551 }; 3552#endif 3553 3554 // Now that we've decided what we want, make it so. 3555 ImplementSolution(Solution, P); 3556} 3557 3558void LSRInstance::print_factors_and_types(raw_ostream &OS) const { 3559 if (Factors.empty() && Types.empty()) return; 3560 3561 OS << "LSR has identified the following interesting factors and types: "; 3562 bool First = true; 3563 3564 for (SmallSetVector<int64_t, 8>::const_iterator 3565 I = Factors.begin(), E = Factors.end(); I != E; ++I) { 3566 if (!First) OS << ", "; 3567 First = false; 3568 OS << '*' << *I; 3569 } 3570 3571 for (SmallSetVector<const Type *, 4>::const_iterator 3572 I = Types.begin(), E = Types.end(); I != E; ++I) { 3573 if (!First) OS << ", "; 3574 First = false; 3575 OS << '(' << **I << ')'; 3576 } 3577 OS << '\n'; 3578} 3579 3580void LSRInstance::print_fixups(raw_ostream &OS) const { 3581 OS << "LSR is examining the following fixup sites:\n"; 3582 for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(), 3583 E = Fixups.end(); I != E; ++I) { 3584 const LSRFixup &LF = *I; 3585 dbgs() << " "; 3586 LF.print(OS); 3587 OS << '\n'; 3588 } 3589} 3590 3591void LSRInstance::print_uses(raw_ostream &OS) const { 3592 OS << "LSR is examining the following uses:\n"; 3593 for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(), 3594 E = Uses.end(); I != E; ++I) { 3595 const LSRUse &LU = *I; 3596 dbgs() << " "; 3597 LU.print(OS); 3598 OS << '\n'; 3599 for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(), 3600 JE = LU.Formulae.end(); J != JE; ++J) { 3601 OS << " "; 3602 J->print(OS); 3603 OS << '\n'; 3604 } 3605 } 3606} 3607 3608void LSRInstance::print(raw_ostream &OS) const { 3609 print_factors_and_types(OS); 3610 print_fixups(OS); 3611 print_uses(OS); 3612} 3613 3614void LSRInstance::dump() const { 3615 print(errs()); errs() << '\n'; 3616} 3617 3618namespace { 3619 3620class LoopStrengthReduce : public LoopPass { 3621 /// TLI - Keep a pointer of a TargetLowering to consult for determining 3622 /// transformation profitability. 3623 const TargetLowering *const TLI; 3624 3625public: 3626 static char ID; // Pass ID, replacement for typeid 3627 explicit LoopStrengthReduce(const TargetLowering *tli = 0); 3628 3629private: 3630 bool runOnLoop(Loop *L, LPPassManager &LPM); 3631 void getAnalysisUsage(AnalysisUsage &AU) const; 3632}; 3633 3634} 3635 3636char LoopStrengthReduce::ID = 0; 3637static RegisterPass<LoopStrengthReduce> 3638X("loop-reduce", "Loop Strength Reduction"); 3639 3640Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) { 3641 return new LoopStrengthReduce(TLI); 3642} 3643 3644LoopStrengthReduce::LoopStrengthReduce(const TargetLowering *tli) 3645 : LoopPass(&ID), TLI(tli) {} 3646 3647void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { 3648 // We split critical edges, so we change the CFG. However, we do update 3649 // many analyses if they are around. 3650 AU.addPreservedID(LoopSimplifyID); 3651 AU.addPreserved("domfrontier"); 3652 3653 AU.addRequired<LoopInfo>(); 3654 AU.addPreserved<LoopInfo>(); 3655 AU.addRequiredID(LoopSimplifyID); 3656 AU.addRequired<DominatorTree>(); 3657 AU.addPreserved<DominatorTree>(); 3658 AU.addRequired<ScalarEvolution>(); 3659 AU.addPreserved<ScalarEvolution>(); 3660 AU.addRequired<IVUsers>(); 3661 AU.addPreserved<IVUsers>(); 3662} 3663 3664bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { 3665 bool Changed = false; 3666 3667 // Run the main LSR transformation. 3668 Changed |= LSRInstance(TLI, L, this).getChanged(); 3669 3670 // At this point, it is worth checking to see if any recurrence PHIs are also 3671 // dead, so that we can remove them as well. 3672 Changed |= DeleteDeadPHIs(L->getHeader()); 3673 3674 return Changed; 3675} 3676