Jeff Law wrote:
Vladimir Makarov wrote:
Jeff Law wrote:
I've been thinking further about instruction alternative selection
prior to allocation and one of the questions in my mind is how this
interacts with IRA.
We select an alternative for each insn based on some "best guess"
heuristic -- the selection of an alternative will often restrict the
register classes available for each of the operands. Presumably
we'd want to encode that information it the conflict graph so that
IRA would allocate registers so as to fit the constraints of the
early insn alternative selection. Right? In the case where the
graph is uncolorable, do we allow IRA to override the alternative
selection, or do we insert copies to simplify the conflict graph or
some mixture of both?
Thoughts?
As for copies, I think it would be a bad decision to stick only to
original (after the code selection) alternative and generate copies
to satisfy this alternative. For example, if pseudo got memory
instead of hard-register required by the alternative, it would be bad
to generate a copy (ld/st in this case) if memory is accepted by the
insn.
That's why I mentioned the possibility of relaxing the conflict graph
to allow other alternatives if we find that the graph is
uncolorable. So if we initially wanted class A, but couldn't get it
and the operand could accept class B, then we remove the conflict
between the pseudo and the hard regs in class B and recolor.
I have no idea how expensive this would be.
This also implies that we're representing conflicts for register
classes & memory in the conflict graph.
The problem is that graph coloring working well on non-intersected
register classes. There were some articles how to make it work on
intersected register classes. The most known is "A Generalized
Algorithm for Graph-Coloring Register Allocation":
http://www.cs.tufts.edu/~nr/pubs/gcra-abstract.html
I read this article with attention several times and even wrote some
notes but unfortunately can not find it. I got an impression that it
will not work.
As for changing register class from one cover class (e.g. GENERAL_REGS)
to another non-intersected one (FLOAT_REGS), it is possible but more
rare than changing register class in one cover class (like from GENERAL
to AREG in x86). The most common example is usage pseudo for moving
memory values (e.g. generated from a[i] = b[i]). It can be done through
int or fp regs. I've tried some graph coloring algorithm modification
to permit register class changing when register pressure for original
class is high and one for new class is low but got mixed results on x86
and ppc (some tests were worse some were better with practically the
same average result).
