Compiler Engineering in Practice | Hacker News Reader

Compiler Engineering in Practice

chisophugis.github.io

134 pointsdhruv300630 comments

I learned about DFA (Data Flow Analysis) optimizations back in the early 1980s. I eagerly implemented them for my C compiler, and it was released as "Optimum C". Then came the C compiler roundup benchmarks in the programming magazines. I breathlessly opened the issue, and was faced with the reviewers' review that Optimum C was a bad compiler because it deleted the code in the benchmarks. (The reviewer wrote Optimum C was cheating by recognizing the specific benchmark code and deleting it.)

I was really, really angry that the review had not attempted to contact me about this.

But the other compiler venders knew what I'd done, and the competition implemented DFA as well by the next year, and the benchmarks were updated.

The benchmarks were things like:

    void foo() { int i,x = 1; for (i = 0; i < 1000; ++i) x += 1; }

That's a terrible benchmark but the correct thing to do is not to eliminate the code but to issue an error or warning that this is a cpu cycle burning no-op.

Where do you draw the line on this logic? Should we never inline or unroll and only warn? Should we never re-order and only warn? The CPU is doings its own re-ordering and that can't be manually controlled, should we pick instructions to force ordering and warn?

I can understand if we'd want to emit perfectly matching control flow logic with certain debug flags to verify correctness in specific scenarios. But I'd want it to be opt-in.

The more high level code is used, the more purposeless code is there to be eliminated. For example, an RAII object with an empty default destructor.

That would make for a bad experience in the presence of macros or other compile-time configuration.

It's pretty common to have code that only exists in one configuration but not others. In those, you end up with some obviously pointless code that the compiler should silently discard. It would be no fun if you couldn't compile your release build because the compiler yelled at you that the removed `assert()`s turned some of the surrounding code into dead code.

That's hard to implement, because typically, constructs like this will be the result of various previous passes (macro expansion, inlining, dead code elimination,...), typically it's not written by the user directly.

Embedded code where "do nothing" loops are common for timing purposes is often marked with "do not optimise" pragmas specifically because eliminating dead code has become the norm. On the other hand, many codebases have also become dependent on this default trimming behaviour and would be disgustingly bloated with dead code if it weren't for the compiler helping to remove some of it.

  Why compilers are hard – the IR data structure

If you claim an IR makes things harder, just skip it.

  Compilers do have an essential complexity that makes them "hard" [...waffle waffle waffle...]

  The primary data [...waffle...] represents the computation that the compiler needs to preserve all the way to the output program. This data structure is usually called an IR (intermediate representation). The primary way that compilers work is by taking an IR that represents the input program, and applying a series of small transformations all of which have been individually verified to not change the meaning of the program (i.e. not miscompile). In doing so, we decompose one large translation problem into many smaller ones, making it manageable.

There we go. The section header should be updated to:

  Why compilers are manageable – the IR data structure

In the D compiler, I realized that while loops could be rewritten as for loops, and so implemented that. The for loops are then rewritten using goto's. This makes the IR a list of expression trees connected by goto's. This data structure makes Data Flow Analysis fairly simple.

An early function inliner I implemented by inlining the IR. When I wrote the D front end, I attempted to do this in the front end. This turned out to be a significantly more complicated problem, and in the end not worth it.

The difficulty with the IR versions is, for error messages, it is impractical to try and issue error messages in the context of the original parse trees. I.e. it's the ancient "turn the hamburger into a cow" problem.

> Why compilers are manageable – the IR data structure

Yeah, I've been working on an APL interpreter, just for the hell of it as it's a very interesting problem, and without the IR (or continuation graph in this case) I can't even imagine how much harder it would be as you can't really tell what most things are until you evaluate the things around it at runtime -- is it a monadic or dyadic function/operator application, variable lookup, function as an argument, whatever?

The compiler (parser, really) builds this intricate graph which curries computations, dispatches functions and, eventually, evaluates expressions to get to the result. Aside from defined operators, which get looked up in the environment at parse time, the parser just knows that it has the name of something with no real clue what it represents as that changes based on the context.

