[ELF] - Allow to postpone SymbolAssignment proccessing.

[grimar]

Summary

In some cases we are unable to handle SymbolAssignment instantly.
Expression may depend on offset of input section which was not set yet,
because corresponding output section command was not handled.

Patch adds a list of dependency symbols for Expr class. Before perform
assign, this list is updated and checked if all dependencies are resolved.
If not, assign expression is delayed.

This fixes PR32031.

ELF/LinkerScript.h

 struct Expr {
   std::function<uint64_t(uint64_t)> Val;
   std::function<bool()> IsAbsolute;
 
   // If expression is section-relative the function below is used
   // to get the output section pointer.
   std::function<const OutputSection *()> Section;
 
+  // Initially contains symbols this expression uses. During
+  // processing commands, resolved dependencies are removed.
+  std::vector<StringRef> DependsOn;
+
   uint64_t operator()(uint64_t Dot) const { return Val(Dot); }
   operator bool() const { return (bool)Val; }
 
   Expr(std::function<uint64_t(uint64_t)> Val, std::function<bool()> IsAbsolute,
        std::function<const OutputSection *()> Section)
       : Val(Val), IsAbsolute(IsAbsolute), Section(Section) {}
   template <typename T>
   Expr(T V) : Expr(V, [] { return true; }, [] { return nullptr; }) {}
public:
   const OutputSection *getOutputSection(const Twine &Loc, StringRef S) override;
   uint64_t getOutputSectionSize(StringRef S) override;
 
   std::vector<OutputSection *> *OutputSections;
 
   int getSectionIndex(StringRef Name);
 
 private:
+  bool canCalculate(SymbolAssignment *Cmd);
   void assignSymbol(SymbolAssignment *Cmd, bool InSec = false);
   void addSymbol(SymbolAssignment *Cmd);
   void computeInputSections(InputSectionDescription *);
   void setDot(Expr E, const Twine &Loc, bool InSec = false);
 
   void discard(ArrayRef<InputSectionBase *> V);
 
   std::vector<InputSectionBase *>

ELF/LinkerScript.cpp

else
       error(Loc + ": unable to move location counter backward");
   }
   Dot = Val;
   // Update to location counter means update to section size.
   if (InSec)
     CurOutSec->Size = Dot - CurOutSec->Addr;
 }
 
+template <class ELFT>
+bool LinkerScript<ELFT>::canCalculate(SymbolAssignment *Cmd) {
+  if (Cmd->Expression.DependsOn.empty())
+    return true;
+
+  std::vector<StringRef> Dep = std::move(Cmd->Expression.DependsOn);
+  for (StringRef Name : Dep) {
+    const OutputSection *OutSec = getSymbolSection(Name);
+    if (!OutSec || OutSec->HasAddr)
+      continue;
+    Cmd->Expression.DependsOn.push_back(Name);
+  }
+
+  return Cmd->Expression.DependsOn.empty();
+}
+
 // Sets value of a symbol. Two kinds of symbols are processed: synthetic
 // symbols, whose value is an offset from beginning of section and regular
 // symbols whose value is absolute.
 template <class ELFT>
 void LinkerScript<ELFT>::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
   if (Cmd->Name == ".") {
     setDot(Cmd->Expression, Cmd->Location, InSec);
     return;
template <class ELFT> void LinkerScript<ELFT>::switchTo(OutputSection *Sec) {
   if (AlreadyOutputOS.count(Sec))
     return;
 
   flush();
   CurOutSec = Sec;
 
   Dot = alignTo(Dot, CurOutSec->Addralign);
   CurOutSec->Addr = isTbss<ELFT>(CurOutSec) ? Dot + ThreadBssOffset : Dot;
+  CurOutSec->HasAddr = true;
 
   // If neither AT nor AT> is specified for an allocatable section, the linker
   // will set the LMA such that the difference between VMA and LMA for the
   // section is the same as the preceding output section in the same region
   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
   if (LMAOffset)
     CurOutSec->LMAOffset = LMAOffset();
 }
void LinkerScript<ELFT>::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   // * Any value meaning a regular section.
   // To handle that, create a dummy aether section that fills the void before
   // the linker scripts switches to another section. It has an index of one
   // which will map to whatever the first actual section is.
   auto *Aether = make<OutputSection>("", 0, SHF_ALLOC);
   Aether->SectionIndex = 1;
   switchTo(Aether);
 
+  std::vector<SymbolAssignment*> PendingAssignments;
   for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
+    // Sometimes we cannot calculate the symbols value right now.
+    // For example it may depend on offset of input section, which
+    // was not yet assigned because corresponding OutputSectionCommand
+    // was not processed. We postpone execution in that case.
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base.get())) {
+      if (!canCalculate(Cmd))
+        PendingAssignments.push_back(Cmd);
+      else
         assignSymbol(Cmd);
       continue;
     }
 
     if (auto *Cmd = dyn_cast<AssertCommand>(Base.get())) {
       Cmd->Expression(Dot);
       continue;
     }
 
     auto *Cmd = cast<OutputSectionCommand>(Base.get());
     assignOffsets(Cmd);
