BinaryContext.cpp

//===- bolt/Core/BinaryContext.cpp - Low-level context --------------------===//
//
// 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 BinaryContext class.
//
//===----------------------------------------------------------------------===//

#include"bolt/Core/BinaryContext.h"
#include"bolt/Core/BinaryEmitter.h"
#include"bolt/Core/BinaryFunction.h"
#include"bolt/Utils/CommandLineOpts.h"
#include"bolt/Utils/Utils.h"
#include"llvm/ADT/STLExtras.h"
#include"llvm/ADT/Twine.h"
#include"llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
#include"llvm/DebugInfo/DWARF/DWARFFormValue.h"
#include"llvm/DebugInfo/DWARF/DWARFUnit.h"
#include"llvm/MC/MCAssembler.h"
#include"llvm/MC/MCContext.h"
#include"llvm/MC/MCDisassembler/MCDisassembler.h"
#include"llvm/MC/MCInstPrinter.h"
#include"llvm/MC/MCObjectStreamer.h"
#include"llvm/MC/MCObjectWriter.h"
#include"llvm/MC/MCRegisterInfo.h"
#include"llvm/MC/MCSectionELF.h"
#include"llvm/MC/MCStreamer.h"
#include"llvm/MC/MCSubtargetInfo.h"
#include"llvm/MC/MCSymbol.h"
#include"llvm/Support/CommandLine.h"
#include"llvm/Support/Error.h"
#include"llvm/Support/Regex.h"
#include<algorithm>
#include<functional>
#include<iterator>
#include<unordered_set>

usingnamespacellvm;

#undef DEBUG_TYPE
#defineDEBUG_TYPE"bolt"

namespaceopts {

static cl::opt<bool>
NoHugePages("no-huge-pages",
cl::desc("use regular size pages for code alignment"),
 cl::Hidden, cl::cat(BoltCategory));

static cl::opt<bool>
PrintDebugInfo("print-debug-info",
cl::desc("print debug info when printing functions"),
 cl::Hidden,
 cl::ZeroOrMore,
 cl::cat(BoltCategory));

cl::opt<bool> PrintRelocations(
"print-relocations",
cl::desc("print relocations when printing functions/objects"), cl::Hidden,
 cl::cat(BoltCategory));

static cl::opt<bool>
PrintMemData("print-mem-data",
cl::desc("print memory data annotations when printing functions"),
 cl::Hidden,
 cl::ZeroOrMore,
 cl::cat(BoltCategory));

cl::opt<std::string> CompDirOverride(
"comp-dir-override",
cl::desc("overrides DW_AT_comp_dir, and provides an alternative base "
"location, which is used with DW_AT_dwo_name to construct a path "
"to *.dwo files."),
 cl::Hidden, cl::init(""), cl::cat(BoltCategory));
} // namespace opts

