[lld][WebAssembly] Delay the merging of section when dynamic linking

[sbc100]

Summary

With dynamic linking we have the current limitation that there can be
only a single active data segment (since we use __memory_base as the
load address and we can't do arithemtic in constant expresions).

This change delays the merging of active segments until a little later
in the linking process which means that the grouping of data by section,
and the magic start/end symbols work as expected under dynamic
linking.

[sbc100]

rebase

lld/test/wasm/data-segments.ll

 ; PASSIVE-PIC-NEXT:      - Index:           1
 ; PASSIVE-PIC-NEXT:        Locals:          []
 ; PASSIVE-PIC-NEXT:        Body:            0B
 ; PASSIVE-PIC-NEXT:      - Index:           2
 ; PASSIVE-PIC-NEXT:        Locals:
 ; PASSIVE32-PIC-NEXT:          - Type:            I32
 ; PASSIVE64-PIC-NEXT:          - Type:            I64
 ; PASSIVE-PIC-NEXT:            Count:           1
-; PASSIVE32-PIC-NEXT:        Body:            230141B4CE006A2100200041004101FE480200044020004101427FFE0102001A05410023016A410041B1CE00FC08000020004102FE1702002000417FFE0002001A0BFC09000B
-; PASSIVE64-PIC-NEXT:        Body:            230142B4CE006A2100200041004101FE480200044020004101427FFE0102001A05420023016A410041B1CE00FC08000020004102FE1702002000417FFE0002001A0BFC09000B
+; PASSIVE32-PIC-NEXT:        Body:            230141B4CE006A2100200041004101FE480200044020004101427FFE0102001A05410023016A410041B4CE00FC08000020004102FE1702002000417FFE0002001A0BFC09000B
+; PASSIVE64-PIC-NEXT:        Body:            230142B4CE006A2100200041004101FE480200044020004101427FFE0102001A05420023016A410041B4CE00FC08000020004102FE1702002000417FFE0002001A0BFC09000B
 ; PASSIVE-PIC-NEXT:      - Index:           3
 ; PASSIVE-PIC-NEXT:        Locals:          []
 ; PASSIVE-PIC-NEXT:        Body:            0B
 ; PASSIVE-PIC-NEXT:  - Type:            DATA
 ; PASSIVE-PIC-NEXT:    Segments:
 ; PASSIVE-PIC-NEXT:      - SectionOffset:   4
 ; PASSIVE-PIC-NEXT:        InitFlags:       1
 

lld/test/wasm/tls-no-shared.s

 # CHECK-NEXT:           Opcode:          I32_CONST
 # CHECK-NEXT:           Value:           66576
 # __tls_base
 # CHECK-NEXT:       - Index:           1
 # CHECK-NEXT:         Type:            I32
 # CHECK-NEXT:         Mutable:         false
 # CHECK-NEXT:         InitExpr:
 # CHECK-NEXT:           Opcode:          I32_CONST
-# CHECK-NEXT:           Value:           1028
+# CHECK-NEXT:           Value:           1024
 # CHECK-NEXT:   - Type:            EXPORT
 
 #      CHECK:  - Type:            DATA
 # .data
 # CHECK-NEXT:    Segments:
 # CHECK-NEXT:      - SectionOffset:   7
 # CHECK-NEXT:        InitFlags:       0
 # CHECK-NEXT:        Offset:
 # CHECK-NEXT:          Opcode:          I32_CONST
 # CHECK-NEXT:          Value:           1024
-# CHECK-NEXT:        Content:         2A000000
+# CHECK-NEXT:        Content:         2B000000
 # .tdata
 # CHECK-NEXT:      - SectionOffset:   17
 # CHECK-NEXT:        InitFlags:       0
 # CHECK-NEXT:        Offset:
 # CHECK-NEXT:          Opcode:          I32_CONST
 # CHECK-NEXT:          Value:           1028
-# CHECK-NEXT:        Content:         2B000000
+# CHECK-NEXT:        Content:         2A000000

lld/wasm/InputChunks.h

public:
 
   uint32_t getAlignment() const { return segment.Data.Alignment; }
   StringRef getName() const override { return segment.Data.Name; }
   StringRef getDebugName() const override { return StringRef(); }
   uint32_t getComdat() const override { return segment.Data.Comdat; }
   uint32_t getInputSectionOffset() const override {
     return segment.SectionOffset;
   }
+  uint64_t getVA() const;
 
   const OutputSegment *outputSeg = nullptr;
   int32_t outputSegmentOffset = 0;
 
 protected:
   ArrayRef<uint8_t> data() const override { return segment.Data.Content; }
 
   const WasmSegment &segment;

lld/wasm/InputChunks.cpp

void InputFunction::writeTo(uint8_t *buf) const {
   }
 
   unsigned chunkSize = end - lastRelocEnd;
   LLVM_DEBUG(dbgs() << "  write final chunk: " << chunkSize << "\n");
   memcpy(buf, lastRelocEnd, chunkSize);
   LLVM_DEBUG(dbgs() << "  total: " << (buf + chunkSize - orig) << "\n");
 }
 
