7 ms·
Missed optimizations in C compilers
- haberman 9y agoI haven't worked on ARM much, but I am surprised how often I find sub-optimal code like coming from production compilers. Here's one that I found several years ago in GCC/x86-64. Took a few years to fix: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=44194 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=44194
- userbinator 9y agoAs someone who has read a ton of compiler output over the years (mostly x86, and actually more embedded stuff like 8051 and PIC than ARM), I'm not surprised. Useless/extra moves, both between registers and to/from memory, are the most common "pessimisation" I've seen. I believe it comes from the way compilers are traditionally designed --- as an extremely stupid code generation pass followed by multiple optimisation passes, which naturally will fail to remove 100% of the "stupidity". In other words, they're making a mess and trying to clean it up instead of avoiding a mess in the first place. We could follow the latter idea, and create "naturally smarter/optimising" compilers --- ones which analyse the data and control flow of the source, and generate the minimum instructions necessary to implement it. This entails working "backwards", starting from the results/outputs and moving towards the inputs. I believe the whole category of useless data movement can be solved with such an algorithm, since it's "goal-seeking". To use your bug as an example of how this could work: The compiler would first determine that func() may be called, and then realise that it finishes with calling bar(). It's a tail call, so we may jump instead of call and ret. (GCC was smart enough to figure that one out.) The two arguments come from a return of foo(), and that is (unfortunately) fixed by the calling convention to be rax/rdx. The inputs to bar() must be in rsi and rdi, so two moves are necessary. (If the input locations were the same as the output, then it wouldn't generate any moves.) We thus arrive at these 4 instructions --- and not one of them is unnecessary: call foo mov rsi, rdx mov rdi, rax jmp bar I'm not a huge compiler academic so I don't know if anyone has tried (and failed?) at making a compiler behave like this before. SSA sounds similar, but doesn't have that crucial "work backwards from the solution" idea.
- a_e_k 9y agoI think the problem with that idea is that there's no guarantee that the input to the compiler is going to be ideal. It might be that the programmer write something in a suboptimal or naive way (possibly expecting the compiler to take care of it) or the source was mechanically generated or expanded via a preprocessor. Working strictly backwards from the source seems like it wouldn't be enough. So a production optimizing compiler is going to need all those cleanup passes one way or another. Why not assume they're there and lean on them rather than duplicating that work?
- chrisseaton 9y agoProgram dependency graphs 'work backwards' in that you have a node that performs a computation, and then you have a graph of edges backwards to information and effects in other nodes it needs in order to run. The 'first node' in a program dependency graph is the result that you want to achieve. This doesn't really solve the problem that you are describing though. I think that's more to-do with the register allocator - there's where the moves come from. Something interesting to note is that I think register to register moves are extremely cheap, because the processor is renaming all registers anyway. I think except for taking up instruction cache and a little work for decode and dispatch, these moves don't actually consume any execution slots so they're not a problem. We are also finding in practice that simpler register allocation algorithms, such as linear scan, don't really seem much worse in practice very complicated algorithms that try to eliminate these moves. So that's more evidence that maybe they're not the problem you think they are. When you read assembly it's frustrating to see redundant moves, but I'm not sure they actually cause as much slowdown as you think. I'm not an expert in architecture though.
- dbaupp 9y ago> I believe it comes from the way compilers are traditionally designed --- as an extremely stupid code generation pass followed by multiple optimisation passes, which naturally will fail to remove 100% of the "stupidity". In other words, they're making a mess and trying to clean it up instead of avoiding a mess in the first place. I think that this is, at best, a misleading view of how most modern compilers work. > We could follow the latter idea, and create "naturally smarter/optimising" compilers --- ones which analyse the data and control flow of the source, and generate the minimum instructions necessary to implement it. Many modern compilers (e.g. pretty much all that are based on LLVM) do this: the only subtlety is that analysing data/control flow on the program's AST isn't the best approach, as it doesn't compose, and is designed to be a representation of the human's view of the program, not one good for computers' understanding. So, first, the compiler converts the code into some form of intermediate representation (typically SSA or similar) and then all the control flow is "obvious" and the analysis is easy. Some compilers just use LLVM IR for this purpose, but most will layer on top another (or multiple, like Haskell's GHC) IR that contains more semantic information relevant to the language being compiled. This IR can then be transformed into estimated-to-run-faster versions of the IR (that hopefully have the same behaviour), until finally instructions are chosen, registers allocated and machine code emitted. It is also easier to use an IR rather than AST to do optimisations like inlining, which is an absolutely critical optimisation for performance (it enables a whole pile of other optimisations to be more effective), something that purely minimising the instruction count of a function won't ever do. In fact, this brings me to another important point: minimising instruction count within individual functions can result in slow code, as it shouldn't unroll nor vectorise loops, and should aggressively outline common code sections (even if they're 'hot'). Pure instruction count doesn't mean that much on modern computers; sure, it correlates (negatively) with performance, but weakly. As a sibling points out, it doesn't seem to make sense to put a pile of effort into getting a "perfect" AST-to-IR converted, which would just be duplicating (in a worse framework for them) a lot of the optimisation and analysis passes that are desirable for IR (due inlining opening up new optimisation opportunities there), meaning one would have two constant-propagators, two common-subexpression-eliminators, etc, rather than just leaning on, and beefing up, a single one.
- pkaye 9y agoAmong other things, I seen lots of inefficiencies with bitfields. I tend to use them a lot in hardware register access and packing of data in embedded development. Imagine a bitfield that fits into one word and setting each of the bitfields to a constant. A good compiler should be able to set all the values with one load operations. Some compilers would break this into many separate loads. I think the ARM compilers were worse at this while Clang would optimize it much better. Many times had to forgo bitfields and use macro definitions and masking to get the best code generation at the cost of readability.
- lomnakkus 9y ago> A good compiler should be able to set all the values with one load operations. Hm? I believe that might actually be entirely wrong for many pieces of actual hardware that I've worked with. Setting a single bit may change the interpretation of a subsequently set bit, so you can't really "batch" the updates. (I'm happy for you if this isn't an issue you've faced. We did. Feel sorry for us.)
- morio 9y agoThat's what the keyword volatile is for. If something is not marked volatile the compiler is allowed to change the order and collapse any memory accesses it deems unnecessary.
- lomnakkus 9y agoIndeed, but I don't think that was the poster I was responding to was talking about? I mean, he/she was talking about bitfields and similar things and how writes to those could be coalesced? In genreal, they cannot. (I dunno, it seemed appropriate to mention the caveats.)
- carlmr 9y agoNot coalescing writes on non-volatile bitfields probably isn't guaranteed by the standard. If you depend on it I hope you have a test catching that.
- nanolith 9y agoThese results don't surprise me. A lot of these suboptimal examples come down to the complexity of the optimization problem. Compilers tend to use heuristics to come up with "generally good enough" solutions in the optimizers instead of using a longer and computationally more expensive foray into the solution space. Register allocation is a prime example. This is an NP-Hard problem. Plenty of heuristics exist for finding "generally good enough" solutions, but without exhausting the search space, it typically isn't possible to select the most optimal solution, or even to determine whether a given solution is optimal. Couple this with the tight execution times demanded for compilers, and issues like these become pretty common. Even missed strength reduction opportunities, such as eliminating unneeded spills or initialization, can come down to poor heuristics. It's possible to write better optimizer code, but this can come at the cost of execution time for the compiler. Hence, faster is often chosen over better. In first-tier platforms like ix86 and x86_64, enough examples and eyes have tweaked many of the heuristics so that "generally good enough" covers a pretty wide area. As someone who writes plenty of firmware, I can tell you that it's still pretty common to have to hand-optimize machine code in tight areas in order to get the best trade-off between size, speed, and specific timing requirements. A good firmware engineer knows when to trust the compiler and when not to. Some of this comes down to profiling, and some comes down to constraints and experience. Then, there are areas in which compilers typically rarely produce better code than humans. Crypto is one example. Crypto code written in languages like C can break in subtle ways, from opening timing oracles and other side-channel attacks to sometimes getting the wrong result when assumptions made by the developer and the optimizer are at odds. In these cases, hand-written assembler -- even in first tier platforms -- tends to be both faster and safer, if the developer knows what he/she is doing.
- userbinator 9y agoRegister allocation is a prime example. This is an NP-Hard problem. Plenty of heuristics exist for finding "generally good enough" solutions, but without exhausting the search space, it typically isn't possible to select the most optimal solution, or even to determine whether a given solution is optimal. That's true only if you're not using SSA-based dataflow analysis (an idea so amazingly simple and powerful that I've often wondered why it didn't become popular sooner); otherwise, the interference graph is chordal and optimal register allocation essentially becomes a very simple linear-time algorithm. http://compilers.cs.uni-saarland.de/projects/ssara/ http://compilers.cs.uni-saarland.de/projects/ssara/ http://www.cs.ucla.edu/~palsberg/paper/aplas05.pdf http://www.cs.ucla.edu/~palsberg/paper/aplas05.pdf
- chaboud 9y agoWhile there may be some compiler misses, I started doubting the whole thing when I hit: "Missed simplification of multiplication by integer-valued floating-point constant Variant of the above code with the constant changed slightly: int N; int fn5(int p1, int p2) { int a = p2; if (N) a = 10.0; return a; } GCC converts a to double and back as above, but the result must be the same as simply multiplying by the integer 10. Clang realizes this and generates an integer multiply, removing all floating-point operations." A double or float literal multiply followed by an integer conversion is nowhere near the same as an integer literal multiply. If the coder wanted = 10 (or even = 10.0f), that was available. If = 10.0 was written, it should generally be compiled that way unless --superfast-wreck-floating-point was turned on...
- chengsun 9y agoThis optimisation is actually fully correct if int is 32-bits wide. This is because doubles have a 52-bit mantissa, which means that they can exactly represent all integers up to 2^53 in magnitude. However you are right that the optimisation would not be valid, had int been 64-bits in width.
- AstralStorm 9y agoIt is still valid after constant lifting or if the range of the long int in question vs can be proven to be representable in 53 bits or less. (E.g. using the polyhedral loop optimizer gcc has.)
- chaboud 9y agoRight, though some side effects (e.g. Status registers) might be affected. (One reason strict modes blow floating point optimization, generally.)
- chaboud 9y agoSince it's a *=, I'd expect the operation to occur in double, quantize accordingly, and handle overflow as double-to-int would, rather than int multiplication would. For 10.0 specifically, double is more than large enough to, as far as I know, result in the same output. For arbitrary double literals, I wouldn't expect this to be the case. Note: overflow cast from double to int is undefined, last I looked, so one could argue that the numerical regions for which quantization would occur are outside of the practical range of this chunk of code.
- Animats 9y agochar fn1(float p1) { return (char) p1; } That's undefined behavior. Don't complain about performance.
- comex 9y agoHow is that undefined behavior? The C spec says: (6.3.1.4) > When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined. char is an integer type and float is a real floating type, so the function should be well-defined for at least some input values, although the exact range (including whether or not it includes negatives, i.e. whether plain ‘char’ is signed) is implementation-defined.
- flamedoge 9y agoPedantic me thinks p1 = NaN
- majewsky 9y agoThat would be undefined as per the last sentence in the quote above, "If the value of the integral part cannot be represented by the integer type, the behavior is undefined." Same goes if p1 = 256.0 and your char type can store 0..255 only, although it would probably be easier to make educated guesses about the result in this case.
- pascal_cuoq 9y agoI would advise against making educated guesses about the result of overflow in the conversion from floating-point to integer: http://blog.frama-c.com/index.php?post/2013/10/09/Overflow-float-integer http://blog.frama-c.com/index.php?post/2013/10/09/Overflow-f... Note: the optimization “Missed simplification of multiplication by integer-valued floating-point constant”, that the article points out that Clang does, relies on this kind of overflow to be undefined and causes yet more unpredictable results in some contexts. If you expect the “a *= 10.0;” statement to be translated to a float-to-int conversion instruction, you may expect the behavior of that instruction to apply on overflow, but it won't because the instruction won't have been generated at all.
- clarry 9y agoGCC can't optimize out the mask (which is required to avoid UB if n may be equal or greater than 64): #include <stdint.h> uint64_t rol(uint64_t n, uint64_t val) { n &= 63; return (val << n) | (val >> 64-n); } Compiles to rol(unsigned long, unsigned long): mov rcx, rdi mov rax, rsi and ecx, 63 rol rax, cl ret Clang and ICC do get it right.
- waterhouse 9y agoInteresting... My AMD64 Programmer's Manual says, about "Rotate Left": "The processor masks the upper three bits of the count operand, thus restricting the count to a number between 0 and 31. When the destination is 64 bits wide, it masks the upper two bits of the count, providing a count in the range of 0 to 63." Are there x86 platforms that don't do that? (I don't know if there's a more official document than the AMD64 manual. Technically Intel's stuff is made to be compatible with a standard that AMD first created.) If not, yeah, that's a nice, clear case of a missed optimization.
- userbinator 9y agoIntel's official reference says the count is masked too, with an interesting note that the 8086 (and presumably '186) doesn't.
- dom0 9y agoWith a fixed n, GCC does get it right as well (kinda has to, because that's the only portable way to do fixed rotations in C). I'd sort it under range analysis.
- jzwinck 9y agoMost of the top questions I've asked on Stack Overflow are related to missed optimizations in C (or C++, but I'll skip those here): - https://stackoverflow.com/questions/45052282/why-is-memcmpa-b-4-only-sometimes-optimized-to-a-uint32-comparison https://stackoverflow.com/questions/45052282/why-is-memcmpa-... - https://stackoverflow.com/questions/23055704/why-cant-gcc-optimize-the-logical-bitwise-and-pair-in-x-x-4242-to-x https://stackoverflow.com/questions/23055704/why-cant-gcc-op... - https://stackoverflow.com/questions/26052640/why-does-gcc-implement-isnan-more-efficiently-for-c-cmath-than-c-math-h https://stackoverflow.com/questions/26052640/why-does-gcc-im... - https://stackoverflow.com/questions/18951520/gcc-optimization-missed-opportunity https://stackoverflow.com/questions/18951520/gcc-optimizatio... But my favorite is this one: - https://stackoverflow.com/questions/26053934/is-it-feasible-for-gcc-to-optimize-isnanx-isnany-into-isunorderedx-y https://stackoverflow.com/questions/26053934/is-it-feasible-... That one is now optimized in GCC and Clang: (isnan(x) || isnan(y)) becomes a single instruction on x86. Some of these are very tricky, but the isnan pairing one is simple, and quite useful for some math routines whose first order of business is finding NaNs.