[WebAssembly] Use DenseMapInfo traits from LLVM repo. NFC

[sbc100]

I'll defer to @ruiu but seems good to me.

wasm/Writer.cpp

123

Interesting. Is this the preferred way to do this? Seems better I guess.

@ruiu, you know more about the llvm ADT stuff than me. Is this how it should have been from the beginning?

[ncw]

wasm/Writer.cpp

123

In fact - why are we needing to do this in LLD at all? Surely the == operators and DenseMap traits for these fundamental types should be in the LLVM repo (at the end of BinaryFormat/Wasm.h) rather than here in LLD?

There's another mostly-but-not-quite-identical copy of this code in WasmObjectWriter (WasmFunctionTypeDenseMapInfo). So moving it into Wasm.h would make sense to me.

Are core headers like BinaryFormat/Wasm.h "supposed" to define container-specific headers like DenseMap traits and equality operators, for the structures they define?

[ruiu]

Yeah, I agree with Nicholas. Moving this piece of code to llvm makes sense to me.

[sbc100]

I'm not sure about putting this stuff in the BinaryFormat. To me it makes sense to keep those headers as mostly structures and enums. If its just a matter of having this in two places I don't think that a huge deal (although the one in llvm is missing a recent fix which argues against my point :)

[ncw]

In D44150#1029149, @sbc100 wrote:

I'm not sure about putting this stuff in the BinaryFormat. To me it makes sense to keep those headers as mostly structures and enums. If its just a matter of having this in two places I don't think that a huge deal (although the one in llvm is missing a recent fix which argues against my point :)

Bikeshed time! Feel free to suggest any header you like, I'm not picky... Would it be allowed to give Wasm another header like BinaryFormat/Wasm{Util/Ops/MapTraits/...}.h? The DenseMap traits are a bit specific and maybe could earn a header of their own, but personally I feel utilities like operator== should really go alongside their structs, since they're so useful to have around.

[llvm-commits]

• msg-8842-58.txt162 BDownload

[sbc100]

Having two copies seems fine for now.

wasm/WriterUtils.h

19–20

Do these need to be moved into the namespace? if so can you drop the extra llvm:: prefixes?

40

Should we just inline this and drop the operators overloads for signatures? Or are they used elsewhere? (In which case the comment neeeds updating I guess).

[ncw]

Thanks for the reviews - I've actually been deluged with "real" work and won't have any time at all to respond and land things today. Sorry for filing a batch of patches and then ignoring them...

Patches I have coming up - in my queue and just need to submit them:

• Fiddling with COMDAT handling, to avoid the need to do a hashmap lookup per symbol
• Improve MarkLive to allow pruning imports as well as defined functions
• Output demangled names in the "name" section for linked output (Dan Gohman indicated that was the intended design, and it makes good sense actually)
• Add support for thread-local variables

After that, all the patches I accumulated over Feb will be caught up!

Things I intend to look into after that:

• Save some space by avoiding writing out zeros for BSS segments
• ICF support (fold identical constant data sections together)

[ncw]

Updated: just for neatness, I think I may as well move them to LLVM, now we've started a discussion of it.

The structures themselves and DenseMapInfo come from there, and LLD shouldn't need to be defining much stuff in the llvm namespace.

Also addressed Sam's comments (oops, non-member operator== should go in the same namespace as their struct, you're right). What is the fix that's missing for the other DenseMap traits implementation? In WasmObjectWriter it has a slightly different way of handling the empty/tombstone values, is that what you mean?

[ruiu]

• ICF support (fold identical constant data sections together)

For ICF, I'd recommend you make an improvement to the compiler and the wasm object file format first. The current implementation of lld's ICF is in some sense too aggressive -- it merges functions when they are identical. But that's actually a violation of the C/C++ spec because if you take addresses of two different functions, they must be distinct. If your program depends on pointer uniqueness, lld's ICF break your program.

On the other hand, lld is conservative on merging data. Comparing two pointers for data is more common in programs, so we don't merge two read-only data by ICF even if their contents are identical. So there's a missed opportunity here.

