xref: /llvm-project/bolt/lib/Passes/RegReAssign.cpp (revision 60b09997237c6b4a9d92baa054089bf4d838cdbf) 
1 //===--- 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 //===----------------------------------------------------------------------===//
10 
11 #include "bolt/Passes/RegReAssign.h"
12 #include "bolt/Core/MCPlus.h"
13 #include "bolt/Passes/BinaryFunctionCallGraph.h"
14 #include "bolt/Passes/DataflowAnalysis.h"
15 #include "bolt/Passes/DataflowInfoManager.h"
16 #include "bolt/Utils/Utils.h"
17 #include <numeric>
18 
19 #define DEBUG_TYPE "regreassign"
20 
21 using namespace llvm;
22 
23 namespace opts {
24 extern cl::OptionCategory BoltOptCategory;
25 extern cl::opt<bool> UpdateDebugSections;
26 
27 static cl::opt<bool>
28 AggressiveReAssign("use-aggr-reg-reassign",
29   cl::desc("use register liveness analysis to try to find more opportunities "
30            "for -reg-reassign optimization"),
31   cl::init(false),
32   cl::ZeroOrMore,
33   cl::cat(BoltOptCategory));
34 
35 }
36 
37 namespace llvm {
38 namespace bolt {
39 
40 void RegReAssign::swap(BinaryFunction &Function, MCPhysReg A, MCPhysReg B) {
41   BinaryContext &BC = Function.getBinaryContext();
42   const BitVector &AliasA = BC.MIB->getAliases(A, false);
43   const BitVector &AliasB = BC.MIB->getAliases(B, false);
44 
45   // Regular instructions
46   for (BinaryBasicBlock &BB : Function) {
47     for (MCInst &Inst : BB) {
48       for (int I = 0, E = MCPlus::getNumPrimeOperands(Inst); I != E; ++I) {
49         MCOperand &Operand = Inst.getOperand(I);
50         if (!Operand.isReg())
51           continue;
52 
53         unsigned Reg = Operand.getReg();
54         if (AliasA.test(Reg)) {
55           Operand.setReg(BC.MIB->getAliasSized(B, BC.MIB->getRegSize(Reg)));
56           --StaticBytesSaved;
57           DynBytesSaved -= BB.getKnownExecutionCount();
58           continue;
59         }
60         if (!AliasB.test(Reg))
61           continue;
62         Operand.setReg(BC.MIB->getAliasSized(A, BC.MIB->getRegSize(Reg)));
63         ++StaticBytesSaved;
64         DynBytesSaved += BB.getKnownExecutionCount();
65       }
66     }
67   }
68 
69   // CFI
70   DenseSet<const MCCFIInstruction *> Changed;
71   for (BinaryBasicBlock &BB : Function) {
72     for (MCInst &Inst : BB) {
73       if (!BC.MIB->isCFI(Inst))
74         continue;
75       const MCCFIInstruction *CFI = Function.getCFIFor(Inst);
76       if (Changed.count(CFI))
77         continue;
78       Changed.insert(CFI);
79 
80       switch (CFI->getOperation()) {
81       case MCCFIInstruction::OpRegister: {
82         const unsigned CFIReg2 = CFI->getRegister2();
83         const MCPhysReg Reg2 = *BC.MRI->getLLVMRegNum(CFIReg2, /*isEH=*/false);
84         if (AliasA.test(Reg2)) {
85           Function.setCFIFor(
86               Inst, MCCFIInstruction::createRegister(
87                         nullptr, CFI->getRegister(),
88                         BC.MRI->getDwarfRegNum(
89                             BC.MIB->getAliasSized(B, BC.MIB->getRegSize(Reg2)),
90                             false)));
91         } else if (AliasB.test(Reg2)) {
92           Function.setCFIFor(
93               Inst, MCCFIInstruction::createRegister(
94                         nullptr, CFI->getRegister(),
95                         BC.MRI->getDwarfRegNum(
96                             BC.MIB->getAliasSized(A, BC.MIB->getRegSize(Reg2)),
97                             false)));
98         }
99       }
100       LLVM_FALLTHROUGH;
101       case MCCFIInstruction::OpUndefined:
102       case MCCFIInstruction::OpDefCfa:
103       case MCCFIInstruction::OpOffset:
104       case MCCFIInstruction::OpRestore:
105       case MCCFIInstruction::OpSameValue:
106       case MCCFIInstruction::OpDefCfaRegister:
107       case MCCFIInstruction::OpRelOffset:
108       case MCCFIInstruction::OpEscape: {
109         unsigned CFIReg;
110         if (CFI->getOperation() != MCCFIInstruction::OpEscape) {
111           CFIReg = CFI->getRegister();
112         } else {
113           Optional<uint8_t> Reg =
114               readDWARFExpressionTargetReg(CFI->getValues());
115           // Handle DW_CFA_def_cfa_expression
116           if (!Reg)
117             break;
118           CFIReg = *Reg;
119         }
120         const MCPhysReg Reg = *BC.MRI->getLLVMRegNum(CFIReg, /*isEH=*/false);
121         if (AliasA.test(Reg)) {
122           Function.mutateCFIRegisterFor(
123               Inst,
124               BC.MRI->getDwarfRegNum(
125                   BC.MIB->getAliasSized(B, BC.MIB->getRegSize(Reg)), false));
126         } else if (AliasB.test(Reg)) {
127           Function.mutateCFIRegisterFor(
128               Inst,
129               BC.MRI->getDwarfRegNum(
130                   BC.MIB->getAliasSized(A, BC.MIB->getRegSize(Reg)), false));
131         }
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.find_first(); J != -1;
228        J = ClassicRegs.find_next(J)) {
229     if (RegScore[J] <= 0)
230       continue;
231     Bail = false;
232     if (RegScore[J] < LowScoreClassic)
233       LowScoreClassic = RegScore[J];
234   }
235   if (Bail)
236     return;
237   BitVector Extended = ClassicRegs;
238   Extended.flip();
239   Extended &= GPRegs;
240   Bail = true;
241   int64_t HighScoreExtended = 0;
242   for (int J = Extended.find_first(); J != -1; J = Extended.find_next(J)) {
243     if (RegScore[J] <= 0)
244       continue;
245     Bail = false;
246     if (RegScore[J] > HighScoreExtended)
247       HighScoreExtended = RegScore[J];
248   }
249   // Also bail early if there is no profitable substitution even if we assume
250   // all registers can be exchanged
251   if (Bail || (LowScoreClassic << 1) >= HighScoreExtended)
252     return;
253 
254   // -- expensive pass -- determine all regs alive during func start
255   DataflowInfoManager Info(Function, RA.get(), nullptr);
256   BitVector AliveAtStart = *Info.getLivenessAnalysis().getStateAt(
257       ProgramPoint::getFirstPointAt(*Function.begin()));
258   for (BinaryBasicBlock &BB : Function) {
259     if (BB.pred_size() == 0)
260       AliveAtStart |= *Info.getLivenessAnalysis().getStateAt(
261           ProgramPoint::getFirstPointAt(BB));
262   }
263   // Mark frame pointer alive because of CFI
264   AliveAtStart |= BC.MIB->getAliases(BC.MIB->getFramePointer(), false);
265   // Never touch return registers
266   BC.MIB->getDefaultLiveOut(AliveAtStart);
267 
268   // Try swapping more profitable options first
269   auto Begin = RankedRegs.begin();
270   auto End = std::prev(RankedRegs.end());
271   while (Begin != End) {
272     MCPhysReg ClassicReg = *End;
273     if (!ClassicRegs[ClassicReg] || RegScore[ClassicReg] <= 0) {
274       --End;
275       continue;
276     }
277 
278     MCPhysReg ExtReg = *Begin;
279     if (!Extended[ExtReg] || RegScore[ExtReg] <= 0) {
280       ++Begin;
281       continue;
282     }
283 
284     if (RegScore[ClassicReg] << 1 >= RegScore[ExtReg]) {
285       LLVM_DEBUG(dbgs() << " Ending at " << BC.MRI->getName(ClassicReg)
286                         << " with " << BC.MRI->getName(ExtReg)
287                         << " because exchange is not profitable\n");
288       break;
289     }
290 
291     BitVector AnyAliasAlive = AliveAtStart;
292     AnyAliasAlive &= BC.MIB->getAliases(ClassicReg);
293     if (AnyAliasAlive.any()) {
294       LLVM_DEBUG(dbgs() << " Bailed on " << BC.MRI->getName(ClassicReg)
295                         << " with " << BC.MRI->getName(ExtReg)
296                         << " because classic reg is alive\n");
297       --End;
298       continue;
299     }
300     AnyAliasAlive = AliveAtStart;
301     AnyAliasAlive &= BC.MIB->getAliases(ExtReg);
302     if (AnyAliasAlive.any()) {
303       LLVM_DEBUG(dbgs() << " Bailed on " << BC.MRI->getName(ClassicReg)
304                         << " with " << BC.MRI->getName(ExtReg)
305                         << " because extended reg is alive\n");
306       ++Begin;
307       continue;
308     }
309 
310     // Opportunity detected. Swap.
311     LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(ClassicReg)
312                       << " with " << BC.MRI->getName(ExtReg) << "\n\n");
313     swap(Function, ClassicReg, ExtReg);
314     FuncsChanged.insert(&Function);
315     ++Begin;
316     if (Begin == End)
317       break;
318     --End;
319   }
320 }
321 
322 bool RegReAssign::conservativePassOverFunction(BinaryFunction &Function) {
323   BinaryContext &BC = Function.getBinaryContext();
324   rankRegisters(Function);
325 
326   // Try swapping R12, R13, R14 or R15 with RBX (we work with all callee-saved
327   // regs except RBP)
328   MCPhysReg Candidate = 0;
329   for (int J = ExtendedCSR.find_first(); J != -1;
330        J = ExtendedCSR.find_next(J)) {
331     if (RegScore[J] > RegScore[Candidate])
332       Candidate = J;
333   }
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 
351   if (!RBX)
352     return false;
353 
354   LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(RBX) << " with "
355                     << BC.MRI->getName(Candidate) << "\n\n");
356   swap(Function, RBX, Candidate);
357   FuncsChanged.insert(&Function);
358   return true;
359 }
360 
361 void RegReAssign::setupAggressivePass(BinaryContext &BC,
362                                      std::map<uint64_t, BinaryFunction> &BFs) {
363   setupConservativePass(BC, BFs);
364   CG.reset(new BinaryFunctionCallGraph(buildCallGraph(BC)));
365   RA.reset(new RegAnalysis(BC, &BFs, &*CG));
366 
367   GPRegs = BitVector(BC.MRI->getNumRegs(), false);
368   BC.MIB->getGPRegs(GPRegs);
369 }
370 
371 void RegReAssign::setupConservativePass(
372     BinaryContext &BC, std::map<uint64_t, BinaryFunction> &BFs) {
373   // Set up constant bitvectors used throughout this analysis
374   ClassicRegs = BitVector(BC.MRI->getNumRegs(), false);
375   CalleeSaved = BitVector(BC.MRI->getNumRegs(), false);
376   ClassicCSR = BitVector(BC.MRI->getNumRegs(), false);
377   ExtendedCSR = BitVector(BC.MRI->getNumRegs(), false);
378   // Never consider the frame pointer
379   BC.MIB->getClassicGPRegs(ClassicRegs);
380   ClassicRegs.flip();
381   ClassicRegs |= BC.MIB->getAliases(BC.MIB->getFramePointer(), false);
382   ClassicRegs.flip();
383   BC.MIB->getCalleeSavedRegs(CalleeSaved);
384   ClassicCSR |= ClassicRegs;
385   ClassicCSR &= CalleeSaved;
386   BC.MIB->getClassicGPRegs(ClassicRegs);
387   ExtendedCSR |= ClassicRegs;
388   ExtendedCSR.flip();
389   ExtendedCSR &= CalleeSaved;
390 
391   LLVM_DEBUG({
392     RegStatePrinter P(BC);
393     dbgs() << "Starting register reassignment\nClassicRegs: ";
394     P.print(dbgs(), ClassicRegs);
395     dbgs() << "\nCalleeSaved: ";
396     P.print(dbgs(), CalleeSaved);
397     dbgs() << "\nClassicCSR: ";
398     P.print(dbgs(), ClassicCSR);
399     dbgs() << "\nExtendedCSR: ";
400     P.print(dbgs(), ExtendedCSR);
401     dbgs() << "\n";
402   });
403 }
404 
405 void RegReAssign::runOnFunctions(BinaryContext &BC) {
406   RegScore = std::vector<int64_t>(BC.MRI->getNumRegs(), 0);
407   RankedRegs = std::vector<size_t>(BC.MRI->getNumRegs(), 0);
408 
409   if (opts::AggressiveReAssign)
410     setupAggressivePass(BC, BC.getBinaryFunctions());
411   else
412     setupConservativePass(BC, BC.getBinaryFunctions());
413 
414   for (auto &I : BC.getBinaryFunctions()) {
415     BinaryFunction &Function = I.second;
416 
417     if (!Function.isSimple() || Function.isIgnored())
418       continue;
419 
420     LLVM_DEBUG(dbgs() << "====================================\n");
421     LLVM_DEBUG(dbgs() << " - " << Function.getPrintName() << "\n");
422     if (!conservativePassOverFunction(Function) && opts::AggressiveReAssign) {
423       aggressivePassOverFunction(Function);
424       LLVM_DEBUG({
425         if (FuncsChanged.count(&Function)) {
426           dbgs() << "Aggressive pass successful on " << Function.getPrintName()
427                  << "\n";
428         }
429       });
430     }
431   }
432 
433   if (FuncsChanged.empty()) {
434     outs() << "BOLT-INFO: Reg Reassignment Pass: no changes were made.\n";
435     return;
436   }
437   if (opts::UpdateDebugSections) {
438     outs() << "BOLT-WARNING: You used -reg-reassign and -update-debug-sections."
439            << " Some registers were changed but associated AT_LOCATION for "
440            << "impacted variables were NOT updated! This operation is "
441            << "currently unsupported by BOLT.\n";
442   }
443   outs() << "BOLT-INFO: Reg Reassignment Pass Stats:\n";
444   outs() << "\t   " << FuncsChanged.size() << " functions affected.\n";
445   outs() << "\t   " << StaticBytesSaved << " static bytes saved.\n";
446   outs() << "\t   " << DynBytesSaved << " dynamic bytes saved.\n";
447 }
448 
449 }
450 }
451