civicaml/phases/constprop.mli

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

(** The compiler sometimes generates variables of the form [_foo_1_],
    indicating that the variable is assigned exactly once (it is in SSA form).
    In many cases, generated variables leads to over-complex constructions with
    more variable definitions then necessary, for example when converting
    for-loops to while-loops. We use the knowledge of these variables being in
    SSA form, by propagating the constant values to their uses, and then apply
    arithmetic simplification to operators to reduce the size and complexity of
    the generated code. Note that this can only be applied when the assigned
    expression is a constant or an SSA variable, since these have no side
    effects and will not change in between the assignment and their uses. For
    optimisation regular of variables, some form of liveness analysis would be
    required.

    Constant propagation is supplemented with constand folding and some
    arithmetic simplification, the latter specifically targeting optimisation
    oppertunities created by earlier constant propagation. For example, in and
    array index calculation when constant array dimensions are propagated, the
    index calculation can often be simplified.

    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 = 3;
\} v}

After desugaring and array dimension reduction this becomes:

{v void foo() \{
    int _i_4;
    int _stop_5_;
    int _step_6_;
    int _i_7;
    int _stop_8_;
    int _step_9_;
    int _arr_0_;
    int _arr_1_;
    int _scalar_1_;
    int[] arr;
    _arr_0_ = 2;
    _arr_1_ = 2;
    _scalar_1_ = 3;
    arr := <allocate>((_arr_0_ * _arr_1_));
    _i_4 = 0;
    _stop_5_ = _arr_0_;
    _step_6_ = 1;
    while (((_step_6_ > 0) ? (_i_4 < _stop_5_) : (_i_4 > _stop_5_))) \{
        _i_7 = 0;
        _stop_8_ = _arr_1_;
        _step_9_ = 1;
        while (((_step_9_ > 0) ? (_i_7 < _stop_8_) : (_i_7 > _stop_8_))) \{
            arr[((_i_4 * _arr_1_) + _i_7)] = _scalar_1_;
            _i_7 = (_i_7 + _step_9_);
        \}
        _i_4 = (_i_4 + _step_6_);
    \}
\} v}

Constant propagation reduces this to:

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