Distributed ThinLTO final linking order

I am trying out distributed ThinLTO for project with prebuilt native libraries and bitcode libraries. So far the steps I am taking

  1. compile sources into bitcode object files:
clang++ -flto=thin -O3 -c -o file1.o file1.cpp
clang++ -flto=thin -O3 -c -o file2.o file2.cpp
  1. thin link both bitcode and prebuilt native object files:
clang++ -flto=thin -O3 -Wl,-plugin-opt,thinlto-index-only=thinlto.objects -Wl,-plugin-opt,thinlto-emit-imports-files -Wl,--start-lib file1.o file2.o -Wl,--end-lib -Wl,--start-lib native1.o -Wl,--end-lib -o index
  1. compile bitcode libs listed in thinlto.objects into native libs and record the same order as the index file shows:
native_objs=""
while IFS=read -r bc_object
do
	native_object="${bc_object%.*}".opt.o
	clang++ -O3 -c -x ir ${bc_object} -o ${native_object} -fthinlto-index=${bc_object}.thinlto.bc
	native_objs+="${native_object} "
done < thinlto.objects
  1. final linking:
clang++ -fuse-ld=lld -Wl,-plugin-opt,-function-sections -Wl,--gc-sections ${native_objs} native1.o -o final.bin

My question is in the final linking, how to decide the order between prebuilt native libraries and bitcode compiled native libraries. The index file thinlto.objects only records order for bitcode object files.

I found an old post from the mailing list:
https://lists.llvm.org/pipermail/llvm-dev/2019-January/128955.html
Maybe it can help you.

Thanks. I looked at it before posting here. Also another related post: [llvm-dev] Running distributed thinLTO without thin archives.. If all the sources are bitcode, I can just use the order given in the index file (“thinlto.objects” in above example). But it is still unclear how to feed the list of both prebuilt native libraries and “bitcode-compiled” native libraries to the linker in an order such that we get consistent result as non-distributed (in-memory) ThinLTO. I feel the order would matter to how linker chooses symbols/definitions and odr resolution.

tl;dr If --thinlto-index-only=a.out-lto-final.params, let -Wl,@.../a.out-lto-final.params occur before all other ELF object files.

Say we have a0.indexing.o a1.indexing.o elf.o b.indexing.o (*.indexing.o are -fthin-link-bitcode produced bitcode files).

cc_binary( name = "a.out", deps = [ ":a", ":elf", ":b", ])
cc_library( name = "a", srcs = ["a0.cc", "a1.cc"], alwayslink = 1 )
cc_library( name = "elf", srcs = ["elf.cc"], features = ["-thin_lto"], alwayslink = 1 )
cc_library( name = "b", srcs = ["b.cc"], alwayslink = 1 )

Bazel runs the ThinLTO indexing action with an option like -Wl,-plugin-opt,thinlto-index-only=.../a.out-lto-final.params
a.out-lto-final.params contains selected object files (–start-lib member extraction) in symbol resolution order:

a0.o  # path mangled by thinlto-prefix-replace/thinlto-object-suffix-replace
a1.o
b.o

The order is important to ensure that dynamic initializations in these modules happen in order: a0, a1, b.

Bazel and our internal build system do the final ELF link with something like

clang -o ...a.out -Wl,@.../a.out-lto-final.params elf0.o elf1.o ...

(I think it’s thinltoParamFile in bazel/CppLinkActionBuilder.java at master · bazelbuild/bazel · GitHub )

I.e. The ThinLTO compiled object files all precede specified ELF object files.
Therefore there is some order shuffle and changes the dynamic initialization order.
This should be OK if your build doesn’t have static initialization order fiasco (or not exposed with such a limited order shuffling).

Duplicate definition

If a bitcode file and an ELF object file both define a symbol (this is ok if after COMDAT selection at least one is weak), symbol resolution for the ThinLTO indexing action decides which one is prevailing.
We don’t need to worry about the order shuffle.

If the ELF object file defines the symbol, ThinLTO consider this an external definition.
If the bitcode file defines the symbol, ThinLTO knows that the symbol is used by regular object files and needs to retain it after dead stripping.

Symbol resolutions in ThinLTO indexing/final link differ

Placing all bitcode files before ELF object files has an issue in pathological case. Teresa mentioned the case which I’ve seen just once (among so many use cases internally).
The following diagrams describe that a ThinLTO indexing action and a final link may have different symbol resolution results.

ThinLTO indexing action

--start-lib
alert_state.o         non-prevailing
--end-lib

--start-lib
wipeout_status_key.o  prevailing
--end-lib

--start-lib
type.indexing.o       define a symbol referenced by alert_state.o
--end-lib

--start-lib
dnsproto.indexing.o   cause wipeout_status_key.o to be extracted
--end-lib

--start-lib
escaping.indexing.o   cause type.indexing.o to be extracted
--end-lib

Both alert_state.o and wipeout_status_key.o define a symbol. The --thinlto-index-only symbol resolution picks wipeout_status_key.o and discards alert_state.o.
The written api-server-lto-final.params lists the 3 bitcode files but the backend compile for type.o does not retain the definition referenced by alert_state.o.

Final link

# In api-server-lto-final.params
type.o
dnsproto.o            cause alert_state.o to be extracted
escaping.o

--start-lib
alert_state.o         prevailing (bad)
--end-lib

--start-lib
wipeout_status_key.o  non-prevailing (bad)
--end-lib

In the final link, dnsproto.o is reordered before all native object files. alert_state.o instead of wipeout_status_key.o is extracted.
alert_state.o references a symbol discarded by the backend compile for type.o, leading to an “undefined symbol” error.

The main issue is the different archive member extraction results.
One idea is to let --thinlto-index-only= specify ELF object files as well.
This requires adapation in Bazel. The implementation may have some complexity due to supporting archives containing ELF object files.
(Archives containing bitcode files is currently not supported.)

I created ⚙ D130229 [ELF] Add --thinlto-index= and --remapping-file= to add --thinlto-index= and --remapping-file= to help preserve ordering.