/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

Bug Summary

File:	llvm/lib/ExecutionEngine/JITLink/JITLink.cpp
Warning:	line 176, column 62 Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name JITLink.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/ExecutionEngine/JITLink -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/ExecutionEngine/JITLink -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/ExecutionEngine/JITLink -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/ExecutionEngine/JITLink -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

→

1//===------------- JITLink.cpp - Core Run-time JIT linker APIs ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//

9#include "llvm/ExecutionEngine/JITLink/JITLink.h"

11#include "llvm/BinaryFormat/Magic.h"
12#include "llvm/ExecutionEngine/JITLink/ELF.h"
13#include "llvm/ExecutionEngine/JITLink/MachO.h"
14#include "llvm/Support/Format.h"
15#include "llvm/Support/ManagedStatic.h"
16#include "llvm/Support/MemoryBuffer.h"
17#include "llvm/Support/raw_ostream.h"

19using namespace llvm;
20using namespace llvm::object;

22#define DEBUG_TYPE"jitlink" "jitlink"

24namespace {

26enum JITLinkErrorCode { GenericJITLinkError = 1 };

28// FIXME: This class is only here to support the transition to llvm::Error. It
29// will be removed once this transition is complete. Clients should prefer to
30// deal with the Error value directly, rather than converting to error_code.
31class JITLinkerErrorCategory : public std::error_category {
32public:
const char *name() const noexcept override { return "runtimedyld"; }

std::string message(int Condition) const override {
  switch (static_cast<JITLinkErrorCode>(Condition)) {
  case GenericJITLinkError:
    return "Generic JITLink error";
  }
  llvm_unreachable("Unrecognized JITLinkErrorCode")__builtin_unreachable();
}
42};

44static ManagedStatic<JITLinkerErrorCategory> JITLinkerErrorCategory;

46} // namespace

48namespace llvm {
49namespace jitlink {

51char JITLinkError::ID = 0;

53void JITLinkError::log(raw_ostream &OS) const { OS << ErrMsg; }

55std::error_code JITLinkError::convertToErrorCode() const {
return std::error_code(GenericJITLinkError, *JITLinkerErrorCategory);
57}

59const char *getGenericEdgeKindName(Edge::Kind K) {
switch (K) {
case Edge::Invalid:
  return "INVALID RELOCATION";
case Edge::KeepAlive:
  return "Keep-Alive";
default:
  return "<Unrecognized edge kind>";
}
68}

70const char *getLinkageName(Linkage L) {
switch (L) {
case Linkage::Strong:
  return "strong";
case Linkage::Weak:
  return "weak";
}
llvm_unreachable("Unrecognized llvm.jitlink.Linkage enum")__builtin_unreachable();
78}

80const char *getScopeName(Scope S) {
switch (S) {
case Scope::Default:
  return "default";
case Scope::Hidden:
  return "hidden";
case Scope::Local:
  return "local";
}
llvm_unreachable("Unrecognized llvm.jitlink.Scope enum")__builtin_unreachable();
90}

92raw_ostream &operator<<(raw_ostream &OS, const Block &B) {
return OS << formatv("{0:x16}", B.getAddress()) << " -- "
          << formatv("{0:x8}", B.getAddress() + B.getSize()) << ": "
          << "size = " << formatv("{0:x8}", B.getSize()) << ", "
          << (B.isZeroFill() ? "zero-fill" : "content")
          << ", align = " << B.getAlignment()
          << ", align-ofs = " << B.getAlignmentOffset()
          << ", section = " << B.getSection().getName();
100}

102raw_ostream &operator<<(raw_ostream &OS, const Symbol &Sym) {
OS << formatv("{0:x16}", Sym.getAddress()) << " ("
   << (Sym.isDefined() ? "block" : "addressable") << " + "
   << formatv("{0:x8}", Sym.getOffset())
   << "): size: " << formatv("{0:x8}", Sym.getSize())
   << ", linkage: " << formatv("{0:6}", getLinkageName(Sym.getLinkage()))
   << ", scope: " << formatv("{0:8}", getScopeName(Sym.getScope())) << ", "
   << (Sym.isLive() ? "live" : "dead") << "  -   "
   << (Sym.hasName() ? Sym.getName() : "<anonymous symbol>");
return OS;
112}

114void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
             StringRef EdgeKindName) {
OS << "edge@" << formatv("{0:x16}", B.getAddress() + E.getOffset()) << ": "
   << formatv("{0:x16}", B.getAddress()) << " + "
   << formatv("{0:x}", E.getOffset()) << " -- " << EdgeKindName << " -> ";

auto &TargetSym = E.getTarget();
if (TargetSym.hasName())
  OS << TargetSym.getName();
else {
  auto &TargetBlock = TargetSym.getBlock();
  auto &TargetSec = TargetBlock.getSection();
  JITTargetAddress SecAddress = ~JITTargetAddress(0);
  for (auto *B : TargetSec.blocks())
    if (B->getAddress() < SecAddress)
      SecAddress = B->getAddress();

  JITTargetAddress SecDelta = TargetSym.getAddress() - SecAddress;
  OS << formatv("{0:x16}", TargetSym.getAddress()) << " (section "
     << TargetSec.getName();
  if (SecDelta)
    OS << " + " << formatv("{0:x}", SecDelta);
  OS << " / block " << formatv("{0:x16}", TargetBlock.getAddress());
  if (TargetSym.getOffset())
    OS << " + " << formatv("{0:x}", TargetSym.getOffset());
  OS << ")";
}

if (E.getAddend() != 0)
  OS << " + " << E.getAddend();
144}

146Section::~Section() {
for (auto *Sym : Symbols)
  Sym->~Symbol();
for (auto *B : Blocks)
  B->~Block();
151}

153Block &LinkGraph::splitBlock(Block &B, size_t SplitIndex,
                           SplitBlockCache *Cache) {

assert(SplitIndex > 0 && "splitBlock can not be called with SplitIndex == 0")(static_cast<void> (0));

// If the split point covers all of B then just return B.
if (SplitIndex == B.getSize())
1
Assuming the condition is false→
2
←
Taking false branch→
  return B;

assert(SplitIndex < B.getSize() && "SplitIndex out of range")(static_cast<void> (0));

// Create the new block covering [ 0, SplitIndex ).
auto &NewBlock =
    B.isZeroFill()
3
←
'?' condition is true→
        ? createZeroFillBlock(B.getSection(), SplitIndex, B.getAddress(),
                              B.getAlignment(), B.getAlignmentOffset())
        : createContentBlock(
              B.getSection(), B.getContent().slice(0, SplitIndex),
              B.getAddress(), B.getAlignment(), B.getAlignmentOffset());

// Modify B to cover [ SplitIndex, B.size() ).
B.setAddress(B.getAddress() + SplitIndex);
B.setContent(B.getContent().slice(SplitIndex));
B.setAlignmentOffset((B.getAlignmentOffset() + SplitIndex) %
7
←
Division by zero
                     B.getAlignment());
4
←
Calling 'Block::getAlignment'→
6
←
Returning from 'Block::getAlignment'→

// Handle edge transfer/update.
{
  // Copy edges to NewBlock (recording their iterators so that we can remove
  // them from B), and update of Edges remaining on B.
  std::vector<Block::edge_iterator> EdgesToRemove;
  for (auto I = B.edges().begin(); I != B.edges().end();) {
    if (I->getOffset() < SplitIndex) {
      NewBlock.addEdge(*I);
      I = B.removeEdge(I);
    } else {
      I->setOffset(I->getOffset() - SplitIndex);
      ++I;
    }
  }
}

// Handle symbol transfer/update.
{
  // Initialize the symbols cache if necessary.
  SplitBlockCache LocalBlockSymbolsCache;
  if (!Cache)
    Cache = &LocalBlockSymbolsCache;
  if (*Cache == None) {
    *Cache = SplitBlockCache::value_type();
    for (auto *Sym : B.getSection().symbols())
      if (&Sym->getBlock() == &B)
        (*Cache)->push_back(Sym);

    llvm::sort(**Cache, [](const Symbol *LHS, const Symbol *RHS) {
      return LHS->getOffset() > RHS->getOffset();
    });
  }
  auto &BlockSymbols = **Cache;

  // Transfer all symbols with offset less than SplitIndex to NewBlock.
  while (!BlockSymbols.empty() &&
         BlockSymbols.back()->getOffset() < SplitIndex) {
    BlockSymbols.back()->setBlock(NewBlock);
    BlockSymbols.pop_back();
  }

  // Update offsets for all remaining symbols in B.
  for (auto *Sym : BlockSymbols)
    Sym->setOffset(Sym->getOffset() - SplitIndex);
}

return NewBlock;
226}

228void LinkGraph::dump(raw_ostream &OS) {
DenseMap<Block *, std::vector<Symbol *>> BlockSymbols;

// Map from blocks to the symbols pointing at them.
for (auto *Sym : defined_symbols())
  BlockSymbols[&Sym->getBlock()].push_back(Sym);

// For each block, sort its symbols by something approximating
// relevance.
for (auto &KV : BlockSymbols)
  llvm::sort(KV.second, [](const Symbol *LHS, const Symbol *RHS) {
    if (LHS->getOffset() != RHS->getOffset())
      return LHS->getOffset() < RHS->getOffset();
    if (LHS->getLinkage() != RHS->getLinkage())
      return LHS->getLinkage() < RHS->getLinkage();
    if (LHS->getScope() != RHS->getScope())
      return LHS->getScope() < RHS->getScope();
    if (LHS->hasName()) {
      if (!RHS->hasName())
        return true;
      return LHS->getName() < RHS->getName();
    }
    return false;
  });

for (auto &Sec : sections()) {
  OS << "section " << Sec.getName() << ":\n\n";

  std::vector<Block *> SortedBlocks;
  llvm::copy(Sec.blocks(), std::back_inserter(SortedBlocks));
  llvm::sort(SortedBlocks, [](const Block *LHS, const Block *RHS) {
    return LHS->getAddress() < RHS->getAddress();
  });

  for (auto *B : SortedBlocks) {
    OS << "  block " << formatv("{0:x16}", B->getAddress())
       << " size = " << formatv("{0:x8}", B->getSize())
       << ", align = " << B->getAlignment()
       << ", alignment-offset = " << B->getAlignmentOffset();
    if (B->isZeroFill())
      OS << ", zero-fill";
    OS << "\n";

    auto BlockSymsI = BlockSymbols.find(B);
    if (BlockSymsI != BlockSymbols.end()) {
      OS << "    symbols:\n";
      auto &Syms = BlockSymsI->second;
      for (auto *Sym : Syms)
        OS << "      " << *Sym << "\n";
    } else
      OS << "    no symbols\n";

    if (!B->edges_empty()) {
      OS << "    edges:\n";
      std::vector<Edge> SortedEdges;
      llvm::copy(B->edges(), std::back_inserter(SortedEdges));
      llvm::sort(SortedEdges, [](const Edge &LHS, const Edge &RHS) {
        return LHS.getOffset() < RHS.getOffset();
      });
      for (auto &E : SortedEdges) {
        OS << "      " << formatv("{0:x16}", B->getFixupAddress(E))
           << " (block + " << formatv("{0:x8}", E.getOffset())
           << "), addend = ";
        if (E.getAddend() >= 0)
          OS << formatv("+{0:x8}", E.getAddend());
        else
          OS << formatv("-{0:x8}", -E.getAddend());
        OS << ", kind = " << getEdgeKindName(E.getKind()) << ", target = ";
        if (E.getTarget().hasName())
          OS << E.getTarget().getName();
        else
          OS << "addressable@"
             << formatv("{0:x16}", E.getTarget().getAddress()) << "+"
             << formatv("{0:x8}", E.getTarget().getOffset());
        OS << "\n";
      }
    } else
      OS << "    no edges\n";
    OS << "\n";
  }
}

OS << "Absolute symbols:\n";
if (!llvm::empty(absolute_symbols())) {
  for (auto *Sym : absolute_symbols())
    OS << "  " << format("0x%016" PRIx64"l" "x", Sym->getAddress()) << ": " << *Sym
       << "\n";
} else
  OS << "  none\n";

OS << "\nExternal symbols:\n";
if (!llvm::empty(external_symbols())) {
  for (auto *Sym : external_symbols())
    OS << "  " << format("0x%016" PRIx64"l" "x", Sym->getAddress()) << ": " << *Sym
       << "\n";
} else
  OS << "  none\n";
325}

327raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF) {
switch (LF) {
case SymbolLookupFlags::RequiredSymbol:
  return OS << "RequiredSymbol";
case SymbolLookupFlags::WeaklyReferencedSymbol:
  return OS << "WeaklyReferencedSymbol";
}
llvm_unreachable("Unrecognized lookup flags")__builtin_unreachable();
335}

