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
15using namespace llvm;
16
17#define DEBUG_TYPE "reaching-deps-analysis"
18
19char ReachingDefAnalysis::ID = 0;
20INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
21                true)
22
23void 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
78void 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
96void 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
125void 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
135bool 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
165void ReachingDefAnalysis::releaseMemory() {
166  // Clear the internal vectors.
167  MBBOutRegsInfos.clear();
168  MBBReachingDefs.clear();
169  InstIds.clear();
170}
171
172int 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
191MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI, int PhysReg) {
192  return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
193}
194
195bool 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
205MachineInstr *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
222int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
223  assert(InstIds.count(MI) && "Unexpected machine instuction.");
224  return InstIds[MI] - getReachingDef(MI, PhysReg);
225}
226
227void 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
248unsigned ReachingDefAnalysis::getNumUses(MachineInstr *Def, int PhysReg) {
249  SmallVector<MachineInstr*, 4> Uses;
250  getReachingLocalUses(Def, PhysReg, Uses);
251  return Uses.size();
252}
253
254bool 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
273bool 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
293MachineInstr* 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
309MachineInstr *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
323void 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