JuliaLang/julia — pull request #6271 by ArchRobison (2014-03-26 21:52:17+00:00)
Title: WIP: Enable SLPVectorizer and make it work for tuples

This pull request enables implicit vectorization of tuple math idioms. I consider it not quite yet ready for production because it slows down compilation. End of note has measurements.

The changes comprise:
* Adding LLVM's [SLPVectorizer](http://llvm.org/docs/Vectorizers.html#the-slp-vectorizer) to the pass list.
* Adding a patch that makes ```SLPVectorizer``` work for tuply idioms of interest.
The changes to LLVM 3.3 were backported from recent changes developed by me for LLVM trunk, which are close to being committed there. The patch includes backported LLVM unit tests.

For background, see Issue #5857 and in particular my [comment](https://github.com/JuliaLang/julia/issues/5857#issuecomment-35784676). Here is an example of what the enhanced SLPVectorizer can do:
```
$ cat foo.jl
function add( a::NTuple{4,Float32}, b::NTuple{4,Float32} )
(a[1]+b[1],a[2]+b[2],a[3]+b[3],a[4]+b[4])
end

function mul( a::NTuple{4,Float32}, b::NTuple{4,Float32} )
(a[1]*b[1],a[2]*b[2],a[3]*b[3],a[4]*b[4])
end

function madd( a::NTuple{4,Float32}, b::NTuple{4,Float32}, c::NTuple{4,Float32} )
add(mul(a,b),c)
end

t = NTuple{4,Float32}

code_llvm(madd,(t,t,t))
$ julia foo.jl

define <4 x float> @julia_madd15575(<4 x float>, <4 x float>, <4 x float>) {
top:
%3 = fmul <4 x float> %0, %1, !dbg !151
%4 = fadd <4 x float> %3, %2, !dbg !151
ret <4 x float> %4, !dbg !151
}
```
Without the patch, the LLVM code for ```madd``` is [lengthy scalar stuff](https://gist.github.com/ArchRobison/9793916#file-gistfile1-txt). Performance improvement for ```madd``` (wrapped in a flogging loop) was about 1.6x, and about 2.9x for an 8-wide variant, on a machine with AVX2.

The compilation time slowdown was disappointing. I measured compilation time via:
```
rm -f usr/lib/julia/sys.*
time make
```
Compared to the Julia master, the time was 1.67x longer. With the LLVM trunk incarnation of the patch, the time was only 1.25x longer, so there's some hope for shrinking the time. Perhaps SLPVectorizer is in need of a fast rejection test.