337void JITLinkAsyncLookupContinuation::anchor() {}

339JITLinkContext::~JITLinkContext() {}

341bool JITLinkContext::shouldAddDefaultTargetPasses(const Triple &TT) const {
return true;
343}

345LinkGraphPassFunction JITLinkContext::getMarkLivePass(const Triple &TT) const {
return LinkGraphPassFunction();
347}

349Error JITLinkContext::modifyPassConfig(LinkGraph &G,
                                     PassConfiguration &Config) {
return Error::success();
352}

354Error markAllSymbolsLive(LinkGraph &G) {
for (auto *Sym : G.defined_symbols())
  Sym->setLive(true);
return Error::success();
358}

360Error makeTargetOutOfRangeError(const LinkGraph &G, const Block &B,
                              const Edge &E) {
std::string ErrMsg;
{
  raw_string_ostream ErrStream(ErrMsg);
  Section &Sec = B.getSection();
  ErrStream << "In graph " << G.getName() << ", section " << Sec.getName()
            << ": relocation target ";
  if (E.getTarget().hasName())
    ErrStream << "\"" << E.getTarget().getName() << "\" ";
  ErrStream << "at address " << formatv("{0:x}", E.getTarget().getAddress());
  ErrStream << " is out of range of " << G.getEdgeKindName(E.getKind())
            << " fixup at " << formatv("{0:x}", B.getFixupAddress(E)) << " (";

  Symbol *BestSymbolForBlock = nullptr;
  for (auto *Sym : Sec.symbols())
    if (&Sym->getBlock() == &B && Sym->hasName() && Sym->getOffset() == 0 &&
        (!BestSymbolForBlock ||
         Sym->getScope() < BestSymbolForBlock->getScope() ||
         Sym->getLinkage() < BestSymbolForBlock->getLinkage()))
      BestSymbolForBlock = Sym;

  if (BestSymbolForBlock)
    ErrStream << BestSymbolForBlock->getName() << ", ";
  else
    ErrStream << "<anonymous block> @ ";

  ErrStream << formatv("{0:x}", B.getAddress()) << " + "
            << formatv("{0:x}", E.getOffset()) << ")";
}
return make_error<JITLinkError>(std::move(ErrMsg));
391}

393Expected<std::unique_ptr<LinkGraph>>
394createLinkGraphFromObject(MemoryBufferRef ObjectBuffer) {
auto Magic = identify_magic(ObjectBuffer.getBuffer());
switch (Magic) {
case file_magic::macho_object:
  return createLinkGraphFromMachOObject(ObjectBuffer);
case file_magic::elf_relocatable:
  return createLinkGraphFromELFObject(ObjectBuffer);
default:
  return make_error<JITLinkError>("Unsupported file format");
};
404}

406void link(std::unique_ptr<LinkGraph> G, std::unique_ptr<JITLinkContext> Ctx) {
switch (G->getTargetTriple().getObjectFormat()) {
case Triple::MachO:
  return link_MachO(std::move(G), std::move(Ctx));
case Triple::ELF:
  return link_ELF(std::move(G), std::move(Ctx));
default:
  Ctx->notifyFailed(make_error<JITLinkError>("Unsupported object format"));
};
415}

417} // end namespace jitlink
418} // end namespace llvm

←

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

1//===------------ JITLink.h - JIT linker functionality ----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Contains generic JIT-linker types.
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H
14#define LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H

16#include "JITLinkMemoryManager.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/Triple.h"
22#include "llvm/ExecutionEngine/JITSymbol.h"
23#include "llvm/Support/Allocator.h"
24#include "llvm/Support/Endian.h"
25#include "llvm/Support/Error.h"
26#include "llvm/Support/FormatVariadic.h"
27#include "llvm/Support/MathExtras.h"
28#include "llvm/Support/Memory.h"
29#include "llvm/Support/MemoryBuffer.h"

31#include <map>
32#include <string>
33#include <system_error>

