Goals

When I got out of grad school in '92, I went to work for Tera Computer. Besides the interesting hardware, they had this great compiler, written mostly by David Callahan and Brian Koblenz. It had front ends for Fortran, C, and C++ from Edison Design Group, but the rest of it was written from scratch. In addition to the ordinary optimizations, they had good dependence analysis (along with directives) and a herd of xforms: parallelization (including reductions and recurrences), loop collapse, loop fusion, loop distribution, loop interchange, scalar expansion, scalar replacement, unroll and jam, etc, plus a nice tool to help show what had been done.

It was great. People always say that automatic parallelization doesn't work on dusty decks, but I think they miss the point. When we write programs for a parallel machine, it's quite delightful to have a compiler to do the heavy lifting. (Alternatively, we might say that it's pathetic that people are still having to manually parallelize recurrences.) I used the Tera compiler for several years back when and I've started using it again - it's still great.

Unfortunately, the Tera compiler is not open source and it doesn't target a popular machine. So we naturally think: Let's recreate it, somehow, to support our architectural research. After some review of the alternatives, it appears that LLVM is the best vehicle for our effort.

So, a big job, best broken into small steps... For a first step, I'd like to build a dependence analyzer, working over complete functions (not just loops) to build a set of dependence edges connecting array references, a dependence graph. Edges would include annotations for type (flow, anti, output), loop-carried/loop-independent, along with direction vectors (and distances when available).

Just building the dependence graph is a big job. I'm looking at the problem in two parts: 

  1. A dependence test that, given two memory references, decides if a dependence exists between them, and
  2. The dependence-graph builder that looks over the complete function and finds pairs of memory references to pass to the dependence test, using the results to build a dependence graph, with edges labeled as to the kind of dependence and direction vectors.

The implementation of the dependence test is done; the LLVM review process is underway. The design of the dependence-graph builder is complete; I'll start on the implementation soon.