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