Re: combine_givs_p address cost

[Toon Moene <toon at moene dot indiv dot nluug dot nl>]

[ Note:  I have to be a bit vague about this here, because I haven't
  been able to build the egcs trunk since mid-October, due to a mis-
  compilation of the stage2 compiler that crashes the build when
  trying to compile `bb' for the second time (on m68k-next-nextstep3) ]

>Richard Henderson writes:
> > The problem with that test is that it decides, with no surrounding
> > context, whether the giv should be combined.  Now suppose there are
> > twenty givs that could be combined instead of two.  Failing to allow
> > their combination means we'll have oodles of spills and oodles of
> > increments where offsets from one register would have sufficed.

>  Hang on, I'm confused ;-(  What I'm seeing is the
>  opposite.  With combine_givs_p as it stands at present,
>  too many address registers are required rather than a
>  few with offsets from them.

I can't see how this is possible.  Combine_givs_p should determine  
if givs can be combined (i.e. if two givs are related via an  
expression x such that x(giv1) if giv1 resides in a register is a  
valid addressing mode for the architecture at hand.).

This can only _reduce_ the number of registers used (unless  
combine_givs_p decides *incorrectly* that two givs can't be  
combined).

> > If you have specific suggestions for heuristics, I'm quite willing
> > to discuss them.  And we can always try them out on various problem
> > sets to see how they do.

>  I suppose the simplest heuristic would be a function of
>  the number of GIVs found in a loop and the number of
>  address registers on the target machine.  This could be
>  supplemented by the ADDRESS_COST information or whether
>  all the displacements from a register could be converted
>  to autoincrements  (I'm about to submit patches to flow.c
>  that will convert a series of memory references into
>  autoincrements).

As far as I can see combining givs *cannot* lead to more registers  
being used than already were.  Are you sure you're not misled by the  
fact that strength reduction of induction variables _itself_ can  
lead to more address registers being used ?  There is already an  
heuristic in place for this (one that we circumvent for FORTRAN,  
because it's only approximately right for rank-one arrays like in  
your example code).

HTH,
Toon.