[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

1848

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

1849

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

1902

@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

1890

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

1895

1910

1912

1918

1919

[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

1750

Is there a reason to keep Found in a variable?

1762

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

1890–1891

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.
for (MCInst &Instr : BB) {
 
       addUnknownControlFlow(BB);
     }
   }
 
   if (HasInternalLabelReference)
     return false;
 
+  // Validate that all references to function internals from data are claimed by
+  // recognized jump tables. Register externally referenced blocks as entry
+  // points otherwise.
+  if (!HasUnknownControlFlow && hasInternalReference()) {
+    SmallPtrSet<MCSymbol *, 4> JTTargets;
+    for (const JumpTable *JT : llvm::make_second_range(JumpTables))
+      JTTargets.insert(JT->Entries.begin(), JT->Entries.end());
+    for (uint64_t Destination : ExternallyReferencedOffsets) {
+      if (BinaryBasicBlock *BB = getBasicBlockAtOffset(Destination)) {
+        bool Found = JTTargets.contains(BB->getLabel());
+        if (!Found) {
+          if (opts::Verbosity >= 1) {
+            outs() << "BOLT-WARNING: registering externally referenced "
+                   << BB->getName() << " as a secondary entry point in "
+                   << *this << ".\n";
+          }
+          addEntryPoint(*BB);
+        }
+      } else {
+        outs() << "BOLT-WARNING: external reference to offset "
+               << formatv("{0:x}", Destination)
+               << " does not point to a valid instruction in " << *this
+               << ". Ignoring the function.";
+        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;
 
   if (HasUnknownControlFlow && !BC.HasRelocations)
     return false;
 
   return true;
 }
 
 void BinaryFunction::recomputeLandingPads() {
   updateBBIndices(0);
 
   for (BinaryBasicBlock *BB : BasicBlocks) {
     BB->LandingPads.clear();
     BB->Throwers.clear();
   }
 
   for (BinaryBasicBlock *BB : BasicBlocks) {
     std::unordered_set<const BinaryBasicBlock *> BBLandingPads;
     for (MCInst &Instr : *BB) {
       if (!BC.MIB->isInvoke(Instr))
         continue;
 
       const Optional<MCPlus::MCLandingPad> EHInfo = BC.MIB->getEHInfo(Instr);
       if (!EHInfo || !EHInfo->first)
         continue;
 
       BinaryBasicBlock *LPBlock = getBasicBlockForLabel(EHInfo->first);
       if (!BBLandingPads.count(LPBlock)) {
         BBLandingPads.insert(LPBlock);
         BB->LandingPads.emplace_back(LPBlock);
         LPBlock->Throwers.emplace_back(BB);
       }
     }
   }
 }
 
 bool BinaryFunction::buildCFG(MCPlusBuilder::AllocatorIdTy AllocatorId) {
   auto &MIB = BC.MIB;
 
   if (!isSimple()) {
     assert(!BC.HasRelocations &&
            "cannot process file with non-simple function in relocs mode");
     return false;