1 //===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===// 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 // natural loops may actually be several loops that share the same header node. 12 // 13 // This analysis calculates the nesting structure of loops in a function. For 14 // each natural loop identified, this analysis identifies natural loops 15 // contained entirely within the loop and the basic blocks the make up the loop. 16 // 17 // It can calculate on the fly various bits of information, for example: 18 // 19 // * whether there is a preheader for the loop 20 // * the number of back edges to the header 21 // * whether or not a particular block branches out of the loop 22 // * the successor blocks of the loop 23 // * the loop depth 24 // * the trip count 25 // * etc... 26 // 27 //===----------------------------------------------------------------------===// 28 29 #ifndef LLVM_CODEGEN_MACHINELOOPINFO_H 30 #define LLVM_CODEGEN_MACHINELOOPINFO_H 31 32 #include "llvm/CodeGen/MachineBasicBlock.h" 33 #include "llvm/CodeGen/MachineFunctionPass.h" 34 #include "llvm/CodeGen/MachinePassManager.h" 35 #include "llvm/IR/CFG.h" 36 #include "llvm/IR/DebugLoc.h" 37 #include "llvm/Support/Compiler.h" 38 #include "llvm/Support/GenericLoopInfo.h" 39 40 namespace llvm { 41 42 class MachineDominatorTree; 43 // Implementation in LoopInfoImpl.h 44 class MachineLoop; 45 extern template class LoopBase<MachineBasicBlock, MachineLoop>; 46 47 class MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> { 48 public: 49 /// Return the "top" block in the loop, which is the first block in the linear 50 /// layout, ignoring any parts of the loop not contiguous with the part that 51 /// contains the header. 52 LLVM_ABI MachineBasicBlock *getTopBlock(); 53 54 /// Return the "bottom" block in the loop, which is the last block in the 55 /// linear layout, ignoring any parts of the loop not contiguous with the part 56 /// that contains the header. 57 LLVM_ABI MachineBasicBlock *getBottomBlock(); 58 59 /// Find the block that contains the loop control variable and the 60 /// loop test. This will return the latch block if it's one of the exiting 61 /// blocks. Otherwise, return the exiting block. Return 'null' when 62 /// multiple exiting blocks are present. 63 LLVM_ABI MachineBasicBlock *findLoopControlBlock() const; 64 65 /// Return the debug location of the start of this loop. 66 /// This looks for a BB terminating instruction with a known debug 67 /// location by looking at the preheader and header blocks. If it 68 /// cannot find a terminating instruction with location information, 69 /// it returns an unknown location. 70 LLVM_ABI DebugLoc getStartLoc() const; 71 72 /// Find the llvm.loop metadata for this loop. 73 /// If each branch to the header of this loop contains the same llvm.loop 74 /// metadata, then this metadata node is returned. Otherwise, if any 75 /// latch instruction does not contain the llvm.loop metadata or 76 /// multiple latch instructions contain different llvm.loop metadata nodes, 77 /// then null is returned. 78 LLVM_ABI MDNode *getLoopID() const; 79 80 /// Returns true if the instruction is loop invariant. 81 /// I.e., all virtual register operands are defined outside of the loop, 82 /// physical registers aren't accessed explicitly, and there are no side 83 /// effects that aren't captured by the operands or other flags. 84 /// ExcludeReg can be used to exclude the given register from the check 85 /// i.e. when we're considering hoisting it's definition but not hoisted it 86 /// yet 87 LLVM_ABI bool isLoopInvariant(MachineInstr &I, 88 const Register ExcludeReg = 0) const; 89 90 LLVM_ABI void dump() const; 91 92 private: 93 friend class LoopInfoBase<MachineBasicBlock, MachineLoop>; 94 95 /// Returns true if the given physreg has no defs inside the loop. 96 bool isLoopInvariantImplicitPhysReg(Register Reg) const; 97 MachineLoop(MachineBasicBlock * MBB)98 explicit MachineLoop(MachineBasicBlock *MBB) 99 : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {} 100 101 MachineLoop() = default; 102 }; 103 104 // Implementation in LoopInfoImpl.h 105 extern template class LLVM_TEMPLATE_ABI 106 LoopInfoBase<MachineBasicBlock, MachineLoop>; 107 108 class MachineLoopInfo : public LoopInfoBase<MachineBasicBlock, MachineLoop> { 109 friend class LoopBase<MachineBasicBlock, MachineLoop>; 110 friend class MachineLoopInfoWrapperPass; 111 112 public: 113 MachineLoopInfo() = default; MachineLoopInfo(MachineDominatorTree & MDT)114 explicit MachineLoopInfo(MachineDominatorTree &MDT) { calculate(MDT); } 115 MachineLoopInfo(MachineLoopInfo &&) = default; 116 MachineLoopInfo(const MachineLoopInfo &) = delete; 117 MachineLoopInfo &operator=(const MachineLoopInfo &) = delete; 118 119 /// Handle invalidation explicitly. 120 LLVM_ABI bool invalidate(MachineFunction &, const PreservedAnalyses &PA, 121 MachineFunctionAnalysisManager::Invalidator &); 122 123 /// Find the block that either is the loop preheader, or could 124 /// speculatively be used as the preheader. This is e.g. useful to place 125 /// loop setup code. Code that cannot be speculated should not be placed 126 /// here. SpeculativePreheader is controlling whether it also tries to 127 /// find the speculative preheader if the regular preheader is not present. 128 /// With FindMultiLoopPreheader = false, nullptr will be returned if the found 129 /// preheader is the preheader of multiple loops. 130 LLVM_ABI MachineBasicBlock * 131 findLoopPreheader(MachineLoop *L, bool SpeculativePreheader = false, 132 bool FindMultiLoopPreheader = false) const; 133 134 /// Calculate the natural loop information. 135 LLVM_ABI void calculate(MachineDominatorTree &MDT); 136 }; 137 138 /// Analysis pass that exposes the \c MachineLoopInfo for a machine function. 139 class MachineLoopAnalysis : public AnalysisInfoMixin<MachineLoopAnalysis> { 140 friend AnalysisInfoMixin<MachineLoopAnalysis>; 141 LLVM_ABI static AnalysisKey Key; 142 143 public: 144 using Result = MachineLoopInfo; 145 LLVM_ABI Result run(MachineFunction &MF, 146 MachineFunctionAnalysisManager &MFAM); 147 }; 148 149 /// Printer pass for the \c LoopAnalysis results. 150 class MachineLoopPrinterPass : public PassInfoMixin<MachineLoopPrinterPass> { 151 raw_ostream &OS; 152 153 public: MachineLoopPrinterPass(raw_ostream & OS)154 explicit MachineLoopPrinterPass(raw_ostream &OS) : OS(OS) {} 155 LLVM_ABI PreservedAnalyses run(MachineFunction &MF, 156 MachineFunctionAnalysisManager &MFAM); isRequired()157 static bool isRequired() { return true; } 158 }; 159 160 class LLVM_ABI MachineLoopInfoWrapperPass : public MachineFunctionPass { 161 MachineLoopInfo LI; 162 163 public: 164 static char ID; // Pass identification, replacement for typeid 165 166 MachineLoopInfoWrapperPass(); 167 168 bool runOnMachineFunction(MachineFunction &F) override; 169 releaseMemory()170 void releaseMemory() override { LI.releaseMemory(); } 171 172 void getAnalysisUsage(AnalysisUsage &AU) const override; 173 getLI()174 MachineLoopInfo &getLI() { return LI; } 175 }; 176 177 // Allow clients to walk the list of nested loops... 178 template <> struct GraphTraits<const MachineLoop*> { 179 using NodeRef = const MachineLoop *; 180 using ChildIteratorType = MachineLoopInfo::iterator; 181 182 static NodeRef getEntryNode(const MachineLoop *L) { return L; } 183 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 184 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 185 }; 186 187 template <> struct GraphTraits<MachineLoop*> { 188 using NodeRef = MachineLoop *; 189 using ChildIteratorType = MachineLoopInfo::iterator; 190 191 static NodeRef getEntryNode(MachineLoop *L) { return L; } 192 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 193 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 194 }; 195 196 } // end namespace llvm 197 198 #endif // LLVM_CODEGEN_MACHINELOOPINFO_H 199