[BOLT] Decouple disassembly (decoding) from the control flow analysis

[Amir]

Summary

Populating Instructions field of a BinaryFunction is independent from
the control flow analysis. This would allow disassembling all functions
in parallel later.

bolt/include/bolt/Core/BinaryFunction.h

 /// In the input binary, an instance of BinaryFunction can represent a fragment
 /// of a function if the higher-level function was split, e.g. into hot and cold
 /// parts. The fragment containing the main entry point is called a parent
 /// or the main fragment.
 class BinaryFunction {
 public:
   enum class State : char {
     Empty = 0,     /// Function body is empty.
+    Decoded,       /// Instructions have been populated.
     Disassembled,  /// Function have been disassembled.
     CFG,           /// Control flow graph has been built.
     CFG_Finalized, /// CFG is finalized. No optimizations allowed.
     EmittedCFG,    /// Instructions have been emitted to output.
     Emitted,       /// Same as above plus CFG is destroyed.
   };
 
   /// Types of profile the function can use. Could be a combination.

 
   /// Return true iff the symbol could be seen inside this function otherwise
   /// it is probably another function.
   bool isSymbolValidInScope(const SymbolRef &Symbol, uint64_t SymbolSize) const;
 
   /// Disassemble function from raw data.
   /// If successful, this function will populate the list of instructions
   /// for this function together with offsets from the function start
-  /// in the input. It will also populate Labels with destinations for
-  /// local branches, and TakenBranches with [from, to] info.
-  ///
+  /// in the input.
   /// The Function should be properly initialized before this function
   /// is called. I.e. function address and size should be set.
   ///
   /// Returns true on successful disassembly, and updates the current
-  /// state to State:Disassembled.
+  /// state to State::Decoded.
+  bool decode(MCPlusBuilder::AllocatorIdTy AllocId);
+
+  /// If successful, this function will populate Labels with destinations for
+  /// local branches, and TakenBranches with [from, to] info.
+  ///
+  /// Returns true on successful disassembly, and updates the current
+  /// state to State::Disassembled.
   ///
   /// Returns false if disassembly failed.
   bool disassemble();
 
   void handlePCRelOperand(MCInst &Instruction, uint64_t Address, uint64_t Size);
 
   MCSymbol *handleExternalReference(MCInst &Instruction, uint64_t Size,
                                     uint64_t Offset, uint64_t TargetAddress,

bolt/include/bolt/Rewrite/RewriteInstance.h

private:
   /// Read profile data without having disassembled functions available.
   void preprocessProfileData();
 
   void processProfileDataPreCFG();
 
   /// Associate profile data with functions and data objects.
   void processProfileData();
 
+  /// Disassemble instructions in each function in the binary.
+  void disassembleInstructions();
+
   /// Disassemble each function in the binary and associate it with a
   /// BinaryFunction object, preparing all information necessary for binary
   /// optimization.
   void disassembleFunctions();
 
   void buildFunctionsCFG();
 
   void postProcessFunctions();

bolt/lib/Core/BinaryFunction.cpp

if (BC.isELF())
     return (Prefix + Name).str();
   static NameShortener NS;
   return (Prefix + Twine(NS.getID(Name))).str();
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const BinaryFunction::State State) {
   switch (State) {
   case BinaryFunction::State::Empty:         OS << "empty"; break;
+  case BinaryFunction::State::Decoded:       OS << "decoded"; break;
   case BinaryFunction::State::Disassembled:  OS << "disassembled"; break;
   case BinaryFunction::State::CFG:           OS << "CFG constructed"; break;
   case BinaryFunction::State::CFG_Finalized: OS << "CFG finalized"; break;
   case BinaryFunction::State::EmittedCFG:    OS << "emitted with CFG"; break;
   case BinaryFunction::State::Emitted:       OS << "emitted"; break;
   }
 
   return OS;
for (auto It = std::prev(Instructions.end()); Count != 0;
       MIB->addAnnotation(It->second, "AArch64Veneer", true);
     }
 
     BC.addAdrpAddRelocAArch64(*this, *TargetLowBits, *TargetHiBits,
                               TargetAddress);
   }
 }
 
