1 //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- 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 #include "llvm/CodeGen/LivePhysRegs.h"
10 #include "llvm/CodeGen/ReachingDefAnalysis.h"
11 #include "llvm/CodeGen/TargetRegisterInfo.h"
12 #include "llvm/CodeGen/TargetSubtargetInfo.h"
13 #include "llvm/Support/Debug.h"
14 
15 using namespace llvm;
16 
17 #define DEBUG_TYPE "reaching-deps-analysis"
18 
19 char ReachingDefAnalysis::ID = 0;
20 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
21                 true)
22 
23 void ReachingDefAnalysis::enterBasicBlock(
24     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
25 
26   MachineBasicBlock *MBB = TraversedMBB.MBB;
27   unsigned MBBNumber = MBB->getNumber();
28   assert(MBBNumber < MBBReachingDefs.size() &&
29          "Unexpected basic block number.");
30   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
31 
32   // Reset instruction counter in each basic block.
33   CurInstr = 0;
34 
35   // Set up LiveRegs to represent registers entering MBB.
36   // Default values are 'nothing happened a long time ago'.
37   if (LiveRegs.empty())
38     LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
39 
40   // This is the entry block.
41   if (MBB->pred_empty()) {
42     for (const auto &LI : MBB->liveins()) {
43       for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
44         // Treat function live-ins as if they were defined just before the first
45         // instruction.  Usually, function arguments are set up immediately
46         // before the call.
47         LiveRegs[*Unit] = -1;
48         MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
49       }
50     }
51     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
52     return;
53   }
54 
55   // Try to coalesce live-out registers from predecessors.
56   for (MachineBasicBlock *pred : MBB->predecessors()) {
57     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
58            "Should have pre-allocated MBBInfos for all MBBs");
59     const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
60     // Incoming is null if this is a backedge from a BB
61     // we haven't processed yet
62     if (Incoming.empty())
63       continue;
64 
65     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
66       // Use the most recent predecessor def for each register.
67       LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
68       if ((LiveRegs[Unit] != ReachingDefDefaultVal))
69         MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
70     }
71   }
72 
73   LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
74                     << (!TraversedMBB.IsDone ? ": incomplete\n"
75                                              : ": all preds known\n"));
76 }
77 
78 void ReachingDefAnalysis::leaveBasicBlock(
79     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
80   assert(!LiveRegs.empty() && "Must enter basic block first.");
81   unsigned MBBNumber = TraversedMBB.MBB->getNumber();
82   assert(MBBNumber < MBBOutRegsInfos.size() &&
83          "Unexpected basic block number.");
84   // Save register clearances at end of MBB - used by enterBasicBlock().
85   MBBOutRegsInfos[MBBNumber] = LiveRegs;
86 
87   // While processing the basic block, we kept `Def` relative to the start
88   // of the basic block for convenience. However, future use of this information
89   // only cares about the clearance from the end of the block, so adjust
90   // everything to be relative to the end of the basic block.
91   for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
92     OutLiveReg -= CurInstr;
93   LiveRegs.clear();
94 }
95 
96 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
97   assert(!MI->isDebugInstr() && "Won't process debug instructions");
98 
99   unsigned MBBNumber = MI->getParent()->getNumber();
100   assert(MBBNumber < MBBReachingDefs.size() &&
101          "Unexpected basic block number.");
102   const MCInstrDesc &MCID = MI->getDesc();
103   for (unsigned i = 0,
104                 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
105        i != e; ++i) {
106     MachineOperand &MO = MI->getOperand(i);
107     if (!MO.isReg() || !MO.getReg())
108       continue;
109     if (MO.isUse())
110       continue;
111     for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
112       // This instruction explicitly defines the current reg unit.
113       LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
114                         << '\t' << *MI);
115 
116       // How many instructions since this reg unit was last written?
117       LiveRegs[*Unit] = CurInstr;
118       MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
119     }
120   }
121   InstIds[MI] = CurInstr;
122   ++CurInstr;
123 }
124 
125 void ReachingDefAnalysis::processBasicBlock(
126     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
127   enterBasicBlock(TraversedMBB);
128   for (MachineInstr &MI : *TraversedMBB.MBB) {
129     if (!MI.isDebugInstr())
130       processDefs(&MI);
131   }
132   leaveBasicBlock(TraversedMBB);
133 }
134 
135 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
136   if (skipFunction(mf.getFunction()))
137     return false;
138   MF = &mf;
139   TRI = MF->getSubtarget().getRegisterInfo();
140 
141   LiveRegs.clear();
142   NumRegUnits = TRI->getNumRegUnits();
143 
144   MBBReachingDefs.resize(mf.getNumBlockIDs());
145 
146   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
147 
148   // Initialize the MBBOutRegsInfos
149   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
150 
151   // Traverse the basic blocks.
152   LoopTraversal Traversal;
153   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
154   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
155     processBasicBlock(TraversedMBB);
156   }
157 
158   // Sorting all reaching defs found for a ceartin reg unit in a given BB.
159   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
160     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
161       llvm::sort(RegUnitDefs);
162   }
163 
164   return false;
165 }
166 
167 void ReachingDefAnalysis::releaseMemory() {
168   // Clear the internal vectors.
169   MBBOutRegsInfos.clear();
170   MBBReachingDefs.clear();
171   InstIds.clear();
172 }
173 
174 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
175   assert(InstIds.count(MI) && "Unexpected machine instuction.");
176   int InstId = InstIds[MI];
177   int DefRes = ReachingDefDefaultVal;
178   unsigned MBBNumber = MI->getParent()->getNumber();
179   assert(MBBNumber < MBBReachingDefs.size() &&
180          "Unexpected basic block number.");
181   int LatestDef = ReachingDefDefaultVal;
182   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
183     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
184       if (Def >= InstId)
185         break;
186       DefRes = Def;
187     }
188     LatestDef = std::max(LatestDef, DefRes);
189   }
190   return LatestDef;
191 }
192 
193 MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI, int PhysReg) {
194   return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
195 }
196 
197 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
198                                              int PhysReg) {
199   MachineBasicBlock *ParentA = A->getParent();
200   MachineBasicBlock *ParentB = B->getParent();
201   if (ParentA != ParentB)
202     return false;
203 
204   return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
205 }
206 
207 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
208                                                  int InstId) {
209   assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
210          "Unexpected basic block number.");
211   assert(InstId < static_cast<int>(MBB->size()) &&
212          "Unexpected instruction id.");
213 
214   if (InstId < 0)
215     return nullptr;
216 
217   for (auto &MI : *MBB) {
218     if (InstIds.count(&MI) && InstIds[&MI] == InstId)
219       return &MI;
220   }
221   return nullptr;
222 }
223 
224 int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
225   assert(InstIds.count(MI) && "Unexpected machine instuction.");
226   return InstIds[MI] - getReachingDef(MI, PhysReg);
227 }
228 
229 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
230     SmallVectorImpl<MachineInstr*> &Uses) {
231   MachineBasicBlock *MBB = Def->getParent();
232   MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
233   while (++MI != MBB->end()) {
234     for (auto &MO : MI->operands()) {
235       if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
236         continue;
237 
238       // If/when we find a new reaching def, we know that there's no more uses
239       // of 'Def'.
240       if (getReachingMIDef(&*MI, PhysReg) != Def)
241         return;
242 
243       Uses.push_back(&*MI);
244       if (MO.isKill())
245         return;
246     }
247   }
248 }
249 
250 unsigned ReachingDefAnalysis::getNumUses(MachineInstr *Def, int PhysReg) {
251   SmallVector<MachineInstr*, 4> Uses;
252   getReachingLocalUses(Def, PhysReg, Uses);
253   return Uses.size();
254 }
255 
256 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) {
257   MachineBasicBlock *MBB = MI->getParent();
258   LivePhysRegs LiveRegs(*TRI);
259   LiveRegs.addLiveOuts(*MBB);
260 
261   // Yes if the register is live out of the basic block.
262   if (LiveRegs.contains(PhysReg))
263     return true;
264 
265   // Walk backwards through the block to see if the register is live at some
266   // point.
267   for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
268     LiveRegs.stepBackward(*Last);
269     if (LiveRegs.contains(PhysReg))
270       return InstIds[&*Last] > InstIds[MI];
271   }
272   return false;
273 }
274 
275 MachineInstr *ReachingDefAnalysis::getInstWithUseBefore(MachineInstr *MI,
276     int PhysReg) {
277   auto I = MachineBasicBlock::reverse_iterator(MI);
278   auto E = MI->getParent()->rend();
279   I++;
280 
281   for ( ; I != E; I++)
282     for (auto &MO : I->operands())
283       if (MO.isReg() && MO.isUse() && MO.getReg() == PhysReg)
284         return &*I;
285 
286   return nullptr;
287 }
288 
289 void ReachingDefAnalysis::getAllInstWithUseBefore(MachineInstr *MI,
290     int PhysReg, SmallVectorImpl<MachineInstr*> &Uses) {
291   MachineInstr *Use = nullptr;
292   MachineInstr *Pos = MI;
293 
294   while ((Use = getInstWithUseBefore(Pos, PhysReg))) {
295     Uses.push_back(Use);
296     Pos = Use;
297   }
298 }
299