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