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