[ORC][JITLink] Do not claim dead symbols

[Hahnfeld]

Summary

For this to work, only claim or externalize weak symbols post-prune
because the pruning phase also propagates liveness from blocks to
symbols. This fixes JIT codegen of code involving exceptions without
also registering the .eh_frame because the DW.ref.__gxx_personality_v0
would be dead-stripped and claimed at the same time.

[lhames]

Thanks for continuing to dig into this, and sorry that it has taken me so long to find time to check it out. You've identified the underlying issue: "liveness" and "responsibility" being out-of-sync for these symbols. As things stand* though, we want to run claimOrExternalizeWeakAndCommonSymbols prior to dead stripping: The primary purpose of claimOrExternalizeWeakAndCommonSymbols is to externalize regular (non-late-breaking) weak defs that are absent from the materialization responsibility due to deliberate removal (because ORC decided to source the definition from some other materialization unit). Externalizing those weak defs before running dead stripping allows them, and their otherwise-unused transitive dependencies, to be dead-stripped. Auto-claiming "late-breaking" weak-defs at this point is mostly a matter of efficiency: the algorithm for "late breaking" weak defs is the same for regular weak defs**, and in the 99% case a late-breaking weak-def is in the graph because it's needed (so it would survive dead-stripping anyway).

I think ba26b5ef15dc should fix your issue for now.

• Right now we have a single dead-stripping phase. Some of these phase-ordering issues may be easier to tackle if we could run dead-stripping on the graph at multiple points, but I haven't had time to give the idea serious consideration.

• We have no way to distinguish regular and "late-breaking" weaks at this level. We could distinguish them, and improve them performance of claimAndExternalizeWeakAndCommonSymbols if materialization responsibility objects were able to express non-responsibility (as opposed to absence of responsibility). In that case the claimOrExternalizeWeakAndCommonSymbols would only need to call defineMaterializing for the set of symbols where there's no responsibility indicator one way or another.

[Hahnfeld]

@lhames yes, this approach also seems to work. However, this means that we are emitting more weak symbols than we need to, right? But I guess I just have to accept that you implement something if you don't agree with my patches...

[lhames]

However, this means that we are emitting more weak symbols than we need to, right?

It means that we claim and emit late-breaking definitions by default, rather than dead-stripping them by default. In my experience with code generated from C and C++, late-breaking weak defs are only inserted because something in the same TU needs them and in this case both approaches behave the same (for late-breaking defs, at least).

But I guess I just have to accept that you implement something if you don't agree with my patches...

I can't stress enough how much I appreciate you digging into the issue and proposing patches. This would have gone unsolved for much longer if it had not been for your hard work. That said I thought there was an issue with your approach, which is why I implemented ba26b5ef15dc instead. I tried to explain the issue in abstract terms, but a concrete example might be better. Consider the following two-file program:

% cat main.c
static int X = 42;
int *P = &X;
extern int getValuePointedToByP();
int main(int argc, char *argv[]) {
  return getValuePointedToByP();
}

% cat ext.c
static int Y = 42;
int __attribute__((weak)) *P = &Y;
int getValuePointedToByP() {
  return *P;
}

In this case the definition of P from main.c is guaranteed to be chosen as it is strong, whereas ext.c's definition is weak. When we jit-link ext.o we want to externalize its weak definition of P prior to dead-stripping so that both P and Y from ext.o can be removed. If we wait until after dead-stripping then the block for Y will already have been marked live and will be allocated memory unnecessarily.

In this case Y is just an int and the overhead is just a few bytes, but in practice Y could be anything (e.g. a struct, or a function) and could have its own references that pull in still more symbols (and potentially whole other files). This is the motivation for externalizing symbols that are not in the responsibility set prior to dead-stripping, rather than after.

As mentioned above: there may be other ways to solve this problem by introducing new dead-stripping phases, and there may also be ways to improve the performance of what we have by introducing explicit non-responsibility markers, but these are speculative ideas. I believe that ba26b5ef15dc is the right approach for now.

llvm/lib/ExecutionEngine/Orc/ObjectLinkingLayer.cpp

public:
 
   LinkGraphPassFunction getMarkLivePass(const Triple &TT) const override {
     return [this](LinkGraph &G) { return markResponsibilitySymbolsLive(G); };
   }
 
   Error modifyPassConfig(LinkGraph &LG, PassConfiguration &Config) override {
     // Add passes to mark duplicate defs as should-discard, and to walk the
     // link graph to build the symbol dependence graph.
-    Config.PrePrunePasses.push_back([this](LinkGraph &G) {
+    Config.PostPrunePasses.push_back([this](LinkGraph &G) {
       return claimOrExternalizeWeakAndCommonSymbols(G);
     });
 
     Layer.modifyPassConfig(*MR, LG, Config);
 
     Config.PostPrunePasses.push_back(
         [this](LinkGraph &G) { return computeNamedSymbolDependencies(G); });
 
private:
 
   Error claimOrExternalizeWeakAndCommonSymbols(LinkGraph &G) {
     auto &ES = Layer.getExecutionSession();
 
     SymbolFlagsMap NewSymbolsToClaim;
     std::vector<std::pair<SymbolStringPtr, Symbol *>> NameToSym;
 
     auto ProcessSymbol = [&](Symbol *Sym) {
-      if (Sym->hasName() && Sym->getLinkage() == Linkage::Weak &&
+      if (Sym->isLive() && Sym->hasName() &&
+          Sym->getLinkage() == Linkage::Weak &&
           Sym->getScope() != Scope::Local) {
         auto Name = ES.intern(Sym->getName());
         if (!MR->getSymbols().count(ES.intern(Sym->getName()))) {
           JITSymbolFlags SF = JITSymbolFlags::Weak;
           if (Sym->getScope() == Scope::Default)
             SF |= JITSymbolFlags::Exported;
           NewSymbolsToClaim[Name] = SF;
           NameToSym.push_back(std::make_pair(std::move(Name), Sym));