Line data Source code
1 : //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #include "llvm/CodeGen/ReachingDefAnalysis.h"
11 : #include "llvm/CodeGen/TargetRegisterInfo.h"
12 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
13 :
14 : using namespace llvm;
15 :
16 : #define DEBUG_TYPE "reaching-deps-analysis"
17 :
18 : char ReachingDefAnalysis::ID = 0;
19 277470 : INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
20 : true)
21 :
22 437466 : void ReachingDefAnalysis::enterBasicBlock(
23 : const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
24 :
25 437466 : MachineBasicBlock *MBB = TraversedMBB.MBB;
26 437466 : unsigned MBBNumber = MBB->getNumber();
27 : assert(MBBNumber < MBBReachingDefs.size() &&
28 : "Unexpected basic block number.");
29 874932 : MBBReachingDefs[MBBNumber].resize(NumRegUnits);
30 :
31 : // Reset instruction counter in each basic block.
32 437466 : CurInstr = 0;
33 :
34 : // Set up LiveRegs to represent registers entering MBB.
35 : // Default values are 'nothing happened a long time ago'.
36 437466 : if (LiveRegs.empty())
37 437466 : LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
38 :
39 : // This is the entry block.
40 437466 : if (MBB->pred_empty()) {
41 371700 : for (const auto &LI : MBB->liveins()) {
42 683416 : 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 873160 : LiveRegs[*Unit] = -1;
47 873160 : 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 756675 : for (MachineBasicBlock *pred : MBB->predecessors()) {
56 : assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
57 : "Should have pre-allocated MBBInfos for all MBBs");
58 444073 : 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 444073 : if (Incoming.empty())
62 : continue;
63 :
64 70588377 : for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
65 : // Use the most recent predecessor def for each register.
66 140301606 : LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
67 70150803 : if ((LiveRegs[Unit] != ReachingDefDefaultVal))
68 27472910 : MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
69 : }
70 : }
71 :
72 : LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
73 : << (!TraversedMBB.IsDone ? ": incomplete\n"
74 : : ": all preds known\n"));
75 : }
76 :
77 437466 : void ReachingDefAnalysis::leaveBasicBlock(
78 : const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
79 : assert(!LiveRegs.empty() && "Must enter basic block first.");
80 437466 : 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 874932 : 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 69619291 : for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
91 69181825 : OutLiveReg -= CurInstr;
92 : LiveRegs.clear();
93 437466 : }
94 :
95 2979549 : void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
96 : assert(!MI->isDebugInstr() && "Won't process debug instructions");
97 :
98 2979549 : unsigned MBBNumber = MI->getParent()->getNumber();
99 : assert(MBBNumber < MBBReachingDefs.size() &&
100 : "Unexpected basic block number.");
101 2979549 : const MCInstrDesc &MCID = MI->getDesc();
102 1647201 : for (unsigned i = 0,
103 2979550 : e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
104 4626751 : i != e; ++i) {
105 1647201 : MachineOperand &MO = MI->getOperand(i);
106 1647201 : if (!MO.isReg() || !MO.getReg())
107 : continue;
108 1547368 : if (MO.isUse())
109 : continue;
110 5545475 : 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 2744193 : LiveRegs[*Unit] = CurInstr;
117 8232579 : MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
118 : }
119 : }
120 2979550 : InstIds[MI] = CurInstr;
121 2979550 : ++CurInstr;
122 2979550 : }
123 :
124 437466 : void ReachingDefAnalysis::processBasicBlock(
125 : const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
126 437466 : enterBasicBlock(TraversedMBB);
127 3560951 : for (MachineInstr &MI : *TraversedMBB.MBB) {
128 : if (!MI.isDebugInstr())
129 2979550 : processDefs(&MI);
130 : }
131 437466 : leaveBasicBlock(TraversedMBB);
132 437466 : }
133 :
134 125006 : bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
135 125006 : if (skipFunction(mf.getFunction()))
136 : return false;
137 124864 : MF = &mf;
138 124864 : TRI = MF->getSubtarget().getRegisterInfo();
139 :
140 : LiveRegs.clear();
141 124864 : NumRegUnits = TRI->getNumRegUnits();
142 :
143 249728 : MBBReachingDefs.resize(mf.getNumBlockIDs());
144 :
145 : LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
146 :
147 : // Initialize the MBBOutRegsInfos
148 249728 : MBBOutRegsInfos.resize(mf.getNumBlockIDs());
149 :
150 : // Traverse the basic blocks.
151 : LoopTraversal Traversal;
152 124864 : LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
153 562330 : for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
154 437466 : processBasicBlock(TraversedMBB);
155 : }
156 :
157 : // Sorting all reaching defs found for a ceartin reg unit in a given BB.
158 492195 : for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
159 58002734 : for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
160 : llvm::sort(RegUnitDefs);
161 : }
162 :
163 : return false;
164 : }
165 :
166 125019 : void ReachingDefAnalysis::releaseMemory() {
167 : // Clear the internal vectors.
168 125019 : MBBOutRegsInfos.clear();
169 : MBBReachingDefs.clear();
170 125019 : InstIds.clear();
171 125019 : }
172 :
173 14320 : int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
174 : assert(InstIds.count(MI) && "Unexpected machine instuction.");
175 14320 : int InstId = InstIds[MI];
176 14320 : int DefRes = ReachingDefDefaultVal;
177 14320 : unsigned MBBNumber = MI->getParent()->getNumber();
178 : assert(MBBNumber < MBBReachingDefs.size() &&
179 : "Unexpected basic block number.");
180 14320 : int LatestDef = ReachingDefDefaultVal;
181 28864 : for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
182 71717 : for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
183 53552 : if (Def >= InstId)
184 : break;
185 42629 : DefRes = Def;
186 : }
187 14544 : LatestDef = std::max(LatestDef, DefRes);
188 : }
189 14320 : return LatestDef;
190 : }
191 :
192 7024 : int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
193 : assert(InstIds.count(MI) && "Unexpected machine instuction.");
194 7024 : return InstIds[MI] - getReachingDef(MI, PhysReg);
195 : }
|