-bool BinaryFunction::disassemble() {
+bool BinaryFunction::decode(MCPlusBuilder::AllocatorIdTy AllocId) {
   NamedRegionTimer T("disassemble", "Disassemble function", "buildfuncs",
                      "Build Binary Functions", opts::TimeBuild);
   ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData();
   assert(ErrorOrFunctionData && "function data is not available");
   ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData;
   assert(FunctionData.size() == getMaxSize() &&
          "function size does not match raw data size");
 
   auto &Ctx = BC.Ctx;
   auto &MIB = BC.MIB;
 
-  BC.SymbolicDisAsm->setSymbolizer(MIB->createTargetSymbolizer(*this));
-
-  // Insert a label at the beginning of the function. This will be our first
-  // basic block.
-  Labels[0] = Ctx->createNamedTempSymbol("BB0");
+  MCDisassembler *SymbolicDisAsm(
+      BC.TheTarget->createMCDisassembler(*BC.STI, *Ctx));
+  assert(SymbolicDisAsm);
+  SymbolicDisAsm->setSymbolizer(MIB->createTargetSymbolizer(*this));
 
   uint64_t Size = 0; // instruction size
   for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
     MCInst Instruction;
     const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
 
     // Check for data inside code and ignore it
     if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) {
       Size = DataInCodeSize;
       continue;
     }
 
-    if (!BC.SymbolicDisAsm->getInstruction(Instruction, Size,
-                                           FunctionData.slice(Offset),
-                                           AbsoluteInstrAddr, nulls())) {
+    if (!SymbolicDisAsm->getInstruction(Instruction, Size,
       // Functions with "soft" boundaries, e.g. coming from assembly source,
       // can have 0-byte padding at the end.
       if (isZeroPaddingAt(Offset))
         break;
 
+      auto L = BC.scopeLock();
       errs() << "BOLT-WARNING: unable to disassemble instruction at offset 0x"
              << Twine::utohexstr(Offset) << " (address 0x"
              << Twine::utohexstr(AbsoluteInstrAddr) << ") in function " << *this
              << '\n';
       // Some AVX-512 instructions could not be disassembled at all.
       if (BC.HasRelocations && opts::TrapOnAVX512 && BC.isX86()) {
         setTrapOnEntry();
         BC.TrappedFunctions.push_back(this);
       } else {
         setIgnored();
       }
 
       break;
     }
 
     // Check integrity of LLVM assembler/disassembler.
     if (opts::CheckEncoding && !BC.MIB->isBranch(Instruction) &&
         !BC.MIB->isCall(Instruction) && !BC.MIB->isNoop(Instruction)) {
       if (!BC.validateInstructionEncoding(FunctionData.slice(Offset, Size))) {
+        auto L = BC.scopeLock();
         errs() << "BOLT-WARNING: mismatching LLVM encoding detected in "
                << "function " << *this << " for instruction :\n";
         BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr);
         errs() << '\n';
       }
     }
 
     // Special handling for AVX-512 instructions.
     if (MIB->hasEVEXEncoding(Instruction)) {
       if (BC.HasRelocations && opts::TrapOnAVX512) {
+        auto L = BC.scopeLock();
         setTrapOnEntry();
         BC.TrappedFunctions.push_back(this);
         break;
       }
 
       if (!BC.validateInstructionEncoding(FunctionData.slice(Offset, Size))) {
+        auto L = BC.scopeLock();
         errs() << "BOLT-WARNING: internal assembler/disassembler error "
                   "detected for AVX512 instruction:\n";
         BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr);
         errs() << " in function " << *this << '\n';
         setIgnored();
         break;
       }
     }
 
+    // add instruction
+    if (getDWARFLineTable()) {
+      Instruction.setLoc(findDebugLineInformationForInstructionAt(
+          AbsoluteInstrAddr, getDWARFUnit(), getDWARFLineTable()));
+    }
+
+    // Record offset of the instruction for profile matching.
+    if (BC.keepOffsetForInstruction(Instruction))
+      MIB->setOffset(Instruction, static_cast<uint32_t>(Offset), AllocId);
+
+    // NOTE: disassembly loses the correct size information for noops.
+    //       E.g. nopw 0x0(%rax,%rax,1) is 9 bytes, but re-encoded it's only
+    //       5 bytes. Preserve the size info using annotations.
+    MIB->addAnnotation(Instruction, "Size", static_cast<uint32_t>(Size),
+                       AllocId);
+
+    addInstruction(Offset, std::move(Instruction));
+  }
+
+  // Reset symbolizer for the disassembler.
+  SymbolicDisAsm->setSymbolizer(nullptr);
+
+  updateState(State::Decoded);
+
+  return IsSimple;
+}
+
+bool BinaryFunction::disassemble() {
+  NamedRegionTimer T("disassemble", "Disassemble function", "buildfuncs",
+                     "Build Binary Functions", opts::TimeBuild);
+  ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData();
+  assert(ErrorOrFunctionData && "function data is not available");
+  ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData;
+  assert(FunctionData.size() == getMaxSize() &&
+         "function size does not match raw data size");
+
+  auto &Ctx = BC.Ctx;
+  auto &MIB = BC.MIB;
+
+  // Insert a label at the beginning of the function. This will be our first
+  // basic block.
+  Labels[0] = Ctx->createNamedTempSymbol("BB0");
+
+  for (auto &InstructionOffsetPair : Instructions) {
+    uint64_t Offset = InstructionOffsetPair.first;
+    MCInst &Instruction = InstructionOffsetPair.second;
+    const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
+    // instruction size
+    uint32_t Size = MIB->getAnnotationWithDefault(Instruction, "Size", 0);
+    assert(Size);
+    // Only preserve Size annotation for nops.
+    if (!BC.MIB->isNoop(Instruction))
+      MIB->removeAnnotation(Instruction, "Size");
+
     if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) {
       uint64_t TargetAddress = 0;
       if (MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size,
                               TargetAddress)) {
         // Check if the target is within the same function. Otherwise it's
         // a call, possibly a tail call.
         //
         // If the target *is* the function address it could be either a branch
if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) {
                                 << Twine::utohexstr(AbsoluteInstrAddr)
                                 << " in function " << *this
                                 << " : replacing with nop.\n");
               BC.MIB->createNoop(Instruction);
               if (IsCondBranch) {
                 // Register branch offset for profile validation.
                 IgnoredBranches.emplace_back(Offset, Offset + Size);
               }
-              goto add_instruction;
+              continue;
             }
             // May update Instruction and IsCall
             TargetSymbol = handleExternalReference(Instruction, Size, Offset,
                                                    TargetAddress, IsCall);
           }
         }
 
         if (!IsCall) {
if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) {
         // relocation, we mark it so we do not try to further process a
         // pc-relative operand. All we need is the symbol.
         UsedReloc = true;
       }
 
       if (MIB->hasPCRelOperand(Instruction) && !UsedReloc)
         handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size);
     }
