[LLVMdev] [Polly] Summary of some expensive compiler passes, especially PollyDependence

[Tobias Grosser]

On 08/08/2013 06:27 PM, Star Tan wrote:
> At 2013-08-08 22:28:33,"Tobias Grosser" <tobias at grosser.es> wrote:
>> On 08/08/2013 01:29 AM, Star Tan wrote:
>>> Hi all,
>>>
>>>
>>> I have summarized the top 10 compiler passes for Polly when compiling LLVM test-ssuite. Results can be viewed on:
>>>       https://gist.github.com/tanstar/581bcea1e4e03498f935/raw/f6a4ec4e8565f7a7bbdb924cd59fcf145caac039/Polly-top10
>>>
>>>
>>> Based on the comparison between "clang -O3" and "polly -O3" listed on:
>>>       http://188.40.87.11:8000/db_default/v4/nts/18?compare_to=14&baseline=14
>>
>> Please compare against clang -O3 -load LLVMPolly.so, otherwise
>> especially the compile time of the small binaries includes the overhead
>> of loading the Polly shared object file.
>
> In fact, the compile-time overhead of loading Polly shared object file is very small (usually less than 1%). Their overhead can be viewed on:
>      http://188.40.87.11:8000/db_default/v4/nts/15?compare_to=14&baseline=14

I see. Still, I think we should eliminate to remove another source of noise.

>>> diff --git a/lib/Analysis/Dependences.cpp b/lib/Analysis/Dependences.cpp index 9f918f3..39c3fb6 100644 --- a/lib/Analysis/Dependences.cpp +++ b/lib/Analysis/Dependences.cpp @@ -95,6 +95,10 @@ void Dependences::calculateDependences(Scop &S) { collectInfo(S, &Read, &Write, &MayWrite, &Schedule); + Read = isl_union_map_coalesce(Read); + Write = isl_union_map_coalesce(Write); + MayWrite = isl_union_map_coalesce(MayWrite); + DEBUG(dbgs() << "Read: " << Read << "\n"
>>
>> This patch is unreadable in the mail. However, the one you submitted
>> looked good and was committed.
>>
>>> With this patch file, we can reduce the compile-time percentage of PollyDependence from 98.5% to 15.3%. Unfortunately, the compile-time percentage of PollyDependence for benchmarks, such as "nestedloop", is still very high.
>>
>> It would be good to get an up-to-date comparison with the latest patch
>> having gone into Polly.
>
> Yes, you can view the comparison on:
>      http://188.40.87.11:8000/db_default/v4/nts/26?compare_to=25&baseline=25

I am slightly confused. What are we comparing here? It seems we compare 
a PollyScopInfo run with a PollyDependences run (same source code?) and 
the Dependences run shows compile time speedup over ScopInfo? This is 
surprising.

The numbers rather suggest that those are two Dependences runs the first 
without the patch applied the second with. If this is the case,
why does the page say "*** WARNING ***: comparison is against a 
different machine (pollyScopInfo__clang_DEV__x86_64,11)"?

> Results show that this patch file is very effective for several benchmarks, such as salsa20 (reduced by 97.72%), Obsequi (54.62%), seidel-2d (48.64%), telecomm-gsm (33.71%).
>
>> I did not yet look at the nestedloop benchmark, but it sounds basically
>> like a benchmark only consisting of loop nests that we can optimise.
>> This is definitely interesting to look into. Both in respect of how fast
>> we can analyse it faster, but also if we are able to improve the
>> performance of the generated code. Especially if we improve the
>> execution performance some additional compile time is justified.
>
> Yes. nestedloop.c is a very simple benchmark that contains a single nested loop as follows:
>      int n = ((argc == 2) ? atoi(argv[1]) : LENGTH);
>      int a, b, c, d, e, f, x=0;
>      for (a=0; a<n; a++)
>          for (b=0; b<n; b++)
>              for (c=0; c<n; c++)
>                  for (d=0; d<n; d++)
>                      for (e=0; e<n; e++)
>                          for (f=0; f<n; f++)
>                              x++;
> Polly would significantly increases the compile-time from 0.0320s to 2.3320 (70x), but it also reduces the execution time from 0.048s to 0.004s (12x). Maybe it is worth, but I think that would be eif we can reduce the compile-time without hurting the execution performance.

Sure. Any ideas what is going on here? It seems you have a couple of 
open problems. It probably makes sense to open a bug report for each of 
them and attach source code as well as your findings there.

Cheers,
Tobias