[lto] Kill undefined extern_weak declarations before opt

[eugenis]

Summary

If an extern_weak declaration is resolved as undefined, RAUW it with
a null pointer and remove it from the module before running LTO
optimizations.

Besides the obvious codegen improvement, it allows CFI to avoid
generating jump tables for such functions (which can not be done
correctly, as a jump table entry can not be weak).

[mehdi_amini]

include/llvm/LTO/LTO.h

469

Add that it is only valid for extern_weak

lib/LTO/LTO.cpp

253

This logic isn't clear to me, mostly because it is testing redundant thing.
We should not allow Res.Undefined to be used with a non extern_weak, so I expect some error handling instead.

475

Comment.

[pcc]

include/llvm/LTO/LTO.h

428

Do we need to track this globally?

lib/LTO/LTO.cpp

346

I would have thought that you could keep track of the undefined symbols in a local variable here and RAUW them in a loop below. That way, you can avoid the global tracking.

[mehdi_amini]

lib/LTO/LTO.cpp

346

How do you address ThinLTO?

Which needs to be added to the patch BTW.

[pcc]

lib/LTO/LTO.cpp

346

How do you address ThinLTO?

The way I see this feature eventually being added to ThinLTO is:

• decouple LLVM linkages from ThinLTO summary linkages
• (orthogonally: represent "drop" as another type of linkage -- this would allow us to drop unchosen linkonce or weak (non-odr) definitions)
• add a new "linkage" (at this point we can probably call it a resolution) which represents an undefined extern_weak.
• copy all resolution information into the summary during addThinLTO while handling each input file (during mergeFrom or thereabouts)

Which needs to be added to the patch BTW.

It doesn't seem necessary to do so in the first patch. This is just an optimisation, and the CFI feature that relies on this does not (currently) work with ThinLTO. But @eugenis please do add a FIXME.

tools/llvm-lto2/llvm-lto2.cpp

68

Please update the documentation.

[mehdi_amini]

lib/LTO/LTO.cpp

346

The way I see this feature eventually being added to ThinLTO is [...]

Please send an RFC for such kind of changes.

It doesn't seem necessary to do so in the first patch.

I don't like this. One of the main reason I wanted a unified API is also exactly to avoid these kinds of discrepancies and designed these from the ground-up for LTO *and* ThinLTO.

[mehdi_amini]

lib/LTO/LTO.cpp

346

To clarify my position, I'm fine with an "incremental" patch, as long as we first validate a design that handle both, i.e. not having ThinLTO folks (including me) arriving after the fact and having to basically redo everything from scratch because the way it is done cannot integrate with ThinLTO.

[eugenis]

It appears that this optimization is only possible in executables.

Extern_weak declarations can not be bound at link time when building a shared library, because any available definition is not final, and even the lack of any definition is not final.

This means that CFI will have to deal with undefined extern_weak declarations somehow, which makes this change only a minor optimization, so I'm going to drop it for now. I agree with the thinlto comments, and if I decide to work on this again, I'll start with an RFC.

include/llvm/LTO/LTO.h

struct GlobalResolution {
     /// Special partition numbers.
     enum : unsigned {
       /// A partition number has not yet been assigned to this global.
       Unknown = -1u,
 
       /// This global is either used by more than one partition or has an
       /// external reference, and therefore cannot be internalized.
       External = -2u,
+
+      /// This global is undefined.
+      Undefined = -3u,
     };
   };
 
   // Global mapping from mangled symbol names to resolutions.
   StringMap<GlobalResolution> GlobalResolutions;
 
   void addSymbolToGlobalRes(object::IRObjectFile *Obj,
                             SmallPtrSet<GlobalValue *, 8> &Used,
private:
 
   mutable bool CalledGetMaxTasks = false;
 };
 
 /// The resolution for a symbol. The linker must provide a SymbolResolution for
 /// each global symbol based on its internal resolution of that symbol.
 struct SymbolResolution {
   SymbolResolution()
-      : Prevailing(0), FinalDefinitionInLinkageUnit(0), VisibleToRegularObj(0) {
-  }
+      : Prevailing(0), FinalDefinitionInLinkageUnit(0), VisibleToRegularObj(0),
+        Undefined(0) {}
   /// The linker has chosen this definition of the symbol.
   unsigned Prevailing : 1;
 
   /// The definition of this symbol is unpreemptable at runtime and is known to
   /// be in this linkage unit.
   unsigned FinalDefinitionInLinkageUnit : 1;
 
   /// The definition of this symbol is visible outside of the LTO unit.
   unsigned VisibleToRegularObj : 1;
+
+  /// This symbol has no definition.
+  unsigned Undefined : 1;
 };
 
 } // namespace lto
 } // namespace llvm
 
 #endif

lib/LTO/LTO.cpp

