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("assume-abi",
28                         cl::desc("assume the ABI is never violated"),
29                         cl::cat(BoltOptCategory));
30 }
31 
32 namespace llvm {
33 namespace bolt {
34 
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 
109 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 
127 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 
143 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 
191 void RegAnalysis::getInstClobberList(const MCInst &Inst,
192                                      BitVector &KillSet) const {
193   return getInstUsedRegsList(Inst, KillSet, /*GetClobbers*/ true);
194 }
195 
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 
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 
234 void RegAnalysis::printStats() {
235   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