After reading your blog article, I have some questions. In , it says:
"It was an important design goal to make the algorithm as flexible as possible,
and to avoid introducing arbitrary constraints. It is possible to change machine
code and live ranges at any time. Simply evict the relevant live ranges, make
the change, and put them back on the queue."
The "machine code" mentioned above means LLVM MI (MachineInstr) or?
In , Evan illustrates current LLVM MI flow below.
1. DAG to MI lowering (and pre-RA schedule)
2. MI optimizations (LICM, CSE, etc.)
3. Register allocation super pass
3a. De-ssa (2-address, phi slim)
3c. Actual register allocation
4. Post-RA optimizations
6. Post-RA scheduling
Does "change machine code and live ranges at any time" means we want to change
the machine code at some points in the above flow? If so, could you point it out?
If you can give me a small example, that would be great!
In the section "Lessons learned from linear scan", you say "advanced register
allocation algorithms often need to build expensive data structures, or they make
assumptions about live ranges being invariant".
Does that imply the graph coloring algorithm? If an algorithm A requires the
live ranges being invariant, does it mean when we assign a register to a variable
then it's done and cannot be changed latter on?