void LTO::addSymbolToGlobalRes(IRObjectFile *Obj,
                                SmallPtrSet<GlobalValue *, 8> &Used,
                                const InputFile::Symbol &Sym,
                                SymbolResolution Res, unsigned Partition) {
   GlobalValue *GV = Obj->getSymbolGV(Sym.I->getRawDataRefImpl());
 
   auto &GlobalRes = GlobalResolutions[Sym.getName()];
   if (GV) {
     GlobalRes.UnnamedAddr &= GV->hasGlobalUnnamedAddr();
-    if (Res.Prevailing)
+    if (Res.Prevailing || Res.Undefined)
       GlobalRes.IRName = GV->getName();
   }
-  if (Res.VisibleToRegularObj || (GV && Used.count(GV)) ||
+  if (Res.Undefined && GV && GV->isDeclarationForLinker())
+    GlobalRes.Partition = GlobalResolution::Undefined;
+  else if (Res.VisibleToRegularObj || (GV && Used.count(GV)) ||
       (GlobalRes.Partition != GlobalResolution::Unknown &&
        GlobalRes.Partition != Partition))
     GlobalRes.Partition = GlobalResolution::External;
   else
     GlobalRes.Partition = Partition;
 }
 
 static void writeToResolutionFile(raw_ostream &OS, InputFile *Input,
                                   ArrayRef<SymbolResolution> Res) {
   StringRef Path = Input->getMemoryBufferRef().getBufferIdentifier();
   OS << Path << '\n';
   auto ResI = Res.begin();
   for (const InputFile::Symbol &Sym : Input->symbols()) {
     assert(ResI != Res.end());
     SymbolResolution Res = *ResI++;
 
     OS << "-r=" << Path << ',' << Sym.getName() << ',';
     if (Res.Prevailing)
       OS << 'p';
     if (Res.FinalDefinitionInLinkageUnit)
       OS << 'l';
     if (Res.VisibleToRegularObj)
       OS << 'x';
+    if (Res.Undefined)
+      OS << 'u';
     OS << '\n';
   }
   assert(ResI == Res.end());
 }
 
 Error LTO::add(std::unique_ptr<InputFile> Input,
                ArrayRef<SymbolResolution> Res) {
   assert(!CalledGetMaxTasks);
for (const InputFile::Symbol &Sym :
                   InputFile::symbol_iterator(Obj->symbol_end()))) {
     assert(ResI != Res.end());
     SymbolResolution Res = *ResI++;
     addSymbolToGlobalRes(Obj.get(), Used, Sym, Res, 0);
 
     GlobalValue *GV = Obj->getSymbolGV(Sym.I->getRawDataRefImpl());
     if (Sym.getFlags() & object::BasicSymbolRef::SF_Undefined)
       continue;
     if (Res.Prevailing && GV) {
       Keep.push_back(GV);
       switch (GV->getLinkage()) {
       default:
         break;
       case GlobalValue::LinkOnceAnyLinkage:
         GV->setLinkage(GlobalValue::WeakAnyLinkage);
         break;
       case GlobalValue::LinkOnceODRLinkage:
if (Conf.PreOptModuleHook &&
       !Conf.PreOptModuleHook(0, *RegularLTO.CombinedModule))
     return Error();
 
   if (!Conf.CodeGenOnly) {
     for (const auto &R : GlobalResolutions) {
       if (R.second.IRName.empty())
         continue;
       if (R.second.Partition != 0 &&
-          R.second.Partition != GlobalResolution::External)
+          R.second.Partition != GlobalResolution::External &&
+          R.second.Partition != GlobalResolution::Undefined)
         continue;
 
       GlobalValue *GV =
           RegularLTO.CombinedModule->getNamedValue(R.second.IRName);
+
+      if (GV && GV->hasExternalWeakLinkage() &&
+          R.second.Partition == GlobalResolution::Undefined) {
+        GV->replaceAllUsesWith(Constant::getNullValue(GV->getType()));
+        GV->eraseFromParent();
+        continue;
+      }
+
       // Ignore symbols defined in other partitions.
       if (!GV || GV->hasLocalLinkage())
         continue;
       GV->setUnnamedAddr(R.second.UnnamedAddr ? GlobalValue::UnnamedAddr::Global
                                               : GlobalValue::UnnamedAddr::None);
       if (R.second.Partition == 0)
         GV->setLinkage(GlobalValue::InternalLinkage);
     }

test/LTO/Resolution/X86/weak.ll

+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-lto2 %t.bc -r %t.bc,main,plx -r %t.bc,_Z1fv,u -o %t.o -save-temps
+; RUN: llvm-dis %t.o.0.2.internalize.bc -o - | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @main() {
+entry:
+; weak symbol _Z1fv resolved as undefined, replaced with nullptr.
+; CHECK-NOT: _Z1fv
+  br i1 icmp ne (void ()* @_Z1fv, void ()* null), label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  ret i32 1
+  unreachable
+
+if.end:                                           ; preds = %entry
+  ret i32 0
+}
+
+declare extern_weak void @_Z1fv()

test/tools/gold/X86/comdat.ll

 ; RES: 1.o,r12,px{{$}}
 ; RES: 1.o,a11,px{{$}}
 ; RES: 1.o,a12,px{{$}}
 ; RES: 1.o,a13,px{{$}}
 ; RES: 1.o,a14,px{{$}}
 ; RES: 1.o,a15,px{{$}}
 
 ; RES: 2.o,f1,l{{$}}
-; RES: 2.o,will_be_undefined,{{$}}
+; RES: 2.o,will_be_undefined,u{{$}}
 ; RES: 2.o,v1,{{$}}
 ; RES: 2.o,r21,px{{$}}
 ; RES: 2.o,r22,px{{$}}
 ; RES: 2.o,a21,px{{$}}
 ; RES: 2.o,a22,px{{$}}
 ; RES: 2.o,a23,px{{$}}
 ; RES: 2.o,a24,px{{$}}
 ; RES: 2.o,a25,px{{$}}

test/tools/gold/X86/emit-llvm.ll

 
 ; CHECK-DAG: @g5 = weak_odr global i32 32
 @g5 = linkonce_odr local_unnamed_addr global i32 32
 
 ; CHECK-DAG: @g6 = internal unnamed_addr global i32 32
 @g6 = linkonce_odr unnamed_addr global i32 32
 
 @g7 = extern_weak global i32
-; CHECK-DAG: @g7 = extern_weak global i32
+; CHECK-NOT: @g7
 
 @g8 = external global i32
 
 ; CHECK-DAG: define internal void @f1()
 ; OPT2-NOT: @f1
 define hidden void @f1() {
   ret void
 }

 ; RES: .o,f7,px{{$}}
 ; RES: .o,f8,px{{$}}
 ; RES: .o,g1,px{{$}}
 ; RES: .o,g2,p{{$}}
 ; RES: .o,g3,p{{$}}
 ; RES: .o,g4,px{{$}}
 ; RES: .o,g5,px{{$}}
 ; RES: .o,g6,p{{$}}
-; RES: .o,g7,{{$}}
-; RES: .o,g8,{{$}}
+; RES: .o,g7,u{{$}}
+; RES: .o,g8,u{{$}}
 ; RES: .o,g9,px{{$}}
 ; RES: .o,g10,px{{$}}

test/tools/gold/X86/weak_undefined.ll

+; RUN: llvm-as %s -o %t.o
+; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
+; RUN:    --plugin-opt=emit-llvm \
+; RUN:    -shared %t.o -o %t2.o
+; RUN: llvm-dis %t2.o -o - | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @main() {
+entry:
+; weak symbol _Z1fv resolved as undefined, replaced with nullptr.
+; CHECK-NOT: _Z1fv
+  br i1 icmp ne (void ()* @_Z1fv, void ()* null), label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  ret i32 1
+  unreachable
+
+if.end:                                           ; preds = %entry
+  ret i32 0
+}
+
+declare extern_weak void @_Z1fv()

tools/gold/gold-plugin.cpp

ld_plugin_symbol_resolution Resolution =
         (ld_plugin_symbol_resolution)Sym.resolution;
 
     ResolutionInfo &Res = ResInfo[Sym.name];
 
     switch (Resolution) {
     case LDPR_UNKNOWN:
       llvm_unreachable("Unexpected resolution");
 
+    case LDPR_UNDEF:
+      R.Undefined = true;
+      break;
+
     case LDPR_RESOLVED_IR:
     case LDPR_RESOLVED_EXEC:
     case LDPR_RESOLVED_DYN:
     case LDPR_PREEMPTED_IR:
     case LDPR_PREEMPTED_REG:
-    case LDPR_UNDEF:
       break;
 
     case LDPR_PREVAILING_DEF_IRONLY:
       R.Prevailing = true;
       break;
 
     case LDPR_PREVAILING_DEF:
       R.Prevailing = true;

tools/llvm-lto2/llvm-lto2.cpp

cl::desc("Specify a symbol resolution: filename,symbolname,resolution\n"
              "where \"resolution\" is a sequence (which may be empty) of the\n"
              "following characters:\n"
              " p - prevailing: the linker has chosen this definition of the\n"
              "     symbol\n"
              " l - local: the definition of this symbol is unpreemptable at\n"
              "     runtime and is known to be in this linkage unit\n"
              " x - externally visible: the definition of this symbol is\n"
              "     visible outside of the LTO unit\n"
              "A resolution for each symbol must be specified."),
     cl::ZeroOrMore);
 
 static void check(Error E, std::string Msg) {
   if (!E)
     return;
   handleAllErrors(std::move(E), [&](ErrorInfoBase &EIB) {
     errs() << "llvm-lto: " << Msg << ": " << EIB.message().c_str() << '\n';
   });
for (std::string R : SymbolResolutions) {
     SymbolResolution Res;
     for (char C : Rest) {
       if (C == 'p')
         Res.Prevailing = true;
       else if (C == 'l')
         Res.FinalDefinitionInLinkageUnit = true;
       else if (C == 'x')
         Res.VisibleToRegularObj = true;
+      else if (C == 'u')
+        Res.Undefined = true;
       else
         llvm::errs() << "invalid character " << C << " in resolution: " << R
                      << '\n';
     }
     CommandLineResolutions[{FileName, SymbolName}] = Res;
   }
 
   std::vector<std::unique_ptr<MemoryBuffer>> MBs;