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   MF = &mf;
137   TRI = MF->getSubtarget().getRegisterInfo();
138 
139   LiveRegs.clear();
140   NumRegUnits = TRI->getNumRegUnits();
141 
142   MBBReachingDefs.resize(mf.getNumBlockIDs());
143 
144   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
145 
146   // Initialize the MBBOutRegsInfos
147   MBBOutRegsInfos.resize(mf.getNumBlockIDs());
148 
149   // Traverse the basic blocks.
150   LoopTraversal Traversal;
151   LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
152   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
153     processBasicBlock(TraversedMBB);
154   }
155 
156   // Sorting all reaching defs found for a ceartin reg unit in a given BB.
157   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
158     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
159       llvm::sort(RegUnitDefs);
160   }
161 
162   return false;
163 }
164 
165 void ReachingDefAnalysis::releaseMemory() {
166   // Clear the internal vectors.
167   MBBOutRegsInfos.clear();
168   MBBReachingDefs.clear();
169   InstIds.clear();
170 }
171 
172 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
173   assert(InstIds.count(MI) && "Unexpected machine instuction.");
174   int InstId = InstIds[MI];
175   int DefRes = ReachingDefDefaultVal;
176   unsigned MBBNumber = MI->getParent()->getNumber();
177   assert(MBBNumber < MBBReachingDefs.size() &&
178          "Unexpected basic block number.");
179   int LatestDef = ReachingDefDefaultVal;
180   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
181     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
182       if (Def >= InstId)
183         break;
184       DefRes = Def;
185     }
186     LatestDef = std::max(LatestDef, DefRes);
187   }
188   return LatestDef;
189 }
190 
191 MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI, int PhysReg) {
192   return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
193 }
194 
195 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
196                                              int PhysReg) {
197   MachineBasicBlock *ParentA = A->getParent();
198   MachineBasicBlock *ParentB = B->getParent();
199   if (ParentA != ParentB)
200     return false;
201 
202   return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
203 }
204 
205 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
206                                                  int InstId) {
207   assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
208          "Unexpected basic block number.");
209   assert(InstId < static_cast<int>(MBB->size()) &&
210          "Unexpected instruction id.");
211 
212   if (InstId < 0)
213     return nullptr;
214 
215   for (auto &MI : *MBB) {
216     if (InstIds.count(&MI) && InstIds[&MI] == InstId)
217       return &MI;
218   }
219   return nullptr;
220 }
221 
222 int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
223   assert(InstIds.count(MI) && "Unexpected machine instuction.");
224   return InstIds[MI] - getReachingDef(MI, PhysReg);
225 }
226 
227 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
228     SmallVectorImpl<MachineInstr*> &Uses) {
229   MachineBasicBlock *MBB = Def->getParent();
230   MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
231   while (++MI != MBB->end()) {
232     // If/when we find a new reaching def, we know that there's no more uses
233     // of 'Def'.
234     if (getReachingMIDef(&*MI, PhysReg) != Def)
235       return;
236 
237     for (auto &MO : MI->operands()) {
238       if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
239         continue;
240 
241       Uses.push_back(&*MI);
242       if (MO.isKill())
243         return;
244     }
245   }
246 }
247 
248 unsigned ReachingDefAnalysis::getNumUses(MachineInstr *Def, int PhysReg) {
249   SmallVector<MachineInstr*, 4> Uses;
250   getReachingLocalUses(Def, PhysReg, Uses);
251   return Uses.size();
252 }
253 
254 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) {
255   MachineBasicBlock *MBB = MI->getParent();
256   LivePhysRegs LiveRegs(*TRI);
257   LiveRegs.addLiveOuts(*MBB);
258 
259   // Yes if the register is live out of the basic block.
260   if (LiveRegs.contains(PhysReg))
261     return true;
262 
263   // Walk backwards through the block to see if the register is live at some
264   // point.
265   for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
266     LiveRegs.stepBackward(*Last);
267     if (LiveRegs.contains(PhysReg))
268       return InstIds[&*Last] > InstIds[MI];
269   }
270   return false;
271 }
272 
273 bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) {
274   MachineBasicBlock *MBB = MI->getParent();
275   LivePhysRegs LiveRegs(*TRI);
276   LiveRegs.addLiveOuts(*MBB);
277   if (!LiveRegs.contains(PhysReg))
278     return false;
279 
280   MachineInstr *Last = &MBB->back();
281   int Def = getReachingDef(MI, PhysReg);
282   if (getReachingDef(Last, PhysReg) != Def)
283     return false;
284 
285   // Finally check that the last instruction doesn't redefine the register.
286   for (auto &MO : Last->operands())
287     if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
288       return false;
289 
290   return true;
291 }
292 
293 MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
294                                                         int PhysReg) {
295   LivePhysRegs LiveRegs(*TRI);
296   LiveRegs.addLiveOuts(*MBB);
297   if (!LiveRegs.contains(PhysReg))
298     return nullptr;
299 
300   MachineInstr *Last = &MBB->back();
301   int Def = getReachingDef(Last, PhysReg);
302   for (auto &MO : Last->operands())
303     if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
304       return Last;
305 
306   return Def < 0 ? nullptr : getInstFromId(MBB, Def);
307 }
308 
309 MachineInstr *ReachingDefAnalysis::getInstWithUseBefore(MachineInstr *MI,
310     int PhysReg) {
311   auto I = MachineBasicBlock::reverse_iterator(MI);
312   auto E = MI->getParent()->rend();
313   I++;
314 
315   for ( ; I != E; I++)
316     for (auto &MO : I->operands())
317       if (MO.isReg() && MO.isUse() && MO.getReg() == PhysReg)
318         return &*I;
319 
320   return nullptr;
321 }
322 
323 void ReachingDefAnalysis::getAllInstWithUseBefore(MachineInstr *MI,
324     int PhysReg, SmallVectorImpl<MachineInstr*> &Uses) {
325   MachineInstr *Use = nullptr;
326   MachineInstr *Pos = MI;
327 
328   while ((Use = getInstWithUseBefore(Pos, PhysReg))) {
329     Uses.push_back(Use);
330     Pos = Use;
331   }
332 }
333