What we really should do is to make an improvement to the compiler so that it emits the information as to whether an address is significant or not for each chunk, and use that information in the linker. In this way, we can optimize linker output for size the most.

[sbc100]

In D44150#1037839, @ruiu wrote:

• ICF support (fold identical constant data sections together)

For ICF, I'd recommend you make an improvement to the compiler and the wasm object file format first. The current implementation of lld's ICF is in some sense too aggressive -- it merges functions when they are identical. But that's actually a violation of the C/C++ spec because if you take addresses of two different functions, they must be distinct. If your program depends on pointer uniqueness, lld's ICF break your program.

On the other hand, lld is conservative on merging data. Comparing two pointers for data is more common in programs, so we don't merge two read-only data by ICF even if their contents are identical. So there's a missed opportunity here.

What we really should do is to make an improvement to the compiler so that it emits the information as to whether an address is significant or not for each chunk, and use that information in the linker. In this way, we can optimize linker output for size the most.

Would including llvm's nnamed_addr/local_unnamed_addr attribute in the symbol info be right direction for this?

[ncw]

In D44150#1037839, @ruiu wrote:

• ICF support (fold identical constant data sections together)

For ICF, I'd recommend you make an improvement to the compiler and the wasm object file format first. The current implementation of lld's ICF is in some sense too aggressive -- it merges functions when they are identical. But that's actually a violation of the C/C++ spec because if you take addresses of two different functions, they must be distinct. If your program depends on pointer uniqueness, lld's ICF break your program.

On the other hand, lld is conservative on merging data. Comparing two pointers for data is more common in programs, so we don't merge two read-only data by ICF even if their contents are identical. So there's a missed opportunity here.

What we really should do is to make an improvement to the compiler so that it emits the information as to whether an address is significant or not for each chunk, and use that information in the linker. In this way, we can optimize linker output for size the most.

Cool! Good points.

Interestingly, for Wasm we can merge functions without violating pointer uniqueness. That's because we can create two different pointers for the exact same function! Function pointers are indexes into the "table", and the table in turn is populated with real function addresses. Currently we give each function one and only one pointer (so two aliases to the same function get the same pointer, as required), but if we merge two functions (via some "OutputFunction" object) then we'd still de-duplicate the table entries based on the InputFunctions, allowing one OutputFunction to have two pointers, and address-taken relocations would get the right value for the symbol.

I'll think about data too, that's a good point about needing to look at the relocations to work out whether the data is mergable.

wasm/Writer.cpp

 #include "SymbolTable.h"
 #include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
 #include "lld/Common/Threads.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/BinaryFormat/Wasm.h"
