1//===--------- JITLinkGeneric.cpp - Generic JIT linker utilities ----------===//
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// Generic JITLinker utility class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "JITLinkGeneric.h"
14
15#include "llvm/Support/BinaryStreamReader.h"
16#include "llvm/Support/MemoryBuffer.h"
17
18#define DEBUG_TYPE "jitlink"
19
20namespace llvm {
21namespace jitlink {
22
23JITLinkerBase::~JITLinkerBase() = default;
24
25void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
26
27  LLVM_DEBUG({
28    dbgs() << "Starting link phase 1 for graph " << G->getName() << "\n";
29  });
30
31  // Prune and optimize the graph.
32  if (auto Err = runPasses(Passes.PrePrunePasses))
33    return Ctx->notifyFailed(std::move(Err));
34
35  LLVM_DEBUG({
36    dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
37    G->dump(dbgs());
38  });
39
40  prune(*G);
41
42  LLVM_DEBUG({
43    dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
44    G->dump(dbgs());
45  });
46
47  // Run post-pruning passes.
48  if (auto Err = runPasses(Passes.PostPrunePasses))
49    return Ctx->notifyFailed(std::move(Err));
50
51  // Skip straight to phase 2 if the graph is empty with no associated actions.
52  if (G->allocActions().empty() && llvm::all_of(G->sections(), [](Section &S) {
53        return S.getMemLifetime() == orc::MemLifetime::NoAlloc;
54      })) {
55    linkPhase2(std::move(Self), nullptr);
56    return;
57  }
58
59  Ctx->getMemoryManager().allocate(
60      Ctx->getJITLinkDylib(), *G,
61      [S = std::move(Self)](AllocResult AR) mutable {
62        // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
63        // this can be simplified to
64        //          S->linkPhase2(std::move(S), std::move(AR));
65        auto *TmpSelf = S.get();
66        TmpSelf->linkPhase2(std::move(S), std::move(AR));
67      });
68}
69
70void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
71                               AllocResult AR) {
72
73  if (AR)
74    Alloc = std::move(*AR);
75  else
76    return Ctx->notifyFailed(AR.takeError());
77
78  LLVM_DEBUG({
79    dbgs() << "Link graph \"" << G->getName()
80           << "\" before post-allocation passes:\n";
81    G->dump(dbgs());
82  });
83
84  // Run post-allocation passes.
85  if (auto Err = runPasses(Passes.PostAllocationPasses))
86    return abandonAllocAndBailOut(std::move(Self), std::move(Err));
87
88  // Notify client that the defined symbols have been assigned addresses.
89  LLVM_DEBUG(dbgs() << "Resolving symbols defined in " << G->getName() << "\n");
90
91  if (auto Err = Ctx->notifyResolved(*G))
92    return abandonAllocAndBailOut(std::move(Self), std::move(Err));
93
94  auto ExternalSymbols = getExternalSymbolNames();
95
96  // If there are no external symbols then proceed immediately with phase 3.
97  if (ExternalSymbols.empty()) {
98    LLVM_DEBUG({
99      dbgs() << "No external symbols for " << G->getName()
100             << ". Proceeding immediately with link phase 3.\n";
101    });
102    // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
103    // this can be simplified. See below.
104    auto &TmpSelf = *Self;
105    TmpSelf.linkPhase3(std::move(Self), AsyncLookupResult());
106    return;
107  }
108
109  // Otherwise look up the externals.
110  LLVM_DEBUG({
111    dbgs() << "Issuing lookup for external symbols for " << G->getName()
112           << " (may trigger materialization/linking of other graphs)...\n";
113  });
114
115  // We're about to hand off ownership of ourself to the continuation. Grab a
116  // pointer to the context so that we can call it to initiate the lookup.
117  //
118  // FIXME: Once MSVC implements c++17 order of evaluation rules for calls this
119  // can be simplified to:
120  //
121  // Ctx->lookup(std::move(UnresolvedExternals),
122  //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
123  //               Self->linkPhase3(std::move(Self), std::move(Result));
124  //             });
125  Ctx->lookup(std::move(ExternalSymbols),
126              createLookupContinuation(
127                  [S = std::move(Self)](
128                      Expected<AsyncLookupResult> LookupResult) mutable {
129                    auto &TmpSelf = *S;
130                    TmpSelf.linkPhase3(std::move(S), std::move(LookupResult));
131                  }));
132}
133
134void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self,
135                               Expected<AsyncLookupResult> LR) {
136
137  LLVM_DEBUG({
138    dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
139  });
140
141  // If the lookup failed, bail out.
142  if (!LR)
143    return abandonAllocAndBailOut(std::move(Self), LR.takeError());
144
145  // Assign addresses to external addressables.
146  applyLookupResult(*LR);
147
148  LLVM_DEBUG({
149    dbgs() << "Link graph \"" << G->getName()
150           << "\" before pre-fixup passes:\n";
151    G->dump(dbgs());
152  });
153
154  if (auto Err = runPasses(Passes.PreFixupPasses))
155    return abandonAllocAndBailOut(std::move(Self), std::move(Err));
156
157  LLVM_DEBUG({
158    dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
159    G->dump(dbgs());
160  });
161
162  // Fix up block content.
163  if (auto Err = fixUpBlocks(*G))
164    return abandonAllocAndBailOut(std::move(Self), std::move(Err));
165
166  LLVM_DEBUG({
167    dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
168    G->dump(dbgs());
169  });
170
171  if (auto Err = runPasses(Passes.PostFixupPasses))
172    return abandonAllocAndBailOut(std::move(Self), std::move(Err));
173
174  // Skip straight to phase 4 if the graph has no allocation.
175  if (!Alloc) {
176    linkPhase4(std::move(Self), JITLinkMemoryManager::FinalizedAlloc{});
177    return;
178  }
179
180  Alloc->finalize([S = std::move(Self)](FinalizeResult FR) mutable {
181    // FIXME: Once MSVC implements c++17 order of evaluation rules for calls
182    // this can be simplified to
183    //          S->linkPhase2(std::move(S), std::move(AR));
184    auto *TmpSelf = S.get();
185    TmpSelf->linkPhase4(std::move(S), std::move(FR));
186  });
187}
188
189void JITLinkerBase::linkPhase4(std::unique_ptr<JITLinkerBase> Self,
190                               FinalizeResult FR) {
191
192  LLVM_DEBUG({
193    dbgs() << "Starting link phase 4 for graph " << G->getName() << "\n";
194  });
195
196  if (!FR)
197    return Ctx->notifyFailed(FR.takeError());
198
199  Ctx->notifyFinalized(std::move(*FR));
200
201  LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
202}
203
204Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
205  for (auto &P : Passes)
206    if (auto Err = P(*G))
207      return Err;
208  return Error::success();
209}
210
211JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
212  // Identify unresolved external symbols.
213  JITLinkContext::LookupMap UnresolvedExternals;
214  for (auto *Sym : G->external_symbols()) {
215    assert(!Sym->getAddress() &&
216           "External has already been assigned an address");
217    assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
218           "Externals must be named");
219    SymbolLookupFlags LookupFlags =
220        Sym->isWeaklyReferenced() ? SymbolLookupFlags::WeaklyReferencedSymbol
221                                  : SymbolLookupFlags::RequiredSymbol;
222    UnresolvedExternals[Sym->getName()] = LookupFlags;
223  }
224  return UnresolvedExternals;
225}
226
227void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
228  for (auto *Sym : G->external_symbols()) {
229    assert(Sym->getOffset() == 0 &&
230           "External symbol is not at the start of its addressable block");
231    assert(!Sym->getAddress() && "Symbol already resolved");
232    assert(!Sym->isDefined() && "Symbol being resolved is already defined");
233    auto ResultI = Result.find(Sym->getName());
234    if (ResultI != Result.end()) {
235      Sym->getAddressable().setAddress(ResultI->second.getAddress());
236      Sym->setLinkage(ResultI->second.getFlags().isWeak() ? Linkage::Weak
237                                                          : Linkage::Strong);
238      Sym->setScope(ResultI->second.getFlags().isExported() ? Scope::Default
239                                                            : Scope::Hidden);
240    } else
241      assert(Sym->isWeaklyReferenced() &&
242             "Failed to resolve non-weak reference");
243  }
244
245  LLVM_DEBUG({
246    dbgs() << "Externals after applying lookup result:\n";
247    for (auto *Sym : G->external_symbols()) {
248      dbgs() << "  " << Sym->getName() << ": "
249             << formatv("{0:x16}", Sym->getAddress().getValue());
250      switch (Sym->getLinkage()) {
251      case Linkage::Strong:
252        break;
253      case Linkage::Weak:
254        dbgs() << " (weak)";
255        break;
256      }
257      switch (Sym->getScope()) {
258      case Scope::Local:
259        llvm_unreachable("External symbol should not have local linkage");
260      case Scope::Hidden:
261        break;
262      case Scope::Default:
263        dbgs() << " (exported)";
264        break;
265      }
266      dbgs() << "\n";
267    }
268  });
269}
270
271void JITLinkerBase::abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,
272                                           Error Err) {
273  assert(Err && "Should not be bailing out on success value");
274  assert(Alloc && "can not call abandonAllocAndBailOut before allocation");
275  Alloc->abandon([S = std::move(Self), E1 = std::move(Err)](Error E2) mutable {
276    S->Ctx->notifyFailed(joinErrors(std::move(E1), std::move(E2)));
277  });
278}
279
280void prune(LinkGraph &G) {
281  std::vector<Symbol *> Worklist;
282  DenseSet<Block *> VisitedBlocks;
283
284  // Build the initial worklist from all symbols initially live.
285  for (auto *Sym : G.defined_symbols())
286    if (Sym->isLive())
287      Worklist.push_back(Sym);
288
289  // Propagate live flags to all symbols reachable from the initial live set.
290  while (!Worklist.empty()) {
291    auto *Sym = Worklist.back();
292    Worklist.pop_back();
293
294    auto &B = Sym->getBlock();
295
296    // Skip addressables that we've visited before.
297    if (VisitedBlocks.count(&B))
298      continue;
299
300    VisitedBlocks.insert(&B);
301
302    for (auto &E : Sym->getBlock().edges()) {
303      // If the edge target is a defined symbol that is being newly marked live
304      // then add it to the worklist.
305      if (E.getTarget().isDefined() && !E.getTarget().isLive())
306        Worklist.push_back(&E.getTarget());
307
308      // Mark the target live.
309      E.getTarget().setLive(true);
310    }
311  }
312
313  // Collect all defined symbols to remove, then remove them.
314  {
315    LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
316    std::vector<Symbol *> SymbolsToRemove;
317    for (auto *Sym : G.defined_symbols())
318      if (!Sym->isLive())
319        SymbolsToRemove.push_back(Sym);
320    for (auto *Sym : SymbolsToRemove) {
321      LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
322      G.removeDefinedSymbol(*Sym);
323    }
324  }
325
326  // Delete any unused blocks.
327  {
328    LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
329    std::vector<Block *> BlocksToRemove;
330    for (auto *B : G.blocks())
331      if (!VisitedBlocks.count(B))
332        BlocksToRemove.push_back(B);
333    for (auto *B : BlocksToRemove) {
334      LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
335      G.removeBlock(*B);
336    }
337  }
338
339  // Collect all external symbols to remove, then remove them.
340  {
341    LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
342    std::vector<Symbol *> SymbolsToRemove;
343    for (auto *Sym : G.external_symbols())
344      if (!Sym->isLive())
345        SymbolsToRemove.push_back(Sym);
346    for (auto *Sym : SymbolsToRemove) {
347      LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
348      G.removeExternalSymbol(*Sym);
349    }
350  }
351}
352
353} // end namespace jitlink
354} // end namespace llvm
355