namespacellvm {
namespacebolt {

char BOLTError::ID = 0;

BOLTError::BOLTError(bool IsFatal, const Twine &S)
 : IsFatal(IsFatal), Msg(S.str()) {}

voidBOLTError::log(raw_ostream &OS) const {
if (IsFatal)
 OS << "FATAL ";
 StringRef ErrMsg = StringRef(Msg);
// Prepend our error prefix if it is missing
if (ErrMsg.empty()) {
 OS << "BOLT-ERROR\n";
 } else {
if (!ErrMsg.starts_with("BOLT-ERROR"))
 OS << "BOLT-ERROR: ";
 OS << ErrMsg << "\n";
 }
}

std::error_code BOLTError::convertToErrorCode() const {
returninconvertibleErrorCode();
}

Error createNonFatalBOLTError(const Twine &S) {
return make_error<BOLTError>(/*IsFatal*/false, S);
}

Error createFatalBOLTError(const Twine &S) {
return make_error<BOLTError>(/*IsFatal*/true, S);
}

voidBinaryContext::logBOLTErrorsAndQuitOnFatal(Error E) {
handleAllErrors(Error(std::move(E)), [&](const BOLTError &E) {
if (!E.getMessage().empty())
 E.log(this->errs());
if (E.isFatal())
exit(1);
 });
}

BinaryContext::BinaryContext(std::unique_ptr<MCContext> Ctx,
 std::unique_ptr<DWARFContext> DwCtx,
 std::unique_ptr<Triple> TheTriple,
 std::shared_ptr<orc::SymbolStringPool> SSP,
const Target *TheTarget, std::string TripleName,
 std::unique_ptr<MCCodeEmitter> MCE,
 std::unique_ptr<MCObjectFileInfo> MOFI,
 std::unique_ptr<const MCAsmInfo> AsmInfo,
 std::unique_ptr<const MCInstrInfo> MII,
 std::unique_ptr<const MCSubtargetInfo> STI,
 std::unique_ptr<MCInstPrinter> InstPrinter,
 std::unique_ptr<const MCInstrAnalysis> MIA,
 std::unique_ptr<MCPlusBuilder> MIB,
 std::unique_ptr<const MCRegisterInfo> MRI,
 std::unique_ptr<MCDisassembler> DisAsm,
 JournalingStreams Logger)
 : Ctx(std::move(Ctx)), DwCtx(std::move(DwCtx)),
TheTriple(std::move(TheTriple)), SSP(std::move(SSP)),
 TheTarget(TheTarget), TripleName(TripleName), MCE(std::move(MCE)),
 MOFI(std::move(MOFI)), AsmInfo(std::move(AsmInfo)), MII(std::move(MII)),
 STI(std::move(STI)), InstPrinter(std::move(InstPrinter)),
 MIA(std::move(MIA)), MIB(std::move(MIB)), MRI(std::move(MRI)),
 DisAsm(std::move(DisAsm)), Logger(Logger), InitialDynoStats(isAArch64()) {
 RegularPageSize = isAArch64() ? RegularPageSizeAArch64 : RegularPageSizeX86;
 PageAlign = opts::NoHugePages ? RegularPageSize : HugePageSize;
}

BinaryContext::~BinaryContext() {
for (BinarySection *Section : Sections)
delete Section;
for (BinaryFunction *InjectedFunction : InjectedBinaryFunctions)
delete InjectedFunction;
for (std::pair<constuint64_t, JumpTable *> JTI : JumpTables)
delete JTI.second;
clearBinaryData();
}

/// Create BinaryContext for a given architecture \p ArchName and
/// triple \p TripleName.
Expected<std::unique_ptr<BinaryContext>> BinaryContext::createBinaryContext(
 Triple TheTriple, std::shared_ptr<orc::SymbolStringPool> SSP,
 StringRef InputFileName, SubtargetFeatures *Features, bool IsPIC,
 std::unique_ptr<DWARFContext> DwCtx, JournalingStreams Logger) {
 StringRef ArchName = "";
 std::string FeaturesStr = "";
switch (TheTriple.getArch()) {
case llvm::Triple::x86_64:
if (Features)
returncreateFatalBOLTError(
"x86_64 target does not use SubtargetFeatures");
 ArchName = "x86-64";
 FeaturesStr = "+nopl";
break;
case llvm::Triple::aarch64:
if (Features)
returncreateFatalBOLTError(
"AArch64 target does not use SubtargetFeatures");
 ArchName = "aarch64";
 FeaturesStr = "+all";
break;
case llvm::Triple::riscv64: {
 ArchName = "riscv64";
if (!Features)
returncreateFatalBOLTError("RISCV target needs SubtargetFeatures");
// We rely on relaxation for some transformations (e.g., promoting all calls
// to PseudoCALL and then making JITLink relax them). Since the relax
// feature is not stored in the object file, we manually enable it.
 Features->AddFeature("relax");
 FeaturesStr = Features->getString();
break;
 }
default:
returncreateStringError(std::errc::not_supported,
"BOLT-ERROR: Unrecognized machine in ELF file");
 }

const std::string TripleName = TheTriple.str();

 std::string Error;
const Target *TheTarget =
TargetRegistry::lookupTarget(std::string(ArchName), TheTriple, Error);
if (!TheTarget)
returncreateStringError(make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: ", Error));

 std::unique_ptr<const MCRegisterInfo> MRI(
 TheTarget->createMCRegInfo(TripleName));
if (!MRI)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no register info for target ", TripleName));

// Set up disassembler.
 std::unique_ptr<MCAsmInfo> AsmInfo(
 TheTarget->createMCAsmInfo(*MRI, TripleName, MCTargetOptions()));
if (!AsmInfo)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no assembly info for target ", TripleName));
// BOLT creates "func@PLT" symbols for PLT entries. In function assembly dump
// we want to emit such names as using @PLT without double quotes to convey
// variant kind to the assembler. BOLT doesn't rely on the linker so we can
// override the default AsmInfo behavior to emit names the way we want.
 AsmInfo->setAllowAtInName(true);

 std::unique_ptr<const MCSubtargetInfo> STI(
 TheTarget->createMCSubtargetInfo(TripleName, "", FeaturesStr));
if (!STI)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no subtarget info for target ", TripleName));

 std::unique_ptr<const MCInstrInfo> MII(TheTarget->createMCInstrInfo());
if (!MII)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no instruction info for target ", TripleName));

 std::unique_ptr<MCContext> Ctx(
newMCContext(TheTriple, AsmInfo.get(), MRI.get(), STI.get()));
 std::unique_ptr<MCObjectFileInfo> MOFI(
 TheTarget->createMCObjectFileInfo(*Ctx, IsPIC));
 Ctx->setObjectFileInfo(MOFI.get());
// We do not support X86 Large code model. Change this in the future.
bool Large = false;
if (TheTriple.getArch() == llvm::Triple::aarch64)
 Large = true;
unsigned LSDAEncoding =
 Large ? dwarf::DW_EH_PE_absptr : dwarf::DW_EH_PE_udata4;
if (IsPIC) {
 LSDAEncoding = dwarf::DW_EH_PE_pcrel |
 (Large ? dwarf::DW_EH_PE_sdata8 : dwarf::DW_EH_PE_sdata4);
 }

 std::unique_ptr<MCDisassembler> DisAsm(
 TheTarget->createMCDisassembler(*STI, *Ctx));

if (!DisAsm)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no disassembler info for target ", TripleName));

 std::unique_ptr<const MCInstrAnalysis> MIA(
 TheTarget->createMCInstrAnalysis(MII.get()));
if (!MIA)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: failed to create instruction analysis for target ",
 TripleName));

int AsmPrinterVariant = AsmInfo->getAssemblerDialect();
 std::unique_ptr<MCInstPrinter> InstructionPrinter(
 TheTarget->createMCInstPrinter(TheTriple, AsmPrinterVariant, *AsmInfo,
 *MII, *MRI));
if (!InstructionPrinter)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no instruction printer for target ", TripleName));
 InstructionPrinter->setPrintImmHex(true);

 std::unique_ptr<MCCodeEmitter> MCE(
 TheTarget->createMCCodeEmitter(*MII, *Ctx));

auto BC = std::make_unique<BinaryContext>(
std::move(Ctx), std::move(DwCtx), std::make_unique<Triple>(TheTriple),
std::move(SSP), TheTarget, std::string(TripleName), std::move(MCE),
std::move(MOFI), std::move(AsmInfo), std::move(MII), std::move(STI),
std::move(InstructionPrinter), std::move(MIA), nullptr, std::move(MRI),
std::move(DisAsm), Logger);

 BC->LSDAEncoding = LSDAEncoding;

 BC->MAB = std::unique_ptr<MCAsmBackend>(
 BC->TheTarget->createMCAsmBackend(*BC->STI, *BC->MRI, MCTargetOptions()));

 BC->setFilename(InputFileName);

 BC->HasFixedLoadAddress = !IsPIC;

 BC->SymbolicDisAsm = std::unique_ptr<MCDisassembler>(
 BC->TheTarget->createMCDisassembler(*BC->STI, *BC->Ctx));

if (!BC->SymbolicDisAsm)
returncreateStringError(
make_error_code(std::errc::not_supported),
Twine("BOLT-ERROR: no disassembler info for target ", TripleName));

returnstd::move(BC);
}

boolBinaryContext::forceSymbolRelocations(StringRef SymbolName) const {
if (opts::HotText &&
 (SymbolName == "__hot_start" || SymbolName == "__hot_end"))
returntrue;

if (opts::HotData &&
 (SymbolName == "__hot_data_start" || SymbolName == "__hot_data_end"))
returntrue;

if (SymbolName == "_end")
returntrue;

returnfalse;
}

std::unique_ptr<MCObjectWriter>
BinaryContext::createObjectWriter(raw_pwrite_stream &OS) {
return MAB->createObjectWriter(OS);
}

boolBinaryContext::validateObjectNesting() const {
auto Itr = BinaryDataMap.begin();
auto End = BinaryDataMap.end();
bool Valid = true;
while (Itr != End) {
auto Next = std::next(Itr);
while (Next != End &&
 Itr->second->getSection() == Next->second->getSection() &&
 Itr->second->containsRange(Next->second->getAddress(),
 Next->second->getSize())) {
if (Next->second->Parent != Itr->second) {
this->errs() << "BOLT-WARNING: object nesting incorrect for:\n"
 << "BOLT-WARNING: " << *Itr->second << "\n"
 << "BOLT-WARNING: " << *Next->second << "\n";
 Valid = false;
 }
 ++Next;
 }
 Itr = Next;
 }
return Valid;
}

boolBinaryContext::validateHoles() const {
bool Valid = true;
for (BinarySection &Section : sections()) {
for (const Relocation &Rel : Section.relocations()) {
uint64_t RelAddr = Rel.Offset + Section.getAddress();
const BinaryData *BD = getBinaryDataContainingAddress(RelAddr);
if (!BD) {
this->errs()
 << "BOLT-WARNING: no BinaryData found for relocation at address"
 << " 0x" << Twine::utohexstr(RelAddr) << " in " << Section.getName()
 << "\n";
 Valid = false;
 } elseif (!BD->getAtomicRoot()) {
this->errs()
 << "BOLT-WARNING: no atomic BinaryData found for relocation at "
 << "address 0x" << Twine::utohexstr(RelAddr) << " in "
 << Section.getName() << "\n";
 Valid = false;
 }
 }
 }
return Valid;
}

voidBinaryContext::updateObjectNesting(BinaryDataMapType::iterator GAI) {
constuint64_t Address = GAI->second->getAddress();
constuint64_tSize = GAI->second->getSize();

auto fixParents = [&](BinaryDataMapType::iterator Itr,
 BinaryData *NewParent) {
 BinaryData *OldParent = Itr->second->Parent;
 Itr->second->Parent = NewParent;
 ++Itr;
while (Itr != BinaryDataMap.end() && OldParent &&
 Itr->second->Parent == OldParent) {
 Itr->second->Parent = NewParent;
 ++Itr;
 }
 };

// Check if the previous symbol contains the newly added symbol.
if (GAI != BinaryDataMap.begin()) {
 BinaryData *Prev = std::prev(GAI)->second;
while (Prev) {
if (Prev->getSection() == GAI->second->getSection() &&
 Prev->containsRange(Address, Size)) {
fixParents(GAI, Prev);
 } else {
fixParents(GAI, nullptr);
 }
 Prev = Prev->Parent;
 }
 }

// Check if the newly added symbol contains any subsequent symbols.
if (Size != 0) {
 BinaryData *BD = GAI->second->Parent ? GAI->second->Parent : GAI->second;
auto Itr = std::next(GAI);
while (
 Itr != BinaryDataMap.end() &&
 BD->containsRange(Itr->second->getAddress(), Itr->second->getSize())) {
 Itr->second->Parent = BD;
 ++Itr;
 }
 }
}

iterator_range<BinaryContext::binary_data_iterator>
BinaryContext::getSubBinaryData(BinaryData *BD) {
auto Start = std::next(BinaryDataMap.find(BD->getAddress()));
auto End = Start;
while (End != BinaryDataMap.end() && BD->isAncestorOf(End->second))
 ++End;
returnmake_range(Start, End);
}

std::pair<const MCSymbol *, uint64_t>
BinaryContext::handleAddressRef(uint64_t Address, BinaryFunction &BF,
bool IsPCRel) {
if (isAArch64()) {
// Check if this is an access to a constant island and create bookkeeping
// to keep track of it and emit it later as part of this function.
if (MCSymbol *IslandSym = BF.getOrCreateIslandAccess(Address))
returnstd::make_pair(IslandSym, 0);

// Detect custom code written in assembly that refers to arbitrary
// constant islands from other functions. Write this reference so we
// can pull this constant island and emit it as part of this function
// too.
auto IslandIter = AddressToConstantIslandMap.lower_bound(Address);

if (IslandIter != AddressToConstantIslandMap.begin() &&
 (IslandIter == AddressToConstantIslandMap.end() ||
 IslandIter->first > Address))
 --IslandIter;

if (IslandIter != AddressToConstantIslandMap.end()) {
// Fall-back to referencing the original constant island in the presence
// of dynamic relocs, as we currently do not support cloning them.
// Notice: we might fail to link because of this, if the original constant
// island we are referring would be emitted too far away.
if (IslandIter->second->hasDynamicRelocationAtIsland()) {
 MCSymbol *IslandSym =
 IslandIter->second->getOrCreateIslandAccess(Address);
if (IslandSym)
returnstd::make_pair(IslandSym, 0);
 } elseif (MCSymbol *IslandSym =
 IslandIter->second->getOrCreateProxyIslandAccess(Address,
 BF)) {
 BF.createIslandDependency(IslandSym, IslandIter->second);
returnstd::make_pair(IslandSym, 0);
 }
 }
 }

// Note that the address does not necessarily have to reside inside
// a section, it could be an absolute address too.
 ErrorOr<BinarySection &> Section = getSectionForAddress(Address);
if (Section && Section->isText()) {
if (BF.containsAddress(Address, /*UseMaxSize=*/isAArch64())) {
if (Address != BF.getAddress()) {
// The address could potentially escape. Mark it as another entry
// point into the function.
if (opts::Verbosity >= 1) {
this->outs() << "BOLT-INFO: potentially escaped address 0x"
 << Twine::utohexstr(Address) << " in function " << BF
 << '\n';
 }
 BF.HasInternalLabelReference = true;
returnstd::make_pair(
 BF.addEntryPointAtOffset(Address - BF.getAddress()), 0);
 }
 } else {
addInterproceduralReference(&BF, Address);
 }
 }

// With relocations, catch jump table references outside of the basic block
// containing the indirect jump.
if (HasRelocations) {
const MemoryContentsType MemType = analyzeMemoryAt(Address, BF);
if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE && IsPCRel) {
const MCSymbol *Symbol =
getOrCreateJumpTable(BF, Address, JumpTable::JTT_PIC);

returnstd::make_pair(Symbol, 0);
 }
 }

if (BinaryData *BD = getBinaryDataContainingAddress(Address))
returnstd::make_pair(BD->getSymbol(), Address - BD->getAddress());

// TODO: use DWARF info to get size/alignment here?
 MCSymbol *TargetSymbol = getOrCreateGlobalSymbol(Address, "DATAat");
LLVM_DEBUG(dbgs() << "Created symbol " << TargetSymbol->getName() << '\n');
returnstd::make_pair(TargetSymbol, 0);
}