After the continuation graph is built then it's just graph transformations all the way down, at least in theory, which is what I think TFA was trying to get at because this is where the dragons be. Allegedly, haven't gotten to the optimizer yet but I have some ideas so, we'll see...

For some strange reason I have this fascination with CEK machines so that's what I built and reading the article I was thinking how much easier all this would be (for the robots) if we were dealing with a regular old IR (or a more sane language).

This resonates with how compiler work looks outside textbooks. Most of the hard problems aren’t about inventing new optimizations, but about making existing ones interact safely, predictably, and debuggably. Engineering effort often goes into tooling, invariants, and diagnostics rather than the optimizations themselves.

> A miscompile of an AI program can cause bad medical advice

I think the AI program is plenty capable of causing bad medical advice on its own without being miscompiled.

This is a tangent on language semantics (of the English kind) instead of engaging with the (interesting!) narrative on miscompiles. Feel free to skip.

> A compiler is a translator that translates between two different languages.

I lament the word "compile" subsuming "translate" for most of tech. Computers interpret instructions and do them now, and translate instructions from one code to another that is later interpreted or translated again.

The English word "compile" means "bring together" and compiler systems usually have lots of interpreting and translating and linking to make some kind of artifact file, to wit:

> taking a step back, a compiler is simply a program that reads a file and writes a file

But not necessarily! You don't even need that much! Just source and target codes.

Forth systems (which I enjoy) for example have a single global STATE variable to switch between _execute this word now_ and _compile a call to this word for later_ directly into memory (plus metadata on words that allow them to execute anyway, extending the compiler, but I digress). You could snapshot the memory of the Forth process with its built target program and reload that way, but the usual Forth way is to just store the source and recompile to memory when needed.

Traditional threaded Forths compile calls to a list of routine addresses for a virtual machine interpreter routine (load address then jump to code, not much more work than the processor already does). I prefer subroutine threading, though, where calls are bone fide CALL instructions and the inner interpreter is the processor itself, because it's easier to understand.

Nowadays even the processor translates the instructions you give it to its own microcode for interpreting. It's code all the way down.

(I'm still reading the article.)

> What is a compiler?

Might be worth skipping to the interesting parts that aren’t in textbooks

While the reduction of a compiler to a deterministic function is theoretically sound, modern engineering practice necessitates addressing "Compiler-as-a-Service" architectures (LSP, incrementalism), where persistent state management complicates the purported simplicity of debugging. Furthermore, the article overlooks the non-deterministic nature of JIT compilation and parallel builds, which fundamentally challenges the comparison to stateless CLI utilities like grep.

I don't feel his overflow miscompilation example is a good one. A 64bit multiplication converted back to 32bit has the same overflow behavior as if the computation was in 32bit (assuming nobody depends on the overflow indication, which is rare). And in high level programming languages you typically can't tell the difference.

The only way to understand compilers is to have already written one.

Always interested in compiler testing, so I look forward to what he has to say on that.

skimmed through the article and the structure just hints at being not written by a human

have to disagree. maybe read a paragraph, its dense with context imo. i find slop to be light on context and wordy, this is not.

It seemed odd to me too, but unfortunately, it hints at being written by a human that has either gravitated towards AI-dialect, or contributed to AI training data.

The compiler part of a language is actually a piece of cake compared to designing a concurrent garbage collector.

A good enough one isn't so bad. Here's an example concurrent collector that was used with the Inferno OS:

https://github.com/inferno-os/inferno-os/blob/master/libinte...

There's lots of room to improve it, but it worked well enough to run on telephony equipment in prod.

This has gotta be one of the most dunning-kruger comments on hn

Maybe I should have formulated it the other way around then.

Not really... A true concurrent high-throughput low-latency garbage collector is the stuff of nightmares. Just ask Azul Systems that sells real-time JDK for the high-performance trading applications.

Ladies and gentlemen dunning-kruger contender #2

^ Found a person who hasn't worked on high-througput GCs!

^ Found a person who hasn't worked on high-throughout compilers!

“Compiler Engineering in Practice” is a blog series intended to pass on wisdom that seemingly every seasoned compiler developer knows, but is not systematically written down in any textbook or online resource. Some (but not much) prior experience with compilers is needed.

Reply on news.ycombinator.com