MachineLICM.cpp revision af6949d0b1e1545dff21c5e492fbf1760aa74b59
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/CommandLine.h" 34#include "llvm/Support/Compiler.h" 35#include "llvm/Support/Debug.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 DOUT << "******** Machine LICM ********\n"; 130 131 Changed = false; 132 TM = &MF.getTarget(); 133 TII = TM->getInstrInfo(); 134 RegInfo = &MF.getRegInfo(); 135 136 // Get our Loop information... 137 LI = &getAnalysis<MachineLoopInfo>(); 138 DT = &getAnalysis<MachineDominatorTree>(); 139 140 for (MachineLoopInfo::iterator 141 I = LI->begin(), E = LI->end(); I != E; ++I) { 142 CurLoop = *I; 143 144 // Only visit outer-most preheader-sporting loops. 145 if (!LoopIsOuterMostWithPreheader(CurLoop)) 146 continue; 147 148 // Determine the block to which to hoist instructions. If we can't find a 149 // suitable loop preheader, we can't do any hoisting. 150 // 151 // FIXME: We are only hoisting if the basic block coming into this loop 152 // has only one successor. This isn't the case in general because we haven't 153 // broken critical edges or added preheaders. 154 CurPreheader = CurLoop->getLoopPreheader(); 155 if (!CurPreheader) 156 continue; 157 158 HoistRegion(DT->getNode(CurLoop->getHeader())); 159 } 160 161 return Changed; 162} 163 164/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 165/// dominated by the specified block, and that are in the current loop) in depth 166/// first order w.r.t the DominatorTree. This allows us to visit definitions 167/// before uses, allowing us to hoist a loop body in one pass without iteration. 168/// 169void MachineLICM::HoistRegion(MachineDomTreeNode *N) { 170 assert(N != 0 && "Null dominator tree node?"); 171 MachineBasicBlock *BB = N->getBlock(); 172 173 // If this subregion is not in the top level loop at all, exit. 174 if (!CurLoop->contains(BB)) return; 175 176 for (MachineBasicBlock::iterator 177 MII = BB->begin(), E = BB->end(); MII != E; ) { 178 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 179 MachineInstr &MI = *MII; 180 181 Hoist(MI); 182 183 MII = NextMII; 184 } 185 186 const std::vector<MachineDomTreeNode*> &Children = N->getChildren(); 187 188 for (unsigned I = 0, E = Children.size(); I != E; ++I) 189 HoistRegion(Children[I]); 190} 191 192/// IsLoopInvariantInst - Returns true if the instruction is loop 193/// invariant. I.e., all virtual register operands are defined outside of the 194/// loop, physical registers aren't accessed explicitly, and there are no side 195/// effects that aren't captured by the operands or other flags. 196/// 197bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) { 198 const TargetInstrDesc &TID = I.getDesc(); 199 200 // Ignore stuff that we obviously can't hoist. 201 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 202 TID.hasUnmodeledSideEffects()) 203 return false; 204 205 if (TID.mayLoad()) { 206 // Okay, this instruction does a load. As a refinement, we allow the target 207 // to decide whether the loaded value is actually a constant. If so, we can 208 // actually use it as a load. 209 if (!TII->isInvariantLoad(&I)) 210 // FIXME: we should be able to sink loads with no other side effects if 211 // there is nothing that can change memory from here until the end of 212 // block. This is a trivial form of alias analysis. 213 return false; 214 } 215 216 DEBUG({ 217 DOUT << "--- Checking if we can hoist " << I; 218 if (I.getDesc().getImplicitUses()) { 219 DOUT << " * Instruction has implicit uses:\n"; 220 221 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 222 for (const unsigned *ImpUses = I.getDesc().getImplicitUses(); 223 *ImpUses; ++ImpUses) 224 DOUT << " -> " << TRI->getName(*ImpUses) << "\n"; 225 } 226 227 if (I.getDesc().getImplicitDefs()) { 228 DOUT << " * Instruction has implicit defines:\n"; 229 230 const TargetRegisterInfo *TRI = TM->getRegisterInfo(); 231 for (const unsigned *ImpDefs = I.getDesc().getImplicitDefs(); 232 *ImpDefs; ++ImpDefs) 233 DOUT << " -> " << TRI->getName(*ImpDefs) << "\n"; 234 } 235 }); 236 237 if (I.getDesc().getImplicitDefs() || I.getDesc().getImplicitUses()) { 238 DOUT << "Cannot hoist with implicit defines or uses\n"; 239 return false; 240 } 241 242 // The instruction is loop invariant if all of its operands are. 243 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 244 const MachineOperand &MO = I.getOperand(i); 245 246 if (!MO.isReg()) 247 continue; 248 249 unsigned Reg = MO.getReg(); 250 if (Reg == 0) continue; 251 252 // Don't hoist an instruction that uses or defines a physical register. 253 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 254 return false; 255 256 if (!MO.isUse()) 257 continue; 258 259 assert(RegInfo->getVRegDef(Reg) && 260 "Machine instr not mapped for this vreg?!"); 261 262 // If the loop contains the definition of an operand, then the instruction 263 // isn't loop invariant. 264 if (CurLoop->contains(RegInfo->getVRegDef(Reg)->getParent())) 265 return false; 266 } 267 268 // If we got this far, the instruction is loop invariant! 269 return true; 270} 271 272 273/// HasPHIUses - Return true if the specified register has any PHI use. 274static bool HasPHIUses(unsigned Reg, MachineRegisterInfo *RegInfo) { 275 for (MachineRegisterInfo::use_iterator UI = RegInfo->use_begin(Reg), 276 UE = RegInfo->use_end(); UI != UE; ++UI) { 277 MachineInstr *UseMI = &*UI; 278 if (UseMI->getOpcode() == TargetInstrInfo::PHI) 279 return true; 280 } 281 return false; 282} 283 284/// IsProfitableToHoist - Return true if it is potentially profitable to hoist 285/// the given loop invariant. 286bool MachineLICM::IsProfitableToHoist(MachineInstr &MI) { 287 const TargetInstrDesc &TID = MI.getDesc(); 288 289 // FIXME: For now, only hoist re-materilizable instructions. LICM will 290 // increase register pressure. We want to make sure it doesn't increase 291 // spilling. 292 if (!TID.mayLoad() && (!TID.isRematerializable() || 293 !TII->isTriviallyReMaterializable(&MI))) 294 return false; 295 296 // If result(s) of this instruction is used by PHIs, then don't hoist it. 297 // The presence of joins makes it difficult for current register allocator 298 // implementation to perform remat. 299 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 300 const MachineOperand &MO = MI.getOperand(i); 301 if (!MO.isReg() || !MO.isDef()) 302 continue; 303 if (HasPHIUses(MO.getReg(), RegInfo)) 304 return false; 305 } 306 307 return true; 308} 309 310static const MachineInstr *LookForDuplicate(const MachineInstr *MI, 311 std::vector<const MachineInstr*> &PrevMIs) { 312 unsigned NumOps = MI->getNumOperands(); 313 for (unsigned i = 0, e = PrevMIs.size(); i != e; ++i) { 314 const MachineInstr *PrevMI = PrevMIs[i]; 315 unsigned NumOps2 = PrevMI->getNumOperands(); 316 if (NumOps != NumOps2) 317 continue; 318 bool IsSame = true; 319 for (unsigned j = 0; j != NumOps; ++j) { 320 const MachineOperand &MO = MI->getOperand(j); 321 if (MO.isReg() && MO.isDef()) 322 continue; 323 if (!MO.isIdenticalTo(PrevMI->getOperand(j))) { 324 IsSame = false; 325 break; 326 } 327 } 328 if (IsSame) 329 return PrevMI; 330 } 331 return 0; 332} 333 334/// Hoist - When an instruction is found to use only loop invariant operands 335/// that are safe to hoist, this instruction is called to do the dirty work. 336/// 337void MachineLICM::Hoist(MachineInstr &MI) { 338 if (!IsLoopInvariantInst(MI)) return; 339 if (!IsProfitableToHoist(MI)) return; 340 341 // Now move the instructions to the predecessor, inserting it before any 342 // terminator instructions. 343 DEBUG({ 344 DOUT << "Hoisting " << MI; 345 if (CurPreheader->getBasicBlock()) 346 DOUT << " to MachineBasicBlock " 347 << CurPreheader->getBasicBlock()->getName(); 348 if (MI.getParent()->getBasicBlock()) 349 DOUT << " from MachineBasicBlock " 350 << MI.getParent()->getBasicBlock()->getName(); 351 DOUT << "\n"; 352 }); 353 354 // Look for opportunity to CSE the hoisted instruction. 355 std::pair<unsigned, unsigned> BBOpcPair = 356 std::make_pair(CurPreheader->getNumber(), MI.getOpcode()); 357 DenseMap<std::pair<unsigned, unsigned>, 358 std::vector<const MachineInstr*> >::iterator CI = CSEMap.find(BBOpcPair); 359 bool DoneCSE = false; 360 if (CI != CSEMap.end()) { 361 const MachineInstr *Dup = LookForDuplicate(&MI, CI->second); 362 if (Dup) { 363 DOUT << "CSEing " << MI; 364 DOUT << " with " << *Dup; 365 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 366 const MachineOperand &MO = MI.getOperand(i); 367 if (MO.isReg() && MO.isDef()) 368 RegInfo->replaceRegWith(MO.getReg(), Dup->getOperand(i).getReg()); 369 } 370 MI.eraseFromParent(); 371 DoneCSE = true; 372 ++NumCSEed; 373 } 374 } 375 376 // Otherwise, splice the instruction to the preheader. 377 if (!DoneCSE) { 378 CurPreheader->splice(CurPreheader->getFirstTerminator(), 379 MI.getParent(), &MI); 380 // Add to the CSE map. 381 if (CI != CSEMap.end()) 382 CI->second.push_back(&MI); 383 else { 384 std::vector<const MachineInstr*> CSEMIs; 385 CSEMIs.push_back(&MI); 386 CSEMap.insert(std::make_pair(BBOpcPair, CSEMIs)); 387 } 388 } 389 390 ++NumHoisted; 391 Changed = true; 392} 393