Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/ReachingDefAnalysis.cpp @ 134:3a76565eade5 LLVM5.0.1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 5.0.1
author mir3636
date Sat, 17 Feb 2018 09:57:20 +0900
parents
children c2174574ed3a
comparison
equal deleted inserted replaced
133:c60214abe0e8 134:3a76565eade5
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 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, ReachingDedDefaultVal);
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 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] != ReachingDedDefaultVal))
68 MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
69 }
70 }
71
72 DEBUG(dbgs() << printMBBReference(*MBB)
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->isDebugValue() && "Won't process debug values");
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 DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr << '\t'
113 << *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.isDebugValue())
129 processDefs(&MI);
130 }
131 leaveBasicBlock(TraversedMBB);
132 }
133
134 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
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 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 std::sort(RegUnitDefs.begin(), RegUnitDefs.end());
161 }
162
163 return false;
164 }
165
166 void ReachingDefAnalysis::releaseMemory() {
167 // Clear the internal vectors.
168 MBBOutRegsInfos.clear();
169 MBBReachingDefs.clear();
170 InstIds.clear();
171 }
172
173 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
174 assert(InstIds.count(MI) && "Unexpected machine instuction.");
175 int InstId = InstIds[MI];
176 int DefRes = ReachingDedDefaultVal;
177 unsigned MBBNumber = MI->getParent()->getNumber();
178 assert(MBBNumber < MBBReachingDefs.size() &&
179 "Unexpected basic block number.");
180 int LatestDef = ReachingDedDefaultVal;
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
192 int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
193 assert(InstIds.count(MI) && "Unexpected machine instuction.");
194 return InstIds[MI] - getReachingDef(MI, PhysReg);
195 }