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