Vectorization in Rust: November 2 status report

Vectorization in Rust: 11/2 status report

Since the last status report

We've tweaked the expr_for AST node to accept an additional parameter for vectorization and added support to the parser for a vfor language form. These changes have been threaded through all of the places the AST is used. Currently, the flag is ignored when it gets to the translation pass.

Changes from mainline Rust can be seen by looking at a compare view: https://github.com/lkuper/rust/compare/master...vectorization

Our first "fantasy land" program that uses vfor (https://github.com/lkuper/rust/blob/f34edc8b96272686eafc2c89e2481a27ee7cd059/src/test/run-pass/vectorization-01.rs) compiles and runs fine, but now that we're trying to write code with it, we're having second thoughts about vfor. The vectorization literature says that a vectorizable loop is something like (in Fortran 77, from the book that Arun suggested, [Optimizing Compilers for Modern Architectures][http://www.amazon.com/Optimizing-Compilers-Modern-Architectures-Dependence-based/dp/1558602860], by Allen and Kennedy):

DO I = 1, 64
   C(I) = A(I) * B(I)
ENDDO

But in Rust, if you wanted to iterate over a vector using indices, you wouldn't use for. A for loop is for times when you don't want to bother with indices, like (example from the Rust tutorial):

for elt in ["red", "green", "blue"] {
    std::io::println(elt);
}

If you really needed indices, you'd typically do something like this, using the built-in uint::range function from the standard library and Rust's syntax for blocks, which are a kind of closure:

// Standard vectorizable example
range(0u, 64u, {|i| C[i] = A[i] + B[i]});

Incidentally, Rust also supports this equivalent syntax:

range(0u, 64u) {|i|
    C[i] = A[i] + B[i];
}

So, are there standard vectorization examples that we should be looking at that don't involve loop indices?

What to do next

One thing we haven't done yet is actually generate any vector instructions. That's the next step. Then, to actually do vectorization, Allen and Kennedy suggest that we need to do some kind of data dependence analysis to determine what loops can be vectorized. But how do we reason about this in the presence of loops that don't use indices? Are we going after the wrong thing? Talking with Arun and asking more questions on the Rust mailing list might help.