35namespace llvm {
36namespace jitlink {

38class LinkGraph;
39class Symbol;
40class Section;

42/// Base class for errors originating in JIT linker, e.g. missing relocation
43/// support.
44class JITLinkError : public ErrorInfo<JITLinkError> {
45public:
static char ID;

JITLinkError(Twine ErrMsg) : ErrMsg(ErrMsg.str()) {}

void log(raw_ostream &OS) const override;
const std::string &getErrorMessage() const { return ErrMsg; }
std::error_code convertToErrorCode() const override;

54private:
std::string ErrMsg;
56};

58/// Represents fixups and constraints in the LinkGraph.
59class Edge {
60public:
using Kind = uint8_t;

enum GenericEdgeKind : Kind {
  Invalid,                    // Invalid edge value.
  FirstKeepAlive,             // Keeps target alive. Offset/addend zero.
  KeepAlive = FirstKeepAlive, // Tag first edge kind that preserves liveness.
  FirstRelocation             // First architecture specific relocation.
};

using OffsetT = uint32_t;
using AddendT = int64_t;

Edge(Kind K, OffsetT Offset, Symbol &Target, AddendT Addend)
    : Target(&Target), Offset(Offset), Addend(Addend), K(K) {}

OffsetT getOffset() const { return Offset; }
void setOffset(OffsetT Offset) { this->Offset = Offset; }
Kind getKind() const { return K; }
void setKind(Kind K) { this->K = K; }
bool isRelocation() const { return K >= FirstRelocation; }
Kind getRelocation() const {
  assert(isRelocation() && "Not a relocation edge")(static_cast<void> (0));
  return K - FirstRelocation;
}
bool isKeepAlive() const { return K >= FirstKeepAlive; }
Symbol &getTarget() const { return *Target; }
void setTarget(Symbol &Target) { this->Target = &Target; }
AddendT getAddend() const { return Addend; }
void setAddend(AddendT Addend) { this->Addend = Addend; }

91private:
Symbol *Target = nullptr;
OffsetT Offset = 0;
AddendT Addend = 0;
Kind K = 0;
96};

98/// Returns the string name of the given generic edge kind, or "unknown"
99/// otherwise. Useful for debugging.
100const char *getGenericEdgeKindName(Edge::Kind K);

102/// Base class for Addressable entities (externals, absolutes, blocks).
103class Addressable {
friend class LinkGraph;

106protected:
Addressable(JITTargetAddress Address, bool IsDefined)
    : Address(Address), IsDefined(IsDefined), IsAbsolute(false) {}

Addressable(JITTargetAddress Address)
    : Address(Address), IsDefined(false), IsAbsolute(true) {
  assert(!(IsDefined && IsAbsolute) &&(static_cast<void> (0))
         "Block cannot be both defined and absolute")(static_cast<void> (0));
}

116public:
Addressable(const Addressable &) = delete;
Addressable &operator=(const Addressable &) = default;
Addressable(Addressable &&) = delete;
Addressable &operator=(Addressable &&) = default;

JITTargetAddress getAddress() const { return Address; }
void setAddress(JITTargetAddress Address) { this->Address = Address; }

/// Returns true if this is a defined addressable, in which case you
/// can downcast this to a Block.
bool isDefined() const { return static_cast<bool>(IsDefined); }
bool isAbsolute() const { return static_cast<bool>(IsAbsolute); }

130private:
void setAbsolute(bool IsAbsolute) {
  assert(!IsDefined && "Cannot change the Absolute flag on a defined block")(static_cast<void> (0));
  this->IsAbsolute = IsAbsolute;
}

JITTargetAddress Address = 0;
uint64_t IsDefined : 1;
uint64_t IsAbsolute : 1;

140protected:
// bitfields for Block, allocated here to improve packing.
uint64_t ContentMutable : 1;
uint64_t P2Align : 5;
uint64_t AlignmentOffset : 56;
145};

147using SectionOrdinal = unsigned;

149/// An Addressable with content and edges.
150class Block : public Addressable {
friend class LinkGraph;

153private:
/// Create a zero-fill defined addressable.
Block(Section &Parent, JITTargetAddress Size, JITTargetAddress Address,
      uint64_t Alignment, uint64_t AlignmentOffset)
    : Addressable(Address, true), Parent(&Parent), Size(Size) {
  assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2")(static_cast<void> (0));
  assert(AlignmentOffset < Alignment &&(static_cast<void> (0))
         "Alignment offset cannot exceed alignment")(static_cast<void> (0));
  assert(AlignmentOffset <= MaxAlignmentOffset &&(static_cast<void> (0))
         "Alignment offset exceeds maximum")(static_cast<void> (0));
  ContentMutable = false;
  P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
  this->AlignmentOffset = AlignmentOffset;
}

/// Create a defined addressable for the given content.
/// The Content is assumed to be non-writable, and will be copied when
/// mutations are required.
Block(Section &Parent, ArrayRef<char> Content, JITTargetAddress Address,
      uint64_t Alignment, uint64_t AlignmentOffset)
    : Addressable(Address, true), Parent(&Parent), Data(Content.data()),
      Size(Content.size()) {
  assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2")(static_cast<void> (0));
  assert(AlignmentOffset < Alignment &&(static_cast<void> (0))
         "Alignment offset cannot exceed alignment")(static_cast<void> (0));
  assert(AlignmentOffset <= MaxAlignmentOffset &&(static_cast<void> (0))
         "Alignment offset exceeds maximum")(static_cast<void> (0));
  ContentMutable = false;
  P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
  this->AlignmentOffset = AlignmentOffset;
}

/// Create a defined addressable for the given content.
/// The content is assumed to be writable, and the caller is responsible
/// for ensuring that it lives for the duration of the Block's lifetime.
/// The standard way to achieve this is to allocate it on the Graph's
/// allocator.
Block(Section &Parent, MutableArrayRef<char> Content,
      JITTargetAddress Address, uint64_t Alignment, uint64_t AlignmentOffset)
    : Addressable(Address, true), Parent(&Parent), Data(Content.data()),
      Size(Content.size()) {
  assert(isPowerOf2_64(Alignment) && "Alignment must be power of 2")(static_cast<void> (0));
  assert(AlignmentOffset < Alignment &&(static_cast<void> (0))
         "Alignment offset cannot exceed alignment")(static_cast<void> (0));
  assert(AlignmentOffset <= MaxAlignmentOffset &&(static_cast<void> (0))
         "Alignment offset exceeds maximum")(static_cast<void> (0));
  ContentMutable = true;
  P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
  this->AlignmentOffset = AlignmentOffset;
}

204public:
using EdgeVector = std::vector<Edge>;
using edge_iterator = EdgeVector::iterator;
using const_edge_iterator = EdgeVector::const_iterator;

Block(const Block &) = delete;
Block &operator=(const Block &) = delete;
Block(Block &&) = delete;
Block &operator=(Block &&) = delete;

/// Return the parent section for this block.
Section &getSection() const { return *Parent; }

/// Returns true if this is a zero-fill block.
///
/// If true, getSize is callable but getContent is not (the content is
/// defined to be a sequence of zero bytes of length Size).
bool isZeroFill() const { return !Data; }

/// Returns the size of this defined addressable.
size_t getSize() const { return Size; }

/// Get the content for this block. Block must not be a zero-fill block.
ArrayRef<char> getContent() const {
  assert(Data && "Section does not contain content")(static_cast<void> (0));
  return ArrayRef<char>(Data, Size);
}

/// Set the content for this block.
/// Caller is responsible for ensuring the underlying bytes are not
/// deallocated while pointed to by this block.
void setContent(ArrayRef<char> Content) {
  Data = Content.data();
  Size = Content.size();
  ContentMutable = false;
}

/// Get mutable content for this block.
///
/// If this Block's content is not already mutable this will trigger a copy
/// of the existing immutable content to a new, mutable buffer allocated using
/// LinkGraph::allocateContent.
MutableArrayRef<char> getMutableContent(LinkGraph &G);

/// Get mutable content for this block.
///
/// This block's content must already be mutable. It is a programmatic error
/// to call this on a block with immutable content -- consider using
/// getMutableContent instead.
MutableArrayRef<char> getAlreadyMutableContent() {
  assert(ContentMutable && "Content is not mutable")(static_cast<void> (0));
  return MutableArrayRef<char>(const_cast<char *>(Data), Size);
}

/// Set mutable content for this block.
///
/// The caller is responsible for ensuring that the memory pointed to by
/// MutableContent is not deallocated while pointed to by this block.
void setMutableContent(MutableArrayRef<char> MutableContent) {
  Data = MutableContent.data();
  Size = MutableContent.size();
  ContentMutable = true;
}

/// Returns true if this block's content is mutable.
///
/// This is primarily useful for asserting that a block is already in a
/// mutable state prior to modifying the content. E.g. when applying
/// fixups we expect the block to already be mutable as it should have been
/// copied to working memory.
bool isContentMutable() const { return ContentMutable; }

/// Get the alignment for this content.
uint64_t getAlignment() const { return 1ull << P2Align; }
5
←
Returning zero→

/// Set the alignment for this content.
void setAlignment(uint64_t Alignment) {
  assert(isPowerOf2_64(Alignment) && "Alignment must be a power of two")(static_cast<void> (0));
  P2Align = Alignment ? countTrailingZeros(Alignment) : 0;
}

/// Get the alignment offset for this content.
uint64_t getAlignmentOffset() const { return AlignmentOffset; }

/// Set the alignment offset for this content.
void setAlignmentOffset(uint64_t AlignmentOffset) {
  assert(AlignmentOffset < (1ull << P2Align) &&(static_cast<void> (0))
         "Alignment offset can't exceed alignment")(static_cast<void> (0));
  this->AlignmentOffset = AlignmentOffset;
}

/// Add an edge to this block.
void addEdge(Edge::Kind K, Edge::OffsetT Offset, Symbol &Target,
             Edge::AddendT Addend) {
  Edges.push_back(Edge(K, Offset, Target, Addend));
}

/// Add an edge by copying an existing one. This is typically used when
/// moving edges between blocks.
void addEdge(const Edge &E) { Edges.push_back(E); }

/// Return the list of edges attached to this content.
iterator_range<edge_iterator> edges() {
  return make_range(Edges.begin(), Edges.end());
}

/// Returns the list of edges attached to this content.
iterator_range<const_edge_iterator> edges() const {
  return make_range(Edges.begin(), Edges.end());
}

/// Return the size of the edges list.
size_t edges_size() const { return Edges.size(); }

/// Returns true if the list of edges is empty.
bool edges_empty() const { return Edges.empty(); }

/// Remove the edge pointed to by the given iterator.
/// Returns an iterator to the new next element.
edge_iterator removeEdge(edge_iterator I) { return Edges.erase(I); }

/// Returns the address of the fixup for the given edge, which is equal to
/// this block's address plus the edge's offset.
JITTargetAddress getFixupAddress(const Edge &E) const {
  return getAddress() + E.getOffset();
}

331private:
static constexpr uint64_t MaxAlignmentOffset = (1ULL << 56) - 1;

void setSection(Section &Parent) { this->Parent = &Parent; }

Section *Parent;
const char *Data = nullptr;
size_t Size = 0;
std::vector<Edge> Edges;
340};

342/// Describes symbol linkage. This can be used to make resolve definition
343/// clashes.
344enum class Linkage : uint8_t {
Strong,
Weak,
347};

349/// For errors and debugging output.
350const char *getLinkageName(Linkage L);

352/// Defines the scope in which this symbol should be visible:
353///   Default -- Visible in the public interface of the linkage unit.
354///   Hidden -- Visible within the linkage unit, but not exported from it.
355///   Local -- Visible only within the LinkGraph.
356enum class Scope : uint8_t {
Default,
Hidden,
Local
360};

362/// For debugging output.
363const char *getScopeName(Scope S);

365raw_ostream &operator<<(raw_ostream &OS, const Block &B);

367/// Symbol representation.
368///
369/// Symbols represent locations within Addressable objects.
370/// They can be either Named or Anonymous.
371/// Anonymous symbols have neither linkage nor visibility, and must point at
372/// ContentBlocks.
373/// Named symbols may be in one of four states:
374///   - Null: Default initialized. Assignable, but otherwise unusable.
375///   - Defined: Has both linkage and visibility and points to a ContentBlock
376///   - Common: Has both linkage and visibility, points to a null Addressable.
377///   - External: Has neither linkage nor visibility, points to an external
378///     Addressable.
379///
380class Symbol {
friend class LinkGraph;

383private:
Symbol(Addressable &Base, JITTargetAddress Offset, StringRef Name,
       JITTargetAddress Size, Linkage L, Scope S, bool IsLive,
       bool IsCallable)
    : Name(Name), Base(&Base), Offset(Offset), Size(Size) {
  assert(Offset <= MaxOffset && "Offset out of range")(static_cast<void> (0));
  setLinkage(L);
  setScope(S);
  setLive(IsLive);
  setCallable(IsCallable);
}

static Symbol &constructCommon(void *SymStorage, Block &Base, StringRef Name,
                               JITTargetAddress Size, Scope S, bool IsLive) {
  assert(SymStorage && "Storage cannot be null")(static_cast<void> (0));
  assert(!Name.empty() && "Common symbol name cannot be empty")(static_cast<void> (0));
  assert(Base.isDefined() &&(static_cast<void> (0))
         "Cannot create common symbol from undefined block")(static_cast<void> (0));
  assert(static_cast<Block &>(Base).getSize() == Size &&(static_cast<void> (0))
         "Common symbol size should match underlying block size")(static_cast<void> (0));
  auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
  new (Sym) Symbol(Base, 0, Name, Size, Linkage::Weak, S, IsLive, false);
  return *Sym;
}

static Symbol &constructExternal(void *SymStorage, Addressable &Base,
                                 StringRef Name, JITTargetAddress Size,
                                 Linkage L) {
  assert(SymStorage && "Storage cannot be null")(static_cast<void> (0));
  assert(!Base.isDefined() &&(static_cast<void> (0))
         "Cannot create external symbol from defined block")(static_cast<void> (0));
  assert(!Name.empty() && "External symbol name cannot be empty")(static_cast<void> (0));
  auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
  new (Sym) Symbol(Base, 0, Name, Size, L, Scope::Default, false, false);
  return *Sym;
}

static Symbol &constructAbsolute(void *SymStorage, Addressable &Base,
                                 StringRef Name, JITTargetAddress Size,
                                 Linkage L, Scope S, bool IsLive) {
  assert(SymStorage && "Storage cannot be null")(static_cast<void> (0));
  assert(!Base.isDefined() &&(static_cast<void> (0))
         "Cannot create absolute symbol from a defined block")(static_cast<void> (0));
  auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
  new (Sym) Symbol(Base, 0, Name, Size, L, S, IsLive, false);
  return *Sym;
}

static Symbol &constructAnonDef(void *SymStorage, Block &Base,
                                JITTargetAddress Offset,
                                JITTargetAddress Size, bool IsCallable,
                                bool IsLive) {
  assert(SymStorage && "Storage cannot be null")(static_cast<void> (0));
  assert((Offset + Size) <= Base.getSize() &&(static_cast<void> (0))
         "Symbol extends past end of block")(static_cast<void> (0));
  auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
  new (Sym) Symbol(Base, Offset, StringRef(), Size, Linkage::Strong,
                   Scope::Local, IsLive, IsCallable);
  return *Sym;
}

static Symbol &constructNamedDef(void *SymStorage, Block &Base,
                                 JITTargetAddress Offset, StringRef Name,
                                 JITTargetAddress Size, Linkage L, Scope S,
                                 bool IsLive, bool IsCallable) {
  assert(SymStorage && "Storage cannot be null")(static_cast<void> (0));
  assert((Offset + Size) <= Base.getSize() &&(static_cast<void> (0))
         "Symbol extends past end of block")(static_cast<void> (0));
  assert(!Name.empty() && "Name cannot be empty")(static_cast<void> (0));
  auto *Sym = reinterpret_cast<Symbol *>(SymStorage);
  new (Sym) Symbol(Base, Offset, Name, Size, L, S, IsLive, IsCallable);
  return *Sym;
}

457public:
/// Create a null Symbol. This allows Symbols to be default initialized for
/// use in containers (e.g. as map values). Null symbols are only useful for
/// assigning to.
Symbol() = default;

// Symbols are not movable or copyable.
Symbol(const Symbol &) = delete;
Symbol &operator=(const Symbol &) = delete;
Symbol(Symbol &&) = delete;
Symbol &operator=(Symbol &&) = delete;

/// Returns true if this symbol has a name.
bool hasName() const { return !Name.empty(); }

/// Returns the name of this symbol (empty if the symbol is anonymous).
StringRef getName() const {
  assert((!Name.empty() || getScope() == Scope::Local) &&(static_cast<void> (0))
         "Anonymous symbol has non-local scope")(static_cast<void> (0));
  return Name;
}

/// Rename this symbol. The client is responsible for updating scope and
/// linkage if this name-change requires it.
void setName(StringRef Name) { this->Name = Name; }

/// Returns true if this Symbol has content (potentially) defined within this
/// object file (i.e. is anything but an external or absolute symbol).
bool isDefined() const {
  assert(Base && "Attempt to access null symbol")(static_cast<void> (0));
  return Base->isDefined();
}

/// Returns true if this symbol is live (i.e. should be treated as a root for
/// dead stripping).
bool isLive() const {
  assert(Base && "Attempting to access null symbol")(static_cast<void> (0));
  return IsLive;
}

/// Set this symbol's live bit.
void setLive(bool IsLive) { this->IsLive = IsLive; }

/// Returns true is this symbol is callable.
bool isCallable() const { return IsCallable; }

/// Set this symbol's callable bit.
void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }

/// Returns true if the underlying addressable is an unresolved external.
bool isExternal() const {
  assert(Base && "Attempt to access null symbol")(static_cast<void> (0));
  return !Base->isDefined() && !Base->isAbsolute();
}

/// Returns true if the underlying addressable is an absolute symbol.
bool isAbsolute() const {
  assert(Base && "Attempt to access null symbol")(static_cast<void> (0));
  return Base->isAbsolute();
}

/// Return the addressable that this symbol points to.
Addressable &getAddressable() {
  assert(Base && "Cannot get underlying addressable for null symbol")(static_cast<void> (0));
  return *Base;
}

/// Return the addressable that thsi symbol points to.
const Addressable &getAddressable() const {
  assert(Base && "Cannot get underlying addressable for null symbol")(static_cast<void> (0));
  return *Base;
}

/// Return the Block for this Symbol (Symbol must be defined).
Block &getBlock() {
  assert(Base && "Cannot get block for null symbol")(static_cast<void> (0));
  assert(Base->isDefined() && "Not a defined symbol")(static_cast<void> (0));
  return static_cast<Block &>(*Base);
}

/// Return the Block for this Symbol (Symbol must be defined).
const Block &getBlock() const {
  assert(Base && "Cannot get block for null symbol")(static_cast<void> (0));
  assert(Base->isDefined() && "Not a defined symbol")(static_cast<void> (0));
  return static_cast<const Block &>(*Base);
}

/// Returns the offset for this symbol within the underlying addressable.
JITTargetAddress getOffset() const { return Offset; }

/// Returns the address of this symbol.
JITTargetAddress getAddress() const { return Base->getAddress() + Offset; }

/// Returns the size of this symbol.
JITTargetAddress getSize() const { return Size; }

/// Set the size of this symbol.
void setSize(JITTargetAddress Size) {
  assert(Base && "Cannot set size for null Symbol")(static_cast<void> (0));
  assert((Size == 0 || Base->isDefined()) &&(static_cast<void> (0))
         "Non-zero size can only be set for defined symbols")(static_cast<void> (0));
  assert((Offset + Size <= static_cast<const Block &>(*Base).getSize()) &&(static_cast<void> (0))
         "Symbol size cannot extend past the end of its containing block")(static_cast<void> (0));
  this->Size = Size;
}

/// Returns true if this symbol is backed by a zero-fill block.
/// This method may only be called on defined symbols.
bool isSymbolZeroFill() const { return getBlock().isZeroFill(); }

/// Returns the content in the underlying block covered by this symbol.
/// This method may only be called on defined non-zero-fill symbols.
ArrayRef<char> getSymbolContent() const {
  return getBlock().getContent().slice(Offset, Size);
}

/// Get the linkage for this Symbol.
Linkage getLinkage() const { return static_cast<Linkage>(L); }

/// Set the linkage for this Symbol.
void setLinkage(Linkage L) {
  assert((L == Linkage::Strong || (!Base->isAbsolute() && !Name.empty())) &&(static_cast<void> (0))
         "Linkage can only be applied to defined named symbols")(static_cast<void> (0));
  this->L = static_cast<uint8_t>(L);
}

/// Get the visibility for this Symbol.
Scope getScope() const { return static_cast<Scope>(S); }

/// Set the visibility for this Symbol.
void setScope(Scope S) {
  assert((!Name.empty() || S == Scope::Local) &&(static_cast<void> (0))
         "Can not set anonymous symbol to non-local scope")(static_cast<void> (0));
  assert((S == Scope::Default || Base->isDefined() || Base->isAbsolute()) &&(static_cast<void> (0))
         "Invalid visibility for symbol type")(static_cast<void> (0));
  this->S = static_cast<uint8_t>(S);
}

595private:
void makeExternal(Addressable &A) {
  assert(!A.isDefined() && !A.isAbsolute() &&(static_cast<void> (0))
         "Attempting to make external with defined or absolute block")(static_cast<void> (0));
  Base = &A;
  Offset = 0;
  setScope(Scope::Default);
  IsLive = 0;
  // note: Size, Linkage and IsCallable fields left unchanged.
}

void makeAbsolute(Addressable &A) {
  assert(!A.isDefined() && A.isAbsolute() &&(static_cast<void> (0))
         "Attempting to make absolute with defined or external block")(static_cast<void> (0));
  Base = &A;
  Offset = 0;
}

void setBlock(Block &B) { Base = &B; }

void setOffset(uint64_t NewOffset) {
  assert(NewOffset <= MaxOffset && "Offset out of range")(static_cast<void> (0));
  Offset = NewOffset;
}

static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;

// FIXME: A char* or SymbolStringPtr may pack better.
StringRef Name;
Addressable *Base = nullptr;
uint64_t Offset : 59;
uint64_t L : 1;
uint64_t S : 2;
uint64_t IsLive : 1;
uint64_t IsCallable : 1;
JITTargetAddress Size = 0;
631};

633raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);

