[BOLT] BL/BH are considered aliases in regreassign

[hzq]

Summary

The relationship of X86 registers is shown in the diagram. BL and BH do
not have a direct alias relationship. However, if the BH register cannot be
swapped, then the BX/EBX/RBX registers cannot be swapped as well, which
means that BL register also cannot be swapped. Therefore, in the presence
of BX/EBX/RBX registers, BL and BH have an alias relationship.

┌────────────────┐
│  RBX           │
├────┬───────────┤
│    │ EBX       │
├────┴──┬────────┤
│       │   BX   │
├───────┼───┬────┤
│       │BH │BL  │
└───────┴───┴────┘

[hzq]

Update.

[hzq]

Updating Context and Test Cases.

[rafauler]

bolt/lib/Passes/RegReAssign.cpp

149

move this comment next to the first call to BC.MIB->getAliasSized(Reg, 1), otherwise it is a bit confusing what it is referring to

390

I'm a bit confused, maybe you mean "To prevent the high" instead of "To prevent the low" here?

bolt/test/X86/reg-reassign-no-swap-bl.s

10 ↗

(On Diff #551818)

Drop --debug-only as it is not being used.

11 ↗

(On Diff #551818)

If this test is running the output of BOLT, then it should go to bolt/test/runtime/X86

[rafauler]

Thanks! LGTM

[hzq]

@rafauler, I'm sorry I didn't run the complete test cases earlier. Could you please help review it again?

bolt/lib/Passes/RegReAssign.cpp

390

Yes, you are right, thanks.

[rafauler]

I'm not sure why runtime/X86/reg-reassign-swap-cold.s is failing. I can't repro the failure. I would suggest submitting your changes on another revision using arc diff --draft, so it is not published, but you can still run the tests to see if they pass, and they debug it from there -- perhaps by removing modifications you did to see if the test pass, getting hints on what is wrong.

[hzq]

In D155098#4615583, @rafauler wrote:

I'm not sure why runtime/X86/reg-reassign-swap-cold.s is failing. I can't repro the failure. I would suggest submitting your changes on another revision using arc diff --draft, so it is not published, but you can still run the tests to see if they pass, and they debug it from there -- perhaps by removing modifications you did to see if the test pass, getting hints on what is wrong.

The current modifications appear to have resulted in all test cases passing.

[rafauler]

In D155098#4617428, @hzq wrote:

In D155098#4615583, @rafauler wrote:

I'm not sure why runtime/X86/reg-reassign-swap-cold.s is failing. I can't repro the failure. I would suggest submitting your changes on another revision using arc diff --draft, so it is not published, but you can still run the tests to see if they pass, and they debug it from there -- perhaps by removing modifications you did to see if the test pass, getting hints on what is wrong.

The current modifications appear to have resulted in all test cases passing.

LGTM

bolt/lib/Passes/RegReAssign.cpp

void RegReAssign::rankRegisters(BinaryFunction &Function) {
   std::fill(RankedRegs.begin(), RankedRegs.end(), 0);
 
   auto countRegScore = [&](BinaryBasicBlock &BB) {
     for (MCInst &Inst : BB) {
       const bool CannotUseREX = BC.MIB->cannotUseREX(Inst);
       const MCInstrDesc &Desc = BC.MII->get(Inst.getOpcode());
 
       // Disallow substituitions involving regs in implicit uses lists
       for (MCPhysReg ImplicitUse : Desc.implicit_uses()) {
         const size_t RegEC =
             BC.MIB->getAliases(ImplicitUse, false).find_first();
         RegScore[RegEC] =
             std::numeric_limits<decltype(RegScore)::value_type>::min();
       }
 
       // Disallow substituitions involving regs in implicit defs lists
       for (MCPhysReg ImplicitDef : Desc.implicit_defs()) {
for (MCInst &Inst : BB) {
           continue;
 
         unsigned Reg = Operand.getReg();
         size_t RegEC = BC.MIB->getAliases(Reg, false).find_first();
         if (RegEC == 0)
           continue;
 
         // Disallow substituitions involving regs in instrs that cannot use REX
+        // The relationship of X86 registers is shown in the diagram. BL and BH
+        // do not have a direct alias relationship. However, if the BH register
+        // cannot be swapped, then the BX/EBX/RBX registers cannot be swapped as
+        // well, which means that BL register also cannot be swapped. Therefore,
+        // in the presence of BX/EBX/RBX registers, BL and BH have an alias
+        // relationship.
+        // ┌─────────────────┐
+        // │  RBX            │
+        // ├─────┬───────────┤
+        // │     │  EBX      │
+        // ├─────┴──┬────────┤
+        // │        │   BX   │
+        // ├────────┼───┬────┤
+        // │        │BH │BL  │
+        // └────────┴───┴────┘
         if (CannotUseREX) {
           RegScore[RegEC] =
               std::numeric_limits<decltype(RegScore)::value_type>::min();
+          RegScore[BC.MIB->getAliasSized(Reg, 1)] = RegScore[RegEC];
           continue;
         }
 
         // Unsupported substitution, cannot swap BH with R* regs, bail
         if (BC.MIB->isUpper8BitReg(Reg) && ClassicCSR.test(Reg)) {
           RegScore[RegEC] =
               std::numeric_limits<decltype(RegScore)::value_type>::min();
+          RegScore[BC.MIB->getAliasSized(Reg, 1)] = RegScore[RegEC];
           continue;
         }
 
         RegScore[RegEC] += BB.getKnownExecutionCount();
       }
     }
   };
   for (BinaryBasicBlock &BB : Function)
for (int I : ClassicCSR.set_bits()) {
 
     if (RegScore[Candidate] > (ScoreRBX + 10))
       RBX = I;
   }
 
   if (!RBX)
     return false;
 
+  // The high 8 bits of the register will never be swapped. To prevent the high
+  // 8 bits from being swapped incorrectly, we should switched to swapping the
+  // low 8 bits of the register instead.
+  if (BC.MIB->isUpper8BitReg(RBX)) {
+    RBX = BC.MIB->getAliasSized(RBX, 1);
+    if (RegScore[RBX] < 0 || RegScore[RBX] > RegScore[Candidate])
+      return false;
+  }
+
   LLVM_DEBUG(dbgs() << "\n ** Swapping " << BC.MRI->getName(RBX) << " with "
                     << BC.MRI->getName(Candidate) << "\n\n");
   (void)BC;
   swap(Function, RBX, Candidate);
   FuncsChanged.insert(&Function);
   for (BinaryFunction *ChildFrag : Function.getFragments()) {
     swap(*ChildFrag, RBX, Candidate);
     FuncsChanged.insert(ChildFrag);

bolt/test/runtime/X86/reg-reassign-no-swap-bl.s

+# This test case is used to reproduce an issue found in the mongod database.
+# In function rankRegisters, if there is a BH Reg in the basic block, then the BL Reg
+# also cannot be swap.
+
+# REQUIRES: system-linux
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
+# RUN: link_fdata %s %t.o %t.fdata
+# RUN: llvm-strip --strip-unneeded %t.o
+# RUN: %clang -no-pie %t.o -o %t.exe -Wl,-q
+# RUN: llvm-bolt %t.exe -o %t.out -data=%t.fdata --reg-reassign | FileCheck %s
+# RUN: %t.out
+
+# CHECK: Reg Reassignment Pass: no changes were made
+  .text
+  .globl  main
+  .globl  main.cold
+  .p2align  4, 0x90
+  .type  main,@function
+  .type  main.cold,@function
+main.cold:
+bb1:
+  mov    $0x2,  %bh
+bb2:
+  jmp    bb5
+main:                                   # @main
+  .cfi_startproc
+# %bb.0:                                # %entry
+  pushq  %rax
+  pushq   %r12
+  pushq   %rbx
+  .cfi_def_cfa_offset 16
+  mov     $0x1,   %r12
+  shr     $0x14,  %r12
+  add     $0x14,  %r12
+  mov     $0x11,  %rbx
+  mov    $0x1,  %bh
+  mov    $0x1,  %bl
+bb3:
+  add    $0x1,   %r12
+bb4:
+  jmp    bb1
+bb5:
+  cmp     $0x201,  %rbx
+  jne     0x0
+bb6:
+  xorl    %eax, %eax
+  popq    %rcx
+  popq    %rbx
+  popq    %r12
+  .cfi_def_cfa_offset 8
+  retq
+# FDATA: 1 main.cold #bb2# 1 main 0 0 100
+# FDATA: 1 main #bb3# 1 main #bb4# 0 100
+# FDATA: 1 main #bb4# 1 main.cold 0 0 100
+
+.Lfunc_end0:
+  .size  main, .Lfunc_end0-main
+  .cfi_endproc