[lld] Use -1 as tombstone value for discarded code ranges

[Eric]

Summary

Under existing behavior discarded functions are relocated to have the start pc 0. This causes problems when debugging as they typically overlap the first function and lldb symbol resolution frequently chooses a discarded function instead of the correct one. Using the value -1 or -2 (depending on which DWARF section we are writing) is sufficient to prevent lldb from resolving to these symbols.

[sbc100]

Are there no tests that fail under this change? If not, I guess we should add one.

[MaskRay]

In D91803#2405939, @sbc100 wrote:

Are there no tests that fail under this change? If not, I guess we should add one.

Failed Tests (3):
  lld :: wasm/debug-removed-fn.ll
  lld :: wasm/debuginfo.test
  lld :: wasm/undefined-weak-call.ll

The change does not seem right. For non-debug sections (when --allow-undefined is set), addend; .debug_ranges/.debug_loc => -2; other .debug_* => -1

[dblaikie]

In D91803#2405969, @MaskRay wrote:

In D91803#2405939, @sbc100 wrote:

Are there no tests that fail under this change? If not, I guess we should add one.

Failed Tests (3):
  lld :: wasm/debug-removed-fn.ll
  lld :: wasm/debuginfo.test
  lld :: wasm/undefined-weak-call.ll

The change does not seem right. For non-debug sections (when --allow-undefined is set), addend; .debug_ranges/.debug_loc => -2; other .debug_* => -1

+1 to that. Could also use a test case for this new functionality.

[Eric]

Hope this looks better!

[sbc100]

lgtm!.. I'll leave the final approval to @yurydelendik

lld/wasm/InputChunks.cpp

408

Maybe a comment here explaining why we do this?

lld/wasm/InputChunks.h

230

We use the lowerCamel style so I think this should be tombstoneValue?

lld/wasm/InputFiles.cpp

196

So setting the tombstone to zero means we should include the Addend ?

lld/wasm/InputFiles.h

106

It seems like all of the callsites should probably include the tombstone no?

Perhaps remove the default and specify it at each call site?

[MaskRay]

lld/wasm/InputChunks.h

230

Is the space consumption a concern?

[sbc100]

lld/wasm/InputChunks.h

230

I not been to concerted about adding data O(input chunk). Honestly, we have not done much in the way optimizing wasm-ld for speed or memory consumption. Rui often guided me to keep the symbol size down and to avoid per-symbol hash lookup.. but per-input-chunk data I've not been too concerned about.

I guess one alternative would be to store a tombstone-type enum with three possible values?

[dblaikie]

lld/test/wasm/debug-removed-fn.ll

7

This looks suspcious - is something in the implementation (or the dumper) truncating the 64 bit -1 to a 32 bit -1? Or is this a bug in the dumper that it's printing out a 32bit value as a 64 bit value?

lld/wasm/InputChunks.cpp

411–417

Avoid "else after return" per the LLVM style guide. Also nice to reduce nesting, so I'd probably go with something like:

if (!.debug_)
  return 0;
if (.debug_ranges || .debug_loc)
  return -2
return -1

lld/wasm/InputFiles.cpp

196

Yeah, I guess that's beyond my debug info purview - but I'd suggest checking what bfd ld does here & maybe going with that, rather than what gold does/lld used to do. Which is probably absolute 0 rather than addend. For broader compatibility (& probably make this code a bit less subtle - avoiding the tombstone of zero not really being zero)

[MaskRay]

lld/wasm/InputChunks.h

230

The sizes of SymbolUnion and InputSections are important for the ELF's port.

As an example, the basic block sections feature cost us more than 1% peak memory usage. D91018 claimed back 0.6%

[sbc100]

lld/wasm/InputChunks.h

230

Point taken. And since wasm mandates -ffunction-sections and -fdata-sections is the default we are even more effected than ELF by default I guess.

I'm embarrassed to say I have done zero benchmarking of wasm-ld thus far.

[Eric]

lld/test/wasm/debug-removed-fn.ll

7

Looks like this file is coming from a R_WASM_FUNCTION_OFFSET_I32 type relocation so this is being written as 32 bits. I assume the dumper casts to 64 bits whether it read a 32 or 64 bit address.