+
+    for (auto I = PendingAssignments.begin(); I != PendingAssignments.end();) {
+      if (!canCalculate(*I)) {
+        ++I;
+        continue;
+      }
+      assignSymbol(*I);
+      I = PendingAssignments.erase(I);
+    }
   }
 
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
   for (OutputSection *Sec : *OutputSections) {
     if (Sec->Flags & SHF_ALLOC)
       MinVA = std::min<uint64_t>(MinVA, Sec->Addr);
     else
       Sec->Addr = 0;
Expr ScriptParser::readPrimary() {
   // Tok is a literal number.
   uint64_t V;
   if (readInteger(Tok, V))
     return [=](uint64_t Dot) { return V; };
 
   // Tok is a symbol name.
   if (Tok != "." && !isValidCIdentifier(Tok))
     setError("malformed number: " + Tok);
-  return {[=](uint64_t Dot) { return getSymbolValue(Location, Tok, Dot); },
+  Expr E = {[=](uint64_t Dot) { return getSymbolValue(Location, Tok, Dot); },
             [=] { return isAbsolute(Tok); },
             [=] { return ScriptBase->getSymbolSection(Tok); }};
+  if (Tok != ".")
+    E.DependsOn.push_back(Tok);
+  return E;
 }
 
 Expr ScriptParser::readTernary(Expr Cond) {
   Expr L = readExpr();
   expect(":");
   Expr R = readExpr();
   return [=](uint64_t Dot) { return Cond(Dot) ? L(Dot) : R(Dot); };
 }

ELF/OutputSections.h

void updateAlignment(uint64_t Alignment) {
     if (Alignment > Addralign)
       Addralign = Alignment;
   }
 
   // If true, this section will be page aligned on disk.
   // Typically the first section of each PT_LOAD segment has this flag.
   bool PageAlign = false;
 
+  // true means that VA was assigned to section.
+  bool HasAddr = false;
+
   // Pointer to the first section in PT_LOAD segment, which this section
   // also resides in. This field is used to correctly compute file offset
   // of a section. When two sections share the same load segment, difference
   // between their file offsets should be equal to difference between their
   // virtual addresses. To compute some section offset we use the following
   // formula: Off = Off_first + VA - VA_first.
   OutputSection *FirstInPtLoad = nullptr;
 

ELF/Writer.cpp

if (needsPtLoad<ELFT>(Sec)) {
       Sec->Addr = VA;
       VA += Sec->Size;
     } else if (Sec->Flags & SHF_TLS && Sec->Type == SHT_NOBITS) {
       uintX_t TVA = VA + ThreadBssOffset;
       TVA = alignTo(TVA, Alignment);
       Sec->Addr = TVA;
       ThreadBssOffset = TVA - VA + Sec->Size;
     }
+    Sec->HasAddr = true;
   }
 }
 
 // Adjusts the file alignment for a given output section and returns
 // its new file offset. The file offset must be the same with its
 // virtual address (modulo the page size) so that the loader can load
 // executables without any address adjustment.
 template <class ELFT, class uintX_t>

test/ELF/linkerscript/symbols-dependency.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "SECTIONS { barsym1 = barsym; .bar : { *(.bar*) } }" > %t.script
+# RUN: ld.lld %t --script %t.script -o %t1
+# RUN: llvm-readobj -symbols %t1 | FileCheck %s
+
+# CHECK:     Symbol {
+# CHECK:      Name: barsym
+# CHECK-NEXT: Value: 0x[[VAL:.*]]
+# CHECK:      Name: barsym1
+# CHECK-NEXT: Value: 0x[[VAL]]
+
+.section .bar.1, "a"
+.quad 0
+
+.section .bar.2, "a"
+.quad 0
+.global barsym
+barsym: