xref: /llvm-project/bolt/lib/Core/BinaryFunction.cpp (revision a9cd49d50e88aa142e6d57de90321d8810e1027f)

//===- bolt/Core/BinaryFunction.cpp - Low-level function ------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the BinaryFunction class.
//
//===----------------------------------------------------------------------===//

#include "bolt/Core/BinaryFunction.h"
#include "bolt/Core/BinaryBasicBlock.h"
#include "bolt/Core/DynoStats.h"
#include "bolt/Core/MCPlusBuilder.h"
#include "bolt/Utils/NameResolver.h"
#include "bolt/Utils/NameShortener.h"
#include "bolt/Utils/Utils.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/edit_distance.h"
#include "llvm/Demangle/Demangle.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/MC/MCAsmLayout.h"
#include "llvm/MC/MCContext.h"
#include "llvm/MC/MCDisassembler/MCDisassembler.h"
#include "llvm/MC/MCExpr.h"
#include "llvm/MC/MCInst.h"
#include "llvm/MC/MCInstPrinter.h"
#include "llvm/MC/MCStreamer.h"
#include "llvm/Object/ObjectFile.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/LEB128.h"
#include "llvm/Support/Regex.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include <functional>
#include <limits>
#include <numeric>
#include <string>

#define DEBUG_TYPE "bolt"

using namespace llvm;
using namespace bolt;

namespace opts {

extern cl::OptionCategory BoltCategory;
extern cl::OptionCategory BoltOptCategory;
extern cl::OptionCategory BoltRelocCategory;

extern cl::opt<bool> EnableBAT;
extern cl::opt<bool> Instrument;
extern cl::opt<bool> StrictMode;
extern cl::opt<bool> UpdateDebugSections;
extern cl::opt<unsigned> Verbosity;

extern bool processAllFunctions();

cl::opt<bool>
CheckEncoding("check-encoding",
  cl::desc("perform verification of LLVM instruction encoding/decoding. "
           "Every instruction in the input is decoded and re-encoded. "
           "If the resulting bytes do not match the input, a warning message "
           "is printed."),
  cl::init(false),
  cl::ZeroOrMore,
  cl::Hidden,
  cl::cat(BoltCategory));

static cl::opt<bool>
DotToolTipCode("dot-tooltip-code",
  cl::desc("add basic block instructions as tool tips on nodes"),
  cl::ZeroOrMore,
  cl::Hidden,
  cl::cat(BoltCategory));

cl::opt<JumpTableSupportLevel>
JumpTables("jump-tables",
  cl::desc("jump tables support (default=basic)"),
  cl::init(JTS_BASIC),
  cl::values(
      clEnumValN(JTS_NONE, "none",
                 "do not optimize functions with jump tables"),
      clEnumValN(JTS_BASIC, "basic",
                 "optimize functions with jump tables"),
      clEnumValN(JTS_MOVE, "move",
                 "move jump tables to a separate section"),
      clEnumValN(JTS_SPLIT, "split",
                 "split jump tables section into hot and cold based on "
                 "function execution frequency"),
      clEnumValN(JTS_AGGRESSIVE, "aggressive",
                 "aggressively split jump tables section based on usage "
                 "of the tables")),
  cl::ZeroOrMore,
  cl::cat(BoltOptCategory));

static cl::opt<bool>
NoScan("no-scan",
  cl::desc("do not scan cold functions for external references (may result in "
           "slower binary)"),
  cl::init(false),
  cl::ZeroOrMore,
  cl::Hidden,
  cl::cat(BoltOptCategory));

cl::opt<bool>
PreserveBlocksAlignment("preserve-blocks-alignment",
  cl::desc("try to preserve basic block alignment"),
  cl::init(false),
  cl::ZeroOrMore,
  cl::cat(BoltOptCategory));

cl::opt<bool>
PrintDynoStats("dyno-stats",
  cl::desc("print execution info based on profile"),
  cl::cat(BoltCategory));

static cl::opt<bool>
PrintDynoStatsOnly("print-dyno-stats-only",
  cl::desc("while printing functions output dyno-stats and skip instructions"),
  cl::init(false),
  cl::Hidden,
  cl::cat(BoltCategory));

static cl::list<std::string>
PrintOnly("print-only",
  cl::CommaSeparated,
  cl::desc("list of functions to print"),
  cl::value_desc("func1,func2,func3,..."),
  cl::Hidden,
  cl::cat(BoltCategory));

cl::opt<bool>
TimeBuild("time-build",
  cl::desc("print time spent constructing binary functions"),
  cl::ZeroOrMore,
  cl::Hidden,
  cl::cat(BoltCategory));

cl::opt<bool>
TrapOnAVX512("trap-avx512",
  cl::desc("in relocation mode trap upon entry to any function that uses "
            "AVX-512 instructions"),
  cl::init(false),
  cl::ZeroOrMore,
  cl::Hidden,
  cl::cat(BoltCategory));

bool shouldPrint(const BinaryFunction &Function) {
  if (Function.isIgnored())
    return false;

  if (PrintOnly.empty())
    return true;

  for (std::string &Name : opts::PrintOnly) {
    if (Function.hasNameRegex(Name)) {
      return true;
    }
  }

  return false;
}

} // namespace opts

namespace llvm {
namespace bolt {

constexpr unsigned BinaryFunction::MinAlign;

namespace {

template <typename R> bool emptyRange(const R &Range) {
  return Range.begin() == Range.end();
}

/// Gets debug line information for the instruction located at the given
/// address in the original binary. The SMLoc's pointer is used
/// to point to this information, which is represented by a
/// DebugLineTableRowRef. The returned pointer is null if no debug line
/// information for this instruction was found.
SMLoc findDebugLineInformationForInstructionAt(
    uint64_t Address, DWARFUnit *Unit,
    const DWARFDebugLine::LineTable *LineTable) {
  // We use the pointer in SMLoc to store an instance of DebugLineTableRowRef,
  // which occupies 64 bits. Thus, we can only proceed if the struct fits into
  // the pointer itself.
  assert(sizeof(decltype(SMLoc().getPointer())) >=
             sizeof(DebugLineTableRowRef) &&
         "Cannot fit instruction debug line information into SMLoc's pointer");

  SMLoc NullResult = DebugLineTableRowRef::NULL_ROW.toSMLoc();
  uint32_t RowIndex = LineTable->lookupAddress(
      {Address, object::SectionedAddress::UndefSection});
  if (RowIndex == LineTable->UnknownRowIndex)
    return NullResult;

  assert(RowIndex < LineTable->Rows.size() &&
         "Line Table lookup returned invalid index.");

  decltype(SMLoc().getPointer()) Ptr;
  DebugLineTableRowRef *InstructionLocation =
      reinterpret_cast<DebugLineTableRowRef *>(&Ptr);

  InstructionLocation->DwCompileUnitIndex = Unit->getOffset();
  InstructionLocation->RowIndex = RowIndex + 1;

  return SMLoc::getFromPointer(Ptr);
}

std::string buildSectionName(StringRef Prefix, StringRef Name,
                             const BinaryContext &BC) {
  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::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;
}

} // namespace

std::string BinaryFunction::buildCodeSectionName(StringRef Name,
                                                 const BinaryContext &BC) {
  return buildSectionName(BC.isELF() ? ".local.text." : ".l.text.", Name, BC);
}

std::string BinaryFunction::buildColdCodeSectionName(StringRef Name,
                                                     const BinaryContext &BC) {
  return buildSectionName(BC.isELF() ? ".local.cold.text." : ".l.c.text.", Name,
                          BC);
}

uint64_t BinaryFunction::Count = 0;

Optional<StringRef> BinaryFunction::hasNameRegex(const StringRef Name) const {
  const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str();
  Regex MatchName(RegexName);
  Optional<StringRef> Match = forEachName(
      [&MatchName](StringRef Name) { return MatchName.match(Name); });

  return Match;
}

Optional<StringRef>
BinaryFunction::hasRestoredNameRegex(const StringRef Name) const {
  const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str();
  Regex MatchName(RegexName);
  Optional<StringRef> Match = forEachName([&MatchName](StringRef Name) {
    return MatchName.match(NameResolver::restore(Name));
  });

  return Match;
}

std::string BinaryFunction::getDemangledName() const {
  StringRef MangledName = NameResolver::restore(getOneName());
  return demangle(MangledName.str());
}

BinaryBasicBlock *
BinaryFunction::getBasicBlockContainingOffset(uint64_t Offset) {
  if (Offset > Size)
    return nullptr;

  if (BasicBlockOffsets.empty())
    return nullptr;

  /*
   * This is commented out because it makes BOLT too slow.
   * assert(std::is_sorted(BasicBlockOffsets.begin(),
   *                       BasicBlockOffsets.end(),
   *                       CompareBasicBlockOffsets())));
   */
  auto I = std::upper_bound(BasicBlockOffsets.begin(), BasicBlockOffsets.end(),
                            BasicBlockOffset(Offset, nullptr),
                            CompareBasicBlockOffsets());
  assert(I != BasicBlockOffsets.begin() && "first basic block not at offset 0");
  --I;
  BinaryBasicBlock *BB = I->second;
  return (Offset < BB->getOffset() + BB->getOriginalSize()) ? BB : nullptr;
}

void BinaryFunction::markUnreachableBlocks() {
  std::stack<BinaryBasicBlock *> Stack;

  for (BinaryBasicBlock *BB : layout())
    BB->markValid(false);

  // Add all entries and landing pads as roots.
  for (BinaryBasicBlock *BB : BasicBlocks) {
    if (isEntryPoint(*BB) || BB->isLandingPad()) {
      Stack.push(BB);
      BB->markValid(true);
      continue;
    }
    // FIXME:
    // Also mark BBs with indirect jumps as reachable, since we do not
    // support removing unused jump tables yet (GH-issue20).
    for (const MCInst &Inst : *BB) {
      if (BC.MIB->getJumpTable(Inst)) {
        Stack.push(BB);
        BB->markValid(true);
        break;
      }
    }
  }

  // Determine reachable BBs from the entry point
  while (!Stack.empty()) {
    BinaryBasicBlock *BB = Stack.top();
    Stack.pop();
    for (BinaryBasicBlock *Succ : BB->successors()) {
      if (Succ->isValid())
        continue;
      Succ->markValid(true);
      Stack.push(Succ);
    }
  }
}

// Any unnecessary fallthrough jumps revealed after calling eraseInvalidBBs
// will be cleaned up by fixBranches().
std::pair<unsigned, uint64_t> BinaryFunction::eraseInvalidBBs() {
  BasicBlockOrderType NewLayout;
  unsigned Count = 0;
  uint64_t Bytes = 0;
  for (BinaryBasicBlock *BB : layout()) {
    if (BB->isValid()) {
      NewLayout.push_back(BB);
    } else {
      assert(!isEntryPoint(*BB) && "all entry blocks must be valid");
      ++Count;
      Bytes += BC.computeCodeSize(BB->begin(), BB->end());
    }
  }
  BasicBlocksLayout = std::move(NewLayout);

  BasicBlockListType NewBasicBlocks;
  for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
    BinaryBasicBlock *BB = *I;
    if (BB->isValid()) {
      NewBasicBlocks.push_back(BB);
    } else {
      // Make sure the block is removed from the list of predecessors.
      BB->removeAllSuccessors();
      DeletedBasicBlocks.push_back(BB);
    }
  }
  BasicBlocks = std::move(NewBasicBlocks);

  assert(BasicBlocks.size() == BasicBlocksLayout.size());

  // Update CFG state if needed
  if (Count > 0)
    recomputeLandingPads();

  return std::make_pair(Count, Bytes);
}

bool BinaryFunction::isForwardCall(const MCSymbol *CalleeSymbol) const {
  // This function should work properly before and after function reordering.
  // In order to accomplish this, we use the function index (if it is valid).
  // If the function indices are not valid, we fall back to the original
  // addresses.  This should be ok because the functions without valid indices
  // should have been ordered with a stable sort.
  const BinaryFunction *CalleeBF = BC.getFunctionForSymbol(CalleeSymbol);
  if (CalleeBF) {
    if (CalleeBF->isInjected())
      return true;

    if (hasValidIndex() && CalleeBF->hasValidIndex()) {
      return getIndex() < CalleeBF->getIndex();
    } else if (hasValidIndex() && !CalleeBF->hasValidIndex()) {
      return true;
    } else if (!hasValidIndex() && CalleeBF->hasValidIndex()) {
      return false;
    } else {
      return getAddress() < CalleeBF->getAddress();
    }
  } else {
    // Absolute symbol.
    ErrorOr<uint64_t> CalleeAddressOrError = BC.getSymbolValue(*CalleeSymbol);
    assert(CalleeAddressOrError && "unregistered symbol found");
    return *CalleeAddressOrError > getAddress();
  }
}

void BinaryFunction::dump(bool PrintInstructions) const {
  print(dbgs(), "", PrintInstructions);
}

void BinaryFunction::print(raw_ostream &OS, std::string Annotation,
                           bool PrintInstructions) const {
  if (!opts::shouldPrint(*this))
    return;

  StringRef SectionName =
      OriginSection ? OriginSection->getName() : "<no origin section>";
  OS << "Binary Function \"" << *this << "\" " << Annotation << " {";
  std::vector<StringRef> AllNames = getNames();
  if (AllNames.size() > 1) {
    OS << "\n  All names   : ";
    const char *Sep = "";
    for (const StringRef Name : AllNames) {
      OS << Sep << Name;
      Sep = "\n                ";
    }
  }
  OS << "\n  Number      : "   << FunctionNumber
     << "\n  State       : "   << CurrentState
     << "\n  Address     : 0x" << Twine::utohexstr(Address)
     << "\n  Size        : 0x" << Twine::utohexstr(Size)
     << "\n  MaxSize     : 0x" << Twine::utohexstr(MaxSize)
     << "\n  Offset      : 0x" << Twine::utohexstr(FileOffset)
     << "\n  Section     : "   << SectionName
     << "\n  Orc Section : "   << getCodeSectionName()
     << "\n  LSDA        : 0x" << Twine::utohexstr(getLSDAAddress())
     << "\n  IsSimple    : "   << IsSimple
     << "\n  IsMultiEntry: "   << isMultiEntry()
     << "\n  IsSplit     : "   << isSplit()
     << "\n  BB Count    : "   << size();

  if (HasFixedIndirectBranch)
    OS << "\n  HasFixedIndirectBranch : true";
  if (HasUnknownControlFlow)
    OS << "\n  Unknown CF  : true";
  if (getPersonalityFunction())
    OS << "\n  Personality : " << getPersonalityFunction()->getName();
  if (IsFragment)
    OS << "\n  IsFragment  : true";
  if (isFolded())
    OS << "\n  FoldedInto  : " << *getFoldedIntoFunction();
  for (BinaryFunction *ParentFragment : ParentFragments)
    OS << "\n  Parent      : " << *ParentFragment;
  if (!Fragments.empty()) {
    OS << "\n  Fragments   : ";
    const char *Sep = "";
    for (BinaryFunction *Frag : Fragments) {
      OS << Sep << *Frag;
      Sep = ", ";
    }
  }
  if (hasCFG())
    OS << "\n  Hash        : " << Twine::utohexstr(computeHash());
  if (isMultiEntry()) {
    OS << "\n  Secondary Entry Points : ";
    const char *Sep = "";
    for (const auto &KV : SecondaryEntryPoints) {
      OS << Sep << KV.second->getName();
      Sep = ", ";
    }
  }
  if (FrameInstructions.size())
    OS << "\n  CFI Instrs  : " << FrameInstructions.size();
  if (BasicBlocksLayout.size()) {
    OS << "\n  BB Layout   : ";
    const char *Sep = "";
    for (BinaryBasicBlock *BB : BasicBlocksLayout) {
      OS << Sep << BB->getName();
      Sep = ", ";
    }
  }
  if (ImageAddress)
    OS << "\n  Image       : 0x" << Twine::utohexstr(ImageAddress);
  if (ExecutionCount != COUNT_NO_PROFILE) {
    OS << "\n  Exec Count  : " << ExecutionCount;
    OS << "\n  Profile Acc : " << format("%.1f%%", ProfileMatchRatio * 100.0f);
  }

  if (opts::PrintDynoStats && !BasicBlocksLayout.empty()) {
    OS << '\n';
    DynoStats dynoStats = getDynoStats(*this);
    OS << dynoStats;
  }

  OS << "\n}\n";

  if (opts::PrintDynoStatsOnly || !PrintInstructions || !BC.InstPrinter)
    return;

  // Offset of the instruction in function.
  uint64_t Offset = 0;

  if (BasicBlocks.empty() && !Instructions.empty()) {
    // Print before CFG was built.
    for (const std::pair<const uint32_t, MCInst> &II : Instructions) {
      Offset = II.first;

      // Print label if exists at this offset.
      auto LI = Labels.find(Offset);
      if (LI != Labels.end()) {
        if (const MCSymbol *EntrySymbol =
                getSecondaryEntryPointSymbol(LI->second))
          OS << EntrySymbol->getName() << " (Entry Point):\n";
        OS << LI->second->getName() << ":\n";
      }

      BC.printInstruction(OS, II.second, Offset, this);
    }
  }

  for (uint32_t I = 0, E = BasicBlocksLayout.size(); I != E; ++I) {
    BinaryBasicBlock *BB = BasicBlocksLayout[I];
    if (I != 0 && BB->isCold() != BasicBlocksLayout[I - 1]->isCold())
      OS << "-------   HOT-COLD SPLIT POINT   -------\n\n";

    OS << BB->getName() << " (" << BB->size()
       << " instructions, align : " << BB->getAlignment() << ")\n";

    if (isEntryPoint(*BB)) {
      if (MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB))
        OS << "  Secondary Entry Point: " << EntrySymbol->getName() << '\n';
      else
        OS << "  Entry Point\n";
    }

    if (BB->isLandingPad())
      OS << "  Landing Pad\n";

    uint64_t BBExecCount = BB->getExecutionCount();
    if (hasValidProfile()) {
      OS << "  Exec Count : ";
      if (BB->getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE)
        OS << BBExecCount << '\n';
      else
        OS << "<unknown>\n";
    }
    if (BB->getCFIState() >= 0)
      OS << "  CFI State : " << BB->getCFIState() << '\n';
    if (opts::EnableBAT) {
      OS << "  Input offset: " << Twine::utohexstr(BB->getInputOffset())
         << "\n";
    }
    if (!BB->pred_empty()) {
      OS << "  Predecessors: ";
      const char *Sep = "";
      for (BinaryBasicBlock *Pred : BB->predecessors()) {
        OS << Sep << Pred->getName();
        Sep = ", ";
      }
      OS << '\n';
    }
    if (!BB->throw_empty()) {
      OS << "  Throwers: ";
      const char *Sep = "";
      for (BinaryBasicBlock *Throw : BB->throwers()) {
        OS << Sep << Throw->getName();
        Sep = ", ";
      }
      OS << '\n';
    }

    Offset = alignTo(Offset, BB->getAlignment());

    // Note: offsets are imprecise since this is happening prior to relaxation.
    Offset = BC.printInstructions(OS, BB->begin(), BB->end(), Offset, this);

    if (!BB->succ_empty()) {
      OS << "  Successors: ";
      // For more than 2 successors, sort them based on frequency.
      std::vector<uint64_t> Indices(BB->succ_size());
      std::iota(Indices.begin(), Indices.end(), 0);
      if (BB->succ_size() > 2 && BB->getKnownExecutionCount()) {
        std::stable_sort(Indices.begin(), Indices.end(),
                         [&](const uint64_t A, const uint64_t B) {
                           return BB->BranchInfo[B] < BB->BranchInfo[A];
                         });
      }
      const char *Sep = "";
      for (unsigned I = 0; I < Indices.size(); ++I) {
        BinaryBasicBlock *Succ = BB->Successors[Indices[I]];
        BinaryBasicBlock::BinaryBranchInfo &BI = BB->BranchInfo[Indices[I]];
        OS << Sep << Succ->getName();
        if (ExecutionCount != COUNT_NO_PROFILE &&
            BI.MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
          OS << " (mispreds: " << BI.MispredictedCount
             << ", count: " << BI.Count << ")";
        } else if (ExecutionCount != COUNT_NO_PROFILE &&
                   BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
          OS << " (inferred count: " << BI.Count << ")";
        }
        Sep = ", ";
      }
      OS << '\n';
    }

    if (!BB->lp_empty()) {
      OS << "  Landing Pads: ";
      const char *Sep = "";
      for (BinaryBasicBlock *LP : BB->landing_pads()) {
        OS << Sep << LP->getName();
        if (ExecutionCount != COUNT_NO_PROFILE) {
          OS << " (count: " << LP->getExecutionCount() << ")";
        }
        Sep = ", ";
      }
      OS << '\n';
    }

    // In CFG_Finalized state we can miscalculate CFI state at exit.
    if (CurrentState == State::CFG) {
      const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
      if (CFIStateAtExit >= 0)
        OS << "  CFI State: " << CFIStateAtExit << '\n';
    }

    OS << '\n';
  }

