Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You can't fool the optimizer

xania.org

Post reply on HN
Print view View original

121–130 of 193 posts

Re: You can't fool the optimizer

#121

Post by Joker_vD »

Karliss wrote: post #112
Joker_vD wrote: post #34

Wait, why does GAS use Intel syntax for ARM instead of AT&T? Or something that looks very much like it: the destination is the first operand, not the last, and there is no "%" prefix for the register names?

That's not Intel syntax that's more or less ARM assembly syntax as used by ARM documentation. Intel vs AT&T discussion is primarily relevant only for x86 and x86_64 assembly. If you look at GAS manual https://ftp.gnu.org/old-gnu/Manuals/gas-2.9.1/html_chapter/a... almost every other architecture has architecture specific syntax notes, in many cases for something as trivial comments. If they couldn't even decide on si…

> Why not use same syntax for all architectures?

My question is more, why even try to use the same syntax for all architectures? I thought that was what GAS's approach was: that they took AT&T syntax, which historically was unified syntax for several PDPs (and some other ISA, I believe? VAX?) and they made it fit every other ISA they supported. Except apparently no, they didn't, they adopted the vendors' syntaxes for other ISAs but not for Intel's x86? Why? It just boggles my mind.

Re: You can't fool the optimizer

#122

Post by Koffiepoeder »

senfiaj wrote: post #84
abainbridge wrote: post #80

The 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; } Doesn't get optimized to a single shift right, because the that won't work if num is n…

Yeah, this one as well: 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; } Mathematically x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int values but the compiler doesn't see them as identical, and produces less optimal code for is_divisible_by_6 than for is_divisible_by_6_optimal.

Mhm, this is one of these cases I'd prefer a benchmark to be sure. Checking %2 is very performant and actually just a single bit check. I can also imagine some cpu's having a special code path for %3. In practice I would not be surprised that the double operand is actually faster than the %6. I am mobile at this moment, so not able to verify.

Re: You can't fool the optimizer

#123

Post by gldrk »

Joker_vD wrote: post #121
Karliss wrote: post #112

Earlier quoted context omitted.

That's not Intel syntax that's more or less ARM assembly syntax as used by ARM documentation. Intel vs AT&T discussion is primarily relevant only for x86 and x86_64 assembly. If you look at GAS manual https://ftp.gnu.org/old-gnu/Manuals/gas-2.9.1/html_chapter/a... almost every other architecture has architecture specific syntax notes, in many cases for something as trivial comments. If they couldn't even decide on si…

> Why not use same syntax for all architectures? My question is more, why even try to use the same syntax for all architectures? I thought that was what GAS's approach was: that they took AT&T syntax, which historically was unified syntax for several PDPs (and some other ISA, I believe? VAX?) and they made it fit every other ISA they supported. Except apparently no, they didn't, they adopted the vendors' syntaxes for…

I don’t believe GNU invented the AT&T syntax for x86. System V probably targeted x86 before GNU did (Richard Stallman didn’t think highly of microcomputers). They used some kind of proprietary toolchain at the time that gas must have copied.

Re: You can't fool the optimizer

#124

Post by gfaster »

dzaima wrote: post #113
gfaster wrote: post #102

Earlier quoted context omitted.

In C, I'm pretty confident the loop is defined by the standard to terminate. Also I did take the excuse to plug it (the optimized llvm ir) into Alive: https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(f...

Alive2 does not handle loops; don't know what exactly it does by default, but changing the `shl i32 %and, 1` to `shl i32 %and, 2` has it still report the transformation as valid. You can add `--src-unroll=2` for it to check up to two loop iterations, which does catch such an error (and does still report the original as valid), but of course that's quite limited. (maybe the default is like `--src-unroll=1`?)

Oh wow nice catch - I was not at all familiar with the limitations. I would've hoped for a warning there, but I suppose it is a research project.

I was able to get it working with unrolling and narrower integers:

https://alive2.llvm.org/ce/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF...

Re: You can't fool the optimizer

#125

Post by rdc12 »

abainbridge wrote: post #99
ynik wrote: post #97

Earlier quoted context omitted.