lld/wasm/InputChunks.h

230

Note that this is not in InputChunk, it is in InputSection, so this is once per custom wasm section, of which there might be what, a dozen? I could get rid of it but then we would need to do 1-3 string comparisons against the section name for every relocation in that section, which I was concerned could be costly, though I also have done no wasm-ld benchmarking.

I actually considered putting it in InputChunk so as to avoid lots of virtual function calls. If I did that this would cost us a megabyte for especially large applications.

lld/wasm/InputFiles.cpp

196

Yes, this was based on MaskRay@'s comment on my initial commit. If there is not agreement on this perhaps bring discussion back to the email thread?

lld/wasm/InputFiles.h

106

This felt different to me because zero has a unique meaning, it is not used as a tombstone it means we don't do tombstoning. I don't think adding ", 0" to the other callsites would make the code any clearer but of course I can do that if there is a strong preference for it.

[Eric]

lld/test/wasm/debug-removed-fn.ll

7

It turns out if I update my llvm repo to include your tombstone handling code in llvm-dwarfdump, this line disappears.

[sbc100]

There are 4 callers of calcNewValue():

InputChunk::writeTo
InputFunction::calculateSize
InputFunction::writeTo
InputSegment::generateRelocationCode

It seems that they should all be consistent in passing getTombstone() as the second argument. It doesn't make sense that different callsites would get a different new value for a given relocation. They all logically want to get the same answer I believe.

[Eric]

Okay, I've changed it to call getTombstone everywhere.

[dblaikie]

lld/wasm/InputFiles.cpp

196

Ah, this one?

The change does not seem right. For non-debug sections (when --allow-undefined is set), addend; .debug_ranges/.debug_loc => -2; other .debug_* => -1

@MaskRay is that what ld.bfd does? ("addend" for non-debug sections)

[MaskRay]

lld/wasm/InputChunks.cpp

298

For all these file->calcNewValue(rel, getTombstone()) calls, shouldn't getTombstone() cached to avoid performance overhead?

lld/wasm/InputFiles.cpp

196

Yes for "addend" for non-debug sections. This makes subtraction work.

[dblaikie]

lld/wasm/InputFiles.cpp

196

Ah, fair enough - thanks for the context!

[Eric]

Hope everyone had a nice Thanksgiving break! Are any further changes necessary here?

[MaskRay]

Looks great! Please include diff context in future patches (https://llvm.org/docs/GettingStarted.html#sending-patches)

lld/wasm/InputChunks.cpp

435

-2l is correct but is not an appropriate literal suffix. UINT64_C(-2) can be used.

lld/wasm/InputFiles.cpp

210

Delete braces

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

lld/test/wasm/debug-removed-fn.ll

 ; RUN: llc -filetype=obj < %s -o %t.o
 ; RUN: wasm-ld %t.o --no-entry --export=foo -o %t.wasm
 ; RUN: llvm-dwarfdump -debug-line -debug-ranges %t.wasm | FileCheck %s
 
 ; CHECK: Address
 ; CHECK: 0x0000000000000005
-; CHECK: 0x0000000000000000
+; CHECK-NEXT: 0x0000000000000006
+; CHECK-EMPTY:
 
 ; CHECK: .debug_ranges contents:
 ; CHECK: 00000000 {{[0-9]+}} {{[0-9]+}}
-; CHECK: 00000000 {{[0-9]+}} {{[0-9]+}}
+; CHECK: 00000000 fffffffe fffffffe
 ; CHECK: 00000000 <End of list>
 
 ; ModuleID = 't.bc'
 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown-wasm"
 
 ; Function Attrs: noinline nounwind optnone
 define hidden i32 @foo() #0 !dbg !7 {

lld/test/wasm/debuginfo.test

 CHECK-NEXT:                DW_AT_encoding (DW_ATE_unsigned)
 
 CHECK:   DW_TAG_variable
 CHECK-NEXT:                DW_AT_name ("z")
 CHECK-NEXT:                DW_AT_type (0x000000a7 "int[2]")
 CHECK-NEXT:                DW_AT_external (true)
 CHECK-NEXT:                DW_AT_decl_file  ("{{.*}}hi_foo.c")
 CHECK-NEXT:                DW_AT_decl_line  (8)
-CHECK-NEXT:                DW_AT_location (DW_OP_addr 0x0)
+CHECK-NEXT:                DW_AT_location (DW_OP_addr 0xffffffff)
 
 CHECK:   DW_TAG_subprogram
 CHECK-NEXT:                DW_AT_low_pc
 CHECK-NEXT:                DW_AT_high_pc
 CHECK-NEXT:                DW_AT_frame_base
 CHECK-NEXT:                DW_AT_name ("foo")
 CHECK-NEXT:                DW_AT_decl_file  ("{{.*}}hi_foo.c")
 CHECK-NEXT:                DW_AT_decl_line  (3)
 
 CHECK:     DW_TAG_formal_parameter
 CHECK-NEXT:                  DW_AT_name ("p")
 CHECK-NEXT:                  DW_AT_decl_file  ("{{.*}}hi_foo.c")
 CHECK-NEXT:                  DW_AT_decl_line  (3)
 

lld/wasm/InputChunks.h

public:
   // Signals the chunk was discarded by COMDAT handling.
   unsigned discarded : 1;
 
 protected:
   InputChunk(ObjFile *f, Kind k)
       : file(f), live(!config->gcSections), discarded(false), sectionKind(k) {}
   virtual ~InputChunk() = default;
   virtual ArrayRef<uint8_t> data() const = 0;
+  virtual uint64_t getTombstone() const { return 0; }
 
   // Verifies the existing data at relocation targets matches our expectations.
   // This is performed only debug builds as an extra sanity check.
   void verifyRelocTargets() const;
 
   ArrayRef<WasmRelocation> relocations;
   Kind sectionKind;
 };
