1 //===- bolt/Passes/RegAnalysis.cpp ----------------------------------------===//
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 // This file implements the RegAnalysis class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "bolt/Passes/RegAnalysis.h"
14 #include "bolt/Core/BinaryFunction.h"
15 #include "bolt/Core/CallGraphWalker.h"
16 #include "llvm/MC/MCRegisterInfo.h"
17 #include "llvm/Support/CommandLine.h"
18
19 #define DEBUG_TYPE "ra"
20
21 using namespace llvm;
22
23 namespace opts {
24 extern cl::opt<unsigned> Verbosity;
25 extern cl::OptionCategory BoltOptCategory;
26
27 cl::opt<bool> AssumeABI("assume-abi",
28 cl::desc("assume the ABI is never violated"),
29 cl::cat(BoltOptCategory));
30 }
31
32 namespace llvm {
33 namespace bolt {
34
RegAnalysis(BinaryContext & BC,std::map<uint64_t,BinaryFunction> * BFs,BinaryFunctionCallGraph * CG)35 RegAnalysis::RegAnalysis(BinaryContext &BC,
36 std::map<uint64_t, BinaryFunction> *BFs,
37 BinaryFunctionCallGraph *CG)
38 : BC(BC), CS(opts::AssumeABI ? ConservativeStrategy::CLOBBERS_ABI
39 : ConservativeStrategy::CLOBBERS_ALL) {
40 if (!CG)
41 return;
42
43 CallGraphWalker CGWalker(*CG);
44
45 CGWalker.registerVisitor([&](BinaryFunction *Func) -> bool {
46 BitVector RegsKilled = getFunctionClobberList(Func);
47 bool Updated = RegsKilledMap.find(Func) == RegsKilledMap.end() ||
48 RegsKilledMap[Func] != RegsKilled;
49 if (Updated)
50 RegsKilledMap[Func] = std::move(RegsKilled);
51 return Updated;
52 });
53
54 CGWalker.registerVisitor([&](BinaryFunction *Func) -> bool {
55 BitVector RegsGen = getFunctionUsedRegsList(Func);
56 bool Updated = RegsGenMap.find(Func) == RegsGenMap.end() ||
57 RegsGenMap[Func] != RegsGen;
58 if (Updated)
59 RegsGenMap[Func] = std::move(RegsGen);
60 return Updated;
61 });
62
63 CGWalker.walk();
64
65 if (opts::Verbosity == 0) {
66 #ifndef NDEBUG
67 if (!DebugFlag || !isCurrentDebugType(DEBUG_TYPE))
68 return;
69 #else
70 return;
71 #endif
72 }
73
74 if (!BFs)
75 return;
76
77 // This loop is for computing statistics only
78 for (auto &MapEntry : *BFs) {
79 BinaryFunction *Func = &MapEntry.second;
80 auto Iter = RegsKilledMap.find(Func);
81 assert(Iter != RegsKilledMap.end() &&
82 "Failed to compute all clobbers list");
83 if (Iter->second.all()) {
84 uint64_t Count = Func->getExecutionCount();
85 if (Count != BinaryFunction::COUNT_NO_PROFILE)
86 CountFunctionsAllClobber += Count;
87 ++NumFunctionsAllClobber;
88 }
89 DEBUG_WITH_TYPE("ra",
90 dbgs() << "Killed regs set for func: " << Func->getPrintName() << "\n";
91 const BitVector &RegsKilled = Iter->second;
92 int RegIdx = RegsKilled.find_first();
93 while (RegIdx != -1) {
94 dbgs() << "\tREG" << RegIdx;
95 RegIdx = RegsKilled.find_next(RegIdx);
96 };
97 dbgs() << "\nUsed regs set for func: " << Func->getPrintName() << "\n";
98 const BitVector &RegsUsed = RegsGenMap.find(Func)->second;
99 RegIdx = RegsUsed.find_first();
100 while (RegIdx != -1) {
101 dbgs() << "\tREG" << RegIdx;
102 RegIdx = RegsUsed.find_next(RegIdx);
103 };
104 dbgs() << "\n";
105 );
106 }
107 }
108
beConservative(BitVector & Result) const109 void RegAnalysis::beConservative(BitVector &Result) const {
110 switch (CS) {
111 case ConservativeStrategy::CLOBBERS_ALL:
112 Result.set();
113 break;
114 case ConservativeStrategy::CLOBBERS_ABI: {
115 BitVector BV(BC.MRI->getNumRegs(), false);
116 BC.MIB->getCalleeSavedRegs(BV);
117 BV.flip();
118 Result |= BV;
119 break;
120 }
121 case ConservativeStrategy::CLOBBERS_NONE:
122 Result.reset();
123 break;
124 }
125 }
126
isConservative(BitVector & Vec) const127 bool RegAnalysis::isConservative(BitVector &Vec) const {
128 switch (CS) {
129 case ConservativeStrategy::CLOBBERS_ALL:
130 return Vec.all();
131 case ConservativeStrategy::CLOBBERS_ABI: {
132 BitVector BV(BC.MRI->getNumRegs(), false);
133 BC.MIB->getCalleeSavedRegs(BV);
134 BV |= Vec;
135 return BV.all();
136 }
137 case ConservativeStrategy::CLOBBERS_NONE:
138 return Vec.none();
139 }
140 return false;
141 }
142
getInstUsedRegsList(const MCInst & Inst,BitVector & RegSet,bool GetClobbers) const143 void RegAnalysis::getInstUsedRegsList(const MCInst &Inst, BitVector &RegSet,
144 bool GetClobbers) const {
145 if (!BC.MIB->isCall(Inst)) {
146 if (GetClobbers)
147 BC.MIB->getClobberedRegs(Inst, RegSet);
148 else
149 BC.MIB->getUsedRegs(Inst, RegSet);
150 return;
151 }
152
153 // If no call graph supplied...
154 if (RegsKilledMap.size() == 0) {
155 beConservative(RegSet);
156 return;
157 }
158
159 const MCSymbol *TargetSymbol = BC.MIB->getTargetSymbol(Inst);
160 // If indirect call, we know nothing
161 if (TargetSymbol == nullptr) {
162 beConservative(RegSet);
163 return;
164 }
165
166 const BinaryFunction *Function = BC.getFunctionForSymbol(TargetSymbol);
167 if (Function == nullptr) {
168 // Call to a function without a BinaryFunction object.
169 // This should be a call to a PLT entry, and since it is a trampoline to
170 // a DSO, we can't really know the code in advance.
171 beConservative(RegSet);
172 return;
173 }
174 if (GetClobbers) {
175 auto BV = RegsKilledMap.find(Function);
176 if (BV != RegsKilledMap.end()) {
177 RegSet |= BV->second;
178 return;
179 }
180 // Ignore calls to function whose clobber list wasn't yet calculated. This
181 // instruction will be evaluated again once we have info for the callee.
182 return;
183 }
184 auto BV = RegsGenMap.find(Function);
185 if (BV != RegsGenMap.end()) {
186 RegSet |= BV->second;
187 return;
188 }
189 }
190
getInstClobberList(const MCInst & Inst,BitVector & KillSet) const191 void RegAnalysis::getInstClobberList(const MCInst &Inst,
192 BitVector &KillSet) const {
193 return getInstUsedRegsList(Inst, KillSet, /*GetClobbers*/ true);
194 }
195
getFunctionUsedRegsList(const BinaryFunction * Func)196 BitVector RegAnalysis::getFunctionUsedRegsList(const BinaryFunction *Func) {
197 BitVector UsedRegs = BitVector(BC.MRI->getNumRegs(), false);
198
199 if (!Func->isSimple() || !Func->hasCFG()) {
200 beConservative(UsedRegs);
201 return UsedRegs;
202 }
203
204 for (const BinaryBasicBlock &BB : *Func) {
205 for (const MCInst &Inst : BB) {
206 getInstUsedRegsList(Inst, UsedRegs, /*GetClobbers*/ false);
207 if (UsedRegs.all())
208 return UsedRegs;
209 }
210 }
211
212 return UsedRegs;
213 }
214
getFunctionClobberList(const BinaryFunction * Func)215 BitVector RegAnalysis::getFunctionClobberList(const BinaryFunction *Func) {
216 BitVector RegsKilled = BitVector(BC.MRI->getNumRegs(), false);
217
218 if (!Func->isSimple() || !Func->hasCFG()) {
219 beConservative(RegsKilled);
220 return RegsKilled;
221 }
222
223 for (const BinaryBasicBlock &BB : *Func) {
224 for (const MCInst &Inst : BB) {
225 getInstClobberList(Inst, RegsKilled);
226 if (RegsKilled.all())
227 return RegsKilled;
228 }
229 }
230
231 return RegsKilled;
232 }
233
printStats()234 void RegAnalysis::printStats() {
235 BC.outs() << "BOLT-INFO REG ANALYSIS: Number of functions conservatively "
236 "treated as clobbering all registers: "
237 << NumFunctionsAllClobber
238 << format(" (%.1lf%% dyn cov)\n",
239 (100.0 * CountFunctionsAllClobber / CountDenominator));
240 }
241
242 } // namespace bolt
243 } // namespace llvm
244