llvm dev - Jul 2016 - [GSoC 2016] Enabling Polyhedral Optimizations in Julia - Midterm Report

Dear Community,

in an earlier post, students working on LLVM were asked to provide a short 
report on
their GSoC project. in the following I want to give an overview on the 
current status of my
GSoC project and outline my next planned activities. Since my mentoring 
organization is Julia,
I also send this to the according mailing list.

*1. Activities so far:*

As described in my proposal [1], I am working on making available Polly's 
optimizations on Julia.
Within the pull-requests [2] and [3] I integrated Polly into Julia's 
LLVM-based JIT infrastructure.
Polly can now be explicitly used to optimize Julia functions that are 
annotated with the newly
introduced `@polly` macro. You may also read my blog post [4] on this 
topic, which illustrates how
these new features can be used in Julia. In a next step I used first micro 
benchmarks to analyze
the LLVM code that Julia produces internally and tried to determine 
characteristics of the produced
code that prevents Polly from applying its optimizations. For a more 
comprehensive evaluation,
I ported the PolyBench benchmark suite to Julia. My recent blog post [5] 
provides more details on this.

These benchmarks helped to identify Julia constructs which hinder Polly's 
SCoP detection. `for`-loops
for which both the lower and the upper bound are parametric are lowered to 
LLVM code that restrain
ScalarEvolution analysis and has been discussed in the bug report at [6]. 
It was possible to solve
this problem and I will shortly supply a patch for this. Another language 
construct that is lowered to
LLVM IR that limits the optimization potential are Julia's `StepRange`s. 
More concretely, this regards
loops of the form `for i = lower_bound:step:upper_bound`. They will prevent 
optimizations especially
when occurring inside other loops.

*2. Next steps:*

It is planned to complete the analysis of Polly on Julia code on the 
existing benchmarks and solve the
problems mentioned above. Furthermore, I plan to extend the analysis to 
find critical code
parts. Therefore I plan to use computation kernels from Julia's base 
library to detect further regions that
cause Polly to fail to perform optimizations.

When the necessary corrections make it possible to apply Polly to a 
reasonably large amount of Julia
programs it is furthermore planned to enhance Polly's 
bound-check-elimination to work in Julia. So far
it is only possible to optimize Julia code that does not contain 
bound-checks, that means currently they
have to be turned off explicitly (either through the `@inbounds` macro or 
via Julia's `--check-bounds=no`
command-line switch). The aim is to be able to use Polly in the presence of 
Julia's bound-checks.

Best regards,
Matthias

[1] 
https://docs.google.com/document/d/1s5mmSW965qmOEbHiM3O4XFz-Vd7cy9TxX9RQaTK_SQo/edit?usp=sharing
[2] https://github.com/JuliaLang/julia/pull/16531
[3] https://github.com/JuliaLang/julia/pull/16726
[4] http://www.mreisinger.com/?p=43
[5] http://www.mreisinger.com/?p=137
[6] https://llvm.org/bugs/show_bug.cgi?id=28126
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160621/d03c63a1/attachment-0001.html>

On Wed, Jun 22, 2016, at 02:15 AM, Matthias Reisinger via llvm-dev
wrote:
> Dear Community,
Hi Matthias,

thank you a lot for this update!
 