+#include "llvm/Object/WasmTraits.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/LEB128.h"
 
 #include <cstdarg>
 #include <map>
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;
 using namespace lld;
 using namespace lld::wasm;
 
 static constexpr int kStackAlignment = 16;
 static constexpr int kInitialTableOffset = 1;
 
 namespace {
 
-// Traits for using WasmSignature in a DenseMap.
-struct WasmSignatureDenseMapInfo {
-  static WasmSignature getEmptyKey() {
-    WasmSignature Sig;
-    Sig.ReturnType = 1;
-    return Sig;
-  }
-  static WasmSignature getTombstoneKey() {
-    WasmSignature Sig;
-    Sig.ReturnType = 2;
-    return Sig;
-  }
-  static unsigned getHashValue(const WasmSignature &Sig) {
-    unsigned H = hash_value(Sig.ReturnType);
-    for (int32_t Param : Sig.ParamTypes)
-      H = hash_combine(H, Param);
-    return H;
-  }
-  static bool isEqual(const WasmSignature &LHS, const WasmSignature &RHS) {
-    return LHS == RHS;
-  }
-};
-
 // An init entry to be written to either the synthetic init func or the
 // linking metadata.
 struct WasmInitEntry {
   const FunctionSymbol *Sym;
   uint32_t Priority;
 };
 
 // The writer writes a SymbolTable result to a file.
private:
   void writeHeader();
   void writeSections();
 
   uint64_t FileSize = 0;
   uint32_t NumMemoryPages = 0;
   uint32_t MaxMemoryPages = 0;
 
   std::vector<const WasmSignature *> Types;
-  DenseMap<WasmSignature, int32_t, WasmSignatureDenseMapInfo> TypeIndices;
+  DenseMap<WasmSignature, int32_t> TypeIndices;
   std::vector<const Symbol *> ImportedSymbols;
   unsigned NumImportedFunctions = 0;
   unsigned NumImportedGlobals = 0;
   std::vector<Symbol *> ExportedSymbols;
   std::vector<const DefinedData *> DefinedFakeGlobals;
   std::vector<InputGlobal *> InputGlobals;
   std::vector<InputFunction *> InputFunctions;
   std::vector<const FunctionSymbol *> IndirectFunctions;

wasm/WriterUtils.h

 #define LLD_WASM_WRITERUTILS_H
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Support/raw_ostream.h"
 
 using llvm::raw_ostream;
 
-// Needed for WasmSignatureDenseMapInfo
-inline bool operator==(const llvm::wasm::WasmSignature &LHS,
-                       const llvm::wasm::WasmSignature &RHS) {
-  return LHS.ReturnType == RHS.ReturnType && LHS.ParamTypes == RHS.ParamTypes;
-}
-
-inline bool operator!=(const llvm::wasm::WasmSignature &LHS,
-                       const llvm::wasm::WasmSignature &RHS) {
-  return !(LHS == RHS);
-}
-
-// Used for general comparison
-inline bool operator==(const llvm::wasm::WasmGlobalType &LHS,
-                       const llvm::wasm::WasmGlobalType &RHS) {
-  return LHS.Type == RHS.Type && LHS.Mutable == RHS.Mutable;
-}
-
-inline bool operator!=(const llvm::wasm::WasmGlobalType &LHS,
-                       const llvm::wasm::WasmGlobalType &RHS) {
-  return !(LHS == RHS);
-}
-
 namespace lld {
 namespace wasm {
 
 void debugWrite(uint64_t Offset, const Twine &Msg);
 
 void writeUleb128(raw_ostream &OS, uint32_t Number, const Twine &Msg);
 
 void writeSleb128(raw_ostream &OS, int32_t Number, const Twine &Msg);
 
 void writeBytes(raw_ostream &OS, const char *Bytes, size_t count,
                 const Twine &Msg);
 
 void writeStr(raw_ostream &OS, StringRef String, const Twine &Msg);
 
 void writeU8(raw_ostream &OS, uint8_t byte, const Twine &Msg);
 
 void writeU32(raw_ostream &OS, uint32_t Number, const Twine &Msg);
 
 void writeValueType(raw_ostream &OS, uint8_t Type, const Twine &Msg);
 
 void writeSig(raw_ostream &OS, const llvm::wasm::WasmSignature &Sig);
 
 void writeInitExpr(raw_ostream &OS, const llvm::wasm::WasmInitExpr &InitExpr);
 
 void writeLimits(raw_ostream &OS, const llvm::wasm::WasmLimits &Limits);
 
 void writeGlobalType(raw_ostream &OS, const llvm::wasm::WasmGlobalType &Type);
 
 void writeGlobal(raw_ostream &OS, const llvm::wasm::WasmGlobal &Global);
 
 void writeImport(raw_ostream &OS, const llvm::wasm::WasmImport &Import);
 
 void writeExport(raw_ostream &OS, const llvm::wasm::WasmExport &Export);
 
 } // namespace wasm
 
-std::string toString(const llvm::wasm::ValType Type);
+std::string toString(llvm::wasm::ValType Type);
 std::string toString(const llvm::wasm::WasmSignature &Sig);
 std::string toString(const llvm::wasm::WasmGlobalType &Sig);
 
 } // namespace lld
 
 #endif // LLD_WASM_WRITERUTILS_H