Re: i seem to have hit a problem with my new conflict finder.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

Vladimir N. Makarov wrote:
> Kenneth Zadeck wrote:
>
>> Vladimir N. Makarov wrote:
>>  
>>
>>> Kenneth Zadeck wrote:
>>>
>>>   
>>>> it looks like the backwards scan is not getting "enough" interferences
>>>> to make reload/global happy.
>>>>
>>>> the case comes about because of way local_alloc is preassigning
>>>> regs for
>>>> pseudos that would map into more than 1 hardreg.
>>>>
>>>> pseudo's are as wide as they need to be.  When local_alloc assigns one
>>>> of these to a hard reg, it assigns it to the first hardreg needed and
>>>> the mode is used to indicate how many of the following regs are
>>>> needed.
>>>>
>>>> The problem comes where you have a store that uses 2 or more hard regs
>>>> but one or more of those hardregs is unused.
>>>>
>>>> In a forwards scan, ALL of the set regs will interfere with anything
>>>> live until the last set reg goes dead.  In a backwards scan, the
>>>> unused
>>>> hard regs never cause interferences.
>>>> global/reload wants these interferences.
>>>>
>>>> This is, of course, one of the reasons that backward scanning the
>>>> proper
>>>> way to build an interference graph.  But something in global or reload
>>>> cannot handle the truth.
>>>>
>>>> There are a lot of ways to handle this problem:
>>>> 1) We could do a pass that breaks multiword sets into individual
>>>> regs if
>>>> some of those regs are dead.  I guess the downside of this is that
>>>> such
>>>> insns may not match some patterns anymore.
>>>>
>>>>
>>>>
>>>>     
>>> May be it is right thing to do in long perspective but I think it is
>>> too complicated to implement it working.
>>>
>>>   
>>>> 2) We could turn off local.  I was planning on testing this anyway
>>>> because i want to see if local, at this point, is just making
>>>> global do
>>>> a bad job.   However, my hope is that global or the new allocator from
>>>> vlad is smart enough to properly handle the case where some parts of a
>>>> multiword set are dead.
>>>>
>>>>
>>>>     
>>> The local has very important part update_equiv_regs.  Without it you
>>> will have a serious performance degradation.
>>>
>>>   
>> I understand that, but the actual local assignment is the part that gets
>> in the way of both this and the rest of allocation.  I was going to
>> leave that part and just turn off the local assignment.
>>
>>  
>>
>>> As for IRA I started work on using df-infrastructure for it.  I am not
>>> going to use UREC or LIVE at least at first time.  I'll use LR as it
>>> was in IRA before the df-infrastructure.  IRA also uses forward scan
>>> for building conflicts.  After making df-infrastructure working in
>>> IRA, I should think about using LIVE or backward scan but right now I
>>> am not sure that will give an improvement worth to use it.
>>>
>>>   
>> The reason that i was doing this now was because i thought we might get
>> some gain from it and that it is nonorthogonal to what you were doing
>> with IRA.  I would actually assume that you could just drop this code
>> in.  This was what we talked about doing at the bad Indian restaurant
>> at the summit.
>>
>>  
>>
> Yes, Ken. I remember that talk.  Probably I was not clear.  I meant
> that we could use LR instead of  UREC or LIVE again.  I introduced
> usage of "accurate live analysis" (analog of UREC/LIVE).  It gave 0.5%
> improvement on SPEC95 but creates a lot of problems. I should
> acknowledge that probably the introducing "accurate live analysis" was
> my mistake.
>
> I found that we need LIVE now because it is used in some optimizations
> like initialization of uninitialized regs.  So just getting rid off
> only UREC will be good too.  It might give some gain.
>
> In any case IRA can not use UREC because UREC is needed before IRA
> calculates reg class info and the reg class info is needed for
> calculation of UREC.  If you manage to use LIVE instead of UREC, it
> would permit to use LIVE also in IRA instead of LR.  But I can not say
> can we use LIVE instead of UREC because I don't know the
> df-infrastructure well yet.
>
we should talk.  I am avail today.  i am leaving on vacation tomorrow
for a week.

Even if this patch does not get in this round, you should consider it as
a starting point for building the interference graph for ira.  

it does not use urec and a big part of the patch is just getting rid of
urec,  It does a backwards scan using the live at bottom set as the
starting point for the scan.
This is the most accurate you can get so there really is no reason not
to use it since it is also no more expensive than any weaker technique. 

The biggest difference is what is done with the early clobbers.  The
biggest thing that i objected to with the make accurate live analysis
was it marking the early clobber as being live from the beginning of the
block.   This patch just adds interferences from the early clobber
output to the inputs that die within the insn and could be in the same
class.

Kenny