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
21using namespace llvm;
22
23namespace opts {
24extern cl::opt<unsigned> Verbosity;
25extern cl::OptionCategory BoltOptCategory;
26
27cl::opt<bool> AssumeABI("assume-abi",
28 cl::desc("assume the ABI is never violated"),
29 cl::cat(BoltOptCategory));
30}
31
32namespace llvm {
33namespace bolt {
34
35RegAnalysis::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(Callback: [&](BinaryFunction *Func) -> bool {
46 BitVector RegsKilled = getFunctionClobberList(Func);
47 bool Updated = RegsKilledMap.find(x: Func) == RegsKilledMap.end() ||
48 RegsKilledMap[Func] != RegsKilled;
49 if (Updated)
50 RegsKilledMap[Func] = std::move(RegsKilled);
51 return Updated;
52 });
53
54 CGWalker.registerVisitor(Callback: [&](BinaryFunction *Func) -> bool {
55 BitVector RegsGen = getFunctionUsedRegsList(Func);
56 bool Updated = RegsGenMap.find(x: 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(x: 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
109void 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(Regs&: BV);
117 BV.flip();
118 Result |= BV;
119 break;
120 }
121 case ConservativeStrategy::CLOBBERS_NONE:
122 Result.reset();
123 break;
124 }
125}
126
127bool 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(Regs&: BV);
134 BV |= Vec;
135 return BV.all();
136 }
137 case ConservativeStrategy::CLOBBERS_NONE:
138 return Vec.none();
139 }
140 return false;
141}
142
143void 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, Regs&: RegSet);
148 else
149 BC.MIB->getUsedRegs(Inst, Regs&: RegSet);
150 return;
151 }
152
153 // If no call graph supplied...
154 if (RegsKilledMap.size() == 0) {
155 beConservative(Result&: 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(Result&: RegSet);
163 return;
164 }
165
166 const BinaryFunction *Function = BC.getFunctionForSymbol(Symbol: 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(Result&: RegSet);
172 return;
173 }
174 if (GetClobbers) {
175 auto BV = RegsKilledMap.find(x: 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(x: Function);
185 if (BV != RegsGenMap.end()) {
186 RegSet |= BV->second;
187 return;
188 }
189}
190
191void RegAnalysis::getInstClobberList(const MCInst &Inst,
192 BitVector &KillSet) const {
193 return getInstUsedRegsList(Inst, RegSet&: KillSet, /*GetClobbers*/ true);
194}
195
196BitVector RegAnalysis::getFunctionUsedRegsList(const BinaryFunction *Func) {
197 BitVector UsedRegs = BitVector(BC.MRI->getNumRegs(), false);
198
199 if (!Func->isSimple() || !Func->hasCFG()) {
200 beConservative(Result&: UsedRegs);
201 return UsedRegs;
202 }
203
204 for (const BinaryBasicBlock &BB : *Func) {
205 for (const MCInst &Inst : BB) {
206 getInstUsedRegsList(Inst, RegSet&: UsedRegs, /*GetClobbers*/ false);
207 if (UsedRegs.all())
208 return UsedRegs;
209 }
210 }
211
212 return UsedRegs;
213}
214
215BitVector RegAnalysis::getFunctionClobberList(const BinaryFunction *Func) {
216 BitVector RegsKilled = BitVector(BC.MRI->getNumRegs(), false);
217
218 if (!Func->isSimple() || !Func->hasCFG()) {
219 beConservative(Result&: RegsKilled);
220 return RegsKilled;
221 }
222
223 for (const BinaryBasicBlock &BB : *Func) {
224 for (const MCInst &Inst : BB) {
225 getInstClobberList(Inst, KillSet&: RegsKilled);
226 if (RegsKilled.all())
227 return RegsKilled;
228 }
229 }
230
231 return RegsKilled;
232}
233
234void RegAnalysis::printStats() {
235 BC.outs() << "BOLT-INFO REG ANALYSIS: Number of functions conservatively "
236 "treated as clobbering all registers: "
237 << NumFunctionsAllClobber
238 << format(Fmt: " (%.1lf%% dyn cov)\n",
239 Vals: (100.0 * CountFunctionsAllClobber / CountDenominator));
240}
241
242} // namespace bolt
243} // namespace llvm
244

source code of bolt/lib/Passes/RegAnalysis.cpp