LLVM  10.0.0svn
ReachingDefAnalysis.cpp
Go to the documentation of this file.
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 
12 
13 using namespace llvm;
14 
15 #define DEBUG_TYPE "reaching-deps-analysis"
16 
18 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
19  true)
20 
21 void ReachingDefAnalysis::enterBasicBlock(
22  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
23 
24  MachineBasicBlock *MBB = TraversedMBB.MBB;
25  unsigned MBBNumber = MBB->getNumber();
26  assert(MBBNumber < MBBReachingDefs.size() &&
27  "Unexpected basic block number.");
28  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
29 
30  // Reset instruction counter in each basic block.
31  CurInstr = 0;
32 
33  // Set up LiveRegs to represent registers entering MBB.
34  // Default values are 'nothing happened a long time ago'.
35  if (LiveRegs.empty())
36  LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
37 
38  // This is the entry block.
39  if (MBB->pred_empty()) {
40  for (const auto &LI : MBB->liveins()) {
41  for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
42  // Treat function live-ins as if they were defined just before the first
43  // instruction. Usually, function arguments are set up immediately
44  // before the call.
45  LiveRegs[*Unit] = -1;
46  MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
47  }
48  }
49  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
50  return;
51  }
52 
53  // Try to coalesce live-out registers from predecessors.
54  for (MachineBasicBlock *pred : MBB->predecessors()) {
55  assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
56  "Should have pre-allocated MBBInfos for all MBBs");
57  const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
58  // Incoming is null if this is a backedge from a BB
59  // we haven't processed yet
60  if (Incoming.empty())
61  continue;
62 
63  for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
64  // Use the most recent predecessor def for each register.
65  LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
66  if ((LiveRegs[Unit] != ReachingDefDefaultVal))
67  MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
68  }
69  }
70 
72  << (!TraversedMBB.IsDone ? ": incomplete\n"
73  : ": all preds known\n"));
74 }
75 
76 void ReachingDefAnalysis::leaveBasicBlock(
77  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
78  assert(!LiveRegs.empty() && "Must enter basic block first.");
79  unsigned MBBNumber = TraversedMBB.MBB->getNumber();
80  assert(MBBNumber < MBBOutRegsInfos.size() &&
81  "Unexpected basic block number.");
82  // Save register clearances at end of MBB - used by enterBasicBlock().
83  MBBOutRegsInfos[MBBNumber] = LiveRegs;
84 
85  // While processing the basic block, we kept `Def` relative to the start
86  // of the basic block for convenience. However, future use of this information
87  // only cares about the clearance from the end of the block, so adjust
88  // everything to be relative to the end of the basic block.
89  for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
90  OutLiveReg -= CurInstr;
91  LiveRegs.clear();
92 }
93 
94 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
95  assert(!MI->isDebugInstr() && "Won't process debug instructions");
96 
97  unsigned MBBNumber = MI->getParent()->getNumber();
98  assert(MBBNumber < MBBReachingDefs.size() &&
99  "Unexpected basic block number.");
100  const MCInstrDesc &MCID = MI->getDesc();
101  for (unsigned i = 0,
102  e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
103  i != e; ++i) {
104  MachineOperand &MO = MI->getOperand(i);
105  if (!MO.isReg() || !MO.getReg())
106  continue;
107  if (MO.isUse())
108  continue;
109  for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
110  // This instruction explicitly defines the current reg unit.
111  LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
112  << '\t' << *MI);
113 
114  // How many instructions since this reg unit was last written?
115  LiveRegs[*Unit] = CurInstr;
116  MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
117  }
118  }
119  InstIds[MI] = CurInstr;
120  ++CurInstr;
121 }
122 
123 void ReachingDefAnalysis::processBasicBlock(
124  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
125  enterBasicBlock(TraversedMBB);
126  for (MachineInstr &MI : *TraversedMBB.MBB) {
127  if (!MI.isDebugInstr())
128  processDefs(&MI);
129  }
130  leaveBasicBlock(TraversedMBB);
131 }
132 
134  if (skipFunction(mf.getFunction()))
135  return false;
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 
166  // Clear the internal vectors.
167  MBBOutRegsInfos.clear();
168  MBBReachingDefs.clear();
169  InstIds.clear();
170 }
171 
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 
192  assert(InstIds.count(MI) && "Unexpected machine instuction.");
193  return InstIds[MI] - getReachingDef(MI, PhysReg);
194 }
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
void push_back(const T &Elt)
Definition: SmallVector.h:211
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:178
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
unsigned const TargetRegisterInfo * TRI
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false, true) void ReachingDefAnalysis
This class provides the reaching def analysis.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:408
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
iterator_range< pred_iterator > predecessors()
size_t size() const
Definition: SmallVector.h:52
bool isDebugInstr() const
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
hexagon gen pred
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool isVariadic(QueryType Type=IgnoreBundle) const
Return true if this instruction can have a variable number of operands.
Definition: MachineInstr.h:625
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
Representation of each machine instruction.
Definition: MachineInstr.h:64
int getClearance(MachineInstr *MI, MCPhysReg PhysReg)
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
TraversalOrder traverse(MachineFunction &MF)
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
int getReachingDef(MachineInstr *MI, int PhysReg)
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
aarch64 promote const
IRTranslator LLVM IR MI
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:166
Register getReg() const
getReg - Returns the register number.
#define DEBUG_TYPE
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
void resize(size_type N)
Definition: SmallVector.h:344