Improve fregs-graph.

I'm creating this as a way to keep track of shortcomings of the current implementation.

Some of these are directly taken from TODOS, other are my own opinions.

Things that could be looked at.

Compress spill slots.

Currently we assign each vreg a fixed spill slot. This is terrible for cache performance.

It's possible to end up with sequences like this:

block_ca01_info:
_ca01:
	movq 16(%rbp),%r14
	movq 24(%rbp),%rax
	movq %rax,144(%rsp)
	movq 32(%rbp),%rsi
	movq 40(%rbp),%rdi
	movq 64(%rbp),%rbx
	movq 56(%rbp),%rax
	movq %rax,208(%rsp)
	movq 48(%rbp),%rax
	movq %rax,168(%rsp)
	movq 8(%rbp),%rax
	movq %rax,216(%rsp)
	addq $8,%rbp

Which splits spill slots over multiple cache lines increasing cache pressure.

Things possibly worth trying:

• Assign spill slots in the order they appear - hopefully reducing the average spread within code blocks.
• Dynamically assign vregs to spill slots.

For the later if we have large independent subgraphs we will sometimes get away with using far fewer slots. The reason simply being that non overlapping vregs can share spill slots.

Doing this in an efficient manner however isn't easy.

We sometimes load + spill vregs when we could use memory addressing.

One example I've seen a few times in nofib is this:

	movq 208(%rsp),%rax
	incq %rax
	movq %rax,208(%rsp)

Which we should replace with a single inc operating on memory.

Lift the stack size limit.

There is already a patch in flight.

Revisit spill costs.

Currently the allocator always spills the longest live range. Which often works but is certainly not a great metric.

Ideas:

Consider loop membership.

At least for x86/64 this would be easy to achieve on basic block granularity using the CFG that is also used for block layout.

Revisit chaitins cost model.

There have been major changes to cpus (amd64 becoming the norm) and the backend so at a minimum this cost model should be reevaluated.

Try splitting long live ranges instead of simply spilling the complete live range.

After all long live ranges were the original reason to switch to a life range only based cost heuristic.

Use a different spill algorithm altogether.

Maybe Chows live range splitting based approach would be an option. See "The priority based coloring approach to register allocation" for details.

Trac metadata

Trac field	Value
Version	8.6.3
Type	Task
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler (CodeGen)
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture