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 09:17 +0200
Organization	Compilers Central
Message-ID	<21-10-034@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:

>
> Which poses the question: In your empirical work you stopped at 10^8
> assignments (in some cases, less).  How did you get provably optimal
> assignments on the Z80 with its 9 registers?

> Castañeda Lozano

On one hand, we have the theoretical bound on the number of assignments,
which is useful for proving that we can be optimal in polynomial time.

On the other hand, getting a provably optimal result when compiling an
individual function is something that is easier to achieve, as the
theoretical bound is a worst case.

* In real programs, most bags in the tree-decomposition will be
smaller than the tree-width allows.
* In real programs, there will be parts of the control-flow graph, where
the number of variables alive is less than (tw(G) + 1)*r.
* In the implementation, we can throw away some assignments early,
without sacrificing optimality, when we know that code generation for
them would be impossible (e.g. in the z80 port, unlike the stm8 port,
code generation cannot handle variables that have some of their bytes
allocated to registers, but other bytes spilt).

In ports of SDCC that use this register allocator (which now is most of
them), when enabling extra comments in the generated assembly code via
--fverbose-asm, SDCC will place a comment at the beginning of each
function stating if the register allocation was provably optimal.

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