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
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:
- can C compilers deduplicate code?
- can C++ compilers automatically eliminate duplicate code?
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
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].