MachineLICM.cpp revision 348856e56a247c9815986be51565551394f9e9c2
1//===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===// 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 pass performs loop invariant code motion on machine instructions. We 11// attempt to remove as much code from the body of a loop as possible. 12// 13// This pass does not attempt to throttle itself to limit register pressure. 14// The register allocation phases are expected to perform rematerialization 15// to recover when register pressure is high. 16// 17// This pass is not intended to be a replacement or a complete alternative 18// for the LLVM-IR-level LICM pass. It is only designed to hoist simple 19// constructs that are not exposed before lowering and instruction selection. 20// 21//===----------------------------------------------------------------------===// 22 23#define DEBUG_TYPE "machine-licm" 24#include "llvm/CodeGen/Passes.h" 25#include "llvm/CodeGen/MachineDominators.h" 26#include "llvm/CodeGen/MachineFrameInfo.h" 27#include "llvm/CodeGen/MachineLoopInfo.h" 28#include "llvm/CodeGen/MachineMemOperand.h" 29#include "llvm/CodeGen/MachineRegisterInfo.h" 30#include "llvm/CodeGen/PseudoSourceValue.h" 31#include "llvm/Target/TargetRegisterInfo.h" 32#include "llvm/Target/TargetInstrInfo.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/Analysis/AliasAnalysis.h" 35#include "llvm/ADT/DenseMap.h" 36#include "llvm/ADT/SmallSet.h" 37#include "llvm/ADT/Statistic.h" 38#include "llvm/Support/Debug.h" 39#include "llvm/Support/raw_ostream.h" 40 41using namespace llvm; 42 43STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 44STATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed"); 45STATISTIC(NumPostRAHoisted, 46 "Number of machine instructions hoisted out of loops post regalloc"); 47 48namespace { 49 class MachineLICM : public MachineFunctionPass { 50 bool PreRegAlloc; 51 52 const TargetMachine *TM; 53 const TargetInstrInfo *TII; 54 const TargetRegisterInfo *TRI; 55 const MachineFrameInfo *MFI; 56 MachineRegisterInfo *RegInfo; 57 58 // Various analyses that we use... 59 AliasAnalysis *AA; // Alias analysis info. 60 MachineLoopInfo *LI; // Current MachineLoopInfo 61 MachineDominatorTree *DT; // Machine dominator tree for the cur loop 62 63 // State that is updated as we process loops 64 bool Changed; // True if a loop is changed. 65 bool FirstInLoop; // True if it's the first LICM in the loop. 66 MachineLoop *CurLoop; // The current loop we are working on. 67 MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 68 69 BitVector AllocatableSet; 70 71 // For each opcode, keep a list of potentail CSE instructions. 72 DenseMap<unsigned, std::vector<const MachineInstr*> > CSEMap; 73 74 public: 75 static char ID; // Pass identification, replacement for typeid 76 MachineLICM() : 77 MachineFunctionPass(&ID), PreRegAlloc(true) {} 78 79 explicit MachineLICM(bool PreRA) : 80 MachineFunctionPass(&ID), PreRegAlloc(PreRA) {} 81 82 virtual bool runOnMachineFunction(MachineFunction &MF); 83 84 const char *getPassName() const { return "Machine Instruction LICM"; } 85 86 // FIXME: Loop preheaders? 87 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 88 AU.setPreservesCFG(); 89 AU.addRequired<MachineLoopInfo>(); 90 AU.addRequired<MachineDominatorTree>(); 91 AU.addRequired<AliasAnalysis>(); 92 AU.addPreserved<MachineLoopInfo>(); 93 AU.addPreserved<MachineDominatorTree>(); 94 MachineFunctionPass::getAnalysisUsage(AU); 95 } 96 97 virtual void releaseMemory() { 98 CSEMap.clear(); 99 } 100 101 private: 102 /// IsLoopInvariantInst - Returns true if the instruction is loop 103 /// invariant. I.e., all virtual register operands are defined outside of 104 /// the loop, physical registers aren't accessed (explicitly or implicitly), 105 /// and the instruction is hoistable. 106 /// 107 bool IsLoopInvariantInst(MachineInstr &I); 108 109 /// IsProfitableToHoist - Return true if it is potentially profitable to 110 /// hoist the given loop invariant. 111 bool IsProfitableToHoist(MachineInstr &MI); 112 113 /// HoistRegion - Walk the specified region of the CFG (defined by all 114 /// blocks dominated by the specified block, and that are in the current 115 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 116 /// visit definitions before uses, allowing us to hoist a loop body in one 117 /// pass without iteration. 118 /// 119 void HoistRegion(MachineDomTreeNode *N); 120 void HoistRegionPostRA(MachineDomTreeNode *N); 121 122 /// isLoadFromConstantMemory - Return true if the given instruction is a 123 /// load from constant memory. 124 bool isLoadFromConstantMemory(MachineInstr *MI); 125 126 /// ExtractHoistableLoad - Unfold a load from the given machineinstr if 127 /// the load itself could be hoisted. Return the unfolded and hoistable 128 /// load, or null if the load couldn't be unfolded or if it wouldn't 129 /// be hoistable. 130 MachineInstr *ExtractHoistableLoad(MachineInstr *MI); 131 132 /// LookForDuplicate - Find an instruction amount PrevMIs that is a 133 /// duplicate of MI. Return this instruction if it's found. 134 const MachineInstr *LookForDuplicate(const MachineInstr *MI, 135 std::vector<const MachineInstr*> &PrevMIs); 136 137 /// EliminateCSE - Given a LICM'ed instruction, look for an instruction on 138 /// the preheader that compute the same value. If it's found, do a RAU on 139 /// with the definition of the existing instruction rather than hoisting 140 /// the instruction to the preheader. 141 bool EliminateCSE(MachineInstr *MI, 142 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI); 143 144 /// Hoist - When an instruction is found to only use loop invariant operands 145 /// that is safe to hoist, this instruction is called to do the dirty work. 146 /// 147 void Hoist(MachineInstr *MI); 148 void HoistPostRA(MachineInstr *MI); 149 150 /// InitCSEMap - Initialize the CSE map with instructions that are in the 151 /// current loop preheader that may become duplicates of instructions that 152 /// are hoisted out of the loop. 153 void InitCSEMap(MachineBasicBlock *BB); 154 }; 155} // end anonymous namespace 156 157char MachineLICM::ID = 0; 158static RegisterPass<MachineLICM> 159X("machinelicm", "Machine Loop Invariant Code Motion"); 160 161FunctionPass *llvm::createMachineLICMPass(bool PreRegAlloc) { 162 return new MachineLICM(PreRegAlloc); 163} 164 165/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 166/// loop that has a preheader. 167static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 168 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 169 if (L->getLoopPreheader()) 170 return false; 171 return true; 172} 173 174/// Hoist expressions out of the specified loop. Note, alias info for inner loop 175/// is not preserved so it is not a good idea to run LICM multiple times on one 176/// loop. 177/// 178bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 179 if (PreRegAlloc) 180 DEBUG(dbgs() << "******** Pre-regalloc Machine LICM ********\n"); 181 else 182 DEBUG(dbgs() << "******** Post-regalloc Machine LICM ********\n"); 183 184 Changed = FirstInLoop = false; 185 TM = &MF.getTarget(); 186 TII = TM->getInstrInfo(); 187 TRI = TM->getRegisterInfo(); 188 MFI = MF.getFrameInfo(); 189 RegInfo = &MF.getRegInfo(); 190 AllocatableSet = TRI->getAllocatableSet(MF); 191 192 // Get our Loop information... 193 LI = &getAnalysis<MachineLoopInfo>(); 194 DT = &getAnalysis<MachineDominatorTree>(); 195 AA = &getAnalysis<AliasAnalysis>(); 196 197 for (MachineLoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 198 CurLoop = *I; 199 200 // Only visit outer-most preheader-sporting loops. 201 if (!LoopIsOuterMostWithPreheader(CurLoop)) 202 continue; 203 204 // Determine the block to which to hoist instructions. If we can't find a 205 // suitable loop preheader, we can't do any hoisting. 206 // 207 // FIXME: We are only hoisting if the basic block coming into this loop 208 // has only one successor. This isn't the case in general because we haven't 209 // broken critical edges or added preheaders. 210 CurPreheader = CurLoop->getLoopPreheader(); 211 if (!CurPreheader) 212 continue; 213 214 // CSEMap is initialized for loop header when the first instruction is 215 // being hoisted. 216 FirstInLoop = true; 217 MachineDomTreeNode *N = DT->getNode(CurLoop->getHeader()); 218 if (!PreRegAlloc) 219 HoistRegionPostRA(N); 220 else { 221 HoistRegion(N); 222 CSEMap.clear(); 223 } 224 } 225 226 return Changed; 227} 228 229void MachineLICM::HoistRegionPostRA(MachineDomTreeNode *N) { 230 assert(N != 0 && "Null dominator tree node?"); 231 232 unsigned NumRegs = TRI->getNumRegs(); 233 unsigned *PhysRegDefs = new unsigned[NumRegs]; 234 std::fill(PhysRegDefs, PhysRegDefs + NumRegs, 0); 235 236 SmallVector<std::pair<MachineInstr*, int>, 32> Candidates; 237 SmallSet<int, 32> StoredFIs; 238 239 // Walk the entire region, count number of defs for each register, and 240 // return potential LICM candidates. 241 SmallVector<MachineDomTreeNode*, 8> WorkList; 242 WorkList.push_back(N); 243 do { 244 N = WorkList.pop_back_val(); 245 MachineBasicBlock *BB = N->getBlock(); 246 247 if (!CurLoop->contains(BB)) 248 continue; 249 // Conservatively treat live-in's as an external def. 250 for (MachineBasicBlock::const_livein_iterator I = BB->livein_begin(), 251 E = BB->livein_end(); I != E; ++I) { 252 unsigned Reg = *I; 253 ++PhysRegDefs[Reg]; 254 for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) 255 ++PhysRegDefs[*SR]; 256 } 257 258 for (MachineBasicBlock::iterator 259 MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 260 bool RuledOut = false; 261 bool SeenDef = false; 262 MachineInstr *MI = &*MII; 263 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 264 const MachineOperand &MO = MI->getOperand(i); 265 if (!MO.isReg()) 266 continue; 267 unsigned Reg = MO.getReg(); 268 if (!Reg) 269 continue; 270 assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 271 "Not expecting virtual register!"); 272 273 if (MO.isDef()) { 274 SeenDef = true; 275 if (++PhysRegDefs[Reg] > 1) 276 // MI defined register is seen defined by another instruction in 277 // the loop, it cannot be a LICM candidate. 278 RuledOut = true; 279 for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) 280 if (++PhysRegDefs[*SR] > 1) 281 RuledOut = true; 282 } 283 } 284 285 // FIXME: Only consider reloads for now. 286 bool SkipCheck = false; 287 int FI; 288 if (SeenDef && !RuledOut) { 289 if (TII->isLoadFromStackSlot(MI, FI) && 290 MFI->isSpillSlotObjectIndex(FI)) { 291 Candidates.push_back(std::make_pair(MI, FI)); 292 SkipCheck = true; 293 } 294 } 295 296 // If MI is a store to a stack slot, remember the slot. An instruction 297 // loads from this slot cannot be a LICM candidate. 298 if (!SkipCheck && TII->isStoreToStackSlot(MI, FI)) 299 StoredFIs.insert(FI); 300 } 301 302 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 303 for (unsigned I = 0, E = Children.size(); I != E; ++I) 304 WorkList.push_back(Children[I]); 305 } while (!WorkList.empty()); 306 307 // Now evaluate whether the potential candidates qualify. 308 // 1. Check if the candidate defined register is defined by another 309 // instruction in the loop. 310 // 2. If the candidate is a load from stack slot (always true for now), 311 // check if the slot is stored anywhere in the loop. 312 for (unsigned i = 0, e = Candidates.size(); i != e; ++i) { 313 bool Safe = true; 314 int FI = Candidates[i].second; 315 if (StoredFIs.count(FI)) 316 continue; 317 318 MachineInstr *MI = Candidates[i].first; 319 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 320 const MachineOperand &MO = MI->getOperand(j); 321 if (!MO.isReg()) 322 continue; 323 unsigned Reg = MO.getReg(); 324 if (!Reg) 325 continue; 326 if (MO.isDef() && PhysRegDefs[Reg] > 1) { 327 Safe = false; 328 break; 329 } 330 } 331 332 if (Safe) 333 HoistPostRA(MI); 334 } 335} 336 337void MachineLICM::HoistPostRA(MachineInstr *MI) { 338 // Now move the instructions to the predecessor, inserting it before any 339 // terminator instructions. 340 DEBUG({ 341 dbgs() << "Hoisting " << *MI; 342 if (CurPreheader->getBasicBlock()) 343 dbgs() << " to MachineBasicBlock " 344 << CurPreheader->getName(); 345 if (MI->getParent()->getBasicBlock()) 346 dbgs() << " from MachineBasicBlock " 347 << MI->getParent()->getName(); 348 dbgs() << "\n"; 349 }); 350 351 // Splice the instruction to the preheader. 352 CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI); 353 354 ++NumPostRAHoisted; 355 Changed = true; 356} 357 358/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 359/// dominated by the specified block, and that are in the current loop) in depth 360/// first order w.r.t the DominatorTree. This allows us to visit definitions 361/// before uses, allowing us to hoist a loop body in one pass without iteration. 362/// 363void MachineLICM::HoistRegion(MachineDomTreeNode *N) { 364 assert(N != 0 && "Null dominator tree node?"); 365 MachineBasicBlock *BB = N->getBlock(); 366 367 // If this subregion is not in the top level loop at all, exit. 368 if (!CurLoop->contains(BB)) return; 369 370 for (MachineBasicBlock::iterator 371 MII = BB->begin(), E = BB->end(); MII != E; ) { 372 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 373 Hoist(&*MII); 374 MII = NextMII; 375 } 376 377 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 378 for (unsigned I = 0, E = Children.size(); I != E; ++I) 379 HoistRegion(Children[I]); 380} 381 382/// IsLoopInvariantInst - Returns true if the instruction is loop 383/// invariant. I.e., all virtual register operands are defined outside of the 384/// loop, physical registers aren't accessed explicitly, and there are no side 385/// effects that aren't captured by the operands or other flags. 386/// 387bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 388 const TargetInstrDesc &TID = I.getDesc(); 389 390 // Ignore stuff that we obviously can't hoist. 391 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 392 TID.hasUnmodeledSideEffects()) 393 return false; 394 395 if (TID.mayLoad()) { 396 // Okay, this instruction does a load. As a refinement, we allow the target 397 // to decide whether the loaded value is actually a constant. If so, we can 398 // actually use it as a load. 399 if (!I.isInvariantLoad(AA)) 400 // FIXME: we should be able to hoist loads with no other side effects if 401 // there are no other instructions which can change memory in this loop. 402 // This is a trivial form of alias analysis. 403 return false; 404 } 405 406 // The instruction is loop invariant if all of its operands are. 407 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 408 const MachineOperand &MO = I.getOperand(i); 409 410 if (!MO.isReg()) 411 continue; 412 413 unsigned Reg = MO.getReg(); 414 if (Reg == 0) continue; 415 416 // Don't hoist an instruction that uses or defines a physical register. 417 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 418 if (MO.isUse()) { 419 // If the physreg has no defs anywhere, it's just an ambient register 420 // and we can freely move its uses. Alternatively, if it's allocatable, 421 // it could get allocated to something with a def during allocation. 422 if (!RegInfo->def_empty(Reg)) 423 return false; 424 if (AllocatableSet.test(Reg)) 425 return false; 426 // Check for a def among the register's aliases too. 427 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 428 unsigned AliasReg = *Alias; 429 if (!RegInfo->def_empty(AliasReg)) 430 return false; 431 if (AllocatableSet.test(AliasReg)) 432 return false; 433 } 434 // Otherwise it's safe to move. 435 continue; 436 } else if (!MO.isDead()) { 437 // A def that isn't dead. We can't move it. 438 return false; 439 } else if (CurLoop->getHeader()->isLiveIn(Reg)) { 440 // If the reg is live into the loop, we can't hoist an instruction 441 // which would clobber it. 442 return false; 443 } 444 } 445 446 if (!MO.isUse()) 447 continue; 448 449 assert(RegInfo->getVRegDef(Reg) && 450 "Machine instr not mapped for this vreg?!"); 451 452 // If the loop contains the definition of an operand, then the instruction 453 // isn't loop invariant. 454 if (CurLoop->contains(RegInfo->getVRegDef(Reg))) 455 return false; 456 } 457 458 // If we got this far, the instruction is loop invariant! 459 return true; 460} 461 462 463/// HasPHIUses - Return true if the specified register has any PHI use. 464static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 465 for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 466 UE = RegInfo->use_end(); UI != UE; ++UI) { 467 MachineInstr *UseMI = &*UI; 468 if (UseMI->isPHI()) 469 return true; 470 } 471 return false; 472} 473 474/// isLoadFromConstantMemory - Return true if the given instruction is a 475/// load from constant memory. Machine LICM will hoist these even if they are 476/// not re-materializable. 477bool MachineLICM::isLoadFromConstantMemory(MachineInstr *MI) { 478 if (!MI->getDesc().mayLoad()) return false; 479 if (!MI->hasOneMemOperand()) return false; 480 MachineMemOperand *MMO = *MI->memoperands_begin(); 481 if (MMO->isVolatile()) return false; 482 if (!MMO->getValue()) return false; 483 const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(MMO->getValue()); 484 if (PSV) { 485 MachineFunction &MF = *MI->getParent()->getParent(); 486 return PSV->isConstant(MF.getFrameInfo()); 487 } else { 488 return AA->pointsToConstantMemory(MMO->getValue()); 489 } 490} 491 492/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 493/// the given loop invariant. 494bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 495 if (MI.isImplicitDef()) 496 return false; 497 498 // FIXME: For now, only hoist re-materilizable instructions. LICM will 499 // increase register pressure. We want to make sure it doesn't increase 500 // spilling. 501 // Also hoist loads from constant memory, e.g. load from stubs, GOT. Hoisting 502 // these tend to help performance in low register pressure situation. The 503 // trade off is it may cause spill in high pressure situation. It will end up 504 // adding a store in the loop preheader. But the reload is no more expensive. 505 // The side benefit is these loads are frequently CSE'ed. 506 if (!TII->isTriviallyReMaterializable(&MI, AA)) { 507 if (!isLoadFromConstantMemory(&MI)) 508 return false; 509 } 510 511 // If result(s) of this instruction is used by PHIs, then don't hoist it. 512 // The presence of joins makes it difficult for current register allocator 513 // implementation to perform remat. 514 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 515 const MachineOperand &MO = MI.getOperand(i); 516 if (!MO.isReg() || !MO.isDef()) 517 continue; 518 if (HasPHIUses(MO.getReg(), RegInfo)) 519 return false; 520 } 521 522 return true; 523} 524 525MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { 526 // If not, we may be able to unfold a load and hoist that. 527 // First test whether the instruction is loading from an amenable 528 // memory location. 529 if (!isLoadFromConstantMemory(MI)) 530 return 0; 531 532 // Next determine the register class for a temporary register. 533 unsigned LoadRegIndex; 534 unsigned NewOpc = 535 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 536 /*UnfoldLoad=*/true, 537 /*UnfoldStore=*/false, 538 &LoadRegIndex); 539 if (NewOpc == 0) return 0; 540 const TargetInstrDesc &TID = TII->get(NewOpc); 541 if (TID.getNumDefs() != 1) return 0; 542 const TargetRegisterClass *RC = TID.OpInfo[LoadRegIndex].getRegClass(TRI); 543 // Ok, we're unfolding. Create a temporary register and do the unfold. 544 unsigned Reg = RegInfo->createVirtualRegister(RC); 545 546 MachineFunction &MF = *MI->getParent()->getParent(); 547 SmallVector<MachineInstr *, 2> NewMIs; 548 bool Success = 549 TII->unfoldMemoryOperand(MF, MI, Reg, 550 /*UnfoldLoad=*/true, /*UnfoldStore=*/false, 551 NewMIs); 552 (void)Success; 553 assert(Success && 554 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 555 "succeeded!"); 556 assert(NewMIs.size() == 2 && 557 "Unfolded a load into multiple instructions!"); 558 MachineBasicBlock *MBB = MI->getParent(); 559 MBB->insert(MI, NewMIs[0]); 560 MBB->insert(MI, NewMIs[1]); 561 // If unfolding produced a load that wasn't loop-invariant or profitable to 562 // hoist, discard the new instructions and bail. 563 if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 564 NewMIs[0]->eraseFromParent(); 565 NewMIs[1]->eraseFromParent(); 566 return 0; 567 } 568 // Otherwise we successfully unfolded a load that we can hoist. 569 MI->eraseFromParent(); 570 return NewMIs[0]; 571} 572 573void MachineLICM::InitCSEMap(MachineBasicBlock *BB) { 574 for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) { 575 const MachineInstr *MI = &*I; 576 // FIXME: For now, only hoist re-materilizable instructions. LICM will 577 // increase register pressure. We want to make sure it doesn't increase 578 // spilling. 579 if (TII->isTriviallyReMaterializable(MI, AA)) { 580 unsigned Opcode = MI->getOpcode(); 581 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 582 CI = CSEMap.find(Opcode); 583 if (CI != CSEMap.end()) 584 CI->second.push_back(MI); 585 else { 586 std::vector<const MachineInstr*> CSEMIs; 587 CSEMIs.push_back(MI); 588 CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 589 } 590 } 591 } 592} 593 594const MachineInstr* 595MachineLICM::LookForDuplicate(const MachineInstr *MI, 596 std::vector<const MachineInstr*> &PrevMIs) { 597 for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 598 const MachineInstr *PrevMI = PrevMIs[i]; 599 if (TII->produceSameValue(MI, PrevMI)) 600 return PrevMI; 601 } 602 return 0; 603} 604 605bool MachineLICM::EliminateCSE(MachineInstr *MI, 606 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) { 607 if (CI == CSEMap.end()) 608 return false; 609 610 if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 611 DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 612 613 // Replace virtual registers defined by MI by their counterparts defined 614 // by Dup. 615 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 616 const MachineOperand &MO = MI->getOperand(i); 617 618 // Physical registers may not differ here. 619 assert((!MO.isReg() || MO.getReg() == 0 || 620 !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || 621 MO.getReg() == Dup->getOperand(i).getReg()) && 622 "Instructions with different phys regs are not identical!"); 623 624 if (MO.isReg() && MO.isDef() && 625 !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) 626 RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 627 } 628 MI->eraseFromParent(); 629 ++NumCSEed; 630 return true; 631 } 632 return false; 633} 634 635/// Hoist - When an instruction is found to use only loop invariant operands 636/// that are safe to hoist, this instruction is called to do the dirty work. 637/// 638void MachineLICM::Hoist(MachineInstr *MI) { 639 // First check whether we should hoist this instruction. 640 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 641 // If not, try unfolding a hoistable load. 642 MI = ExtractHoistableLoad(MI); 643 if (!MI) return; 644 } 645 646 // Now move the instructions to the predecessor, inserting it before any 647 // terminator instructions. 648 DEBUG({ 649 dbgs() << "Hoisting " << *MI; 650 if (CurPreheader->getBasicBlock()) 651 dbgs() << " to MachineBasicBlock " 652 << CurPreheader->getName(); 653 if (MI->getParent()->getBasicBlock()) 654 dbgs() << " from MachineBasicBlock " 655 << MI->getParent()->getName(); 656 dbgs() << "\n"; 657 }); 658 659 // If this is the first instruction being hoisted to the preheader, 660 // initialize the CSE map with potential common expressions. 661 InitCSEMap(CurPreheader); 662 663 // Look for opportunity to CSE the hoisted instruction. 664 unsigned Opcode = MI->getOpcode(); 665 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 666 CI = CSEMap.find(Opcode); 667 if (!EliminateCSE(MI, CI)) { 668 // Otherwise, splice the instruction to the preheader. 669 CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI); 670 671 // Add to the CSE map. 672 if (CI != CSEMap.end()) 673 CI->second.push_back(MI); 674 else { 675 std::vector<const MachineInstr*> CSEMIs; 676 CSEMIs.push_back(MI); 677 CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 678 } 679 } 680 681 ++NumHoisted; 682 Changed = true; 683} 684