Re: Modern compilers for ye olde architectures

From	Philipp Klaus Krause <pkk@spth.de>
Newsgroups	comp.compilers
Subject	Re: Modern compilers for ye olde architectures
Date	2021-10-18 08:56 +0200
Organization	Compilers Central
Message-ID	<21-10-033@comp.compilers> (permalink)
References	<21-10-007@comp.compilers> <21-10-012@comp.compilers> <21-10-015@comp.compilers> <21-10-024@comp.compilers>

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Modern compilers for ye olde architectures "Luke A. Guest" <laguest@archeia.com> - 2021-10-05 13:22 +0100
  Re: Modern compilers for ye olde architectures David Brown <david.brown@hesbynett.no> - 2021-10-05 19:59 +0200
  Re: Modern compilers for ye olde architectures Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2021-10-05 22:12 +0200
  Re: Modern compilers for ye olde architectures Derek Jones <derek@NOSPAM-knosof.co.uk> - 2021-10-06 01:26 +0100
    Re: Modern compilers for ye olde architectures "Luke A. Guest" <laguest@archeia.com> - 2021-10-06 09:00 +0100
  Re: Modern compilers for ye olde architectures anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2021-10-06 07:56 +0000
    Re: Modern compilers for ye olde architectures Philipp Klaus Krause <pkk@spth.de> - 2021-10-06 18:20 +0200
      Re: Modern compilers for ye olde architectures anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2021-10-15 07:37 +0000
        Re: Modern compilers for ye olde architectures Philipp Klaus Krause <pkk@spth.de> - 2021-10-18 08:35 +0200
        Re: Modern compilers for ye olde architectures Philipp Klaus Krause <pkk@spth.de> - 2021-10-18 08:56 +0200
        Re: Modern compilers for ye olde architectures Philipp Klaus Krause <pkk@spth.de> - 2021-10-18 09:17 +0200
          Re: Modern compilers for ye olde architectures gah4 <gah4@u.washington.edu> - 2021-10-21 21:53 -0700
            Re: Modern compilers for ye olde architectures Kaz Kylheku <480-992-1380@kylheku.com> - 2021-10-22 17:28 +0000
    Re: Modern compilers for ye olde architectures dave_thompson_2@comcast.net - 2021-11-14 15:04 -0500
  Re: Modern compilers for ye olde architectures Theo <theom+news@chiark.greenend.org.uk> - 2021-10-06 10:36 +0100
    Re: Modern compilers for ye olde architectures "Luke A. Guest" <laguest@archeia.com> - 2021-10-06 16:20 +0100

csiph-web