-
-add_instruction:
-    if (getDWARFLineTable()) {
-      Instruction.setLoc(findDebugLineInformationForInstructionAt(
-          AbsoluteInstrAddr, getDWARFUnit(), getDWARFLineTable()));
-    }
-
-    // Record offset of the instruction for profile matching.
-    if (BC.keepOffsetForInstruction(Instruction))
-      MIB->setOffset(Instruction, static_cast<uint32_t>(Offset));
-
-    if (BC.MIB->isNoop(Instruction)) {
-      // NOTE: disassembly loses the correct size information for noops.
-      //       E.g. nopw 0x0(%rax,%rax,1) is 9 bytes, but re-encoded it's only
-      //       5 bytes. Preserve the size info using annotations.
-      MIB->addAnnotation(Instruction, "Size", static_cast<uint32_t>(Size));
-    }
-
-    addInstruction(Offset, std::move(Instruction));
   }
 
-  // Reset symbolizer for the disassembler.
-  BC.SymbolicDisAsm->setSymbolizer(nullptr);
-
   if (uint64_t Offset = getFirstInstructionOffset())
     Labels[Offset] = BC.Ctx->createNamedTempSymbol();
 
   clearList(Relocations);
 
   if (!IsSimple) {
     clearList(Instructions);
     return false;

bolt/lib/Rewrite/RewriteInstance.cpp

if (opts::AggregateOnly && BAT->enabledFor(InputFile)) {
     processProfileData();
     return Error::success();
   }
 
   selectFunctionsToProcess();
 
   readDebugInfo();
 
+  disassembleInstructions();
+
   disassembleFunctions();
 
   processProfileDataPreCFG();
 
   buildFunctionsCFG();
 
   processProfileData();
 
void RewriteInstance::processProfileData() {
 
   // Release memory used by profile reader.
   ProfileReader.reset();
 
   if (opts::AggregateOnly)
     exit(0);
 }
 
+void RewriteInstance::disassembleInstructions() {
+  NamedRegionTimer T("disassembleInstructions", "disassemble instructions",
+                     TimerGroupName, TimerGroupDesc, opts::TimeRewrite);
+
+  ParallelUtilities::WorkFuncWithAllocTy DisassembleFun =
+      [&](BinaryFunction &Function, MCPlusBuilder::AllocatorIdTy AllocId) {
+        ErrorOr<ArrayRef<uint8_t>> FunctionData = Function.getData();
+        if (!FunctionData) {
+          auto L = BC->scopeLock();
+          errs() << "BOLT-ERROR: corresponding section is non-executable or "
+                 << "empty for function " << Function << '\n';
+          exit(1);
+        }
+
+        // Treat zero-sized functions as non-simple ones.
+        if (Function.getSize() == 0) {
+          Function.setSimple(false);
+          return;
+        }
+
+        // Offset of the function in the file.
+        const auto *FileBegin =
+            reinterpret_cast<const uint8_t *>(InputFile->getData().data());
+        Function.setFileOffset(FunctionData->begin() - FileBegin);
+
+        if (!shouldDisassemble(Function)) {
+          NamedRegionTimer T("scan", "scan functions", "buildfuncs",
+                             "Scan Binary Functions", opts::TimeBuild);
+          Function.scanExternalRefs();
+          Function.setSimple(false);
+          return;
+        }
+
+        if (!Function.decode(AllocId)) {
+          if (opts::processAllFunctions())
+            BC->exitWithBugReport("function cannot be properly disassembled. "
+                                  "Unable to continue in relocation mode.",
+                                  Function);
+          if (opts::Verbosity >= 1)
+            outs() << "BOLT-INFO: could not disassemble function " << Function
+                   << ". Will ignore.\n";
+          // Forcefully ignore the function.
+          Function.setIgnored();
+          return;
+        }
+
+        if (opts::PrintAll || opts::PrintDisasm) {
+          auto L = BC->scopeLock();
+          Function.print(outs(), "after disassembly");
+        }
+      };
+
+  ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
+      *BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, DisassembleFun,
+      [](const BinaryFunction &BF) { return false; },
+      "disassembleFunctions-disassemble",
+      /*ForceSequential*/ opts::SequentialDisassembly || opts::PrintAll);
+}
+
 void RewriteInstance::disassembleFunctions() {
   NamedRegionTimer T("disassembleFunctions", "disassemble functions",
                      TimerGroupName, TimerGroupDesc, opts::TimeRewrite);
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     ErrorOr<ArrayRef<uint8_t>> FunctionData = Function.getData();
     if (!FunctionData) {

bolt/lib/Target/X86/X86MCSymbolizer.cpp

auto processPCRelOperandNoRel = [&]() {
 
     const MCOperand &Scale = Inst.getOperand(MemOp + X86::AddrScaleAmt);
     const MCOperand &Index = Inst.getOperand(MemOp + X86::AddrIndexReg);
     if (Scale.getImm() != 0 && Index.getReg() != MCRegister::NoRegister)
       return false;
 
     const MCSymbol *TargetSymbol;
     uint64_t TargetOffset;
+    auto L = BC.scopeLock();
     std::tie(TargetSymbol, TargetOffset) =
         BC.handleAddressRef(Value, Function, /*IsPCRel=*/true);
 
     addOperand(TargetSymbol, TargetOffset);
 
     return true;
   };
 
if (Relocation && Relocation::isX86GOTPCRELX(Relocation->Type)) {
     // instead of extracting the addend from the relocation, as non-standard
     // forms will be rejected by linker conversion process and the operand
     // will always reference GOT which we don't rewrite.
     if (processPCRelOperandNoRel())
       return true;
 
     // The linker converted the PC-relative address to an absolute one.
     // Symbolize this address.
+    auto L = BC.scopeLock();
     BC.handleAddressRef(Value, Function, /*IsPCRel=*/false);
     const BinaryData *Target = BC.getBinaryDataAtAddress(Value);
     assert(Target &&
            "BinaryData should exist at converted GOTPCRELX destination");
 
     addOperand(Target->getSymbol(), /*Addend=*/0);
 
     return true;
   }
 
   // Check for relocations against the operand.
   if (!Relocation || Relocation->Offset != InstOffset + ImmOffset)
     Relocation = Function.getRelocationAt(InstOffset + ImmOffset);
 
   if (!Relocation)
     return processPCRelOperandNoRel();
 
   uint64_t SymbolValue = Relocation->Value - Relocation->Addend;
   if (Relocation->isPCRelative())
     SymbolValue += InstAddress + ImmOffset;
 
+  auto L = BC.scopeLock();
   // Process reference to the symbol.
   BC.handleAddressRef(SymbolValue, Function, Relocation->isPCRelative());
 
   uint64_t Addend = Relocation->Addend;
   // Real addend for pc-relative targets is adjusted with a delta from
   // the relocation placement to the next instruction.
   if (Relocation->isPCRelative())
     Addend += InstOffset + InstSize - Relocation->Offset;