MachineLICM.cpp revision 51e32f87f4df220f4efa5bfd29318ffce2c6da33
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/Statistic.h" 32#include "llvm/Support/CommandLine.h" 33#include "llvm/Support/Compiler.h" 34#include "llvm/Support/Debug.h" 35 36using namespace llvm; 37 38STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops"); 39 40namespace { 41 class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass { 42 const TargetMachine *TM; 43 const TargetInstrInfo *TII; 44 45 // Various analyses that we use... 46 MachineLoopInfo *LI; // Current MachineLoopInfo 47 MachineDominatorTree *DT; // Machine dominator tree for the cur loop 48 MachineRegisterInfo *RegInfo; // Machine register information 49 50 // State that is updated as we process loops 51 bool Changed; // True if a loop is changed. 52 MachineLoop *CurLoop; // The current loop we are working on. 53 MachineBasicBlock *CurPreheader; // The preheader for CurLoop. 54 public: 55 static char ID; // Pass identification, replacement for typeid 56 MachineLICM() : MachineFunctionPass(&ID) {} 57 58 virtual bool runOnMachineFunction(MachineFunction &MF); 59 60 const char *getPassName() const { return "Machine Instruction LICM"; } 61 62 // FIXME: Loop preheaders? 63 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 64 AU.setPreservesCFG(); 65 AU.addRequired<MachineLoopInfo>(); 66 AU.addRequired<MachineDominatorTree>(); 67 AU.addPreserved<MachineLoopInfo>(); 68 AU.addPreserved<MachineDominatorTree>(); 69 MachineFunctionPass::getAnalysisUsage(AU); 70 } 71 private: 72 /// IsLoopInvariantInst - Returns true if the instruction is loop 73 /// invariant. I.e., all virtual register operands are defined outside of 74 /// the loop, physical registers aren't accessed (explicitly or implicitly), 75 /// and the instruction is hoistable. 76 /// 77 bool IsLoopInvariantInst(MachineInstr &I); 78 79 /// IsProfitableToHoist - Return true if it is potentially profitable to 80 /// hoist the given loop invariant. 81 bool IsProfitableToHoist(MachineInstr &MI); 82 83 /// HoistRegion - Walk the specified region of the CFG (defined by all 84 /// blocks dominated by the specified block, and that are in the current 85 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 86 /// visit definitions before uses, allowing us to hoist a loop body in one 87 /// pass without iteration. 88 /// 89 void HoistRegion(MachineDomTreeNode *N); 90 91 /// Hoist - When an instruction is found to only use loop invariant operands 92 /// that is safe to hoist, this instruction is called to do the dirty work. 93 /// 94 void Hoist(MachineInstr &MI); 95 }; 96} // end anonymous namespace 97 98char MachineLICM::ID = 0; 99static RegisterPass<MachineLICM> 100X("machinelicm", "Machine Loop Invariant Code Motion"); 101 102FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); } 103 104/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most 105/// loop that has a preheader. 106static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { 107 for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) 108 if (L->getLoopPreheader()) 109 return false; 110 return true; 111} 112 113/// Hoist expressions out of the specified loop. Note, alias info for inner loop 114/// is not preserved so it is not a good idea to run LICM multiple times on one 115/// loop. 116/// 117bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { 118 DOUT << "******** Machine LICM ********\n"; 119 120 Changed = false; 121 TM = &MF.getTarget(); 122 TII = TM->getInstrInfo(); 123 RegInfo = &MF.getRegInfo(); 124 125 // Get our Loop information... 126 LI = &getAnalysis<MachineLoopInfo>(); 127 DT = &getAnalysis<MachineDominatorTree>(); 128 129 for (MachineLoopInfo::iterator 130 I = LI->begin(), E = LI->end(); I != E; ++I) { 131 CurLoop = *I; 132 133 // Only visit outer-most preheader-sporting loops. 134 if (!LoopIsOuterMostWithPreheader(CurLoop)) 135 continue; 136 137 // Determine the block to which to hoist instructions. If we can't find a 138 // suitable loop preheader, we can't do any hoisting. 139 // 140 // FIXME: We are only hoisting if the basic block coming into this loop 141 // has only one successor. This isn't the case in general because we haven't 142 // broken critical edges or added preheaders. 143 CurPreheader = CurLoop->getLoopPreheader(); 144 if (!CurPreheader) 145 continue; 146 147 HoistRegion(DT->getNode(CurLoop->getHeader())); 148 } 149 150 return Changed; 151} 152 153/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 154/// dominated by the specified block, and that are in the current loop) in depth 155/// first order w.r.t the DominatorTree. This allows us to visit definitions 156/// before uses, allowing us to hoist a loop body in one pass without iteration. 157/// 158void MachineLICM::HoistRegion(MachineDomTreeNode *N) { 159 assert(N != 0 && "Null dominator tree node?"); 160 MachineBasicBlock *BB = N->getBlock(); 161 162 // If this subregion is not in the top level loop at all, exit. 163 if (!CurLoop->contains(BB)) return; 164 165 for (MachineBasicBlock::iterator 166 I = BB->begin(), E = BB->end(); I != E; ) { 167 MachineInstr &MI = *I++; 168 169 // Try hoisting the instruction out of the loop. We can only do this if 170 // all of the operands of the instruction are loop invariant and if it is 171 // safe to hoist the instruction. 172 Hoist(MI); 173 } 174 175 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 176 177 for (unsigned I = 0, E = Children.size(); I != E; ++I) 178 HoistRegion(Children[I]); 179} 180 181/// IsLoopInvariantInst - Returns true if the instruction is loop 182/// invariant. I.e., all virtual register operands are defined outside of the 183/// loop, physical registers aren't accessed explicitly, and there are no side 184/// effects that aren't captured by the operands or other flags. 185/// 186bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 187 const TargetInstrDesc &TID = I.getDesc(); 188 189 // Ignore stuff that we obviously can't hoist. 190 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 191 TID.hasUnmodeledSideEffects()) 192 return false; 193 194 if (TID.mayLoad()) { 195 // Okay, this instruction does a load. As a refinement, we allow the target 196 // to decide whether the loaded value is actually a constant. If so, we can 197 // actually use it as a load. 198 if (!TII->isInvariantLoad(&I)) 199 // FIXME: we should be able to sink loads with no other side effects if 200 // there is nothing that can change memory from here until the end of 201 // block. This is a trivial form of alias analysis. 202 return false; 203 } 204 205 DEBUG({ 206 DOUT << "--- Checking if we can hoist " << I; 207 if (I.getDesc().getImplicitUses()) { 208 DOUT << " * Instruction has implicit uses:\n"; 209 210 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 211 for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 212 *ImpUses; ++ImpUses) 213 DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; 214 } 215 216 if (I.getDesc().getImplicitDefs()) { 217 DOUT << " * Instruction has implicit defines:\n"; 218 219 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 220 for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 221 *ImpDefs; ++ImpDefs) 222 DOUT << " -> " << TRI->getName(*ImpDefs) << "\n"; 223 } 224 }); 225 226 if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 227 DOUT << "Cannot hoist with implicit defines or uses\n"; 228 return false; 229 } 230 231 // The instruction is loop invariant if all of its operands are. 232 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 233 const MachineOperand &MO = I.getOperand(i); 234 235 if (!MO.isReg()) 236 continue; 237 238 unsigned Reg = MO.getReg(); 239 if (Reg == 0) continue; 240 241 // Don't hoist an instruction that uses or defines a physical register. 242 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 243 return false; 244 245 if (!MO.isUse()) 246 continue; 247 248 assert(RegInfo->getVRegDef(Reg) && 249 "Machine instr not mapped for this vreg?!"); 250 251 // If the loop contains the definition of an operand, then the instruction 252 // isn't loop invariant. 253 if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 254 return false; 255 } 256 257 // If we got this far, the instruction is loop invariant! 258 return true; 259} 260 261/// HasOnlyPHIUses - Return true if the only uses of Reg are PHIs. 262static bool HasOnlyPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 263 bool OnlyPHIUse = false; 264 for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 265 UE = RegInfo->use_end(); UI != UE; ++UI) { 266 MachineInstr *UseMI = &*UI; 267 if (UseMI->getOpcode() != TargetInstrInfo::PHI) 268 return false; 269 OnlyPHIUse = true; 270 } 271 return OnlyPHIUse; 272} 273 274/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 275/// the given loop invariant. 276bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 277 const TargetInstrDesc &TID = MI.getDesc(); 278 279 bool isInvLoad = false; 280 if (TID.mayLoad()) { 281 isInvLoad = TII->isInvariantLoad(&MI); 282 if (!isInvLoad) 283 return false; 284 } 285 286 // FIXME: For now, only hoist re-materilizable instructions. LICM will 287 // increase register pressure. We want to make sure it doesn't increase 288 // spilling. 289 if (!isInvLoad && (!TID.isRematerializable() || 290 !TII->isTriviallyReMaterializable(&MI))) 291 return false; 292 293 if (!TID.isAsCheapAsAMove()) 294 return true; 295 296 // If the instruction is "cheap" and the only uses of the register(s) defined 297 // by this MI are PHIs, then don't hoist it. Otherwise we just end up with a 298 // cheap instruction (e.g. constant) with long live interval feeeding into 299 // copies that are not always coalesced away. 300 bool OnlyPHIUses = false; 301 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 302 const MachineOperand &MO = MI.getOperand(i); 303 if (!MO.isReg() || !MO.isDef()) 304 continue; 305 OnlyPHIUses |= HasOnlyPHIUses(MO.getReg(), RegInfo); 306 } 307 return !OnlyPHIUses; 308} 309 310/// Hoist - When an instruction is found to use only loop invariant operands 311/// that are safe to hoist, this instruction is called to do the dirty work. 312/// 313void MachineLICM::Hoist(MachineInstr &MI) { 314 if (!IsLoopInvariantInst(MI)) return; 315 if (!IsProfitableToHoist(MI)) return; 316 317 // Now move the instructions to the predecessor, inserting it before any 318 // terminator instructions. 319 DEBUG({ 320 DOUT << "Hoisting " << MI; 321 if (CurPreheader->getBasicBlock()) 322 DOUT << " to MachineBasicBlock " 323 << CurPreheader->getBasicBlock()->getName(); 324 if (MI.getParent()->getBasicBlock()) 325 DOUT << " from MachineBasicBlock " 326 << MI.getParent()->getBasicBlock()->getName(); 327 DOUT << "\n"; 328 }); 329 330 CurPreheader->splice(CurPreheader->getFirstTerminator(), MI.getParent(), &MI); 331 332 ++NumHoisted; 333 Changed = true; 334} 335