1 //===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the MachineLoopInfo class that is used to identify natural 10 // loops and determine the loop depth of various nodes of the CFG. Note that 11 // the loops identified may actually be several natural loops that share the 12 // same header node... not just a single natural loop. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/CodeGen/MachineLoopInfo.h" 17 #include "llvm/Analysis/LoopInfoImpl.h" 18 #include "llvm/CodeGen/MachineDominators.h" 19 #include "llvm/CodeGen/MachineRegisterInfo.h" 20 #include "llvm/CodeGen/Passes.h" 21 #include "llvm/CodeGen/TargetInstrInfo.h" 22 #include "llvm/CodeGen/TargetSubtargetInfo.h" 23 #include "llvm/Config/llvm-config.h" 24 #include "llvm/InitializePasses.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/raw_ostream.h" 27 28 using namespace llvm; 29 30 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops. 31 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>; 32 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>; 33 34 char MachineLoopInfo::ID = 0; 35 MachineLoopInfo::MachineLoopInfo() : MachineFunctionPass(ID) { 36 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 37 } 38 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops", 39 "Machine Natural Loop Construction", true, true) 40 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 41 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops", 42 "Machine Natural Loop Construction", true, true) 43 44 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID; 45 46 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) { 47 calculate(getAnalysis<MachineDominatorTree>()); 48 return false; 49 } 50 51 void MachineLoopInfo::calculate(MachineDominatorTree &MDT) { 52 releaseMemory(); 53 LI.analyze(MDT.getBase()); 54 } 55 56 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 57 AU.setPreservesAll(); 58 AU.addRequired<MachineDominatorTree>(); 59 MachineFunctionPass::getAnalysisUsage(AU); 60 } 61 62 MachineBasicBlock *MachineLoop::getTopBlock() { 63 MachineBasicBlock *TopMBB = getHeader(); 64 MachineFunction::iterator Begin = TopMBB->getParent()->begin(); 65 if (TopMBB->getIterator() != Begin) { 66 MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator()); 67 while (contains(PriorMBB)) { 68 TopMBB = PriorMBB; 69 if (TopMBB->getIterator() == Begin) 70 break; 71 PriorMBB = &*std::prev(TopMBB->getIterator()); 72 } 73 } 74 return TopMBB; 75 } 76 77 MachineBasicBlock *MachineLoop::getBottomBlock() { 78 MachineBasicBlock *BotMBB = getHeader(); 79 MachineFunction::iterator End = BotMBB->getParent()->end(); 80 if (BotMBB->getIterator() != std::prev(End)) { 81 MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator()); 82 while (contains(NextMBB)) { 83 BotMBB = NextMBB; 84 if (BotMBB == &*std::next(BotMBB->getIterator())) 85 break; 86 NextMBB = &*std::next(BotMBB->getIterator()); 87 } 88 } 89 return BotMBB; 90 } 91 92 MachineBasicBlock *MachineLoop::findLoopControlBlock() { 93 if (MachineBasicBlock *Latch = getLoopLatch()) { 94 if (isLoopExiting(Latch)) 95 return Latch; 96 else 97 return getExitingBlock(); 98 } 99 return nullptr; 100 } 101 102 DebugLoc MachineLoop::getStartLoc() const { 103 // Try the pre-header first. 104 if (MachineBasicBlock *PHeadMBB = getLoopPreheader()) 105 if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock()) 106 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc()) 107 return DL; 108 109 // If we have no pre-header or there are no instructions with debug 110 // info in it, try the header. 111 if (MachineBasicBlock *HeadMBB = getHeader()) 112 if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock()) 113 return HeadBB->getTerminator()->getDebugLoc(); 114 115 return DebugLoc(); 116 } 117 118 MachineBasicBlock * 119 MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader, 120 bool FindMultiLoopPreheader) const { 121 if (MachineBasicBlock *PB = L->getLoopPreheader()) 122 return PB; 123 124 if (!SpeculativePreheader) 125 return nullptr; 126 127 MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch(); 128 if (HB->pred_size() != 2 || HB->hasAddressTaken()) 129 return nullptr; 130 // Find the predecessor of the header that is not the latch block. 131 MachineBasicBlock *Preheader = nullptr; 132 for (MachineBasicBlock *P : HB->predecessors()) { 133 if (P == LB) 134 continue; 135 // Sanity. 136 if (Preheader) 137 return nullptr; 138 Preheader = P; 139 } 140 141 // Check if the preheader candidate is a successor of any other loop 142 // headers. We want to avoid having two loop setups in the same block. 143 if (!FindMultiLoopPreheader) { 144 for (MachineBasicBlock *S : Preheader->successors()) { 145 if (S == HB) 146 continue; 147 MachineLoop *T = getLoopFor(S); 148 if (T && T->getHeader() == S) 149 return nullptr; 150 } 151 } 152 return Preheader; 153 } 154 155 bool MachineLoop::isLoopInvariant(MachineInstr &I) const { 156 MachineFunction *MF = I.getParent()->getParent(); 157 MachineRegisterInfo *MRI = &MF->getRegInfo(); 158 const TargetSubtargetInfo &ST = MF->getSubtarget(); 159 const TargetRegisterInfo *TRI = ST.getRegisterInfo(); 160 const TargetInstrInfo *TII = ST.getInstrInfo(); 161 162 // The instruction is loop invariant if all of its operands are. 163 for (const MachineOperand &MO : I.operands()) { 164 if (!MO.isReg()) 165 continue; 166 167 Register Reg = MO.getReg(); 168 if (Reg == 0) continue; 169 170 // An instruction that uses or defines a physical register can't e.g. be 171 // hoisted, so mark this as not invariant. 172 if (Register::isPhysicalRegister(Reg)) { 173 if (MO.isUse()) { 174 // If the physreg has no defs anywhere, it's just an ambient register 175 // and we can freely move its uses. Alternatively, if it's allocatable, 176 // it could get allocated to something with a def during allocation. 177 // However, if the physreg is known to always be caller saved/restored 178 // then this use is safe to hoist. 179 if (!MRI->isConstantPhysReg(Reg) && 180 !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) && 181 !TII->isIgnorableUse(MO)) 182 return false; 183 // Otherwise it's safe to move. 184 continue; 185 } else if (!MO.isDead()) { 186 // A def that isn't dead can't be moved. 187 return false; 188 } else if (getHeader()->isLiveIn(Reg)) { 189 // If the reg is live into the loop, we can't hoist an instruction 190 // which would clobber it. 191 return false; 192 } 193 } 194 195 if (!MO.isUse()) 196 continue; 197 198 assert(MRI->getVRegDef(Reg) && 199 "Machine instr not mapped for this vreg?!"); 200 201 // If the loop contains the definition of an operand, then the instruction 202 // isn't loop invariant. 203 if (contains(MRI->getVRegDef(Reg))) 204 return false; 205 } 206 207 // If we got this far, the instruction is loop invariant! 208 return true; 209 } 210 211 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 212 LLVM_DUMP_METHOD void MachineLoop::dump() const { 213 print(dbgs()); 214 } 215 #endif 216