[BOLT][Linux] Support ORC for alternative instructions (#96709)

Alternative instruction sequences in the Linux kernel can modify the
stack and thus they need their own ORC unwind entries. Since there's
only one ORC table, it has to be "shared" among multiple instruction
sequences. The kernel achieves this by putting a restriction on
instruction boundaries. If ORC state changes at a given IP, only one of
the alternative sequences can have an instruction starting/ending at
this IP. Then, developers can insert NOPs to guarantee the above
requirement is met.

The most common use of ORC with alternatives is "pushf; pop %rax"
sequence used for paravirtualization. Note that newer kernel versions
no longer use .parainstructions; instead, they utilize alternatives for
the same purpose.

Before we implement a better support for alternatives, we can safely
skip ORC entries associated with them.

Fixes #87052.

4 files changed, 88 insertions, 8 deletions

diff --git a/bolt/include/bolt/Core/BinaryFunction.h b/bolt/include/bolt/Core/BinaryFunction.h
index 3c64158..1048e50 100644
--- a/bolt/include/bolt/Core/BinaryFunction.h
+++ b/bolt/include/bolt/Core/BinaryFunction.h
@@ -930,6 +930,10 @@ public:
     return const_cast<BinaryFunction *>(this)->getInstructionAtOffset(Offset);
   }
 
+  /// When the function is in disassembled state, return an instruction that
+  /// contains the \p Offset.
+  MCInst *getInstructionContainingOffset(uint64_t Offset);
+
   std::optional<MCInst> disassembleInstructionAtOffset(uint64_t Offset) const;
 
   /// Return offset for the first instruction. If there is data at the
diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp
index 5d33aa6..21c4995 100644
--- a/bolt/lib/Core/BinaryFunction.cpp
+++ b/bolt/lib/Core/BinaryFunction.cpp
@@ -4472,6 +4472,18 @@ MCInst *BinaryFunction::getInstructionAtOffset(uint64_t Offset) {
   }
 }
 
