[llvm-dev] On Loop Distribution pass

[Adam Nemet via llvm-dev]

> On Oct 10, 2016, at 2:53 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> 
> From: "Adam Nemet" <anemet at apple.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Dangeti Tharun kumar" <cs15mtech11002 at iith.ac.in>, "Santanu Das" <cs15mtech11018 at iith.ac.in>, llvm-dev at lists.llvm.org
> Sent: Monday, October 10, 2016 4:52:18 PM
> Subject: Re: [llvm-dev] On Loop Distribution pass
> 
> 
> On Oct 10, 2016, at 2:50 PM, Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at anl.gov>> wrote:
> 
> 
> From: "Dangeti Tharun kumar via llvm-dev" <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
> To: llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> Cc: "Santanu Das" <cs15mtech11018 at iith.ac.in <mailto:cs15mtech11018 at iith.ac.in>>
> Sent: Sunday, October 9, 2016 12:09:01 PM
> Subject: [llvm-dev] On Loop Distribution pass
> 
> Dear community,
> 
> Our team at IITH have been experimenting with loop-distribution pass in LLVM. We see the following results on few benchmarks.
> 
> clang -O3 -mllvm -enable-loop-distribute -Rpass=loop-distribute file.c
> clang -O3 -mllvm -enable-loop-distribute -Rpass-analysis=loop-distribute file.c
> 
> 
> TORCH <http://crd.lbl.gov/departments/computer-science/PAR/research/previous-projects/torch-testbed/>:
> There are nearly 488 loops in this benchmark. LLVM was not able to distribute any loop.
> 
> TSVC <https://github.com/shantanuatiith/TSVC_>:
> There are 151 loops coded in plain ‘C’, none of them got distributed. TSVC has particularly candidates valid for distribution like the one below. The inner loop in this example can be distributed.
> 
> for (int nl = 0; nl < ntimes/2; nl++) {
> for (int i = 1; i < LEN; i++) {
> a[i] += c[i] * d[i];
> b[i] = b[i - 1] + a[i] + d[i];
> }

There are two problems why we can’t currently distribute this:

1. Load-PRE in GVN replaces the b[i-1] with the value from the previous iterations.

This is the reason that we no longer see the backward dependence and report the above message.  The plan is to disable *loop* Load-PRE  in GVN and have LoopLoadElimination handle this which is run after LoopDist.  Unfortunately even with disabling load-pre in GVN we have this:

2. We can’t currently duplicate load operations across the resulting loops (a[I] and d[I] in the loop above). 

This constraint had to do with the limitation in the dependence analysis (LAA) at the time.  This is no longer a problem because we now represent all dependences in the loop thus we don't need to preserve the original program order of the memory accesses.

Adam
> dummy(a, b, c, d, e, aa, bb, cc, 0.);
>  }
> 
>      MiBench <http://vhosts.eecs.umich.edu/mibench//>:
> There are 6539 loops in MiBench. None of the loops were distributed by the loop-distribution pass of LLVM.
> 
>      CoMD <https://github.com/exmatex/CoMD>:
> CoMD is a reference implementation of typical classical molecular dynamics algorithms and workloads.
> Out of 112 loops none of them are distributed.
> 
> 
> For the specific loop I have shown above which is straight forward a good distribution candidate, the remark is "loop not distributed: memory operations are safe for vectorization [-Rpass-analysis=loop-distribute]". 
> 
> Can someone reason these results and this remark?
> 
> The current loop distribution implementation is focused on enabling vectorization. The comment at the top of the file says:
> 
>   // This file implements the Loop Distribution Pass.  Its main focus is to
>   // distribute loops that cannot be vectorized due to dependence cycles.  It
>   // tries to isolate the offending dependences into a new loop allowing
>   // vectorization of the remaining parts.
> 
> Hopefully, this helps explain the diagnostic. Regarding why the loop you highlight is not distributed to enable the vectorization of the a[i] update, I don't know. Adam?
> 
> Yeah, it’s not immediate clear to me why we’re not distributing that.  I think it’s s221() from TSVC.  I will take a look later.
> Yes, it looks like s221.
> 
>  -Hal
> 
> Adam
> 
> 
>  -Hal
> 
> I humbly request the community to correct me, if am missing something in my analysis.
> 
> -- 
> Thank you
> D Tharun kumar
> CS15MTECH11002
> 9948373970
> CSE-IITH
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> 
> -- 
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
> 
> 
> 
> 
> -- 
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161011/4fbb8865/attachment.html>