[WebAssembly] Elide data segments for .bss sections

[tlively]

Summary

WebAssembly memories are zero-initialized, so when module does not
import its memory initializing .bss sections is guaranteed to be a
no-op. To reduce binary size and initialization time, .bss sections
are simply not emitted into the final binary unless the memory is
imported.

[sbc100]

Great!

lld/wasm/OutputSections.cpp

219

You find this easier to read than:

for (auto S : segments) 
  if (!seg->isImplicit)
    return true;
return false;

?

Maybe I just need get of board with the kids and accept the C++ lambda future that we now live in? I mean it is kinda cool.

Is there something like python's any() builtin in stl that might make this more readable?

[ruiu]

lld/wasm/OutputSections.cpp

219

Yeah, in lld the for loops such as the one Sam suggested are used more often than the higher-order predicate function. Rewriting this with for is perhaps more preferable.

lld/wasm/OutputSegment.h

35

isBss is I think more straightforward name, and I believe we use that variable name in ELF too.

[tlively]

lld/wasm/OutputSections.cpp

219

I agree the for loop is more readable, and it's a real shame that all the nice functional programming idioms are so ugly in C++. Will fix.

lld/wasm/OutputSegment.h

35

Sounds good to me.

lld/test/wasm/Inputs/locals-duplicate1.ll

 target triple = "wasm32-unknown-unknown"
 
 ; Will collide: local (internal linkage) with global (external) linkage
-@colliding_global1 = internal default global i32 0, align 4
+@colliding_global1 = internal default global i32 1, align 4
 ; Will collide: global with local
-@colliding_global2 = default global i32 0, align 4
+@colliding_global2 = default global i32 1, align 4
 ; Will collide: local with local
