Do compilers use profile information to allocate compilation time (such as by using an extremely expensive but slightly better register allocator for a hot loop)?
I got the impression that expensive register allocation is not an option. A 1% improvement in register allocation that results in a 0.1% local performance improvement and a 0.002% program performance improvement may be considered not to justify 1000x local compile time, but for frequently run stable-ish software the compile time and compiler development/maintenence time might be justified.
(I am not a programmer, but I do like thinking and learning about such things.)
That said if you do the register allocation while the program is still in SSA form, it becomes polynomial (interference graph is a chordal graph).
https://compilers.cs.uni-saarland.de/projects/ssara/
I got the impression that expensive register allocation is not an option. A 1% improvement in register allocation that results in a 0.1% local performance improvement and a 0.002% program performance improvement may be considered not to justify 1000x local compile time, but for frequently run stable-ish software the compile time and compiler development/maintenence time might be justified.
(I am not a programmer, but I do like thinking and learning about such things.)
LLVM 's FastRegAlloc also uses linear scan.