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

111–120 of 193 posts

Re: You can't fool the optimizer

#111

Post by msarnoff »

I was very surprised that GCC could optimize NEON SIMD intrinsics. After spending hours trying to optimize my vector code, trying to get the spacing between register dependencies right to reduce stalls, breaking long reduction operations into intermediate results, messing with LLVM-MCA, etc., I realized that I just couldn’t beat the compiler. It was doing its best to allocate registers and reorder instructions to keep the pipeline filled.

I don’t think it always did the best job and saw a bunch of register spills I thought were unnecessary, but I couldn’t justify the time and effort to do it in assembly…

Re: You can't fool the optimizer

#112

Post by Karliss »

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 single symbols for comments, there is no hope for everything else.

ARM isn't the only architecture where GAS uses similar syntax as developers of corresponding CPU arch. They are not doing the same for X86 due to historical choices inherited from Unix software ecosystem and thus AT&T. If you play around on Godbolt with compilers for different architectures it seems like x86 and use AT&T syntax is the exception, there are a few other which use similar syntax but it's a minority.

Why not use same syntax for all architectures? I don't really know all the historical reasoning but I have a few guesses and each arch probably has it's own historic baggage. Being consistent with manufacturer docs and rest of ecosystem has the obvious benefits for the ones who need to read it. Assembly is architecture specific by definition so being consistent across different architectures has little value. GAS is consistent with GCC output. Did GCC added support for some architectures early with the with help of manufacturers assembler and only later in GAS? A lot of custom syntax quirks which don't easily fit into Intel/AT&T model and are related to various addressing modes used by different architectures. For example ARM has register postincrement/preincrement and the 0 cost shifts, arm doesn't have the subregister acess like x86 (RAX/EAX/AX/AH/AL) and non word access is more or less limited to load/store instructions unlike x86 where it can show up in more places. You would need to invent quite a few extensions for AT&T syntax for it to be used by all the non x86 architectures, or you could just use the syntax made by developer of architecture.

Re: You can't fool the optimizer

#113

Post by dzaima »

gfaster wrote: post #102
thaumasiotes wrote: post #52

Earlier quoted context omitted.

Since I had to think about it: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; /* every position where addition will generate a carry */ b = x ^ y; /* the addition, with no carries */ x = a It's easy to show that this algorithm is correct in the sense that, when b is returned, it must be equal to x + y . x + y summing to a constant is a loop invariant, and at termination x is 0 and y is b . It's…

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`?)

Re: You can't fool the optimizer

#114

Post by NooneAtAll3 »

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)

good ol' short circuiting

Re: You can't fool the optimizer

#115

Post by WalterBright »

There are general optimizations, based on DFA (Data Flow Analysis). These recognize things like loops, loop invariants, dead code, copy propagation, constant propagation, common subexpressions, etc.

Then, there are is a (very long) list of checks for specific patterns and replacing them with shorter sequences of code, things like recognizing the pattern of bswap and replacing it with a bswap instruction. There's no end to adding patterns to check for.

Re: You can't fool the optimizer

#116

Post by pianom4n »

WalterBright wrote: post #110
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…

`s` may be null, and so the strlen may seg fault.

But that's undefined behavior, so the compiler is free to ignore that possibility.

Re: You can't fool the optimizer

#117

Post by flqn »

WalterBright wrote: post #110
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…

`s` may be null, and so the strlen may seg fault.

Since the optimiser is allowed to assume you're not invoking UB, and strlen of null is UB, I don't believe that it would consider that case when optimising this function.

Re: You can't fool the optimizer

#118

Post by SkiFire13 »

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…

> 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 negative.

Nit: some might think the reason this doesn't work is because the shift would "move" the sign bit, but actually arithmetic shifting instructions exist for this exact purpose. The reason they are not enough is because shifting provides the wrong kind of division rounding for negative numbers. This can however be fixed up by adding 1 if the number is negative (this can be done with an additional logical shift for moving the sign bit to the rightmost position and an addition).

Re: You can't fool the optimizer

#119

Post by LoganDark »

commandlinefan wrote: post #81
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…

> won't work if num is negative I remember reading (although I can't find it now) a great analysis of all the optimizations that Javascript compilers _can't_ do because of the existence of the "eval" instruction.

Could this perhaps be it? https://janvitek.org/pubs/ecoop11.pdf

Re: You can't fool the optimizer

#120

Post by pbsd »

CodeArtisan wrote: post #88

Recursive Popcount: unsigned int popcount(unsigned int n) { return (n &= n - 1u) ? (1u + popcount(n)) : 0u; } Clang 21.1 x64: popcount: mov eax, -1 .LBB0_1: lea ecx, [rdi - 1] inc eax and ecx, edi mov edi, ecx jne .LBB0_1 ret GCC 15.2: popcount: blsr edi, edi popcnt eax, edi ret Both compiled with -O3 -march=znver5

Because the function is not quite correct. It should be

    return n ? (1u  + popcount(n & n - 1u)) : 0u;
which both Clang and GCC promptly optimize to a single popcnt.
Post reply on HN