4 ms·

I wonder if compilers do multiple passes on the intermediate code in order to optimize / simplify it. For example, during each pass the optimizer searches some

by senfiaj 11mo ago

I wonder if compilers do multiple passes on the intermediate code in order to optimize / simplify it. For example, during each pass the optimizer searches some known harcoded patterns and replaces them with something else and repeats until no possible improvement is found. Also optimizers have a limit, they can't reason as abstractly as humans, for example: bool is_divisible_by_6(int x) { return x % 2 == 0 && x % 3 == 0; } bool is_divisible_by_6_optimal(int x) { return x % 6 == 0; } I tried with both gcc and clang, the asm code for is_divisible_by_6 is still less optimal. So no, there are plenty of easy ways to fool the optimizer by obfuscation. The morale is that you still have to optimize algorithms (O notation) and math operations / expressions.

jakobnissen 11mo ago
They do, and the order of the passes matter. Sometimes, optimizations are missed because they require a certain order of passes that is different from the one your compiler uses. On higher optimization levels, many passes occur multiple times. However, as far as I know, compilers don't repeatedly run passes until they've reached an optimum. Instead, they run a fixed series of passes. I don't know why, maybe someone can chime in.
- titzer 11mo ago
  It's a long-standing problem in compilers, often referred to as the "phase ordering problem". In general, forward dataflow optimizations can be combined if they are monotonic (meaning, never make the code worse, or at least, never undo a previous step. It's possible to run forward dataflow problems together repeatedly to a fixpoint. In TurboFan a general graph reduction algorithm is [1] instantiated with a number of reducers, and then a fixpoint is run. The technique of trying to combine multiple passes has been tried a number of times. What doesn't seem so obvious is how to run optimizations that are not traditional forward dataflow problems or are indeed backward dataflow problems (like DCE) together with other transformations. Generally compilers get tuned by running them on lots of different kinds of code, often benchmarks, and then tinkering with the order of passes and other heuristics like loop unroll factors, thresholds for inlining, etc, and seeing what works best. [1]was? TurboFan seems to have splintered into a number of pieces being reused in different ways these days
windward 11mo ago
Those aren't isomorphic. The C spec says `is_divisible_by_6` short-circuits. You don't want the compiler optimising away null checks. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf 6.5.13, semantics
- senfiaj 11mo ago
  So you claim that the compiler "knows about this but doesn't optimize because of some safety measures"? As far as I remember, compilers don't optimize math expressions / brackets, probably because the order of operations might affect the precision of ints/floats, also because of complexity. But my example is trivial (x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int), yet the compiler produced different outputs (the outputs are different and most likely is_divisible_by_6 is slower). Also what null (you mean 0?) checks are you talking about? The denominator is not null/0. Regardless, my point about not over relying on compiler optimization (especially for macro algorithms (O notation) and math expressions) remains valid.
  - 1718627440 11mo ago
    > the order of operations might affect the precision of ints/floats That's only the problem of floats, with ints this issue doesn't exist. Why do you write (x % 2 == 0 && x % 3 == 0) instead of (x % 2 == 0 & x % 3 == 0), when the latter is what you think you mean? Are you sure, that dividing by 6 is actually faster, than dividing by 2 and 3? A division operation is quite costly compared to other arithmetic and 2 and 3 are likely to have some special optimization (2 is a bitshift), which isn't necessary the case for 6.
    - senfiaj 10mo ago
      > That's only the problem of floats, with ints this issue doesn't exist. With ints the results can be dramatically different (often even worse than floats) even though in pure mathematics the order doesn't matter: 1 * 2 * 3 * 4 / 8 --> 3 3 * 4 / 8 * 1 * 2 --> 2 This is a trivial example, but it shows why it's extremely hard for compilers to optimize expressions and why they usually leave this task to humans. But x % 2 == 0 && x % 3 == 0 isn't such case, swapping operands of && has no side effects, nor swapping operands of each ==. > Are you sure, that dividing by 6 is actually faster Compilers usually transform divisions into multiplications when the denominator is a constant. I wrote another example in other comment but I'll write again. I also tried this bool is_divisible_by_15(int x) { return x % 3 == 0 && x % 5 == 0; } bool is_divisible_by_15_optimal(int x) { return x % 15 == 0; } is_divisible_by_15 still has a branch, while is_divisible_by_15_optimal does not is_divisible_by_15(int): imul eax, edi, -1431655765 add eax, 715827882 cmp eax, 1431655764 jbe .LBB0_2 xor eax, eax ret .LBB0_2: imul eax, edi, -858993459 add eax, 429496729 cmp eax, 858993459 setb al ret is_divisible_by_15_optimal(int): imul eax, edi, -286331153 add eax, 143165576 cmp eax, 286331153 setb al ret My point is that the compiler still doesn't notice that 2 functions are equivalent. Even when choosing 3 and 5 (to eliminate the questionable bit check trick for 2) the 1st function appears less optimal (more code + branch).
ramon156 11mo ago
I don't know enough about ASM. Are u saying the first one is more optimal because it is faster or because it uses less instructions? Would this reflect a real world use case? Do any other compilers (e.g. V8) optimize modulo's into something else?
- senfiaj 11mo ago
  The compiler didn't recognize that x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int values. In theory a compiler could detect that and generate identical code for both functions, but it isn't done because this case is "niche" despite being trivial. My point is not to over rely on optimizer for math expressions and algorithms.
