[PATCH][RFC] middle-end array expressions (II)

[Richard Guenther <rguenther at suse dot de>]

This is the final proposal for the introduction of arrays as first
class citizens of the middle-end.  The goal is still to retain
the high-level information that the GFortran frontend has for array
assignments up to the high-level loop optimization passses and to
not lower Fortran array assignments in the frontend.

After several tries I settled on the following scheme (explained in
detail in a paper for the GCC Summit this year).

Whole-array loads and stores to gimple array registers (that will be
put in SSA form) are done via a new variable length tree code that
contains array extents and strides as operands (thus it properly
lowers VLA objects to gimple).  (VLA_VIEW_EXPR)

Expressions operating on gimple array registers are doing so by
means of operating on scalar placeholders, "indexed" array registers,
that are just scalar results of a new indexing operation (VLA_IDX_EXPR).
Results of these expressions are put back into array registers
by doing a reverse transformation (VLA_RIDX_EXPR).

To represent reductions VLA_DELTA_EXPR implements contraction of
dimensions by iterating and summing over all values of certain indices.

Usually examples are more useful than words (and I didn't want to repeat
the whole paper here), so the following GIMPLE would compute the
matrix product of two n x n matrices A and B (pointed to by a and b)
and stores it into C.

  float A[n][n] = VLA(_VIEW_EXPR) <n, 1, n, n> (*a);
  float B[n][n] = VLA <n, 1, n, n> (*b);
  float Aik = VLA_IDX(_EXPR) <i, k> (A);
  float Bkj = VLA_IDX <k, j> (B);
  float tmp = Aik * Bkj;
  float Cij = VLA_DELTA(_EXPR) <n, k> (tmp);
  float C[n][n] = VLA_RIDX(_EXPR) <i, j> (Cij);
  VLA <n, 1, n, n> (*c) = C;

More usual Fortran expressions like

  A(2:n-1) = B(1:n-2) + B(3:n)

would look like

  float Btmp[n] = VLA <n, 1> (B);
  float B1 = VLA_IDX <i> (Btmp);
  float B2 = VLA_IDX <i+2> (Btmp);
  float tmp = B1 + B2;
  float Atmp = VLA_RIDX <i> (tmp);
  VLA <n-2, 1> (A) = Atmp;

The patch below doesn't touch the Fortran frontend but implements a
(hacky) interface to C and C++ using builtins with covariant return types
(see the testsuite entries to get an idea how they work).  It also
implements a lowering pass that turns the array expressions back to
loops.  It doesn't work at -O0 (because we're not in SSA form there)
and I expect the lowering to be done by GRAPHITE in the end, not by
a separate lowering pass.

Now, I'm open to questions and I'll send the paper to anyone that
wants it (but I gues I'm not supposed to put it somewhere public
before the summit?).

Please re-direct followups to gcc/gcc-patches according to subject.

Thanks,
Richard.

Attachment: middle-end-arrays-SSA.gz
Description: GNU Zip compressed data