MemoryContentsType BinaryContext::analyzeMemoryAt(uint64_t Address,
 BinaryFunction &BF) {
if (!isX86())
return MemoryContentsType::UNKNOWN;

 ErrorOr<BinarySection &> Section = getSectionForAddress(Address);
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) {
this->errs() << "BOLT-WARNING: no section for address 0x"
 << Twine::utohexstr(Address) << " referenced from function "
 << BF << '\n';
 }
return MemoryContentsType::UNKNOWN;
 }

if (Section->isVirtual()) {
// The contents are filled at runtime.
return MemoryContentsType::UNKNOWN;
 }

// No support for jump tables in code yet.
if (Section->isText())
return MemoryContentsType::UNKNOWN;

// Start with checking for PIC jump table. We expect non-PIC jump tables
// to have high 32 bits set to 0.
if (analyzeJumpTable(Address, JumpTable::JTT_PIC, BF))
return MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE;

if (analyzeJumpTable(Address, JumpTable::JTT_NORMAL, BF))
return MemoryContentsType::POSSIBLE_JUMP_TABLE;

return MemoryContentsType::UNKNOWN;
}

boolBinaryContext::analyzeJumpTable(constuint64_t Address,
const JumpTable::JumpTableType Type,
const BinaryFunction &BF,
constuint64_t NextJTAddress,
 JumpTable::AddressesType *EntriesAsAddress,
bool *HasEntryInFragment) const {
// Target address of __builtin_unreachable.
constuint64_t UnreachableAddress = BF.getAddress() + BF.getSize();

// Is one of the targets __builtin_unreachable?
bool HasUnreachable = false;

// Does one of the entries match function start address?
bool HasStartAsEntry = false;

// Number of targets other than __builtin_unreachable.
uint64_t NumRealEntries = 0;

// Size of the jump table without trailing __builtin_unreachable entries.
size_t TrimmedSize = 0;

auto addEntryAddress = [&](uint64_t EntryAddress, bool Unreachable = false) {
if (!EntriesAsAddress)
return;
 EntriesAsAddress->emplace_back(EntryAddress);
if (!Unreachable)
 TrimmedSize = EntriesAsAddress->size();
 };

auto printEntryDiagnostics = [&](raw_ostream &OS,
const BinaryFunction *TargetBF) {
 OS << "FAIL: function doesn't contain this address\n";
if (!TargetBF)
return;
 OS << " ! function containing this address: " << *TargetBF << '\n';
if (!TargetBF->isFragment())
return;
 OS << " ! is a fragment with parents: ";
 ListSeparator LS;
for (BinaryFunction *Parent : TargetBF->ParentFragments)
 OS << LS << *Parent;
 OS << '\n';
 };

 ErrorOr<const BinarySection &> Section = getSectionForAddress(Address);
if (!Section)
returnfalse;

// The upper bound is defined by containing object, section limits, and
// the next jump table in memory.
uint64_t UpperBound = Section->getEndAddress();
const BinaryData *JumpTableBD = getBinaryDataAtAddress(Address);
if (JumpTableBD && JumpTableBD->getSize()) {
assert(JumpTableBD->getEndAddress() <= UpperBound &&
"data object cannot cross a section boundary");
 UpperBound = JumpTableBD->getEndAddress();
 }
if (NextJTAddress)
 UpperBound = std::min(NextJTAddress, UpperBound);

LLVM_DEBUG({
using JTT = JumpTable::JumpTableType;
dbgs() << formatv("BOLT-DEBUG: analyzeJumpTable @{0:x} in {1}, JTT={2}\n",
 Address, BF.getPrintName(),
 Type == JTT::JTT_PIC ? "PIC" : "Normal");
 });
constuint64_t EntrySize = getJumpTableEntrySize(Type);
for (uint64_t EntryAddress = Address; EntryAddress <= UpperBound - EntrySize;
 EntryAddress += EntrySize) {
LLVM_DEBUG(dbgs() << " * Checking 0x" << Twine::utohexstr(EntryAddress)
 << " -> ");
// Check if there's a proper relocation against the jump table entry.
if (HasRelocations) {
if (Type == JumpTable::JTT_PIC &&
 !DataPCRelocations.count(EntryAddress)) {
LLVM_DEBUG(
dbgs() << "FAIL: JTT_PIC table, no relocation for this address\n");
break;
 }
if (Type == JumpTable::JTT_NORMAL && !getRelocationAt(EntryAddress)) {
LLVM_DEBUG(
dbgs()
 << "FAIL: JTT_NORMAL table, no relocation for this address\n");
break;
 }
 }

constuint64_t Value =
 (Type == JumpTable::JTT_PIC)
 ? Address + *getSignedValueAtAddress(EntryAddress, EntrySize)
 : *getPointerAtAddress(EntryAddress);

// __builtin_unreachable() case.
if (Value == UnreachableAddress) {
addEntryAddress(Value, /*Unreachable*/true);
 HasUnreachable = true;
LLVM_DEBUG(dbgs() << formatv("OK: {0:x} __builtin_unreachable\n", Value));
continue;
 }

// Function start is another special case. It is allowed in the jump table,
// but we need at least one another regular entry to distinguish the table
// from, e.g. a function pointer array.
if (Value == BF.getAddress()) {
 HasStartAsEntry = true;
addEntryAddress(Value);
continue;
 }

// Function or one of its fragments.
const BinaryFunction *TargetBF = getBinaryFunctionContainingAddress(Value);
if (!TargetBF || !areRelatedFragments(TargetBF, &BF)) {
LLVM_DEBUG(printEntryDiagnostics(dbgs(), TargetBF));
 (void)printEntryDiagnostics;
break;
 }

// Check there's an instruction at this offset.
if (TargetBF->getState() == BinaryFunction::State::Disassembled &&
 !TargetBF->getInstructionAtOffset(Value - TargetBF->getAddress())) {
LLVM_DEBUG(dbgs() << formatv("FAIL: no instruction at {0:x}\n", Value));
break;
 }

 ++NumRealEntries;
LLVM_DEBUG(dbgs() << formatv("OK: {0:x} real entry\n", Value));

if (TargetBF != &BF && HasEntryInFragment)
 *HasEntryInFragment = true;
addEntryAddress(Value);
 }

// Trim direct/normal jump table to exclude trailing unreachable entries that
// can collide with a function address.
if (Type == JumpTable::JTT_NORMAL && EntriesAsAddress &&
 TrimmedSize != EntriesAsAddress->size() &&
getBinaryFunctionAtAddress(UnreachableAddress))
 EntriesAsAddress->resize(TrimmedSize);

// It's a jump table if the number of real entries is more than 1, or there's
// one real entry and one or more special targets. If there are only multiple
// special targets, then it's not a jump table.
return NumRealEntries + (HasUnreachable || HasStartAsEntry) >= 2;
}