-@colliding_global3 = internal default global i32 0, align 4
+@colliding_global3 = internal default global i32 1, align 4
 
 ; Will collide: local with global
 define internal i32 @colliding_func1() {
 entry:
   ret i32 2
 }
 ; Will collide: global with local
 define i32 @colliding_func2() {

lld/test/wasm/Inputs/locals-duplicate2.ll

 target triple = "wasm32-unknown-unknown"
 
 ; Will collide: local (internal linkage) with global (external) linkage
-@colliding_global1 = default global i32 0, align 4
+@colliding_global1 = default global i32 1, align 4
 ; Will collide: global with local
-@colliding_global2 = internal default global i32 0, align 4
+@colliding_global2 = internal default global i32 1, align 4
 ; Will collide: local with local
-@colliding_global3 = internal default global i32 0, align 4
+@colliding_global3 = internal default global i32 1, align 4
 
 ; Will collide: local with global
 define i32 @colliding_func1() {
 entry:
   ret i32 2
 }
 ; Will collide: global with local
 define internal i32 @colliding_func2() {

lld/test/wasm/bss-only.ll

+; RUN: llc -filetype=obj %s -o %t.o
+; RUN: wasm-ld -no-gc-sections --no-entry %t.o -o %t.wasm
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; Test that the data section is skipped entirely when there are only
+; bss segments
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+@a = global [1000 x i8] zeroinitializer, align 1
+@b = global i32 0
+
+; CHECK-NOT: - Type:            DATA

lld/test/wasm/custom-section-name.ll

 ; RUN: llc -filetype=obj %s -o %t.o
 ; RUN: wasm-ld -no-gc-sections --no-entry -o %t.wasm %t.o
-; RUN: obj2yaml %t.wasm | FileCheck %s
+; RUN: obj2yaml %t.wasm | FileCheck %s --check-prefixes=CHECK,NO-BSS
+; RUN: wasm-ld -no-gc-sections --no-entry --import-memory -o %t.bss.wasm %t.o
+; RUN: obj2yaml %t.bss.wasm | FileCheck %s --check-prefixes=CHECK,BSS
 ; RUN: wasm-ld -no-gc-sections --no-entry -o %t_reloc.o %t.o --relocatable
 ; RUN: obj2yaml %t_reloc.o | FileCheck -check-prefix RELOC %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 @bss = hidden global i32 zeroinitializer, align 4
 @foo = hidden global i32 zeroinitializer, section "WowZero!", align 4

 ; CHECK-NEXT:          Value:           1028
 ; CHECK-NEXT:        Content:         2A000000
 ; CHECK-NEXT:      - SectionOffset:   27
 ; CHECK-NEXT:        InitFlags:       0
 ; CHECK-NEXT:        Offset:
 ; CHECK-NEXT:          Opcode:          I32_CONST
 ; CHECK-NEXT:          Value:           1032
 ; CHECK-NEXT:        Content:         '07000000'
-; CHECK-NEXT:      - SectionOffset:   37
-; CHECK-NEXT:        InitFlags:       0
-; CHECK-NEXT:        Offset:
-; CHECK-NEXT:          Opcode:          I32_CONST
-; CHECK-NEXT:          Value:           1036
-; CHECK-NEXT:        Content:         '00000000'
+; BSS-NEXT:        - SectionOffset:   37
+; BSS-NEXT:          InitFlags:       0
+; BSS-NEXT:          Offset:
+; BSS-NEXT:            Opcode:          I32_CONST
+; BSS-NEXT:            Value:           1036
+; BSS-NEXT:          Content:         '00000000'
+; NO-BSS-NOT:      - SectionOffset:
 
 ; RELOC-LABEL: SegmentInfo:
 ; RELOC-NEXT:    - Index:           0
 ; RELOC-NEXT:      Name:            'WowZero!'
 ; RELOC-NEXT:      Alignment:       2
 ; RELOC-NEXT:      Flags:           [  ]
 ; RELOC-NEXT:    - Index:           1
 ; RELOC-NEXT:      Name:            MyAwesomeSection

lld/test/wasm/data-layout.ll

 ; CHECK-NEXT:           Value:           1024
 ; CHECK-NEXT:         Content:         68656C6C6F0A00
 ; CHECK-NEXT:       - SectionOffset:   20
 ; CHECK-NEXT:         InitFlags:       0
 ; CHECK-NEXT:         Offset:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           1040
 ; CHECK-NEXT:         Content:         '0100000000000000000000000000000003000000000000000004000034040000'
-; CHECK-NEXT:       - SectionOffset:   58
-; CHECK-NEXT:         InitFlags:       0
-; CHECK-NEXT:         Offset:
-; CHECK-NEXT:           Opcode:          I32_CONST
-; CHECK-NEXT:           Value:           1072
-; CHECK-NEXT:         Content:         '0000000000000000'
 ; CHECK-NEXT:    - Type:            CUSTOM
 
 
 ; RUN: wasm-ld -no-gc-sections --allow-undefined --no-entry \
 ; RUN:     --initial-memory=131072 --max-memory=131072 -o %t_max.wasm %t.o \
 ; RUN:     %t.hello.o
 ; RUN: obj2yaml %t_max.wasm | FileCheck %s -check-prefix=CHECK-MAX
 

lld/test/wasm/data-segments.ll

 ; ACTIVE-NEXT:          Value:           1024
 ; ACTIVE-NEXT:        Content:         636F6E7374616E74000000002B
 ; ACTIVE-NEXT:      - SectionOffset:   26
 ; ACTIVE-NEXT:        InitFlags:       0
 ; ACTIVE-NEXT:        Offset:
 ; ACTIVE-NEXT:          Opcode:          I32_CONST
 ; ACTIVE-NEXT:          Value:           1040
 ; ACTIVE-NEXT:        Content:         68656C6C6F00676F6F646279650000002A000000
-; ACTIVE-NEXT:      - SectionOffset:   53
-; ACTIVE-NEXT:        InitFlags:       0
-; ACTIVE-NEXT:        Offset:
-; ACTIVE-NEXT:          Opcode:          I32_CONST
-; ACTIVE-NEXT:          Value:           1060
-; ACTIVE-NEXT:        Content:         '0000000000
-; ACTIVE-SAME:                           0000000000'
 ; ACTIVE-NEXT:  - Type:            CUSTOM
 ; ACTIVE-NEXT:    Name:            name
 ; ACTIVE-NEXT:    FunctionNames:
 ; ACTIVE-NEXT:      - Index:           0
 ; ACTIVE-NEXT:        Name:            __wasm_call_ctors
 
 ; PASSIVE-LABEL: - Type:            START
 ; PASSIVE-NEXT:    StartFunction:   1

 ; PASSIVE-NEXT:  - Type:            DATA
 ; PASSIVE-NEXT:    Segments:
 ; PASSIVE-NEXT:      - SectionOffset:   3
 ; PASSIVE-NEXT:        InitFlags:       1
 ; PASSIVE-NEXT:        Content:         636F6E7374616E74000000002B
 ; PASSIVE-NEXT:      - SectionOffset:   18
 ; PASSIVE-NEXT:        InitFlags:       1
 ; PASSIVE-NEXT:        Content:         68656C6C6F00676F6F646279650000002A000000
-; PASSIVE-NEXT:      - SectionOffset:   41
-; PASSIVE-NEXT:        InitFlags:       1
-; PASSIVE-NEXT:        Content:         '0000000000
-; PASSIVE-SAME:                           0000000000'
 ; PASSIVE-NEXT:  - Type:            CUSTOM
 ; PASSIVE-NEXT:    Name:            name
 ; PASSIVE-NEXT:    FunctionNames:
 ; PASSIVE-NEXT:      - Index:           0
 ; PASSIVE-NEXT:        Name:            __wasm_call_ctors
 ; PASSIVE-NEXT:      - Index:           1
 ; PASSIVE-NEXT:        Name:            __wasm_init_memory
 ; PASSIVE-NEXT:      - Index:           2
 ; PASSIVE-NEXT:        Name:            __wasm_init_tls

lld/test/wasm/locals-duplicate.test

 ; CHECK-NEXT:         Body:            4186808080000B
 ; CHECK-NEXT:   - Type:            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:         '000000000000000000000000000000000000000000000000'
+; CHECK-NEXT:         Content:         '010000000100000001000000010000000100000001000000'
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name
 ; CHECK-NEXT:     FunctionNames:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            colliding_func1
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Name:            colliding_func2
 ; CHECK-NEXT:       - Index:           2

 ; RELOC-NEXT:         Body:            4180808080000B
 ; RELOC-NEXT:       - Index:           4
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4188808080000B
 ; RELOC-NEXT:       - Index:           5
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4190808080000B
 ; RELOC-NEXT:       - Index:           6
-; RELOC-NEXT:         Locals:          
+; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4181808080000B
 ; RELOC-NEXT:       - Index:           7
-; RELOC-NEXT:         Locals:          
+; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4182808080000B
 ; RELOC-NEXT:       - Index:           8
-; RELOC-NEXT:         Locals:          
+; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4183808080000B
 ; RELOC-NEXT:       - Index:           9
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            41020B
 ; RELOC-NEXT:       - Index:           10
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            41020B
 ; RELOC-NEXT:       - Index:           11
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            41020B
 ; RELOC-NEXT:       - Index:           12
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4184808080000B
 ; RELOC-NEXT:       - Index:           13
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            418C808080000B
 ; RELOC-NEXT:       - Index:           14
 ; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4194808080000B
 ; RELOC-NEXT:       - Index:           15
-; RELOC-NEXT:         Locals:          
+; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4184808080000B
 ; RELOC-NEXT:       - Index:           16
-; RELOC-NEXT:         Locals:          
+; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4185808080000B
 ; RELOC-NEXT:       - Index:           17
-; RELOC-NEXT:         Locals:          
+; RELOC-NEXT:         Locals:
 ; RELOC-NEXT:         Body:            4186808080000B
 ; RELOC-NEXT:   - Type:            DATA
 ; RELOC-NEXT:     Segments:
 ; RELOC-NEXT:       - SectionOffset:   6
 ; RELOC-NEXT:         InitFlags:       0
 ; RELOC-NEXT:         Offset:
 ; RELOC-NEXT:           Opcode:          I32_CONST
 ; RELOC-NEXT:           Value:           0
-; RELOC-NEXT:         Content:         '0000000000000000'
+; RELOC-NEXT:         Content:         '0100000001000000'
 ; RELOC-NEXT:       - SectionOffset:   19
 ; RELOC-NEXT:         InitFlags:       0
 ; RELOC-NEXT:         Offset:
 ; RELOC-NEXT:           Opcode:          I32_CONST
 ; RELOC-NEXT:           Value:           8
-; RELOC-NEXT:         Content:         '0000000000000000'
+; RELOC-NEXT:         Content:         '0100000001000000'
 ; RELOC-NEXT:       - SectionOffset:   32
 ; RELOC-NEXT:         InitFlags:       0
 ; RELOC-NEXT:         Offset:
 ; RELOC-NEXT:           Opcode:          I32_CONST
 ; RELOC-NEXT:           Value:           16
-; RELOC-NEXT:         Content:         '0000000000000000'
+; RELOC-NEXT:         Content:         '0100000001000000'
 ; RELOC-NEXT:   - Type:            CUSTOM
 ; RELOC-NEXT:     Name:            linking
 ; RELOC-NEXT:     Version:         2
 ; RELOC-NEXT:     SymbolTable:
 ; RELOC-NEXT:       - Index:           0
 ; RELOC-NEXT:         Kind:            FUNCTION
 ; RELOC-NEXT:         Name:            colliding_func2
 ; RELOC-NEXT:         Flags:           [  ]

 ; RELOC-NEXT:         Kind:            DATA
 ; RELOC-NEXT:         Name:            colliding_global3
 ; RELOC-NEXT:         Flags:           [ BINDING_LOCAL ]
 ; RELOC-NEXT:         Segment:         2
 ; RELOC-NEXT:         Offset:          4
 ; RELOC-NEXT:         Size:            4
 ; RELOC-NEXT:     SegmentInfo:
 ; RELOC-NEXT:       - Index:           0
-; RELOC-NEXT:         Name:            .bss.colliding_global1
+; RELOC-NEXT:         Name:            .data.colliding_global1
 ; RELOC-NEXT:         Alignment:       2
 ; RELOC-NEXT:         Flags:           [  ]
 ; RELOC-NEXT:       - Index:           1
-; RELOC-NEXT:         Name:            .bss.colliding_global2
+; RELOC-NEXT:         Name:            .data.colliding_global2
 ; RELOC-NEXT:         Alignment:       2
 ; RELOC-NEXT:         Flags:           [  ]
 ; RELOC-NEXT:       - Index:           2
-; RELOC-NEXT:         Name:            .bss.colliding_global3
+; RELOC-NEXT:         Name:            .data.colliding_global3
 ; RELOC-NEXT:         Alignment:       2
 ; RELOC-NEXT:         Flags:           [  ]
 ; RELOC-NEXT:   - Type:            CUSTOM
 ; RELOC-NEXT:     Name:            name
 ; RELOC-NEXT:     FunctionNames:
 ; RELOC-NEXT:       - Index:           0
 ; RELOC-NEXT:         Name:            colliding_func1
 ; RELOC-NEXT:       - Index:           1

lld/wasm/OutputSections.h

 public:
   explicit DataSection(ArrayRef<OutputSegment *> segments)
       : OutputSection(llvm::wasm::WASM_SEC_DATA), segments(segments) {}
 
   size_t getSize() const override { return header.size() + bodySize; }
   void writeTo(uint8_t *buf) override;
   uint32_t getNumRelocations() const override;
   void writeRelocations(raw_ostream &os) const override;
-  bool isNeeded() const override { return segments.size() > 0; }
+  bool isNeeded() const override;
   void finalizeContents() override;
 
 protected:
   ArrayRef<OutputSegment *> segments;
   std::string dataSectionHeader;
   size_t bodySize = 0;
 };
 

lld/wasm/OutputSections.cpp

 
 void CodeSection::writeRelocations(raw_ostream &os) const {
   for (const InputChunk *c : functions)
     c->writeRelocations(os);
 }
 
 void DataSection::finalizeContents() {
   raw_string_ostream os(dataSectionHeader);
+  unsigned segmentCount = std::count_if(
+      segments.begin(), segments.end(),
+      [](OutputSegment *segment) { return !segment->isImplicit; });
 
-  writeUleb128(os, segments.size(), "data segment count");
+  writeUleb128(os, segmentCount, "data segment count");
   os.flush();
   bodySize = dataSectionHeader.size();
 
   assert((!config->isPic || segments.size() <= 1) &&
          "Currenly only a single data segment is supported in PIC mode");
 
   for (OutputSegment *segment : segments) {
+    if (segment->isImplicit)
+      continue;
     raw_string_ostream os(segment->header);
     writeUleb128(os, segment->initFlags, "init flags");
     if (segment->initFlags & WASM_SEGMENT_HAS_MEMINDEX)
       writeUleb128(os, 0, "memory index");
     if ((segment->initFlags & WASM_SEGMENT_IS_PASSIVE) == 0) {
       WasmInitExpr initExpr;
       if (config->isPic) {
         initExpr.Opcode = WASM_OPCODE_GLOBAL_GET;
void DataSection::writeTo(uint8_t *buf) {
   // Write section header
   memcpy(buf, header.data(), header.size());
   buf += header.size();
 
   // Write data section headers
   memcpy(buf, dataSectionHeader.data(), dataSectionHeader.size());
 
   for (const OutputSegment *segment : segments) {
+    if (segment->isImplicit)
+      continue;
     // Write data segment header
     uint8_t *segStart = buf + segment->sectionOffset;
     memcpy(segStart, segment->header.data(), segment->header.size());
 
     // Write segment data payload
     for (const InputChunk *chunk : segment->inputSegments)
       chunk->writeTo(buf);
   }
 }
 
 uint32_t DataSection::getNumRelocations() const {
   uint32_t count = 0;
   for (const OutputSegment *seg : segments)
     for (const InputChunk *inputSeg : seg->inputSegments)
       count += inputSeg->getNumRelocations();
   return count;
 }
 
 void DataSection::writeRelocations(raw_ostream &os) const {
   for (const OutputSegment *seg : segments)
     for (const InputChunk *c : seg->inputSegments)
       c->writeRelocations(os);
 }
 
+bool DataSection::isNeeded() const {
+  return std::find_if(segments.begin(), segments.end(),
+                      [](OutputSegment *const seg) {
+                        return !seg->isImplicit;
+                      }) != segments.end();
+}
+
 void CustomSection::finalizeContents() {
   raw_string_ostream os(nameData);
   encodeULEB128(name.size(), os);
   os << name;
   os.flush();
 
   for (InputSection *section : inputSections) {
     section->outputOffset = payloadSize;

lld/wasm/OutputSegment.h

void addInputSegment(InputSegment *inSeg) {
     inputSegments.push_back(inSeg);
     size = llvm::alignTo(size, 1ULL << inSeg->getAlignment());
     inSeg->outputSeg = this;
     inSeg->outputSegmentOffset = size;
     size += inSeg->getSize();
   }
 
   StringRef name;
+  bool isImplicit = false;
   uint32_t index = 0;
   uint32_t initFlags = 0;
   uint32_t sectionOffset = 0;
   uint32_t alignment = 0;
   uint32_t startVA = 0;
   std::vector<InputSegment *> inputSegments;
 
   // Sum of the size of the all the input segments

lld/wasm/SyntheticSections.h

public:
   uint32_t numEntries() const { return indirectFunctions.size(); }
 
 protected:
   std::vector<const FunctionSymbol *> indirectFunctions;
 };
 
 class DataCountSection : public SyntheticSection {
 public:
-  DataCountSection(uint32_t numSegments)
-      : SyntheticSection(llvm::wasm::WASM_SEC_DATACOUNT),
-        numSegments(numSegments) {}
+  DataCountSection(ArrayRef<OutputSegment *> segments);
   bool isNeeded() const override;
   void writeBody() override;
 
 protected:
   uint32_t numSegments;
 };
 
 // Create the custom "linking" section containing linker metadata.

lld/wasm/SyntheticSections.cpp

void ElemSection::writeBody() {
   uint32_t tableIndex = config->tableBase;
   for (const FunctionSymbol *sym : indirectFunctions) {
     assert(sym->getTableIndex() == tableIndex);
     writeUleb128(os, sym->getFunctionIndex(), "function index");
     ++tableIndex;
   }
 }
 
+DataCountSection::DataCountSection(ArrayRef<OutputSegment *> segments)
+    : SyntheticSection(llvm::wasm::WASM_SEC_DATACOUNT),
+      numSegments(std::count_if(
+          segments.begin(), segments.end(),
+          [](OutputSegment *const segment) { return !segment->isImplicit; })) {}
+
 void DataCountSection::writeBody() {
   writeUleb128(bodyOutputStream, numSegments, "data count");
 }
 
 bool DataCountSection::isNeeded() const {
   return numSegments && config->sharedMemory;
 }
 

lld/wasm/Writer.cpp

for (InputSegment *segment : file->segments) {
         continue;
       StringRef name = getOutputDataSegmentName(segment->getName());
       OutputSegment *&s = segmentMap[name];
       if (s == nullptr) {
         LLVM_DEBUG(dbgs() << "new segment: " << name << "\n");
         s = make<OutputSegment>(name);
         if (config->sharedMemory || name == ".tdata")
           s->initFlags = WASM_SEGMENT_IS_PASSIVE;
+        // Exported memories are guaranteed to be zero-initialized, so no need
+        // to emit data segments for bss sections.
+        // TODO: consider initializing bss sections with memory.fill
+        // instructions when memory is imported and bulk-memory is available.
+        if (!config->importMemory && !config->relocatable &&
+            name.startswith(".bss"))
+          s->isImplicit = true;
         segments.push_back(s);
       }
       s->addInputSegment(segment);
       LLVM_DEBUG(dbgs() << "added data: " << name << ": " << s->size << "\n");
     }
   }
 
   // Sort segments by type, placing .bss last
void Writer::createSyntheticSections() {
   out.functionSec = make<FunctionSection>();
   out.tableSec = make<TableSection>();
   out.memorySec = make<MemorySection>();
   out.globalSec = make<GlobalSection>();
   out.eventSec = make<EventSection>();
   out.exportSec = make<ExportSection>();
   out.startSec = make<StartSection>(segments.size());
   out.elemSec = make<ElemSection>();
-  out.dataCountSec = make<DataCountSection>(segments.size());
+  out.dataCountSec = make<DataCountSection>(segments);
   out.linkingSec = make<LinkingSection>(initFunctions, segments);
   out.nameSec = make<NameSection>();
   out.producersSec = make<ProducersSection>();
   out.targetFeaturesSec = make<TargetFeaturesSection>();
 }
 
 void Writer::run() {
   if (config->relocatable || config->isPic)