MachineLICM.cpp revision 5b463905be11f8c89bf3a7a777eb5d0c7be7162d
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 // FIXME: That means a reload that's reused into a fallthrough block 251 // will not be LICM'ed. 252 for (MachineBasicBlock::const_livein_iterator I = BB->livein_begin(), 253 E = BB->livein_end(); I != E; ++I) { 254 unsigned Reg = *I; 255 ++PhysRegDefs[Reg]; 256 for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) 257 ++PhysRegDefs[*SR]; 258 } 259 260 for (MachineBasicBlock::iterator 261 MII = BB->begin(), E = BB->end(); MII != E; ++MII) { 262 bool RuledOut = false; 263 bool SeenDef = false; 264 MachineInstr *MI = &*MII; 265 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 266 const MachineOperand &MO = MI->getOperand(i); 267 if (!MO.isReg()) 268 continue; 269 unsigned Reg = MO.getReg(); 270 if (!Reg) 271 continue; 272 assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 273 "Not expecting virtual register!"); 274 275 if (MO.isDef()) { 276 SeenDef = true; 277 if (++PhysRegDefs[Reg] > 1) 278 // MI defined register is seen defined by another instruction in 279 // the loop, it cannot be a LICM candidate. 280 RuledOut = true; 281 for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) 282 if (++PhysRegDefs[*SR] > 1) 283 RuledOut = true; 284 } 285 } 286 287 // FIXME: Only consider reloads for now. We should be able to handle 288 // remat which does not have register operands. 289 bool SkipCheck = false; 290 int FI; 291 if (SeenDef && !RuledOut) { 292 if (TII->isLoadFromStackSlot(MI, FI) && 293 MFI->isSpillSlotObjectIndex(FI)) { 294 Candidates.push_back(std::make_pair(MI, FI)); 295 SkipCheck = true; 296 } 297 } 298 299 // If MI is a store to a stack slot, remember the slot. An instruction 300 // loads from this slot cannot be a LICM candidate. 301 if (!SkipCheck && TII->isStoreToStackSlot(MI, FI)) 302 StoredFIs.insert(FI); 303 } 304 305 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 306 for (unsigned I = 0, E = Children.size(); I != E; ++I) 307 WorkList.push_back(Children[I]); 308 } while (!WorkList.empty()); 309 310 // Now evaluate whether the potential candidates qualify. 311 // 1. Check if the candidate defined register is defined by another 312 // instruction in the loop. 313 // 2. If the candidate is a load from stack slot (always true for now), 314 // check if the slot is stored anywhere in the loop. 315 for (unsigned i = 0, e = Candidates.size(); i != e; ++i) { 316 bool Safe = true; 317 int FI = Candidates[i].second; 318 if (StoredFIs.count(FI)) 319 continue; 320 321 MachineInstr *MI = Candidates[i].first; 322 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 323 const MachineOperand &MO = MI->getOperand(j); 324 if (!MO.isReg()) 325 continue; 326 unsigned Reg = MO.getReg(); 327 if (!Reg) 328 continue; 329 if (MO.isDef() && PhysRegDefs[Reg] > 1) { 330 Safe = false; 331 break; 332 } 333 } 334 335 if (Safe) 336 HoistPostRA(MI); 337 } 338} 339 340void MachineLICM::HoistPostRA(MachineInstr *MI) { 341 // Now move the instructions to the predecessor, inserting it before any 342 // terminator instructions. 343 DEBUG({ 344 dbgs() << "Hoisting " << *MI; 345 if (CurPreheader->getBasicBlock()) 346 dbgs() << " to MachineBasicBlock " 347 << CurPreheader->getName(); 348 if (MI->getParent()->getBasicBlock()) 349 dbgs() << " from MachineBasicBlock " 350 << MI->getParent()->getName(); 351 dbgs() << "\n"; 352 }); 353 354 // Splice the instruction to the preheader. 355 CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI); 356 357 ++NumPostRAHoisted; 358 Changed = true; 359} 360 361/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 362/// dominated by the specified block, and that are in the current loop) in depth 363/// first order w.r.t the DominatorTree. This allows us to visit definitions 364/// before uses, allowing us to hoist a loop body in one pass without iteration. 365/// 366void MachineLICM::HoistRegion(MachineDomTreeNode *N) { 367 assert(N != 0 && "Null dominator tree node?"); 368 MachineBasicBlock *BB = N->getBlock(); 369 370 // If this subregion is not in the top level loop at all, exit. 371 if (!CurLoop->contains(BB)) return; 372 373 for (MachineBasicBlock::iterator 374 MII = BB->begin(), E = BB->end(); MII != E; ) { 375 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 376 Hoist(&*MII); 377 MII = NextMII; 378 } 379 380 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 381 for (unsigned I = 0, E = Children.size(); I != E; ++I) 382 HoistRegion(Children[I]); 383} 384 385/// IsLoopInvariantInst - Returns true if the instruction is loop 386/// invariant. I.e., all virtual register operands are defined outside of the 387/// loop, physical registers aren't accessed explicitly, and there are no side 388/// effects that aren't captured by the operands or other flags. 389/// 390bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 391 const TargetInstrDesc &TID = I.getDesc(); 392 393 // Ignore stuff that we obviously can't hoist. 394 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 395 TID.hasUnmodeledSideEffects()) 396 return false; 397 398 if (TID.mayLoad()) { 399 // Okay, this instruction does a load. As a refinement, we allow the target 400 // to decide whether the loaded value is actually a constant. If so, we can 401 // actually use it as a load. 402 if (!I.isInvariantLoad(AA)) 403 // FIXME: we should be able to hoist loads with no other side effects if 404 // there are no other instructions which can change memory in this loop. 405 // This is a trivial form of alias analysis. 406 return false; 407 } 408 409 // The instruction is loop invariant if all of its operands are. 410 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 411 const MachineOperand &MO = I.getOperand(i); 412 413 if (!MO.isReg()) 414 continue; 415 416 unsigned Reg = MO.getReg(); 417 if (Reg == 0) continue; 418 419 // Don't hoist an instruction that uses or defines a physical register. 420 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 421 if (MO.isUse()) { 422 // If the physreg has no defs anywhere, it's just an ambient register 423 // and we can freely move its uses. Alternatively, if it's allocatable, 424 // it could get allocated to something with a def during allocation. 425 if (!RegInfo->def_empty(Reg)) 426 return false; 427 if (AllocatableSet.test(Reg)) 428 return false; 429 // Check for a def among the register's aliases too. 430 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 431 unsigned AliasReg = *Alias; 432 if (!RegInfo->def_empty(AliasReg)) 433 return false; 434 if (AllocatableSet.test(AliasReg)) 435 return false; 436 } 437 // Otherwise it's safe to move. 438 continue; 439 } else if (!MO.isDead()) { 440 // A def that isn't dead. We can't move it. 441 return false; 442 } else if (CurLoop->getHeader()->isLiveIn(Reg)) { 443 // If the reg is live into the loop, we can't hoist an instruction 444 // which would clobber it. 445 return false; 446 } 447 } 448 449 if (!MO.isUse()) 450 continue; 451 452 assert(RegInfo->getVRegDef(Reg) && 453 "Machine instr not mapped for this vreg?!"); 454 455 // If the loop contains the definition of an operand, then the instruction 456 // isn't loop invariant. 457 if (CurLoop->contains(RegInfo->getVRegDef(Reg))) 458 return false; 459 } 460 461 // If we got this far, the instruction is loop invariant! 462 return true; 463} 464 465 466/// HasPHIUses - Return true if the specified register has any PHI use. 467static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 468 for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 469 UE = RegInfo->use_end(); UI != UE; ++UI) { 470 MachineInstr *UseMI = &*UI; 471 if (UseMI->isPHI()) 472 return true; 473 } 474 return false; 475} 476 477/// isLoadFromConstantMemory - Return true if the given instruction is a 478/// load from constant memory. Machine LICM will hoist these even if they are 479/// not re-materializable. 480bool MachineLICM::isLoadFromConstantMemory(MachineInstr *MI) { 481 if (!MI->getDesc().mayLoad()) return false; 482 if (!MI->hasOneMemOperand()) return false; 483 MachineMemOperand *MMO = *MI->memoperands_begin(); 484 if (MMO->isVolatile()) return false; 485 if (!MMO->getValue()) return false; 486 const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(MMO->getValue()); 487 if (PSV) { 488 MachineFunction &MF = *MI->getParent()->getParent(); 489 return PSV->isConstant(MF.getFrameInfo()); 490 } else { 491 return AA->pointsToConstantMemory(MMO->getValue()); 492 } 493} 494 495/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 496/// the given loop invariant. 497bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 498 if (MI.isImplicitDef()) 499 return false; 500 501 // FIXME: For now, only hoist re-materilizable instructions. LICM will 502 // increase register pressure. We want to make sure it doesn't increase 503 // spilling. 504 // Also hoist loads from constant memory, e.g. load from stubs, GOT. Hoisting 505 // these tend to help performance in low register pressure situation. The 506 // trade off is it may cause spill in high pressure situation. It will end up 507 // adding a store in the loop preheader. But the reload is no more expensive. 508 // The side benefit is these loads are frequently CSE'ed. 509 if (!TII->isTriviallyReMaterializable(&MI, AA)) { 510 if (!isLoadFromConstantMemory(&MI)) 511 return false; 512 } 513 514 // If result(s) of this instruction is used by PHIs, then don't hoist it. 515 // The presence of joins makes it difficult for current register allocator 516 // implementation to perform remat. 517 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 518 const MachineOperand &MO = MI.getOperand(i); 519 if (!MO.isReg() || !MO.isDef()) 520 continue; 521 if (HasPHIUses(MO.getReg(), RegInfo)) 522 return false; 523 } 524 525 return true; 526} 527 528MachineInstr *MachineLICM::ExtractHoistableLoad(MachineInstr *MI) { 529 // If not, we may be able to unfold a load and hoist that. 530 // First test whether the instruction is loading from an amenable 531 // memory location. 532 if (!isLoadFromConstantMemory(MI)) 533 return 0; 534 535 // Next determine the register class for a temporary register. 536 unsigned LoadRegIndex; 537 unsigned NewOpc = 538 TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), 539 /*UnfoldLoad=*/true, 540 /*UnfoldStore=*/false, 541 &LoadRegIndex); 542 if (NewOpc == 0) return 0; 543 const TargetInstrDesc &TID = TII->get(NewOpc); 544 if (TID.getNumDefs() != 1) return 0; 545 const TargetRegisterClass *RC = TID.OpInfo[LoadRegIndex].getRegClass(TRI); 546 // Ok, we're unfolding. Create a temporary register and do the unfold. 547 unsigned Reg = RegInfo->createVirtualRegister(RC); 548 549 MachineFunction &MF = *MI->getParent()->getParent(); 550 SmallVector<MachineInstr *, 2> NewMIs; 551 bool Success = 552 TII->unfoldMemoryOperand(MF, MI, Reg, 553 /*UnfoldLoad=*/true, /*UnfoldStore=*/false, 554 NewMIs); 555 (void)Success; 556 assert(Success && 557 "unfoldMemoryOperand failed when getOpcodeAfterMemoryUnfold " 558 "succeeded!"); 559 assert(NewMIs.size() == 2 && 560 "Unfolded a load into multiple instructions!"); 561 MachineBasicBlock *MBB = MI->getParent(); 562 MBB->insert(MI, NewMIs[0]); 563 MBB->insert(MI, NewMIs[1]); 564 // If unfolding produced a load that wasn't loop-invariant or profitable to 565 // hoist, discard the new instructions and bail. 566 if (!IsLoopInvariantInst(*NewMIs[0]) || !IsProfitableToHoist(*NewMIs[0])) { 567 NewMIs[0]->eraseFromParent(); 568 NewMIs[1]->eraseFromParent(); 569 return 0; 570 } 571 // Otherwise we successfully unfolded a load that we can hoist. 572 MI->eraseFromParent(); 573 return NewMIs[0]; 574} 575 576void MachineLICM::InitCSEMap(MachineBasicBlock *BB) { 577 for (MachineBasicBlock::iterator I = BB->begin(),E = BB->end(); I != E; ++I) { 578 const MachineInstr *MI = &*I; 579 // FIXME: For now, only hoist re-materilizable instructions. LICM will 580 // increase register pressure. We want to make sure it doesn't increase 581 // spilling. 582 if (TII->isTriviallyReMaterializable(MI, AA)) { 583 unsigned Opcode = MI->getOpcode(); 584 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 585 CI = CSEMap.find(Opcode); 586 if (CI != CSEMap.end()) 587 CI->second.push_back(MI); 588 else { 589 std::vector<const MachineInstr*> CSEMIs; 590 CSEMIs.push_back(MI); 591 CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 592 } 593 } 594 } 595} 596 597const MachineInstr* 598MachineLICM::LookForDuplicate(const MachineInstr *MI, 599 std::vector<const MachineInstr*> &PrevMIs) { 600 for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 601 const MachineInstr *PrevMI = PrevMIs[i]; 602 if (TII->produceSameValue(MI, PrevMI)) 603 return PrevMI; 604 } 605 return 0; 606} 607 608bool MachineLICM::EliminateCSE(MachineInstr *MI, 609 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator &CI) { 610 if (CI == CSEMap.end()) 611 return false; 612 613 if (const MachineInstr *Dup = LookForDuplicate(MI, CI->second)) { 614 DEBUG(dbgs() << "CSEing " << *MI << " with " << *Dup); 615 616 // Replace virtual registers defined by MI by their counterparts defined 617 // by Dup. 618 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 619 const MachineOperand &MO = MI->getOperand(i); 620 621 // Physical registers may not differ here. 622 assert((!MO.isReg() || MO.getReg() == 0 || 623 !TargetRegisterInfo::isPhysicalRegister(MO.getReg()) || 624 MO.getReg() == Dup->getOperand(i).getReg()) && 625 "Instructions with different phys regs are not identical!"); 626 627 if (MO.isReg() && MO.isDef() && 628 !TargetRegisterInfo::isPhysicalRegister(MO.getReg())) 629 RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 630 } 631 MI->eraseFromParent(); 632 ++NumCSEed; 633 return true; 634 } 635 return false; 636} 637 638/// Hoist - When an instruction is found to use only loop invariant operands 639/// that are safe to hoist, this instruction is called to do the dirty work. 640/// 641void MachineLICM::Hoist(MachineInstr *MI) { 642 // First check whether we should hoist this instruction. 643 if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { 644 // If not, try unfolding a hoistable load. 645 MI = ExtractHoistableLoad(MI); 646 if (!MI) return; 647 } 648 649 // Now move the instructions to the predecessor, inserting it before any 650 // terminator instructions. 651 DEBUG({ 652 dbgs() << "Hoisting " << *MI; 653 if (CurPreheader->getBasicBlock()) 654 dbgs() << " to MachineBasicBlock " 655 << CurPreheader->getName(); 656 if (MI->getParent()->getBasicBlock()) 657 dbgs() << " from MachineBasicBlock " 658 << MI->getParent()->getName(); 659 dbgs() << "\n"; 660 }); 661 662 // If this is the first instruction being hoisted to the preheader, 663 // initialize the CSE map with potential common expressions. 664 InitCSEMap(CurPreheader); 665 666 // Look for opportunity to CSE the hoisted instruction. 667 unsigned Opcode = MI->getOpcode(); 668 DenseMap<unsigned, std::vector<const MachineInstr*> >::iterator 669 CI = CSEMap.find(Opcode); 670 if (!EliminateCSE(MI, CI)) { 671 // Otherwise, splice the instruction to the preheader. 672 CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI); 673 674 // Add to the CSE map. 675 if (CI != CSEMap.end()) 676 CI->second.push_back(MI); 677 else { 678 std::vector<const MachineInstr*> CSEMIs; 679 CSEMIs.push_back(MI); 680 CSEMap.insert(std::make_pair(Opcode, CSEMIs)); 681 } 682 } 683 684 ++NumHoisted; 685 Changed = true; 686} 687