Re: gcse, store motion and loop optimizer

["Tim Prince" <tprince at computer dot org>]

----- Original Message -----
From: "Jan Hubicka" <jh@suse.cz>
To: <gcc@gcc.gnu.org>; <dan@cgsoftware.com>;
<timothy.c.prince@intel.com>
Sent: Friday, August 03, 2001 12:58 AM
Subject: gcse, store motion and loop optimizer


> Hi,
> I am just tracking down the failure in twolf spec2000 benchmark. What
> happends there is basic-style programming, where all variables are
global,
> and of course loop induction variable is too.
>
> Originally we did handled this in loop optimizer, by hoisting (We
should
> probably kill that code, but at least in twolf it still hoists, I
willl
> re-check one Dan's store motion work is in) and optimized the loop
> in de-facto same was as if it were static.
>
> Now we do have problem. The induction variable is killed by gcse in
two
> steps, first it is PREed, then it is store motioned to sotre the final
> value, resulting in code, that use one regiester for iteration and
> always store the value to other register for storing the result.
>
> CSE is not able to unify these, as her local point of view suggest
that
> it is better to use first value for iterating (it don't know it is the
> induction variable) and then the second variable for storing (as the
lifetime
> is longer and CSE decides it is superrior).
>
> This is unfortunate, as the strength reduction than goes crazy,
creating
> redundant induction variable with value i+1 and doing other crazy
think
> confusing itself in the next loop iteration (by inserting instructions
> in the BIV computation where it don't expect) failing to unroll and
producing
> ugly code. This is basically because it sees computation of
x=induction+1
> separately and don't know, that it is just computation of the
> induction variable and that at the end there is induction=x
> (after several uses x and making several copies of it).
>
> Strength reduction has logic to get around some damage, but IMO it
should
> be able to expect that:
> 1) there are no dead computations of general induction variables
> 2) there are no unneeded copies
>
> as assuring those would require to do similar analyzis as gcse does.
> So my question is, would be possible to fix gcse pass to cleanup the
> damage? It can be done by eighter making store motion curefull and
reuse
> the value in register if it reaches, or run the copy propagation after
> it together with killing dead copy instructions (as subsequent CSE
pass
> undoes copy prpagation partially currently). This would require CPROP
> to do the transformations even locally on the beggining and ends of
basic
> blocks.  I've experimented with using something like "REG_DEPRECATED"
> note to control CSE decisions, but I think it would be cleaner to
avoid
> gcse from being stricly global, as the GCSE itself isn't, just CPROP
is.
>
> OK now I will continue to figure out what exactly goes wrong in the
second
> loop pass.
>
> Tim: May this be the case in your programs?
> Honza

Making induction variables global is bad news.  I'll check whether that
is happening in the samples I sent; if changing the source to make the
induction variables local solves the problem, I'll be satisified.  I'd
even consider it good for the compiler to warn in -Wall -O mode if that
happens, and to indicate that it disables optimization.  If it happens
in SPEC, I'm sure many compilers fail to optimize that.  Does this
answer part of your question?