> in an earlier post, students working on LLVM were asked to provide a
> short 
> report on
> their GSoC project. in the following I want to give an overview on the 
> current status of my
> GSoC project and outline my next planned activities. Since my mentoring 
> organization is Julia,
> I also send this to the according mailing list.
> 
> *1. Activities so far:*
> 
> As described in my proposal [1], I am working on making available
Polly's
> optimizations on Julia.
> Within the pull-requests [2] and [3] I integrated Polly into Julia's 
> LLVM-based JIT infrastructure.
> Polly can now be explicitly used to optimize Julia functions that are 
> annotated with the newly
> introduced `@polly` macro. You may also read my blog post [4] on this 
> topic, which illustrates how
> these new features can be used in Julia. In a next step I used first
> micro 
> benchmarks to analyze
> the LLVM code that Julia produces internally and tried to determine 
> characteristics of the produced
> code that prevents Polly from applying its optimizations. For a more 
> comprehensive evaluation,
> I ported the PolyBench benchmark suite to Julia. My recent blog post [5] 
> provides more details on this.
> 
> These benchmarks helped to identify Julia constructs which hinder
Polly's
> SCoP detection. `for`-loops
> for which both the lower and the upper bound are parametric are lowered
> to 
> LLVM code that restrain
> ScalarEvolution analysis and has been discussed in the bug report at [6]. 
> It was possible to solve
> this problem and I will shortly supply a patch for this. Another language 
> construct that is lowered to
> LLVM IR that limits the optimization potential are Julia's
`StepRange`s.
> More concretely, this regards
> loops of the form `for i = lower_bound:step:upper_bound`. They will
> prevent 
> optimizations especially
> when occurring inside other loops.
Very good work indeed! Thanks for upstreaming the first patches and for
tracking down all the mismatches that today make optimizations more
difficult than necessary! It seems -- despite it certainly requiring
effort -- most of the changes look tracktable. Looking forward to see
them resolved one-by-one.

Also, thank you for writing a PollyBench-Julia version. This is indeed a
great tool to test your work and
obviously gives some nice data to talk about in your blog post.

Best,
Tobias

I am looking forward to trying this out when it is ready!

-viral

On Wednesday, June 22, 2016 at 7:39:54 AM UTC-7, Tobias Grosser
wrote:
>
> On Wed, Jun 22, 2016, at 02:15 AM, Matthias Reisinger via llvm-dev 
> wrote: 
> > Dear Community, 
>
> Hi Matthias, 
>
> thank you a lot for this update! 
>   
> > in an earlier post, students working on LLVM were asked to provide a 
> > short 
> > report on 
> > their GSoC project. in the following I want to give an overview on the
> > current status of my 
> > GSoC project and outline my next planned activities. Since my
mentoring
> > organization is Julia, 
> > I also send this to the according mailing list. 
> > 
> > *1. Activities so far:* 
> > 
> > As described in my proposal [1], I am working on making available 
> Polly's 
> > optimizations on Julia. 
> > Within the pull-requests [2] and [3] I integrated Polly into
Julia's
> > LLVM-based JIT infrastructure. 
> > Polly can now be explicitly used to optimize Julia functions that are 
> > annotated with the newly 
> > introduced `@polly` macro. You may also read my blog post [4] on this 
> > topic, which illustrates how 
> > these new features can be used in Julia. In a next step I used first 
> > micro 
> > benchmarks to analyze 
> > the LLVM code that Julia produces internally and tried to determine 
> > characteristics of the produced 
> > code that prevents Polly from applying its optimizations. For a more 
> > comprehensive evaluation, 
> > I ported the PolyBench benchmark suite to Julia. My recent blog post
[5]
> > provides more details on this. 
> > 
> > These benchmarks helped to identify Julia constructs which hinder 
> Polly's 
> > SCoP detection. `for`-loops 
> > for which both the lower and the upper bound are parametric are
lowered
> > to 
> > LLVM code that restrain 
> > ScalarEvolution analysis and has been discussed in the bug report at 
> [6]. 
> > It was possible to solve 
> > this problem and I will shortly supply a patch for this. Another 
> language 
> > construct that is lowered to 
> > LLVM IR that limits the optimization potential are Julia's
`StepRange`s.
> > More concretely, this regards 
> > loops of the form `for i = lower_bound:step:upper_bound`. They will 
> > prevent 
> > optimizations especially 
> > when occurring inside other loops. 
>
> Very good work indeed! Thanks for upstreaming the first patches and for 
> tracking down all the mismatches that today make optimizations more 
> difficult than necessary! It seems -- despite it certainly requiring 
> effort -- most of the changes look tracktable. Looking forward to see 
> them resolved one-by-one. 
>
> Also, thank you for writing a PollyBench-Julia version. This is indeed a 
> great tool to test your work and 
> obviously gives some nice data to talk about in your blog post. 
>
> Best, 
> Tobias 
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160709/d8308b06/attachment.html>