JuliaLang/julia — pull request #3929 by simonster (2013-08-03 21:08:17+00:00)
Title: WIP: Enable LLVM loop vectorizer

While there's been some discussion of adding SIMD types in #2299, I thought it might be fun to see how well the LLVM loop vectorizer can do with Julia code. This PR compiles, runs, and vectorizes things ([sample](https://gist.github.com/simonster/6147815)), but there are two very big problems with it.

The first issue is that this PR turns all integer `add` operations into `add nsw` in order to get that proof of concept to work. Scalar evolution analysis requires that add/subtract operations on the loop index produce undefined behavior on overflow, but to change this generally might be too unsafe for a high-level language. Since we should be able to guarantee that the `next()` operation on a `Range`/`Range1` doesn't overflow, one option is to add `nsw` intrinsics and use those.

The second issue is that this PR turns `jl_value_t` into `int8*`. Not only does this seem very wrong, it also breaks building `sys.jl`, although Julia seems to run fine with a sys.jl built without this change. Unfortunately, I haven't been able to get the loop vectorizer to work with `jl_value_t` as a structure type. With this change, the IR going into the loop vectorization pass looks like [this](https://gist.github.com/simonster/6147959), whereas without it, the IR looks like [this](https://gist.github.com/simonster/6147965). Notice that, with `jl_value_t` as `i8*`, the bitcast is outside of the loop, whereas with `jl_value_t` as a structure type, it is inside the loop. This seems to bother the loop vectorizer, which tells me:

```
LV: Found a loop: if
LV: Found an induction variable.
LV: Found a runtime check ptr: %7 = bitcast %jl_value_t* %6 to double*, !dbg !3370
LV: Found a runtime check ptr: %7 = bitcast %jl_value_t* %6 to double*, !dbg !3370
LV: We need to compare 1 ptrs.
LV: We can perform a memory runtime check if needed.
LV: Found an unidentified write ptr: %4 = load %jl_value_t** %3, align 8, !dbg !3369
LV: Adding Underlying value: %4 = load %jl_value_t** %3, align 8, !dbg !3369
LV: Found an unidentified read ptr: %4 = load %jl_value_t** %3, align 8, !dbg !3369
LV: Found a possible write-write reorder: %4 = load %jl_value_t** %3, align 8, !dbg !3369
LV: Can't vectorize due to memory conflicts
LV: Not vectorizing.
```

If I move the bitcast out of the loop manually and compile the IR manually with `opt`, it seems to work, but I'm a little confused about what makes these cases different.