4 ms·

With this one I instead wondered: If there are 4 functions doing exactly the same thing, couldn't the compiler also only generate the code for one of them? E.g

With this one I instead wondered: If there are 4 functions doing exactly the same thing, couldn't the compiler also only generate the code for one of them? E.g. if in `main` you called two different add functions, couldn't it optimize one of them away completely? It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? Why doesn't it do that?

cyco130 11mo ago
It would but it's harder to trigger. Here, it's not safe because they're public functions and the standard would require `add_v1 != add_v2` (I think). If you declare them as static, it eliminates the functions and the calls completely: https://aoco.compiler-explorer.com/z/soPqe7eYx https://aoco.compiler-explorer.com/z/soPqe7eYx I'm sure it could also perform definition merging like you suggest but I can't think of a way of triggering it at the moment without also triggering their complete elision.
moefh 11mo ago
> It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? It can't do that because the program might load a dynamic library that depends on the function (it's perfectly OK for a `.so` to depend on a function from the main executable, for example). That's one of the reasons why a very cheap optimization is to always use `static` for functions when you can. You're telling the compiler that the function doesn't need to be visible outside the current compilation unit, so the compiler is free to even inline it completely and never produce an actual callable function, if appropriate.
- bruce343434 11mo ago
  Sadly most C++ projects are organized in a way that hampers static functions. To achieve incremental builds, stuff is split into separate source files that are compiled and optimized separately, and only at the final step linked, which requires symbols of course. I get it though, because carefully structuring your #includes to get a single translation unit is messy, and compile times get too long.
  - cyco130 11mo ago
    That’s where link-time optimization enters the picture. It’s expensive but tolerable for production builds of small projects and feasible for mid-sized ones.
  - gpderetta 11mo ago
    [[gnu::visibility(hidden)]] (or the equivalent for your compiler), might help.
  - 1718627440 10mo ago
    That's one major reason why I don't like C++. I think the concept of header and implementation files is fine, but idiomatic C++ code basically makes it broken. Surely a class should go into the implementation file? (Internal) Types belong into the implementation, what belongs into headers are interfaces and function signatures. A class is a type, so it does not belong into a header file.
- sureglymop 11mo ago
  > It can't do that because the program might load a dynamic library that depends on the function That makes perfect sense, thank you! And I just realized why I was mistaken. I am using fasm with `format ELF64 executable` to create a ELF file. Looking at it with a hex editor, it has no sections or symbol table because it creates a completely stripped binary. Learned something :)
apple1417 11mo ago
The MSVC linker has a feature where it will merge byte-for-byte identical functions. It's most noticeable for default constructors, you might get hundreds of functions which all boil down to "zero the first 32 bytes of this type". A quick google suggests it's called "identical comdat folding" https://devblogs.microsoft.com/oldnewthing/20161024-00/?p=94575 https://devblogs.microsoft.com/oldnewthing/20161024-00/?p=94...
optionalsquid 11mo ago
This is not quite what you asked, I think, but GCC is able to remove duplicate functions and variables after code generation via the -fipa-icf options: > Perform Identical Code Folding for functions (-fipa-icf-functions), read-only variables (-fipa-icf-variables), or both (-fipa-icf). The optimization reduces code size and may disturb unwind stacks by replacing a function by an equivalent one with a different name. The optimization works more effectively with link-time optimization enabled. In addition, the Gold linker supports a similar feature via `--icf={safe,all}`: > Identical Code Folding. '--icf=safe' Folds ctors, dtors and functions whose pointers are definitely not taken
Joker_vD 11mo ago
Nope. Function with external linkage are required to have different addresses. MSVC actually breaks this and this means that you can't reliably compare function pointers on MSVC because some different functions may happen to have same object code by chance: void go_forward(Closure *clo, Closure *cont, Closure *forward) { GC_CHECK(clo, cont, forward); ((Fun0)(forward->fun))(forward, cont); } void go_left(Closure *clo, Closure *cont, Closure *left, Closure *right) { GC_CHECK(clo, cont, left, right); ((Fun0)(left->fun))(left, cont); } void go_right(Closure *clo, Closure *cont, Closure *left, Closure *right) { GC_CHECK(clo, cont, left, right); ((Fun0)(right->fun))(right, cont); } GcInfo gc_info[] = { { .fun = (GenericFun)&go_forward, .envc = 0, .argc = 1 }, { .fun = (GenericFun)&go_left, .envc = 0, .argc = 2 }, { .fun = (GenericFun)&go_right, .envc = 0, .argc = 2 }, }; Since, the pointers to go_forward and go_left will be the same, the gc_info table is less useless that it could be otherwise.
- gpderetta 11mo ago
  But it could generate one then make the remaining three tail call to that one, or lay them out so that they are at 1byte-nop each to the next one and fallthrough the next until the last one implements the logic (This is a bit more compilcated on msvc as I believe the ABI requires a well defined prologue).
  - zozbot234 11mo ago
    They can't be at 1byte-nop distance because pointer addresses as well as branch target addresses are expected to be aligned for performance reasons - often to 16 bytes. You need either a nop sequence or a jump/tailcall.
    - gpderetta 11mo ago
      Sure, there are also probably pointer integrity landing pads. Make it larger nops then.
