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/TargetInstrInfo.h"
21 #include "llvm/CodeGen/TargetSubtargetInfo.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/InitializePasses.h"
24 #include "llvm/Pass.h"
25 #include "llvm/PassRegistry.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 (Register::isPhysicalRegister(Reg)) {
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