  // Dump new exception ranges for the function.
  if (!CallSites.empty()) {
    OS << "EH table:\n";
    for (const CallSite &CSI : CallSites) {
      OS << "  [" << *CSI.Start << ", " << *CSI.End << ") landing pad : ";
      if (CSI.LP)
        OS << *CSI.LP;
      else
        OS << "0";
      OS << ", action : " << CSI.Action << '\n';
    }
    OS << '\n';
  }

  // Print all jump tables.
  for (const std::pair<const uint64_t, JumpTable *> &JTI : JumpTables)
    JTI.second->print(OS);

  OS << "DWARF CFI Instructions:\n";
  if (OffsetToCFI.size()) {
    // Pre-buildCFG information
    for (const std::pair<const uint32_t, uint32_t> &Elmt : OffsetToCFI) {
      OS << format("    %08x:\t", Elmt.first);
      assert(Elmt.second < FrameInstructions.size() && "Incorrect CFI offset");
      BinaryContext::printCFI(OS, FrameInstructions[Elmt.second]);
      OS << "\n";
    }
  } else {
    // Post-buildCFG information
    for (uint32_t I = 0, E = FrameInstructions.size(); I != E; ++I) {
      const MCCFIInstruction &CFI = FrameInstructions[I];
      OS << format("    %d:\t", I);
      BinaryContext::printCFI(OS, CFI);
      OS << "\n";
    }
  }
  if (FrameInstructions.empty())
    OS << "    <empty>\n";

  OS << "End of Function \"" << *this << "\"\n\n";
}

void BinaryFunction::printRelocations(raw_ostream &OS, uint64_t Offset,
                                      uint64_t Size) const {
  const char *Sep = " # Relocs: ";

  auto RI = Relocations.lower_bound(Offset);
  while (RI != Relocations.end() && RI->first < Offset + Size) {
    OS << Sep << "(R: " << RI->second << ")";
    Sep = ", ";
    ++RI;
  }
}

namespace {
std::string mutateDWARFExpressionTargetReg(const MCCFIInstruction &Instr,
                                           MCPhysReg NewReg) {
  StringRef ExprBytes = Instr.getValues();
  assert(ExprBytes.size() > 1 && "DWARF expression CFI is too short");
  uint8_t Opcode = ExprBytes[0];
  assert((Opcode == dwarf::DW_CFA_expression ||
          Opcode == dwarf::DW_CFA_val_expression) &&
         "invalid DWARF expression CFI");
  const uint8_t *const Start =
      reinterpret_cast<const uint8_t *>(ExprBytes.drop_front(1).data());
  const uint8_t *const End =
      reinterpret_cast<const uint8_t *>(Start + ExprBytes.size() - 1);
  unsigned Size = 0;
  decodeULEB128(Start, &Size, End);
  assert(Size > 0 && "Invalid reg encoding for DWARF expression CFI");
  SmallString<8> Tmp;
  raw_svector_ostream OSE(Tmp);
  encodeULEB128(NewReg, OSE);
  return Twine(ExprBytes.slice(0, 1))
      .concat(OSE.str())
      .concat(ExprBytes.drop_front(1 + Size))
      .str();
}
} // namespace

void BinaryFunction::mutateCFIRegisterFor(const MCInst &Instr,
                                          MCPhysReg NewReg) {
  const MCCFIInstruction *OldCFI = getCFIFor(Instr);
  assert(OldCFI && "invalid CFI instr");
  switch (OldCFI->getOperation()) {
  default:
    llvm_unreachable("Unexpected instruction");
  case MCCFIInstruction::OpDefCfa:
    setCFIFor(Instr, MCCFIInstruction::cfiDefCfa(nullptr, NewReg,
                                                 OldCFI->getOffset()));
    break;
  case MCCFIInstruction::OpDefCfaRegister:
    setCFIFor(Instr, MCCFIInstruction::createDefCfaRegister(nullptr, NewReg));
    break;
  case MCCFIInstruction::OpOffset:
    setCFIFor(Instr, MCCFIInstruction::createOffset(nullptr, NewReg,
                                                    OldCFI->getOffset()));
    break;
  case MCCFIInstruction::OpRegister:
    setCFIFor(Instr, MCCFIInstruction::createRegister(nullptr, NewReg,
                                                      OldCFI->getRegister2()));
    break;
  case MCCFIInstruction::OpSameValue:
    setCFIFor(Instr, MCCFIInstruction::createSameValue(nullptr, NewReg));
    break;
  case MCCFIInstruction::OpEscape:
    setCFIFor(Instr,
              MCCFIInstruction::createEscape(
                  nullptr,
                  StringRef(mutateDWARFExpressionTargetReg(*OldCFI, NewReg))));
    break;
  case MCCFIInstruction::OpRestore:
    setCFIFor(Instr, MCCFIInstruction::createRestore(nullptr, NewReg));
    break;
  case MCCFIInstruction::OpUndefined:
    setCFIFor(Instr, MCCFIInstruction::createUndefined(nullptr, NewReg));
    break;
  }
}

const MCCFIInstruction *BinaryFunction::mutateCFIOffsetFor(const MCInst &Instr,
                                                           int64_t NewOffset) {
  const MCCFIInstruction *OldCFI = getCFIFor(Instr);
  assert(OldCFI && "invalid CFI instr");
  switch (OldCFI->getOperation()) {
  default:
    llvm_unreachable("Unexpected instruction");
  case MCCFIInstruction::OpDefCfaOffset:
    setCFIFor(Instr, MCCFIInstruction::cfiDefCfaOffset(nullptr, NewOffset));
    break;
  case MCCFIInstruction::OpAdjustCfaOffset:
    setCFIFor(Instr,
              MCCFIInstruction::createAdjustCfaOffset(nullptr, NewOffset));
    break;
  case MCCFIInstruction::OpDefCfa:
    setCFIFor(Instr, MCCFIInstruction::cfiDefCfa(nullptr, OldCFI->getRegister(),
                                                 NewOffset));
    break;
  case MCCFIInstruction::OpOffset:
    setCFIFor(Instr, MCCFIInstruction::createOffset(
                         nullptr, OldCFI->getRegister(), NewOffset));
    break;
  }
  return getCFIFor(Instr);
}

IndirectBranchType
BinaryFunction::processIndirectBranch(MCInst &Instruction, unsigned Size,
                                      uint64_t Offset,
                                      uint64_t &TargetAddress) {
  const unsigned PtrSize = BC.AsmInfo->getCodePointerSize();

  // The instruction referencing memory used by the branch instruction.
  // It could be the branch instruction itself or one of the instructions
  // setting the value of the register used by the branch.
  MCInst *MemLocInstr;

  // Address of the table referenced by MemLocInstr. Could be either an
  // array of function pointers, or a jump table.
  uint64_t ArrayStart = 0;

  unsigned BaseRegNum, IndexRegNum;
  int64_t DispValue;
  const MCExpr *DispExpr;

  // In AArch, identify the instruction adding the PC-relative offset to
  // jump table entries to correctly decode it.
  MCInst *PCRelBaseInstr;
  uint64_t PCRelAddr = 0;

  auto Begin = Instructions.begin();
  if (BC.isAArch64()) {
    PreserveNops = BC.HasRelocations;
    // Start at the last label as an approximation of the current basic block.
    // This is a heuristic, since the full set of labels have yet to be
    // determined
    for (auto LI = Labels.rbegin(); LI != Labels.rend(); ++LI) {
      auto II = Instructions.find(LI->first);
      if (II != Instructions.end()) {
        Begin = II;
        break;
      }
    }
  }

  IndirectBranchType BranchType = BC.MIB->analyzeIndirectBranch(
      Instruction, Begin, Instructions.end(), PtrSize, MemLocInstr, BaseRegNum,
      IndexRegNum, DispValue, DispExpr, PCRelBaseInstr);

  if (BranchType == IndirectBranchType::UNKNOWN && !MemLocInstr)
    return BranchType;

  if (MemLocInstr != &Instruction)
    IndexRegNum = BC.MIB->getNoRegister();

  if (BC.isAArch64()) {
    const MCSymbol *Sym = BC.MIB->getTargetSymbol(*PCRelBaseInstr, 1);
    assert(Sym && "Symbol extraction failed");
    ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(*Sym);
    if (SymValueOrError) {
      PCRelAddr = *SymValueOrError;
    } else {
      for (std::pair<const uint32_t, MCSymbol *> &Elmt : Labels) {
        if (Elmt.second == Sym) {
          PCRelAddr = Elmt.first + getAddress();
          break;
        }
      }
    }
    uint64_t InstrAddr = 0;
    for (auto II = Instructions.rbegin(); II != Instructions.rend(); ++II) {
      if (&II->second == PCRelBaseInstr) {
        InstrAddr = II->first + getAddress();
        break;
      }
    }
    assert(InstrAddr != 0 && "instruction not found");
    // We do this to avoid spurious references to code locations outside this
    // function (for example, if the indirect jump lives in the last basic
    // block of the function, it will create a reference to the next function).
    // This replaces a symbol reference with an immediate.
    BC.MIB->replaceMemOperandDisp(*PCRelBaseInstr,
                                  MCOperand::createImm(PCRelAddr - InstrAddr));
    // FIXME: Disable full jump table processing for AArch64 until we have a
    // proper way of determining the jump table limits.
    return IndirectBranchType::UNKNOWN;
  }

  // RIP-relative addressing should be converted to symbol form by now
  // in processed instructions (but not in jump).
  if (DispExpr) {
    const MCSymbol *TargetSym;
    uint64_t TargetOffset;
    std::tie(TargetSym, TargetOffset) = BC.MIB->getTargetSymbolInfo(DispExpr);
    ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(*TargetSym);
    assert(SymValueOrError && "global symbol needs a value");
    ArrayStart = *SymValueOrError + TargetOffset;
    BaseRegNum = BC.MIB->getNoRegister();
    if (BC.isAArch64()) {
      ArrayStart &= ~0xFFFULL;
      ArrayStart += DispValue & 0xFFFULL;
    }
  } else {
    ArrayStart = static_cast<uint64_t>(DispValue);
  }

  if (BaseRegNum == BC.MRI->getProgramCounter())
    ArrayStart += getAddress() + Offset + Size;

  LLVM_DEBUG(dbgs() << "BOLT-DEBUG: addressed memory is 0x"
                    << Twine::utohexstr(ArrayStart) << '\n');

  ErrorOr<BinarySection &> Section = BC.getSectionForAddress(ArrayStart);
  if (!Section) {
    // No section - possibly an absolute address. Since we don't allow
    // internal function addresses to escape the function scope - we
    // consider it a tail call.
    if (opts::Verbosity >= 1) {
      errs() << "BOLT-WARNING: no section for address 0x"
             << Twine::utohexstr(ArrayStart) << " referenced from function "
             << *this << '\n';
    }
    return IndirectBranchType::POSSIBLE_TAIL_CALL;
  }
  if (Section->isVirtual()) {
    // The contents are filled at runtime.
    return IndirectBranchType::POSSIBLE_TAIL_CALL;
  }

  if (BranchType == IndirectBranchType::POSSIBLE_FIXED_BRANCH) {
    ErrorOr<uint64_t> Value = BC.getPointerAtAddress(ArrayStart);
    if (!Value)
      return IndirectBranchType::UNKNOWN;

    if (!BC.getSectionForAddress(ArrayStart)->isReadOnly())
      return IndirectBranchType::UNKNOWN;

    outs() << "BOLT-INFO: fixed indirect branch detected in " << *this
           << " at 0x" << Twine::utohexstr(getAddress() + Offset)
           << " referencing data at 0x" << Twine::utohexstr(ArrayStart)
           << " the destination value is 0x" << Twine::utohexstr(*Value)
           << '\n';

    TargetAddress = *Value;
    return BranchType;
  }

  // Check if there's already a jump table registered at this address.
  MemoryContentsType MemType;
  if (JumpTable *JT = BC.getJumpTableContainingAddress(ArrayStart)) {
    switch (JT->Type) {
    case JumpTable::JTT_NORMAL:
      MemType = MemoryContentsType::POSSIBLE_JUMP_TABLE;
      break;
    case JumpTable::JTT_PIC:
      MemType = MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE;
      break;
    }
  } else {
    MemType = BC.analyzeMemoryAt(ArrayStart, *this);
  }

  // Check that jump table type in instruction pattern matches memory contents.
  JumpTable::JumpTableType JTType;
  if (BranchType == IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE) {
    if (MemType != MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE)
      return IndirectBranchType::UNKNOWN;
    JTType = JumpTable::JTT_PIC;
  } else {
    if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE)
      return IndirectBranchType::UNKNOWN;

    if (MemType == MemoryContentsType::UNKNOWN)
      return IndirectBranchType::POSSIBLE_TAIL_CALL;

    BranchType = IndirectBranchType::POSSIBLE_JUMP_TABLE;
    JTType = JumpTable::JTT_NORMAL;
  }

  // Convert the instruction into jump table branch.
  const MCSymbol *JTLabel = BC.getOrCreateJumpTable(*this, ArrayStart, JTType);
  BC.MIB->replaceMemOperandDisp(*MemLocInstr, JTLabel, BC.Ctx.get());
  BC.MIB->setJumpTable(Instruction, ArrayStart, IndexRegNum);

  JTSites.emplace_back(Offset, ArrayStart);

  return BranchType;
}

MCSymbol *BinaryFunction::getOrCreateLocalLabel(uint64_t Address,
                                                bool CreatePastEnd) {
  const uint64_t Offset = Address - getAddress();

  if ((Offset == getSize()) && CreatePastEnd)
    return getFunctionEndLabel();

  auto LI = Labels.find(Offset);
  if (LI != Labels.end())
    return LI->second;

  // For AArch64, check if this address is part of a constant island.
  if (BC.isAArch64()) {
    if (MCSymbol *IslandSym = getOrCreateIslandAccess(Address))
      return IslandSym;
  }

  MCSymbol *Label = BC.Ctx->createNamedTempSymbol();
  Labels[Offset] = Label;

  return Label;
}

ErrorOr<ArrayRef<uint8_t>> BinaryFunction::getData() const {
  BinarySection &Section = *getOriginSection();
  assert(Section.containsRange(getAddress(), getMaxSize()) &&
         "wrong section for function");

  if (!Section.isText() || Section.isVirtual() || !Section.getSize())
    return std::make_error_code(std::errc::bad_address);

  StringRef SectionContents = Section.getContents();

  assert(SectionContents.size() == Section.getSize() &&
         "section size mismatch");

  // Function offset from the section start.
  uint64_t Offset = getAddress() - Section.getAddress();
  auto *Bytes = reinterpret_cast<const uint8_t *>(SectionContents.data());
  return ArrayRef<uint8_t>(Bytes + Offset, getMaxSize());
}

size_t BinaryFunction::getSizeOfDataInCodeAt(uint64_t Offset) const {
  if (!Islands)
    return 0;

  if (Islands->DataOffsets.find(Offset) == Islands->DataOffsets.end())
    return 0;

  auto Iter = Islands->CodeOffsets.upper_bound(Offset);
  if (Iter != Islands->CodeOffsets.end())
    return *Iter - Offset;
  return getSize() - Offset;
}