635void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
             StringRef EdgeKindName);

638/// Represents an object file section.
639class Section {
friend class LinkGraph;

642private:
Section(StringRef Name, sys::Memory::ProtectionFlags Prot,
        SectionOrdinal SecOrdinal)
    : Name(Name), Prot(Prot), SecOrdinal(SecOrdinal) {}

using SymbolSet = DenseSet<Symbol *>;
using BlockSet = DenseSet<Block *>;

650public:
using symbol_iterator = SymbolSet::iterator;
using const_symbol_iterator = SymbolSet::const_iterator;

using block_iterator = BlockSet::iterator;
using const_block_iterator = BlockSet::const_iterator;

~Section();

// Sections are not movable or copyable.
Section(const Section &) = delete;
Section &operator=(const Section &) = delete;
Section(Section &&) = delete;
Section &operator=(Section &&) = delete;

/// Returns the name of this section.
StringRef getName() const { return Name; }

/// Returns the protection flags for this section.
sys::Memory::ProtectionFlags getProtectionFlags() const { return Prot; }

/// Set the protection flags for this section.
void setProtectionFlags(sys::Memory::ProtectionFlags Prot) {
  this->Prot = Prot;
}

/// Returns the ordinal for this section.
SectionOrdinal getOrdinal() const { return SecOrdinal; }

/// Returns an iterator over the blocks defined in this section.
iterator_range<block_iterator> blocks() {
  return make_range(Blocks.begin(), Blocks.end());
}

/// Returns an iterator over the blocks defined in this section.
iterator_range<const_block_iterator> blocks() const {
  return make_range(Blocks.begin(), Blocks.end());
}

BlockSet::size_type blocks_size() const { return Blocks.size(); }

/// Returns an iterator over the symbols defined in this section.
iterator_range<symbol_iterator> symbols() {
  return make_range(Symbols.begin(), Symbols.end());
}

/// Returns an iterator over the symbols defined in this section.
iterator_range<const_symbol_iterator> symbols() const {
  return make_range(Symbols.begin(), Symbols.end());
}

/// Return the number of symbols in this section.
SymbolSet::size_type symbols_size() const { return Symbols.size(); }

704private:
void addSymbol(Symbol &Sym) {
  assert(!Symbols.count(&Sym) && "Symbol is already in this section")(static_cast<void> (0));
  Symbols.insert(&Sym);
}

void removeSymbol(Symbol &Sym) {
  assert(Symbols.count(&Sym) && "symbol is not in this section")(static_cast<void> (0));
  Symbols.erase(&Sym);
}

void addBlock(Block &B) {
  assert(!Blocks.count(&B) && "Block is already in this section")(static_cast<void> (0));
  Blocks.insert(&B);
}

void removeBlock(Block &B) {
  assert(Blocks.count(&B) && "Block is not in this section")(static_cast<void> (0));
  Blocks.erase(&B);
}

void transferContentTo(Section &DstSection) {
  if (&DstSection == this)
    return;
  for (auto *S : Symbols)
    DstSection.addSymbol(*S);
  for (auto *B : Blocks)
    DstSection.addBlock(*B);
  Symbols.clear();
  Blocks.clear();
}

StringRef Name;
sys::Memory::ProtectionFlags Prot;
SectionOrdinal SecOrdinal = 0;
BlockSet Blocks;
SymbolSet Symbols;
741};