protected:
   StringRef debugName;
   ArrayRef<uint8_t> body;
 };
 
 // Represents a single Wasm Section within an input file.
 class InputSection : public InputChunk {
 public:
   InputSection(const WasmSection &s, ObjFile *f)
-      : InputChunk(f, InputChunk::Section), section(s) {
+      : InputChunk(f, InputChunk::Section), section(s), tombstoneValue(getTombstoneForSection(s.Name)) {
     assert(section.Type == llvm::wasm::WASM_SEC_CUSTOM);
   }
 
   StringRef getName() const override { return section.Name; }
   StringRef getDebugName() const override { return StringRef(); }
   uint32_t getComdat() const override { return UINT32_MAX; }
 
 protected:
   ArrayRef<uint8_t> data() const override { return section.Content; }
 
   // Offset within the input section.  This is only zero since this chunk
   // type represents an entire input section, not part of one.
   uint32_t getInputSectionOffset() const override { return 0; }
+  uint64_t getTombstone() const override { return tombstoneValue; }
+  static uint64_t getTombstoneForSection(StringRef name);
 
   const WasmSection &section;
+  const uint64_t tombstoneValue;
 };
 
 } // namespace wasm
 
 std::string toString(const wasm::InputChunk *);
 StringRef relocTypeToString(uint8_t relocType);
 
 } // namespace lld
 
 #endif // LLD_WASM_INPUT_CHUNKS_H

lld/wasm/InputChunks.cpp

 
 #ifndef NDEBUG
   verifyRelocTargets();
 #endif
 
   LLVM_DEBUG(dbgs() << "applying relocations: " << toString(this)
                     << " count=" << relocations.size() << "\n");
   int32_t off = outputOffset - getInputSectionOffset();
