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