743/// Represents a section address range via a pair of Block pointers
744/// to the first and last Blocks in the section.
745class SectionRange {
746public:
SectionRange() = default;
SectionRange(const Section &Sec) {
  if (llvm::empty(Sec.blocks()))
    return;
  First = Last = *Sec.blocks().begin();
  for (auto *B : Sec.blocks()) {
    if (B->getAddress() < First->getAddress())
      First = B;
    if (B->getAddress() > Last->getAddress())
      Last = B;
  }
}
Block *getFirstBlock() const {
  assert((!Last || First) && "First can not be null if end is non-null")(static_cast<void> (0));
  return First;
}
Block *getLastBlock() const {
  assert((First || !Last) && "Last can not be null if start is non-null")(static_cast<void> (0));
  return Last;
}
bool empty() const {
  assert((First || !Last) && "Last can not be null if start is non-null")(static_cast<void> (0));
  return !First;
}
JITTargetAddress getStart() const {
  return First ? First->getAddress() : 0;
}
JITTargetAddress getEnd() const {
  return Last ? Last->getAddress() + Last->getSize() : 0;
}
uint64_t getSize() const { return getEnd() - getStart(); }

779private:
Block *First = nullptr;
Block *Last = nullptr;
782};

784class LinkGraph {
785private:
using SectionList = std::vector<std::unique_ptr<Section>>;
using ExternalSymbolSet = DenseSet<Symbol *>;
using BlockSet = DenseSet<Block *>;

template <typename... ArgTs>
Addressable &createAddressable(ArgTs &&... Args) {
  Addressable *A =
      reinterpret_cast<Addressable *>(Allocator.Allocate<Addressable>());
  new (A) Addressable(std::forward<ArgTs>(Args)...);
  return *A;
}

void destroyAddressable(Addressable &A) {
  A.~Addressable();
  Allocator.Deallocate(&A);
}

template <typename... ArgTs> Block &createBlock(ArgTs &&... Args) {
  Block *B = reinterpret_cast<Block *>(Allocator.Allocate<Block>());
  new (B) Block(std::forward<ArgTs>(Args)...);
  B->getSection().addBlock(*B);
  return *B;
}

void destroyBlock(Block &B) {
  B.~Block();
  Allocator.Deallocate(&B);
}

void destroySymbol(Symbol &S) {
  S.~Symbol();
  Allocator.Deallocate(&S);
}

static iterator_range<Section::block_iterator> getSectionBlocks(Section &S) {
  return S.blocks();
}

static iterator_range<Section::const_block_iterator>
getSectionConstBlocks(Section &S) {
  return S.blocks();
}

static iterator_range<Section::symbol_iterator>
getSectionSymbols(Section &S) {
  return S.symbols();
}

static iterator_range<Section::const_symbol_iterator>
getSectionConstSymbols(Section &S) {
  return S.symbols();
}

839public:
using external_symbol_iterator = ExternalSymbolSet::iterator;

using section_iterator = pointee_iterator<SectionList::iterator>;
using const_section_iterator = pointee_iterator<SectionList::const_iterator>;

template <typename OuterItrT, typename InnerItrT, typename T,
          iterator_range<InnerItrT> getInnerRange(
              typename OuterItrT::reference)>
class nested_collection_iterator
    : public iterator_facade_base<
          nested_collection_iterator<OuterItrT, InnerItrT, T, getInnerRange>,
          std::forward_iterator_tag, T> {
public:
  nested_collection_iterator() = default;

  nested_collection_iterator(OuterItrT OuterI, OuterItrT OuterE)
      : OuterI(OuterI), OuterE(OuterE),
        InnerI(getInnerBegin(OuterI, OuterE)) {
    moveToNonEmptyInnerOrEnd();
  }

  bool operator==(const nested_collection_iterator &RHS) const {
    return (OuterI == RHS.OuterI) && (InnerI == RHS.InnerI);
  }

  T operator*() const {
    assert(InnerI != getInnerRange(*OuterI).end() && "Dereferencing end?")(static_cast<void> (0));
    return *InnerI;
  }

  nested_collection_iterator operator++() {
    ++InnerI;
    moveToNonEmptyInnerOrEnd();
    return *this;
  }

private:
  static InnerItrT getInnerBegin(OuterItrT OuterI, OuterItrT OuterE) {
    return OuterI != OuterE ? getInnerRange(*OuterI).begin() : InnerItrT();
  }

  void moveToNonEmptyInnerOrEnd() {
    while (OuterI != OuterE && InnerI == getInnerRange(*OuterI).end()) {
      ++OuterI;
      InnerI = getInnerBegin(OuterI, OuterE);
    }
  }

  OuterItrT OuterI, OuterE;
  InnerItrT InnerI;
};

using defined_symbol_iterator =
    nested_collection_iterator<const_section_iterator,
                               Section::symbol_iterator, Symbol *,
                               getSectionSymbols>;

using const_defined_symbol_iterator =
    nested_collection_iterator<const_section_iterator,
                               Section::const_symbol_iterator, const Symbol *,
                               getSectionConstSymbols>;

using block_iterator = nested_collection_iterator<const_section_iterator,
                                                  Section::block_iterator,
                                                  Block *, getSectionBlocks>;

using const_block_iterator =
    nested_collection_iterator<const_section_iterator,
                               Section::const_block_iterator, const Block *,
                               getSectionConstBlocks>;

using GetEdgeKindNameFunction = const char *(*)(Edge::Kind);

LinkGraph(std::string Name, const Triple &TT, unsigned PointerSize,
          support::endianness Endianness,
          GetEdgeKindNameFunction GetEdgeKindName)
    : Name(std::move(Name)), TT(TT), PointerSize(PointerSize),
      Endianness(Endianness), GetEdgeKindName(std::move(GetEdgeKindName)) {}

/// Returns the name of this graph (usually the name of the original
/// underlying MemoryBuffer).
const std::string &getName() const { return Name; }

/// Returns the target triple for this Graph.
const Triple &getTargetTriple() const { return TT; }

/// Returns the pointer size for use in this graph.
unsigned getPointerSize() const { return PointerSize; }

/// Returns the endianness of content in this graph.
support::endianness getEndianness() const { return Endianness; }

const char *getEdgeKindName(Edge::Kind K) const { return GetEdgeKindName(K); }

/// Allocate a mutable buffer of the given size using the LinkGraph's
/// allocator.
MutableArrayRef<char> allocateBuffer(size_t Size) {
  return {Allocator.Allocate<char>(Size), Size};
}

/// Allocate a copy of the given string using the LinkGraph's allocator.
/// This can be useful when renaming symbols or adding new content to the
/// graph.
MutableArrayRef<char> allocateContent(ArrayRef<char> Source) {
  auto *AllocatedBuffer = Allocator.Allocate<char>(Source.size());
  llvm::copy(Source, AllocatedBuffer);
  return MutableArrayRef<char>(AllocatedBuffer, Source.size());
}

/// Allocate a copy of the given string using the LinkGraph's allocator.
/// This can be useful when renaming symbols or adding new content to the
/// graph.
///
/// Note: This Twine-based overload requires an extra string copy and an
/// extra heap allocation for large strings. The ArrayRef<char> overload
/// should be preferred where possible.
MutableArrayRef<char> allocateString(Twine Source) {
  SmallString<256> TmpBuffer;
  auto SourceStr = Source.toStringRef(TmpBuffer);
  auto *AllocatedBuffer = Allocator.Allocate<char>(SourceStr.size());
  llvm::copy(SourceStr, AllocatedBuffer);
  return MutableArrayRef<char>(AllocatedBuffer, SourceStr.size());
}

/// Create a section with the given name, protection flags, and alignment.
Section &createSection(StringRef Name, sys::Memory::ProtectionFlags Prot) {
  assert(llvm::find_if(Sections,(static_cast<void> (0))
                       [&](std::unique_ptr<Section> &Sec) {(static_cast<void> (0))
                         return Sec->getName() == Name;(static_cast<void> (0))
                       }) == Sections.end() &&(static_cast<void> (0))
         "Duplicate section name")(static_cast<void> (0));
  std::unique_ptr<Section> Sec(new Section(Name, Prot, Sections.size()));
  Sections.push_back(std::move(Sec));
  return *Sections.back();
}

/// Create a content block.
Block &createContentBlock(Section &Parent, ArrayRef<char> Content,
                          uint64_t Address, uint64_t Alignment,
                          uint64_t AlignmentOffset) {
  return createBlock(Parent, Content, Address, Alignment, AlignmentOffset);
}

/// Create a content block with initially mutable data.
Block &createMutableContentBlock(Section &Parent,
                                 MutableArrayRef<char> MutableContent,
                                 uint64_t Address, uint64_t Alignment,
                                 uint64_t AlignmentOffset) {
  return createBlock(Parent, MutableContent, Address, Alignment,
                     AlignmentOffset);
}

/// Create a zero-fill block.
Block &createZeroFillBlock(Section &Parent, uint64_t Size, uint64_t Address,
                           uint64_t Alignment, uint64_t AlignmentOffset) {
  return createBlock(Parent, Size, Address, Alignment, AlignmentOffset);
}

/// Cache type for the splitBlock function.
using SplitBlockCache = Optional<SmallVector<Symbol *, 8>>;

/// Splits block B at the given index which must be greater than zero.
/// If SplitIndex == B.getSize() then this function is a no-op and returns B.
/// If SplitIndex < B.getSize() then this function returns a new block
/// covering the range [ 0, SplitIndex ), and B is modified to cover the range
/// [ SplitIndex, B.size() ).
///
/// The optional Cache parameter can be used to speed up repeated calls to
/// splitBlock for a single block. If the value is None the cache will be
/// treated as uninitialized and splitBlock will populate it. Otherwise it
/// is assumed to contain the list of Symbols pointing at B, sorted in
/// descending order of offset.
///
/// Notes:
///
/// 1. splitBlock must be used with care. Splitting a block may cause
///    incoming edges to become invalid if the edge target subexpression
///    points outside the bounds of the newly split target block (E.g. an
///    edge 'S + 10 : Pointer64' where S points to a newly split block
///    whose size is less than 10). No attempt is made to detect invalidation
///    of incoming edges, as in general this requires context that the
///    LinkGraph does not have. Clients are responsible for ensuring that
///    splitBlock is not used in a way that invalidates edges.
///
/// 2. The newly introduced block will have a new ordinal which will be
///    higher than any other ordinals in the section. Clients are responsible
///    for re-assigning block ordinals to restore a compatible order if
///    needed.
///
/// 3. The cache is not automatically updated if new symbols are introduced
///    between calls to splitBlock. Any newly introduced symbols may be
///    added to the cache manually (descending offset order must be
///    preserved), or the cache can be set to None and rebuilt by
///    splitBlock on the next call.
Block &splitBlock(Block &B, size_t SplitIndex,
                  SplitBlockCache *Cache = nullptr);

/// Add an external symbol.
/// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
/// size is not known, you should substitute '0'.
/// For external symbols Linkage determines whether the symbol must be
/// present during lookup: Externals with strong linkage must be found or
/// an error will be emitted. Externals with weak linkage are permitted to
/// be undefined, in which case they are assigned a value of 0.
Symbol &addExternalSymbol(StringRef Name, uint64_t Size, Linkage L) {
  assert(llvm::count_if(ExternalSymbols,(static_cast<void> (0))
                        [&](const Symbol *Sym) {(static_cast<void> (0))
                          return Sym->getName() == Name;(static_cast<void> (0))
                        }) == 0 &&(static_cast<void> (0))
         "Duplicate external symbol")(static_cast<void> (0));
  auto &Sym =
      Symbol::constructExternal(Allocator.Allocate<Symbol>(),
                                createAddressable(0, false), Name, Size, L);
  ExternalSymbols.insert(&Sym);
  return Sym;
}

/// Add an absolute symbol.
Symbol &addAbsoluteSymbol(StringRef Name, JITTargetAddress Address,
                          uint64_t Size, Linkage L, Scope S, bool IsLive) {
  assert(llvm::count_if(AbsoluteSymbols,(static_cast<void> (0))
                        [&](const Symbol *Sym) {(static_cast<void> (0))
                          return Sym->getName() == Name;(static_cast<void> (0))
                        }) == 0 &&(static_cast<void> (0))
         "Duplicate absolute symbol")(static_cast<void> (0));
  auto &Sym = Symbol::constructAbsolute(Allocator.Allocate<Symbol>(),
                                        createAddressable(Address), Name,
                                        Size, L, S, IsLive);
  AbsoluteSymbols.insert(&Sym);
  return Sym;
}

/// Convenience method for adding a weak zero-fill symbol.
Symbol &addCommonSymbol(StringRef Name, Scope S, Section &Section,
                        JITTargetAddress Address, uint64_t Size,
                        uint64_t Alignment, bool IsLive) {
  assert(llvm::count_if(defined_symbols(),(static_cast<void> (0))
                        [&](const Symbol *Sym) {(static_cast<void> (0))
                          return Sym->getName() == Name;(static_cast<void> (0))
                        }) == 0 &&(static_cast<void> (0))
         "Duplicate defined symbol")(static_cast<void> (0));
  auto &Sym = Symbol::constructCommon(
      Allocator.Allocate<Symbol>(),
      createBlock(Section, Size, Address, Alignment, 0), Name, Size, S,
      IsLive);
  Section.addSymbol(Sym);
  return Sym;
}

/// Add an anonymous symbol.
Symbol &addAnonymousSymbol(Block &Content, JITTargetAddress Offset,
                           JITTargetAddress Size, bool IsCallable,
                           bool IsLive) {
  auto &Sym = Symbol::constructAnonDef(Allocator.Allocate<Symbol>(), Content,
                                       Offset, Size, IsCallable, IsLive);
  Content.getSection().addSymbol(Sym);
  return Sym;
}

/// Add a named symbol.
Symbol &addDefinedSymbol(Block &Content, JITTargetAddress Offset,
                         StringRef Name, JITTargetAddress Size, Linkage L,
                         Scope S, bool IsCallable, bool IsLive) {
  assert(llvm::count_if(defined_symbols(),(static_cast<void> (0))
                        [&](const Symbol *Sym) {(static_cast<void> (0))
                          return Sym->getName() == Name;(static_cast<void> (0))
                        }) == 0 &&(static_cast<void> (0))
         "Duplicate defined symbol")(static_cast<void> (0));
  auto &Sym =
      Symbol::constructNamedDef(Allocator.Allocate<Symbol>(), Content, Offset,
                                Name, Size, L, S, IsLive, IsCallable);
  Content.getSection().addSymbol(Sym);
  return Sym;
}

iterator_range<section_iterator> sections() {
  return make_range(section_iterator(Sections.begin()),
                    section_iterator(Sections.end()));
}

SectionList::size_type sections_size() const { return Sections.size(); }

/// Returns the section with the given name if it exists, otherwise returns
/// null.
Section *findSectionByName(StringRef Name) {
  for (auto &S : sections())
    if (S.getName() == Name)
      return &S;
  return nullptr;
}

iterator_range<block_iterator> blocks() {
  return make_range(block_iterator(Sections.begin(), Sections.end()),
                    block_iterator(Sections.end(), Sections.end()));
}

iterator_range<const_block_iterator> blocks() const {
  return make_range(const_block_iterator(Sections.begin(), Sections.end()),
                    const_block_iterator(Sections.end(), Sections.end()));
}

iterator_range<external_symbol_iterator> external_symbols() {
  return make_range(ExternalSymbols.begin(), ExternalSymbols.end());
}

iterator_range<external_symbol_iterator> absolute_symbols() {
  return make_range(AbsoluteSymbols.begin(), AbsoluteSymbols.end());
}

iterator_range<defined_symbol_iterator> defined_symbols() {
  return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()),
                    defined_symbol_iterator(Sections.end(), Sections.end()));
}

