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_6_7;
    int __arr_1_2__;
    int __arr_2_1__;
    int __const_3__;
    int __const_4__;
    int __const_5__;
    int[] arr;
    int __stop_8__;
    int __step_9__;
    __arr_1_2__ = 2;
    __arr_2_1__ = 2;
    __const_3__ = 1;
    __const_4__ = 2;
    __const_5__ = 3;
    arr := <allocate>((__arr_1_2__ * __arr_2_1__));
    arr[((0 * __arr_2_1__) + 0)] = __const_3__;
    arr[((0 * __arr_2_1__) + 1)] = __const_4__;
    ____i_6_7 = 0;
    __stop_8__ = __arr_2_1__;
    __step_9__ = 1;
    while (((__step_9__ > 0) ? (____i_6_7 < __stop_8__) : (____i_6_7 > __stop_8__))) \{
        arr[((1 * __arr_2_1__) + ____i_6_7)] = __const_5__;
        ____i_6_7 = (____i_6_7 + __step_9__);
    \}

\} v}

Constant propagation reduces this to:

{v void foo() \{
    int ____i_6_7;
    int[] arr;
    arr := <allocate>(4);
    arr[0] = 1;
    arr[1] = 2;
    ____i_6_7 = 0;
    while ((____i_6_7 < 2)) \{
        arr[(2 + ____i_6_7)] = 3;
        ____i_6_7 = (____i_6_7 + 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