Re: Understanding IRA

[Jeff Law <law at redhat dot com>]

On 12/02/09 13:29, Ian Bolton 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 '*'.



> 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.

> 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.

> > Absolutely.   Note that we use a tiny adjustment to costing for this
> > heuristic so that, in general, this heuristic only applies when  when
> > other costing heuristics don't result in a particular register
> > preference.
> >      
> Yes, you don't want to undo all the cleverness done previously.  I do
> wonder if the costs should all be multiplied by ten so we can distinguish
> between a cost of 1 and something that should be less than 1 but not 0.
>    
Note that most costs are scaled based on REG_FREQ (which is derived from 
BLOCK_FREQ).  So there's already a multiplier effect.  So adding an 
unscaled "1" to allow us to detect this situation precisely.

Jeff