voidBinaryContext::populateJumpTables() {
LLVM_DEBUG(dbgs() << "DataPCRelocations: " << DataPCRelocations.size()
 << '\n');
for (auto JTI = JumpTables.begin(), JTE = JumpTables.end(); JTI != JTE;
 ++JTI) {
 JumpTable *JT = JTI->second;

if (!llvm::all_of(JT->Parents, std::mem_fn(&BinaryFunction::isSimple)))
continue;

uint64_t NextJTAddress = 0;
auto NextJTI = std::next(JTI);
if (NextJTI != JTE)
 NextJTAddress = NextJTI->second->getAddress();

constbool Success =
analyzeJumpTable(JT->getAddress(), JT->Type, *(JT->Parents[0]),
 NextJTAddress, &JT->EntriesAsAddress, &JT->IsSplit);
if (!Success) {
LLVM_DEBUG({
dbgs() << "failed to analyze ";
 JT->print(dbgs());
if (NextJTI != JTE) {
dbgs() << "next ";
 NextJTI->second->print(dbgs());
 }
 });
llvm_unreachable("jump table heuristic failure");
 }
for (BinaryFunction *Frag : JT->Parents) {
if (JT->IsSplit)
 Frag->setHasIndirectTargetToSplitFragment(true);
for (uint64_t EntryAddress : JT->EntriesAsAddress)
// if target is builtin_unreachable
if (EntryAddress == Frag->getAddress() + Frag->getSize()) {
 Frag->IgnoredBranches.emplace_back(EntryAddress - Frag->getAddress(),
 Frag->getSize());
 } elseif (EntryAddress >= Frag->getAddress() &&
 EntryAddress < Frag->getAddress() + Frag->getSize()) {
 Frag->registerReferencedOffset(EntryAddress - Frag->getAddress());
 }
 }

// In strict mode, erase PC-relative relocation record. Later we check that
// all such records are erased and thus have been accounted for.
if (opts::StrictMode && JT->Type == JumpTable::JTT_PIC) {
for (uint64_t Address = JT->getAddress();
 Address < JT->getAddress() + JT->getSize();
 Address += JT->EntrySize) {
 DataPCRelocations.erase(DataPCRelocations.find(Address));
 }
 }

// Mark to skip the function and all its fragments.
for (BinaryFunction *Frag : JT->Parents)
if (Frag->hasIndirectTargetToSplitFragment())
addFragmentsToSkip(Frag);
 }

if (opts::StrictMode && DataPCRelocations.size()) {
LLVM_DEBUG({
dbgs() << DataPCRelocations.size()
 << " unclaimed PC-relative relocations left in data:\n";
for (uint64_t Reloc : DataPCRelocations)
dbgs() << Twine::utohexstr(Reloc) << '\n';
 });
assert(0 && "unclaimed PC-relative relocations left in data\n");
 }
clearList(DataPCRelocations);
}

