JuliaLang/julia — pull request #5355 by ArchRobison (2014-01-10 23:34:29+00:00)
Title: WIP: Add support for @simd 

This pull request enables the LLVM loop vectorizer. It's not quite ready for production. I'd like feedback and help fixing some issues. The overall design is explained in [this comment](https://github.com/JuliaLang/julia/issues/4786#issuecomment-31050948) to issue #4786, except that it no longer relies on the "banana interface"mentioned in that comment.

Here is an example that it can vectorize when ```a``` is of type ```Float32```, and ```x``` and ```y``` are of type ```Array{Float32,1}```:
```
function saxpy( a, x, y )
@simd for i=1:length(x)
@inbounds y[i] = y[i]+a*x[i];
end
end
```
I've seen the vectorized version run 3x faster than the unvectorized version when data fits in cache. When AVX can be enabled, the results are likely even better.

Programmers can put the ```@simd``` macro in front of one-dimensional ```for``` loops that have ranges of the form _m_:_n_ and the type of the loop index supports ```<``` and ```+````. The decoration is guaranteeing that the loop does _not_ rely on wrap-around behavior and the loop iterations are safe to execute in parallel, even if chunks are done in lockstep.

The patch implements [type-based alias analysis](http://llvm.org/docs/LangRef.html#tbaa-metadata) , which may help LLVM optimize better in general, and is essential for vectorization. The name "type-based alias analysis" is a bit of a misnomer, since it's really based on hierarchically partitioning memory. I've implemented it for Julia assuming that type-punning is never done for parts of data structures that users cannot access directly, but that user data can be type-punned freely.

Problems that I seek advice on:
* The ```@simd``` macro is not found. Currently I have to do the following within the REPL:
```
include("base/simdloop.jl")
using SimdLoop.@simd
```
I tried to copy the way```@printf``` is defined/exported, but something is wrong with my patch. What?
* LLVM 3.3 disallows attaching metadata to a block, so I've attached it to an instruction in the block. It's kind of ad-hoc, but seems to work. Is there a better way to do it?
* An alternative to attaching metadata is to eliminate ```src/llvm-simdloop.cpp``` and instead rely on LLVM's auto-vectorization capability, which inserts memory dependence tests. That indeed does work for the ```saxpy``` example above, i.e. it vectorizes *without* the support ```src/llvm-simdloop.cpp```. However, ```@simd``` would still be necessary to tranform the loop into a form such that LLVM can compute a trip count.
* An alternative to the trip-count issue is to eliminate ```@simd``` altogether and instead somehow ensure that _m_:_n_ is lowered to a form for which LLVM can compute a trip count.
* I'm a neophyte at writing macros, ```base/simdloop.jl``` could use a review by an expert.

Apologies for the useless comment:
```
This file defines two entry points:
```
I just noticed it, but being late on a Friday, I'll fix it later. It's supposed to say that one entry point is for marking simd loops and the other is for later lowering marked loops.

Thanks to @simonster for [his information](https://github.com/JuliaLang/julia/pull/3929) on enabling the loop vectorizer. It was a big help to get me going.