Rajkishore Barik wrote:
Hi,
Thanks very much. I still have doubts on your suggestion:
AFAIK, the back-end pass consists of (in order) : reg move -> insn sched
-> reg class -> local alloc -> global alloc -> reload -> post-reload.
There are edges from reg move to reg class and reload back to global
alloc.
In case I want to implement a linear scan which may split live ranges
(pseudos) into live intervals(smaller pseudos) and allocate different
registers
for each of them. This process would break the whole loop.
So, what did you mean by --- "run this pass in between the register
allocator and
reload, that would probably be doable."?
Sorry, you were not specific. When I read your first message, I also
thought that you were going to rewrite the reload pass in other words to
use another algorithm make strict RTL when there are only hard registers
and all insn constraints are satisfied.
As I understood correctly now, you are going to implement linear scan
register allocator which also does what reload in gcc does.
The first of all you did not stated what are your project goals. Is it
better understanding how gcc register allocator and reload work (that is
a good project then) or you want to write a better register allocator
which will be used in gcc. The second goal is hard to achieve because
linear scan register allocator generates worse code than Chaitin-Briggs
and the current gcc register allocator (Chow's priority based
coloring). Another problem is that the linear scan register allocation
is patented. Do you have permission to use it in gcc? Currently we
have permission to Chaitin's (IBM) and Brigg's (Rice university)
patents. We can not ignore patents as LLVM does not worry about patents
which uses petented linear scan and Callahan-Koblentz register allocators.
IMHO, Ian wrote correctly that you can write a decent register allocator
which does also reload stuff for one target (although even in this case
number of details to keep in mind will be overwhelming) but it is a hard
to write a decent code which works for all gcc targets. So many efforts
were used to improve reload for all gcc processors (even weird ones like
SH with many registers but very small displacements or mcore with few
registers and small displacements), you should do the same to be successful.
Reload does a lot of things not mentioned in Zack's document like
register rematerialziation, virtual register elimination, address
inheritance (which is important for processor with small address
displacements) and few others. There is opinion that doing some reload
things before the register allocation will permit to generate a better
code because register allocation will not worry about the constraints
and reload will be more predictable (more accurately will work in less
cases). Such project already exists (see svn branches).
In any case your work on register allocation and reload will be
appreciated by the community only please be prepared that it will be not
an easy way.
Vlad
