civicaml/phases/constprop.mli

(** Rudimentary constant propagation and constant folding on generated
    variables. *)

(** The compiler sometimes generates variables of the form [foo$$1], to make
    sure that expressions are only executed once. In many cases, this leads to
    over-complex constructions with more variable definitions den necessary, for
    example when converting for-loops to while-loops. We use the knowledge of
    these variables being only assigned once, by propagating the constant values
    to their occurrences, and then apply arithmetic simplification to operators
    to reduce the size and complexity of the generated code. Note that this can
    only be applied to constants. For variables in general, some form of
    liveness analysis would be required (e.g. first convert to Static Single
    Assignment form). Expressions can only be propagated when they have no side
    effects, i.e. when they do not contain function calls. The current
    implementation only propagates [Bool|Int|Float] constants and simple
    variable uses ([VarUse]).

    Constant propagation is merged with some some arithmetic simplification here,
    specifically targeting optimization oppertunities created bij earlier
    constant propagation. This is utilized, for example, in array index
    calculation when array dimensions are constant.

    The following example demonstrates the effectivity of this phase. An array
    assignment is transformed into a for-loop, which is transformed into a
    while-loop. Note that the condition of the while-loop body is also
    simplified.

{v void foo() \{
    int[2, 2] arr = [[1, 2], 3];
\} v}

After desugaring and array dimension reduction this becomes:

{v void foo() \{
    int i$4$5;
    int stop$$6;
    int step$$7;
    int arr$dim$$1;
    int arr$dim$$2;
    int const$$1;
    int const$$2;
    int const$$3;
    int[] arr;
    arr$dim$$1 = 2;
    arr$dim$$2 = 2;
    const$$1 = 1;
    const$$2 = 2;
    const$$3 = 3;
    arr = __allocate((arr$dim$$1 * arr$dim$$2));
    arr[((0 * arr$dim$$2) + 0)] = const$$1;
    arr[((0 * arr$dim$$2) + 1)] = const$$2;
    i$4$5 = 0;
    stop$$6 = arr$dim$$2;
    step$$7 = 1;
    while (((step$$7 > 0) ? (i$4$5 < stop$$6) : (i$4$5 > stop$$6))) \{
        arr[((1 * arr$dim$$2) + i$4$5)] = const$$3;
        i$4$5 = (i$4$5 + step$$7);
    \}
\} v}

Constant propagation reduces this to:

{v void foo() \{
    int i$4$5;
    int[] arr;
    arr = __allocate(4);
    arr[0] = 1;
    arr[1] = 2;
    i$4$5 = 0;
    while ((i$4$5 < 2)) \{
        arr[(2 + i$4$5)] = 3;
        i$4$5 = (i$4$5 + 1);
    \}
\} v}
    *)

(** Constant propagation traversal. Exported for use in {!Unroll}. *)
val propagate_consts : Types.node -> Types.node

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