Re: Modern compilers for ye olde architectures

Am 15.10.21 um 09:37 schrieb Anton Ertl:
>
> I had some questions which were mostly answered by the paper, but
> maybe you can offer additional insights:
>
> * Am I right that earlier register allocators were bad for irregular
> register sets, and that's why general-purpose registers won once
> compilers became dominant? Why did general-purpose registers become
> dominant?


Indeed earlier register allocators could not handle irregular
architectures well. In particular, Chaitin-style graph coloring register
allocators are simple, and efficient if we have enough general-purpose
registers. Chaiting-style register allocators and RISC-style
architectufres are a good match.


> * What are the key points why your work can deal with irregular
> register sets, and earlier approaches are pretty bad at that?
>
> It seems to me that you use the CPU power available now to try out
> many different assignments, while earlier work has balked at that.
>
> * Do you have any idea why no good approach for dealing with irregular
> instruction sets has been found in, say, the 1970s and 1980s when
> irregular register sets were more common (e.g. on the Z80 and the
> 8086).
>
> Your approach is an (ideally exhaustive) search that uses more CPU
> power (and memory?) than was available then. At the time, one would
> have resorted to heuristics, but apparently no general effective
> heuristics have been found.


Indeed my approach uses more CPU power and memory than was available
then. There is another newer approach that claims to handle
irregularitites well by Roberto Castañeda Lozano, but it also uses more
CPU time and memory than was available in the past.


Besides the CPU power and memory, both my and his approach also build on
theoretical advances that simply weren't there back then.
I use tree-decompositions. While the basic idea is there in Wagner's
work on S-functions in the 1970s, it did not get applied to register
allocation until Thorup's and Bodlaender's works in 1998. Those two
works considered a quite abstract version of register allocation
(graph-coloring with all variables the same size). Thorup also offered
for the first time, a practical way to get tree-decompositions of
control-flow graphs (there are flaws in what he did, but it was still
good enough to build on for me, then).


Philipp

Return to the comp.compilers page.
Search the comp.compilers archives again.