civicaml/phases/desug.mli

(** Desugaring: split variable initialisations, generate array dimension
    variables, and transform for-loops to while-loops. *)

(** {2 Split variable initialisations}

    Variable initialisations are split into declarations and assignments, to
    generalize the AST format. This makes context analysis easier, since
    initialisations need not be considered. The assignments are placed in the
    function body, after local fuction declarations (which are not in the
    example below). Initialisations fo global variables are moved to a new
    function called "__init", which is a reserved function that is called by the
    VM before the main function is called.

{v int glob = 1;
void foo() \{
  int foo = 0;
  int bar = foo;
\} v}
    becomes:
{v export void __init() \{
    glob = 1;
\}
int glob;
void foo() \{
  int foo;
  int bar;
  foo = 0;
  bar = foo;
\} v}

    {3 Array initialisations}

    A more complex class of initialisations is that of array initialisations.
    Arrays can be initialised to a scalar value or to an array literal in
    bracket notation. A scalar value is rewritten to a nested for-loop over all
    array dmensions, with an assignment in the most nested loop. An array
    constant is rewritten to a series of separate assign statements to the
    corresponding array indices. The following example shows both
    transformations:
{v void foo() \{
    int[3] a = 4;
    int[2, 2] b = [[3, 4], [5, 6]];
\} v}

    This is transformed into:

{v void foo() \{
    int[3] a;
    int[2, 2] b;
    a = __allocate(3);
    for (int i = 0, 3) \{
        a[i] = 4;
    \}
    b = __allocate(2, 2);
    b[0, 0] = 1;
    b[0, 1] = 2;
    b[1, 0] = 3;
    b[1, 1] = 4;
\} v}

    Actually, the dimensions of [a] and [b] should have been replaced by new
    variables earlier for reasons described below, but this is not done in the
    example to maintain readability.

    Note that array constants in bracket expressions must have a nesting level
    that is equal to the number of array dimensions, else an error will occur.

    {2 Move array dimensions and scalars into new variables}

    In the following code:
{v int twos = 0;
int two() \{
  twos = twos + 1;
  return 2;
\}
void foo() \{
  int[2, two()] a = two();
  printInt(twos);
  printInt(a[1, 1]);
\} v}

    [two()] must be evaluated exactly twice in order to preserve correct
    behaviour. However, the scalar inialisation will be transformed into a
    for-loop, evaluating [two()] in each loop iteration. Moreover, [a[1, 1]]
    would at a later stage (during array dimension reduction) be transformed
    into [a[(1 * two()) + 1]], thus incorrectly evaluating [two()] an additional
    time.

    The problem is solved by generating new variables for scalar initialisations
    and array dimensions, and replacing the original expression with the
    generated variables. Note that these variables are marked so-called
    "constant variables" since they are known to be assigned exactly once, and
    thus likely optimizable by {!Constprop}. This way, only the non-constant
    expressions are defined in new variables in the final code.

    In the example above, [int[2, two()] a = two();] is transformed as follows:
{v     ...
    int _a_0_ = 2;  // 2 will be propagated back by constant propagation
    int _a_1_ = two();
    int _scalar_1_ = two();
    int[_a_0_, _a_1_] a = _scalar_1_;
    ...  v}
resulting in:
{v     ...
    int _a_0_;
    int _a_1_;
    int _scalar_1_;
    int[_a_0_, _a_1_] a;
    _a_0_ = 2;
    _a_1_ = two();
    _scalar_1_ = two();
    a := <allocate>(_a_0_, _a_1_);
    for (int _i_2 = 0, _a_0_) \{
        for (int _i_3 = 0, _a_1_) \{
            a[_i_2, _i_3] = _scalar_1_;
        \}
    \}
    ...  v}

    The transformation described above is applied to all array definitions,
    including extern arrays. Although dimensions of extern arrays are not
    expressions (but identifiers), the transformation is necessary in order to
    generate consistent names to be imported/exported. E.g. in [extern int[n]
    a], [n] is just a name given locally to the first dimension of [a].
    Therefore it is transformed into:
{v     extern int _a_0_;
    extern int[_a_0_] a; v}
    Also, all occurrences of [n] in the rest of the module are replaced by
    [_a_0_]. For exported arrays, the generated dimension variables need to be
    exported as well.

    {2 Transforming for-loops to while-loops}

{v for (int i = <start>, <stop>, <step>) \{
    <body>
\} v}

    is transformed into:

{v _i_1 = <start>;
_step_2 = <step>;
_stop_3 = <stop>;
while ((_step_2 > 0) ? (_i_1 < _stop_3) : (_i_1 > _stop_3)) \{
    <body>
    _i_1 = _i_1 + _step_2;
\} v}

    Here, [_i_1], [_step_2] and [_stop_3] are fresh variables. Definitions of
    these new variables are added to the scope of the current function. Every
    occurrence of [i] in [<body>] is replaced with the fresh variable [_i_1],
    this prevents problems with nested for-loops that use the same induction
    variable.
    *)

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