+uint64_t InputSegment::getVA() const {
+  return outputSeg->startVA + outputSegmentOffset;
+}
+
 // Generate code to apply relocations to the data section at runtime.
 // This is only called when generating shared libaries (PIC) where address are
 // not known at static link time.
 void InputSegment::generateRelocationCode(raw_ostream &os) const {
   LLVM_DEBUG(dbgs() << "generating runtime relocations: " << getName()
                     << " count=" << relocations.size() << "\n");
 
   unsigned opcode_ptr_const = config->is64.getValueOr(false)
                                   ? WASM_OPCODE_I64_CONST
                                   : WASM_OPCODE_I32_CONST;
   unsigned opcode_ptr_add = config->is64.getValueOr(false)
                                 ? WASM_OPCODE_I64_ADD
                                 : WASM_OPCODE_I32_ADD;
 
   auto tombstone = getTombstone();
   // TODO(sbc): Encode the relocations in the data section and write a loop
   // here to apply them.
-  uint64_t segmentVA = outputSeg->startVA + outputSegmentOffset;
   for (const WasmRelocation &rel : relocations) {
     uint64_t offset = rel.Offset - getInputSectionOffset();
-    uint64_t outputOffset = segmentVA + offset;
+    uint64_t outputOffset = getVA() + offset;
 
     LLVM_DEBUG(dbgs() << "gen reloc: type=" << relocTypeToString(rel.Type)
                       << " addend=" << rel.Addend << " index=" << rel.Index
                       << " output offset=" << outputOffset << "\n");
 
     // Get __memory_base
     writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
     writeUleb128(os, WasmSym::memoryBase->getGlobalIndex(), "memory_base");

lld/wasm/MapFile.cpp

if (auto *code = dyn_cast<CodeSection>(osec)) {
           os << symStr[sym] << '\n';
       }
     } else if (auto *data = dyn_cast<DataSection>(osec)) {
       for (auto *oseg : data->segments) {
         writeHeader(os, oseg->startVA, data->getOffset() + oseg->sectionOffset,
                     oseg->size);
         os << oseg->name << '\n';
         for (auto *chunk : oseg->inputSegments) {
-          writeHeader(os, oseg->startVA + chunk->outputSegmentOffset,
+          writeHeader(os, chunk->getVA(),
                       chunk->outputSec->getOffset() + chunk->outputOffset,
                       chunk->getSize());
           os.indent(8) << toString(chunk) << '\n';
           for (Symbol *sym : sectionSyms[chunk])
             os << symStr[sym] << '\n';
         }
       }
     } else if (auto *globals = dyn_cast<GlobalSection>(osec)) {
       for (auto *global : globals->inputGlobals) {
         writeHeader(os, global->getAssignedIndex(), 0, 0);
         os.indent(8) << global->getName() << '\n';
       }
     }
     // TODO: other section/symbol types
   }
 }

