A Question About LRA/reload

[Jeff Law]

On 12/10/14 02:02, Ajit Kumar Agarwal wrote:
>>> Right.  After IRA was complete, I'd walk over the unallocated
>>> allocnos and split their ranges at EBB boundaries.  That created
>>> new allocnos with a smaller ??>>conflict set and reduced the
>>> conflict set for the original unallocated allocnos.
>
> Jeff: In the above approach of splitting the ranges for unallocated
> allocnos is aggressive or based on the approach of some heuristics
> that the Live ranges for unallocated allocnos is not touched inside
> the EBBs.
It was focused on allocnos which were live at EBB boundaries and 
splitting the ranges at those boundaries.

In the case where the allocno was live across the EBB, but not used/set 
in the EBB, the split effectively homes the allocno in its stack slot 
across those EBBs.  That reduces the conflicts for the original allocno 
(and possibly other allocnos that need hard registers).

You can actually use that property to free up hard registers as well. 
If there's allocno(s) which are not used/set in an EBB, but which got a 
hard register, you can split their range at the EBB boundary.  This 
results in those allocnos homing into their stack slot across those EBBs 
(or some other hard register).  Which in turn frees one or more hard 
registers within the EBB.

In fact, you can take that concept quite a bit further and use it as the 
fundamental basis for range splitting by simply changing the range over 
which you want the allocnos to be transparent.  The range could be an 
EBB, BB a few insns or a single insn.

And that was the basis for backwards walk through the BB approach I was 
experimenting with.  We just walked insns backwards in the BB, when we 
encountered an insn with an unallocated allocno, we split the range of 
some other allocno to free up a suitable hard register.  First we'd look 
for an allocno that was transparent across the EBB, then a BB, then the 
largest range from the insn needing the reload to the closest prior 
use/set.  By splitting across these larger ranges, we tended to free up 
a hard register over a large range and it could often be used to satisfy 
multiple unassigned allocnos.  I was in the process of refactoring the 
code to handle things like register pairs and such when I got pulled 
away to other things.  I don't recall if this variant was ever 
bootstrapping, but it was getting great fill rates compared to reload.


>
> After the above splitting, are you building the conflict graph again
> to assign the new allocnos. If the Conflict graph is built again,
> this will affect the compile time.
The conflict graph was incrementally updated IIRC.  The compile-time 
issues were mostly to get the register classes and ira cost models accurate.

Jeff