4 ms·

I 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

• userbinator 9y ago
  As 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 ago
    I 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 ago
    Program 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.