voidBinaryContext::skipMarkedFragments() {
 std::vector<BinaryFunction *> FragmentQueue;
// Copy the functions to FragmentQueue.
 FragmentQueue.assign(FragmentsToSkip.begin(), FragmentsToSkip.end());
auto addToWorklist = [&](BinaryFunction *Function) -> void {
if (FragmentsToSkip.count(Function))
return;
 FragmentQueue.push_back(Function);
addFragmentsToSkip(Function);
 };
// Functions containing split jump tables need to be skipped with all
// fragments (transitively).
for (size_t I = 0; I != FragmentQueue.size(); I++) {
 BinaryFunction *BF = FragmentQueue[I];
assert(FragmentsToSkip.count(BF) &&
"internal error in traversing function fragments");
if (opts::Verbosity >= 1)
this->errs() << "BOLT-WARNING: Ignoring " << BF->getPrintName() << '\n';
 BF->setSimple(false);
 BF->setHasIndirectTargetToSplitFragment(true);

llvm::for_each(BF->Fragments, addToWorklist);
llvm::for_each(BF->ParentFragments, addToWorklist);
 }
if (!FragmentsToSkip.empty())
this->errs() << "BOLT-WARNING: skipped " << FragmentsToSkip.size()
 << " function" << (FragmentsToSkip.size() == 1 ? "" : "s")
 << " due to cold fragments\n";
}