bool BinaryFunction::isZeroPaddingAt(uint64_t Offset) const {
  ArrayRef<uint8_t> FunctionData = *getData();
  uint64_t EndOfCode = getSize();
  if (Islands) {
    auto Iter = Islands->DataOffsets.upper_bound(Offset);
    if (Iter != Islands->DataOffsets.end())
      EndOfCode = *Iter;
  }
  for (uint64_t I = Offset; I < EndOfCode; ++I)
    if (FunctionData[I] != 0)
      return false;

  return true;
}

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");

  auto handlePCRelOperand = [&](MCInst &Instruction, uint64_t Address,
                                uint64_t Size) {
    uint64_t TargetAddress = 0;
    if (!MIB->evaluateMemOperandTarget(Instruction, TargetAddress, Address,
                                       Size)) {
      errs() << "BOLT-ERROR: PC-relative operand can't be evaluated:\n";
      BC.InstPrinter->printInst(&Instruction, 0, "", *BC.STI, errs());
      errs() << '\n';
      Instruction.dump_pretty(errs(), BC.InstPrinter.get());
      errs() << '\n';
      errs() << "BOLT-ERROR: cannot handle PC-relative operand at 0x"
             << Twine::utohexstr(Address) << ". Skipping function " << *this
             << ".\n";
      if (BC.HasRelocations)
        exit(1);
      IsSimple = false;
      return;
    }
    if (TargetAddress == 0 && opts::Verbosity >= 1) {
      outs() << "BOLT-INFO: PC-relative operand is zero in function " << *this
             << '\n';
    }

    const MCSymbol *TargetSymbol;
    uint64_t TargetOffset;
    std::tie(TargetSymbol, TargetOffset) =
        BC.handleAddressRef(TargetAddress, *this, /*IsPCRel*/ true);
    const MCExpr *Expr = MCSymbolRefExpr::create(
        TargetSymbol, MCSymbolRefExpr::VK_None, *BC.Ctx);
    if (TargetOffset) {
      const MCConstantExpr *Offset =
          MCConstantExpr::create(TargetOffset, *BC.Ctx);
      Expr = MCBinaryExpr::createAdd(Expr, Offset, *BC.Ctx);
    }
    MIB->replaceMemOperandDisp(Instruction,
                               MCOperand::createExpr(BC.MIB->getTargetExprFor(
                                   Instruction, Expr, *BC.Ctx, 0)));
  };

  // Used to fix the target of linker-generated AArch64 stubs with no relocation
  // info
  auto fixStubTarget = [&](MCInst &LoadLowBits, MCInst &LoadHiBits,
                           uint64_t Target) {
    const MCSymbol *TargetSymbol;
    uint64_t Addend = 0;
    std::tie(TargetSymbol, Addend) = BC.handleAddressRef(Target, *this, true);

    int64_t Val;
    MIB->replaceImmWithSymbolRef(LoadHiBits, TargetSymbol, Addend, Ctx.get(),
                                 Val, ELF::R_AARCH64_ADR_PREL_PG_HI21);
    MIB->replaceImmWithSymbolRef(LoadLowBits, TargetSymbol, Addend, Ctx.get(),
                                 Val, ELF::R_AARCH64_ADD_ABS_LO12_NC);
  };

  auto handleExternalReference = [&](MCInst &Instruction, uint64_t Size,
                                     uint64_t Offset, uint64_t TargetAddress,
                                     bool &IsCall) -> MCSymbol * {
    const bool IsCondBranch = MIB->isConditionalBranch(Instruction);
    const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
    MCSymbol *TargetSymbol = nullptr;
    InterproceduralReferences.insert(TargetAddress);
    if (opts::Verbosity >= 2 && !IsCall && Size == 2 && !BC.HasRelocations) {
      errs() << "BOLT-WARNING: relaxed tail call detected at 0x"
             << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this
             << ". Code size will be increased.\n";
    }

    assert(!MIB->isTailCall(Instruction) &&
           "synthetic tail call instruction found");

    // This is a call regardless of the opcode.
    // Assign proper opcode for tail calls, so that they could be
    // treated as calls.
    if (!IsCall) {
      if (!MIB->convertJmpToTailCall(Instruction)) {
        assert(IsCondBranch && "unknown tail call instruction");
        if (opts::Verbosity >= 2) {
          errs() << "BOLT-WARNING: conditional tail call detected in "
                 << "function " << *this << " at 0x"
                 << Twine::utohexstr(AbsoluteInstrAddr) << ".\n";
        }
      }
      IsCall = true;
    }

    TargetSymbol = BC.getOrCreateGlobalSymbol(TargetAddress, "FUNCat");
    if (opts::Verbosity >= 2 && TargetAddress == 0) {
      // We actually see calls to address 0 in presence of weak
      // symbols originating from libraries. This code is never meant
      // to be executed.
      outs() << "BOLT-INFO: Function " << *this
             << " has a call to address zero.\n";
    }

    return TargetSymbol;
  };

  auto handleIndirectBranch = [&](MCInst &Instruction, uint64_t Size,
                                  uint64_t Offset) {
    uint64_t IndirectTarget = 0;
    IndirectBranchType Result =
        processIndirectBranch(Instruction, Size, Offset, IndirectTarget);
    switch (Result) {
    default:
      llvm_unreachable("unexpected result");
    case IndirectBranchType::POSSIBLE_TAIL_CALL: {
      bool Result = MIB->convertJmpToTailCall(Instruction);
      (void)Result;
      assert(Result);
      break;
    }
    case IndirectBranchType::POSSIBLE_JUMP_TABLE:
    case IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE:
      if (opts::JumpTables == JTS_NONE)
        IsSimple = false;
      break;
    case IndirectBranchType::POSSIBLE_FIXED_BRANCH: {
      if (containsAddress(IndirectTarget)) {
        const MCSymbol *TargetSymbol = getOrCreateLocalLabel(IndirectTarget);
        Instruction.clear();
        MIB->createUncondBranch(Instruction, TargetSymbol, BC.Ctx.get());
        TakenBranches.emplace_back(Offset, IndirectTarget - getAddress());
        HasFixedIndirectBranch = true;
      } else {
        MIB->convertJmpToTailCall(Instruction);
        InterproceduralReferences.insert(IndirectTarget);
      }
      break;
    }
    case IndirectBranchType::UNKNOWN:
      // Keep processing. We'll do more checks and fixes in
      // postProcessIndirectBranches().
      UnknownIndirectBranchOffsets.emplace(Offset);
      break;
    }
  };

  // Check for linker veneers, which lack relocations and need manual
  // adjustments.
  auto handleAArch64IndirectCall = [&](MCInst &Instruction, uint64_t Offset) {
    const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
    MCInst *TargetHiBits, *TargetLowBits;
    uint64_t TargetAddress;
    if (MIB->matchLinkerVeneer(Instructions.begin(), Instructions.end(),
                               AbsoluteInstrAddr, Instruction, TargetHiBits,
                               TargetLowBits, TargetAddress)) {
      MIB->addAnnotation(Instruction, "AArch64Veneer", true);

      uint8_t Counter = 0;
      for (auto It = std::prev(Instructions.end()); Counter != 2;
           --It, ++Counter) {
        MIB->addAnnotation(It->second, "AArch64Veneer", true);
      }

      fixStubTarget(*TargetLowBits, *TargetHiBits, TargetAddress);
    }
  };

  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.DisAsm->getInstruction(Instruction, Size,
                                   FunctionData.slice(Offset),
                                   AbsoluteInstrAddr, nulls())) {
      // Functions with "soft" boundaries, e.g. coming from assembly source,
      // can have 0-byte padding at the end.
      if (isZeroPaddingAt(Offset))
        break;

      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.validateEncoding(Instruction, FunctionData.slice(Offset, Size))) {
        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) {
        setTrapOnEntry();
        BC.TrappedFunctions.push_back(this);
        break;
      }

      // Check if our disassembly is correct and matches the assembler output.
      if (!BC.validateEncoding(Instruction, FunctionData.slice(Offset, Size))) {
        if (opts::Verbosity >= 1) {
          errs() << "BOLT-WARNING: internal assembler/disassembler error "
                    "detected for AVX512 instruction:\n";
          BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr);
          errs() << " in function " << *this << '\n';
        }

        setIgnored();
        break;
      }
    }

    // Check if there's a relocation associated with this instruction.
    bool UsedReloc = false;
    for (auto Itr = Relocations.lower_bound(Offset),
              ItrE = Relocations.lower_bound(Offset + Size);
         Itr != ItrE; ++Itr) {
      const Relocation &Relocation = Itr->second;

      LLVM_DEBUG(dbgs() << "BOLT-DEBUG: replacing immediate 0x"
                        << Twine::utohexstr(Relocation.Value)
                        << " with relocation"
                           " against "
                        << Relocation.Symbol << "+" << Relocation.Addend
                        << " in function " << *this
                        << " for instruction at offset 0x"
                        << Twine::utohexstr(Offset) << '\n');

      // Process reference to the primary symbol.
      if (!Relocation.isPCRelative())
        BC.handleAddressRef(Relocation.Value - Relocation.Addend, *this,
                            /*IsPCRel*/ false);

      int64_t Value = Relocation.Value;
      const bool Result = BC.MIB->replaceImmWithSymbolRef(
          Instruction, Relocation.Symbol, Relocation.Addend, Ctx.get(), Value,
          Relocation.Type);
      (void)Result;
      assert(Result && "cannot replace immediate with relocation");

      // For aarch, if we replaced an immediate with a symbol from a
      // relocation, we mark it so we do not try to further process a
      // pc-relative operand. All we need is the symbol.
      if (BC.isAArch64())
        UsedReloc = true;

      // Make sure we replaced the correct immediate (instruction
      // can have multiple immediate operands).
      if (BC.isX86()) {
        assert(truncateToSize(static_cast<uint64_t>(Value),
                              Relocation::getSizeForType(Relocation.Type)) ==
                   truncateToSize(Relocation.Value, Relocation::getSizeForType(
                                                        Relocation.Type)) &&
               "immediate value mismatch in function");
      }
    }

    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
        // or a recursive call.
        bool IsCall = MIB->isCall(Instruction);
        const bool IsCondBranch = MIB->isConditionalBranch(Instruction);
        MCSymbol *TargetSymbol = nullptr;

        if (BC.MIB->isUnsupportedBranch(Instruction.getOpcode())) {
          setIgnored();
          if (BinaryFunction *TargetFunc =
                  BC.getBinaryFunctionContainingAddress(TargetAddress))
            TargetFunc->setIgnored();
        }

        if (IsCall && containsAddress(TargetAddress)) {
          if (TargetAddress == getAddress()) {
            // Recursive call.
            TargetSymbol = getSymbol();
          } else {
            if (BC.isX86()) {
              // Dangerous old-style x86 PIC code. We may need to freeze this
              // function, so preserve the function as is for now.
              PreserveNops = true;
            } else {
              errs() << "BOLT-WARNING: internal call detected at 0x"
                     << Twine::utohexstr(AbsoluteInstrAddr) << " in function "
                     << *this << ". Skipping.\n";
              IsSimple = false;
            }
          }
        }

        if (!TargetSymbol) {
          // Create either local label or external symbol.
          if (containsAddress(TargetAddress)) {
            TargetSymbol = getOrCreateLocalLabel(TargetAddress);
          } else {
            if (TargetAddress == getAddress() + getSize() &&
                TargetAddress < getAddress() + getMaxSize()) {
              // Result of __builtin_unreachable().
              LLVM_DEBUG(dbgs() << "BOLT-DEBUG: jump past end detected at 0x"
                                << 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;
            }
            // May update Instruction and IsCall
            TargetSymbol = handleExternalReference(Instruction, Size, Offset,
                                                   TargetAddress, IsCall);
          }
        }

        if (!IsCall) {
          // Add taken branch info.
          TakenBranches.emplace_back(Offset, TargetAddress - getAddress());
        }
        BC.MIB->replaceBranchTarget(Instruction, TargetSymbol, &*Ctx);

        // Mark CTC.
        if (IsCondBranch && IsCall)
          MIB->setConditionalTailCall(Instruction, TargetAddress);
      } else {
        // Could not evaluate branch. Should be an indirect call or an
        // indirect branch. Bail out on the latter case.
        if (MIB->isIndirectBranch(Instruction))
          handleIndirectBranch(Instruction, Size, Offset);
        // Indirect call. We only need to fix it if the operand is RIP-relative.
        if (IsSimple && MIB->hasPCRelOperand(Instruction))
          handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size);

        if (BC.isAArch64())
          handleAArch64IndirectCall(Instruction, Offset);
      }
    } else 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));
  }

  clearList(Relocations);

  if (!IsSimple) {
    clearList(Instructions);
    return false;
  }

  updateState(State::Disassembled);

  return true;
}

bool BinaryFunction::scanExternalRefs() {
  bool Success = true;
  bool DisassemblyFailed = false;

  // Ignore pseudo functions.
  if (isPseudo())
    return Success;

  if (opts::NoScan) {
    clearList(Relocations);
    clearList(ExternallyReferencedOffsets);

    return false;
  }

  // List of external references for this function.
  std::vector<Relocation> FunctionRelocations;

  static BinaryContext::IndependentCodeEmitter Emitter =
      BC.createIndependentMCCodeEmitter();

  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");

  uint64_t Size = 0; // instruction size
  for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
    // Check for data inside code and ignore it
    if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) {
      Size = DataInCodeSize;
      continue;
    }

    const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
    MCInst Instruction;
    if (!BC.DisAsm->getInstruction(Instruction, Size,
                                   FunctionData.slice(Offset),
                                   AbsoluteInstrAddr, nulls())) {
      if (opts::Verbosity >= 1 && !isZeroPaddingAt(Offset)) {
        errs() << "BOLT-WARNING: unable to disassemble instruction at offset 0x"
               << Twine::utohexstr(Offset) << " (address 0x"
               << Twine::utohexstr(AbsoluteInstrAddr) << ") in function "
               << *this << '\n';
      }
      Success = false;
      DisassemblyFailed = true;
      break;
    }

    // Return true if we can skip handling the Target function reference.
    auto ignoreFunctionRef = [&](const BinaryFunction &Target) {
      if (&Target == this)
        return true;

      // Note that later we may decide not to emit Target function. In that
      // case, we conservatively create references that will be ignored or
      // resolved to the same function.
      if (!BC.shouldEmit(Target))
        return true;

      return false;
    };

    // Return true if we can ignore reference to the symbol.
    auto ignoreReference = [&](const MCSymbol *TargetSymbol) {
      if (!TargetSymbol)
        return true;

      if (BC.forceSymbolRelocations(TargetSymbol->getName()))
        return false;

      BinaryFunction *TargetFunction = BC.getFunctionForSymbol(TargetSymbol);
      if (!TargetFunction)
        return true;

      return ignoreFunctionRef(*TargetFunction);
    };

    // Detect if the instruction references an address.
    // Without relocations, we can only trust PC-relative address modes.
    uint64_t TargetAddress = 0;
    bool IsPCRel = false;
    bool IsBranch = false;
    if (BC.MIB->hasPCRelOperand(Instruction)) {
      if (BC.MIB->evaluateMemOperandTarget(Instruction, TargetAddress,
                                           AbsoluteInstrAddr, Size)) {
        IsPCRel = true;
      }
    } else if (BC.MIB->isCall(Instruction) || BC.MIB->isBranch(Instruction)) {
      if (BC.MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size,
                                 TargetAddress)) {
        IsBranch = true;
      }
    }

    MCSymbol *TargetSymbol = nullptr;

    // Create an entry point at reference address if needed.
    BinaryFunction *TargetFunction =
        BC.getBinaryFunctionContainingAddress(TargetAddress);
    if (TargetFunction && !ignoreFunctionRef(*TargetFunction)) {
      const uint64_t FunctionOffset =
          TargetAddress - TargetFunction->getAddress();
      TargetSymbol = FunctionOffset
                         ? TargetFunction->addEntryPointAtOffset(FunctionOffset)
                         : TargetFunction->getSymbol();
    }

    // Can't find more references and not creating relocations.
    if (!BC.HasRelocations)
      continue;

    // Create a relocation against the TargetSymbol as the symbol might get
    // moved.
    if (TargetSymbol) {
      if (IsBranch) {
        BC.MIB->replaceBranchTarget(Instruction, TargetSymbol,
                                    Emitter.LocalCtx.get());
      } else if (IsPCRel) {
        const MCExpr *Expr = MCSymbolRefExpr::create(
            TargetSymbol, MCSymbolRefExpr::VK_None, *Emitter.LocalCtx.get());
        BC.MIB->replaceMemOperandDisp(
            Instruction, MCOperand::createExpr(BC.MIB->getTargetExprFor(
                             Instruction, Expr, *Emitter.LocalCtx.get(), 0)));
      }
    }

    // Create more relocations based on input file relocations.
    bool HasRel = false;
    for (auto Itr = Relocations.lower_bound(Offset),
              ItrE = Relocations.lower_bound(Offset + Size);
         Itr != ItrE; ++Itr) {
      Relocation &Relocation = Itr->second;
      if (ignoreReference(Relocation.Symbol))
        continue;

      int64_t Value = Relocation.Value;
      const bool Result = BC.MIB->replaceImmWithSymbolRef(
          Instruction, Relocation.Symbol, Relocation.Addend,
          Emitter.LocalCtx.get(), Value, Relocation.Type);
      (void)Result;
      assert(Result && "cannot replace immediate with relocation");

      HasRel = true;
    }

    if (!TargetSymbol && !HasRel)
      continue;

    // Emit the instruction using temp emitter and generate relocations.
    SmallString<256> Code;
    SmallVector<MCFixup, 4> Fixups;
    raw_svector_ostream VecOS(Code);
    Emitter.MCE->encodeInstruction(Instruction, VecOS, Fixups, *BC.STI);

    // Create relocation for every fixup.
    for (const MCFixup &Fixup : Fixups) {
      Optional<Relocation> Rel = BC.MIB->createRelocation(Fixup, *BC.MAB);
      if (!Rel) {
        Success = false;
        continue;
      }

      if (Relocation::getSizeForType(Rel->Type) < 4) {
        // If the instruction uses a short form, then we might not be able
        // to handle the rewrite without relaxation, and hence cannot reliably
        // create an external reference relocation.
        Success = false;
        continue;
      }
      Rel->Offset += getAddress() - getOriginSection()->getAddress() + Offset;
      FunctionRelocations.push_back(*Rel);
    }

    if (!Success)
      break;
  }

  // Add relocations unless disassembly failed for this function.
  if (!DisassemblyFailed)
    for (Relocation &Rel : FunctionRelocations)
      getOriginSection()->addPendingRelocation(Rel);

  // Inform BinaryContext that this function symbols will not be defined and
  // relocations should not be created against them.
  if (BC.HasRelocations) {
    for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
      BC.UndefinedSymbols.insert(LI.second);
    if (FunctionEndLabel)
      BC.UndefinedSymbols.insert(FunctionEndLabel);
  }

  clearList(Relocations);
  clearList(ExternallyReferencedOffsets);

  if (Success && BC.HasRelocations)
    HasExternalRefRelocations = true;

  if (opts::Verbosity >= 1 && !Success)
    outs() << "BOLT-INFO: failed to scan refs for  " << *this << '\n';

  return Success;
}

void BinaryFunction::postProcessEntryPoints() {
  if (!isSimple())
    return;

  for (auto &KV : Labels) {
    MCSymbol *Label = KV.second;
    if (!getSecondaryEntryPointSymbol(Label))
      continue;

    // In non-relocation mode there's potentially an external undetectable
    // reference to the entry point and hence we cannot move this entry
    // point. Optimizing without moving could be difficult.
    if (!BC.HasRelocations)
      setSimple(false);

    const uint32_t Offset = KV.first;

    // If we are at Offset 0 and there is no instruction associated with it,
    // this means this is an empty function. Just ignore. If we find an
    // instruction at this offset, this entry point is valid.
    if (!Offset || getInstructionAtOffset(Offset))
      continue;

    // On AArch64 there are legitimate reasons to have references past the
    // end of the function, e.g. jump tables.
    if (BC.isAArch64() && Offset == getSize())
      continue;

    errs() << "BOLT-WARNING: reference in the middle of instruction "
              "detected in function "
           << *this << " at offset 0x" << Twine::utohexstr(Offset) << '\n';
    if (BC.HasRelocations)
      setIgnored();
    setSimple(false);
    return;
  }
}

void BinaryFunction::postProcessJumpTables() {
  // Create labels for all entries.
  for (auto &JTI : JumpTables) {
    JumpTable &JT = *JTI.second;
    if (JT.Type == JumpTable::JTT_PIC && opts::JumpTables == JTS_BASIC) {
      opts::JumpTables = JTS_MOVE;
      outs() << "BOLT-INFO: forcing -jump-tables=move as PIC jump table was "
                "detected in function "
             << *this << '\n';
    }
    for (unsigned I = 0; I < JT.OffsetEntries.size(); ++I) {
      MCSymbol *Label =
          getOrCreateLocalLabel(getAddress() + JT.OffsetEntries[I],
                                /*CreatePastEnd*/ true);
      JT.Entries.push_back(Label);
    }

    const uint64_t BDSize =
        BC.getBinaryDataAtAddress(JT.getAddress())->getSize();
    if (!BDSize) {
      BC.setBinaryDataSize(JT.getAddress(), JT.getSize());
    } else {
      assert(BDSize >= JT.getSize() &&
             "jump table cannot be larger than the containing object");
    }
  }

  // Add TakenBranches from JumpTables.
  //
  // We want to do it after initial processing since we don't know jump tables'
  // boundaries until we process them all.
  for (auto &JTSite : JTSites) {
    const uint64_t JTSiteOffset = JTSite.first;
    const uint64_t JTAddress = JTSite.second;
    const JumpTable *JT = getJumpTableContainingAddress(JTAddress);
    assert(JT && "cannot find jump table for address");

    uint64_t EntryOffset = JTAddress - JT->getAddress();
    while (EntryOffset < JT->getSize()) {
      uint64_t TargetOffset = JT->OffsetEntries[EntryOffset / JT->EntrySize];
      if (TargetOffset < getSize()) {
        TakenBranches.emplace_back(JTSiteOffset, TargetOffset);

        if (opts::StrictMode)
          registerReferencedOffset(TargetOffset);
      }

      EntryOffset += JT->EntrySize;

      // A label at the next entry means the end of this jump table.
      if (JT->Labels.count(EntryOffset))
        break;
    }
  }
  clearList(JTSites);

  // Free memory used by jump table offsets.
  for (auto &JTI : JumpTables) {
    JumpTable &JT = *JTI.second;
    clearList(JT.OffsetEntries);
  }

  // Conservatively populate all possible destinations for unknown indirect
  // branches.
  if (opts::StrictMode && hasInternalReference()) {
    for (uint64_t Offset : UnknownIndirectBranchOffsets) {
      for (uint64_t PossibleDestination : ExternallyReferencedOffsets) {
        // Ignore __builtin_unreachable().
        if (PossibleDestination == getSize())
          continue;
        TakenBranches.emplace_back(Offset, PossibleDestination);
      }
    }
  }

  // Remove duplicates branches. We can get a bunch of them from jump tables.
  // Without doing jump table value profiling we don't have use for extra
  // (duplicate) branches.
  std::sort(TakenBranches.begin(), TakenBranches.end());
  auto NewEnd = std::unique(TakenBranches.begin(), TakenBranches.end());
  TakenBranches.erase(NewEnd, TakenBranches.end());
}