lld/wasm/OutputSegment.h

 namespace wasm {
 
 class InputSegment;
 
 class OutputSegment {
 public:
   OutputSegment(StringRef n) : name(n) {}
 
-  void addInputSegment(InputSegment *inSeg) {
-    alignment = std::max(alignment, inSeg->getAlignment());
+  void addInputSegment(InputSegment *inSeg, uint32_t forceAlignment = 0) {
+    uint32_t segAlign = std::max(forceAlignment, inSeg->getAlignment());
+    alignment = std::max(alignment, segAlign);
     inputSegments.push_back(inSeg);
-    size = llvm::alignTo(size, 1ULL << inSeg->getAlignment());
+    size = llvm::alignTo(size, 1ULL << segAlign);
     inSeg->outputSeg = this;
     inSeg->outputSegmentOffset = size;
     size += inSeg->getSize();
   }
 
   StringRef name;
   bool isBss = false;
   uint32_t index = 0;

lld/wasm/Symbols.cpp

DefinedFunction::DefinedFunction(StringRef name, uint32_t flags, InputFile *f,
                                  InputFunction *function)
     : FunctionSymbol(name, DefinedFunctionKind, flags, f,
                      function ? &function->signature : nullptr),
       function(function) {}
 
 uint64_t DefinedData::getVirtualAddress() const {
   LLVM_DEBUG(dbgs() << "getVirtualAddress: " << getName() << "\n");
   if (segment)
-    return segment->outputSeg->startVA + segment->outputSegmentOffset + offset;
+    return segment->getVA() + offset;
   return offset;
 }
 
 void DefinedData::setVirtualAddress(uint64_t value) {
   LLVM_DEBUG(dbgs() << "setVirtualAddress " << name << " -> " << value << "\n");
   assert(!segment);
   offset = value;
 }

lld/wasm/Writer.cpp

private:
   void populateProducers();
   void populateTargetFeatures();
   void calculateInitFunctions();
   void calculateImports();
   void calculateExports();
   void calculateCustomSections();
   void calculateTypes();
   void createOutputSegments();
+  void combineOutputSegments();
   void layoutMemory();
   void createHeader();
 
   void addSection(OutputSection *sec);
 
   void addSections();
 
   void createCustomSections();
   void createSyntheticSections();
+  void createSyntheticSectionsPostLayout();
   void finalizeSections();
 
   // Custom sections
   void createRelocSections();
 
   void writeHeader();
   void writeSections();
 

 }
 
 static StringRef getOutputDataSegmentName(StringRef name) {
   // We only support one thread-local segment, so we must merge the segments
   // despite --no-merge-data-segments.
   // We also need to merge .tbss into .tdata so they share the same offsets.
   if (name.startswith(".tdata") || name.startswith(".tbss"))
     return ".tdata";
-  // With PIC code we currently only support a single data segment since
-  // we only have a single __memory_base to use as our base address.
-  if (config->isPic)
-    return ".data";
   if (!config->mergeDataSegments)
     return name;
   if (name.startswith(".text."))
     return ".text";
   if (name.startswith(".data."))
     return ".data";
   if (name.startswith(".bss."))
     return ".bss";
for (ObjFile *file : symtab->objectFiles) {
     }
   }
 
   // Sort segments by type, placing .bss last
   std::stable_sort(segments.begin(), segments.end(),
                    [](const OutputSegment *a, const OutputSegment *b) {
                      auto order = [](StringRef name) {
                        return StringSwitch<int>(name)
-                           .StartsWith(".rodata", 0)
-                           .StartsWith(".data", 1)
-                           .StartsWith(".tdata", 2)
+                           .StartsWith(".tdata", 0)
+                           .StartsWith(".rodata", 1)
+                           .StartsWith(".data", 2)
                            .StartsWith(".bss", 4)
                            .Default(3);
                      };
                      return order(a->name) < order(b->name);
                    });
 
   for (size_t i = 0; i < segments.size(); ++i)
     segments[i]->index = i;
 }
 
+void Writer::combineOutputSegments() {
+  // With PIC code we currently only support a single data segment since
+  // we only have a single __memory_base to use as our base address.
+  // This pass combines all non-TLS data segments into a single .data
+  // segment.
+  // This restructions can be relaxed once we have extended constant
+  // expressions available:
+  // https://github.com/WebAssembly/extended-const
+  assert(config->isPic);
+  if (segments.size() <= 1)
+    return;
+  OutputSegment *combined = nullptr;
+  std::vector<OutputSegment *> new_segments;
+  for (OutputSegment *s : segments) {
+    if (s->name == ".tdata") {
+      new_segments.push_back(s);
+    } else {
+      if (!combined) {
+        combined = make<OutputSegment>(".data");
+        combined->startVA = s->startVA;
+        if (config->sharedMemory)
+          combined->initFlags = WASM_DATA_SEGMENT_IS_PASSIVE;
+      }
+      bool first = true;
+      for (InputSegment *inSeg : s->inputSegments) {
+        uint32_t alignment = first ? s->alignment : 0;
+        first = false;
+#ifndef NDEBUG
+        uint64_t oldVA = inSeg->getVA();
+#endif
+        combined->addInputSegment(inSeg, alignment);
+#ifndef NDEBUG
+        uint64_t newVA = inSeg->getVA();
+        assert(oldVA == newVA);
+#endif
+      }
+    }
+  }
+  if (combined) {
+    new_segments.push_back(combined);
+    segments = new_segments;
+    for (size_t i = 0; i < segments.size(); ++i)
+      segments[i]->index = i;
+  }
+}
+
 static void createFunction(DefinedFunction *func, StringRef bodyContent) {
   std::string functionBody;
   {
     raw_string_ostream os(functionBody);
     writeUleb128(os, bodyContent.size(), "function size");
     os << bodyContent;
   }
   ArrayRef<uint8_t> body = arrayRefFromStringRef(saver.save(functionBody));
void Writer::createSyntheticSections() {
   out.functionSec = make<FunctionSection>();
   out.tableSec = make<TableSection>();
   out.memorySec = make<MemorySection>();
   out.eventSec = make<EventSection>();
   out.globalSec = make<GlobalSection>();
   out.exportSec = make<ExportSection>();
   out.startSec = make<StartSection>();
   out.elemSec = make<ElemSection>();
+  out.producersSec = make<ProducersSection>();
+  out.targetFeaturesSec = make<TargetFeaturesSection>();
+}
+
+void Writer::createSyntheticSectionsPostLayout() {
   out.dataCountSec = make<DataCountSection>(segments);
   out.linkingSec = make<LinkingSection>(initFunctions, segments);
   out.nameSec = make<NameSection>(segments);
-  out.producersSec = make<ProducersSection>();
-  out.targetFeaturesSec = make<TargetFeaturesSection>();
 }
 
 void Writer::run() {
   if (config->relocatable || config->isPic)
     config->globalBase = 0;
 
   // For PIC code the table base is assigned dynamically by the loader.
   // For non-PIC, we start at 1 so that accessing table index 0 always traps.
   if (!config->isPic) {
     config->tableBase = 1;
     if (WasmSym::definedTableBase)
       WasmSym::definedTableBase->setVirtualAddress(config->tableBase);
   }
 
   log("-- createOutputSegments");
   createOutputSegments();
   log("-- createSyntheticSections");
   createSyntheticSections();
-  log("-- populateProducers");
-  populateProducers();
-  log("-- calculateImports");
-  calculateImports();
   log("-- layoutMemory");
   layoutMemory();
 
   if (!config->relocatable) {
     // Create linker synthesized __start_SECNAME/__stop_SECNAME symbols
     // This has to be done after memory layout is performed.
-    for (const OutputSegment *seg : segments)
+    for (const OutputSegment *seg : segments) {
       addStartStopSymbols(seg);
     }
+  }
 
   // Delay reporting error about explict exports until after addStartStopSymbols
   // which can create optional symbols.
   for (auto &entry : config->exportedSymbols) {
     StringRef name = entry.first();
     Symbol *sym = symtab->find(name);
     if (sym && sym->isDefined())
       sym->forceExport = true;
     else if (config->unresolvedSymbols == UnresolvedPolicy::ReportError)
       error(Twine("symbol exported via --export not found: ") + name);
     else if (config->unresolvedSymbols == UnresolvedPolicy::Warn)
       warn(Twine("symbol exported via --export not found: ") + name);
   }
 
+  if (config->isPic) {
+    log("-- combineOutputSegments");
+    combineOutputSegments();
+  }
+
+  log("-- createSyntheticSectionsPostLayout");
+  createSyntheticSectionsPostLayout();
+  log("-- populateProducers");
+  populateProducers();
+  log("-- calculateImports");
+  calculateImports();
   log("-- scanRelocations");
   scanRelocations();
   log("-- finalizeIndirectFunctionTable");
   finalizeIndirectFunctionTable();
   log("-- createSyntheticInitFunctions");
   createSyntheticInitFunctions();
   log("-- assignIndexes");
   assignIndexes();