Re: complete_unrolli / complete_unroll

[Richard Guenther <richard dot guenther at gmail dot com>]

On Thu, Aug 20, 2009 at 3:19 AM, Albert Cohen<Albert.Cohen@inria.fr> wrote:
> Richard Guenther wrote:
>>
>> gfortran.dg/reassoc_4.f, the hottest loop from calculix.
>
> Thanks.
>
> This example is slightly different. Graphite should be able to handle it
> with loop fusion rather than pre-unrolling + cse. But I agree that the
> unrolling + cse approach also makes sense (and does not depend on the same
> legality constraints as loop fusion).
>
> This makes me think of a simple, general criterion to detect cases where
> pre-unrolling of inner loop helps further cse and loop optimizations.
> The idea is to unroll only when we can see some evidence of array references
> that are not presently loop-invariant that would be made (outer)-loop
> invariant via full unrolling of some inner loop.
> This can be implemented by complementing the current heuristic (or its
> complementary enhancements by Honza) with an additional condition, only
> enabled when running it with the "i" (inner) flag (which should probably be
> renamed if we do implement this...).
>
> The simplest, weakest condition I can think of would be to traverse all
> array references in the region enclosed by the loop-to-be-unrolled, compute
> the SCEV for each one, instanciate it in the loop's context, and checking if
> it only depends on the loop counter, as well as outer loop counters or
> parameters.
>
> This condition would a priori pass on the tramp3d and reassoc_4 cases. Yet
> it is probably too weak and will still pass on many codes where unrolling
> would probably not help at all... and probably harm.
> If this is the case, we should consider multiple loops to be unrolled, and
> the combined effect of unrolling ALL of these, resulting in complete
> instanciation of the array subscripts with constants. This is a very special
> case, again satisfied by our two motivating examples. Maybe it will be too
> specific and we'll have performance regressions... It remained to be
> investigated if we have to go through a stricter condition than the first,
> weak one I proposed.
>
> If this is not clear, I can write some pseudo-code to clarify :-).

Can't we use graphite to re-roll loops?  That is, compress the
polyhedron by introducing a new parameter?  But maybe I am
not good at guessing what your initial bloat issue looks like.

The reason I'm asking is that there is enough code out in the
wild that has loops with manually unrolled bodies - I have seen
up to 16 times here.

Richard.
> Albert
>