RE: Understanding IRA (The Story so far)

["Ian Bolton" <bolton at IceraSemi dot com>]

For those who have been following my adventure in the world of IRA, or
just
want to take advantage of some of the time I've spent on this, here's a
detailed recap of my exploits and my current status (which I'm very
happy
with):

I initially thought IRA was calculating costs wrongly for our
architecture
and so I experimented with adding more costs in different places.  This
effectively raised the priority of coloring certain allocnos and it led
to
good performance on some benchmarks, but it was really a complete hack
and
not an acceptable solution, so I went back to the drawing board.

After chatting with Vlad and Jeff, I realised IRA was calculating costs
correctly and the issue was that the costs only reflect the preferences
of
each allocno, as opposed to their "agnosticism" (i.e. not caring what
register they get), and so instructions that will happily take any
register
would take whichever one you showed them first; this meant that high
priority
agnostic instructions (that are colored first) were pinching BOTTOM_REGS
before the lower-priority special instructions got a chance.  To address
this, I came up with the simple solution of changing the
REG_ALLOC_ORDER,
where I show TOP_CREGS (the top half of our register set) to agnostic
instructions before the callee-save BOTTOM_REGS (c7-c15) by default, so
they
take TOP_CREGS when all other costs are equal; meanwhile, allocnos
requiring
BOTTOM_REGS were given them because they'd been left unallocated and
their
costs were lower than the TOP_CREGS.

This resulted in good performance improvements on some key benchmarks,
where
previously agnostic instructions were unwittingly using up these special
BOTTOM_REGS and leading to us allocating TOP_CREGS for operands in
special
instructions (which then required spills and moves to get a BOTTOM_REG
in
time to do the special instruction).  The main drawback of this
alternate
REG_ALLOC_ORDER was that we reduce the chance to reuse a callee-save
register
if we pick a TOP_CREG, because it doesn't work on all instructions, and
I
ended up getting regressions on some low-pressure benchmarks because we
used
more callee-save registers than previously.

I then tried various other ways of achieving the performance
improvements I
got on the high register pressure benchmarks and eliminating the
regressions
on the low-pressure ones:

* I tried using '?' constraints on agnostic instructions, such that they
erred to TOP_CREGS instead of callee-save BOTTOM_REGS, but this led to
too
much bias away from the more reusable BOTTOM_REGS (even when there was
no
need to avoid them) and I subsequently got regressions;

* I tried restricting the effect of the '?', by not using it for the
register
preferencing pass and by only adding on the alt_cost if I'd determined
the
allocno never requires BOTTOM_REG, and this got some decent performance,
but
I was still effectively penalising agnostic instructions for using
BOTTOM_REGS regardless of whether others allocnos were demanding them,
so I
got regressions;

* I tried coloring the ones that need BOTTOM_REGS first, which maximises
the
reuse opportunities, but this was essentially a rejection of the
existing
tried-and-tested coloring heuristics in IRA and consequently led to some
regressions;

* I tried combining the new REG_ALLOC_ORDER with a modified coloring
heuristic that uses the need for BOTTOM_REGS as a tie-breaker when two
allocnos are otherwise indistinguishable, but this was overriding the
ALLOCNO_NUM ordering (which I guess represents live range starting
points?),
so I got some regressions.

Fortunately, I was hit by another epiphany on Monday night and I
realised I
could emulate the new REG_ALLOC_ORDER dynamically within assign_hard_reg
and
only when necessary.  When allocating for an agnostic allocno, if it
conflicted with other allocnos that needed BOTTOM_REGS, I added 1 to the
full_cost of each of the BOTTOM_REGS so this allocno took a TOP_CREG.
This
gave me my best performance overall, but there were still some
regressions on
low-pressure benchmarks.  Whilst investigating them, I realised I had
gone
beyond my original new REG_ALLOC_ORDER because I was now avoiding all
BOTTOM_REGS instead of just the callee-save BOTTOM_REGS, so I changed
assign_hard_reg so it only adds 1 to each callee-save BOTTOM_REG.  This
means
we happily use up the caller-save BOTTOM_REGS (c1 - c6), regardless of
whether the allocno is agnostic or not, and this leads to more
reusability in
low-pressure cases (whereas avoiding all BOTTOM_REGS for an agnostic
instruction decreases reusability).

Note that I had been experimenting with Priority algorithm and
Chaitin-Briggs
up until this point and have decided to stick with Priority for now
because
we are using Priority already and this minimises the disruption and
reduces
the risk of regressions on untested inputs.  (Results generally show CB
to be
better performing and smaller code-size, but it suffers badly in very
high
pressure cases and spills more than Priority.)

As of yesterday, I had two versions of the Priority algorithm IRA: one
that
biases against all BOTTOM_REGS when an agnostic allocno conflicts with
one
that wants BOTTOM_REGS; and one that biases against only the callee-save
BOTTOM_REGS.  The former got me better performance on high-pressure
benchmarks and the latter got me better performance on the ones with
some low
pressure.  Either were an improvement on what I started with (default
IRA),
but I wanted to have the best of both worlds and so I needed a hybrid
that
biases against only callee-save BOTTOM_REGS for low-pressure and biases
against all BOTTOM_REGS for high-pressure.

Sure, I could have put in some ugly hack that looks at the register
pressure
number and picks one or the other, but instead I came up with a more
intelligent solution, which takes advantage of our single caller-save
TOP_CREG (c16), which appears after the caller-save BOTTOM_REGS in our
REG_ALLOC_ORDER.  Now, when an agnostic allocno conflicts with one that
wants
BOTTOM_REGS, I add 1 to the cost of c16 too, so we still give out c1, c2
etc
early on (because they have lower costs than all the callee-save regs
and
they appear earlier in the REG_ALLOC_ORDER than c16) to whichever
allocno
gets there first.  But later, when all the caller-save regs are
allocated, we
will use our first callee-save reg (agnostic allocnos will take c17,
ones
that need BOTTOM_REGS will take c7).  At this point, the future cost of
this
allocated callee-save reg becomes cheaper in future than the caller-save
regs, and we opt to use this in preference to the caller-save regs
(including
c1-c6).  The result is that, for high pressure, we are holding back all
the
BOTTOM_REGS for those that need them.

The performance of this version is my best ever and I am very happy with
it.
It doesn't quite get the highest performance I've seen on one of the
high-
pressure benchmarks, because we may still be giving up some BOTTOM_REGS
to
agnostic instructions early on, but it's pretty pretty good otherwise.

Thanks for reading and happy allocating!