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/BinaryFunctionCallGraph.h"
15#include "bolt/Core/MCPlus.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
23using namespace llvm;
24
25namespace opts {
26extern cl::OptionCategory BoltOptCategory;
27extern cl::opt<bool> UpdateDebugSections;
28
29static 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
36namespace llvm {
37namespace bolt {
38
39void RegReAssign::swap(BinaryFunction &Function, MCPhysReg A, MCPhysReg B) {
40 BinaryContext &BC = Function.getBinaryContext();
41 const BitVector &AliasA = BC.MIB->getAliases(Reg: A, OnlySmaller: false);
42 const BitVector &AliasB = BC.MIB->getAliases(Reg: B, OnlySmaller: 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(Idx: Reg)) {
53 Operand.setReg(BC.MIB->getAliasSized(Reg: B, Size: BC.MIB->getRegSize(Reg)));
54 --StaticBytesSaved;
55 DynBytesSaved -= BB.getKnownExecutionCount();
56 continue;
57 }
58 if (!AliasB.test(Idx: Reg))
59 continue;
60 Operand.setReg(BC.MIB->getAliasSized(Reg: A, Size: 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(Instr: Inst);
74 if (Changed.count(V: CFI))
75 continue;
76 Changed.insert(V: CFI);
77
78 switch (CFI->getOperation()) {
79 case MCCFIInstruction::OpRegister: {
80 const unsigned CFIReg2 = CFI->getRegister2();
81 const MCPhysReg Reg2 = *BC.MRI->getLLVMRegNum(RegNum: CFIReg2, /*isEH=*/false);
82 if (AliasA.test(Idx: Reg2)) {
83 Function.setCFIFor(
84 Instr: Inst, CFIInst: MCCFIInstruction::createRegister(
85 L: nullptr, Register1: CFI->getRegister(),
86 Register2: BC.MRI->getDwarfRegNum(
87 RegNum: BC.MIB->getAliasSized(Reg: B, Size: BC.MIB->getRegSize(Reg: Reg2)),
88 isEH: false)));
89 } else if (AliasB.test(Idx: Reg2)) {
90 Function.setCFIFor(
91 Instr: Inst, CFIInst: MCCFIInstruction::createRegister(
92 L: nullptr, Register1: CFI->getRegister(),
93 Register2: BC.MRI->getDwarfRegNum(
94 RegNum: BC.MIB->getAliasSized(Reg: A, Size: BC.MIB->getRegSize(Reg: Reg2)),
95 isEH: 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(ExprBytes: 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(RegNum: CFIReg, /*isEH=*/false);
119 if (AliasA.test(Idx: Reg))
120 Function.mutateCFIRegisterFor(
121 Instr: Inst,
122 NewReg: BC.MRI->getDwarfRegNum(
123 RegNum: BC.MIB->getAliasSized(Reg: B, Size: BC.MIB->getRegSize(Reg)), isEH: false));
124 else if (AliasB.test(Idx: Reg))
125 Function.mutateCFIRegisterFor(
126 Instr: Inst,
127 NewReg: BC.MRI->getDwarfRegNum(
128 RegNum: BC.MIB->getAliasSized(Reg: A, Size: BC.MIB->getRegSize(Reg)), isEH: false));
129 break;
130 }
131 default:
132 break;
133 }
134 }
135 }
136}
137
138void RegReAssign::rankRegisters(BinaryFunction &Function) {
139 BinaryContext &BC = Function.getBinaryContext();
140 std::fill(first: RegScore.begin(), last: RegScore.end(), value: 0);
141 std::fill(first: RankedRegs.begin(), last: RankedRegs.end(), value: 0);
142
143 auto countRegScore = [&](BinaryBasicBlock &BB) {
144 for (MCInst &Inst : BB) {
145 const bool CannotUseREX = BC.MIB->cannotUseREX(Inst);
146 const MCInstrDesc &Desc = BC.MII->get(Opcode: 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(Reg: ImplicitUse, OnlySmaller: 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(Reg: ImplicitDef, OnlySmaller: 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: I);
166 if (!Operand.isReg())
167 continue;
168
169 if (Desc.getOperandConstraint(OpNum: I, Constraint: MCOI::TIED_TO) != -1)
170 continue;
171
172 unsigned Reg = Operand.getReg();
173 size_t RegEC = BC.MIB->getAliases(Reg, OnlySmaller: false).find_first();
174 if (RegEC == 0)
175 continue;
176
177 // Disallow substituitions involving regs in instrs that cannot use REX
178 // The relationship of X86 registers is shown in the diagram. BL and BH
179 // do not have a direct alias relationship. However, if the BH register
180 // cannot be swapped, then the BX/EBX/RBX registers cannot be swapped as
181 // well, which means that BL register also cannot be swapped. Therefore,
182 // in the presence of BX/EBX/RBX registers, BL and BH have an alias
183 // relationship.
184 // ┌─────────────────┐
185 // │ RBX │
186 // ├─────┬───────────┤
187 // │ │ EBX │
188 // ├─────┴──┬────────┤
189 // │ │ BX │
190 // ├────────┼───┬────┤
191 // │ │BH │BL │
192 // └────────┴───┴────┘
193 if (CannotUseREX) {
194 RegScore[RegEC] =
195 std::numeric_limits<decltype(RegScore)::value_type>::min();
196 RegScore[BC.MIB->getAliasSized(Reg, Size: 1)] = RegScore[RegEC];
197 continue;
198 }
199
200 // Unsupported substitution, cannot swap BH with R* regs, bail
201 if (BC.MIB->isUpper8BitReg(Reg) && ClassicCSR.test(Idx: Reg)) {
202 RegScore[RegEC] =
203 std::numeric_limits<decltype(RegScore)::value_type>::min();
204 RegScore[BC.MIB->getAliasSized(Reg, Size: 1)] = RegScore[RegEC];
205 continue;
206 }
207
208 RegScore[RegEC] += BB.getKnownExecutionCount();
209 }
210 }
211 };
212 for (BinaryBasicBlock &BB : Function)
213 countRegScore(BB);
214
215 for (BinaryFunction *ChildFrag : Function.getFragments()) {
216 for (BinaryBasicBlock &BB : *ChildFrag)
217 countRegScore(BB);
218 }
219
220 std::iota(first: RankedRegs.begin(), last: RankedRegs.end(), value: 0); // 0, 1, 2, 3...
221 llvm::sort(C&: RankedRegs,
222 Comp: [&](size_t A, size_t B) { return RegScore[A] > RegScore[B]; });
223
224 LLVM_DEBUG({
225 for (size_t Reg : RankedRegs) {
226 if (RegScore[Reg] == 0)
227 continue;
228 dbgs() << Reg << " ";
229 if (RegScore[Reg] > 0)
230 dbgs() << BC.MRI->getName(Reg) << ": " << RegScore[Reg] << "\n";
231 else
232 dbgs() << BC.MRI->getName(Reg) << ": (blacklisted)\n";
233 }
234 });
235}
236
237void RegReAssign::aggressivePassOverFunction(BinaryFunction &Function) {
238 BinaryContext &BC = Function.getBinaryContext();
239 rankRegisters(Function);
240
241 // If there is a situation where function:
242 // A() -> A.cold()
243 // A.localalias() -> A.cold()
244 // simply swapping these two calls can cause issues.
245 for (BinaryFunction *ChildFrag : Function.getFragments()) {
246 if (ChildFrag->getParentFragments()->size() > 1)
247 return;
248 if (ChildFrag->empty())
249 return;
250 }
251
252 // Bail early if our registers are all black listed, before running expensive
253 // analysis passes
254 bool Bail = true;
255 int64_t LowScoreClassic = std::numeric_limits<int64_t>::max();
256 for (int J : ClassicRegs.set_bits()) {
257 if (RegScore[J] <= 0)
258 continue;
259 Bail = false;
260 if (RegScore[J] < LowScoreClassic)
261 LowScoreClassic = RegScore[J];
262 }
263 if (Bail)
264 return;
265 BitVector Extended = ClassicRegs;
266 Extended.flip();
267 Extended &= GPRegs;
268 Bail = true;
269 int64_t HighScoreExtended = 0;
270 for (int J : Extended.set_bits()) {
271 if (RegScore[J] <= 0)
272 continue;
273 Bail = false;
274 if (RegScore[J] > HighScoreExtended)
275 HighScoreExtended = RegScore[J];
276 }
277 // Also bail early if there is no profitable substitution even if we assume
278 // all registers can be exchanged
279 if (Bail || (LowScoreClassic << 1) >= HighScoreExtended)
280 return;
281
282 // -- expensive pass -- determine all regs alive during func start
283 DataflowInfoManager Info(Function, RA.get(), nullptr);
284 BitVector AliveAtStart = *Info.getLivenessAnalysis().getStateAt(
285 Point: ProgramPoint::getFirstPointAt(BB&: *Function.begin()));
286 for (BinaryBasicBlock &BB : Function)
287 if (BB.pred_size() == 0)
288 AliveAtStart |= *Info.getLivenessAnalysis().getStateAt(
289 Point: ProgramPoint::getFirstPointAt(BB));
290
291 // Mark frame pointer alive because of CFI
292 AliveAtStart |= BC.MIB->getAliases(Reg: BC.MIB->getFramePointer(), OnlySmaller: false);
293 // Never touch return registers
294 BC.MIB->getDefaultLiveOut(Regs&: AliveAtStart);
295
296 // Try swapping more profitable options first
297 auto Begin = RankedRegs.begin();
298 auto End = std::prev(x: RankedRegs.end());
299 while (Begin != End) {
300 MCPhysReg ClassicReg = *End;
301 if (!ClassicRegs[ClassicReg] || RegScore[ClassicReg] <= 0) {
302 --End;
303 continue;
304 }
305
306 MCPhysReg ExtReg = *Begin;
307 if (!Extended[ExtReg] || RegScore[ExtReg] <= 0) {
308 ++Begin;
309 continue;
310 }
311
312 if (RegScore[ClassicReg] << 1 >= RegScore[ExtReg]) {
313 LLVM_DEBUG(dbgs() << " Ending at " << BC.MRI->getName(ClassicReg)
314 << " with " << BC.MRI->getName(ExtReg)
315 << " because exchange is not profitable\n");
316 break;
317 }
318
319 BitVector AnyAliasAlive = AliveAtStart;
320 AnyAliasAlive &= BC.MIB->getAliases(Reg: ClassicReg);
321 if (AnyAliasAlive.any()) {
322 LLVM_DEBUG(dbgs() << " Bailed on " << BC.MRI->getName(ClassicReg)
323 << " with " << BC.MRI->getName(ExtReg)
324 << " because classic reg is alive\n");
325 --End;
326 continue;
327 }
328 AnyAliasAlive = AliveAtStart;
329 AnyAliasAlive &= BC.MIB->getAliases(Reg: ExtReg);
330 if (AnyAliasAlive.any()) {
331 LLVM_DEBUG(dbgs() << " Bailed on " << BC.MRI->getName(ClassicReg)
332 << " with " << BC.MRI->getName(ExtReg)
333 << " because extended reg is alive\n");
334 ++Begin;
335 continue;
336 }
337
338 // Opportunity detected. Swap.
339 LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(ClassicReg)
340 << " with " << BC.MRI->getName(ExtReg) << "\n\n");
341 swap(Function, A: ClassicReg, B: ExtReg);
342 FuncsChanged.insert(V: &Function);
343 for (BinaryFunction *ChildFrag : Function.getFragments()) {
344 swap(Function&: *ChildFrag, A: ClassicReg, B: ExtReg);
345 FuncsChanged.insert(V: ChildFrag);
346 }
347 ++Begin;
348 if (Begin == End)
349 break;
350 --End;
351 }
352}
353
354bool RegReAssign::conservativePassOverFunction(BinaryFunction &Function) {
355 BinaryContext &BC = Function.getBinaryContext();
356 rankRegisters(Function);
357
358 for (BinaryFunction *ChildFrag : Function.getFragments()) {
359 if (ChildFrag->getParentFragments()->size() > 1)
360 return false;
361 if (ChildFrag->empty())
362 return false;
363 }
364
365 // Try swapping R12, R13, R14 or R15 with RBX (we work with all callee-saved
366 // regs except RBP)
367 MCPhysReg Candidate = 0;
368 for (int J : ExtendedCSR.set_bits())
369 if (RegScore[J] > RegScore[Candidate])
370 Candidate = J;
371
372 if (!Candidate || RegScore[Candidate] < 0)
373 return false;
374
375 // Check if our classic callee-saved reg (RBX is the only one) has lower
376 // score / utilization rate
377 MCPhysReg RBX = 0;
378 for (int I : ClassicCSR.set_bits()) {
379 int64_t ScoreRBX = RegScore[I];
380 if (ScoreRBX <= 0)
381 continue;
382
383 if (RegScore[Candidate] > (ScoreRBX + 10))
384 RBX = I;
385 }
386
387 if (!RBX)
388 return false;
389
390 // The high 8 bits of the register will never be swapped. To prevent the high
391 // 8 bits from being swapped incorrectly, we should switched to swapping the
392 // low 8 bits of the register instead.
393 if (BC.MIB->isUpper8BitReg(Reg: RBX)) {
394 RBX = BC.MIB->getAliasSized(Reg: RBX, Size: 1);
395 if (RegScore[RBX] < 0 || RegScore[RBX] > RegScore[Candidate])
396 return false;
397 }
398
399 LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(RBX) << " with "
400 << BC.MRI->getName(Candidate) << "\n\n");
401 (void)BC;
402 swap(Function, A: RBX, B: Candidate);
403 FuncsChanged.insert(V: &Function);
404 for (BinaryFunction *ChildFrag : Function.getFragments()) {
405 swap(Function&: *ChildFrag, A: RBX, B: Candidate);
406 FuncsChanged.insert(V: ChildFrag);
407 }
408 return true;
409}
410
411void RegReAssign::setupAggressivePass(BinaryContext &BC,
412 std::map<uint64_t, BinaryFunction> &BFs) {
413 setupConservativePass(BC, BFs);
414 CG.reset(p: new BinaryFunctionCallGraph(buildCallGraph(BC)));
415 RA.reset(p: new RegAnalysis(BC, &BFs, &*CG));
416
417 GPRegs = BitVector(BC.MRI->getNumRegs(), false);
418 BC.MIB->getGPRegs(Regs&: GPRegs);
419}
420
421void RegReAssign::setupConservativePass(
422 BinaryContext &BC, std::map<uint64_t, BinaryFunction> &BFs) {
423 // Set up constant bitvectors used throughout this analysis
424 ClassicRegs = BitVector(BC.MRI->getNumRegs(), false);
425 CalleeSaved = BitVector(BC.MRI->getNumRegs(), false);
426 ClassicCSR = BitVector(BC.MRI->getNumRegs(), false);
427 ExtendedCSR = BitVector(BC.MRI->getNumRegs(), false);
428 // Never consider the frame pointer
429 BC.MIB->getClassicGPRegs(Regs&: ClassicRegs);
430 ClassicRegs.flip();
431 ClassicRegs |= BC.MIB->getAliases(Reg: BC.MIB->getFramePointer(), OnlySmaller: false);
432 ClassicRegs.flip();
433 BC.MIB->getCalleeSavedRegs(Regs&: CalleeSaved);
434 ClassicCSR |= ClassicRegs;
435 ClassicCSR &= CalleeSaved;
436 BC.MIB->getClassicGPRegs(Regs&: ClassicRegs);
437 ExtendedCSR |= ClassicRegs;
438 ExtendedCSR.flip();
439 ExtendedCSR &= CalleeSaved;
440
441 LLVM_DEBUG({
442 RegStatePrinter P(BC);
443 dbgs() << "Starting register reassignment\nClassicRegs: ";
444 P.print(dbgs(), ClassicRegs);
445 dbgs() << "\nCalleeSaved: ";
446 P.print(dbgs(), CalleeSaved);
447 dbgs() << "\nClassicCSR: ";
448 P.print(dbgs(), ClassicCSR);
449 dbgs() << "\nExtendedCSR: ";
450 P.print(dbgs(), ExtendedCSR);
451 dbgs() << "\n";
452 });
453}
454
455Error RegReAssign::runOnFunctions(BinaryContext &BC) {
456 RegScore = std::vector<int64_t>(BC.MRI->getNumRegs(), 0);
457 RankedRegs = std::vector<size_t>(BC.MRI->getNumRegs(), 0);
458
459 if (opts::AggressiveReAssign)
460 setupAggressivePass(BC, BFs&: BC.getBinaryFunctions());
461 else
462 setupConservativePass(BC, BFs&: BC.getBinaryFunctions());
463
464 for (auto &I : BC.getBinaryFunctions()) {
465 BinaryFunction &Function = I.second;
466
467 if (!Function.isSimple() || Function.isIgnored() || Function.isFragment())
468 continue;
469
470 LLVM_DEBUG(dbgs() << "====================================\n");
471 LLVM_DEBUG(dbgs() << " - " << Function.getPrintName() << "\n");
472 if (!conservativePassOverFunction(Function) && opts::AggressiveReAssign) {
473 aggressivePassOverFunction(Function);
474 LLVM_DEBUG({
475 if (FuncsChanged.count(&Function))
476 dbgs() << "Aggressive pass successful on " << Function.getPrintName()
477 << "\n";
478 });
479 }
480 }
481
482 if (FuncsChanged.empty()) {
483 BC.outs() << "BOLT-INFO: Reg Reassignment Pass: no changes were made.\n";
484 return Error::success();
485 }
486 if (opts::UpdateDebugSections)
487 BC.outs()
488 << "BOLT-WARNING: You used -reg-reassign and -update-debug-sections."
489 << " Some registers were changed but associated AT_LOCATION for "
490 << "impacted variables were NOT updated! This operation is "
491 << "currently unsupported by BOLT.\n";
492 BC.outs() << "BOLT-INFO: Reg Reassignment Pass Stats:\n";
493 BC.outs() << "\t " << FuncsChanged.size() << " functions affected.\n";
494 BC.outs() << "\t " << StaticBytesSaved << " static bytes saved.\n";
495 BC.outs() << "\t " << DynBytesSaved << " dynamic bytes saved.\n";
496 return Error::success();
497}
498
499} // namespace bolt
500} // namespace llvm
501

source code of bolt/lib/Passes/RegReAssign.cpp