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