civicaml/phases/dimreduce.mli

(** Dimension reduction: transform multi-dimensional arrays to one-dimensional
    arrays, and pass original array dimensions in function calls. *)

(**
    This phase lowers multi-dimensional arrays to one-dimensional arrays. This
    transformation is done in two steps.

    In the first step, function calls and function parameter lists are modified.
    For function calls, array dimensions are passed as explicit arguments before
    the array argument itself. Naturally, function declarations need to be
    modified accordingly, adding explicit parameters for array dimensions.
    Similarly, dimensions of imported arrays are moved into new integer
    variables.

    In the second step, statements and expressions involving multi-dimensional
    array referencing are transformed such that they reference a one-dimensional
    array. Variable declarations with type [ArrayDims] are transformed into
    variables of type [Array], thus removing the dimensionality information.
    Allocation statements become one-dimensional allocations with a length that
    is the product of all array dimensions. Indexing multi-dimensional arrays is
    changed such that arrays are accessed in row-major order.

    Original code ([x], [y] and [z] are defined elsewhere):

{v extern int[u] ext;

void foo(int[a, b, c] p) \{
    int[5, 10, 3] q;
    q[x, y, z] = p[x, y, z];
    foo(q);
\} v}

    Input for dimension reduction (we use [n], [m] and [k] for readability but
    in reality these are generated variables):

{v extern int[__ext_0] ext;  // dimensions are encoded in type

void foo(int[a, b, c] p) \{
    int n; int m; int k; int[n, m, k] q;  // n, m, k are added during desugaring
    n = 5;
    m = 10;
    k = 3;
    q = __allocate(n, m, k);
    q[x, y, z] = p[x, y, z];
    foo(q);
\} v}

    step 1:

{v extern int __ext_0;  // imported dimensions moved to new variables
extern int[__ext_0] ext;

void foo(int a, int b, int c, int[a, b, c] p) \{  // array parameter
    int n; int m; int k; int[n, m, k] q;
    n = 5;
    m = 10;
    k = 3;
    q = __allocate(n, m, k);
    q[x, y, z] = p[x, y, z];
    foo(n, m, k, q);                      // array argument
\} v}

    step 2:

{v extern int __ext_0;
extern int[] ext;                  // removing dimension information

void foo(int a, int b, int c, int[] p) \{
    int n; int m; int k; int[] q;  // removing dimension information
    n = 5;
    m = 10;
    k = 3;
    q = __allocate(n * m * k);                            // allocation
    q[((x * m) + y) * k + z] = p[((x * b) + y) * c + z];  // indexing
    foo(n, m, k, q);
\} v}

    Note that when array dimensions are constant integer values, an array index
    may be simplified to a single constant value during contant propagation.
    *)


(** Main phase function, called by {!Main}. *)
val phase : Main.phase_func