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 #include "llvm/Support/Debug.h"
13 
14 using namespace llvm;
15 
16 #define DEBUG_TYPE "reaching-deps-analysis"
17 
19 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
20  true)
21 
22 void ReachingDefAnalysis::enterBasicBlock(
23  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
24 
25  MachineBasicBlock *MBB = TraversedMBB.MBB;
26  unsigned MBBNumber = MBB->getNumber();
27  assert(MBBNumber < MBBReachingDefs.size() &&
28  "Unexpected basic block number.");
29  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
30 
31  // Reset instruction counter in each basic block.
32  CurInstr = 0;
33 
34  // Set up LiveRegs to represent registers entering MBB.
35  // Default values are 'nothing happened a long time ago'.
36  if (LiveRegs.empty())
37  LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
38 
39  // This is the entry block.
40  if (MBB->pred_empty()) {
41  for (const auto &LI : MBB->liveins()) {
42  for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
43  // Treat function live-ins as if they were defined just before the first
44  // instruction. Usually, function arguments are set up immediately
45  // before the call.
46  LiveRegs[*Unit] = -1;
47  MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
48  }
49  }
50  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
51  return;
52  }
53 
54  // Try to coalesce live-out registers from predecessors.
55  for (MachineBasicBlock *pred : MBB->predecessors()) {
56  assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
57  "Should have pre-allocated MBBInfos for all MBBs");
58  const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
59  // Incoming is null if this is a backedge from a BB
60  // we haven't processed yet
61  if (Incoming.empty())
62  continue;
63 
64  for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
65  // Use the most recent predecessor def for each register.
66  LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
67  if ((LiveRegs[Unit] != ReachingDefDefaultVal))
68  MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
69  }
70  }
71 
73  << (!TraversedMBB.IsDone ? ": incomplete\n"
74  : ": all preds known\n"));
75 }
76 
77 void ReachingDefAnalysis::leaveBasicBlock(
78  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
79  assert(!LiveRegs.empty() && "Must enter basic block first.");
80  unsigned MBBNumber = TraversedMBB.MBB->getNumber();
81  assert(MBBNumber < MBBOutRegsInfos.size() &&
82  "Unexpected basic block number.");
83  // Save register clearances at end of MBB - used by enterBasicBlock().
84  MBBOutRegsInfos[MBBNumber] = LiveRegs;
85 
86  // While processing the basic block, we kept `Def` relative to the start
87  // of the basic block for convenience. However, future use of this information
88  // only cares about the clearance from the end of the block, so adjust
89  // everything to be relative to the end of the basic block.
90  for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
91  OutLiveReg -= CurInstr;
92  LiveRegs.clear();
93 }
94 
95 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
96  assert(!MI->isDebugInstr() && "Won't process debug instructions");
97 
98  unsigned MBBNumber = MI->getParent()->getNumber();
99  assert(MBBNumber < MBBReachingDefs.size() &&
100  "Unexpected basic block number.");
101  const MCInstrDesc &MCID = MI->getDesc();
102  for (unsigned i = 0,
103  e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
104  i != e; ++i) {
105  MachineOperand &MO = MI->getOperand(i);
106  if (!MO.isReg() || !MO.getReg())
107  continue;
108  if (MO.isUse())
109  continue;
110  for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
111  // This instruction explicitly defines the current reg unit.
112  LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
113  << '\t' << *MI);
114 
115  // How many instructions since this reg unit was last written?
116  LiveRegs[*Unit] = CurInstr;
117  MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
118  }
119  }
120  InstIds[MI] = CurInstr;
121  ++CurInstr;
122 }
123 
124 void ReachingDefAnalysis::processBasicBlock(
125  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
126  enterBasicBlock(TraversedMBB);
127  for (MachineInstr &MI : *TraversedMBB.MBB) {
128  if (!MI.isDebugInstr())
129  processDefs(&MI);
130  }
131  leaveBasicBlock(TraversedMBB);
132 }
133 
135  if (skipFunction(mf.getFunction()))
136  return false;
137  MF = &mf;
138  TRI = MF->getSubtarget().getRegisterInfo();
139 
140  LiveRegs.clear();
141  NumRegUnits = TRI->getNumRegUnits();
142 
143  MBBReachingDefs.resize(mf.getNumBlockIDs());
144 
145  LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
146 
147  // Initialize the MBBOutRegsInfos
148  MBBOutRegsInfos.resize(mf.getNumBlockIDs());
149 
150  // Traverse the basic blocks.
151  LoopTraversal Traversal;
152  LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
153  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
154  processBasicBlock(TraversedMBB);
155  }
156 
157  // Sorting all reaching defs found for a ceartin reg unit in a given BB.
158  for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
159  for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
160  llvm::sort(RegUnitDefs);
161  }
162 
163  return false;
164 }
165 
167  // Clear the internal vectors.
168  MBBOutRegsInfos.clear();
169  MBBReachingDefs.clear();
170  InstIds.clear();
171 }
172 
174  assert(InstIds.count(MI) && "Unexpected machine instuction.");
175  int InstId = InstIds[MI];
176  int DefRes = ReachingDefDefaultVal;
177  unsigned MBBNumber = MI->getParent()->getNumber();
178  assert(MBBNumber < MBBReachingDefs.size() &&
179  "Unexpected basic block number.");
180  int LatestDef = ReachingDefDefaultVal;
181  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
182  for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
183  if (Def >= InstId)
184  break;
185  DefRes = Def;
186  }
187  LatestDef = std::max(LatestDef, DefRes);
188  }
189  return LatestDef;
190 }
191 
193  assert(InstIds.count(MI) && "Unexpected machine instuction.");
194  return InstIds[MI] - getReachingDef(MI, PhysReg);
195 }
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:179
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:413
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
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.
constexpr double e
Definition: MathExtras.h:57
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
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
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:630
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:255
Representation of each machine instruction.
Definition: MachineInstr.h:63
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:415
void resize(size_type N)
Definition: SmallVector.h:344