I'm wondering how the compiler optimised add_v3() and add_v4() though.
Was it through "idiom detection", i.e. by recognising those specific patterns, or did the compiler deduce the answers them through some more involved analysis?
You can't fool the optimizer
71–80 of 193 posts
Re: You can't fool the optimizer
#72I 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 =…
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
6.5.13, semantics
Re: You can't fool the optimizer
#73I 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 =…
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?
Re: You can't fool the optimizer
#74Obvious caveat: pushing this a bit further it can quickly fallback to the default case. The optimizer is a superpower but you still need to try to write efficient code. unsigned add_v5(unsigned x, unsigned y) { if (x == y) return 2 * x; return x + y; } Results in: add_v5(unsigned int, unsigned int): lsl w8, w0, #1 add w9, w1, w0 cmp w0, w1 csel w0, w8, w9, eq ret (armv8-a clang 21.1.0 with O3) If compiler folks can c…
This sort of pattern can't be found by incremental lowering (and isn't common enough to have more sophisticated analysis written for it) so it ends up in a local maximum. Basically the idea for most compilers is to do a series of transforms which incrementally improve the program (or at least make it worse in understood and reversible ways). To do this transform you need the optimizer to do the (not always trivial) p…
I agree, but GCC manages the optimization, and not all optimizations need to take fewer cycles. The single instruction version is obviously better for -Os and it would probably be a win in general.
Re: You can't fool the optimizer
#75Earlier quoted context omitted.
I’m not a compiler expert, an assembly expert or an ARM expert, so this may be wildly wrong, but this looks optimized to me. The trick is that it’s doing both the add and the left shift in parallel then selecting which to use based on a compare of the two values with csel. (To see this, rather than reading the code sequentially, think of every instruction as being issued at the same time until you hit an instruction…
> this looks optimized to me. It's not. Why would lsl+csel or add+csel or cmp+csel ever be faster than a simple add? Or have higher throughput? Or require less energy? An integer addition is just about the lowest-latency operation you can do on mainstream CPUs, apart from register-renaming operations that never leave the front-end.
ARM is a big target, there could be cpus where lsl is 1 cycle and add is 2+.
Without knowing about specific compiler targets/settings this looks reasonable.
Dumb in the majority case? Absolutely, but smart on the lowest common denominator.
Re: You can't fool the optimizer
#76I'm wondering how the compiler optimised add_v3() and add_v4() though. Was it through "idiom detection", i.e. by recognising those specific patterns, or did the compiler deduce the answers them through some more involved analysis?
add_v3() is the result of induction variable simplification: https://llvm.org/doxygen/IndVarSimplify_8cpp_source.html
Re: You can't fool the optimizer
#77I 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 =…
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 6.5.13, semantics
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.
Re: You can't fool the optimizer
#78I 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 =…
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 6.5.13, semantics
x % 3 == 0 is an expression without side effects (the only cases that trap on a % operator are x % 0 and INT_MIN % -1), and thus the compiler is free to speculate the expression, allowing the comparison to be converted to (x % 2 == 0) & (x % 3 == 0).
Yes, compilers will tend to convert && and || to non-short-circuiting operations when able, so as to avoid control flow.
Re: You can't fool the optimizer
#79I 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 =…
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?
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.
Re: You can't fool the optimizer
#80The examples are fun, but rather than yet another article saying how amazing optimizing compilers are (they are, I already know), I'd probably benefit more from an article explaining when obvious optimizations are missed and what to do about it.
Some boring examples I've just thought of...
eg 1:
int bar(int num) { return num / 2; }
eg 2:
int foo(void) { return strlen("hello"); }
eg 3:
int foo(char const *s) {
if (strlen(s)