bool BinaryFunction::postProcessIndirectBranches(
    MCPlusBuilder::AllocatorIdTy AllocId) {
  auto addUnknownControlFlow = [&](BinaryBasicBlock &BB) {
    HasUnknownControlFlow = true;
    BB.removeAllSuccessors();
    for (uint64_t PossibleDestination : ExternallyReferencedOffsets)
      if (BinaryBasicBlock *SuccBB = getBasicBlockAtOffset(PossibleDestination))
        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 : layout()) {
    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 (layout_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.
      if (BC.MIB->isTailCall(Instr) || BC.MIB->getJumpTable(Instr)) {
        const unsigned PtrSize = BC.AsmInfo->getCodePointerSize();
        MCInst *MemLocInstr;
        unsigned BaseRegNum, IndexRegNum;
        int64_t DispValue;
        const MCExpr *DispExpr;
        MCInst *PCRelBaseInstr;
        IndirectBranchType Type = BC.MIB->analyzeIndirectBranch(
            Instr, BB->begin(), BB->end(), PtrSize, MemLocInstr, BaseRegNum,
            IndexRegNum, DispValue, DispExpr, PCRelBaseInstr);
        if (Type != IndirectBranchType::UNKNOWN || MemLocInstr != nullptr)
          continue;

        if (!opts::StrictMode)
          return false;

        if (BC.MIB->isTailCall(Instr)) {
          BC.MIB->convertTailCallToJmp(Instr);
        } else {
          LastIndirectJump = &Instr;
          LastIndirectJumpBB = BB;
          LastJT = BC.MIB->getJumpTable(Instr);
          LastJTIndexReg = BC.MIB->getJumpTableIndexReg(Instr);
          BC.MIB->unsetJumpTable(Instr);

          JumpTable *JT = BC.getJumpTableContainingAddress(LastJT);
          if (JT->Type == JumpTable::JTT_NORMAL) {
            // Invalidating the jump table may also invalidate other jump table
            // boundaries. Until we have/need a support for this, mark the
            // function as non-simple.
            LLVM_DEBUG(dbgs() << "BOLT-DEBUG: rejected jump table reference"
                              << JT->getName() << " in " << *this << '\n');
            return false;
          }
        }

        addUnknownControlFlow(*BB);
        continue;
      }

      // If this block contains an epilogue code and has an indirect branch,
      // then most likely it's a tail call. Otherwise, we cannot tell for sure
      // what it is and conservatively reject the function's CFG.
      bool IsEpilogue = false;
      for (const MCInst &Instr : *BB) {
        if (BC.MIB->isLeave(Instr) || BC.MIB->isPop(Instr)) {
          IsEpilogue = true;
          break;
        }
      }
      if (IsEpilogue) {
        BC.MIB->convertJmpToTailCall(Instr);
        BB->removeAllSuccessors();
        continue;
      }

      if (opts::Verbosity >= 2) {
        outs() << "BOLT-INFO: rejected potential indirect tail call in "
               << "function " << *this << " in basic block " << BB->getName()
               << ".\n";
        LLVM_DEBUG(BC.printInstructions(dbgs(), BB->begin(), BB->end(),
                                        BB->getOffset(), this, true));
      }

      if (!opts::StrictMode)
        return false;

      addUnknownControlFlow(*BB);
    }
  }

  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;

    // re-populate successors based on the jump table.
    std::set<const MCSymbol *> JTLabels;
    LastIndirectJumpBB->removeAllSuccessors();
    const JumpTable *JT = getJumpTableContainingAddress(LastJT);
    for (const MCSymbol *Label : JT->Entries)
      JTLabels.emplace(Label);
    for (const MCSymbol *Label : JTLabels) {
      BinaryBasicBlock *BB = getBasicBlockForLabel(Label);
      // Ignore __builtin_unreachable()
      if (!BB) {
        assert(Label == getFunctionEndLabel() && "if no BB found, must be end");
        continue;
      }
      LastIndirectJumpBB->addSuccessor(BB);
    }
  }

  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;
  }

  if (CurrentState != State::Disassembled)
    return false;

  assert(BasicBlocks.empty() && "basic block list should be empty");
  assert((Labels.find(0) != Labels.end()) &&
         "first instruction should always have a label");

  // Create basic blocks in the original layout order:
  //
  //  * Every instruction with associated label marks
  //    the beginning of a basic block.
  //  * Conditional instruction marks the end of a basic block,
  //    except when the following instruction is an
  //    unconditional branch, and the unconditional branch is not
  //    a destination of another branch. In the latter case, the
  //    basic block will consist of a single unconditional branch
  //    (missed "double-jump" optimization).
  //
  // Created basic blocks are sorted in layout order since they are
  // created in the same order as instructions, and instructions are
  // sorted by offsets.
  BinaryBasicBlock *InsertBB = nullptr;
  BinaryBasicBlock *PrevBB = nullptr;
  bool IsLastInstrNop = false;
  // Offset of the last non-nop instruction.
  uint64_t LastInstrOffset = 0;

  auto addCFIPlaceholders = [this](uint64_t CFIOffset,
                                   BinaryBasicBlock *InsertBB) {
    for (auto FI = OffsetToCFI.lower_bound(CFIOffset),
              FE = OffsetToCFI.upper_bound(CFIOffset);
         FI != FE; ++FI) {
      addCFIPseudo(InsertBB, InsertBB->end(), FI->second);
    }
  };

  // For profiling purposes we need to save the offset of the last instruction
  // in the basic block.
  // NOTE: nops always have an Offset annotation. Annotate the last non-nop as
  //       older profiles ignored nops.
  auto updateOffset = [&](uint64_t Offset) {
    assert(PrevBB && PrevBB != InsertBB && "invalid previous block");
    MCInst *LastNonNop = nullptr;
    for (BinaryBasicBlock::reverse_iterator RII = PrevBB->getLastNonPseudo(),
                                            E = PrevBB->rend();
         RII != E; ++RII) {
      if (!BC.MIB->isPseudo(*RII) && !BC.MIB->isNoop(*RII)) {
        LastNonNop = &*RII;
        break;
      }
    }
    if (LastNonNop && !MIB->getOffset(*LastNonNop))
      MIB->setOffset(*LastNonNop, static_cast<uint32_t>(Offset), AllocatorId);
  };

  for (auto I = Instructions.begin(), E = Instructions.end(); I != E; ++I) {
    const uint32_t Offset = I->first;
    MCInst &Instr = I->second;

    auto LI = Labels.find(Offset);
    if (LI != Labels.end()) {
      // Always create new BB at branch destination.
      PrevBB = InsertBB ? InsertBB : PrevBB;
      InsertBB = addBasicBlock(LI->first, LI->second,
                               opts::PreserveBlocksAlignment && IsLastInstrNop);
      if (PrevBB)
        updateOffset(LastInstrOffset);
    }

    const uint64_t InstrInputAddr = I->first + Address;
    bool IsSDTMarker =
        MIB->isNoop(Instr) && BC.SDTMarkers.count(InstrInputAddr);
    bool IsLKMarker = BC.LKMarkers.count(InstrInputAddr);
    // Mark all nops with Offset for profile tracking purposes.
    if (MIB->isNoop(Instr) || IsLKMarker) {
      if (!MIB->getOffset(Instr))
        MIB->setOffset(Instr, static_cast<uint32_t>(Offset), AllocatorId);
      if (IsSDTMarker || IsLKMarker)
        HasSDTMarker = true;
      else
        // Annotate ordinary nops, so we can safely delete them if required.
        MIB->addAnnotation(Instr, "NOP", static_cast<uint32_t>(1), AllocatorId);
    }

    if (!InsertBB) {
      // It must be a fallthrough or unreachable code. Create a new block unless
      // we see an unconditional branch following a conditional one. The latter
      // should not be a conditional tail call.
      assert(PrevBB && "no previous basic block for a fall through");
      MCInst *PrevInstr = PrevBB->getLastNonPseudoInstr();
      assert(PrevInstr && "no previous instruction for a fall through");
      if (MIB->isUnconditionalBranch(Instr) &&
          !MIB->isUnconditionalBranch(*PrevInstr) &&
          !MIB->getConditionalTailCall(*PrevInstr)) {
        // Temporarily restore inserter basic block.
        InsertBB = PrevBB;
      } else {
        MCSymbol *Label;
        {
          auto L = BC.scopeLock();
          Label = BC.Ctx->createNamedTempSymbol("FT");
        }
        InsertBB = addBasicBlock(
            Offset, Label, opts::PreserveBlocksAlignment && IsLastInstrNop);
        updateOffset(LastInstrOffset);
      }
    }
    if (Offset == 0) {
      // Add associated CFI pseudos in the first offset (0)
      addCFIPlaceholders(0, InsertBB);
    }

    const bool IsBlockEnd = MIB->isTerminator(Instr);
    IsLastInstrNop = MIB->isNoop(Instr);
    if (!IsLastInstrNop)
      LastInstrOffset = Offset;
    InsertBB->addInstruction(std::move(Instr));

    // Add associated CFI instrs. We always add the CFI instruction that is
    // located immediately after this instruction, since the next CFI
    // instruction reflects the change in state caused by this instruction.
    auto NextInstr = std::next(I);
    uint64_t CFIOffset;
    if (NextInstr != E)
      CFIOffset = NextInstr->first;
    else
      CFIOffset = getSize();

    // Note: this potentially invalidates instruction pointers/iterators.
    addCFIPlaceholders(CFIOffset, InsertBB);

    if (IsBlockEnd) {
      PrevBB = InsertBB;
      InsertBB = nullptr;
    }
  }

  if (BasicBlocks.empty()) {
    setSimple(false);
    return false;
  }

  // Intermediate dump.
  LLVM_DEBUG(print(dbgs(), "after creating basic blocks"));

  // TODO: handle properly calls to no-return functions,
  // e.g. exit(3), etc. Otherwise we'll see a false fall-through
  // blocks.

  for (std::pair<uint32_t, uint32_t> &Branch : TakenBranches) {
    LLVM_DEBUG(dbgs() << "registering branch [0x"
                      << Twine::utohexstr(Branch.first) << "] -> [0x"
                      << Twine::utohexstr(Branch.second) << "]\n");
    BinaryBasicBlock *FromBB = getBasicBlockContainingOffset(Branch.first);
    BinaryBasicBlock *ToBB = getBasicBlockAtOffset(Branch.second);
    if (!FromBB || !ToBB) {
      if (!FromBB)
        errs() << "BOLT-ERROR: cannot find BB containing the branch.\n";
      if (!ToBB)
        errs() << "BOLT-ERROR: cannot find BB containing branch destination.\n";
      BC.exitWithBugReport("disassembly failed - inconsistent branch found.",
                           *this);
    }

    FromBB->addSuccessor(ToBB);
  }

  // Add fall-through branches.
  PrevBB = nullptr;
  bool IsPrevFT = false; // Is previous block a fall-through.
  for (BinaryBasicBlock *BB : BasicBlocks) {
    if (IsPrevFT)
      PrevBB->addSuccessor(BB);

    if (BB->empty()) {
      IsPrevFT = true;
      PrevBB = BB;
      continue;
    }

    MCInst *LastInstr = BB->getLastNonPseudoInstr();
    assert(LastInstr &&
           "should have non-pseudo instruction in non-empty block");

    if (BB->succ_size() == 0) {
      // Since there's no existing successors, we know the last instruction is
      // not a conditional branch. Thus if it's a terminator, it shouldn't be a
      // fall-through.
      //
      // Conditional tail call is a special case since we don't add a taken
      // branch successor for it.
      IsPrevFT = !MIB->isTerminator(*LastInstr) ||
                 MIB->getConditionalTailCall(*LastInstr);
    } else if (BB->succ_size() == 1) {
      IsPrevFT = MIB->isConditionalBranch(*LastInstr);
    } else {
      IsPrevFT = false;
    }

    PrevBB = BB;
  }

  // Assign landing pads and throwers info.
  recomputeLandingPads();

  // Assign CFI information to each BB entry.
  annotateCFIState();

  // Annotate invoke instructions with GNU_args_size data.
  propagateGnuArgsSizeInfo(AllocatorId);

  // Set the basic block layout to the original order and set end offsets.
  PrevBB = nullptr;
  for (BinaryBasicBlock *BB : BasicBlocks) {
    BasicBlocksLayout.emplace_back(BB);
    if (PrevBB)
      PrevBB->setEndOffset(BB->getOffset());
    PrevBB = BB;
  }
  PrevBB->setEndOffset(getSize());

  updateLayoutIndices();

  normalizeCFIState();

  // Clean-up memory taken by intermediate structures.
  //
  // NB: don't clear Labels list as we may need them if we mark the function
  //     as non-simple later in the process of discovering extra entry points.
  clearList(Instructions);
  clearList(OffsetToCFI);
  clearList(TakenBranches);

  // Update the state.
  CurrentState = State::CFG;

  // Make any necessary adjustments for indirect branches.
  if (!postProcessIndirectBranches(AllocatorId)) {
    if (opts::Verbosity) {
      errs() << "BOLT-WARNING: failed to post-process indirect branches for "
             << *this << '\n';
    }
    // In relocation mode we want to keep processing the function but avoid
    // optimizing it.
    setSimple(false);
  }

  clearList(ExternallyReferencedOffsets);
  clearList(UnknownIndirectBranchOffsets);

  return true;
}

void BinaryFunction::postProcessCFG() {
  if (isSimple() && !BasicBlocks.empty()) {
    // Convert conditional tail call branches to conditional branches that jump
    // to a tail call.
    removeConditionalTailCalls();

    postProcessProfile();

    // Eliminate inconsistencies between branch instructions and CFG.
    postProcessBranches();
  }

  calculateMacroOpFusionStats();

  // The final cleanup of intermediate structures.
  clearList(IgnoredBranches);

  // Remove "Offset" annotations, unless we need an address-translation table
  // later. This has no cost, since annotations are allocated by a bumpptr
  // allocator and won't be released anyway until late in the pipeline.
  if (!requiresAddressTranslation() && !opts::Instrument) {
    for (BinaryBasicBlock *BB : layout())
      for (MCInst &Inst : *BB)
        BC.MIB->clearOffset(Inst);
  }

  assert((!isSimple() || validateCFG()) &&
         "invalid CFG detected after post-processing");
}

void BinaryFunction::calculateMacroOpFusionStats() {
  if (!getBinaryContext().isX86())
    return;
  for (BinaryBasicBlock *BB : layout()) {
    auto II = BB->getMacroOpFusionPair();
    if (II == BB->end())
      continue;

    // Check offset of the second instruction.
    // FIXME: arch-specific.
    const uint32_t Offset = BC.MIB->getOffsetWithDefault(*std::next(II), 0);
    if (!Offset || (getAddress() + Offset) % 64)
      continue;

    LLVM_DEBUG(dbgs() << "\nmissed macro-op fusion at address 0x"
                      << Twine::utohexstr(getAddress() + Offset)
                      << " in function " << *this << "; executed "
                      << BB->getKnownExecutionCount() << " times.\n");
    ++BC.MissedMacroFusionPairs;
    BC.MissedMacroFusionExecCount += BB->getKnownExecutionCount();
  }
}

void BinaryFunction::removeTagsFromProfile() {
  for (BinaryBasicBlock *BB : BasicBlocks) {
    if (BB->ExecutionCount == BinaryBasicBlock::COUNT_NO_PROFILE)
      BB->ExecutionCount = 0;
    for (BinaryBasicBlock::BinaryBranchInfo &BI : BB->branch_info()) {
      if (BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
          BI.MispredictedCount != BinaryBasicBlock::COUNT_NO_PROFILE)
        continue;
      BI.Count = 0;
      BI.MispredictedCount = 0;
    }
  }
}

void BinaryFunction::removeConditionalTailCalls() {
  // Blocks to be appended at the end.
  std::vector<std::unique_ptr<BinaryBasicBlock>> NewBlocks;

  for (auto BBI = begin(); BBI != end(); ++BBI) {
    BinaryBasicBlock &BB = *BBI;
    MCInst *CTCInstr = BB.getLastNonPseudoInstr();
    if (!CTCInstr)
      continue;

    Optional<uint64_t> TargetAddressOrNone =
        BC.MIB->getConditionalTailCall(*CTCInstr);
    if (!TargetAddressOrNone)
      continue;

    // Gather all necessary information about CTC instruction before
    // annotations are destroyed.
    const int32_t CFIStateBeforeCTC = BB.getCFIStateAtInstr(CTCInstr);
    uint64_t CTCTakenCount = BinaryBasicBlock::COUNT_NO_PROFILE;
    uint64_t CTCMispredCount = BinaryBasicBlock::COUNT_NO_PROFILE;
    if (hasValidProfile()) {
      CTCTakenCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
          *CTCInstr, "CTCTakenCount");
      CTCMispredCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
          *CTCInstr, "CTCMispredCount");
    }

    // Assert that the tail call does not throw.
    assert(!BC.MIB->getEHInfo(*CTCInstr) &&
           "found tail call with associated landing pad");

    // Create a basic block with an unconditional tail call instruction using
    // the same destination.
    const MCSymbol *CTCTargetLabel = BC.MIB->getTargetSymbol(*CTCInstr);
    assert(CTCTargetLabel && "symbol expected for conditional tail call");
    MCInst TailCallInstr;
    BC.MIB->createTailCall(TailCallInstr, CTCTargetLabel, BC.Ctx.get());
    // Link new BBs to the original input offset of the BB where the CTC
    // is, so we can map samples recorded in new BBs back to the original BB
    // seem in the input binary (if using BAT)
    std::unique_ptr<BinaryBasicBlock> TailCallBB = createBasicBlock(
        BB.getInputOffset(), BC.Ctx->createNamedTempSymbol("TC"));
    TailCallBB->addInstruction(TailCallInstr);
    TailCallBB->setCFIState(CFIStateBeforeCTC);

    // Add CFG edge with profile info from BB to TailCallBB.
    BB.addSuccessor(TailCallBB.get(), CTCTakenCount, CTCMispredCount);

    // Add execution count for the block.
    TailCallBB->setExecutionCount(CTCTakenCount);

    BC.MIB->convertTailCallToJmp(*CTCInstr);

    BC.MIB->replaceBranchTarget(*CTCInstr, TailCallBB->getLabel(),
                                BC.Ctx.get());

    // Add basic block to the list that will be added to the end.
    NewBlocks.emplace_back(std::move(TailCallBB));

    // Swap edges as the TailCallBB corresponds to the taken branch.
    BB.swapConditionalSuccessors();

    // This branch is no longer a conditional tail call.
    BC.MIB->unsetConditionalTailCall(*CTCInstr);
  }

  insertBasicBlocks(std::prev(end()), std::move(NewBlocks),
                    /* UpdateLayout */ true,
                    /* UpdateCFIState */ false);
}

