[BOLT] Add data to code relocations postprocessing

[Amir]

Summary

BOLT's assumption regarding data to code relocations is that
they will be "consumed", or accounted for, as jump table entries.
For jump tables that we failed to recognize, the relocation would
still be created and later attempted to be emitted, but if the
symbol was removed, this leads to undefined symbol error.

Add a post-processing step that accounts for such unclaimed
relocations and creates secondary entry points.

[Amir]

Add printing stats about created entry points

[tschuett]

bolt/lib/Core/BinaryContext.cpp

999

Are you tied to unordered_set ? There are more memory-efficient data structures:
https://llvm.org/docs/ProgrammersManual.html#set-like-containers-std-set-smallset-setvector-etc

[Amir]

bolt/lib/Core/BinaryContext.cpp

999

Thanks for a tip! No, a SmallPtrSet is probably a better data structure here.

[Amir]

Fix jump table entry check; SmallPtrSet

[Amir]

The issue should be handled via postProcessIndirectBranches ExternallyReferencedOffsets mechanism.

[Amir]

D132495

bolt/include/bolt/Core/BinaryContext.h

public:
   }
   /// Return true if the array of bytes represents a valid code padding.
   bool hasValidCodePadding(const BinaryFunction &BF);
 
   /// Verify padding area between functions, and adjust max function size
   /// accordingly.
   void adjustCodePadding();
 
+  /// Verify unclaimed Data to Code relocations, creating secondary entry points
+  /// for targets.
+  void postProcessDataRelocations();
+
   /// Regular page size.
   unsigned RegularPageSize{0x1000};
   static constexpr unsigned RegularPageSizeX86 = 0x1000;
   static constexpr unsigned RegularPageSizeAArch64 = 0x10000;
 
   /// Huge page size to use.
   static constexpr unsigned HugePageSize = 0x200000;
 

bolt/lib/Core/BinaryContext.cpp

 //===----------------------------------------------------------------------===//
 
 #include "bolt/Core/BinaryContext.h"
 #include "bolt/Core/BinaryEmitter.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Utils/CommandLineOpts.h"
 #include "bolt/Utils/NameResolver.h"
 #include "bolt/Utils/Utils.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
 #include "llvm/MC/MCAsmLayout.h"
 #include "llvm/MC/MCAssembler.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
if (!hasValidCodePadding(BF)) {
         BF.setIgnored();
       } else {
         BF.setMaxSize(BF.getSize());
       }
     }
   }
 }
 
+void BinaryContext::postProcessDataRelocations() {
+  if (!HasRelocations)
+    return;
+
+  SmallPtrSet<BinaryFunction *, 1> Functions;
+  SmallPtrSet<const MCSymbol *, 2> EntryPoints;
+
+  for (BinarySection &Section : sections()) {
+    const uint64_t SourceSectionStart = Section.getAddress();
+    for (const Relocation &Rel : Section.relocations()) {
+      LLVM_DEBUG({
+        dbgs() << "BOLT-DEBUG: post-processing relocation ";
+        Rel.print(dbgs());
+        dbgs() << '\n';
+      });
+      // PC-relative relocations have separate checking mechanism (strict mode)
+      if (Relocation::isPCRelative(Rel.Type))
+        continue;
+
+      // We expect relocations against function local labels, which have
+      // Addend == 0.
+      if (Rel.Addend)
+        continue;
+
+      const MCSymbol *ReferencedSymbol = Rel.Symbol;
+      // Check if the relocation value is a function entry point
+      if (getFunctionForSymbol(ReferencedSymbol))
+        continue;
+
+      // Check if the relocation value is a recognized jump table target
+      const uint64_t RelValue = Rel.Value;
+      const uint64_t RelSourceAddress = SourceSectionStart + Rel.Offset;
+      BinaryFunction *BF = getBinaryFunctionContainingAddress(
+          RelValue, /* CheckPastEnd */ false, /* UseMaxSize */ false);
+
+      // If there's no function at RelValue address, no need to register the
+      // target symbol as an entry point - i.e. checking past function end.
+      if (!BF)
+        continue;
+
+      // Skip non-simple functions
+      if (!BF->isSimple())
+        continue;
+
+      const JumpTable *JT = BF->getJumpTableContainingAddress(RelSourceAddress);
+      if (JT && llvm::is_contained(JT->Entries, ReferencedSymbol))
+        continue;
+
+      // Otherwise register the relocation target as a secondary entry point
+      const BinaryBasicBlock *BB = BF->getBasicBlockForLabel(ReferencedSymbol);
+      const MCSymbol *Label = BF->addEntryPoint(*BB);
+
+      Functions.insert(BF);
+      EntryPoints.insert(Label);
+      LLVM_DEBUG({
+        dbgs() << "BOLT-DEBUG: registered " << BB->getName()
+               << " as a secondary entry point in function " << *BF << '\n';
+      });
+    }
+  }
+  for (BinaryFunction *BF : Functions)
+    BF->setSimple(false);
+  if (opts::Verbosity >= 1) {
+    outs() << "BOLT-INFO: created " << EntryPoints.size() << " secondary entry "
+           << "points in " << Functions.size() << " functions for unclaimed "
+           << "data to code relocations.\n";
+    if (opts::Verbosity >= 2) {
+      for (BinaryFunction *BF : Functions)
+        outs() << *BF << '\n';
+      for (const MCSymbol *Symbol : EntryPoints)
+        outs() << Symbol->getName() << '\n';
+    }
+  }
+}
+
 MCSymbol *BinaryContext::registerNameAtAddress(StringRef Name, uint64_t Address,
                                                uint64_t Size,
                                                uint16_t Alignment,
                                                unsigned Flags) {
   // Register the name with MCContext.
   MCSymbol *Symbol = Ctx->getOrCreateSymbol(Name);
 
   auto GAI = BinaryDataMap.find(Address);

bolt/lib/Rewrite/RewriteInstance.cpp

void RewriteInstance::buildFunctionsCFG() {
   };
 
   ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
       *BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,
       SkipPredicate, "disassembleFunctions-buildCFG",
       /*ForceSequential*/ opts::SequentialDisassembly || opts::PrintAll);
 
   BC->postProcessSymbolTable();
+  BC->postProcessDataRelocations();
 }
 
 void RewriteInstance::postProcessFunctions() {
   // We mark fragments as non-simple here, not during disassembly,
   // So we can build their CFGs.
   BC->skipMarkedFragments();
   BC->clearFragmentsToSkip();