+  auto tombstone = getTombstone();
 
   for (const WasmRelocation &rel : relocations) {
     uint8_t *loc = buf + rel.Offset + off;
-    auto value = file->calcNewValue(rel);
+    auto value = file->calcNewValue(rel, tombstone);
     LLVM_DEBUG(dbgs() << "apply reloc: type=" << relocTypeToString(rel.Type));
     if (rel.Type != R_WASM_TYPE_INDEX_LEB)
       LLVM_DEBUG(dbgs() << " sym=" << file->getSymbols()[rel.Index]->getName());
     LLVM_DEBUG(dbgs() << " addend=" << rel.Addend << " index=" << rel.Index
                       << " value=" << value << " offset=" << rel.Offset
                       << "\n");
 
     switch (rel.Type) {
void InputFunction::calculateSize() {
   const uint8_t *secStart = file->codeSection->Content.data();
   const uint8_t *funcStart = secStart + getInputSectionOffset();
   uint32_t functionSizeLength;
   decodeULEB128(funcStart, &functionSizeLength);
 
   uint32_t start = getInputSectionOffset();
   uint32_t end = start + function->Size;
 
+  auto tombstone = getTombstone();
+
   uint32_t lastRelocEnd = start + functionSizeLength;
   for (const WasmRelocation &rel : relocations) {
     LLVM_DEBUG(dbgs() << "  region: " << (rel.Offset - lastRelocEnd) << "\n");
     compressedFuncSize += rel.Offset - lastRelocEnd;
-    compressedFuncSize += getRelocWidth(rel, file->calcNewValue(rel));
+    compressedFuncSize += getRelocWidth(rel, file->calcNewValue(rel, tombstone));
     lastRelocEnd = rel.Offset + getRelocWidthPadded(rel);
   }
   LLVM_DEBUG(dbgs() << "  final region: " << (end - lastRelocEnd) << "\n");
   compressedFuncSize += end - lastRelocEnd;
 
   // Now we know how long the resulting function is we can add the encoding
   // of its length
   uint8_t buf[5];
void InputFunction::writeTo(uint8_t *buf) const {
 
   buf += outputOffset;
   uint8_t *orig = buf;
   (void)orig;
 
   const uint8_t *secStart = file->codeSection->Content.data();
   const uint8_t *funcStart = secStart + getInputSectionOffset();
   const uint8_t *end = funcStart + function->Size;
+  auto tombstone = getTombstone();
   uint32_t count;
   decodeULEB128(funcStart, &count);
   funcStart += count;
 
   LLVM_DEBUG(dbgs() << "write func: " << getName() << "\n");
   buf += encodeULEB128(compressedFuncSize, buf);
   const uint8_t *lastRelocEnd = funcStart;
   for (const WasmRelocation &rel : relocations) {
     unsigned chunkSize = (secStart + rel.Offset) - lastRelocEnd;
     LLVM_DEBUG(dbgs() << "  write chunk: " << chunkSize << "\n");
     memcpy(buf, lastRelocEnd, chunkSize);
     buf += chunkSize;
-    buf += writeCompressedReloc(buf, rel, file->calcNewValue(rel));
+    buf += writeCompressedReloc(buf, rel, file->calcNewValue(rel, tombstone));
     lastRelocEnd = secStart + rel.Offset + getRelocWidthPadded(rel);
   }
 
   unsigned chunkSize = end - lastRelocEnd;
   LLVM_DEBUG(dbgs() << "  write final chunk: " << chunkSize << "\n");
   memcpy(buf, lastRelocEnd, chunkSize);
   LLVM_DEBUG(dbgs() << "  total: " << (buf + chunkSize - orig) << "\n");
 }
 
 // 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;
 
     LLVM_DEBUG(dbgs() << "gen reloc: type=" << relocTypeToString(rel.Type)
if (sym->hasGOTIndex()) {
       if (rel.Addend) {
         writeU8(os, opcode_reloc_const, "CONST");
         writeSleb128(os, rel.Addend, "addend");
         writeU8(os, opcode_reloc_add, "ADD");
       }
     } else {
       const GlobalSymbol* baseSymbol = WasmSym::memoryBase;
       if (rel.Type == R_WASM_TABLE_INDEX_I32 ||
           rel.Type == R_WASM_TABLE_INDEX_I64)
         baseSymbol = WasmSym::tableBase;
       writeU8(os, WASM_OPCODE_GLOBAL_GET, "GLOBAL_GET");
       writeUleb128(os, baseSymbol->getGlobalIndex(), "base");
       writeU8(os, opcode_reloc_const, "CONST");
-      writeSleb128(os, file->calcNewValue(rel), "offset");
+      writeSleb128(os, file->calcNewValue(rel, tombstone), "offset");
       writeU8(os, opcode_reloc_add, "ADD");
     }
 
     // Store that value at the virtual address
     writeU8(os, opcode_reloc_store, "I32_STORE");
     writeUleb128(os, 2, "align");
     writeUleb128(os, 0, "offset");
   }
 }
 
+uint64_t InputSection::getTombstoneForSection(StringRef name) {
+  // When a function is not live we need to update relocations referring to it.
+  // If they occur in DWARF debug symbols, we want to change the pc of the
+  // function to -1 to avoid overlapping with a valid range. However for the
+  // debug_ranges and debug_loc sections that would conflict with the existing
+  // meaning of -1 so we use -2.
+  // Returning 0 means there is no tombstone value for this section, and relocation
+  // will just use the addend.
+  if (!name.startswith(".debug_"))
+    return 0;
+  if (name.equals(".debug_ranges") || name.equals(".debug_loc"))
+    return UINT64_C(-2);
+  return UINT64_C(-1);
+}
+
 } // namespace wasm
 } // namespace lld

