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?
Sticking with one insn alternative (by alternative I mean set of operand
constraints - one constraint for one operand. That is different from
RTL insn alternative which is superset of such set) permits more
accurate (and much faster) cost calculation of register class costs for
pseudos which improves coloring and spilling decisions especially for
CISC architectures likes x86, x86_64. On the other hand it rejects some
more possible alternatives. What is more important? I don't know.
Therefore I wrote about it as an experiment. That is ok because to get
current state IRA algorithms I tried probably 5 times more different
coloring algorithms.
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 is
because a new pseudo will need a hard register and could result in
spilling another pseudo. And this can not be fixed by a simple
subsequent pass removing ld/st by using memory operands. So I think if
the altrernative is not satisfied then we should choose the cheapest one
and use it for the insn. Still some copies might be needed to satisfy
the new alternative. After changing some insn alternatives and
generating copies, choosing alternative for them and generating new
pseudos we modify register class costs of the pseudos and calculate
costs for the new pseudos (it should be a fast process because we need
to change costs only for pseudos involved in insns with changed
alternatives and because again each insn has only one alternative).
After cost recalculation, another round of coloring is done.
That is in brief how I see it and there are a lot of reload details
missed (like virtual register eliminations or addressing displacement
constraints etc).
