xref: /llvm-project/bolt/lib/Passes/RegReAssign.cpp (revision 139744ac5388e86139b1e33e0bf25359947e2522) 
1 //===- bolt/Passes/RegReAssign.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 RegReAssign class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "bolt/Passes/RegReAssign.h"
14 #include "bolt/Core/MCPlus.h"
15 #include "bolt/Passes/BinaryFunctionCallGraph.h"
16 #include "bolt/Passes/DataflowAnalysis.h"
17 #include "bolt/Passes/DataflowInfoManager.h"
18 #include "bolt/Utils/Utils.h"
19 #include <numeric>
20 
21 #define DEBUG_TYPE "regreassign"
22 
23 using namespace llvm;
24 
25 namespace opts {
26 extern cl::OptionCategory BoltOptCategory;
27 extern cl::opt<bool> UpdateDebugSections;
28 
29 static cl::opt<bool>
30 AggressiveReAssign("use-aggr-reg-reassign",
31   cl::desc("use register liveness analysis to try to find more opportunities "
32            "for -reg-reassign optimization"),
33   cl::init(false),
34   cl::ZeroOrMore,
35   cl::cat(BoltOptCategory));
36 
37 }
38 
39 namespace llvm {
40 namespace bolt {
41 
42 void RegReAssign::swap(BinaryFunction &Function, MCPhysReg A, MCPhysReg B) {
43   BinaryContext &BC = Function.getBinaryContext();
44   const BitVector &AliasA = BC.MIB->getAliases(A, false);
45   const BitVector &AliasB = BC.MIB->getAliases(B, false);
46 
47   // Regular instructions
48   for (BinaryBasicBlock &BB : Function) {
49     for (MCInst &Inst : BB) {
50       for (MCOperand &Operand : MCPlus::primeOperands(Inst)) {
51         if (!Operand.isReg())
52           continue;
53 
54         unsigned Reg = Operand.getReg();
55         if (AliasA.test(Reg)) {
56           Operand.setReg(BC.MIB->getAliasSized(B, BC.MIB->getRegSize(Reg)));
57           --StaticBytesSaved;
58           DynBytesSaved -= BB.getKnownExecutionCount();
59           continue;
60         }
61         if (!AliasB.test(Reg))
62           continue;
63         Operand.setReg(BC.MIB->getAliasSized(A, BC.MIB->getRegSize(Reg)));
64         ++StaticBytesSaved;
65         DynBytesSaved += BB.getKnownExecutionCount();
66       }
67     }
68   }
69 
70   // CFI
71   DenseSet<const MCCFIInstruction *> Changed;
72   for (BinaryBasicBlock &BB : Function) {
73     for (MCInst &Inst : BB) {
74       if (!BC.MIB->isCFI(Inst))
75         continue;
76       const MCCFIInstruction *CFI = Function.getCFIFor(Inst);
77       if (Changed.count(CFI))
78         continue;
79       Changed.insert(CFI);
80 
81       switch (CFI->getOperation()) {
82       case MCCFIInstruction::OpRegister: {
83         const unsigned CFIReg2 = CFI->getRegister2();
84         const MCPhysReg Reg2 = *BC.MRI->getLLVMRegNum(CFIReg2, /*isEH=*/false);
85         if (AliasA.test(Reg2)) {
86           Function.setCFIFor(
87               Inst, MCCFIInstruction::createRegister(
88                         nullptr, CFI->getRegister(),
89                         BC.MRI->getDwarfRegNum(
90                             BC.MIB->getAliasSized(B, BC.MIB->getRegSize(Reg2)),
91                             false)));
92         } else if (AliasB.test(Reg2)) {
93           Function.setCFIFor(
94               Inst, MCCFIInstruction::createRegister(
95                         nullptr, CFI->getRegister(),
96                         BC.MRI->getDwarfRegNum(
97                             BC.MIB->getAliasSized(A, BC.MIB->getRegSize(Reg2)),
98                             false)));
99         }
100       }
101       LLVM_FALLTHROUGH;
102       case MCCFIInstruction::OpUndefined:
103       case MCCFIInstruction::OpDefCfa:
104       case MCCFIInstruction::OpOffset:
105       case MCCFIInstruction::OpRestore:
106       case MCCFIInstruction::OpSameValue:
107       case MCCFIInstruction::OpDefCfaRegister:
108       case MCCFIInstruction::OpRelOffset:
109       case MCCFIInstruction::OpEscape: {
110         unsigned CFIReg;
111         if (CFI->getOperation() != MCCFIInstruction::OpEscape) {
112           CFIReg = CFI->getRegister();
113         } else {
114           Optional<uint8_t> Reg =
115               readDWARFExpressionTargetReg(CFI->getValues());
116           // Handle DW_CFA_def_cfa_expression
117           if (!Reg)
118             break;
119           CFIReg = *Reg;
120         }
121         const MCPhysReg Reg = *BC.MRI->getLLVMRegNum(CFIReg, /*isEH=*/false);
122         if (AliasA.test(Reg))
123           Function.mutateCFIRegisterFor(
124               Inst,
125               BC.MRI->getDwarfRegNum(
126                   BC.MIB->getAliasSized(B, BC.MIB->getRegSize(Reg)), false));
127         else if (AliasB.test(Reg))
128           Function.mutateCFIRegisterFor(
129               Inst,
130               BC.MRI->getDwarfRegNum(
131                   BC.MIB->getAliasSized(A, BC.MIB->getRegSize(Reg)), false));
132         break;
133       }
134       default:
135         break;
136       }
137     }
138   }
139 }
140 
141 void RegReAssign::rankRegisters(BinaryFunction &Function) {
142   BinaryContext &BC = Function.getBinaryContext();
143   std::fill(RegScore.begin(), RegScore.end(), 0);
144   std::fill(RankedRegs.begin(), RankedRegs.end(), 0);
145 
146   for (BinaryBasicBlock &BB : Function) {
147     for (MCInst &Inst : BB) {
148       const bool CannotUseREX = BC.MIB->cannotUseREX(Inst);
149       const MCInstrDesc &Desc = BC.MII->get(Inst.getOpcode());
150 
151       // Disallow substituitions involving regs in implicit uses lists
152       const MCPhysReg *ImplicitUses = Desc.getImplicitUses();
153       while (ImplicitUses && *ImplicitUses) {
154         const size_t RegEC =
155             BC.MIB->getAliases(*ImplicitUses, false).find_first();
156         RegScore[RegEC] =
157             std::numeric_limits<decltype(RegScore)::value_type>::min();
158         ++ImplicitUses;
159       }
160 
161       // Disallow substituitions involving regs in implicit defs lists
162       const MCPhysReg *ImplicitDefs = Desc.getImplicitDefs();
163       while (ImplicitDefs && *ImplicitDefs) {
164         const size_t RegEC =
165             BC.MIB->getAliases(*ImplicitDefs, false).find_first();
166         RegScore[RegEC] =
167             std::numeric_limits<decltype(RegScore)::value_type>::min();
168         ++ImplicitDefs;
169       }
170 
171       for (int I = 0, E = MCPlus::getNumPrimeOperands(Inst); I != E; ++I) {
172         const MCOperand &Operand = Inst.getOperand(I);
173         if (!Operand.isReg())
174           continue;
175 
176         if (Desc.getOperandConstraint(I, MCOI::TIED_TO) != -1)
177           continue;
178 
179         unsigned Reg = Operand.getReg();
180         size_t RegEC = BC.MIB->getAliases(Reg, false).find_first();
181         if (RegEC == 0)
182           continue;
183 
184         // Disallow substituitions involving regs in instrs that cannot use REX
185         if (CannotUseREX) {
186           RegScore[RegEC] =
187               std::numeric_limits<decltype(RegScore)::value_type>::min();
188           continue;
189         }
190 
191         // Unsupported substitution, cannot swap BH with R* regs, bail
192         if (BC.MIB->isUpper8BitReg(Reg) && ClassicCSR.test(Reg)) {
193           RegScore[RegEC] =
194               std::numeric_limits<decltype(RegScore)::value_type>::min();
195           continue;
196         }
197 
198         RegScore[RegEC] += BB.getKnownExecutionCount();
199       }
200     }
201   }
202   std::iota(RankedRegs.begin(), RankedRegs.end(), 0); // 0, 1, 2, 3...
203   std::sort(RankedRegs.begin(), RankedRegs.end(),
204             [&](size_t A, size_t B) { return RegScore[A] > RegScore[B]; });
205 
206   LLVM_DEBUG({
207     for (size_t Reg : RankedRegs) {
208       if (RegScore[Reg] == 0)
209         continue;
210       dbgs() << Reg << " ";
211       if (RegScore[Reg] > 0)
212         dbgs() << BC.MRI->getName(Reg) << ": " << RegScore[Reg] << "\n";
213       else
214         dbgs() << BC.MRI->getName(Reg) << ": (blacklisted)\n";
215     }
216   });
217 }
218 
219 void RegReAssign::aggressivePassOverFunction(BinaryFunction &Function) {
220   BinaryContext &BC = Function.getBinaryContext();
221   rankRegisters(Function);
222 
223   // Bail early if our registers are all black listed, before running expensive
224   // analysis passes
225   bool Bail = true;
226   int64_t LowScoreClassic = std::numeric_limits<int64_t>::max();
227   for (int J : ClassicRegs.set_bits()) {
228     if (RegScore[J] <= 0)
229       continue;
230     Bail = false;
231     if (RegScore[J] < LowScoreClassic)
232       LowScoreClassic = RegScore[J];
233   }
234   if (Bail)
235     return;
236   BitVector Extended = ClassicRegs;
237   Extended.flip();
238   Extended &= GPRegs;
239   Bail = true;
240   int64_t HighScoreExtended = 0;
241   for (int J : Extended.set_bits()) {
242     if (RegScore[J] <= 0)
243       continue;
244     Bail = false;
245     if (RegScore[J] > HighScoreExtended)
246       HighScoreExtended = RegScore[J];
247   }
248   // Also bail early if there is no profitable substitution even if we assume
249   // all registers can be exchanged
250   if (Bail || (LowScoreClassic << 1) >= HighScoreExtended)
251     return;
252 
253   // -- expensive pass -- determine all regs alive during func start
254   DataflowInfoManager Info(Function, RA.get(), nullptr);
255   BitVector AliveAtStart = *Info.getLivenessAnalysis().getStateAt(
256       ProgramPoint::getFirstPointAt(*Function.begin()));
257   for (BinaryBasicBlock &BB : Function)
258     if (BB.pred_size() == 0)
259       AliveAtStart |= *Info.getLivenessAnalysis().getStateAt(
260           ProgramPoint::getFirstPointAt(BB));
261 
262   // Mark frame pointer alive because of CFI
263   AliveAtStart |= BC.MIB->getAliases(BC.MIB->getFramePointer(), false);
264   // Never touch return registers
265   BC.MIB->getDefaultLiveOut(AliveAtStart);
266 
267   // Try swapping more profitable options first
268   auto Begin = RankedRegs.begin();
269   auto End = std::prev(RankedRegs.end());
270   while (Begin != End) {
271     MCPhysReg ClassicReg = *End;
272     if (!ClassicRegs[ClassicReg] || RegScore[ClassicReg] <= 0) {
273       --End;
274       continue;
275     }
276 
277     MCPhysReg ExtReg = *Begin;
278     if (!Extended[ExtReg] || RegScore[ExtReg] <= 0) {
279       ++Begin;
280       continue;
281     }
282 
283     if (RegScore[ClassicReg] << 1 >= RegScore[ExtReg]) {
284       LLVM_DEBUG(dbgs() << " Ending at " << BC.MRI->getName(ClassicReg)
285                         << " with " << BC.MRI->getName(ExtReg)
286                         << " because exchange is not profitable\n");
287       break;
288     }
289 
290     BitVector AnyAliasAlive = AliveAtStart;
291     AnyAliasAlive &= BC.MIB->getAliases(ClassicReg);
292     if (AnyAliasAlive.any()) {
293       LLVM_DEBUG(dbgs() << " Bailed on " << BC.MRI->getName(ClassicReg)
294                         << " with " << BC.MRI->getName(ExtReg)
295                         << " because classic reg is alive\n");
296       --End;
297       continue;
298     }
299     AnyAliasAlive = AliveAtStart;
300     AnyAliasAlive &= BC.MIB->getAliases(ExtReg);
301     if (AnyAliasAlive.any()) {
302       LLVM_DEBUG(dbgs() << " Bailed on " << BC.MRI->getName(ClassicReg)
303                         << " with " << BC.MRI->getName(ExtReg)
304                         << " because extended reg is alive\n");
305       ++Begin;
306       continue;
307     }
308 
309     // Opportunity detected. Swap.
310     LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(ClassicReg)
311                       << " with " << BC.MRI->getName(ExtReg) << "\n\n");
312     swap(Function, ClassicReg, ExtReg);
313     FuncsChanged.insert(&Function);
314     ++Begin;
315     if (Begin == End)
316       break;
317     --End;
318   }
319 }
320 
321 bool RegReAssign::conservativePassOverFunction(BinaryFunction &Function) {
322   BinaryContext &BC = Function.getBinaryContext();
323   rankRegisters(Function);
324 
325   // Try swapping R12, R13, R14 or R15 with RBX (we work with all callee-saved
326   // regs except RBP)
327   MCPhysReg Candidate = 0;
328   for (int J : ExtendedCSR.set_bits())
329     if (RegScore[J] > RegScore[Candidate])
330       Candidate = J;
331 
332   if (!Candidate || RegScore[Candidate] < 0)
333     return false;
334 
335   // Check if our classic callee-saved reg (RBX is the only one) has lower
336   // score / utilization rate
337   MCPhysReg RBX = 0;
338   for (int I : ClassicCSR.set_bits()) {
339     int64_t ScoreRBX = RegScore[I];
340     if (ScoreRBX <= 0)
341       continue;
342 
343     if (RegScore[Candidate] > (ScoreRBX + 10))
344       RBX = I;
345   }
346 
347   if (!RBX)
348     return false;
349 
350   LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(RBX) << " with "
351                     << BC.MRI->getName(Candidate) << "\n\n");
352   (void)BC;
353   swap(Function, RBX, Candidate);
354   FuncsChanged.insert(&Function);
355   return true;
356 }
357 
358 void RegReAssign::setupAggressivePass(BinaryContext &BC,
359                                       std::map<uint64_t, BinaryFunction> &BFs) {
360   setupConservativePass(BC, BFs);
361   CG.reset(new BinaryFunctionCallGraph(buildCallGraph(BC)));
362   RA.reset(new RegAnalysis(BC, &BFs, &*CG));
363 
364   GPRegs = BitVector(BC.MRI->getNumRegs(), false);
365   BC.MIB->getGPRegs(GPRegs);
366 }
367 
368 void RegReAssign::setupConservativePass(
369     BinaryContext &BC, std::map<uint64_t, BinaryFunction> &BFs) {
370   // Set up constant bitvectors used throughout this analysis
371   ClassicRegs = BitVector(BC.MRI->getNumRegs(), false);
372   CalleeSaved = BitVector(BC.MRI->getNumRegs(), false);
373   ClassicCSR = BitVector(BC.MRI->getNumRegs(), false);
374   ExtendedCSR = BitVector(BC.MRI->getNumRegs(), false);
375   // Never consider the frame pointer
376   BC.MIB->getClassicGPRegs(ClassicRegs);
377   ClassicRegs.flip();
378   ClassicRegs |= BC.MIB->getAliases(BC.MIB->getFramePointer(), false);
379   ClassicRegs.flip();
380   BC.MIB->getCalleeSavedRegs(CalleeSaved);
381   ClassicCSR |= ClassicRegs;
382   ClassicCSR &= CalleeSaved;
383   BC.MIB->getClassicGPRegs(ClassicRegs);
384   ExtendedCSR |= ClassicRegs;
385   ExtendedCSR.flip();
386   ExtendedCSR &= CalleeSaved;
387 
388   LLVM_DEBUG({
389     RegStatePrinter P(BC);
390     dbgs() << "Starting register reassignment\nClassicRegs: ";
391     P.print(dbgs(), ClassicRegs);
392     dbgs() << "\nCalleeSaved: ";
393     P.print(dbgs(), CalleeSaved);
394     dbgs() << "\nClassicCSR: ";
395     P.print(dbgs(), ClassicCSR);
396     dbgs() << "\nExtendedCSR: ";
397     P.print(dbgs(), ExtendedCSR);
398     dbgs() << "\n";
399   });
400 }
401 
402 void RegReAssign::runOnFunctions(BinaryContext &BC) {
403   RegScore = std::vector<int64_t>(BC.MRI->getNumRegs(), 0);
404   RankedRegs = std::vector<size_t>(BC.MRI->getNumRegs(), 0);
405 
406   if (opts::AggressiveReAssign)
407     setupAggressivePass(BC, BC.getBinaryFunctions());
408   else
409     setupConservativePass(BC, BC.getBinaryFunctions());
410 
411   for (auto &I : BC.getBinaryFunctions()) {
412     BinaryFunction &Function = I.second;
413 
414     if (!Function.isSimple() || Function.isIgnored())
415       continue;
416 
417     LLVM_DEBUG(dbgs() << "====================================\n");
418     LLVM_DEBUG(dbgs() << " - " << Function.getPrintName() << "\n");
419     if (!conservativePassOverFunction(Function) && opts::AggressiveReAssign) {
420       aggressivePassOverFunction(Function);
421       LLVM_DEBUG({
422         if (FuncsChanged.count(&Function))
423           dbgs() << "Aggressive pass successful on " << Function.getPrintName()
424                  << "\n";
425       });
426     }
427   }
428 
429   if (FuncsChanged.empty()) {
430     outs() << "BOLT-INFO: Reg Reassignment Pass: no changes were made.\n";
431     return;
432   }
433   if (opts::UpdateDebugSections)
434     outs() << "BOLT-WARNING: You used -reg-reassign and -update-debug-sections."
435            << " Some registers were changed but associated AT_LOCATION for "
436            << "impacted variables were NOT updated! This operation is "
437            << "currently unsupported by BOLT.\n";
438   outs() << "BOLT-INFO: Reg Reassignment Pass Stats:\n";
439   outs() << "\t   " << FuncsChanged.size() << " functions affected.\n";
440   outs() << "\t   " << StaticBytesSaved << " static bytes saved.\n";
441   outs() << "\t   " << DynBytesSaved << " dynamic bytes saved.\n";
442 }
443 
444 } // namespace bolt
445 } // namespace llvm
446