Re: Modern compilers for ye olde architectures

Am 15.10.21 um 09:37 schrieb Anton Ertl:
> Philipp Klaus Krause <pkk@spth.de> writes:
>
> I am wondering about one thing in the empirical results in your paper:
> Why is the code size not monotonously falling with increased numbers
> of assignments? Are these independent runs with different
> (pseudo-random) assignments?


The basic idea is that for some subsets of nodes in the control-flow
graph, we try all possible assignments to registers. The
tree-decomposition tells us which subsets that are, and how we can
assemble the locally optimal solutions into globally optimal ones.


Since the cost function gives us the real costs from code generation, we
are optimal wrt. to the optimization goal, e.g. code size. However, thre
ar three aspects, why code size might not fall monotonously with an
increased number of tried assignments:


1) If the peephole optimizer is active: The register allocation approach
can only consider code size after code generation, it doesn't know what
the peephole optimizer might do with the result.


2) The register allocator considers variables / parts of variables as
assigned to certain registers, or spilt. It doesn't know where spilt
variables will end up on the stack. It can thus consider the benefits of
coalescing for variables assigned to registers, but not for spilt variables.


3) We know that the number of assignments we need to consider to get a
provably optimal result is polynomial if the input is a structured
program. But the polynomial bound might be too big for practical
compilation, so we limit the number of assignments considered (via the
--max-allocs-per-node parameter to SDCC). In that case the allocator can
not give a provably optimal result. In some cases, it needs to make a
decision, on which assignments to condier further (and does so based on
incomplete information using a heuristic). Here, considering more
assignments can lead to a certain assignment considered previously no
lonjger being considered. E.g. when going from --max-allocs-per-node 10
to --max-allocs-per-node 100, we will now consider 100 assignments
instead of 10. But not all of the previously considered 10 might make it
into the 100 considered now. And in the end it might turn out that one
of the 10 might have given us a better result globally. The decision
which assignments to consider further us not random, but based on a
heuristic that mostly takes local information into account.


Philipp

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