iterator_range<const_defined_symbol_iterator> defined_symbols() const {
  return make_range(
      const_defined_symbol_iterator(Sections.begin(), Sections.end()),
      const_defined_symbol_iterator(Sections.end(), Sections.end()));
}

/// Make the given symbol external (must not already be external).
///
/// Symbol size, linkage and callability will be left unchanged. Symbol scope
/// will be set to Default, and offset will be reset to 0.
void makeExternal(Symbol &Sym) {
  assert(!Sym.isExternal() && "Symbol is already external")(static_cast<void> (0));
  if (Sym.isAbsolute()) {
    assert(AbsoluteSymbols.count(&Sym) &&(static_cast<void> (0))
           "Sym is not in the absolute symbols set")(static_cast<void> (0));
    assert(Sym.getOffset() == 0 && "Absolute not at offset 0")(static_cast<void> (0));
    AbsoluteSymbols.erase(&Sym);
    Sym.getAddressable().setAbsolute(false);
  } else {
    assert(Sym.isDefined() && "Sym is not a defined symbol")(static_cast<void> (0));
    Section &Sec = Sym.getBlock().getSection();
    Sec.removeSymbol(Sym);
    Sym.makeExternal(createAddressable(0, false));
  }
  ExternalSymbols.insert(&Sym);
}

