[m-rev.] for review: extend constant propagation to sized integer types

[Julien Fischer]

On Tue, 18 Apr 2023, Zoltan Somogyi wrote:

> Extend constant propagation to sized integers.
> 
> compiler/int_emu.m:
>     Give the emulation predicates for arithmetic predicates their inputs
>     as two arbitrary-precision integers, and then check whether the results
>     fit into the representable range of their expected type.
>
>     Give the emulation predicates for shift predicates their inputs
>     as an arbitrary-precision integer (the value to be shifted) and as
>     an int (the shift amount) and then check whether the results fit into
>     the representable range of their expected type.
>
>     In both cases, the caller (const_prop.m) will convert the inputs
>     to the above types. In both cases, the original code of int_emu.m
>     worked by doing the operation on arbitrary precision integers.
>     This approach emulates operations on fives times as many types
>     using less code (which includes just a bit more than half the
>     original number of predicates).
>
>     Add predicates to emulate the logical operations AND, OR, XOR and NOT.
>     With these, the original code (in const_prop.m) did *not* work by
>     doing the operation on arbitrary precision integers. I am not sure
>     if that was a deliberate decision to avoid integer.m's logical operations,
>     which I expect would not have been tested nearly as thoroughly
>     as the arithmetic ops.

I'm fairly certain that they haven't been as extensively tested, but I don't
think that's the reason. (Note that the initial version of const_prop.m was in
1997, which predates the addition of bitwise operations to the integer module
by two years.)

>     ZZZ Does anyone know the history here?

AND, OR XOR and NOT are never going to extend a value beyond what can be
represented by its type; the original version of const_prop did not use
int_emu.m (which was added in 2015). The treatment of these bitwise operations
is what const_prop.m has always done.

>     To be on the safe side, the emulation of logical ops does the work
>     on the actual types themselves, even though this needs much more code.
>
>     Split a convenience function into two, for two distinct use cases.

...

> 
> diff --git a/compiler/const_prop.m b/compiler/const_prop.m
> index 3082d3e3e..7b7872cea 100644
> --- a/compiler/const_prop.m
> +++ b/compiler/const_prop.m

...


> @@ -270,70 +272,48 @@ evaluate_det_call_uint_1(Globals, ProcName, ModeNum, X, OutputArg, ConsId) :-
>
>  %---------------------%
> 
> -:- pred evaluate_det_call_int_2(globals::in, string::in, int::in,
> -    arg_hlds_info::in, arg_hlds_info::in, arg_hlds_info::out, cons_id::out)
> -    is semidet.
> +:- pred evaluate_det_call_int_uint_2(globals::in, op_type::in,
> +    string::in, int::in, arg_hlds_info::in,
> +    arg_hlds_info::in, arg_hlds_info::out, cons_id::out) is semidet.
> 
> -evaluate_det_call_int_2(Globals, ProcName, ModeNum, X, Y,
> -        OutputArg, some_int_const(int_const(OutputArgVal))) :-
> +evaluate_det_call_int_uint_2(Globals, OpType, ProcName, ModeNum, X, Y,
> +        OutputArg, some_int_const(OutputArgVal)) :-
>      ModeNum = 0,
>      X ^ arg_inst = bound(_, _, [bound_functor(FunctorX, [])]),
> -    FunctorX = some_int_const(int_const(XVal)),
> +    FunctorX = some_int_const(ConstX),
>      OutputArg = Y,
> +    % All of the {int,uint}{,8,16,32,64} modules define unary plus,
> +    % unary minus, and bitwise negation. The other procedures below
> +    % are defined only in int.m; this is checked by the predicates that
> +    % emulate them.

None of the uint* modules provide unary plus and unary minus.

>
>      % If we can statically determine the result of a semidet call
> diff --git a/compiler/int_emu.m b/compiler/int_emu.m
> index b767a471b..ef6c6c260 100644
> --- a/compiler/int_emu.m
> +++ b/compiler/int_emu.m

...

> +%---------------------------------------------------------------------------%
> +
> +:- pred to_some_int_const_if_in_in_range(op_type::in, integer::in,
> +    some_int_const::out) is semidet.
> +
> +to_some_int_const_if_in_in_range(OpType, Integer, Const) :-
> +    (
> +        OpType = op_int(OpNumBits),
> +        NumBits = get_op_num_bits(OpNumBits),
> +        Integer >= -pow(integer(2), integer(NumBits - 1)),
> +        % ZZZ This was Integer =< pow(integer(2), integer(NumBits - 1)) - one,
> +        % but this one fits in better with the unsigned case below.
> +        Integer < pow(integer(2), integer(NumBits - 1)),
> +        (
> +            OpNumBits = word_bits(_),
> +            % Fails if Integer is representable on the target machine,
> +            % but not on the host.
> +            integer.to_int(Integer, Int),
> +            Const = int_const(Int)
> +        ;
> +            OpNumBits = bits_8,
> +            integer.to_int8(Integer, Int8),
> +            Const = int8_const(Int8)
> +        ;
> +            OpNumBits = bits_16,
> +            integer.to_int16(Integer, Int16),
> +            Const = int16_const(Int16)
> +        ;
> +            OpNumBits = bits_32,
> +            integer.to_int32(Integer, Int32),
> +            Const = int32_const(Int32)
> +        ;
> +            OpNumBits = bits_64,
> +            integer.to_int64(Integer, Int64),
> +            Const = int64_const(Int64)
> +        )
> +    ;
> +        OpType = op_uint(OpNumBits),
> +        NumBits = get_op_num_bits(OpNumBits),
>          Integer >= integer.zero,
> -    Integer =< pow(integer(2), integer(WordBits)),
> -    integer.to_uint(Integer, UInt).
> +        % ZZZ This was Integer =< pow(integer(2), integer(NumBits)),
> +        % which I (zs) think is a bug.
> +        Integer < pow(integer(2), integer(NumBits)),

Yes, it's a bug; it should be a strict inequality as you have here since
the values of any unsigned type will range from 0 .. (2 ^ NumBits) - 1.

That looks fine otherwise.

Julien.