Re: Bug in ra-colorize.c:merge_moves?

[Daniel Berlin <dberlin at dberlin dot org>]

On Monday, March 3, 2003, at 04:12  PM, Denis Chertykov wrote:

> Daniel Berlin <dberlin at dberlin dot org> writes:
>
> > On Monday, March 3, 2003, at 02:59  PM, Michael Matz wrote:
> >
> > > Hi,
> > >
> > > On Mon, 3 Mar 2003, Daniel Berlin wrote:
> > >
> > > > new-regalloc-branch isn't very good compile-time wise.
> > > > For instance, we can't ever color in one pass anymore (it pretends
> > > > something has changed, even if nothing has, so the minimum number of
> > > > passes is 2).
> > >
> > > Oh, really?  That should obviously not happen.  Do you have a
> > > testcase, so
> > > I can fix that?
> >
> > You probably don't need a testcase, since it's obvious from looking at
> > the code itself.  You just probably didn't notice when it happened
> > (it's a one line problem, hard to see).
> >
> > In one_pass, we have:
> >
> >   else if (ra_pass == 1)
> >      {
> >        if (death_insns_max_uid < get_max_uid ())
> >          {
> >            sbitmap_free (insns_with_deaths);
> >            insns_with_deaths = sbitmap_alloc (get_max_uid ());
> >            sbitmap_ones (insns_with_deaths);
> >            death_insns_max_uid = get_max_uid ();
> >          }
> >        last_changed_insns = ra_modified_insns;
> >        detect_web_parts_to_rebuild ();
> >        last_changed_insns = NULL;
> >        something_spilled = 1;
> >        last_max_uid = get_max_uid ();
> >      }
> >
> > Note that it's setting something_spilled to 1 unconditionally on the
> > first pass (which automatically means we will do another pass, since
> > we return something spilled as the return value of one_pass, and the
> > calling code is "changed = one_pass ...").
> > This code isn't in the HEAD's ra.c.  IIRC, it was added by Denis on
> > 08-Jan-03, in revision 1.1.2.65:
> > 1.1.2.65     (denisc   08-Jan-03):       something_spilled = 1;
>
> The previous condition is 'if (!WEBS (SPILLED))'.
> Only if we have a webs to spill then we doing this.
I actually pointed out the wrong line. Your stack slot stuff (the 
subst_to_stack() check + setting of something_spilled) makes us always 
do an extra pass if something got colored by an unusable color (even if 
nothing else spilled) which means we can never color in *2* passes 
(going by RA counts, which is 3 coloring rounds), not one (sorry about 
that), which we didn't use to do before.

From params.c:

 spill cost of graph (initially) = 0
 spill cost of graph (after alias-breaking) = 0
 spill cost of graph (before spill-recolor) = 0
 spill cost of graph (after spill-recolor) = 0
Stack spill slots must be added.
Allocate stack spill slots for webs:
         62(89) insns:  134(u37) 139(d156)
         63(90) insns:  135(u35) 138(d157)
         64(88) insns:  133(u36) 136(u34) 137(d158)

....
RegAlloc Pass 3 (because of the subst_to_stack_p() call setting 
something_spilled).

Extra passes cost a lot of time (the time new-regalloc takes is 
directly related to how many passes it performed).  I've got a tree 
with everything but your stack slots changes merged (including 
pre-reload), and the number of coloring passes is about the same.  
However, with your stack slots changes , it takes 3-5x as many passes 
in those functions that spill (some functions went from 3 passes to 15 
passes).  It seems we have cases where after you assigned stack slots, 
we spill again the next pass, and then have another couple passes to 
remove those spills, repeat.

If it wasn't really that bad, i would have merged it into the changes 
i'm cleaning up for merging into the mainline.

I should also point out the code i pointed out in the previous message 
is still broken, if you think it will ever do something.
It will never trigger, afaict.
I change it to an abort in that case, and bootstrapped, and it doesn't 
trigger the abort (meaning it never falls into that case during a 
bootstrap).

What exactly are you trying to do with that code?
> Only if we want to spill a web which can't have sigle color.
> (May be I'm wrong.)
> I'm very interested in testcase.


> Denis.