uint64_t BinaryFunction::getFunctionScore() const {
  if (FunctionScore != -1)
    return FunctionScore;

  if (!isSimple() || !hasValidProfile()) {
    FunctionScore = 0;
    return FunctionScore;
  }

  uint64_t TotalScore = 0ULL;
  for (BinaryBasicBlock *BB : layout()) {
    uint64_t BBExecCount = BB->getExecutionCount();
    if (BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
      continue;
    TotalScore += BBExecCount;
  }
  FunctionScore = TotalScore;
  return FunctionScore;
}

void BinaryFunction::annotateCFIState() {
  assert(CurrentState == State::Disassembled && "unexpected function state");
  assert(!BasicBlocks.empty() && "basic block list should not be empty");

  // This is an index of the last processed CFI in FDE CFI program.
  uint32_t State = 0;

  // This is an index of RememberState CFI reflecting effective state right
  // after execution of RestoreState CFI.
  //
  // It differs from State iff the CFI at (State-1)
  // was RestoreState (modulo GNU_args_size CFIs, which are ignored).
  //
  // This allows us to generate shorter replay sequences when producing new
  // CFI programs.
  uint32_t EffectiveState = 0;

  // For tracking RememberState/RestoreState sequences.
  std::stack<uint32_t> StateStack;

  for (BinaryBasicBlock *BB : BasicBlocks) {
    BB->setCFIState(EffectiveState);

    for (const MCInst &Instr : *BB) {
      const MCCFIInstruction *CFI = getCFIFor(Instr);
      if (!CFI)
        continue;

      ++State;

      switch (CFI->getOperation()) {
      case MCCFIInstruction::OpRememberState:
        StateStack.push(EffectiveState);
        EffectiveState = State;
        break;
      case MCCFIInstruction::OpRestoreState:
        assert(!StateStack.empty() && "corrupt CFI stack");
        EffectiveState = StateStack.top();
        StateStack.pop();
        break;
      case MCCFIInstruction::OpGnuArgsSize:
        // OpGnuArgsSize CFIs do not affect the CFI state.
        break;
      default:
        // Any other CFI updates the state.
        EffectiveState = State;
        break;
      }
    }
  }

  assert(StateStack.empty() && "corrupt CFI stack");
}

namespace {

/// Our full interpretation of a DWARF CFI machine state at a given point
struct CFISnapshot {
  /// CFA register number and offset defining the canonical frame at this
  /// point, or the number of a rule (CFI state) that computes it with a
  /// DWARF expression. This number will be negative if it refers to a CFI
  /// located in the CIE instead of the FDE.
  uint32_t CFAReg;
  int32_t CFAOffset;
  int32_t CFARule;
  /// Mapping of rules (CFI states) that define the location of each
  /// register. If absent, no rule defining the location of such register
  /// was ever read. This number will be negative if it refers to a CFI
  /// located in the CIE instead of the FDE.
  DenseMap<int32_t, int32_t> RegRule;

  /// References to CIE, FDE and expanded instructions after a restore state
  const BinaryFunction::CFIInstrMapType &CIE;
  const BinaryFunction::CFIInstrMapType &FDE;
  const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents;

  /// Current FDE CFI number representing the state where the snapshot is at
  int32_t CurState;

  /// Used when we don't have information about which state/rule to apply
  /// to recover the location of either the CFA or a specific register
  constexpr static int32_t UNKNOWN = std::numeric_limits<int32_t>::min();

private:
  /// Update our snapshot by executing a single CFI
  void update(const MCCFIInstruction &Instr, int32_t RuleNumber) {
    switch (Instr.getOperation()) {
    case MCCFIInstruction::OpSameValue:
    case MCCFIInstruction::OpRelOffset:
    case MCCFIInstruction::OpOffset:
    case MCCFIInstruction::OpRestore:
    case MCCFIInstruction::OpUndefined:
    case MCCFIInstruction::OpRegister:
      RegRule[Instr.getRegister()] = RuleNumber;
      break;
    case MCCFIInstruction::OpDefCfaRegister:
      CFAReg = Instr.getRegister();
      CFARule = UNKNOWN;
      break;
    case MCCFIInstruction::OpDefCfaOffset:
      CFAOffset = Instr.getOffset();
      CFARule = UNKNOWN;
      break;
    case MCCFIInstruction::OpDefCfa:
      CFAReg = Instr.getRegister();
      CFAOffset = Instr.getOffset();
      CFARule = UNKNOWN;
      break;
    case MCCFIInstruction::OpEscape: {
      Optional<uint8_t> Reg = readDWARFExpressionTargetReg(Instr.getValues());
      // Handle DW_CFA_def_cfa_expression
      if (!Reg) {
        CFARule = RuleNumber;
        break;
      }
      RegRule[*Reg] = RuleNumber;
      break;
    }
    case MCCFIInstruction::OpAdjustCfaOffset:
    case MCCFIInstruction::OpWindowSave:
    case MCCFIInstruction::OpNegateRAState:
    case MCCFIInstruction::OpLLVMDefAspaceCfa:
      llvm_unreachable("unsupported CFI opcode");
      break;
    case MCCFIInstruction::OpRememberState:
    case MCCFIInstruction::OpRestoreState:
    case MCCFIInstruction::OpGnuArgsSize:
      // do not affect CFI state
      break;
    }
  }

public:
  /// Advance state reading FDE CFI instructions up to State number
  void advanceTo(int32_t State) {
    for (int32_t I = CurState, E = State; I != E; ++I) {
      const MCCFIInstruction &Instr = FDE[I];
      if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) {
        update(Instr, I);
        continue;
      }
      // If restore state instruction, fetch the equivalent CFIs that have
      // the same effect of this restore. This is used to ensure remember-
      // restore pairs are completely removed.
      auto Iter = FrameRestoreEquivalents.find(I);
      if (Iter == FrameRestoreEquivalents.end())
        continue;
      for (int32_t RuleNumber : Iter->second)
        update(FDE[RuleNumber], RuleNumber);
    }

    assert(((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) ||
            CFARule != UNKNOWN) &&
           "CIE did not define default CFA?");

    CurState = State;
  }

  /// Interpret all CIE and FDE instructions up until CFI State number and
  /// populate this snapshot
  CFISnapshot(
      const BinaryFunction::CFIInstrMapType &CIE,
      const BinaryFunction::CFIInstrMapType &FDE,
      const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents,
      int32_t State)
      : CIE(CIE), FDE(FDE), FrameRestoreEquivalents(FrameRestoreEquivalents) {
    CFAReg = UNKNOWN;
    CFAOffset = UNKNOWN;
    CFARule = UNKNOWN;
    CurState = 0;

    for (int32_t I = 0, E = CIE.size(); I != E; ++I) {
      const MCCFIInstruction &Instr = CIE[I];
      update(Instr, -I);
    }

    advanceTo(State);
  }
};

/// A CFI snapshot with the capability of checking if incremental additions to
/// it are redundant. This is used to ensure we do not emit two CFI instructions
/// back-to-back that are doing the same state change, or to avoid emitting a
/// CFI at all when the state at that point would not be modified after that CFI
struct CFISnapshotDiff : public CFISnapshot {
  bool RestoredCFAReg{false};
  bool RestoredCFAOffset{false};
  DenseMap<int32_t, bool> RestoredRegs;

  CFISnapshotDiff(const CFISnapshot &S) : CFISnapshot(S) {}

  CFISnapshotDiff(
      const BinaryFunction::CFIInstrMapType &CIE,
      const BinaryFunction::CFIInstrMapType &FDE,
      const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents,
      int32_t State)
      : CFISnapshot(CIE, FDE, FrameRestoreEquivalents, State) {}

  /// Return true if applying Instr to this state is redundant and can be
  /// dismissed.
  bool isRedundant(const MCCFIInstruction &Instr) {
    switch (Instr.getOperation()) {
    case MCCFIInstruction::OpSameValue:
    case MCCFIInstruction::OpRelOffset:
    case MCCFIInstruction::OpOffset:
    case MCCFIInstruction::OpRestore:
    case MCCFIInstruction::OpUndefined:
    case MCCFIInstruction::OpRegister:
    case MCCFIInstruction::OpEscape: {
      uint32_t Reg;
      if (Instr.getOperation() != MCCFIInstruction::OpEscape) {
        Reg = Instr.getRegister();
      } else {
        Optional<uint8_t> R = readDWARFExpressionTargetReg(Instr.getValues());
        // Handle DW_CFA_def_cfa_expression
        if (!R) {
          if (RestoredCFAReg && RestoredCFAOffset)
            return true;
          RestoredCFAReg = true;
          RestoredCFAOffset = true;
          return false;
        }
        Reg = *R;
      }
      if (RestoredRegs[Reg])
        return true;
      RestoredRegs[Reg] = true;
      const int32_t CurRegRule =
          RegRule.find(Reg) != RegRule.end() ? RegRule[Reg] : UNKNOWN;
      if (CurRegRule == UNKNOWN) {
        if (Instr.getOperation() == MCCFIInstruction::OpRestore ||
            Instr.getOperation() == MCCFIInstruction::OpSameValue)
          return true;
        return false;
      }
      const MCCFIInstruction &LastDef =
          CurRegRule < 0 ? CIE[-CurRegRule] : FDE[CurRegRule];
      return LastDef == Instr;
    }
    case MCCFIInstruction::OpDefCfaRegister:
      if (RestoredCFAReg)
        return true;
      RestoredCFAReg = true;
      return CFAReg == Instr.getRegister();
    case MCCFIInstruction::OpDefCfaOffset:
      if (RestoredCFAOffset)
        return true;
      RestoredCFAOffset = true;
      return CFAOffset == Instr.getOffset();
    case MCCFIInstruction::OpDefCfa:
      if (RestoredCFAReg && RestoredCFAOffset)
        return true;
      RestoredCFAReg = true;
      RestoredCFAOffset = true;
      return CFAReg == Instr.getRegister() && CFAOffset == Instr.getOffset();
    case MCCFIInstruction::OpAdjustCfaOffset:
    case MCCFIInstruction::OpWindowSave:
    case MCCFIInstruction::OpNegateRAState:
    case MCCFIInstruction::OpLLVMDefAspaceCfa:
      llvm_unreachable("unsupported CFI opcode");
      return false;
    case MCCFIInstruction::OpRememberState:
    case MCCFIInstruction::OpRestoreState:
    case MCCFIInstruction::OpGnuArgsSize:
      // do not affect CFI state
      return true;
    }
    return false;
  }
};

} // end anonymous namespace

bool BinaryFunction::replayCFIInstrs(int32_t FromState, int32_t ToState,
                                     BinaryBasicBlock *InBB,
                                     BinaryBasicBlock::iterator InsertIt) {
  if (FromState == ToState)
    return true;
  assert(FromState < ToState && "can only replay CFIs forward");

  CFISnapshotDiff CFIDiff(CIEFrameInstructions, FrameInstructions,
                          FrameRestoreEquivalents, FromState);

  std::vector<uint32_t> NewCFIs;
  for (int32_t CurState = FromState; CurState < ToState; ++CurState) {
    MCCFIInstruction *Instr = &FrameInstructions[CurState];
    if (Instr->getOperation() == MCCFIInstruction::OpRestoreState) {
      auto Iter = FrameRestoreEquivalents.find(CurState);
      assert(Iter != FrameRestoreEquivalents.end());
      NewCFIs.insert(NewCFIs.end(), Iter->second.begin(), Iter->second.end());
      // RestoreState / Remember will be filtered out later by CFISnapshotDiff,
      // so we might as well fall-through here.
    }
    NewCFIs.push_back(CurState);
    continue;
  }

  // Replay instructions while avoiding duplicates
  for (auto I = NewCFIs.rbegin(), E = NewCFIs.rend(); I != E; ++I) {
    if (CFIDiff.isRedundant(FrameInstructions[*I]))
      continue;
    InsertIt = addCFIPseudo(InBB, InsertIt, *I);
  }

  return true;
}

SmallVector<int32_t, 4>
BinaryFunction::unwindCFIState(int32_t FromState, int32_t ToState,
                               BinaryBasicBlock *InBB,
                               BinaryBasicBlock::iterator &InsertIt) {
  SmallVector<int32_t, 4> NewStates;

  CFISnapshot ToCFITable(CIEFrameInstructions, FrameInstructions,
                         FrameRestoreEquivalents, ToState);
  CFISnapshotDiff FromCFITable(ToCFITable);
  FromCFITable.advanceTo(FromState);

  auto undoStateDefCfa = [&]() {
    if (ToCFITable.CFARule == CFISnapshot::UNKNOWN) {
      FrameInstructions.emplace_back(MCCFIInstruction::cfiDefCfa(
          nullptr, ToCFITable.CFAReg, ToCFITable.CFAOffset));
      if (FromCFITable.isRedundant(FrameInstructions.back())) {
        FrameInstructions.pop_back();
        return;
      }
      NewStates.push_back(FrameInstructions.size() - 1);
      InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size() - 1);
      ++InsertIt;
    } else if (ToCFITable.CFARule < 0) {
      if (FromCFITable.isRedundant(CIEFrameInstructions[-ToCFITable.CFARule]))
        return;
      NewStates.push_back(FrameInstructions.size());
      InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size());
      ++InsertIt;
      FrameInstructions.emplace_back(CIEFrameInstructions[-ToCFITable.CFARule]);
    } else if (!FromCFITable.isRedundant(
                   FrameInstructions[ToCFITable.CFARule])) {
      NewStates.push_back(ToCFITable.CFARule);
      InsertIt = addCFIPseudo(InBB, InsertIt, ToCFITable.CFARule);
      ++InsertIt;
    }
  };

  auto undoState = [&](const MCCFIInstruction &Instr) {
    switch (Instr.getOperation()) {
    case MCCFIInstruction::OpRememberState:
    case MCCFIInstruction::OpRestoreState:
      break;
    case MCCFIInstruction::OpSameValue:
    case MCCFIInstruction::OpRelOffset:
    case MCCFIInstruction::OpOffset:
    case MCCFIInstruction::OpRestore:
    case MCCFIInstruction::OpUndefined:
    case MCCFIInstruction::OpEscape:
    case MCCFIInstruction::OpRegister: {
      uint32_t Reg;
      if (Instr.getOperation() != MCCFIInstruction::OpEscape) {
        Reg = Instr.getRegister();
      } else {
        Optional<uint8_t> R = readDWARFExpressionTargetReg(Instr.getValues());
        // Handle DW_CFA_def_cfa_expression
        if (!R) {
          undoStateDefCfa();
          return;
        }
        Reg = *R;
      }

      if (ToCFITable.RegRule.find(Reg) == ToCFITable.RegRule.end()) {
        FrameInstructions.emplace_back(
            MCCFIInstruction::createRestore(nullptr, Reg));
        if (FromCFITable.isRedundant(FrameInstructions.back())) {
          FrameInstructions.pop_back();
          break;
        }
        NewStates.push_back(FrameInstructions.size() - 1);
        InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size() - 1);
        ++InsertIt;
        break;
      }
      const int32_t Rule = ToCFITable.RegRule[Reg];
      if (Rule < 0) {
        if (FromCFITable.isRedundant(CIEFrameInstructions[-Rule]))
          break;
        NewStates.push_back(FrameInstructions.size());
        InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size());
        ++InsertIt;
        FrameInstructions.emplace_back(CIEFrameInstructions[-Rule]);
        break;
      }
      if (FromCFITable.isRedundant(FrameInstructions[Rule]))
        break;
      NewStates.push_back(Rule);
      InsertIt = addCFIPseudo(InBB, InsertIt, Rule);
      ++InsertIt;
      break;
    }
    case MCCFIInstruction::OpDefCfaRegister:
    case MCCFIInstruction::OpDefCfaOffset:
    case MCCFIInstruction::OpDefCfa:
      undoStateDefCfa();
      break;
    case MCCFIInstruction::OpAdjustCfaOffset:
    case MCCFIInstruction::OpWindowSave:
    case MCCFIInstruction::OpNegateRAState:
    case MCCFIInstruction::OpLLVMDefAspaceCfa:
      llvm_unreachable("unsupported CFI opcode");
      break;
    case MCCFIInstruction::OpGnuArgsSize:
      // do not affect CFI state
      break;
    }
  };

  // Undo all modifications from ToState to FromState
  for (int32_t I = ToState, E = FromState; I != E; ++I) {
    const MCCFIInstruction &Instr = FrameInstructions[I];
    if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) {
      undoState(Instr);
      continue;
    }
    auto Iter = FrameRestoreEquivalents.find(I);
    if (Iter == FrameRestoreEquivalents.end())
      continue;
    for (int32_t State : Iter->second)
      undoState(FrameInstructions[State]);
  }

  return NewStates;
}

void BinaryFunction::normalizeCFIState() {
  // Reordering blocks with remember-restore state instructions can be specially
  // tricky. When rewriting the CFI, we omit remember-restore state instructions
  // entirely. For restore state, we build a map expanding each restore to the
  // equivalent unwindCFIState sequence required at that point to achieve the
  // same effect of the restore. All remember state are then just ignored.
  std::stack<int32_t> Stack;
  for (BinaryBasicBlock *CurBB : BasicBlocksLayout) {
    for (auto II = CurBB->begin(); II != CurBB->end(); ++II) {
      if (const MCCFIInstruction *CFI = getCFIFor(*II)) {
        if (CFI->getOperation() == MCCFIInstruction::OpRememberState) {
          Stack.push(II->getOperand(0).getImm());
          continue;
        }
        if (CFI->getOperation() == MCCFIInstruction::OpRestoreState) {
          const int32_t RememberState = Stack.top();
          const int32_t CurState = II->getOperand(0).getImm();
          FrameRestoreEquivalents[CurState] =
              unwindCFIState(CurState, RememberState, CurBB, II);
          Stack.pop();
        }
      }
    }
  }
}

bool BinaryFunction::finalizeCFIState() {
  LLVM_DEBUG(
      dbgs() << "Trying to fix CFI states for each BB after reordering.\n");
  LLVM_DEBUG(dbgs() << "This is the list of CFI states for each BB of " << *this
                    << ": ");

  int32_t State = 0;
  bool SeenCold = false;
  const char *Sep = "";
  (void)Sep;
  for (BinaryBasicBlock *BB : BasicBlocksLayout) {
    const int32_t CFIStateAtExit = BB->getCFIStateAtExit();

    // Hot-cold border: check if this is the first BB to be allocated in a cold
    // region (with a different FDE). If yes, we need to reset the CFI state.
    if (!SeenCold && BB->isCold()) {
      State = 0;
      SeenCold = true;
    }

    // We need to recover the correct state if it doesn't match expected
    // state at BB entry point.
    if (BB->getCFIState() < State) {
      // In this case, State is currently higher than what this BB expect it
      // to be. To solve this, we need to insert CFI instructions to undo
      // the effect of all CFI from BB's state to current State.
      auto InsertIt = BB->begin();
      unwindCFIState(State, BB->getCFIState(), BB, InsertIt);
    } else if (BB->getCFIState() > State) {
      // If BB's CFI state is greater than State, it means we are behind in the
      // state. Just emit all instructions to reach this state at the
      // beginning of this BB. If this sequence of instructions involve
      // remember state or restore state, bail out.
      if (!replayCFIInstrs(State, BB->getCFIState(), BB, BB->begin()))
        return false;
    }

    State = CFIStateAtExit;
    LLVM_DEBUG(dbgs() << Sep << State; Sep = ", ");
  }
  LLVM_DEBUG(dbgs() << "\n");

  for (BinaryBasicBlock *BB : BasicBlocksLayout) {
    for (auto II = BB->begin(); II != BB->end();) {
      const MCCFIInstruction *CFI = getCFIFor(*II);
      if (CFI && (CFI->getOperation() == MCCFIInstruction::OpRememberState ||
                  CFI->getOperation() == MCCFIInstruction::OpRestoreState)) {
        II = BB->eraseInstruction(II);
      } else {
        ++II;
      }
    }
  }

  return true;
}

bool BinaryFunction::requiresAddressTranslation() const {
  return opts::EnableBAT || hasSDTMarker() || hasPseudoProbe();
}

uint64_t BinaryFunction::getInstructionCount() const {
  uint64_t Count = 0;
  for (BinaryBasicBlock *const &Block : BasicBlocksLayout)
    Count += Block->getNumNonPseudos();
  return Count;
}

bool BinaryFunction::hasLayoutChanged() const { return ModifiedLayout; }

uint64_t BinaryFunction::getEditDistance() const {
  return ComputeEditDistance<BinaryBasicBlock *>(BasicBlocksPreviousLayout,
                                                 BasicBlocksLayout);
}

