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

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

On Wed, Jun 30, 2010 at 8:10 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Wed, Jun 30, 2010 at 13:05, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Wed, Jun 30, 2010 at 8:01 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
>>> Hi,
>>>
>>>> On Wed, Jun 30, 2010 at 7:34 PM, Fang, Changpeng <Changpeng.Fang@amd.com> wrote:
>>>> >> FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
>>>> >
>>>> >>does that make a difference?
>>>> >
>>>> > This doesn't help, because "compute_all_dependences" was called the same number of time
>>>> > as before.
>>>> >
>>>> > (BTW, should we limit prefetching only to the innermost one?)
>>>> >
>>>> > In this test case, there are 6 large loops, where each loop has 729 memory reference.
>>>> > It takes 4~5 seconds to "compute_all_dependence" for one such loop.
>>>>
>>>> It shouldn't take that long. ?Can you gather a more detailed profile?
>>>
>>> actually, compute_all_dependences is quadratic in the number of memory
>>> references, and in more complicated cases, it can perform rather complex
>>> computations, so 5 seconds on 729 references does seem like a realistic time.
>>> Of course, we need to either speed up the analysis or add an cut-off to avoid
>>> it on loops with too many memory references (or both),
>>
>> Well, but at -O3 the vectorizer computes dependences as well, and it
>> doesn't take that much of time, ?So there must be something obvious
>> going wrong.
>>
>
> The dependence analysis in the vectorizer is done only in the innermost
> loop that is vectorized, whereas prefetch does the analysis of data deps
> for every loop.

The vectorizer also does dependence analysis for outer-loop vectorization.
I guess prefetch analysis should restrict itself to data dependences on a
maximum loop nest depth (of say 2 or 3).

Still dependence analysis looks overly costly here.

Richard.

> Sebastian
>