Well, let me tell you what I have done so far. First, I set it up as a
problem solution framework, which is great for the furthest first
spill heuristic. The problem holds a sequence of registers. I modeled
the sequence as a structure with the values:
struct seq {
unsigned register, next, prev, preferred;
bool live_in, phi_reg, ... everything I could possible want to know.
The caveats come later.
};
The sequence is built as a doubly linked list from the next/prev.
Thus, if a register exists in the sequence, it can point to the next
register in the sequence from the next value. So I have the
vector<seq> and I have some functions getRegister(unsigned index) and
getNext(unsigned index) from the problem. The goal is once I build my
problem, I can then iterate through my problem with a simple for loop
like "for( unsigned i=0,e=problem->size(); i != e; ++i )" and I have
the register value, the next value, etc at my fingertips.
I did not use pointers because the furthest first heuristic is
difficult when it looks around branches. It's great for local
allocation, but when the furthest first hits a conditional branch, it
has at least two paths to look down. A simple recursive search with
cache is useful, but spending time to find a recurrence relation would
be beneficial for performance. Thus, when I look at a different branch
the pointer in that different problem cannot give a time value. So I
use lots of unsigned values as indexes into tables.
Now from this sequence, I can take a pass and build the solution. The
solution checks on every register and adds / spills registers with
it's furthest first heuristic (slightly modified with my own
heuristic).
Ok, so for each machine basic block, I create a problem. From each
problem, I create a solution. The solution happens to be a
pre-coloring algorithm. So each problem starts out with nothing
allocated in the registers. From there, I run the slightly modified
furthest first heuristic until the end of the problem. Unfortunately,
machine basic blocks are not usually large. For instance, how long do
you go without using an 'if' in c++.
This now brings me to my third pass. From here I coalesce between the
problems/solutions which correspond directly to machine basic blocks.
Caveats and Optimizations:
1. Some machine basic blocks jump to only one other block and the
other blocks is only reached from the previous block. So, the problem
eats up both blocks without worrying about the branch.
2. When a virtual register needs to be in a physical register, the
physical register already exists as a precolored register. Precolored
coalesced registers like this can be added to the furthest first
heuristic without loosing performance.
There are quite a few others. I do not fully have an understanding on
copy instructions outside of phi elimination.
I wish I was being paid for this.
Thanks,
Jeff Kunkel