void BinaryFunction::clearDisasmState() {
  clearList(Instructions);
  clearList(IgnoredBranches);
  clearList(TakenBranches);
  clearList(InterproceduralReferences);

  if (BC.HasRelocations) {
    for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
      BC.UndefinedSymbols.insert(LI.second);
    if (FunctionEndLabel)
      BC.UndefinedSymbols.insert(FunctionEndLabel);
  }
}

void BinaryFunction::setTrapOnEntry() {
  clearDisasmState();

  auto addTrapAtOffset = [&](uint64_t Offset) {
    MCInst TrapInstr;
    BC.MIB->createTrap(TrapInstr);
    addInstruction(Offset, std::move(TrapInstr));
  };

  addTrapAtOffset(0);
  for (const std::pair<const uint32_t, MCSymbol *> &KV : getLabels())
    if (getSecondaryEntryPointSymbol(KV.second))
      addTrapAtOffset(KV.first);

  TrapsOnEntry = true;
}

void BinaryFunction::setIgnored() {
  if (opts::processAllFunctions()) {
    // We can accept ignored functions before they've been disassembled.
    // In that case, they would still get disassembled and emited, but not
    // optimized.
    assert(CurrentState == State::Empty &&
           "cannot ignore non-empty functions in current mode");
    IsIgnored = true;
    return;
  }

  clearDisasmState();

  // Clear CFG state too.
  if (hasCFG()) {
    releaseCFG();

    for (BinaryBasicBlock *BB : BasicBlocks)
      delete BB;
    clearList(BasicBlocks);

    for (BinaryBasicBlock *BB : DeletedBasicBlocks)
      delete BB;
    clearList(DeletedBasicBlocks);

    clearList(BasicBlocksLayout);
    clearList(BasicBlocksPreviousLayout);
  }

  CurrentState = State::Empty;

  IsIgnored = true;
  IsSimple = false;
  LLVM_DEBUG(dbgs() << "Ignoring " << getPrintName() << '\n');
}

void BinaryFunction::duplicateConstantIslands() {
  assert(Islands && "function expected to have constant islands");

  for (BinaryBasicBlock *BB : layout()) {
    if (!BB->isCold())
      continue;

    for (MCInst &Inst : *BB) {
      int OpNum = 0;
      for (MCOperand &Operand : Inst) {
        if (!Operand.isExpr()) {
          ++OpNum;
          continue;
        }
        const MCSymbol *Symbol = BC.MIB->getTargetSymbol(Inst, OpNum);
        // Check if this is an island symbol
        if (!Islands->Symbols.count(Symbol) &&
            !Islands->ProxySymbols.count(Symbol))
          continue;

        // Create cold symbol, if missing
        auto ISym = Islands->ColdSymbols.find(Symbol);
        MCSymbol *ColdSymbol;
        if (ISym != Islands->ColdSymbols.end()) {
          ColdSymbol = ISym->second;
        } else {
          ColdSymbol = BC.Ctx->getOrCreateSymbol(Symbol->getName() + ".cold");
          Islands->ColdSymbols[Symbol] = ColdSymbol;
          // Check if this is a proxy island symbol and update owner proxy map
          if (Islands->ProxySymbols.count(Symbol)) {
            BinaryFunction *Owner = Islands->ProxySymbols[Symbol];
            auto IProxiedSym = Owner->Islands->Proxies[this].find(Symbol);
            Owner->Islands->ColdProxies[this][IProxiedSym->second] = ColdSymbol;
          }
        }

        // Update instruction reference
        Operand = MCOperand::createExpr(BC.MIB->getTargetExprFor(
            Inst,
            MCSymbolRefExpr::create(ColdSymbol, MCSymbolRefExpr::VK_None,
                                    *BC.Ctx),
            *BC.Ctx, 0));
        ++OpNum;
      }
    }
  }
}

namespace {

#ifndef MAX_PATH
#define MAX_PATH 255
#endif

std::string constructFilename(std::string Filename, std::string Annotation,
                              std::string Suffix) {
  std::replace(Filename.begin(), Filename.end(), '/', '-');
  if (!Annotation.empty())
    Annotation.insert(0, "-");
  if (Filename.size() + Annotation.size() + Suffix.size() > MAX_PATH) {
    assert(Suffix.size() + Annotation.size() <= MAX_PATH);
    if (opts::Verbosity >= 1) {
      errs() << "BOLT-WARNING: Filename \"" << Filename << Annotation << Suffix
             << "\" exceeds the " << MAX_PATH << " size limit, truncating.\n";
    }
    Filename.resize(MAX_PATH - (Suffix.size() + Annotation.size()));
  }
  Filename += Annotation;
  Filename += Suffix;
  return Filename;
}

std::string formatEscapes(const std::string &Str) {
  std::string Result;
  for (unsigned I = 0; I < Str.size(); ++I) {
    char C = Str[I];
    switch (C) {
    case '\n':
      Result += "&#13;";
      break;
    case '"':
      break;
    default:
      Result += C;
      break;
    }
  }
  return Result;
}

} // namespace

void BinaryFunction::dumpGraph(raw_ostream &OS) const {
  OS << "strict digraph \"" << getPrintName() << "\" {\n";
  uint64_t Offset = Address;
  for (BinaryBasicBlock *BB : BasicBlocks) {
    auto LayoutPos =
        std::find(BasicBlocksLayout.begin(), BasicBlocksLayout.end(), BB);
    unsigned Layout = LayoutPos - BasicBlocksLayout.begin();
    const char *ColdStr = BB->isCold() ? " (cold)" : "";
    OS << format("\"%s\" [label=\"%s%s\\n(C:%lu,O:%lu,I:%u,L:%u:CFI:%u)\"]\n",
                 BB->getName().data(), BB->getName().data(), ColdStr,
                 (BB->ExecutionCount != BinaryBasicBlock::COUNT_NO_PROFILE
                      ? BB->ExecutionCount
                      : 0),
                 BB->getOffset(), getIndex(BB), Layout, BB->getCFIState());
    OS << format("\"%s\" [shape=box]\n", BB->getName().data());
    if (opts::DotToolTipCode) {
      std::string Str;
      raw_string_ostream CS(Str);
      Offset = BC.printInstructions(CS, BB->begin(), BB->end(), Offset, this);
      const std::string Code = formatEscapes(CS.str());
      OS << format("\"%s\" [tooltip=\"%s\"]\n", BB->getName().data(),
                   Code.c_str());
    }

    // analyzeBranch is just used to get the names of the branch
    // opcodes.
    const MCSymbol *TBB = nullptr;
    const MCSymbol *FBB = nullptr;
    MCInst *CondBranch = nullptr;
    MCInst *UncondBranch = nullptr;
    const bool Success = BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);

    const MCInst *LastInstr = BB->getLastNonPseudoInstr();
    const bool IsJumpTable = LastInstr && BC.MIB->getJumpTable(*LastInstr);

    auto BI = BB->branch_info_begin();
    for (BinaryBasicBlock *Succ : BB->successors()) {
      std::string Branch;
      if (Success) {
        if (Succ == BB->getConditionalSuccessor(true)) {
          Branch = CondBranch ? std::string(BC.InstPrinter->getOpcodeName(
                                    CondBranch->getOpcode()))
                              : "TB";
        } else if (Succ == BB->getConditionalSuccessor(false)) {
          Branch = UncondBranch ? std::string(BC.InstPrinter->getOpcodeName(
                                      UncondBranch->getOpcode()))
                                : "FB";
        } else {
          Branch = "FT";
        }
      }
      if (IsJumpTable)
        Branch = "JT";
      OS << format("\"%s\" -> \"%s\" [label=\"%s", BB->getName().data(),
                   Succ->getName().data(), Branch.c_str());

      if (BB->getExecutionCount() != COUNT_NO_PROFILE &&
          BI->MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
        OS << "\\n(C:" << BI->Count << ",M:" << BI->MispredictedCount << ")";
      } else if (ExecutionCount != COUNT_NO_PROFILE &&
                 BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
        OS << "\\n(IC:" << BI->Count << ")";
      }
      OS << "\"]\n";

      ++BI;
    }
    for (BinaryBasicBlock *LP : BB->landing_pads()) {
      OS << format("\"%s\" -> \"%s\" [constraint=false style=dashed]\n",
                   BB->getName().data(), LP->getName().data());
    }
  }
  OS << "}\n";
}

void BinaryFunction::viewGraph() const {
  SmallString<MAX_PATH> Filename;
  if (std::error_code EC =
          sys::fs::createTemporaryFile("bolt-cfg", "dot", Filename)) {
    errs() << "BOLT-ERROR: " << EC.message() << ", unable to create "
           << " bolt-cfg-XXXXX.dot temporary file.\n";
    return;
  }
  dumpGraphToFile(std::string(Filename));
  if (DisplayGraph(Filename))
    errs() << "BOLT-ERROR: Can't display " << Filename << " with graphviz.\n";
  if (std::error_code EC = sys::fs::remove(Filename)) {
    errs() << "BOLT-WARNING: " << EC.message() << ", failed to remove "
           << Filename << "\n";
  }
}

void BinaryFunction::dumpGraphForPass(std::string Annotation) const {
  std::string Filename = constructFilename(getPrintName(), Annotation, ".dot");
  outs() << "BOLT-DEBUG: Dumping CFG to " << Filename << "\n";
  dumpGraphToFile(Filename);
}

void BinaryFunction::dumpGraphToFile(std::string Filename) const {
  std::error_code EC;
  raw_fd_ostream of(Filename, EC, sys::fs::OF_None);
  if (EC) {
    if (opts::Verbosity >= 1) {
      errs() << "BOLT-WARNING: " << EC.message() << ", unable to open "
             << Filename << " for output.\n";
    }
    return;
  }
  dumpGraph(of);
}

bool BinaryFunction::validateCFG() const {
  bool Valid = true;
  for (BinaryBasicBlock *BB : BasicBlocks)
    Valid &= BB->validateSuccessorInvariants();

  if (!Valid)
    return Valid;

  // Make sure all blocks in CFG are valid.
  auto validateBlock = [this](const BinaryBasicBlock *BB, StringRef Desc) {
    if (!BB->isValid()) {
      errs() << "BOLT-ERROR: deleted " << Desc << " " << BB->getName()
             << " detected in:\n";
      this->dump();
      return false;
    }
    return true;
  };
  for (const BinaryBasicBlock *BB : BasicBlocks) {
    if (!validateBlock(BB, "block"))
      return false;
    for (const BinaryBasicBlock *PredBB : BB->predecessors())
      if (!validateBlock(PredBB, "predecessor"))
        return false;
    for (const BinaryBasicBlock *SuccBB : BB->successors())
      if (!validateBlock(SuccBB, "successor"))
        return false;
    for (const BinaryBasicBlock *LP : BB->landing_pads())
      if (!validateBlock(LP, "landing pad"))
        return false;
    for (const BinaryBasicBlock *Thrower : BB->throwers())
      if (!validateBlock(Thrower, "thrower"))
        return false;
  }

  for (const BinaryBasicBlock *BB : BasicBlocks) {
    std::unordered_set<const BinaryBasicBlock *> BBLandingPads;
    for (const BinaryBasicBlock *LP : BB->landing_pads()) {
      if (BBLandingPads.count(LP)) {
        errs() << "BOLT-ERROR: duplicate landing pad detected in"
               << BB->getName() << " in function " << *this << '\n';
        return false;
      }
      BBLandingPads.insert(LP);
    }

    std::unordered_set<const BinaryBasicBlock *> BBThrowers;
    for (const BinaryBasicBlock *Thrower : BB->throwers()) {
      if (BBThrowers.count(Thrower)) {
        errs() << "BOLT-ERROR: duplicate thrower detected in" << BB->getName()
               << " in function " << *this << '\n';
        return false;
      }
      BBThrowers.insert(Thrower);
    }

    for (const BinaryBasicBlock *LPBlock : BB->landing_pads()) {
      if (std::find(LPBlock->throw_begin(), LPBlock->throw_end(), BB) ==
          LPBlock->throw_end()) {
        errs() << "BOLT-ERROR: inconsistent landing pad detected in " << *this
               << ": " << BB->getName() << " is in LandingPads but not in "
               << LPBlock->getName() << " Throwers\n";
        return false;
      }
    }
    for (const BinaryBasicBlock *Thrower : BB->throwers()) {
      if (std::find(Thrower->lp_begin(), Thrower->lp_end(), BB) ==
          Thrower->lp_end()) {
        errs() << "BOLT-ERROR: inconsistent thrower detected in " << *this
               << ": " << BB->getName() << " is in Throwers list but not in "
               << Thrower->getName() << " LandingPads\n";
        return false;
      }
    }
  }

  return Valid;
}

void BinaryFunction::fixBranches() {
  auto &MIB = BC.MIB;
  MCContext *Ctx = BC.Ctx.get();

  for (unsigned I = 0, E = BasicBlocksLayout.size(); I != E; ++I) {
    BinaryBasicBlock *BB = BasicBlocksLayout[I];
    const MCSymbol *TBB = nullptr;
    const MCSymbol *FBB = nullptr;
    MCInst *CondBranch = nullptr;
    MCInst *UncondBranch = nullptr;
    if (!BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch))
      continue;

    // We will create unconditional branch with correct destination if needed.
    if (UncondBranch)
      BB->eraseInstruction(BB->findInstruction(UncondBranch));

    // Basic block that follows the current one in the final layout.
    const BinaryBasicBlock *NextBB = nullptr;
    if (I + 1 != E && BB->isCold() == BasicBlocksLayout[I + 1]->isCold())
      NextBB = BasicBlocksLayout[I + 1];

    if (BB->succ_size() == 1) {
      // __builtin_unreachable() could create a conditional branch that
      // falls-through into the next function - hence the block will have only
      // one valid successor. Since behaviour is undefined - we replace
      // the conditional branch with an unconditional if required.
      if (CondBranch)
        BB->eraseInstruction(BB->findInstruction(CondBranch));
      if (BB->getSuccessor() == NextBB)
        continue;
      BB->addBranchInstruction(BB->getSuccessor());
    } else if (BB->succ_size() == 2) {
      assert(CondBranch && "conditional branch expected");
      const BinaryBasicBlock *TSuccessor = BB->getConditionalSuccessor(true);
      const BinaryBasicBlock *FSuccessor = BB->getConditionalSuccessor(false);
      // Check whether we support reversing this branch direction
      const bool IsSupported =
          !MIB->isUnsupportedBranch(CondBranch->getOpcode());
      if (NextBB && NextBB == TSuccessor && IsSupported) {
        std::swap(TSuccessor, FSuccessor);
        {
          auto L = BC.scopeLock();
          MIB->reverseBranchCondition(*CondBranch, TSuccessor->getLabel(), Ctx);
        }
        BB->swapConditionalSuccessors();
      } else {
        auto L = BC.scopeLock();
        MIB->replaceBranchTarget(*CondBranch, TSuccessor->getLabel(), Ctx);
      }
      if (TSuccessor == FSuccessor)
        BB->removeDuplicateConditionalSuccessor(CondBranch);
      if (!NextBB ||
          ((NextBB != TSuccessor || !IsSupported) && NextBB != FSuccessor)) {
        // If one of the branches is guaranteed to be "long" while the other
        // could be "short", then prioritize short for "taken". This will
        // generate a sequence 1 byte shorter on x86.
        if (IsSupported && BC.isX86() &&
            TSuccessor->isCold() != FSuccessor->isCold() &&
            BB->isCold() != TSuccessor->isCold()) {
          std::swap(TSuccessor, FSuccessor);
          {
            auto L = BC.scopeLock();
            MIB->reverseBranchCondition(*CondBranch, TSuccessor->getLabel(),
                                        Ctx);
          }
          BB->swapConditionalSuccessors();
        }
        BB->addBranchInstruction(FSuccessor);
      }
    }
    // Cases where the number of successors is 0 (block ends with a
    // terminator) or more than 2 (switch table) don't require branch
    // instruction adjustments.
  }
  assert((!isSimple() || validateCFG()) &&
         "Invalid CFG detected after fixing branches");
}

void BinaryFunction::propagateGnuArgsSizeInfo(
    MCPlusBuilder::AllocatorIdTy AllocId) {
  assert(CurrentState == State::Disassembled && "unexpected function state");

  if (!hasEHRanges() || !usesGnuArgsSize())
    return;

  // The current value of DW_CFA_GNU_args_size affects all following
  // invoke instructions until the next CFI overrides it.
  // It is important to iterate basic blocks in the original order when
  // assigning the value.
  uint64_t CurrentGnuArgsSize = 0;
  for (BinaryBasicBlock *BB : BasicBlocks) {
    for (auto II = BB->begin(); II != BB->end();) {
      MCInst &Instr = *II;
      if (BC.MIB->isCFI(Instr)) {
        const MCCFIInstruction *CFI = getCFIFor(Instr);
        if (CFI->getOperation() == MCCFIInstruction::OpGnuArgsSize) {
          CurrentGnuArgsSize = CFI->getOffset();
          // Delete DW_CFA_GNU_args_size instructions and only regenerate
          // during the final code emission. The information is embedded
          // inside call instructions.
          II = BB->erasePseudoInstruction(II);
          continue;
        }
      } else if (BC.MIB->isInvoke(Instr)) {
        // Add the value of GNU_args_size as an extra operand to invokes.
        BC.MIB->addGnuArgsSize(Instr, CurrentGnuArgsSize, AllocId);
      }
      ++II;
    }
  }
}

void BinaryFunction::postProcessBranches() {
  if (!isSimple())
    return;
  for (BinaryBasicBlock *BB : BasicBlocksLayout) {
    auto LastInstrRI = BB->getLastNonPseudo();
    if (BB->succ_size() == 1) {
      if (LastInstrRI != BB->rend() &&
          BC.MIB->isConditionalBranch(*LastInstrRI)) {
        // __builtin_unreachable() could create a conditional branch that
        // falls-through into the next function - hence the block will have only
        // one valid successor. Such behaviour is undefined and thus we remove
        // the conditional branch while leaving a valid successor.
        BB->eraseInstruction(std::prev(LastInstrRI.base()));
        LLVM_DEBUG(dbgs() << "BOLT-DEBUG: erasing conditional branch in "
                          << BB->getName() << " in function " << *this << '\n');
      }
    } else if (BB->succ_size() == 0) {
      // Ignore unreachable basic blocks.
      if (BB->pred_size() == 0 || BB->isLandingPad())
        continue;

      // If it's the basic block that does not end up with a terminator - we
      // insert a return instruction unless it's a call instruction.
      if (LastInstrRI == BB->rend()) {
        LLVM_DEBUG(
            dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "
                   << BB->getName() << " in function " << *this << '\n');
        continue;
      }
      if (!BC.MIB->isTerminator(*LastInstrRI) &&
          !BC.MIB->isCall(*LastInstrRI)) {
        LLVM_DEBUG(dbgs() << "BOLT-DEBUG: adding return to basic block "
                          << BB->getName() << " in function " << *this << '\n');
        MCInst ReturnInstr;
        BC.MIB->createReturn(ReturnInstr);
        BB->addInstruction(ReturnInstr);
      }
    }
  }
  assert(validateCFG() && "invalid CFG");
}

MCSymbol *BinaryFunction::addEntryPointAtOffset(uint64_t Offset) {
  assert(Offset && "cannot add primary entry point");
  assert(CurrentState == State::Empty || CurrentState == State::Disassembled);

  const uint64_t EntryPointAddress = getAddress() + Offset;
  MCSymbol *LocalSymbol = getOrCreateLocalLabel(EntryPointAddress);

  MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(LocalSymbol);
  if (EntrySymbol)
    return EntrySymbol;

  if (BinaryData *EntryBD = BC.getBinaryDataAtAddress(EntryPointAddress)) {
    EntrySymbol = EntryBD->getSymbol();
  } else {
    EntrySymbol = BC.getOrCreateGlobalSymbol(
        EntryPointAddress, Twine("__ENTRY_") + getOneName() + "@");
  }
  SecondaryEntryPoints[LocalSymbol] = EntrySymbol;

  BC.setSymbolToFunctionMap(EntrySymbol, this);

  return EntrySymbol;
}

