MachineLICM.cpp revision 7da0592edfecaac630500ce491f7e339d416be60
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/MachineLoopInfo.h" 27#include "llvm/CodeGen/MachineRegisterInfo.h" 28#include "llvm/Target/TargetRegisterInfo.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/ADT/DenseMap.h" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/Support/Compiler.h" 34#include "llvm/Support/Debug.h" 35#include "llvm/Support/raw_ostream.h" 36 37using namespace llvm; 38 39STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 40STATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed"); 41 42namespace { 43 class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { 44 const TargetMachine *TM; 45 const TargetInstrInfo *TII; 46 const TargetRegisterInfo *TRI; 47 BitVector AllocatableSet; 48 49 // Various analyses that we use... 50 MachineLoopInfo *LI; // Current MachineLoopInfo 51 MachineDominatorTree *DT; // Machine dominator tree for the cur loop 52 MachineRegisterInfo *RegInfo; // Machine register information 53 54 // State that is updated as we process loops 55 bool Changed; // True if a loop is changed. 56 MachineLoop *CurLoop; // The current loop we are working on. 57 MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 58 59 // For each BB and opcode pair, keep a list of hoisted instructions. 60 DenseMap<std::pair<unsigned, unsigned>, 61 std::vector<const MachineInstr*> > CSEMap; 62 public: 63 static char ID; // Pass identification, replacement for typeid 64 MachineLICM() : MachineFunctionPass(&ID) {} 65 66 virtual bool runOnMachineFunction(MachineFunction &MF); 67 68 const char *getPassName() const { return "Machine Instruction LICM"; } 69 70 // FIXME: Loop preheaders? 71 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 72 AU.setPreservesCFG(); 73 AU.addRequired<MachineLoopInfo>(); 74 AU.addRequired<MachineDominatorTree>(); 75 AU.addPreserved<MachineLoopInfo>(); 76 AU.addPreserved<MachineDominatorTree>(); 77 MachineFunctionPass::getAnalysisUsage(AU); 78 } 79 80 virtual void releaseMemory() { 81 CSEMap.clear(); 82 } 83 84 private: 85 /// IsLoopInvariantInst - Returns true if the instruction is loop 86 /// invariant. I.e., all virtual register operands are defined outside of 87 /// the loop, physical registers aren't accessed (explicitly or implicitly), 88 /// and the instruction is hoistable. 89 /// 90 bool IsLoopInvariantInst(MachineInstr &I); 91 92 /// IsProfitableToHoist - Return true if it is potentially profitable to 93 /// hoist the given loop invariant. 94 bool IsProfitableToHoist(MachineInstr &MI); 95 96 /// HoistRegion - Walk the specified region of the CFG (defined by all 97 /// blocks dominated by the specified block, and that are in the current 98 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 99 /// visit definitions before uses, allowing us to hoist a loop body in one 100 /// pass without iteration. 101 /// 102 void HoistRegion(MachineDomTreeNode *N); 103 104 /// Hoist - When an instruction is found to only use loop invariant operands 105 /// that is safe to hoist, this instruction is called to do the dirty work. 106 /// 107 void Hoist(MachineInstr &MI); 108 }; 109} // end anonymous namespace 110 111char MachineLICM::ID = 0; 112static RegisterPass<MachineLICM> 113X("machinelicm", "Machine Loop Invariant Code Motion"); 114 115FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } 116 117/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 118/// loop that has a preheader. 119static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 120 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 121 if (L->getLoopPreheader()) 122 return false; 123 return true; 124} 125 126/// Hoist expressions out of the specified loop. Note, alias info for inner loop 127/// is not preserved so it is not a good idea to run LICM multiple times on one 128/// loop. 129/// 130bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 131 const Function *F = MF.getFunction(); 132 if (F->hasFnAttr(Attribute::OptimizeForSize)) 133 return false; 134 135 DEBUG(errs() << "******** Machine LICM ********\n"); 136 137 Changed = false; 138 TM = &MF.getTarget(); 139 TII = TM->getInstrInfo(); 140 TRI = TM->getRegisterInfo(); 141 RegInfo = &MF.getRegInfo(); 142 AllocatableSet = TRI->getAllocatableSet(MF); 143 144 // Get our Loop information... 145 LI = &getAnalysis<MachineLoopInfo>(); 146 DT = &getAnalysis<MachineDominatorTree>(); 147 148 for (MachineLoopInfo::iterator 149 I = LI->begin(), E = LI->end(); I != E; ++I) { 150 CurLoop = *I; 151 152 // Only visit outer-most preheader-sporting loops. 153 if (!LoopIsOuterMostWithPreheader(CurLoop)) 154 continue; 155 156 // Determine the block to which to hoist instructions. If we can't find a 157 // suitable loop preheader, we can't do any hoisting. 158 // 159 // FIXME: We are only hoisting if the basic block coming into this loop 160 // has only one successor. This isn't the case in general because we haven't 161 // broken critical edges or added preheaders. 162 CurPreheader = CurLoop->getLoopPreheader(); 163 if (!CurPreheader) 164 continue; 165 166 HoistRegion(DT->getNode(CurLoop->getHeader())); 167 } 168 169 return Changed; 170} 171 172/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 173/// dominated by the specified block, and that are in the current loop) in depth 174/// first order w.r.t the DominatorTree. This allows us to visit definitions 175/// before uses, allowing us to hoist a loop body in one pass without iteration. 176/// 177void MachineLICM::HoistRegion(MachineDomTreeNode *N) { 178 assert(N != 0 && "Null dominator tree node?"); 179 MachineBasicBlock *BB = N->getBlock(); 180 181 // If this subregion is not in the top level loop at all, exit. 182 if (!CurLoop->contains(BB)) return; 183 184 for (MachineBasicBlock::iterator 185 MII = BB->begin(), E = BB->end(); MII != E; ) { 186 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 187 MachineInstr &MI = *MII; 188 189 Hoist(MI); 190 191 MII = NextMII; 192 } 193 194 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 195 196 for (unsigned I = 0, E = Children.size(); I != E; ++I) 197 HoistRegion(Children[I]); 198} 199 200/// IsLoopInvariantInst - Returns true if the instruction is loop 201/// invariant. I.e., all virtual register operands are defined outside of the 202/// loop, physical registers aren't accessed explicitly, and there are no side 203/// effects that aren't captured by the operands or other flags. 204/// 205bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 206 const TargetInstrDesc &TID = I.getDesc(); 207 208 // Ignore stuff that we obviously can't hoist. 209 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 210 TID.hasUnmodeledSideEffects()) 211 return false; 212 213 if (TID.mayLoad()) { 214 // Okay, this instruction does a load. As a refinement, we allow the target 215 // to decide whether the loaded value is actually a constant. If so, we can 216 // actually use it as a load. 217 if (!TII->isInvariantLoad(&I)) 218 // FIXME: we should be able to sink loads with no other side effects if 219 // there is nothing that can change memory from here until the end of 220 // block. This is a trivial form of alias analysis. 221 return false; 222 } 223 224 DEBUG({ 225 errs() << "--- Checking if we can hoist " << I; 226 if (I.getDesc().getImplicitUses()) { 227 errs() << " * Instruction has implicit uses:\n"; 228 229 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 230 for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 231 *ImpUses; ++ImpUses) 232 errs() << " -> " << TRI->getName(*ImpUses) << "\n"; 233 } 234 235 if (I.getDesc().getImplicitDefs()) { 236 errs() << " * Instruction has implicit defines:\n"; 237 238 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 239 for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 240 *ImpDefs; ++ImpDefs) 241 errs() << " -> " << TRI->getName(*ImpDefs) << "\n"; 242 } 243 }); 244 245 if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 246 DEBUG(errs() << "Cannot hoist with implicit defines or uses\n"); 247 return false; 248 } 249 250 // The instruction is loop invariant if all of its operands are. 251 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 252 const MachineOperand &MO = I.getOperand(i); 253 254 if (!MO.isReg()) 255 continue; 256 257 unsigned Reg = MO.getReg(); 258 if (Reg == 0) continue; 259 260 // Don't hoist an instruction that uses or defines a physical register. 261 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 262 // If this is a physical register use, we can't move it. If it is a def, 263 // we can move it, but only if the def is dead. 264 if (MO.isUse()) { 265 // If the physreg has no defs anywhere, it's just an ambient register 266 // and we can freely move its uses. Alternatively, if it's allocatable, 267 // it could get allocated to something with a def during allocation. 268 if (!RegInfo->def_empty(Reg)) 269 return false; 270 if (AllocatableSet.test(Reg)) 271 return false; 272 // Check for a def among the register's aliases too. 273 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 274 unsigned AliasReg = *Alias; 275 if (!RegInfo->def_empty(AliasReg)) 276 return false; 277 if (AllocatableSet.test(AliasReg)) 278 return false; 279 } 280 // Otherwise it's safe to move. 281 continue; 282 } else if (!MO.isDead()) { 283 // A def that isn't dead. We can't move it. 284 return false; 285 } 286 } 287 288 if (!MO.isUse()) 289 continue; 290 291 assert(RegInfo->getVRegDef(Reg) && 292 "Machine instr not mapped for this vreg?!"); 293 294 // If the loop contains the definition of an operand, then the instruction 295 // isn't loop invariant. 296 if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 297 return false; 298 } 299 300 // If we got this far, the instruction is loop invariant! 301 return true; 302} 303 304 305/// HasPHIUses - Return true if the specified register has any PHI use. 306static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 307 for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 308 UE = RegInfo->use_end(); UI != UE; ++UI) { 309 MachineInstr *UseMI = &*UI; 310 if (UseMI->getOpcode() == TargetInstrInfo::PHI) 311 return true; 312 } 313 return false; 314} 315 316/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 317/// the given loop invariant. 318bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 319 if (MI.getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 320 return false; 321 322 const TargetInstrDesc &TID = MI.getDesc(); 323 324 // FIXME: For now, only hoist re-materilizable instructions. LICM will 325 // increase register pressure. We want to make sure it doesn't increase 326 // spilling. 327 if (!TID.mayLoad() && (!TID.isRematerializable() || 328 !TII->isTriviallyReMaterializable(&MI))) 329 return false; 330 331 // If result(s) of this instruction is used by PHIs, then don't hoist it. 332 // The presence of joins makes it difficult for current register allocator 333 // implementation to perform remat. 334 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 335 const MachineOperand &MO = MI.getOperand(i); 336 if (!MO.isReg() || !MO.isDef()) 337 continue; 338 if (HasPHIUses(MO.getReg(), RegInfo)) 339 return false; 340 } 341 342 return true; 343} 344 345static const MachineInstr *LookForDuplicate(const MachineInstr *MI, 346 std::vector<const MachineInstr*> &PrevMIs, 347 MachineRegisterInfo *RegInfo) { 348 unsigned NumOps = MI->getNumOperands(); 349 for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 350 const MachineInstr *PrevMI = PrevMIs[i]; 351 unsigned NumOps2 = PrevMI->getNumOperands(); 352 if (NumOps != NumOps2) 353 continue; 354 bool IsSame = true; 355 for (unsigned j = 0; j != NumOps; ++j) { 356 const MachineOperand &MO = MI->getOperand(j); 357 if (MO.isReg() && MO.isDef()) { 358 if (RegInfo->getRegClass(MO.getReg()) != 359 RegInfo->getRegClass(PrevMI->getOperand(j).getReg())) { 360 IsSame = false; 361 break; 362 } 363 continue; 364 } 365 if (!MO.isIdenticalTo(PrevMI->getOperand(j))) { 366 IsSame = false; 367 break; 368 } 369 } 370 if (IsSame) 371 return PrevMI; 372 } 373 return 0; 374} 375 376/// Hoist - When an instruction is found to use only loop invariant operands 377/// that are safe to hoist, this instruction is called to do the dirty work. 378/// 379void MachineLICM::Hoist(MachineInstr &MI) { 380 if (!IsLoopInvariantInst(MI)) return; 381 if (!IsProfitableToHoist(MI)) return; 382 383 // Now move the instructions to the predecessor, inserting it before any 384 // terminator instructions. 385 DEBUG({ 386 errs() << "Hoisting " << MI; 387 if (CurPreheader->getBasicBlock()) 388 errs() << " to MachineBasicBlock " 389 << CurPreheader->getBasicBlock()->getName(); 390 if (MI.getParent()->getBasicBlock()) 391 errs() << " from MachineBasicBlock " 392 << MI.getParent()->getBasicBlock()->getName(); 393 errs() << "\n"; 394 }); 395 396 // Look for opportunity to CSE the hoisted instruction. 397 std::pair<unsigned, unsigned> BBOpcPair = 398 std::make_pair(CurPreheader->getNumber(), MI.getOpcode()); 399 DenseMap<std::pair<unsigned, unsigned>, 400 std::vector<const MachineInstr*> >::iterator CI = CSEMap.find(BBOpcPair); 401 bool DoneCSE = false; 402 if (CI != CSEMap.end()) { 403 const MachineInstr *Dup = LookForDuplicate(&MI, CI->second, RegInfo); 404 if (Dup) { 405 DEBUG(errs() << "CSEing " << MI << " with " << *Dup); 406 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 407 const MachineOperand &MO = MI.getOperand(i); 408 if (MO.isReg() && MO.isDef()) 409 RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 410 } 411 MI.eraseFromParent(); 412 DoneCSE = true; 413 ++NumCSEed; 414 } 415 } 416 417 // Otherwise, splice the instruction to the preheader. 418 if (!DoneCSE) { 419 CurPreheader->splice(CurPreheader->getFirstTerminator(), 420 MI.getParent(), &MI); 421 // Add to the CSE map. 422 if (CI != CSEMap.end()) 423 CI->second.push_back(&MI); 424 else { 425 std::vector<const MachineInstr*> CSEMIs; 426 CSEMIs.push_back(&MI); 427 CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs)); 428 } 429 } 430 431 ++NumHoisted; 432 Changed = true; 433} 434