Re: Modern compilers for ye olde architectures

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

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