How do modern compilers choose which variables to put in registers?

Unfortunately, just like with parser generators and more powerful parsing algorithms (in particular bottom-up LR and such), the practice proved very different than the theory. Linear-scan and variants of it have become the norm for register allocation.

Compilers are of course on of the purest applications of theoretical computer science.

> Stack Overflow

This is on 'Programming Language Design and Implementation Stack Exchange'[0] -- I'm not pointing this out to tell you that you're wrong -- I think the various 'Stacks Exchange' often have better, more thoughtful answers than the average Stack Overflow question.

[0] really rolls off the tongue

Oh, it's from Alexis King. No wonder it's written so well.

I didn't even check the author before reading this comment. She is a great writer and super talented.

I always enjoy your explanations of how you've implemented features in D

Would you have references?

Cache usage won't be known statically at compile-time. If you retrieve one item from a database, it will result in a different usage of the cache than if you retrieved a different item.

I$ pressure from bloating machine code with such high-volume information. Though c.f. prefetch and clflush instructions, as well as the concept (s) of non-tenporal and write-combining stores.

First, you can manage the cache explicitly. You can load from memory bypassing the cache (if you know you won't need something again), you can prefetch into the cache ahead of time, and you can expunge lines from the cache. Those instructions are useful in high performance code (and in Spectre-like exploits :) ).

Second, it's harder than it looks. Even a simpler problem, branch speculation, is notoriously difficult to get right without profiling information from program execution. For example the Linux kernel has the likely() and unlikely() macros which can inject branch predictor hints into the assembly. You use them like "if(likely(...))". Problem? Those hints, carefully inserted by serious systems engineers, were often terrible! So much so that removing all of them increased the performance of the kernel.

I think that you pretty much have to provide profiling information to think about having the compiler manage the cache. It's doable, but it's a lot of work - your profiles better be highly representative.

Register allocation is a form of value analysis, while managing caches like you suggest is a form of pointer analysis which is 100 times harder. One huge problem is aliasing. It is in general very difficult to tell whether X[i] and Y[j] are distinct memory locations. So the compiler has to err on the side of caution and assume that X[i] overwrites Y[j] and vice versa. The C99 "restrict" keyword and modern improvements in language semantics help (like forbidding pointer arithmetic), but doesn't completely eliminate aliasing. You also have pointer indirection, e.g., X[Y[Z[j]]], making the analysis even harder.

In other words, state-of-the-art compilers can beat 99.9% of all developers on register allocation, but they can't beat a developer who manages cache memory explicitly.

Aren't registers fixed by x86_64, while cache is a CPU hardware specific thing (e.g.: newer cpus have more cache than older ones, bit register count is fixed 8 on x86 and 16 on x86_64)?

So I think the compiler can work with registers at compile time but cant work with an unknown structure of cache

Cache was designed to be program-transparent so hardware makers could add it and get better benchmarks without recompiling. Since then, it's stayed that way because it's easier for the hardware maker to change and improve it without having to change the ISA

GameBoy Advance had a CPU without cache, but with 32kbit of fast RAM on the chip. That was pretty close to a fully manual cache, and turned out to be a complete waste in practice.

It was impractical to share/reuse it like a real cache, because that would require writing some sort of memory allocator or a hash table — in software. Managing that was a hassle, and an overhead in itself. Only a few games (mostly 3D) took advantage of it, and simply by copying their hottest loop in there.

In addition to the other good answers, if the amount of state that's explicitly managed by software gets too large then it gets really expensive to save or restore that state. This happens, for example, when a syscall transfers control to the operating system. If the (many-MB) cache were software-managed, the OS would need to decide between flushing it all to main memory (expensive for quick syscalls) or leaving it in place and having OS code and data be uncached. Function calls between libraries have similar problems, how is a called function supposed to know which cache space is available for it to use? If you call the same function multiple times who's responsible for keeping its working data cached? For a 32MB L3 cache, flushing the entire cache to memory (as would be required when switching between processes) could take over a millisecond, let alone trying to manage caches shared by multiple cores.

> You might say "optimizers will do a better job", and you're right

That's probably why nothing good has been created to fill that space yet (that I know of). Any serious project is just going to opt for compiler optimizations.

I second this.

It's nice to wish for the optimizer to do the [almost] perfect job, but sometimes that never arrives. Consider for example the case of AMD GPU ISA (GCN) generated by LLVM: it's been so far from optimal for so long, that one can lose hope that'll ever happen; and wish for a simple solution that works in the meantime.

Sounds like Forth to me.

I think you want a macro assembler.

You may think that’s too close to the hardware, but if you want “actual control over things like register allocation”, you will be writing your code for a specific register set size, types of (vector) registers, etc, so you’ll soon be targeting a specific CPU.

Also, was C ever “portable assembly”? There may have been a brief period where that was true, but it started as a language where programmers could fairly reliably predict what assembly the compiler would generated but that wasn’t portable, and once it had become portable, users wanted optimizations, so predicting what code it would generate was a lot harder.

Jasmin is something like this. It is essentially a high-level assembler, will handle register allocation (but not spills) for you, has some basic control flow primitives that map 1-to-1 to assembly instructions. There is also an optional formal verification component to prove some function is equivalent to its reference , is side-channel free, etc.

[1] https://github.com/jasmin-lang/jasmin/wiki

Yeah, but x86 is perverse like that :^D

> attempting to separate them, like what most if not all compilers do, results in (sometimes very) suboptimal results

Not separating them would have a big disadvantage: all register allocation decisions need to be strictly local, because information about upcoming instructions and their register constraints is not available. Even simple graph coloring algorithms give much better code than algorithms with local decisions only.

In our baseline/unoptimized compiler, we do ISel+RegAlloc(+Encoding) combined in a single step and we get lots of easily avoidable moves and spills. (These typically don't hurt performance that much on modern out-of-order CPUs with store forwarding, but substantially increase the code size.)

You're not wrong - in that ALL optimizations are inter-dependent. But, for reasons that I think are rather obvious, it's really hard to do them optimally, all at once. So typically you'd do things like "register-pressure-aware" selection & scheduling, repeated optimization steps (like, do a register-pressure-aware first scheduling, RA, then schedule again) etc. It's all just heuristics, in the end.

> since it can only make the latter easier.

Not necessarily. For a simple case, yes; but in general, committing to early to reuse a virtual register may have very bad performance implications, since it limits code mobility, freedom to select a particular register, and may increase register pressure in critical sections of the code (say you have "A conflicts with B, B with C and C with D"; you can put all of these in 2 registers: A=R0, B=R1, C=R0, D=R1. But if you committed too early to unify the lifetimes of A and D - eg. for instruction selection purposes - now you need 3 registers. Which is fine, and likely the best solution if you actually end up having 3 registers available - but very likely sub-optimal if you only had 2).

Interestingly clang does not lower down to that (instead it multiplies by 7 in a separate step) while GCC does.

A compiler would probably emit shift-and-add by constants. Which may very well be faster than a lea.

Isn't that one of the "slow lea" cases? https://reviews.llvm.org/D32277 (I can't quite parse whether using EBP/RBP/R13 is necessary to hit the slow case, or if it's any of those bullet points that cause slowness.)

That's not 100% correct but it's correct enough to give sufficient intuition to understand the problem.

It's basically a caching problem. Unloading variables and saving them and loading another one because it is needed for a compuation takes time. So you want to minimize that, just like with a cache.

Now a compiler has an advantage over a pure cache in that it actually gets to read the code and so knows the exact number of variables and when they get used! whereas with a pure cache it has to be an oracle :) so, a compiler can try and optimize the cache placements (register assignments) ahead of time by analyzing the code. That's where these algorithms come into play. So knowing nothing we can safely guess that all compiler algorithms must be beating something simple like an LRU ..

> Perhaps this is layman's understanding, but afaik all CPU operations are only done on registers, so any variable has to be moved to registers when it's operated on

From the CPU point of view, yes, but many instructions set architectures (including the very common x86 family) have instructions in which one of the operands can be either a register or a memory location. When it's a memory location, the CPU will load it into an internal register, do the operation there, and write it back to memory if it's the destination operand; but from the point of view of the compiler, the CPU is operating directly on memory.

> (or are some operations possible on memory without going to registers?)

Some atomic memory operations (like atomic compare and exchange) can be thought of as being done directly on memory (or on the cache which sits above the memory). Some CPUs might even implement it that way (by having an "atomic memory operation" command between the CPU and the cache, instead of doing the operation on the CPU).

It extremely depends on the target CPU. Some CPUs do have instructions that operate on RAM directly, no register required.

However, the tradeoff is that RAM is almost always 2-4 times slower than writing to registers. Most of the time it's more efficient to copy from RAM to a register and back.

Most CPUs are designed to operate on registers, but it's not too uncommon to see simple things like incrementing a variable in RAM without an intermediate copy. There might be more, I don't know a lot about x86

> all CPU operations are only done on registers

Not correct for the X86_64, such as:

    INC EA

https://www.felixcloutier.com/x86/inc