`s[0] == 'h'` isn't sufficient to guarantee that `s[3]` can be access without a segfault, so the compiler is not allowed to perform this optimization. If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen: https://godbolt.org/z/KjdT16Kfb (also note you got the endianness wrong in your hand-optimized version)

Ooo, I'd never thought of using & like that. Interesting. > (also note you got the endianness wrong in your hand-optimized version) Doh :-)

Matt Godbolt's talk on ray tracers, shows how effective that change can be. Think it was that talk anyway.

https://www.youtube.com/watch?v=HG6c4Kwbv4I

Re: You can't fool the optimizer

#126

Post by zrm »

ynik wrote: post #97
abainbridge wrote: post #92

Earlier quoted context omitted.

eg 4: int foo(char const *s) { if (s[0] == 'h' && s[1] == 'e' && s[2] == 'l' && s[3] == 'l') return 1; return 0; } The outputs 4 cmp instructions here, even though I'd have thought 1 was sufficient. https://godbolt.org/z/hqMnbrnKe

`s[0] == 'h'` isn't sufficient to guarantee that `s[3]` can be access without a segfault, so the compiler is not allowed to perform this optimization. If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen: https://godbolt.org/z/KjdT16Kfb (also note you got the endianness wrong in your hand-optimized version)

> If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen

But then you're accessing four elements of a string that could have a strlen of less than 3. If the strlen is 1 then the short circuit case saves you because s[1] will be '\0' instead of 'e' and then you don't access elements past the end of the string. The "optimized" version is UB for short strings.

Re: You can't fool the optimizer

#127

Post by Denvercoder9 »

anon-3988 wrote: post #53

What I am curious about is, is the compiler smart enough to be lazy with computation and or variables? For example consider: let a = expr let b = expr2 if (a || b) { return true; } is the compiler allowed to lazily compute this if it is indeed faster to do that way? Or declaring a bunch of variables that may or may not be used in all of the branches. Is the compiler smart enough to only compute them whenever it is ne…

> It did not turn all of this into a SIMD mask or something like that.

Did you try using bitwise and (&), or a local for the struct? The short-circuiting behaviour of the logical means that if `s->a != a`, `s->b` must not be dereferenced, so the compiler cannot turn this into a SIMD mask operation, because it behaves differently.

Generally compilers are pretty smart these days, and I find that more often than not if they miss an "obvious" optimization it's because there's a cornercase where it behaves differently from the code I wrote.

Re: You can't fool the optimizer

#128

Post by Denvercoder9 »

zrm wrote: post #126
ynik wrote: post #97

Earlier quoted context omitted.

`s[0] == 'h'` isn't sufficient to guarantee that `s[3]` can be access without a segfault, so the compiler is not allowed to perform this optimization. If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen: https://godbolt.org/z/KjdT16Kfb (also note you got the endianness wrong in your hand-optimized version)

> If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen But then you're accessing four elements of a string that could have a strlen of less than 3. If the strlen is 1 then the short circuit case saves you because s[1] will be '\0' instead of 'e' and then you don't access elements past the end of the string. The "optimized" version is UB for short strin…

Yes, so that's why the compiler can't and doesn't emit the optimized version if you write the short circuited version - because it behaves differently for short strings.

Re: You can't fool the optimizer

#129

Post by Bratmon »

Koffiepoeder wrote: post #122
senfiaj wrote: post #84

Earlier quoted context omitted.

Yeah, this one as well: 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; } Mathematically x % 2 == 0 && x % 3 == 0 is exactly the same as x % 6 == 0 for all C/C++ int values but the compiler doesn't see them as identical, and produces less optimal code for is_divisible_by_6 than for is_divisible_by_6_optimal.

Mhm, this is one of these cases I'd prefer a benchmark to be sure. Checking %2 is very performant and actually just a single bit check. I can also imagine some cpu's having a special code path for %3. In practice I would not be surprised that the double operand is actually faster than the %6. I am mobile at this moment, so not able to verify.

But if % 2 && % 3 is better, then isn't there still a missed optimization in this example?

Re: You can't fool the optimizer

#130

Post by titzer »

jakobnissen wrote: post #64
senfiaj wrote: post #62

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 =…

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 c…

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

Post reply on HN