MCSymbol *BinaryContext::getOrCreateGlobalSymbol(uint64_t Address, Twine Prefix,
uint64_tSize,
uint16_t Alignment,
unsigned Flags) {
auto Itr = BinaryDataMap.find(Address);
if (Itr != BinaryDataMap.end()) {
assert(Itr->second->getSize() == Size || !Size);
return Itr->second->getSymbol();
 }

 std::string Name = (Prefix + "0x" + Twine::utohexstr(Address)).str();
assert(!GlobalSymbols.count(Name) && "created name is not unique");
returnregisterNameAtAddress(Name, Address, Size, Alignment, Flags);
}

MCSymbol *BinaryContext::getOrCreateUndefinedGlobalSymbol(StringRef Name) {
return Ctx->getOrCreateSymbol(Name);
}

BinaryFunction *BinaryContext::createBinaryFunction(
const std::string &Name, BinarySection &Section, uint64_t Address,
uint64_tSize, uint64_t SymbolSize, uint16_t Alignment) {
auto Result = BinaryFunctions.emplace(
 Address, BinaryFunction(Name, Section, Address, Size, *this));
assert(Result.second == true && "unexpected duplicate function");
 BinaryFunction *BF = &Result.first->second;
registerNameAtAddress(Name, Address, SymbolSize ? SymbolSize : Size,
 Alignment);
setSymbolToFunctionMap(BF->getSymbol(), BF);
return BF;
}

