RE: Understanding IRA

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

Jeff Law wrote:
> >
> > I had an epiphany this morning and came up with an idea to achieve
> the
> > lookahead I thought I needed, thereby making the costs created by '?'
> a
> > lot more concrete and reliable.
> >
> > Firstly, I have altered the alt_cost adjustment (for '?') in ira-
> costs.c,
> > so that it only happens on the second pass *and* only when the first
> pass
> > has determined that this allocno never needs a BOTTOM_REG.
> >
> > The first condition (that it only occurs on the second pass) is there
> so
> > that the preferred class calculated for an allocno is based on hard
> > constraints, as opposed to the fuzzier constraints of '?'.  Without
> this
> > change, the second pass cannot use the preferred class to correctly
> add
> > costs for each class that doesn't intersect with the preferred class.
> >
> > e.g. If an insn has an allocno as an operand that requires
> BOTTOM_REGS,
> > then we want the cost for TOP_CREGS for that allocno in that operand
> to
> > be higher to show the cost of moving it into BOTTOM_REGS.  But if we
> let
> > the '?' constraints dictate the pref class, and this allocno appears
> in
> > other insns where the '?' constraint has appeared, then TOP_CREGS may
> > end up being the preferred class and so this insn, which actually
> needs
> > BOTTOM_REGS for its operand, will end increasing the costs for any
> class
> > that doesn't intersect with TOP_CREGS (i.e. BOTTOM_REGS).
> >
> > I'm thinking that this change will be generally useful.  What are
> your
> > thoughts?
> >
> Step #1 seems a lot like adding '*' before the '?'.   The idea behind
> '*' was to make it possible to ignore a constraint modifier such as '?'
> or '!' when choosing register preferences.   I haven't looked at IRA's
> implementation of preferencing, but I suspect it mostly lifted the old
> allocator's preferencing code, so I'd expect we're still supporting
> '*'.

I just had a look through the code and '*' means the '?' is completely
ignored during costing.  A quick grep shows me that '?' would then only
have meaning in reload.c, reload1.c and postreload.c.

This is the code I have from record_reg_classes() in ira-costs.c:

		case '*':
		  /* Ignore the next letter for this pass.  */
		  c = *++p;
		  break;

The comment suggests it will be ignored in "this pass", but the code
makes it get ignored in both passes during ira-costs.c.  Maybe this is a
bug?  Perhaps it should read:

		case '*':
		  /* Ignore the next letter for this pass.  */
		  if (!allocno_pref)
                c = *++p;
		  break;

If I changed all my '?' constraints to be '*?' then the above
change would achieve what my hack does.

> > The second condition is determined by me storing a new variable in
> each
> > allocno on the first pass to flag whether it ever appears as an
> operand
> > that must have BOTTOM_REGS.  On the second pass, I can then only
> penalise
> > an allocno for using my precious BOTTOM_REGS if I have already
> determined
> > that it will never need them.
> >
> > This change is probably too specific to our case at the moment, but
> it
> > could probably be made generic, if it has use to other architectures.
> >
> I think we already have code to do something like this via
> CONFLICT_HARD_REGNO_COSTS.  Though I must admit, I haven't entirely
> wrapped my head around those costs and how they're used yet.

I was hoping I would be able to avoid all the conflict-related stuff, but
this may be where I have to go next, although I am considering returning
to my elegant solution of just giving out TOP_REGS first unless someone
specifically needs BOTTOM_REGS.  This does perform slightly worse for low
reg pressure cases (due to the case I mention below), but is the best
solution I have come up with for the high pressure cases.

> > Sadly, I don't think either approach will handle the case where there
> is
> > low pressure and we first grab a TOP_CREG for something like an ADD
> (due
> > to our constraints telling us to) then we free up that register cos
> it's
> > not needed anymore and then we have to use a different (BOTTOM_REG)
> reg
> > for something like an AND; we should have just used just one
> BOTTOM_REG.
> >
> That would actually be something helped by the patch we were discussing
> in a prior message.  The only trick is the two allocnos would have to
> be
> connected by conflicting with some 3rd allocno.  The 3rd allocno may
> not
> be a high degree, but the heuristic will still trigger and slightly
> encourage the ADD and AND allocnos to share the same reg.

Yeah, but how do I ensure that the one that needs the BOTTOM_REG gets
colored first, thereby leaving its register free to be re-used?  This
little tweak only kicks in when you are coloring the first of the non-
conflicting pair, right?  If the agnostic allocno is colored first, it
will grab the TOP_REG, thereby causing your tweak to slightly decrement
the cost of using that TOP_REG for the other allocno, to encourage
sharing, and it will end up with a TOP_REG that it can't use.

I have thought of using the need for BOTTOM_REGS as a tie-breaker when
coloring (in allocno_bucket_compare_func), so that two non-conflicting
ones that otherwise have the same priority will end up being ordered
so that the one that needs BOTTOM_REGS gets colored first.  What are
your thoughts on this approach?

Cheers,
Ian