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

[Michael Matz <matz at suse dot de>]

Hi,

On Mon, 3 Mar 2003, Daniel Berlin wrote:

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

As Denis already pointed out, this if() branch is only run, if we have
WEBS(SPILLED), i.e. if in fact something needs to change.

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

Hmm.  It's like this:  webs representing stack slots (stack pseudos I call
them, or so), can be colored with an_unusable_color, which means
conceptually, that they indeed have to be placed onto the stack.  Denis
made changes which in fact put those webs onto the stack, where formerly
they were placed onto stack only as last pass, if there were _only_
"uncolored" stack webs.

> Extra passes cost a lot of time (the time new-regalloc takes is
> directly related to how many passes it performed).

Yes, this thing, that uncolored stack webs are forced to stack early is
only necessary one some machines (namely to early expose the stack access
addresses), while for instance on ppc and i686 not.

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

Ugh, that's much.  I wouldn't have expected this.  The only thing which
_should_ have changed is, that now sometimes there are stack-accesses
while coloring, where formerly there were simply only accesses to
SPILL_SLOT_P() pseudos.  I believe Denis also makes some local
optimizations while creating the code for the stack accesses early.

Are you sure, that you don't coalesce SPILL_SLOT_P pseudos with non-spill
slots?  This indeed makes the time go up fairly much without improving the
code.  The change for that was only committed a few days ago, without it,
one had needed to ignore moves with any SPILL_SLOT_P pseudo involved.

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

It will, with pre-reload.  One sub function of build_i_graph() is
select_regclass(), which calls web_class(), which can put a web into
SPILLED.  This happens if one reference of a pseudo has conflicting
constraints with all other references.  In that case this reference is
"spilled" (for a lack of a better word, not to be confused with spilling
resulting from register pressure; it's similar to reloads just on
pseudos).  Such a web is then marked as changed, and Denis uses the
SPILLED list for this.

The integration with the allocator is rather ugly, I agree.  The use of
the SPILLED list for this is confusing.  What this code basically does is
something like:
  build-graph-including-webclasses
  if (pre-reloads needed && this-is-first-pass)
    go-to-next-round;
  else if (!pre-reloads needed)
    make-normal-coloring-attempt
  else
    abort

I.e. if there are pre-reloads, there is _no_ coloring attempt done (this
is so, because the code changed, and the interference graph doesn't
reflect this code anymore correctly, i.e. needs to be rebuilt).  But
pre-reloads are only expected in the first pass, if at all, therefore the
abort.

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

On your platform.  Take one with stranger constraints, and involving
sources which cast between funny types, and you somewhen will hit it.


Ciao,
Michael.