const MCSymbol *
BinaryContext::getOrCreateJumpTable(BinaryFunction &Function, uint64_t Address,
 JumpTable::JumpTableType Type) {
// Two fragments of same function access same jump table
if (JumpTable *JT = getJumpTableContainingAddress(Address)) {
assert(JT->Type == Type && "jump table types have to match");
assert(Address == JT->getAddress() && "unexpected non-empty jump table");

if (llvm::is_contained(JT->Parents, &Function))
return JT->getFirstLabel();

// Prevent associating a jump table to a specific fragment twice.
auto isSibling = std::bind(&BinaryContext::areRelatedFragments, this,
 &Function, std::placeholders::_1);
assert(llvm::all_of(JT->Parents, isSibling) &&
"cannot re-use jump table of a different function");
 (void)isSibling;
if (opts::Verbosity > 2) {
this->outs() << "BOLT-INFO: multiple fragments access the same jump table"
 << ": " << *JT->Parents[0] << "; " << Function << '\n';
 JT->print(this->outs());
 }
if (JT->Parents.size() == 1)
 JT->Parents.front()->setHasIndirectTargetToSplitFragment(true);
 Function.setHasIndirectTargetToSplitFragment(true);
// Duplicate the entry for the parent function for easy access
 JT->Parents.push_back(&Function);
 Function.JumpTables.emplace(Address, JT);
return JT->getFirstLabel();
 }

// Re-use the existing symbol if possible.
 MCSymbol *JTLabel = nullptr;
if (BinaryData *Object = getBinaryDataAtAddress(Address)) {
if (!isInternalSymbolName(Object->getSymbol()->getName()))
 JTLabel = Object->getSymbol();
 }

constuint64_t EntrySize = getJumpTableEntrySize(Type);
if (!JTLabel) {
const std::string JumpTableName = generateJumpTableName(Function, Address);
 JTLabel = registerNameAtAddress(JumpTableName, Address, 0, EntrySize);
 }

LLVM_DEBUG(dbgs() << "BOLT-DEBUG: creating jump table " << JTLabel->getName()
 << " in function " << Function << '\n');

 JumpTable *JT = newJumpTable(*JTLabel, Address, EntrySize, Type,
 JumpTable::LabelMapType{{0, JTLabel}},
 *getSectionForAddress(Address));
 JT->Parents.push_back(&Function);
if (opts::Verbosity > 2)
 JT->print(this->outs());
 JumpTables.emplace(Address, JT);

// Duplicate the entry for the parent function for easy access.
 Function.JumpTables.emplace(Address, JT);
return JTLabel;
}

