search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
29.35k stars 12.14k forks source link

llvm::MachO::InterfaceFile::symbols is non-deterministic #97127

Open MaskRay opened 5 months ago

MaskRay commented 5 months ago

https://github.com/llvm/llvm-project/blob/0991bd7887a313d4d6bb66ca44d11939ad71b660/llvm/include/llvm/TextAPI/InterfaceFile.h#L447 std::unique_ptr<SymbolSet> SymbolsSet; is implemented as a using SymbolsMapType = llvm::DenseMap<SymbolsMapKey, Symbol *>;, which has a non-deterministic iteration order in LLVM_ENABLE_ABI_BREAKING_CHECKS=on builds (hash_combine(hash_value(Key.Kind), hash_value(Key.Name)) uses a non-deterministic seed #96282).

This hade made lld/test/MachO/dead-strip.s flaky until I fixed by it with ceeea9193726ff3ceeee48e0e121ac25ac12cef0. The fix is imperfect, since it's better for llvm/include/llvm/TextAPI/InterfaceFile.h to provide a stable iteration order.

llvmbot commented 5 months ago

@llvm/issue-subscribers-lld-macho

Author: Fangrui Song (MaskRay)

https://github.com/llvm/llvm-project/blob/0991bd7887a313d4d6bb66ca44d11939ad71b660/llvm/include/llvm/TextAPI/InterfaceFile.h#L447 `std::unique_ptr<SymbolSet> SymbolsSet;` is implemented as a `using SymbolsMapType = llvm::DenseMap<SymbolsMapKey, Symbol *>;`, which has a non-deterministic iteration order in `LLVM_ENABLE_ABI_BREAKING_CHECKS=on` builds (`hash_combine(hash_value(Key.Kind), hash_value(Key.Name))` uses a non-deterministic seed #96282). This hade made `lld/test/MachO/dead-strip.s` flaky until I fixed by it with ceeea9193726ff3ceeee48e0e121ac25ac12cef0. The fix is imperfect, since it's better for `llvm/include/llvm/TextAPI/InterfaceFile.h` to provide a stable iteration order.
MaskRay commented 5 months ago

@cyndyishida @int3

tgymnich commented 4 months ago

here is a draft addressing the issue using std::map https://github.com/llvm/llvm-project/pull/97615

cyndyishida commented 4 months ago

For most operations it's not necessary, so I'd prefer to keep the DenseMap container to keep TAPI & Apple's linker's usage of tbd files fast. I'd be happy to provide an API in InterfaceFile that provides an ordered view of the symbols though, so it doesn't need to be handled on the client side. WDYT?