MCSymbol *BinaryFunction::addEntryPoint(const BinaryBasicBlock &BB) {
  assert(CurrentState == State::CFG &&
         "basic block can be added as an entry only in a function with CFG");

  if (&BB == BasicBlocks.front())
    return getSymbol();

  MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB);
  if (EntrySymbol)
    return EntrySymbol;

  EntrySymbol =
      BC.Ctx->getOrCreateSymbol("__ENTRY_" + BB.getLabel()->getName());

  SecondaryEntryPoints[BB.getLabel()] = EntrySymbol;

  BC.setSymbolToFunctionMap(EntrySymbol, this);

  return EntrySymbol;
}

MCSymbol *BinaryFunction::getSymbolForEntryID(uint64_t EntryID) {
  if (EntryID == 0)
    return getSymbol();

  if (!isMultiEntry())
    return nullptr;

  uint64_t NumEntries = 0;
  if (hasCFG()) {
    for (BinaryBasicBlock *BB : BasicBlocks) {
      MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB);
      if (!EntrySymbol)
        continue;
      if (NumEntries == EntryID)
        return EntrySymbol;
      ++NumEntries;
    }
  } else {
    for (std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
      MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second);
      if (!EntrySymbol)
        continue;
      if (NumEntries == EntryID)
        return EntrySymbol;
      ++NumEntries;
    }
  }

  return nullptr;
}

uint64_t BinaryFunction::getEntryIDForSymbol(const MCSymbol *Symbol) const {
  if (!isMultiEntry())
    return 0;

  for (const MCSymbol *FunctionSymbol : getSymbols())
    if (FunctionSymbol == Symbol)
      return 0;

  // Check all secondary entries available as either basic blocks or lables.
  uint64_t NumEntries = 0;
  for (const BinaryBasicBlock *BB : BasicBlocks) {
    MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB);
    if (!EntrySymbol)
      continue;
    if (EntrySymbol == Symbol)
      return NumEntries;
    ++NumEntries;
  }
  NumEntries = 0;
  for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
    MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second);
    if (!EntrySymbol)
      continue;
    if (EntrySymbol == Symbol)
      return NumEntries;
    ++NumEntries;
  }

  llvm_unreachable("symbol not found");
}

bool BinaryFunction::forEachEntryPoint(EntryPointCallbackTy Callback) const {
  bool Status = Callback(0, getSymbol());
  if (!isMultiEntry())
    return Status;

  for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
    if (!Status)
      break;

    MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second);
    if (!EntrySymbol)
      continue;

    Status = Callback(KV.first, EntrySymbol);
  }

  return Status;
}

BinaryFunction::BasicBlockOrderType BinaryFunction::dfs() const {
  BasicBlockOrderType DFS;
  unsigned Index = 0;
  std::stack<BinaryBasicBlock *> Stack;

  // Push entry points to the stack in reverse order.
  //
  // NB: we rely on the original order of entries to match.
  for (auto BBI = layout_rbegin(); BBI != layout_rend(); ++BBI) {
    BinaryBasicBlock *BB = *BBI;
    if (isEntryPoint(*BB))
      Stack.push(BB);
    BB->setLayoutIndex(BinaryBasicBlock::InvalidIndex);
  }

  while (!Stack.empty()) {
    BinaryBasicBlock *BB = Stack.top();
    Stack.pop();

    if (BB->getLayoutIndex() != BinaryBasicBlock::InvalidIndex)
      continue;

    BB->setLayoutIndex(Index++);
    DFS.push_back(BB);

    for (BinaryBasicBlock *SuccBB : BB->landing_pads()) {
      Stack.push(SuccBB);
    }

    const MCSymbol *TBB = nullptr;
    const MCSymbol *FBB = nullptr;
    MCInst *CondBranch = nullptr;
    MCInst *UncondBranch = nullptr;
    if (BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch) && CondBranch &&
        BB->succ_size() == 2) {
      if (BC.MIB->getCanonicalBranchCondCode(BC.MIB->getCondCode(
              *CondBranch)) == BC.MIB->getCondCode(*CondBranch)) {
        Stack.push(BB->getConditionalSuccessor(true));
        Stack.push(BB->getConditionalSuccessor(false));
      } else {
        Stack.push(BB->getConditionalSuccessor(false));
        Stack.push(BB->getConditionalSuccessor(true));
      }
    } else {
      for (BinaryBasicBlock *SuccBB : BB->successors()) {
        Stack.push(SuccBB);
      }
    }
  }

  return DFS;
}

size_t BinaryFunction::computeHash(bool UseDFS,
                                   OperandHashFuncTy OperandHashFunc) const {
  if (size() == 0)
    return 0;

  assert(hasCFG() && "function is expected to have CFG");

  const BasicBlockOrderType &Order = UseDFS ? dfs() : BasicBlocksLayout;

  // The hash is computed by creating a string of all instruction opcodes and
  // possibly their operands and then hashing that string with std::hash.
  std::string HashString;
  for (const BinaryBasicBlock *BB : Order) {
    for (const MCInst &Inst : *BB) {
      unsigned Opcode = Inst.getOpcode();

      if (BC.MIB->isPseudo(Inst))
        continue;

      // Ignore unconditional jumps since we check CFG consistency by processing
      // basic blocks in order and do not rely on branches to be in-sync with
      // CFG. Note that we still use condition code of conditional jumps.
      if (BC.MIB->isUnconditionalBranch(Inst))
        continue;

      if (Opcode == 0)
        HashString.push_back(0);

      while (Opcode) {
        uint8_t LSB = Opcode & 0xff;
        HashString.push_back(LSB);
        Opcode = Opcode >> 8;
      }

      for (unsigned I = 0, E = MCPlus::getNumPrimeOperands(Inst); I != E; ++I)
        HashString.append(OperandHashFunc(Inst.getOperand(I)));
    }
  }

  return Hash = std::hash<std::string>{}(HashString);
}

void BinaryFunction::insertBasicBlocks(
    BinaryBasicBlock *Start,
    std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs,
    const bool UpdateLayout, const bool UpdateCFIState,
    const bool RecomputeLandingPads) {
  const auto StartIndex = Start ? getIndex(Start) : -1;
  const size_t NumNewBlocks = NewBBs.size();

  BasicBlocks.insert(BasicBlocks.begin() + (StartIndex + 1), NumNewBlocks,
                     nullptr);

  auto I = StartIndex + 1;
  for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) {
    assert(!BasicBlocks[I]);
    BasicBlocks[I++] = BB.release();
  }

  if (RecomputeLandingPads)
    recomputeLandingPads();
  else
    updateBBIndices(0);

  if (UpdateLayout)
    updateLayout(Start, NumNewBlocks);

  if (UpdateCFIState)
    updateCFIState(Start, NumNewBlocks);
}

BinaryFunction::iterator BinaryFunction::insertBasicBlocks(
    BinaryFunction::iterator StartBB,
    std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs,
    const bool UpdateLayout, const bool UpdateCFIState,
    const bool RecomputeLandingPads) {
  const unsigned StartIndex = getIndex(&*StartBB);
  const size_t NumNewBlocks = NewBBs.size();

  BasicBlocks.insert(BasicBlocks.begin() + StartIndex + 1, NumNewBlocks,
                     nullptr);
  auto RetIter = BasicBlocks.begin() + StartIndex + 1;

  unsigned I = StartIndex + 1;
  for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) {
    assert(!BasicBlocks[I]);
    BasicBlocks[I++] = BB.release();
  }

  if (RecomputeLandingPads)
    recomputeLandingPads();
  else
    updateBBIndices(0);

  if (UpdateLayout)
    updateLayout(*std::prev(RetIter), NumNewBlocks);

  if (UpdateCFIState)
    updateCFIState(*std::prev(RetIter), NumNewBlocks);

  return RetIter;
}

void BinaryFunction::updateBBIndices(const unsigned StartIndex) {
  for (unsigned I = StartIndex; I < BasicBlocks.size(); ++I)
    BasicBlocks[I]->Index = I;
}

void BinaryFunction::updateCFIState(BinaryBasicBlock *Start,
                                    const unsigned NumNewBlocks) {
  const int32_t CFIState = Start->getCFIStateAtExit();
  const unsigned StartIndex = getIndex(Start) + 1;
  for (unsigned I = 0; I < NumNewBlocks; ++I)
    BasicBlocks[StartIndex + I]->setCFIState(CFIState);
}

void BinaryFunction::updateLayout(BinaryBasicBlock *Start,
                                  const unsigned NumNewBlocks) {
  // If start not provided insert new blocks at the beginning
  if (!Start) {
    BasicBlocksLayout.insert(layout_begin(), BasicBlocks.begin(),
                             BasicBlocks.begin() + NumNewBlocks);
    updateLayoutIndices();
    return;
  }

  // Insert new blocks in the layout immediately after Start.
  auto Pos = std::find(layout_begin(), layout_end(), Start);
  assert(Pos != layout_end());
  BasicBlockListType::iterator Begin =
      std::next(BasicBlocks.begin(), getIndex(Start) + 1);
  BasicBlockListType::iterator End =
      std::next(BasicBlocks.begin(), getIndex(Start) + NumNewBlocks + 1);
  BasicBlocksLayout.insert(Pos + 1, Begin, End);
  updateLayoutIndices();
}

bool BinaryFunction::checkForAmbiguousJumpTables() {
  SmallSet<uint64_t, 4> JumpTables;
  for (BinaryBasicBlock *&BB : BasicBlocks) {
    for (MCInst &Inst : *BB) {
      if (!BC.MIB->isIndirectBranch(Inst))
        continue;
      uint64_t JTAddress = BC.MIB->getJumpTable(Inst);
      if (!JTAddress)
        continue;
      // This address can be inside another jump table, but we only consider
      // it ambiguous when the same start address is used, not the same JT
      // object.
      if (!JumpTables.count(JTAddress)) {
        JumpTables.insert(JTAddress);
        continue;
      }
      return true;
    }
  }
  return false;
}

void BinaryFunction::disambiguateJumpTables(
    MCPlusBuilder::AllocatorIdTy AllocId) {
  assert((opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations);
  SmallPtrSet<JumpTable *, 4> JumpTables;
  for (BinaryBasicBlock *&BB : BasicBlocks) {
    for (MCInst &Inst : *BB) {
      if (!BC.MIB->isIndirectBranch(Inst))
        continue;
      JumpTable *JT = getJumpTable(Inst);
      if (!JT)
        continue;
      auto Iter = JumpTables.find(JT);
      if (Iter == JumpTables.end()) {
        JumpTables.insert(JT);
        continue;
      }
      // This instruction is an indirect jump using a jump table, but it is
      // using the same jump table of another jump. Try all our tricks to
      // extract the jump table symbol and make it point to a new, duplicated JT
      MCPhysReg BaseReg1;
      uint64_t Scale;
      const MCSymbol *Target;
      // In case we match if our first matcher, first instruction is the one to
      // patch
      MCInst *JTLoadInst = &Inst;
      // Try a standard indirect jump matcher, scale 8
      std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher =
          BC.MIB->matchIndJmp(BC.MIB->matchReg(BaseReg1),
                              BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
                              /*Offset=*/BC.MIB->matchSymbol(Target));
      if (!IndJmpMatcher->match(
              *BC.MRI, *BC.MIB,
              MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) ||
          BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) {
        MCPhysReg BaseReg2;
        uint64_t Offset;
        // Standard JT matching failed. Trying now:
        //     movq  "jt.2397/1"(,%rax,8), %rax
        //     jmpq  *%rax
        std::unique_ptr<MCPlusBuilder::MCInstMatcher> LoadMatcherOwner =
            BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg1),
                              BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
                              /*Offset=*/BC.MIB->matchSymbol(Target));
        MCPlusBuilder::MCInstMatcher *LoadMatcher = LoadMatcherOwner.get();
        std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher2 =
            BC.MIB->matchIndJmp(std::move(LoadMatcherOwner));
        if (!IndJmpMatcher2->match(
                *BC.MRI, *BC.MIB,
                MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) ||
            BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) {
          // JT matching failed. Trying now:
          // PIC-style matcher, scale 4
          //    addq    %rdx, %rsi
          //    addq    %rdx, %rdi
          //    leaq    DATAat0x402450(%rip), %r11
          //    movslq  (%r11,%rdx,4), %rcx
          //    addq    %r11, %rcx
          //    jmpq    *%rcx # JUMPTABLE @0x402450
          std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICIndJmpMatcher =
              BC.MIB->matchIndJmp(BC.MIB->matchAdd(
                  BC.MIB->matchReg(BaseReg1),
                  BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg2),
                                    BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
                                    BC.MIB->matchImm(Offset))));
          std::unique_ptr<MCPlusBuilder::MCInstMatcher> LEAMatcherOwner =
              BC.MIB->matchLoadAddr(BC.MIB->matchSymbol(Target));
          MCPlusBuilder::MCInstMatcher *LEAMatcher = LEAMatcherOwner.get();
          std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICBaseAddrMatcher =
              BC.MIB->matchIndJmp(BC.MIB->matchAdd(std::move(LEAMatcherOwner),
                                                   BC.MIB->matchAnyOperand()));
          if (!PICIndJmpMatcher->match(
                  *BC.MRI, *BC.MIB,
                  MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) ||
              Scale != 4 || BaseReg1 != BaseReg2 || Offset != 0 ||
              !PICBaseAddrMatcher->match(
                  *BC.MRI, *BC.MIB,
                  MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1)) {
            llvm_unreachable("Failed to extract jump table base");
            continue;
          }
          // Matched PIC, identify the instruction with the reference to the JT
          JTLoadInst = LEAMatcher->CurInst;
        } else {
          // Matched non-PIC
          JTLoadInst = LoadMatcher->CurInst;
        }
      }

      uint64_t NewJumpTableID = 0;
      const MCSymbol *NewJTLabel;
      std::tie(NewJumpTableID, NewJTLabel) =
          BC.duplicateJumpTable(*this, JT, Target);
      {
        auto L = BC.scopeLock();
        BC.MIB->replaceMemOperandDisp(*JTLoadInst, NewJTLabel, BC.Ctx.get());
      }
      // We use a unique ID with the high bit set as address for this "injected"
      // jump table (not originally in the input binary).
      BC.MIB->setJumpTable(Inst, NewJumpTableID, 0, AllocId);
    }
  }
}

bool BinaryFunction::replaceJumpTableEntryIn(BinaryBasicBlock *BB,
                                             BinaryBasicBlock *OldDest,
                                             BinaryBasicBlock *NewDest) {
  MCInst *Instr = BB->getLastNonPseudoInstr();
  if (!Instr || !BC.MIB->isIndirectBranch(*Instr))
    return false;
  uint64_t JTAddress = BC.MIB->getJumpTable(*Instr);
  assert(JTAddress && "Invalid jump table address");
  JumpTable *JT = getJumpTableContainingAddress(JTAddress);
  assert(JT && "No jump table structure for this indirect branch");
  bool Patched = JT->replaceDestination(JTAddress, OldDest->getLabel(),
                                        NewDest->getLabel());
  (void)Patched;
  assert(Patched && "Invalid entry to be replaced in jump table");
  return true;
}

BinaryBasicBlock *BinaryFunction::splitEdge(BinaryBasicBlock *From,
                                            BinaryBasicBlock *To) {
  // Create intermediate BB
  MCSymbol *Tmp;
  {
    auto L = BC.scopeLock();
    Tmp = BC.Ctx->createNamedTempSymbol("SplitEdge");
  }
  // Link new BBs to the original input offset of the From BB, so we can map
  // samples recorded in new BBs back to the original BB seem in the input
  // binary (if using BAT)
  std::unique_ptr<BinaryBasicBlock> NewBB =
      createBasicBlock(From->getInputOffset(), Tmp);
  BinaryBasicBlock *NewBBPtr = NewBB.get();

  // Update "From" BB
  auto I = From->succ_begin();
  auto BI = From->branch_info_begin();
  for (; I != From->succ_end(); ++I) {
    if (*I == To)
      break;
    ++BI;
  }
  assert(I != From->succ_end() && "Invalid CFG edge in splitEdge!");
  uint64_t OrigCount = BI->Count;
  uint64_t OrigMispreds = BI->MispredictedCount;
  replaceJumpTableEntryIn(From, To, NewBBPtr);
  From->replaceSuccessor(To, NewBBPtr, OrigCount, OrigMispreds);

  NewBB->addSuccessor(To, OrigCount, OrigMispreds);
  NewBB->setExecutionCount(OrigCount);
  NewBB->setIsCold(From->isCold());

  // Update CFI and BB layout with new intermediate BB
  std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;
  NewBBs.emplace_back(std::move(NewBB));
  insertBasicBlocks(From, std::move(NewBBs), true, true,
                    /*RecomputeLandingPads=*/false);
  return NewBBPtr;
}

void BinaryFunction::deleteConservativeEdges() {
  // Our goal is to aggressively remove edges from the CFG that we believe are
  // wrong. This is used for instrumentation, where it is safe to remove
  // fallthrough edges because we won't reorder blocks.
  for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
    BinaryBasicBlock *BB = *I;
    if (BB->succ_size() != 1 || BB->size() == 0)
      continue;

    auto NextBB = std::next(I);
    MCInst *Last = BB->getLastNonPseudoInstr();
    // Fallthrough is a landing pad? Delete this edge (as long as we don't
    // have a direct jump to it)
    if ((*BB->succ_begin())->isLandingPad() && NextBB != E &&
        *BB->succ_begin() == *NextBB && Last && !BC.MIB->isBranch(*Last)) {
      BB->removeAllSuccessors();
      continue;
    }

    // Look for suspicious calls at the end of BB where gcc may optimize it and
    // remove the jump to the epilogue when it knows the call won't return.
    if (!Last || !BC.MIB->isCall(*Last))
      continue;

    const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(*Last);
    if (!CalleeSymbol)
      continue;

    StringRef CalleeName = CalleeSymbol->getName();
    if (CalleeName != "__cxa_throw@PLT" && CalleeName != "_Unwind_Resume@PLT" &&
        CalleeName != "__cxa_rethrow@PLT" && CalleeName != "exit@PLT" &&
        CalleeName != "abort@PLT")
      continue;

    BB->removeAllSuccessors();
  }
}

bool BinaryFunction::isDataMarker(const SymbolRef &Symbol,
                                  uint64_t SymbolSize) const {
  // For aarch64, the ABI defines mapping symbols so we identify data in the
  // code section (see IHI0056B). $d identifies a symbol starting data contents.
  if (BC.isAArch64() && Symbol.getType() &&
      cantFail(Symbol.getType()) == SymbolRef::ST_Unknown && SymbolSize == 0 &&
      Symbol.getName() &&
      (cantFail(Symbol.getName()) == "$d" ||
       cantFail(Symbol.getName()).startswith("$d.")))
    return true;
  return false;
}

bool BinaryFunction::isCodeMarker(const SymbolRef &Symbol,
                                  uint64_t SymbolSize) const {
  // For aarch64, the ABI defines mapping symbols so we identify data in the
  // code section (see IHI0056B). $x identifies a symbol starting code or the
  // end of a data chunk inside code.
  if (BC.isAArch64() && Symbol.getType() &&
      cantFail(Symbol.getType()) == SymbolRef::ST_Unknown && SymbolSize == 0 &&
      Symbol.getName() &&
      (cantFail(Symbol.getName()) == "$x" ||
       cantFail(Symbol.getName()).startswith("$x.")))
    return true;
  return false;
}