inkyoto 11mo ago
> So no, there are plenty of easy ways to fool the optimizer by obfuscation. If you mean fooling the compiler by the source code obfuscation, it won't – by the time the first optimisation pass arrives, the source had already been transformed into an abstract syntax tree and the source code obfuscation becomes irrelevant. Multiple optimiser passes do take place, but they are bounded in time – it is not an accepted expectation that the optimiser will spend a – theoretically – indefinite amount of time trying to arrive at the most perfect instruction sequence. There was a GNU project a long time ago, «superoptimiser», which, given a sequence of instructions, would spend a very long time trying to optimise it into oblivion. The project was more of an academic exercise, and it has been long abandoned since.

by senfiaj 11mo ago

jakobnissen 11mo ago

They do, and the order of the passes matter. Sometimes, optimizations are missed because they require a certain order of passes that is different from the one your compiler uses. On higher optimization levels, many passes occur multiple times. However, as far as I know, compilers don't repeatedly run passes until they've reached an optimum. Instead, they run a fixed series of passes. I don't know why, maybe someone can chime in.

titzer 11mo ago
It's a long-standing problem in compilers, often referred to as the "phase ordering problem". In general, forward dataflow optimizations can be combined if they are monotonic (meaning, never make the code worse, or at least, never undo a previous step. It's possible to run forward dataflow problems together repeatedly to a fixpoint. In TurboFan a general graph reduction algorithm is [1] instantiated with a number of reducers, and then a fixpoint is run. The technique of trying to combine multiple passes has been tried a number of times. What doesn't seem so obvious is how to run optimizations that are not traditional forward dataflow problems or are indeed backward dataflow problems (like DCE) together with other transformations. Generally compilers get tuned by running them on lots of different kinds of code, often benchmarks, and then tinkering with the order of passes and other heuristics like loop unroll factors, thresholds for inlining, etc, and seeing what works best. [1]was? TurboFan seems to have splintered into a number of pieces being reused in different ways these days

windward 11mo ago

Those aren't isomorphic. The C spec says `is_divisible_by_6` short-circuits. You don't want the compiler optimising away null checks. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf 6.5.13, semantics

senfiaj 11mo ago
So you claim that the compiler "knows about this but doesn't optimize because of some safety measures"? As far as I remember, compilers don't optimize math expressions / brackets, probably because the order of operations might affect the precision of ints/floats, also because of complexity. But my example is trivial (x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int), yet the compiler produced different outputs (the outputs are different and most likely is_divisible_by_6 is slower). Also what null (you mean 0?) checks are you talking about? The denominator is not null/0. Regardless, my point about not over relying on compiler optimization (especially for macro algorithms (O notation) and math expressions) remains valid.
- 1718627440 11mo ago
  > the order of operations might affect the precision of ints/floats That's only the problem of floats, with ints this issue doesn't exist. Why do you write (x % 2 == 0 && x % 3 == 0) instead of (x % 2 == 0 & x % 3 == 0), when the latter is what you think you mean? Are you sure, that dividing by 6 is actually faster, than dividing by 2 and 3? A division operation is quite costly compared to other arithmetic and 2 and 3 are likely to have some special optimization (2 is a bitshift), which isn't necessary the case for 6.
  - senfiaj 10mo ago
    > That's only the problem of floats, with ints this issue doesn't exist. With ints the results can be dramatically different (often even worse than floats) even though in pure mathematics the order doesn't matter: 1 * 2 * 3 * 4 / 8 --> 3 3 * 4 / 8 * 1 * 2 --> 2 This is a trivial example, but it shows why it's extremely hard for compilers to optimize expressions and why they usually leave this task to humans. But x % 2 == 0 && x % 3 == 0 isn't such case, swapping operands of && has no side effects, nor swapping operands of each ==. > Are you sure, that dividing by 6 is actually faster Compilers usually transform divisions into multiplications when the denominator is a constant. I wrote another example in other comment but I'll write again. I also tried this bool is_divisible_by_15(int x) { return x % 3 == 0 && x % 5 == 0; } bool is_divisible_by_15_optimal(int x) { return x % 15 == 0; } is_divisible_by_15 still has a branch, while is_divisible_by_15_optimal does not is_divisible_by_15(int): imul eax, edi, -1431655765 add eax, 715827882 cmp eax, 1431655764 jbe .LBB0_2 xor eax, eax ret .LBB0_2: imul eax, edi, -858993459 add eax, 429496729 cmp eax, 858993459 setb al ret is_divisible_by_15_optimal(int): imul eax, edi, -286331153 add eax, 143165576 cmp eax, 286331153 setb al ret My point is that the compiler still doesn't notice that 2 functions are equivalent. Even when choosing 3 and 5 (to eliminate the questionable bit check trick for 2) the 1st function appears less optimal (more code + branch).

ramon156 11mo ago

I don't know enough about ASM. Are u saying the first one is more optimal because it is faster or because it uses less instructions? Would this reflect a real world use case? Do any other compilers (e.g. V8) optimize modulo's into something else?

senfiaj 11mo ago
The compiler didn't recognize that x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int values. In theory a compiler could detect that and generate identical code for both functions, but it isn't done because this case is "niche" despite being trivial. My point is not to over rely on optimizer for math expressions and algorithms.

inkyoto 11mo ago

> So no, there are plenty of easy ways to fool the optimizer by obfuscation. If you mean fooling the compiler by the source code obfuscation, it won't – by the time the first optimisation pass arrives, the source had already been transformed into an abstract syntax tree and the source code obfuscation becomes irrelevant. Multiple optimiser passes do take place, but they are bounded in time – it is not an accepted expectation that the optimiser will spend a – theoretically – indefinite amount of time trying to arrive at the most perfect instruction sequence. There was a GNU project a long time ago, «superoptimiser», which, given a sequence of instructions, would spend a very long time trying to optimise it into oblivion. The project was more of an academic exercise, and it has been long abandoned since.