xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/MachineLoopInfo.cpp (revision c7a063741720ef81d4caa4613242579d12f1d605)
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