LLVM API Documentation
00001 //===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass performs loop invariant code motion on machine instructions. We 00011 // attempt to remove as much code from the body of a loop as possible. 00012 // 00013 // This pass does not attempt to throttle itself to limit register pressure. 00014 // The register allocation phases are expected to perform rematerialization 00015 // to recover when register pressure is high. 00016 // 00017 // This pass is not intended to be a replacement or a complete alternative 00018 // for the LLVM-IR-level LICM pass. It is only designed to hoist simple 00019 // constructs that are not exposed before lowering and instruction selection. 00020 // 00021 //===----------------------------------------------------------------------===// 00022 00023 #define DEBUG_TYPE "machine-licm" 00024 #include "llvm/CodeGen/Passes.h" 00025 #include "llvm/CodeGen/MachineDominators.h" 00026 #include "llvm/CodeGen/MachineLoopInfo.h" 00027 #include "llvm/CodeGen/MachineRegisterInfo.h" 00028 #include "llvm/Target/TargetRegisterInfo.h" 00029 #include "llvm/Target/TargetInstrInfo.h" 00030 #include "llvm/Target/TargetMachine.h" 00031 #include "llvm/ADT/DenseMap.h" 00032 #include "llvm/ADT/Statistic.h" 00033 #include "llvm/Support/Compiler.h" 00034 #include "llvm/Support/Debug.h" 00035 #include "llvm/Support/raw_ostream.h" 00036 00037 using namespace llvm; 00038 00039 STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 00040 STATISTIC(NumCSEed, "Number of hoisted machine instructions CSEed"); 00041 00042 namespace { 00043 class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { 00044 const TargetMachine *TM; 00045 const TargetInstrInfo *TII; 00046 00047 // Various analyses that we use... 00048 MachineLoopInfo *LI; // Current MachineLoopInfo 00049 MachineDominatorTree *DT; // Machine dominator tree for the cur loop 00050 MachineRegisterInfo *RegInfo; // Machine register information 00051 00052 // State that is updated as we process loops 00053 bool Changed; // True if a loop is changed. 00054 MachineLoop *CurLoop; // The current loop we are working on. 00055 MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 00056 00057 // For each BB and opcode pair, keep a list of hoisted instructions. 00058 DenseMap<std::pair<unsigned, unsigned>, 00059 std::vector<const MachineInstr*> > CSEMap; 00060 public: 00061 static char ID; // Pass identification, replacement for typeid 00062 MachineLICM() : MachineFunctionPass(&ID) {} 00063 00064 virtual bool runOnMachineFunction(MachineFunction &MF); 00065 00066 const char *getPassName() const { return "Machine Instruction LICM"; } 00067 00068 // FIXME: Loop preheaders? 00069 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00070 AU.setPreservesCFG(); 00071 AU.addRequired<MachineLoopInfo>(); 00072 AU.addRequired<MachineDominatorTree>(); 00073 AU.addPreserved<MachineLoopInfo>(); 00074 AU.addPreserved<MachineDominatorTree>(); 00075 MachineFunctionPass::getAnalysisUsage(AU); 00076 } 00077 00078 virtual void releaseMemory() { 00079 CSEMap.clear(); 00080 } 00081 00082 private: 00083 /// IsLoopInvariantInst - Returns true if the instruction is loop 00084 /// invariant. I.e., all virtual register operands are defined outside of 00085 /// the loop, physical registers aren't accessed (explicitly or implicitly), 00086 /// and the instruction is hoistable. 00087 /// 00088 bool IsLoopInvariantInst(MachineInstr &I); 00089 00090 /// IsProfitableToHoist - Return true if it is potentially profitable to 00091 /// hoist the given loop invariant. 00092 bool IsProfitableToHoist(MachineInstr &MI); 00093 00094 /// HoistRegion - Walk the specified region of the CFG (defined by all 00095 /// blocks dominated by the specified block, and that are in the current 00096 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 00097 /// visit definitions before uses, allowing us to hoist a loop body in one 00098 /// pass without iteration. 00099 /// 00100 void HoistRegion(MachineDomTreeNode *N); 00101 00102 /// Hoist - When an instruction is found to only use loop invariant operands 00103 /// that is safe to hoist, this instruction is called to do the dirty work. 00104 /// 00105 void Hoist(MachineInstr &MI); 00106 }; 00107 } // end anonymous namespace 00108 00109 char MachineLICM::ID = 0; 00110 static RegisterPass<MachineLICM> 00111 X("machinelicm", "Machine Loop Invariant Code Motion"); 00112 00113 FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } 00114 00115 /// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 00116 /// loop that has a preheader. 00117 static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 00118 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 00119 if (L->getLoopPreheader()) 00120 return false; 00121 return true; 00122 } 00123 00124 /// Hoist expressions out of the specified loop. Note, alias info for inner loop 00125 /// is not preserved so it is not a good idea to run LICM multiple times on one 00126 /// loop. 00127 /// 00128 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 00129 const Function *F = MF.getFunction(); 00130 if (F->hasFnAttr(Attribute::OptimizeForSize)) 00131 return false; 00132 00133 DOUT << "******** Machine LICM ********\n"; 00134 00135 Changed = false; 00136 TM = &MF.getTarget(); 00137 TII = TM->getInstrInfo(); 00138 RegInfo = &MF.getRegInfo(); 00139 00140 // Get our Loop information... 00141 LI = &getAnalysis<MachineLoopInfo>(); 00142 DT = &getAnalysis<MachineDominatorTree>(); 00143 00144 for (MachineLoopInfo::iterator 00145 I = LI->begin(), E = LI->end(); I != E; ++I) { 00146 CurLoop = *I; 00147 00148 // Only visit outer-most preheader-sporting loops. 00149 if (!LoopIsOuterMostWithPreheader(CurLoop)) 00150 continue; 00151 00152 // Determine the block to which to hoist instructions. If we can't find a 00153 // suitable loop preheader, we can't do any hoisting. 00154 // 00155 // FIXME: We are only hoisting if the basic block coming into this loop 00156 // has only one successor. This isn't the case in general because we haven't 00157 // broken critical edges or added preheaders. 00158 CurPreheader = CurLoop->getLoopPreheader(); 00159 if (!CurPreheader) 00160 continue; 00161 00162 HoistRegion(DT->getNode(CurLoop->getHeader())); 00163 } 00164 00165 return Changed; 00166 } 00167 00168 /// HoistRegion - Walk the specified region of the CFG (defined by all blocks 00169 /// dominated by the specified block, and that are in the current loop) in depth 00170 /// first order w.r.t the DominatorTree. This allows us to visit definitions 00171 /// before uses, allowing us to hoist a loop body in one pass without iteration. 00172 /// 00173 void MachineLICM::HoistRegion(MachineDomTreeNode *N) { 00174 assert(N != 0 && "Null dominator tree node?"); 00175 MachineBasicBlock *BB = N->getBlock(); 00176 00177 // If this subregion is not in the top level loop at all, exit. 00178 if (!CurLoop->contains(BB)) return; 00179 00180 for (MachineBasicBlock::iterator 00181 MII = BB->begin(), E = BB->end(); MII != E; ) { 00182 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 00183 MachineInstr &MI = *MII; 00184 00185 Hoist(MI); 00186 00187 MII = NextMII; 00188 } 00189 00190 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 00191 00192 for (unsigned I = 0, E = Children.size(); I != E; ++I) 00193 HoistRegion(Children[I]); 00194 } 00195 00196 /// IsLoopInvariantInst - Returns true if the instruction is loop 00197 /// invariant. I.e., all virtual register operands are defined outside of the 00198 /// loop, physical registers aren't accessed explicitly, and there are no side 00199 /// effects that aren't captured by the operands or other flags. 00200 /// 00201 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 00202 const TargetInstrDesc &TID = I.getDesc(); 00203 00204 // Ignore stuff that we obviously can't hoist. 00205 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 00206 TID.hasUnmodeledSideEffects()) 00207 return false; 00208 00209 if (TID.mayLoad()) { 00210 // Okay, this instruction does a load. As a refinement, we allow the target 00211 // to decide whether the loaded value is actually a constant. If so, we can 00212 // actually use it as a load. 00213 if (!TII->isInvariantLoad(&I)) 00214 // FIXME: we should be able to sink loads with no other side effects if 00215 // there is nothing that can change memory from here until the end of 00216 // block. This is a trivial form of alias analysis. 00217 return false; 00218 } 00219 00220 DEBUG({ 00221 DOUT << "--- Checking if we can hoist " << I; 00222 if (I.getDesc().getImplicitUses()) { 00223 DOUT << " * Instruction has implicit uses:\n"; 00224 00225 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 00226 for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 00227 *ImpUses; ++ImpUses) 00228 DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; 00229 } 00230 00231 if (I.getDesc().getImplicitDefs()) { 00232 DOUT << " * Instruction has implicit defines:\n"; 00233 00234 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 00235 for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 00236 *ImpDefs; ++ImpDefs) 00237 DOUT << " -> " << TRI->getName(*ImpDefs) << "\n"; 00238 } 00239 }); 00240 00241 if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 00242 DOUT << "Cannot hoist with implicit defines or uses\n"; 00243 return false; 00244 } 00245 00246 // The instruction is loop invariant if all of its operands are. 00247 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00248 const MachineOperand &MO = I.getOperand(i); 00249 00250 if (!MO.isReg()) 00251 continue; 00252 00253 unsigned Reg = MO.getReg(); 00254 if (Reg == 0) continue; 00255 00256 // Don't hoist an instruction that uses or defines a physical register. 00257 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 00258 return false; 00259 00260 if (!MO.isUse()) 00261 continue; 00262 00263 assert(RegInfo->getVRegDef(Reg) && 00264 "Machine instr not mapped for this vreg?!"); 00265 00266 // If the loop contains the definition of an operand, then the instruction 00267 // isn't loop invariant. 00268 if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 00269 return false; 00270 } 00271 00272 // If we got this far, the instruction is loop invariant! 00273 return true; 00274 } 00275 00276 00277 /// HasPHIUses - Return true if the specified register has any PHI use. 00278 static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 00279 for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 00280 UE = RegInfo->use_end(); UI != UE; ++UI) { 00281 MachineInstr *UseMI = &*UI; 00282 if (UseMI->getOpcode() == TargetInstrInfo::PHI) 00283 return true; 00284 } 00285 return false; 00286 } 00287 00288 /// IsProfitableToHoist - Return true if it is potentially profitable to hoist 00289 /// the given loop invariant. 00290 bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 00291 if (MI.getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 00292 return false; 00293 00294 const TargetInstrDesc &TID = MI.getDesc(); 00295 00296 // FIXME: For now, only hoist re-materilizable instructions. LICM will 00297 // increase register pressure. We want to make sure it doesn't increase 00298 // spilling. 00299 if (!TID.mayLoad() && (!TID.isRematerializable() || 00300 !TII->isTriviallyReMaterializable(&MI))) 00301 return false; 00302 00303 // If result(s) of this instruction is used by PHIs, then don't hoist it. 00304 // The presence of joins makes it difficult for current register allocator 00305 // implementation to perform remat. 00306 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 00307 const MachineOperand &MO = MI.getOperand(i); 00308 if (!MO.isReg() || !MO.isDef()) 00309 continue; 00310 if (HasPHIUses(MO.getReg(), RegInfo)) 00311 return false; 00312 } 00313 00314 return true; 00315 } 00316 00317 static const MachineInstr *LookForDuplicate(const MachineInstr *MI, 00318 std::vector<const MachineInstr*> &PrevMIs, 00319 MachineRegisterInfo *RegInfo) { 00320 unsigned NumOps = MI->getNumOperands(); 00321 for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 00322 const MachineInstr *PrevMI = PrevMIs[i]; 00323 unsigned NumOps2 = PrevMI->getNumOperands(); 00324 if (NumOps != NumOps2) 00325 continue; 00326 bool IsSame = true; 00327 for (unsigned j = 0; j != NumOps; ++j) { 00328 const MachineOperand &MO = MI->getOperand(j); 00329 if (MO.isReg() && MO.isDef()) { 00330 if (RegInfo->getRegClass(MO.getReg()) != 00331 RegInfo->getRegClass(PrevMI->getOperand(j).getReg())) { 00332 IsSame = false; 00333 break; 00334 } 00335 continue; 00336 } 00337 if (!MO.isIdenticalTo(PrevMI->getOperand(j))) { 00338 IsSame = false; 00339 break; 00340 } 00341 } 00342 if (IsSame) 00343 return PrevMI; 00344 } 00345 return 0; 00346 } 00347 00348 /// Hoist - When an instruction is found to use only loop invariant operands 00349 /// that are safe to hoist, this instruction is called to do the dirty work. 00350 /// 00351 void MachineLICM::Hoist(MachineInstr &MI) { 00352 if (!IsLoopInvariantInst(MI)) return; 00353 if (!IsProfitableToHoist(MI)) return; 00354 00355 // Now move the instructions to the predecessor, inserting it before any 00356 // terminator instructions. 00357 DEBUG({ 00358 errs() << "Hoisting " << MI; 00359 if (CurPreheader->getBasicBlock()) 00360 errs() << " to MachineBasicBlock " 00361 << CurPreheader->getBasicBlock()->getName(); 00362 if (MI.getParent()->getBasicBlock()) 00363 errs() << " from MachineBasicBlock " 00364 << MI.getParent()->getBasicBlock()->getName(); 00365 errs() << "\n"; 00366 }); 00367 00368 // Look for opportunity to CSE the hoisted instruction. 00369 std::pair<unsigned, unsigned> BBOpcPair = 00370 std::make_pair(CurPreheader->getNumber(), MI.getOpcode()); 00371 DenseMap<std::pair<unsigned, unsigned>, 00372 std::vector<const MachineInstr*> >::iterator CI = CSEMap.find(BBOpcPair); 00373 bool DoneCSE = false; 00374 if (CI != CSEMap.end()) { 00375 const MachineInstr *Dup = LookForDuplicate(&MI, CI->second, RegInfo); 00376 if (Dup) { 00377 DOUT << "CSEing " << MI; 00378 DOUT << " with " << *Dup; 00379 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 00380 const MachineOperand &MO = MI.getOperand(i); 00381 if (MO.isReg() && MO.isDef()) 00382 RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 00383 } 00384 MI.eraseFromParent(); 00385 DoneCSE = true; 00386 ++NumCSEed; 00387 } 00388 } 00389 00390 // Otherwise, splice the instruction to the preheader. 00391 if (!DoneCSE) { 00392 CurPreheader->splice(CurPreheader->getFirstTerminator(), 00393 MI.getParent(), &MI); 00394 // Add to the CSE map. 00395 if (CI != CSEMap.end()) 00396 CI->second.push_back(&MI); 00397 else { 00398 std::vector<const MachineInstr*> CSEMIs; 00399 CSEMIs.push_back(&MI); 00400 CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs)); 00401 } 00402 } 00403 00404 ++NumHoisted; 00405 Changed = true; 00406 }