/// Make the given symbol an absolute with the given address (must not already
/// be absolute).
///
/// Symbol size, linkage, scope, and callability, and liveness will be left
/// unchanged. Symbol offset will be reset to 0.
void makeAbsolute(Symbol &Sym, JITTargetAddress Address) {
  assert(!Sym.isAbsolute() && "Symbol is already absolute")(static_cast<void> (0));
  if (Sym.isExternal()) {
    assert(ExternalSymbols.count(&Sym) &&(static_cast<void> (0))
           "Sym is not in the absolute symbols set")(static_cast<void> (0));
    assert(Sym.getOffset() == 0 && "External is not at offset 0")(static_cast<void> (0));
    ExternalSymbols.erase(&Sym);
    Sym.getAddressable().setAbsolute(true);
  } else {
    assert(Sym.isDefined() && "Sym is not a defined symbol")(static_cast<void> (0));
    Section &Sec = Sym.getBlock().getSection();
    Sec.removeSymbol(Sym);
    Sym.makeAbsolute(createAddressable(Address));
  }
  AbsoluteSymbols.insert(&Sym);
}

/// Turn an absolute or external symbol into a defined one by attaching it to
/// a block. Symbol must not already be defined.
void makeDefined(Symbol &Sym, Block &Content, JITTargetAddress Offset,
                 JITTargetAddress Size, Linkage L, Scope S, bool IsLive) {
  assert(!Sym.isDefined() && "Sym is already a defined symbol")(static_cast<void> (0));
  if (Sym.isAbsolute()) {
    assert(AbsoluteSymbols.count(&Sym) &&(static_cast<void> (0))
           "Symbol is not in the absolutes set")(static_cast<void> (0));
    AbsoluteSymbols.erase(&Sym);
  } else {
    assert(ExternalSymbols.count(&Sym) &&(static_cast<void> (0))
           "Symbol is not in the externals set")(static_cast<void> (0));
    ExternalSymbols.erase(&Sym);
  }
  Addressable &OldBase = *Sym.Base;
  Sym.setBlock(Content);
  Sym.setOffset(Offset);
  Sym.setSize(Size);
  Sym.setLinkage(L);
  Sym.setScope(S);
  Sym.setLive(IsLive);
  Content.getSection().addSymbol(Sym);
  destroyAddressable(OldBase);
}

/// Transfer a defined symbol from one block to another.
///
/// The symbol's offset within DestBlock is set to NewOffset.
///
/// If ExplicitNewSize is given as None then the size of the symbol will be
/// checked and auto-truncated to at most the size of the remainder (from the
/// given offset) of the size of the new block.
///
/// All other symbol attributes are unchanged.
void transferDefinedSymbol(Symbol &Sym, Block &DestBlock,
                           JITTargetAddress NewOffset,
                           Optional<JITTargetAddress> ExplicitNewSize) {
  Sym.setBlock(DestBlock);
  Sym.setOffset(NewOffset);
  if (ExplicitNewSize)
    Sym.setSize(*ExplicitNewSize);
  else {
    JITTargetAddress RemainingBlockSize = DestBlock.getSize() - NewOffset;
    if (Sym.getSize() > RemainingBlockSize)
      Sym.setSize(RemainingBlockSize);
  }
}

/// Transfers the given Block and all Symbols pointing to it to the given
/// Section.
///
/// No attempt is made to check compatibility of the source and destination
/// sections. Blocks may be moved between sections with incompatible
/// permissions (e.g. from data to text). The client is responsible for
/// ensuring that this is safe.
void transferBlock(Block &B, Section &NewSection) {
  auto &OldSection = B.getSection();
  if (&OldSection == &NewSection)
    return;
  SmallVector<Symbol *> AttachedSymbols;
  for (auto *S : OldSection.symbols())
    if (&S->getBlock() == &B)
      AttachedSymbols.push_back(S);
  for (auto *S : AttachedSymbols) {
    OldSection.removeSymbol(*S);
    NewSection.addSymbol(*S);
  }
  OldSection.removeBlock(B);
  NewSection.addBlock(B);
}

/// Move all blocks and symbols from the source section to the destination
/// section.
///
/// If PreserveSrcSection is true (or SrcSection and DstSection are the same)
/// then SrcSection is preserved, otherwise it is removed (the default).
void mergeSections(Section &DstSection, Section &SrcSection,
                   bool PreserveSrcSection = false) {
  if (&DstSection == &SrcSection)
    return;
  SrcSection.transferContentTo(DstSection);
  if (!PreserveSrcSection)
    removeSection(SrcSection);
}

/// Removes an external symbol. Also removes the underlying Addressable.
void removeExternalSymbol(Symbol &Sym) {
  assert(!Sym.isDefined() && !Sym.isAbsolute() &&(static_cast<void> (0))
         "Sym is not an external symbol")(static_cast<void> (0));
  assert(ExternalSymbols.count(&Sym) && "Symbol is not in the externals set")(static_cast<void> (0));
  ExternalSymbols.erase(&Sym);
  Addressable &Base = *Sym.Base;
  assert(llvm::find_if(ExternalSymbols,(static_cast<void> (0))
                       [&](Symbol *AS) { return AS->Base == &Base; }) ==(static_cast<void> (0))
             ExternalSymbols.end() &&(static_cast<void> (0))
         "Base addressable still in use")(static_cast<void> (0));
  destroySymbol(Sym);
  destroyAddressable(Base);
}

/// Remove an absolute symbol. Also removes the underlying Addressable.
void removeAbsoluteSymbol(Symbol &Sym) {
  assert(!Sym.isDefined() && Sym.isAbsolute() &&(static_cast<void> (0))
         "Sym is not an absolute symbol")(static_cast<void> (0));
  assert(AbsoluteSymbols.count(&Sym) &&(static_cast<void> (0))
         "Symbol is not in the absolute symbols set")(static_cast<void> (0));
  AbsoluteSymbols.erase(&Sym);
  Addressable &Base = *Sym.Base;
  assert(llvm::find_if(ExternalSymbols,(static_cast<void> (0))
                       [&](Symbol *AS) { return AS->Base == &Base; }) ==(static_cast<void> (0))
             ExternalSymbols.end() &&(static_cast<void> (0))
         "Base addressable still in use")(static_cast<void> (0));
  destroySymbol(Sym);
  destroyAddressable(Base);
}

/// Removes defined symbols. Does not remove the underlying block.
void removeDefinedSymbol(Symbol &Sym) {
  assert(Sym.isDefined() && "Sym is not a defined symbol")(static_cast<void> (0));
  Sym.getBlock().getSection().removeSymbol(Sym);
  destroySymbol(Sym);
}

/// Remove a block. The block reference is defunct after calling this
/// function and should no longer be used.
void removeBlock(Block &B) {
  assert(llvm::none_of(B.getSection().symbols(),(static_cast<void> (0))
                       [&](const Symbol *Sym) {(static_cast<void> (0))
                         return &Sym->getBlock() == &B;(static_cast<void> (0))
                       }) &&(static_cast<void> (0))
         "Block still has symbols attached")(static_cast<void> (0));
  B.getSection().removeBlock(B);
  destroyBlock(B);
}

/// Remove a section. The section reference is defunct after calling this
/// function and should no longer be used.
void removeSection(Section &Sec) {
  auto I = llvm::find_if(Sections, [&Sec](const std::unique_ptr<Section> &S) {
    return S.get() == &Sec;
  });
  assert(I != Sections.end() && "Section does not appear in this graph")(static_cast<void> (0));
  Sections.erase(I);
}

/// Dump the graph.
void dump(raw_ostream &OS);

1351private:
// Put the BumpPtrAllocator first so that we don't free any of the underlying
// memory until the Symbol/Addressable destructors have been run.
BumpPtrAllocator Allocator;

std::string Name;
Triple TT;
unsigned PointerSize;
support::endianness Endianness;
GetEdgeKindNameFunction GetEdgeKindName = nullptr;
SectionList Sections;
ExternalSymbolSet ExternalSymbols;
ExternalSymbolSet AbsoluteSymbols;
1364};

1366inline MutableArrayRef<char> Block::getMutableContent(LinkGraph &G) {
if (!ContentMutable)
  setMutableContent(G.allocateContent({Data, Size}));
return MutableArrayRef<char>(const_cast<char *>(Data), Size);
1370}

1372/// Enables easy lookup of blocks by addresses.
1373class BlockAddressMap {
1374public:
using AddrToBlockMap = std::map<JITTargetAddress, Block *>;
using const_iterator = AddrToBlockMap::const_iterator;

/// A block predicate that always adds all blocks.
static bool includeAllBlocks(const Block &B) { return true; }

/// A block predicate that always includes blocks with non-null addresses.
static bool includeNonNull(const Block &B) { return B.getAddress(); }

BlockAddressMap() = default;

/// Add a block to the map. Returns an error if the block overlaps with any
/// existing block.
template <typename PredFn = decltype(includeAllBlocks)>
Error addBlock(Block &B, PredFn Pred = includeAllBlocks) {
  if (!Pred(B))
    return Error::success();

  auto I = AddrToBlock.upper_bound(B.getAddress());

  // If we're not at the end of the map, check for overlap with the next
  // element.
  if (I != AddrToBlock.end()) {
    if (B.getAddress() + B.getSize() > I->second->getAddress())
      return overlapError(B, *I->second);
  }

  // If we're not at the start of the map, check for overlap with the previous
  // element.
  if (I != AddrToBlock.begin()) {
    auto &PrevBlock = *std::prev(I)->second;
    if (PrevBlock.getAddress() + PrevBlock.getSize() > B.getAddress())
      return overlapError(B, PrevBlock);
  }

  AddrToBlock.insert(I, std::make_pair(B.getAddress(), &B));
  return Error::success();
}

/// Add a block to the map without checking for overlap with existing blocks.
/// The client is responsible for ensuring that the block added does not
/// overlap with any existing block.
void addBlockWithoutChecking(Block &B) { AddrToBlock[B.getAddress()] = &B; }

/// Add a range of blocks to the map. Returns an error if any block in the
/// range overlaps with any other block in the range, or with any existing
/// block in the map.
template <typename BlockPtrRange,
          typename PredFn = decltype(includeAllBlocks)>
Error addBlocks(BlockPtrRange &&Blocks, PredFn Pred = includeAllBlocks) {
  for (auto *B : Blocks)
    if (auto Err = addBlock(*B, Pred))
      return Err;
  return Error::success();
}

/// Add a range of blocks to the map without checking for overlap with
/// existing blocks. The client is responsible for ensuring that the block
/// added does not overlap with any existing block.
template <typename BlockPtrRange>
void addBlocksWithoutChecking(BlockPtrRange &&Blocks) {
  for (auto *B : Blocks)
    addBlockWithoutChecking(*B);
}

/// Iterates over (Address, Block*) pairs in ascending order of address.
const_iterator begin() const { return AddrToBlock.begin(); }
const_iterator end() const { return AddrToBlock.end(); }

/// Returns the block starting at the given address, or nullptr if no such
/// block exists.
Block *getBlockAt(JITTargetAddress Addr) const {
  auto I = AddrToBlock.find(Addr);
  if (I == AddrToBlock.end())
    return nullptr;
  return I->second;
}

/// Returns the block covering the given address, or nullptr if no such block
/// exists.
Block *getBlockCovering(JITTargetAddress Addr) const {
  auto I = AddrToBlock.upper_bound(Addr);
  if (I == AddrToBlock.begin())
    return nullptr;
  auto *B = std::prev(I)->second;
  if (Addr < B->getAddress() + B->getSize())
    return B;
  return nullptr;
}

1465private:
Error overlapError(Block &NewBlock, Block &ExistingBlock) {
  auto NewBlockEnd = NewBlock.getAddress() + NewBlock.getSize();
  auto ExistingBlockEnd =
      ExistingBlock.getAddress() + ExistingBlock.getSize();
  return make_error<JITLinkError>(
      "Block at " +
      formatv("{0:x16} -- {1:x16}", NewBlock.getAddress(), NewBlockEnd) +
      " overlaps " +
      formatv("{0:x16} -- {1:x16}", ExistingBlock.getAddress(),
              ExistingBlockEnd));
}

AddrToBlockMap AddrToBlock;
1479};

