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