lld/wasm/InputFiles.h

 };
 
 // .o file (wasm object file)
 class ObjFile : public InputFile {
 public:
   explicit ObjFile(MemoryBufferRef m, StringRef archiveName)
       : InputFile(ObjectKind, m) {
     this->archiveName = std::string(archiveName);
 
     // If this isn't part of an archive, it's eagerly linked, so mark it live.
     if (archiveName.empty())
       markLive();
   }
   static bool classof(const InputFile *f) { return f->kind() == ObjectKind; }
 
   void parse(bool ignoreComdats = false);
 
   // Returns the underlying wasm file.
   const WasmObjectFile *getWasmObj() const { return wasmObj.get(); }
 
   void dumpInfo() const;
 
   uint32_t calcNewIndex(const WasmRelocation &reloc) const;
-  uint64_t calcNewValue(const WasmRelocation &reloc) const;
+  uint64_t calcNewValue(const WasmRelocation &reloc, uint64_t tombstone) const;
   uint64_t calcNewAddend(const WasmRelocation &reloc) const;
   uint64_t calcExpectedValue(const WasmRelocation &reloc) const;
   Symbol *getSymbol(const WasmRelocation &reloc) const {
     return symbols[reloc.Index];
   };
 
   const WasmSection *codeSection = nullptr;
   const WasmSection *dataSection = nullptr;

lld/wasm/InputFiles.cpp

uint64_t ObjFile::calcExpectedValue(const WasmRelocation &reloc) const {
   case R_WASM_GLOBAL_INDEX_LEB:
   case R_WASM_GLOBAL_INDEX_I32:
   case R_WASM_EVENT_INDEX_LEB: {
     const WasmSymbol &sym = wasmObj->syms()[reloc.Index];
     return sym.Info.ElementIndex;
   }
   default:
     llvm_unreachable("unknown relocation type");
   }
 }
 
 // Translate from the relocation's index into the final linked output value.
-uint64_t ObjFile::calcNewValue(const WasmRelocation &reloc) const {
+uint64_t ObjFile::calcNewValue(const WasmRelocation &reloc, uint64_t tombstone) const {
   const Symbol* sym = nullptr;
   if (reloc.Type != R_WASM_TYPE_INDEX_LEB) {
     sym = symbols[reloc.Index];
 
     // We can end up with relocations against non-live symbols.  For example
-    // in debug sections. We return reloc.Addend because always returning zero
-    // causes the generation of spurious range-list terminators in the
-    // .debug_ranges section.
+    // in debug sections. We return a tombstone value in debug symbol sections
+    // so this will not produce a valid range conflicting with ranges of actual
+    // code. In other sections we return reloc.Addend.
+
     if ((isa<FunctionSymbol>(sym) || isa<DataSymbol>(sym)) && !sym->isLive())
-      return reloc.Addend;
+      return tombstone ? tombstone : reloc.Addend;
   }
 
   switch (reloc.Type) {
   case R_WASM_TABLE_INDEX_I32:
   case R_WASM_TABLE_INDEX_I64:
   case R_WASM_TABLE_INDEX_SLEB:
   case R_WASM_TABLE_INDEX_SLEB64:
   case R_WASM_TABLE_INDEX_REL_SLEB: {