1481/// A map of addresses to Symbols.
1482class SymbolAddressMap {
1483public:
using SymbolVector = SmallVector<Symbol *, 1>;

/// Add a symbol to the SymbolAddressMap.
void addSymbol(Symbol &Sym) {
  AddrToSymbols[Sym.getAddress()].push_back(&Sym);
}

/// Add all symbols in a given range to the SymbolAddressMap.
template <typename SymbolPtrCollection>
void addSymbols(SymbolPtrCollection &&Symbols) {
  for (auto *Sym : Symbols)
    addSymbol(*Sym);
}

/// Returns the list of symbols that start at the given address, or nullptr if
/// no such symbols exist.
const SymbolVector *getSymbolsAt(JITTargetAddress Addr) const {
  auto I = AddrToSymbols.find(Addr);
  if (I == AddrToSymbols.end())
    return nullptr;
  return &I->second;
}

1507private:
std::map<JITTargetAddress, SymbolVector> AddrToSymbols;
1509};

1511/// A function for mutating LinkGraphs.
1512using LinkGraphPassFunction = std::function<Error(LinkGraph &)>;

1514/// A list of LinkGraph passes.
1515using LinkGraphPassList = std::vector<LinkGraphPassFunction>;

1517/// An LinkGraph pass configuration, consisting of a list of pre-prune,
1518/// post-prune, and post-fixup passes.
1519struct PassConfiguration {

/// Pre-prune passes.
///
/// These passes are called on the graph after it is built, and before any
/// symbols have been pruned. Graph nodes still have their original vmaddrs.
///
/// Notable use cases: Marking symbols live or should-discard.
LinkGraphPassList PrePrunePasses;

/// Post-prune passes.
///
/// These passes are called on the graph after dead stripping, but before
/// memory is allocated or nodes assigned their final addresses.
///
/// Notable use cases: Building GOT, stub, and TLV symbols.
LinkGraphPassList PostPrunePasses;

/// Post-allocation passes.
///
/// These passes are called on the graph after memory has been allocated and
/// defined nodes have been assigned their final addresses, but before the
/// context has been notified of these addresses. At this point externals
/// have not been resolved, and symbol content has not yet been copied into
/// working memory.
///
/// Notable use cases: Setting up data structures associated with addresses
/// of defined symbols (e.g. a mapping of __dso_handle to JITDylib* for the
/// JIT runtime) -- using a PostAllocationPass for this ensures that the
/// data structures are in-place before any query for resolved symbols
/// can complete.
LinkGraphPassList PostAllocationPasses;

/// Pre-fixup passes.
///
/// These passes are called on the graph after memory has been allocated,
/// content copied into working memory, and all nodes (including externals)
/// have been assigned their final addresses, but before any fixups have been
/// applied.
///
/// Notable use cases: Late link-time optimizations like GOT and stub
/// elimination.
LinkGraphPassList PreFixupPasses;

/// Post-fixup passes.
///
/// These passes are called on the graph after block contents has been copied
/// to working memory, and fixups applied. Blocks have been updated to point
/// to their fixed up content.
///
/// Notable use cases: Testing and validation.
LinkGraphPassList PostFixupPasses;
1571};

1573/// Flags for symbol lookup.
1574///
1575/// FIXME: These basically duplicate orc::SymbolLookupFlags -- We should merge
1576///        the two types once we have an OrcSupport library.
1577enum class SymbolLookupFlags { RequiredSymbol, WeaklyReferencedSymbol };

1579raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF);

1581/// A map of symbol names to resolved addresses.
1582using AsyncLookupResult = DenseMap<StringRef, JITEvaluatedSymbol>;

1584/// A function object to call with a resolved symbol map (See AsyncLookupResult)
1585/// or an error if resolution failed.
1586class JITLinkAsyncLookupContinuation {
1587public:
virtual ~JITLinkAsyncLookupContinuation() {}
virtual void run(Expected<AsyncLookupResult> LR) = 0;

1591private:
virtual void anchor();
1593};

1595/// Create a lookup continuation from a function object.
1596template <typename Continuation>
1597std::unique_ptr<JITLinkAsyncLookupContinuation>
1598createLookupContinuation(Continuation Cont) {

class Impl final : public JITLinkAsyncLookupContinuation {
public:
  Impl(Continuation C) : C(std::move(C)) {}
  void run(Expected<AsyncLookupResult> LR) override { C(std::move(LR)); }

private:
  Continuation C;
};

return std::make_unique<Impl>(std::move(Cont));
1610}

1612/// Holds context for a single jitLink invocation.
1613class JITLinkContext {
1614public:
using LookupMap = DenseMap<StringRef, SymbolLookupFlags>;

/// Create a JITLinkContext.
JITLinkContext(const JITLinkDylib *JD) : JD(JD) {}

/// Destroy a JITLinkContext.
virtual ~JITLinkContext();

/// Return the JITLinkDylib that this link is targeting, if any.
const JITLinkDylib *getJITLinkDylib() const { return JD; }

/// Return the MemoryManager to be used for this link.
virtual JITLinkMemoryManager &getMemoryManager() = 0;

/// Notify this context that linking failed.
/// Called by JITLink if linking cannot be completed.
virtual void notifyFailed(Error Err) = 0;

/// Called by JITLink to resolve external symbols. This method is passed a
/// lookup continutation which it must call with a result to continue the
/// linking process.
virtual void lookup(const LookupMap &Symbols,
                    std::unique_ptr<JITLinkAsyncLookupContinuation> LC) = 0;

/// Called by JITLink once all defined symbols in the graph have been assigned
/// their final memory locations in the target process. At this point the
/// LinkGraph can be inspected to build a symbol table, however the block
/// content will not generally have been copied to the target location yet.
///
/// If the client detects an error in the LinkGraph state (e.g. unexpected or
/// missing symbols) they may return an error here. The error will be
/// propagated to notifyFailed and the linker will bail out.
virtual Error notifyResolved(LinkGraph &G) = 0;

/// Called by JITLink to notify the context that the object has been
/// finalized (i.e. emitted to memory and memory permissions set). If all of
/// this objects dependencies have also been finalized then the code is ready
/// to run.
virtual void
notifyFinalized(std::unique_ptr<JITLinkMemoryManager::Allocation> A) = 0;

/// Called by JITLink prior to linking to determine whether default passes for
/// the target should be added. The default implementation returns true.
/// If subclasses override this method to return false for any target then
/// they are required to fully configure the pass pipeline for that target.
virtual bool shouldAddDefaultTargetPasses(const Triple &TT) const;

/// Returns the mark-live pass to be used for this link. If no pass is
/// returned (the default) then the target-specific linker implementation will
/// choose a conservative default (usually marking all symbols live).
/// This function is only called if shouldAddDefaultTargetPasses returns true,
/// otherwise the JITContext is responsible for adding a mark-live pass in
/// modifyPassConfig.
virtual LinkGraphPassFunction getMarkLivePass(const Triple &TT) const;

/// Called by JITLink to modify the pass pipeline prior to linking.
/// The default version performs no modification.
virtual Error modifyPassConfig(LinkGraph &G, PassConfiguration &Config);

1674private:
const JITLinkDylib *JD = nullptr;
1676};

1678/// Marks all symbols in a graph live. This can be used as a default,
1679/// conservative mark-live implementation.
1680Error markAllSymbolsLive(LinkGraph &G);

1682/// Create an out of range error for the given edge in the given block.
1683Error makeTargetOutOfRangeError(const LinkGraph &G, const Block &B,
                              const Edge &E);

1686/// Create a LinkGraph from the given object buffer.
1687///
1688/// Note: The graph does not take ownership of the underlying buffer, nor copy
1689/// its contents. The caller is responsible for ensuring that the object buffer
1690/// outlives the graph.
1691Expected<std::unique_ptr<LinkGraph>>
1692createLinkGraphFromObject(MemoryBufferRef ObjectBuffer);

1694/// Link the given graph.
1695void link(std::unique_ptr<LinkGraph> G, std::unique_ptr<JITLinkContext> Ctx);

1697} // end namespace jitlink
1698} // end namespace llvm

1700#endif // LLVM_EXECUTIONENGINE_JITLINK_JITLINK_H