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