bool BinaryFunction::isSymbolValidInScope(const SymbolRef &Symbol,
                                          uint64_t SymbolSize) const {
  // If this symbol is in a different section from the one where the
  // function symbol is, don't consider it as valid.
  if (!getOriginSection()->containsAddress(
          cantFail(Symbol.getAddress(), "cannot get symbol address")))
    return false;

  // Some symbols are tolerated inside function bodies, others are not.
  // The real function boundaries may not be known at this point.
  if (isDataMarker(Symbol, SymbolSize) || isCodeMarker(Symbol, SymbolSize))
    return true;

  // It's okay to have a zero-sized symbol in the middle of non-zero-sized
  // function.
  if (SymbolSize == 0 && containsAddress(cantFail(Symbol.getAddress())))
    return true;

  if (cantFail(Symbol.getType()) != SymbolRef::ST_Unknown)
    return false;

  if (cantFail(Symbol.getFlags()) & SymbolRef::SF_Global)
    return false;

  return true;
}

void BinaryFunction::adjustExecutionCount(uint64_t Count) {
  if (getKnownExecutionCount() == 0 || Count == 0)
    return;

  if (ExecutionCount < Count)
    Count = ExecutionCount;

  double AdjustmentRatio = ((double)ExecutionCount - Count) / ExecutionCount;
  if (AdjustmentRatio < 0.0)
    AdjustmentRatio = 0.0;

  for (BinaryBasicBlock *&BB : layout())
    BB->adjustExecutionCount(AdjustmentRatio);

  ExecutionCount -= Count;
}

BinaryFunction::~BinaryFunction() {
  for (BinaryBasicBlock *BB : BasicBlocks)
    delete BB;
  for (BinaryBasicBlock *BB : DeletedBasicBlocks)
    delete BB;
}

void BinaryFunction::calculateLoopInfo() {
  // Discover loops.
  BinaryDominatorTree DomTree;
  DomTree.recalculate(*this);
  BLI.reset(new BinaryLoopInfo());
  BLI->analyze(DomTree);

  // Traverse discovered loops and add depth and profile information.
  std::stack<BinaryLoop *> St;
  for (auto I = BLI->begin(), E = BLI->end(); I != E; ++I) {
    St.push(*I);
    ++BLI->OuterLoops;
  }

  while (!St.empty()) {
    BinaryLoop *L = St.top();
    St.pop();
    ++BLI->TotalLoops;
    BLI->MaximumDepth = std::max(L->getLoopDepth(), BLI->MaximumDepth);

    // Add nested loops in the stack.
    for (BinaryLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
      St.push(*I);

    // Skip if no valid profile is found.
    if (!hasValidProfile()) {
      L->EntryCount = COUNT_NO_PROFILE;
      L->ExitCount = COUNT_NO_PROFILE;
      L->TotalBackEdgeCount = COUNT_NO_PROFILE;
      continue;
    }

    // Compute back edge count.
    SmallVector<BinaryBasicBlock *, 1> Latches;
    L->getLoopLatches(Latches);

    for (BinaryBasicBlock *Latch : Latches) {
      auto BI = Latch->branch_info_begin();
      for (BinaryBasicBlock *Succ : Latch->successors()) {
        if (Succ == L->getHeader()) {
          assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
                 "profile data not found");
          L->TotalBackEdgeCount += BI->Count;
        }
        ++BI;
      }
    }

    // Compute entry count.
    L->EntryCount = L->getHeader()->getExecutionCount() - L->TotalBackEdgeCount;

    // Compute exit count.
    SmallVector<BinaryLoop::Edge, 1> ExitEdges;
    L->getExitEdges(ExitEdges);
    for (BinaryLoop::Edge &Exit : ExitEdges) {
      const BinaryBasicBlock *Exiting = Exit.first;
      const BinaryBasicBlock *ExitTarget = Exit.second;
      auto BI = Exiting->branch_info_begin();
      for (BinaryBasicBlock *Succ : Exiting->successors()) {
        if (Succ == ExitTarget) {
          assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
                 "profile data not found");
          L->ExitCount += BI->Count;
        }
        ++BI;
      }
    }
  }
}

void BinaryFunction::updateOutputValues(const MCAsmLayout &Layout) {
  if (!isEmitted()) {
    assert(!isInjected() && "injected function should be emitted");
    setOutputAddress(getAddress());
    setOutputSize(getSize());
    return;
  }

  const uint64_t BaseAddress = getCodeSection()->getOutputAddress();
  ErrorOr<BinarySection &> ColdSection = getColdCodeSection();
  const uint64_t ColdBaseAddress =
      isSplit() ? ColdSection->getOutputAddress() : 0;
  if (BC.HasRelocations || isInjected()) {
    const uint64_t StartOffset = Layout.getSymbolOffset(*getSymbol());
    const uint64_t EndOffset = Layout.getSymbolOffset(*getFunctionEndLabel());
    setOutputAddress(BaseAddress + StartOffset);
    setOutputSize(EndOffset - StartOffset);
    if (hasConstantIsland()) {
      const uint64_t DataOffset =
          Layout.getSymbolOffset(*getFunctionConstantIslandLabel());
      setOutputDataAddress(BaseAddress + DataOffset);
    }
    if (isSplit()) {
      const MCSymbol *ColdStartSymbol = getColdSymbol();
      assert(ColdStartSymbol && ColdStartSymbol->isDefined() &&
             "split function should have defined cold symbol");
      const MCSymbol *ColdEndSymbol = getFunctionColdEndLabel();
      assert(ColdEndSymbol && ColdEndSymbol->isDefined() &&
             "split function should have defined cold end symbol");
      const uint64_t ColdStartOffset = Layout.getSymbolOffset(*ColdStartSymbol);
      const uint64_t ColdEndOffset = Layout.getSymbolOffset(*ColdEndSymbol);
      cold().setAddress(ColdBaseAddress + ColdStartOffset);
      cold().setImageSize(ColdEndOffset - ColdStartOffset);
      if (hasConstantIsland()) {
        const uint64_t DataOffset =
            Layout.getSymbolOffset(*getFunctionColdConstantIslandLabel());
        setOutputColdDataAddress(ColdBaseAddress + DataOffset);
      }
    }
  } else {
    setOutputAddress(getAddress());
    setOutputSize(Layout.getSymbolOffset(*getFunctionEndLabel()));
  }

  // Update basic block output ranges for the debug info, if we have
  // secondary entry points in the symbol table to update or if writing BAT.
  if (!opts::UpdateDebugSections && !isMultiEntry() &&
      !requiresAddressTranslation())
    return;

  // Output ranges should match the input if the body hasn't changed.
  if (!isSimple() && !BC.HasRelocations)
    return;

  // AArch64 may have functions that only contains a constant island (no code).
  if (layout_begin() == layout_end())
    return;

  BinaryBasicBlock *PrevBB = nullptr;
  for (auto BBI = layout_begin(), BBE = layout_end(); BBI != BBE; ++BBI) {
    BinaryBasicBlock *BB = *BBI;
    assert(BB->getLabel()->isDefined() && "symbol should be defined");
    const uint64_t BBBaseAddress = BB->isCold() ? ColdBaseAddress : BaseAddress;
    if (!BC.HasRelocations) {
      if (BB->isCold()) {
        assert(BBBaseAddress == cold().getAddress());
      } else {
        assert(BBBaseAddress == getOutputAddress());
      }
    }
    const uint64_t BBOffset = Layout.getSymbolOffset(*BB->getLabel());
    const uint64_t BBAddress = BBBaseAddress + BBOffset;
    BB->setOutputStartAddress(BBAddress);

    if (PrevBB) {
      uint64_t PrevBBEndAddress = BBAddress;
      if (BB->isCold() != PrevBB->isCold())
        PrevBBEndAddress = getOutputAddress() + getOutputSize();
      PrevBB->setOutputEndAddress(PrevBBEndAddress);
    }
    PrevBB = BB;

    BB->updateOutputValues(Layout);
  }
  PrevBB->setOutputEndAddress(PrevBB->isCold()
                                  ? cold().getAddress() + cold().getImageSize()
                                  : getOutputAddress() + getOutputSize());
}

DebugAddressRangesVector BinaryFunction::getOutputAddressRanges() const {
  DebugAddressRangesVector OutputRanges;

  if (isFolded())
    return OutputRanges;

  if (IsFragment)
    return OutputRanges;

  OutputRanges.emplace_back(getOutputAddress(),
                            getOutputAddress() + getOutputSize());
  if (isSplit()) {
    assert(isEmitted() && "split function should be emitted");
    OutputRanges.emplace_back(cold().getAddress(),
                              cold().getAddress() + cold().getImageSize());
  }

  if (isSimple())
    return OutputRanges;

  for (BinaryFunction *Frag : Fragments) {
    assert(!Frag->isSimple() &&
           "fragment of non-simple function should also be non-simple");
    OutputRanges.emplace_back(Frag->getOutputAddress(),
                              Frag->getOutputAddress() + Frag->getOutputSize());
  }

  return OutputRanges;
}

uint64_t BinaryFunction::translateInputToOutputAddress(uint64_t Address) const {
  if (isFolded())
    return 0;

  // If the function hasn't changed return the same address.
  if (!isEmitted())
    return Address;

  if (Address < getAddress())
    return 0;

  // Check if the address is associated with an instruction that is tracked
  // by address translation.
  auto KV = InputOffsetToAddressMap.find(Address - getAddress());
  if (KV != InputOffsetToAddressMap.end())
    return KV->second;

  // FIXME: #18950828 - we rely on relative offsets inside basic blocks to stay
  //        intact. Instead we can use pseudo instructions and/or annotations.
  const uint64_t Offset = Address - getAddress();
  const BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
  if (!BB) {
    // Special case for address immediately past the end of the function.
    if (Offset == getSize())
      return getOutputAddress() + getOutputSize();

    return 0;
  }

  return std::min(BB->getOutputAddressRange().first + Offset - BB->getOffset(),
                  BB->getOutputAddressRange().second);
}

DebugAddressRangesVector BinaryFunction::translateInputToOutputRanges(
    const DWARFAddressRangesVector &InputRanges) const {
  DebugAddressRangesVector OutputRanges;

  if (isFolded())
    return OutputRanges;

  // If the function hasn't changed return the same ranges.
  if (!isEmitted()) {
    OutputRanges.resize(InputRanges.size());
    std::transform(InputRanges.begin(), InputRanges.end(), OutputRanges.begin(),
                   [](const DWARFAddressRange &Range) {
                     return DebugAddressRange(Range.LowPC, Range.HighPC);
                   });
    return OutputRanges;
  }

  // Even though we will merge ranges in a post-processing pass, we attempt to
  // merge them in a main processing loop as it improves the processing time.
  uint64_t PrevEndAddress = 0;
  for (const DWARFAddressRange &Range : InputRanges) {
    if (!containsAddress(Range.LowPC)) {
      LLVM_DEBUG(
          dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
                 << *this << " : [0x" << Twine::utohexstr(Range.LowPC) << ", 0x"
                 << Twine::utohexstr(Range.HighPC) << "]\n");
      PrevEndAddress = 0;
      continue;
    }
    uint64_t InputOffset = Range.LowPC - getAddress();
    const uint64_t InputEndOffset =
        std::min(Range.HighPC - getAddress(), getSize());

    auto BBI = std::upper_bound(
        BasicBlockOffsets.begin(), BasicBlockOffsets.end(),
        BasicBlockOffset(InputOffset, nullptr), CompareBasicBlockOffsets());
    --BBI;
    do {
      const BinaryBasicBlock *BB = BBI->second;
      if (InputOffset < BB->getOffset() || InputOffset >= BB->getEndOffset()) {
        LLVM_DEBUG(
            dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
                   << *this << " : [0x" << Twine::utohexstr(Range.LowPC)
                   << ", 0x" << Twine::utohexstr(Range.HighPC) << "]\n");
        PrevEndAddress = 0;
        break;
      }

      // Skip the range if the block was deleted.
      if (const uint64_t OutputStart = BB->getOutputAddressRange().first) {
        const uint64_t StartAddress =
            OutputStart + InputOffset - BB->getOffset();
        uint64_t EndAddress = BB->getOutputAddressRange().second;
        if (InputEndOffset < BB->getEndOffset())
          EndAddress = StartAddress + InputEndOffset - InputOffset;

        if (StartAddress == PrevEndAddress) {
          OutputRanges.back().HighPC =
              std::max(OutputRanges.back().HighPC, EndAddress);
        } else {
          OutputRanges.emplace_back(StartAddress,
                                    std::max(StartAddress, EndAddress));
        }
        PrevEndAddress = OutputRanges.back().HighPC;
      }

      InputOffset = BB->getEndOffset();
      ++BBI;
    } while (InputOffset < InputEndOffset);
  }

  // Post-processing pass to sort and merge ranges.
  std::sort(OutputRanges.begin(), OutputRanges.end());
  DebugAddressRangesVector MergedRanges;
  PrevEndAddress = 0;
  for (const DebugAddressRange &Range : OutputRanges) {
    if (Range.LowPC <= PrevEndAddress) {
      MergedRanges.back().HighPC =
          std::max(MergedRanges.back().HighPC, Range.HighPC);
    } else {
      MergedRanges.emplace_back(Range.LowPC, Range.HighPC);
    }
    PrevEndAddress = MergedRanges.back().HighPC;
  }

  return MergedRanges;
}

MCInst *BinaryFunction::getInstructionAtOffset(uint64_t Offset) {
  if (CurrentState == State::Disassembled) {
    auto II = Instructions.find(Offset);
    return (II == Instructions.end()) ? nullptr : &II->second;
  } else if (CurrentState == State::CFG) {
    BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
    if (!BB)
      return nullptr;

    for (MCInst &Inst : *BB) {
      constexpr uint32_t InvalidOffset = std::numeric_limits<uint32_t>::max();
      if (Offset == BC.MIB->getOffsetWithDefault(Inst, InvalidOffset))
        return &Inst;
    }

    if (MCInst *LastInstr = BB->getLastNonPseudoInstr()) {
      const uint32_t Size =
          BC.MIB->getAnnotationWithDefault<uint32_t>(*LastInstr, "Size");
      if (BB->getEndOffset() - Offset == Size)
        return LastInstr;
    }

    return nullptr;
  } else {
    llvm_unreachable("invalid CFG state to use getInstructionAtOffset()");
  }
}

DebugLocationsVector BinaryFunction::translateInputToOutputLocationList(
    const DebugLocationsVector &InputLL) const {
  DebugLocationsVector OutputLL;

  if (isFolded())
    return OutputLL;

  // If the function hasn't changed - there's nothing to update.
  if (!isEmitted())
    return InputLL;

  uint64_t PrevEndAddress = 0;
  SmallVectorImpl<uint8_t> *PrevExpr = nullptr;
  for (const DebugLocationEntry &Entry : InputLL) {
    const uint64_t Start = Entry.LowPC;
    const uint64_t End = Entry.HighPC;
    if (!containsAddress(Start)) {
      LLVM_DEBUG(dbgs() << "BOLT-DEBUG: invalid debug address range detected "
                           "for "
                        << *this << " : [0x" << Twine::utohexstr(Start)
                        << ", 0x" << Twine::utohexstr(End) << "]\n");
      continue;
    }
    uint64_t InputOffset = Start - getAddress();
    const uint64_t InputEndOffset = std::min(End - getAddress(), getSize());
    auto BBI = std::upper_bound(
        BasicBlockOffsets.begin(), BasicBlockOffsets.end(),
        BasicBlockOffset(InputOffset, nullptr), CompareBasicBlockOffsets());
    --BBI;
    do {
      const BinaryBasicBlock *BB = BBI->second;
      if (InputOffset < BB->getOffset() || InputOffset >= BB->getEndOffset()) {
        LLVM_DEBUG(dbgs() << "BOLT-DEBUG: invalid debug address range detected "
                             "for "
                          << *this << " : [0x" << Twine::utohexstr(Start)
                          << ", 0x" << Twine::utohexstr(End) << "]\n");
        PrevEndAddress = 0;
        break;
      }

      // Skip the range if the block was deleted.
      if (const uint64_t OutputStart = BB->getOutputAddressRange().first) {
        const uint64_t StartAddress =
            OutputStart + InputOffset - BB->getOffset();
        uint64_t EndAddress = BB->getOutputAddressRange().second;
        if (InputEndOffset < BB->getEndOffset())
          EndAddress = StartAddress + InputEndOffset - InputOffset;

        if (StartAddress == PrevEndAddress && Entry.Expr == *PrevExpr) {
          OutputLL.back().HighPC = std::max(OutputLL.back().HighPC, EndAddress);
        } else {
          OutputLL.emplace_back(DebugLocationEntry{
              StartAddress, std::max(StartAddress, EndAddress), Entry.Expr});
        }
        PrevEndAddress = OutputLL.back().HighPC;
        PrevExpr = &OutputLL.back().Expr;
      }

      ++BBI;
      InputOffset = BB->getEndOffset();
    } while (InputOffset < InputEndOffset);
  }

  // Sort and merge adjacent entries with identical location.
  std::stable_sort(
      OutputLL.begin(), OutputLL.end(),
      [](const DebugLocationEntry &A, const DebugLocationEntry &B) {
        return A.LowPC < B.LowPC;
      });
  DebugLocationsVector MergedLL;
  PrevEndAddress = 0;
  PrevExpr = nullptr;
  for (const DebugLocationEntry &Entry : OutputLL) {
    if (Entry.LowPC <= PrevEndAddress && *PrevExpr == Entry.Expr) {
      MergedLL.back().HighPC = std::max(Entry.HighPC, MergedLL.back().HighPC);
    } else {
      const uint64_t Begin = std::max(Entry.LowPC, PrevEndAddress);
      const uint64_t End = std::max(Begin, Entry.HighPC);
      MergedLL.emplace_back(DebugLocationEntry{Begin, End, Entry.Expr});
    }
    PrevEndAddress = MergedLL.back().HighPC;
    PrevExpr = &MergedLL.back().Expr;
  }

  return MergedLL;
}

void BinaryFunction::printLoopInfo(raw_ostream &OS) const {
  OS << "Loop Info for Function \"" << *this << "\"";
  if (hasValidProfile())
    OS << " (count: " << getExecutionCount() << ")";
  OS << "\n";

  std::stack<BinaryLoop *> St;
  for (auto I = BLI->begin(), E = BLI->end(); I != E; ++I)
    St.push(*I);
  while (!St.empty()) {
    BinaryLoop *L = St.top();
    St.pop();

    for (BinaryLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
      St.push(*I);

    if (!hasValidProfile())
      continue;

    OS << (L->getLoopDepth() > 1 ? "Nested" : "Outer")
       << " loop header: " << L->getHeader()->getName();
    OS << "\n";
    OS << "Loop basic blocks: ";
    const char *Sep = "";
    for (auto BI = L->block_begin(), BE = L->block_end(); BI != BE; ++BI) {
      OS << Sep << (*BI)->getName();
      Sep = ", ";
    }
    OS << "\n";
    if (hasValidProfile()) {
      OS << "Total back edge count: " << L->TotalBackEdgeCount << "\n";
      OS << "Loop entry count: " << L->EntryCount << "\n";
      OS << "Loop exit count: " << L->ExitCount << "\n";
      if (L->EntryCount > 0) {
        OS << "Average iters per entry: "
           << format("%.4lf", (double)L->TotalBackEdgeCount / L->EntryCount)
           << "\n";
      }
    }
    OS << "----\n";
  }

  OS << "Total number of loops: " << BLI->TotalLoops << "\n";
  OS << "Number of outer loops: " << BLI->OuterLoops << "\n";
  OS << "Maximum nested loop depth: " << BLI->MaximumDepth << "\n\n";
}

bool BinaryFunction::isAArch64Veneer() const {
  if (BasicBlocks.size() != 1)
    return false;

  BinaryBasicBlock &BB = **BasicBlocks.begin();
  if (BB.size() != 3)
    return false;

  for (MCInst &Inst : BB)
    if (!BC.MIB->hasAnnotation(Inst, "AArch64Veneer"))
      return false;

  return true;
}

} // namespace bolt
} // namespace llvm