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