Hacker News Reader

(I work on GPU compilers in LLVM.)

I'd say that the fact that compilers are designed with a "stupid" IR-generation pass (e.g. the C++ AST to LLVM IR pass in clang) is part of a broader design strategy, namely, designing compilers to have many simple components that work together to do a complex thing.

There are always trade-offs, as you point out, but one of the reasons that it's beneficial to design compilers this way stems from the fact that we generally apply a very high quality bar to compilers, because bugs in the compiler are expensive.

Having simple components with strict interfaces allows us to reason precisely about what each of our transformations is supposed to do. That makes it easier to write unit tests and to do code reviews, and ultimately, in my experience, helps us put correctness first.

I also don't think that this approach of dumb components necessarily leads to worse code. Indeed, for each of the LLVM missed optimizations in the list, I have a pretty good idea of which pass ought to be responsible for fixing the issue. And because the thing that each of these passes does is simple, I can have some confidence that my change won't break other passes.

To add onto that, my understanding is that just "knowing" which sequence of passes is required to perform desired transformation is isomorphic to the halting problem. We might do better if we were more intelligent about our pass managers, but last I checked, LLVM uses simple ones.

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.

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?

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