[BOLT] Ignore functions accessing false positive jump tables

[nhuhuan]

Summary

Disassembly and branch target analysis are not decoupled, so any
analysis that depends on disassembly may not operate properly.

In specific, analyzeJumpTable uses instruction bounds check property.
A jump table was analyzed twice: (a) during disassembly, and (b) after
disassembly, so there are potentially some mismatched results.

In this update, functions that access JTs which fail the second check
will be marked as ignored.

Test Plan:

ninja check-bolt

[Amir]

Good findings, and the code looks good generally.
The summary lists three separate issues, can you please split up this diff so that each is addressed separately?

bolt/lib/Core/BinaryContext.cpp

623

Please add a context for this vector (e.g. "collect jump tables that failed analyzeJumpTable checks") and run clang-format on this commit.

704

[nhuhuan]

Split this diff into a few diffs.

[nhuhuan]

Add description for AbortedJTs

[nhuhuan]

Added the manual test back

[nhuhuan]

Rebase.

[Amir]

LGTM

[Amir]

Let's retitle as "[BOLT] Ignore functions accessing false positive jump tables"

[Amir]

bolt/lib/Core/BinaryContext.cpp

673

Sorry, let's not reland this diff.
We want to preserve this llvm_unreachable here to crash in cases we failed to recognize the jump table.

bolt/lib/Core/BinaryContext.cpp

bool BinaryContext::analyzeJumpTable(
 
   // It's a jump table if the number of real entries is more than 1, or there's
   // one real entry and "unreachable" targets. If there are only multiple
   // "unreachable" targets, then it's not a jump table.
   return NumRealEntries + HasUnreachable >= 2;
 }
 
 void BinaryContext::populateJumpTables() {
   LLVM_DEBUG(dbgs() << "DataPCRelocations: " << DataPCRelocations.size()
                     << '\n');
+
+  // Collect jump tables that pass the analyzeJumpTable's first check,
+  // but fail the analyzeJumpTable's second check
+  SmallVector<JumpTable *, 1> AbortedJTs;
   for (auto JTI = JumpTables.begin(), JTE = JumpTables.end(); JTI != JTE;
        ++JTI) {
     JumpTable *JT = JTI->second;
 
     bool NonSimpleParent = false;
     for (BinaryFunction *BF : JT->Parents)
       NonSimpleParent |= !BF->isSimple();
     if (NonSimpleParent)
       continue;
 
     uint64_t NextJTAddress = 0;
     auto NextJTI = std::next(JTI);
     if (NextJTI != JTE)
       NextJTAddress = NextJTI->second->getAddress();
 
     const bool Success =
         analyzeJumpTable(JT->getAddress(), JT->Type, *(JT->Parents[0]),
                          NextJTAddress, &JT->EntriesAsAddress);
+    // !Success means a false positive from earlier analysis run due to
+    // different context. A possible culprit is instruction bounds check.
+    // Previous run happens during disassembly. If the target function
+    // is not disassembled, the check will be skipped, leading to a false
+    // positive
+    //
+    // Solution: Ignore fragments accessing JT that fails the check
     if (!Success) {
       LLVM_DEBUG(ListSeparator LS;
                  dbgs() << "failed to analyze jump table in function ";
                  for (BinaryFunction *Frag
                       : JT->Parents) dbgs()
                  << LS << *Frag;
                  dbgs() << '\n';);
       JT->print(dbgs());
       if (NextJTI != JTE) {
         LLVM_DEBUG(ListSeparator LS;
                    dbgs() << "next jump table at 0x"
                           << Twine::utohexstr(NextJTI->second->getAddress())
                           << " belongs to function ";
                    for (BinaryFunction *Frag
                         : NextJTI->second->Parents) dbgs()
                    << LS << *Frag;
                    dbgs() << "\n";);
         NextJTI->second->print(dbgs());
       }
-      llvm_unreachable("jump table heuristic failure");
+      AbortedJTs.push_back(JT);
+      continue;
     }
     for (BinaryFunction *Frag : JT->Parents) {
       for (uint64_t EntryAddress : JT->EntriesAsAddress)
         // if target is builtin_unreachable
         if (EntryAddress == Frag->getAddress() + Frag->getSize()) {
           Frag->IgnoredBranches.emplace_back(EntryAddress - Frag->getAddress(),
                                              Frag->getSize());
         } else if (EntryAddress >= Frag->getAddress() &&
for (auto JTI = JumpTables.begin(), JTE = JumpTables.end(); JTI != JTE;
     }
 
     // Mark to skip the function and all its fragments.
     for (BinaryFunction *Frag : JT->Parents)
       if (Frag->hasIndirectTargetToSplitFragment())
         addFragmentsToSkip(Frag);
   }
 
+  // Ignore fragments accessing JT that fails analyzeJumpTable check
+  for (JumpTable *JT : AbortedJTs) {
+    for (BinaryFunction *Frag : JT->Parents) {
+      Frag->setIgnored();
+      Frag->JumpTables.erase(Frag->JumpTables.find(JT->getAddress()));
+    }
+    JumpTables.erase(JumpTables.find(JT->getAddress()));
+  }
+
   if (opts::StrictMode && DataPCRelocations.size()) {
     LLVM_DEBUG({
       dbgs() << DataPCRelocations.size()
              << " unclaimed PC-relative relocations left in data:\n";
       for (uint64_t Reloc : DataPCRelocations)
         dbgs() << Twine::utohexstr(Reloc) << '\n';
     });
     assert(0 && "unclaimed PC-relative relocations left in data\n");

bolt/test/X86/fake_jump_table.s

+# Currently disassembly is not decoupled from branch target analysis.
+# This causes a few checks related to availability of target insn to
+# fail for stripped binaries:
+#   (a) analyzeJumpTable
+#   (b) postProcessEntryPoints
+# This test checks if BOLT can safely support instruction bounds check
+# for cross-function targets.
+
+# REQUIRES: system-linux
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
+# RUN: %clang %cflags %t.o -o %t.exe -Wl,-q
+# RUN: llvm-bolt %t.exe -o %t.out -v=1 -print-cfg
+
+  .text
+  .globl main
+  .type main, %function
+  .p2align 2
+main:
+LBB0:
+  .cfi_startproc
+  andl $0xf, %ecx
+  cmpb $0x4, %cl
+  ja .main.cold.1
+LBB1:
+  leaq FAKE_JUMP_TABLE(%rip), %r8
+  cmpq %r8, %r9
+LBB2:
+  xorq %rax, %rax
+  ret
+  .cfi_endproc
+.size main, .-main
+
+  .globl main.cold.1
+  .type main.cold.1, %function
+  .p2align 2
+main.cold.1:
+  .cfi_startproc
+  nop
+LBB3:
+  callq abort
+  .cfi_endproc
+.size main.cold.1, .-main.cold.1
+
+  .rodata
+  .globl FAKE_JUMP_TABLE
+FAKE_JUMP_TABLE:
+  .long LBB2-FAKE_JUMP_TABLE
+  .long LBB3-FAKE_JUMP_TABLE+0x1