std::pair<uint64_t, const MCSymbol *>
BinaryContext::duplicateJumpTable(BinaryFunction &Function, JumpTable *JT,
const MCSymbol *OldLabel) {
auto L = scopeLock();
unsigned Offset = 0;
bool Found = false;
for (std::pair<constunsigned, MCSymbol *> Elmt : JT->Labels) {
if (Elmt.second != OldLabel)
continue;
 Offset = Elmt.first;
 Found = true;
break;
 }
assert(Found && "Label not found");
 (void)Found;
 MCSymbol *NewLabel = Ctx->createNamedTempSymbol("duplicatedJT");
 JumpTable *NewJT =
newJumpTable(*NewLabel, JT->getAddress(), JT->EntrySize, JT->Type,
 JumpTable::LabelMapType{{Offset, NewLabel}},
 *getSectionForAddress(JT->getAddress()));
 NewJT->Parents = JT->Parents;
 NewJT->Entries = JT->Entries;
 NewJT->Counts = JT->Counts;
uint64_t JumpTableID = ++DuplicatedJumpTables;
// Invert it to differentiate from regular jump tables whose IDs are their
// addresses in the input binary memory space
 JumpTableID = ~JumpTableID;
 JumpTables.emplace(JumpTableID, NewJT);
 Function.JumpTables.emplace(JumpTableID, NewJT);
returnstd::make_pair(JumpTableID, NewLabel);
}

std::string BinaryContext::generateJumpTableName(const BinaryFunction &BF,
uint64_t Address) {
size_t Id;
uint64_t Offset = 0;
if (const JumpTable *JT = BF.getJumpTableContainingAddress(Address)) {
 Offset = Address - JT->getAddress();
auto JTLabelsIt = JT->Labels.find(Offset);
if (JTLabelsIt != JT->Labels.end())
returnstd::string(JTLabelsIt->second->getName());

auto JTIdsIt = JumpTableIds.find(JT->getAddress());
assert(JTIdsIt != JumpTableIds.end());
 Id = JTIdsIt->second;
 } else {
 Id = JumpTableIds[Address] = BF.JumpTables.size();
 }
return ("JUMP_TABLE/" + BF.getOneName().str() + "." + std::to_string(Id) +
 (Offset ? ("." + std::to_string(Offset)) : ""));
}

boolBinaryContext::hasValidCodePadding(const BinaryFunction &BF) {
// FIXME: aarch64 support is missing.
if (!isX86())
returntrue;

if (BF.getSize() == BF.getMaxSize())
returntrue;

 ErrorOr<ArrayRef<unsignedchar>> FunctionData = BF.getData();
assert(FunctionData && "cannot get function as data");

uint64_t Offset = BF.getSize();
 MCInst Instr;
uint64_t InstrSize = 0;
uint64_t InstrAddress = BF.getAddress() + Offset;
using std::placeholders::_1;

// Skip instructions that satisfy the predicate condition.
auto skipInstructions = [&](std::function<bool(const MCInst &)> Predicate) {
constuint64_t StartOffset = Offset;
for (; Offset < BF.getMaxSize();
 Offset += InstrSize, InstrAddress += InstrSize) {
if (!DisAsm->getInstruction(Instr, InstrSize, FunctionData->slice(Offset),
 InstrAddress, nulls()))
break;
if (!Predicate(Instr))
break;
 }

return Offset - StartOffset;
 };

// Skip a sequence of zero bytes.
auto skipZeros = [&]() {
constuint64_t StartOffset = Offset;
for (; Offset < BF.getMaxSize(); ++Offset)
if ((*FunctionData)[Offset] != 0)
break;

return Offset - StartOffset;
 };

// Accept the whole padding area filled with breakpoints.
auto isBreakpoint = std::bind(&MCPlusBuilder::isBreakpoint, MIB.get(), _1);
if (skipInstructions(isBreakpoint) && Offset == BF.getMaxSize())
returntrue;

auto isNoop = std::bind(&MCPlusBuilder::isNoop, MIB.get(), _1);

// Some functions have a jump to the next function or to the padding area
// inserted after the body.
auto isSkipJump = [&](const MCInst &Instr) {
uint64_t TargetAddress = 0;
if (MIB->isUnconditionalBranch(Instr) &&
 MIB->evaluateBranch(Instr, InstrAddress, InstrSize, TargetAddress)) {
if (TargetAddress >= InstrAddress + InstrSize &&
 TargetAddress <= BF.getAddress() + BF.getMaxSize()) {
returntrue;