Re: new-regalloc.c patch

[Daniel Berlin <dberlin at redhat dot com>]

On 3 Feb 2001, Denis Chertykov wrote:

> Daniel Berlin <dberlin@redhat.com> writes:
>
> > > > > 	(edge_weight): Weight of edge between v1 and v2 equal to hard
> > > > > 	regs count in v2.
> > > >
> > > > This is wrong.
> > > > The edge weight is dependent on the number of hard regs in both. The
> > > > reason i left out the other cases is because i couldn't figure them out in
> > > > my head, and they didn't seem to crop up.
> > > >
> > > > edge_weight (v1,v2) is directly dependent on how much v2 can block
> > > > coloring of v1, and v1 can block coloring of v2.
> > >
> > > v2 of v1 and v1 of v2 isn't the same.
> > yes it is, because v2 + v1 == v1 + v2.
>
> Is you agree with "edge_weight isn't commutative" ?
> IE: Can be (not must be) edge_weight (v1, v2) != edge_weight (v2, v1)
>
No, i don't agree.
> > > So,
> > > edge_weight (v1,v2) + edge_weight (v2,v1)
> > > == (CLASS_MAX_NREGS (reg_preferred_class (v1), PSEUDO_REGNO_MODE (v1)
> > >     + CLASS_MAX_NREGS (reg_preferred_class (v2), PSEUDO_REGNO_MODE (v2))
> >
> > Not quite.
> > If each has two registers, you have a weight of two, not four.
>
> Why you think that weight is four ?
> It's only a thesis not a weight calculation.
>
> (edge_weight (v1,v2) + edge_weight (v2,v1)) must be equal to
> (hard regs of v1) + (hard regs of v2)
>
> Am I wrong ?

Yes.

>
> > > IE: For edge_weight (v1,v2): v2 can block
> > > CLASS_MAX_NREGS (regclass-v2, mode-of-v2) colors of v1.
> > >
> > > (IMHO: I can be wrong here, but I don't know where.)
>
> Where I'm wrong ?
See below.

>
> > >From machsuif, who uses this method as well:
> > static int
> > edge_weight(var_node *n1, var_node *n2)
> > {
> >    int w1 = (n1->status == PRECOLORED ? 0 : regs_needed(n1));
> >    int w2 = (n2->status == PRECOLORED ? 0 : regs_needed(n2));
> >
> >    switch(w1 + w2) {
> >      case 0:
> >      case 1:
> >      case 2: return 1;
> >      case 3: return 2;
> >      case 4: return (unaligned_pairs ? 3 : 2);
> >      default: assert(FALSE);
> >    }
> >    return -1;                   /* pacify compiler */
> > }
>
> Procedure above is commutative.
> IE: edge_weight (v1,v2) == edge_weight (v2,v1)
> It's strange for me.
>
> What is edge_weight ?
> IMHO: `edge_weight (v1, v2)' is a color count needed for coloring v2
> and (edge_weight (v1, v2) + edge_weight (v2, v1)) is a count of colors
> needed for coloring both v1 and v2.
>
> Example:
> v1 require one hard register;
> v2 require three hard registers.
>
> edge_weight (v1, v2) is 3 it's true because v2 block 3 colors for v1.
> edge_weight (v2, v1) is 3 - I can't understand why, because v1 block
> only one color for v2.
No it doesn't. It can potentially block all three.
What if it chooses the 2nd to last register available for v1?
Now you have nowhere to put v2, and v1 has blocked all three colors of v2.

I.E.
you have 16 registers.
All but 3 are precolored (for simplicity. In reality, they'd be used by
other candidates already)
v1 = 1 hard reg
v2 = 3 hard regs

1 precolored
2 precolored
3 precolored
4 precolored
5 precolored
6 precolored
7 precolored
8 precolored
9 precolored
10 precolored
11 precolored
12 precolored
13 precolored
14
15
16

Now, if you choose register 14 for v1, you have blocked *all three* colors
for use with v2, because it needs 3 consecutive hard regs.
If you choose register 14 for v2, you have blocked *all three* colors for
use with v1, because there are no hard regs left.

You are right in the *general* case that, given enough registers, v1 will
only block one color of v2.
But because v1, *in some cases*, can block 3 colors of v2, we have to say
it can always block 3, because otherwise we won't account for the
possibility, which exists.

 >

> > >    On some machines, double-precision values must be kept in even/odd
> > >    register pairs.  The way to implement that is to define this macro
> > >    to reject odd register numbers for such modes.
> > > --------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >
> > Wheee.
> >
> > Let me double check that the change doesn't break anything for weird
> > reasons, and i'll check it in as well.
>
> Is you agree here (remove HARD_REGNO_MODE_OK) ?
>
Yeah.