tialaramex 11mo ago
If your language has monomorphization† (as C++ and Rust do) then it's really common to have this commonality in the emitted code and I believe it is common for compilers to detect and condense the resulting identical machine code. If the foo<T> function for an integer checks if it's equal to four, it well be that on your target hardware that's the same exact machine code whether the integer types T are 1 byte, 2 bytes or 4 bytes and whether they're signed or unsigned, so we should only emit one such implementation of foo, not six for u8, i8, u16, i16, u32 and i32. † Monomorphization takes Parametrically Polymorphic functions, ie functions which are strongly typed but those types are parameters at compile time, and it emits distinct machine code for each needed variation of the function, so e.g. add(a, b) maybe gets compiled to produce add_integer(a, b) and add_float(a, b) and add_matrix(a, b) even though we only wrote one function, and then code which calls add(a, b) with matrices, is at compile time emitted as calling add_matrix(a, b), because the compiler knew it needs that version. In C++ the number of parameters is also potentially allowed to vary between callers so add_matrix(a, b, c, d) might exist too, this feature is not yet available in Rust.
- titzer 11mo ago
  The linker de-duping identical machine code is common, but most frontends that do monomorphization aren't that smart about identical copies, because monomorphization is usually done with source-level types, and there are lots of typeful operations that need to get resolved and lowered before it's known that the machine code will be identical.

cyco130 11mo ago

It would but it's harder to trigger. Here, it's not safe because they're public functions and the standard would require `add_v1 != add_v2` (I think). If you declare them as static, it eliminates the functions and the calls completely: https://aoco.compiler-explorer.com/z/soPqe7eYx https://aoco.compiler-explorer.com/z/soPqe7eYx I'm sure it could also perform definition merging like you suggest but I can't think of a way of triggering it at the moment without also triggering their complete elision.

moefh 11mo ago