+MCInst *BinaryFunction::getInstructionContainingOffset(uint64_t Offset) {
+  assert(CurrentState == State::Disassembled && "Wrong function state");
+
+  if (Offset > Size)
+    return nullptr;
+
+  auto II = Instructions.upper_bound(Offset);
+  assert(II != Instructions.begin() && "First instruction not at offset 0");
+  --II;
+  return &II->second;
+}
+
 void BinaryFunction::printLoopInfo(raw_ostream &OS) const {
   if (!opts::shouldPrint(*this))
     return;
diff --git a/bolt/lib/Rewrite/LinuxKernelRewriter.cpp b/bolt/lib/Rewrite/LinuxKernelRewriter.cpp
index aa18e79..03b414b 100644
--- a/bolt/lib/Rewrite/LinuxKernelRewriter.cpp
+++ b/bolt/lib/Rewrite/LinuxKernelRewriter.cpp
@@ -295,9 +295,6 @@ public:
     if (Error E = processSMPLocks())
       return E;
 
-    if (Error E = readORCTables())
-      return E;
-
     if (Error E = readStaticCalls())
       return E;
 
@@ -313,6 +310,11 @@ public:
     if (Error E = readAltInstructions())
       return E;
 
+    // Some ORC entries could be linked to alternative instruction
+    // sequences. Hence, we read ORC after .altinstructions.
+    if (Error E = readORCTables())
+      return E;
+
     if (Error E = readPCIFixupTable())
       return E;
 
@@ -563,11 +565,28 @@ Error LinuxKernelRewriter::readORCTables() {
     if (!BF->hasInstructions())
       continue;
 
-    MCInst *Inst = BF->getInstructionAtOffset(IP - BF->getAddress());
-    if (!Inst)
+    const uint64_t Offset = IP - BF->getAddress();
+    MCInst *Inst = BF->getInstructionAtOffset(Offset);
+    if (!Inst) {
+      // Check if there is an alternative instruction(s) at this IP. Multiple
+      // alternative instructions can take a place of a single original
+      // instruction and each alternative can have a separate ORC entry.
+      // Since ORC table is shared between all alternative sequences, there's
+      // a requirement that only one (out of many) sequences can have an
+      // instruction from the ORC table to avoid ambiguities/conflicts.
+      //
+      // For now, we have limited support for alternatives. I.e. we still print
+      // functions with them, but will not change the code in the output binary.
+      // As such, we can ignore alternative ORC entries. They will be preserved
+      // in the binary, but will not get printed in the instruction stream.
+      Inst = BF->getInstructionContainingOffset(Offset);
+      if (Inst || BC.MIB->hasAnnotation(*Inst, "AltInst"))
+        continue;
+
       return createStringError(
           errc::executable_format_error,
           "no instruction at address 0x%" PRIx64 " in .orc_unwind_ip", IP);
+    }
 
     // Some addresses will have two entries associated with them. The first
     // one being a "weak" section terminator. Since we ignore the terminator,
@@ -1440,7 +1459,7 @@ Error LinuxKernelRewriter::tryReadAltInstructions(uint32_t AltInstFeatureSize,
       AltBF->setIgnored();
     }
 
-    if (!BF || !BC.shouldEmit(*BF))
+    if (!BF || !BF->hasInstructions())
       continue;
 
     if (OrgInstAddress + OrgSize > BF->getAddress() + BF->getSize())
diff --git a/bolt/test/X86/linux-alt-instruction.s b/bolt/test/X86/linux-alt-instruction.s
index dc1b12a2..fe3abbf 100644
--- a/bolt/test/X86/linux-alt-instruction.s
+++ b/bolt/test/X86/linux-alt-instruction.s
@@ -38,7 +38,7 @@
 # RUN: llvm-bolt %t.exe --print-cfg -o %t.fs4.out | FileCheck %s
 
 # CHECK:      BOLT-INFO: Linux kernel binary detected
-# CHECK:      BOLT-INFO: parsed 2 alternative instruction entries
+# CHECK:      BOLT-INFO: parsed 3 alternative instruction entries
 
   .text
   .globl _start
@@ -50,10 +50,12 @@ _start:
 # CHECK:      rdtsc
 # CHECK-SAME: AltInst: 1
 # CHECK-SAME: AltInst2: 2
+# CHECK-SAME: AltInst3: 3
   nop
 # CHECK-NEXT: nop
 # CHECK-SAME: AltInst: 1
 # CHECK-SAME: AltInst2: 2
+# CHECK-SAME: AltInst3: 3
   nop
   nop
 .L1:
@@ -66,6 +68,9 @@ _start:
   rdtsc
 .A1:
   rdtscp
+.A2:
+  pushf
+  pop %rax
 .Ae:
 
 ## Alternative instruction info.
@@ -92,11 +97,51 @@ _start:
   .word 0x3b      # feature flags
 .endif
   .byte .L1 - .L0 # org size
-  .byte .Ae - .A1 # alt size
+  .byte .A2 - .A1 # alt size
 .ifdef PADLEN
   .byte 0
 .endif
 
+  .long .L0 - .   # org instruction
+  .long .A2 - .   # alt instruction
+.ifdef FEATURE_SIZE_4
+  .long 0x110     # feature flags
+.else
+  .word 0x110     # feature flags
+.endif
+  .byte .L1 - .L0 # org size
+  .byte .Ae - .A2 # alt size
+.ifdef PADLEN
+  .byte 0
+.endif
+
+## ORC unwind for "pushf; pop %rax" alternative sequence.
+  .section .orc_unwind,"a",@progbits
+  .align 4
+  .section .orc_unwind_ip,"a",@progbits
+  .align 4
+
+  .section .orc_unwind
+  .2byte 8
+  .2byte 0
+  .2byte 0x205
+  .section .orc_unwind_ip
+  .long _start - .
+
+  .section .orc_unwind
+  .2byte 16
+  .2byte 0
+  .2byte 0x205
+  .section .orc_unwind_ip
+  .long .L0 + 1 - .
+
+  .section .orc_unwind
+  .2byte 8
+  .2byte 0
+  .2byte 0x205
+  .section .orc_unwind_ip
+  .long .L0 + 2 - .
+
 ## Fake Linux Kernel sections.
   .section __ksymtab,"a",@progbits
   .section __ksymtab_gpl,"a",@progbits