Re:Popcount CPU instruction
by saagarjha on Sunday September 08, 2019 @11:33PM
(#20915014)
A lot of things. Even somewhat complicated arithmetic will become a constant if possible. Certain formulas are hardcoded (e.g. the constant-time sum of the first n positive integers). It’ll perform inlining and tail call recursion elimination. Certain loops can be vectorized automatically. And a lot of library functions are “intrinsics” that the compiler knows a lot about: if you implement you own it might replace it with the standard one, or it may specialize your call to the standard library function to suit your specific use (e.g. a 16-byte memcpy for local variables might just be a load into the XMM registers). Godbolt is a really great resource to see what the compiler will and will not do for you.
[ Parent
| on HN ]
Re:Popcount CPU instruction
by userbinator on Sunday September 08, 2019 @11:56PM
(#20915108)
Even somewhat complicated arithmetic will become a constant if possible.
That's one of the simplest optimisations to implement even in a toy compiler, can be done at the asme time as parsing, and comes practically "for free" --- if all operands of an operator are constant, perform the operation and replace the operator and its operands with the constant result; and repeat this recursively.
Everything else is done based on pattern-matching the AST and performing the appropriate transformations.
Hm, last time I wrote a constant elimination I did so in the optimizer pass over the AST (as part of a lecture, we built a custom C frontend for LLVM and added some optimization passes). What you describe replaces e.g. "x = 3 + 4;", but you get that for free once your optimizer is able to replace more complicated things (e.g. "a = 3; b = 4; x = a + b;").
Also, your parser becomes more complicated; when writing a toy compiler, I think having a clean parser is worth a lot.
But of course it can be done ;-)