Unfortunately instruction selection is also NP, and so is instruction scheduling, and all three are inter-related. An optimal solution for one tends to be suboptimal for the other two.
Ideally one would feed all three problems into a constraint solver together. Thus far this is considered computationally infeasible, though I don't think that belief would bear up to scrutiny with a supercomputer.
It's certainly computationally infeasible for home users, that's for sure.
Is this really true for cases where there is no choice but to spill registers? How would a graph coloring solver understand to spill outer loop variables instead of inner loop ones? I've never written a "proper" register allocator so I'm curious.
The core idea is that memory for spilling is treated as an additional set of register-like locations, with costs for using.
1 int
2 main(int argc, char *argv[])
3 {
4 int sum = 0;
5 int sum2 = 0;
6
7 if (argc >= 2)
8 for (int i = 0; i < argv[1]; i++)
9 sum += i;
10
11 if (argc >= 3)
12 for (int i = 0; i < argv[2]; i++)
13 sum2 += sum + i;
14
15 return 0;
16 }So, an optimizing compiler would see that pretty much everything is dead code it would assign 0 to the return register and done.
gcc-trunk at -O3 for x64 will vectorize the loops but there's no register pressure, so the register allocator wasn't taxed much.
No niche optimization pass to convert to using Gauss's shortcut - https://physicsdb.com/sum-natural-numbers/
wow. wonder if there's much use for that optimization pattern.
edit: clang discussion https://stackoverflow.com/questions/74417624/how-does-clang-...
A truly good compiler would use the same register for sum and sum2 and for argv[1] and argv[2] if it needs to, (even if they weren’t dead, as in this toy example)
With only one register, the answer probably will be “none or every single one”, depending on the instruction set, though.
For example, how do you index into arrays? Self modifying code as often is done on the 6502? Or do you have stack-relative indirect addressing that allows you to say “add the contents of the address pointed to by the value at stack pointer plus 6 to the register”? Either way, there will be lots of contention for that single register.
Or does this hypothetical architecture have various complex “add contents of addresses foo[register] and bar and store the result in baz[3] instructions? (Which would probably make it a very bad design. Adding a second register would be about the first thing to do (fun fact: the 4004 had 16 registers), but maybe this hypothetical design has RAM that’s as fast as registers?)