4

Does a compiler look for recurrent expressions to convert it into 'function' to reduce binary size and improve performance?

Of course, the obvious answer might be "some do it, some don't", so I ask for compiler of mainstream language, let's take for example : Java SDK compiler, GCC compiler and Clang.

If "yes, they do it", is it frequent or in very specific case? (A code example where it actually happens might be very instructive)

6
  • 4
    This optimization is known as Common Subexpression Elimination, and is fairly common for off-line compilers.
    – amon
    Sep 22, 2014 at 9:57
  • 1
    @amon If I understand your link, it isn't what I'm asking for, the Common Subexpression Elimination looks like storing a result that is used multiple times, in my case I'm asking if compiler avoid repeating instruction in the binary.
    – anopse
    Sep 22, 2014 at 10:01
  • 2
    They could and they often do, especially when optimizing for space (e.g. the -Os flag of GCC) Sep 22, 2014 at 10:09
  • If you don't mean common subexpression elimination, you might be interested in Threaded Code, which is a technique for extremely space-efficient compilation. It was popular when using the Forth language, but today it's not generally useful outside of embedded programming.
    – amon
    Sep 22, 2014 at 10:15
  • 1
    I remember reading about the visual studio debugger somewhere. It sometimes jumps into the wrong function. The reason is that the linker noticed that 2 functions have identical assembler code (usually getters/setters) even though they are different at c++ level, so the linker uses the exact same implementation for different functions and the debugger cannot tell the original function and just picks one, sometimes the wrong one.
    – nwp
    Sep 22, 2014 at 22:09

2 Answers 2

3

They don‘t do it.

What you are looking for is clone detection and automatic code deduplication. There are many tools to discover duplicate code (some quite advanced, see AST based clone detectors) and a good literature about this topic but usually only two cases of duplication are managed by the compiler:

  • common subexpression elimination
  • code vectorization

Anyway consider that code duplication is bad for readability/maintainability of source code not necessarily for performance of compiled code.

Some related questions are:

EDIT

Some linkers can perform the Identical Code Folding (ICF): at link time, ICF detects functions with identical object code and merges them into a single copy.

But

  • ICF can be unsafe as it can change the run-time behaviour of code that relies on each function having a unique address (C99 guarantees that the addresses of two different functions are not equal; for C++11 it isn't so clear). ICF can be used in a safe mode where it identifies and folds functions whose addresses are guaranteed not to have been used in comparison operations. Further, profiling and debugging binaries with merged functions can be confusing, as the PC values of merged functions cannot be always disambiguated to point to the correct function
  • this is a somewhat "passive" optimization with a limited scope: mainly useful for C++ templates.
2
  • I know that it is very bad for maintainability, but I was just asking anyway because I was wondering if the compiler would do it or not.
    – anopse
    Sep 22, 2014 at 22:02
  • 1
    There is no problem with maintainability. What the compiler or linker does, as long as it is correct, is no problem for maintainability.
    – gnasher729
    Nov 13, 2023 at 11:08
0

The only thing reasonably similar that I have seen regularly: Say you have two places in the same C function with the statement "return x+2;". Normally each would be translated as "take x, add 2, clean up to the stack, return to the caller". But one is often translated to "jump to the other return statement". Or if one says "return 3*x + 2;" it could be translated to "take x, multiply by 3, jump to the other return statement just after it has read x". Or the other way round "take x, jump to the other return statement just after it has multiplied x by 3". This can be done easily by just comparing the code that is generated.

In C++ "return;" often forces the compiler to call destructors, and often the same destructors. So this will be a valid space optimisation even if you have a plain return statement. (And saving space can save time if it means your code is cached. If you have ten return statements each calling the same destructors, and all return statements have an equal amount of usage, you know have a much better chance that the return statement code is cached when you call the function again. And if the same destructor is in only one place instead of ten, the cost of inlining it would be much much lower. So instead of ten calls to the destructor code, you might have one inlined destructor).

Similar things happen if you use an if/else statement, and both branches end with the same code. That could be quite trivial, "if (condition) a[i] = expr1; else a[i] = expr2; ". Normally the if part would jump past the else part when it's done. But here, both branches will like end with code to store some value into a[i]. If that code is identical, the if-branch may not include this code, but jump to the place in the else branch where it stores into a[i].

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.