[BOLT] Verify externally referenced blocks against jump table targets

[Amir]

Summary

For functions with references to internal offsets from data, verify externally
referenced blocks against the set of jump table targets. Mark the function
as non-simple if there are any unclaimed data to code references.

[Amir]

Verify the set of internal references against jump table targets.

[rafauler]

bolt/lib/Core/BinaryFunction.cpp

1852

What happens if we do have JumpTables and yet we have internal references that do not appear in any jump table?

1853

From reading this code I got the impression that UnknownControlFlow is only used in strict mode?

[rafauler]

I guess I reviewed an older version of the diff

[Amir]

HasUnknownControlFlow -> !Strict

[Amir]

Move checks past HasFixedIndirectBranch

[Amir]

clang-format

[Amir]

Update warning message to make it clear for end user what's going on

bolt/lib/Core/BinaryFunction.cpp

1878

@ayermolo: hope the warning makes sense now

[Amir]

Add extra check

[Amir]

Mark as non-simple

[Amir]

Added assembly test

[Amir]

Fix shrinkwrapping-restore-position test

[Amir]

Add runtime test checking if the moved code with external data references to it
works correctly. If there's a reference to offset which is not a registered BB
or label, ignore the function.

[Amir]

clang-format

[Amir]

Check for constant islands

[maksfb]

bolt/lib/Core/BinaryFunction.cpp

1866

Let's refactor the code into a function since it's quite large.

1871

1886

1888

1894

1895

[Amir]

Move checks into BF::validateExternalReferences

[Amir]

Address nits

[Amir]

rebase

[Amir]

Ping @maksfb

[maksfb]

bolt/include/bolt/Core/BinaryFunction.h

2108 ↗

(On Diff #458612)

It's reasonable to expect for validate...() function to return true if all checks pass. Please invert the return code.

bolt/lib/Core/BinaryFunction.cpp

1754

Is there a reason to keep Found in a variable?

1766

If you don't expect this warning to be firing frequently, let's print it at default verbosity level.

[Amir]

Address Maksim's comments

[maksfb]

LGTM, but please rename the method before the commit.

bolt/lib/Core/BinaryFunction.cpp

1866–1867

There's an apparent confusion with "internal" vs "external" reference in this context. Let's rename the method to validateExternallyReferencedOffsets() or validateReferencedOffsets() to avoid it.

[Amir]

Rename method to validateExternallyReferencedOffsets

[Amir]

clang-format

bolt/lib/Core/BinaryFunction.cpp

for (uint64_t PossibleDestination : ExternallyReferencedOffsets)
         BB.addSuccessor(SuccBB);
   };
 
   uint64_t NumIndirectJumps = 0;
   MCInst *LastIndirectJump = nullptr;
   BinaryBasicBlock *LastIndirectJumpBB = nullptr;
   uint64_t LastJT = 0;
   uint16_t LastJTIndexReg = BC.MIB->getNoRegister();
   for (BinaryBasicBlock &BB : blocks()) {
     for (MCInst &Instr : BB) {
       if (!BC.MIB->isIndirectBranch(Instr))
         continue;
 
       // If there's an indirect branch in a single-block function -
       // it must be a tail call.
       if (BasicBlocks.size() == 1) {
         BC.MIB->convertJmpToTailCall(Instr);
         return true;
       }
 
       ++NumIndirectJumps;
 
       if (opts::StrictMode && !hasInternalReference()) {
         BC.MIB->convertJmpToTailCall(Instr);
         break;
       }
 
       // Validate the tail call or jump table assumptions now that we know
       // basic block boundaries.
bool BinaryFunction::postProcessIndirectBranches(
   }
 
   if (HasInternalLabelReference)
     return false;
 
   // If there's only one jump table, and one indirect jump, and no other
   // references, then we should be able to derive the jump table even if we
   // fail to match the pattern.
   if (HasUnknownControlFlow && NumIndirectJumps == 1 &&
       JumpTables.size() == 1 && LastIndirectJump) {
     BC.MIB->setJumpTable(*LastIndirectJump, LastJT, LastJTIndexReg, AllocId);
     HasUnknownControlFlow = false;
 
     LastIndirectJumpBB->updateJumpTableSuccessors();
   }
 
   if (HasFixedIndirectBranch)
     return false;
 
+  // Validate that all data references to function offsets are claimed by
+  // recognized jump tables. Register externally referenced blocks as entry
+  // points.
+  if (!opts::StrictMode && hasInternalReference()) {
+    SmallPtrSet<MCSymbol *, 4> JTTargets;
+    for (const JumpTable *JT : llvm::make_second_range(JumpTables))
+      JTTargets.insert(JT->Entries.begin(), JT->Entries.end());
+
+    bool UnclaimedReference = false;
+    for (uint64_t Destination : ExternallyReferencedOffsets) {
+      // Ignore __builtin_unreachable().
+      if (Destination == getSize())
+        continue;
+
+      if (BinaryBasicBlock *BB = getBasicBlockAtOffset(Destination)) {
+        bool Found = JTTargets.contains(BB->getLabel());
+        if (Found)
+          continue;
+
+        if (opts::Verbosity >= 1) {
+          outs() << "BOLT-WARNING: unclaimed data to code reference (possibly "
+                 << "an unrecognized jump table entry) to " << BB->getName()
+                 << " in " << *this << ".\n";
+        }
+      } else if (opts::Verbosity >= 1) {
+        outs() << "BOLT-WARNING: unknown data to code reference to offset "
+               << Twine::utohexstr(Destination) << " in " << *this << ".\n";
+      }
+      UnclaimedReference = true;
+    }
+    if (UnclaimedReference)
+      return false;
+  }
+
   if (HasUnknownControlFlow && !BC.HasRelocations)
     return false;
 
   return true;
 }
 
 void BinaryFunction::recomputeLandingPads() {
   updateBBIndices(0);