Re: [Patch PR 44576]: Reduce the computation cost in compute_miss_rate for prefetching loop arrays

[Sebastian Pop <sebpop at gmail dot com>]

On Wed, Jun 30, 2010 at 03:52, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Wed, Jun 30, 2010 at 2:06 AM, Fang, Changpeng <Changpeng.Fang@amd.com> wrote:
>> Hi,
>>
>> Attached is the patch that partially fixes bug 44576: ?testsuite/gfortran.dg/zero_sized_1.f90 with huge compile
>> time on prefetching + peeling.
>>
>> The cost of compute_miss_rate in tree-ssa-loop-prefetch.c is found to be very high, and it results in an exploding
>> compilation time when there are thousands of memory references in the loop.
>>
>> compute_miss_rate is to compute the possibility (miss_rate) that two memory references fall on difference cache
>> lines. We will insert prefetches for both references if the computed miss rate is greater than the experimentally
>> determined ACCEPTABLE_MISS_RATE.
>>
>> In this patch, compute_miss_rate is renamed as is_miss_rate_acceptable, and does an early return if the computed
>> miss rate is already greater than the ACCEPTABLE_MISS_RATE, and thus significantly reduces the cost for such
>> case. Note that the worst case cost is not affected by this patch.
>>
>> This patch reduces the compile time of the test case from 1m20'' to 1m03'' on an amd-linux64 system.
>> Note that without -fprefetching-loop-arrays, the compile time on the same system is 0m30''. The extra 33'' is mostly
>> spent in "compute_all_dependences (datarefs, &dependences, vloops, true)". ?I am not sure whether the cost in
>> ?dependence analysis for loop should be that high (with several thousands memory references in loop) or there
>> is a bug in dependence computation.
>
> Well, it seems that you compute the same information over-and-over
> by doing
>
> unsigned int
> tree_ssa_prefetch_arrays (void)
> {
> ...
> ?FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
> ? ?{
> ? ? ?if (dump_file && (dump_flags & TDF_DETAILS))
> ? ? ? ?fprintf (dump_file, "Processing loop %d:\n", loop->num);
>
> ? ? ?unrolled |= loop_prefetch_arrays (loop);
>
> static bool
> loop_prefetch_arrays (struct loop *loop)
> {
> ...
> ?determine_loop_nest_reuse (loop, refs, no_other_refs);
>
> static void
> determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
> ? ? ? ? ? ? ? ? ? ? ? ? ? bool no_other_refs)
> {
> ...
> ?if (loop->inner)
> ? ?return;
> ...
> ?/* Find the outermost loop of the loop nest of loop (we require that
> ? ? there are no sibling loops inside the nest). ?*/
> ?nest = loop;
> ?while (1)
> ? ?{
> ? ? ?aloop = loop_outer (nest);
>
> ? ? ?if (aloop == current_loops->tree_root
> ? ? ? ? ?|| aloop->inner->next)
> ? ? ? ?break;
>
> ? ? ?nest = aloop;
> ? ?}
> ...
> ?compute_all_dependences (datarefs, &dependences, vloops, true);
>
>
> In fact you should iterate _only_ over innermost loops like
>
> ?FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
>
> does that make a difference?
>
>>
>> The patch passed Bootstrapping and regression tests.
>>
>> Is this patch OK to commit?
>
> Ok.
>

Committed r161728