> It probably shouldn't do that if you create a dynamic library that needs a symbol table but for an ELF binary it could, no? It can't do that because the program might load a dynamic library that depends on the function (it's perfectly OK for a `.so` to depend on a function from the main executable, for example). That's one of the reasons why a very cheap optimization is to always use `static` for functions when you can. You're telling the compiler that the function doesn't need to be visible outside the current compilation unit, so the compiler is free to even inline it completely and never produce an actual callable function, if appropriate.

bruce343434 11mo ago
Sadly most C++ projects are organized in a way that hampers static functions. To achieve incremental builds, stuff is split into separate source files that are compiled and optimized separately, and only at the final step linked, which requires symbols of course. I get it though, because carefully structuring your #includes to get a single translation unit is messy, and compile times get too long.
- cyco130 11mo ago
  That’s where link-time optimization enters the picture. It’s expensive but tolerable for production builds of small projects and feasible for mid-sized ones.
- gpderetta 11mo ago
  [[gnu::visibility(hidden)]] (or the equivalent for your compiler), might help.
- 1718627440 10mo ago
  That's one major reason why I don't like C++. I think the concept of header and implementation files is fine, but idiomatic C++ code basically makes it broken. Surely a class should go into the implementation file? (Internal) Types belong into the implementation, what belongs into headers are interfaces and function signatures. A class is a type, so it does not belong into a header file.
sureglymop 11mo ago
> It can't do that because the program might load a dynamic library that depends on the function That makes perfect sense, thank you! And I just realized why I was mistaken. I am using fasm with `format ELF64 executable` to create a ELF file. Looking at it with a hex editor, it has no sections or symbol table because it creates a completely stripped binary. Learned something :)

apple1417 11mo ago

The MSVC linker has a feature where it will merge byte-for-byte identical functions. It's most noticeable for default constructors, you might get hundreds of functions which all boil down to "zero the first 32 bytes of this type". A quick google suggests it's called "identical comdat folding" https://devblogs.microsoft.com/oldnewthing/20161024-00/?p=94575 https://devblogs.microsoft.com/oldnewthing/20161024-00/?p=94...

optionalsquid 11mo ago

This is not quite what you asked, I think, but GCC is able to remove duplicate functions and variables after code generation via the -fipa-icf options: > Perform Identical Code Folding for functions (-fipa-icf-functions), read-only variables (-fipa-icf-variables), or both (-fipa-icf). The optimization reduces code size and may disturb unwind stacks by replacing a function by an equivalent one with a different name. The optimization works more effectively with link-time optimization enabled. In addition, the Gold linker supports a similar feature via `--icf={safe,all}`: > Identical Code Folding. '--icf=safe' Folds ctors, dtors and functions whose pointers are definitely not taken

Joker_vD 11mo ago

Nope. Function with external linkage are required to have different addresses. MSVC actually breaks this and this means that you can't reliably compare function pointers on MSVC because some different functions may happen to have same object code by chance: void go_forward(Closure *clo, Closure *cont, Closure *forward) { GC_CHECK(clo, cont, forward); ((Fun0)(forward->fun))(forward, cont); } void go_left(Closure *clo, Closure *cont, Closure *left, Closure *right) { GC_CHECK(clo, cont, left, right); ((Fun0)(left->fun))(left, cont); } void go_right(Closure *clo, Closure *cont, Closure *left, Closure *right) { GC_CHECK(clo, cont, left, right); ((Fun0)(right->fun))(right, cont); } GcInfo gc_info[] = { { .fun = (GenericFun)&go_forward, .envc = 0, .argc = 1 }, { .fun = (GenericFun)&go_left, .envc = 0, .argc = 2 }, { .fun = (GenericFun)&go_right, .envc = 0, .argc = 2 }, }; Since, the pointers to go_forward and go_left will be the same, the gc_info table is less useless that it could be otherwise.

gpderetta 11mo ago
But it could generate one then make the remaining three tail call to that one, or lay them out so that they are at 1byte-nop each to the next one and fallthrough the next until the last one implements the logic (This is a bit more compilcated on msvc as I believe the ABI requires a well defined prologue).
- zozbot234 11mo ago
  They can't be at 1byte-nop distance because pointer addresses as well as branch target addresses are expected to be aligned for performance reasons - often to 16 bytes. You need either a nop sequence or a jump/tailcall.
  - gpderetta 11mo ago
    Sure, there are also probably pointer integrity landing pads. Make it larger nops then.

tialaramex 11mo ago

If your language has monomorphization† (as C++ and Rust do) then it's really common to have this commonality in the emitted code and I believe it is common for compilers to detect and condense the resulting identical machine code. If the foo<T> function for an integer checks if it's equal to four, it well be that on your target hardware that's the same exact machine code whether the integer types T are 1 byte, 2 bytes or 4 bytes and whether they're signed or unsigned, so we should only emit one such implementation of foo, not six for u8, i8, u16, i16, u32 and i32. † Monomorphization takes Parametrically Polymorphic functions, ie functions which are strongly typed but those types are parameters at compile time, and it emits distinct machine code for each needed variation of the function, so e.g. add(a, b) maybe gets compiled to produce add_integer(a, b) and add_float(a, b) and add_matrix(a, b) even though we only wrote one function, and then code which calls add(a, b) with matrices, is at compile time emitted as calling add_matrix(a, b), because the compiler knew it needs that version. In C++ the number of parameters is also potentially allowed to vary between callers so add_matrix(a, b, c, d) might exist too, this feature is not yet available in Rust.

titzer 11mo ago
The linker de-duping identical machine code is common, but most frontends that do monomorphization aren't that smart about identical copies, because monomorphization is usually done with source-level types, and there are lots of typeful operations that need to get resolved and lowered before it's known that the machine code will be identical.