diff options
Diffstat (limited to 'lib/compiler/src/beam_bounds.erl')
| -rw-r--r-- | lib/compiler/src/beam_bounds.erl | 301 |
1 files changed, 301 insertions, 0 deletions
diff --git a/lib/compiler/src/beam_bounds.erl b/lib/compiler/src/beam_bounds.erl new file mode 100644 index 0000000000..9a0507bb38 --- /dev/null +++ b/lib/compiler/src/beam_bounds.erl @@ -0,0 +1,301 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2022-2023. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% +%% Purpose: Calculate tight bounds for integer operations. +%% +%% Reference: +%% +%% Henry S. Warren, Jr. Hacker's Delight (2 ed). Addison Wesley - +%% Pearson Education, Inc. Chapter 4. Arithmetic Bounds. +%% +%% +-module(beam_bounds). +-export(['+'/2, '-'/2, '*'/2, 'div'/2, 'rem'/2, + 'band'/2, 'bor'/2, 'bxor'/2, 'bsr'/2, 'bsl'/2, + relop/3]). + +-type range() :: {integer(), integer()} | 'any'. +-type range_result() :: range() | 'any'. +-type relop() :: '<' | '=<' | '>' | '>='. +-type bool_result() :: 'true' | 'false' | 'maybe'. + +-spec '+'(range(), range()) -> range_result(). + +'+'({A,B}, {C,D}) when abs(A) bsr 256 =:= 0, abs(B) bsr 256 =:= 0, + abs(C) bsr 256 =:= 0, abs(D) bsr 256 =:= 0 -> + verify_range({A+C,B+D}); +'+'(_, _) -> + any. + +-spec '-'(range(), range()) -> range_result(). + +'-'({A,B}, {C,D}) when abs(A) bsr 256 =:= 0, abs(B) bsr 256 =:= 0, + abs(C) bsr 256 =:= 0, abs(D) bsr 256 =:= 0 -> + verify_range({A-D,B-C}); +'-'(_, _) -> + any. + +-spec '*'(range(), range()) -> range_result(). + +'*'({A,B}, {C,D}) when abs(A) bsr 256 =:= 0, abs(B) bsr 256 =:= 0, + abs(C) bsr 256 =:= 0, abs(D) bsr 256 =:= 0 -> + All = [X * Y || X <- [A,B], Y <- [C,D]], + Min = lists:min(All), + Max = lists:max(All), + verify_range({Min,Max}); +'*'(_, _) -> + any. + +-spec 'div'(range(), range()) -> range_result(). + +'div'({_,_}, {0,0}) -> + %% Division by zero, don't try to do anything clever. + any; +'div'({A,B}, {C,D}) when is_integer(A), is_integer(B), + is_integer(C), is_integer(D) -> + Denominators = [min(C, D),max(C, D)| + %% Handle zero crossing for the denominator. + if + C < 0, 0 < D -> [-1, 1]; + C =:= 0 -> [1]; + D =:= 0 -> [-1]; + true -> [] + end], + All = [X div Y || X <- [A,B], + Y <- Denominators, + Y =/= 0], + Min = lists:min(All), + Max = lists:max(All), + verify_range({Min,Max}); +'div'(_, _) -> + any. + +-spec 'rem'(range(), range()) -> range_result(). + +'rem'({A,_}, {C,D}) when C > 0 -> + Max = D - 1, + Min = if + A >= 0 -> 0; + true -> -Max + end, + verify_range({Min,Max}); +'rem'(_, {C,D}) when C =/= 0; D =/= 0 -> + Max = max(abs(C), abs(D)) - 1, + Min = -Max, + verify_range({Min,Max}); +'rem'(_, _) -> + any. + +-spec 'band'(range(), range()) -> range_result(). + +'band'({A,B}, {C,D}) when A >= 0, A bsr 256 =:= 0, C >= 0, C bsr 256 =:= 0 -> + Min = min_band(A, B, C, D), + Max = max_band(A, B, C, D), + {Min,Max}; +'band'(_, {C,D}) when C >= 0 -> + {0,D}; +'band'({A,B}, _) when A >= 0 -> + {0,B}; +'band'(_, _) -> + any. + +-spec 'bor'(range(), range()) -> range_result(). + +'bor'({A,B}, {C,D}) when A >= 0, A bsr 256 =:= 0, C >= 0, C bsr 256 =:= 0 -> + Min = min_bor(A, B, C, D), + Max = max_bor(A, B, C, D), + {Min,Max}; +'bor'(_, _) -> + any. + +-spec 'bxor'(range(), range()) -> range_result(). + +'bxor'({A,B}, {C,D}) when A >= 0, A bsr 256 =:= 0, C >= 0, C bsr 256 =:= 0 -> + Max = max_bxor(A, B, C, D), + {0,Max}; +'bxor'(_, _) -> + any. + +-spec 'bsr'(range(), range()) -> range_result(). + +'bsr'({A,B}, {C,D}) when C >= 0 -> + Min = min(A bsr C, A bsr D), + Max = max(B bsr C, B bsr D), + {Min,Max}; +'bsr'(_, _) -> + any. + +-spec 'bsl'(range(), range()) -> range_result(). + +'bsl'({A,B}, {C,D}) when abs(B) bsr 128 =:= 0, C >= 0, D < 128 -> + Min = min(A bsl C, A bsl D), + Max = max(B bsl C, B bsl D), + {Min,Max}; +'bsl'(_, _) -> + any. + +-spec relop(relop(), range(), range()) -> bool_result(). + +relop(Op, {A,B}, {C,D}) -> + case {erlang:Op(B, C),erlang:Op(A, D)} of + {Bool,Bool} -> Bool; + {_,_} -> 'maybe' + end; +relop(_, _, _) -> + 'maybe'. + +%%% +%%% Internal functions. +%%% + +verify_range({Min,Max}=T) when Min =< Max -> T. + +min_band(A, B, C, D) -> + M = 1 bsl (upper_bit(A bor C) + 1), + min_band(A, B, C, D, M). + +min_band(A, _B, C, _D, 0) -> + A band C; +min_band(A, B, C, D, M) -> + if + (bnot A) band (bnot C) band M =/= 0 -> + case (A bor M) band -M of + NewA when NewA =< B -> + min_band(NewA, B, C, D, 0); + _ -> + case (C bor M) band -M of + NewC when NewC =< D -> + min_band(A, B, NewC, D, 0); + _ -> + min_band(A, B, C, D, M bsr 1) + end + end; + true -> + min_band(A, B, C, D, M bsr 1) + end. + +max_band(A, B, C, D) -> + M = 1 bsl upper_bit(B bxor D), + max_band(A, B, C, D, M). + +max_band(_A, B, _C, D, 0) -> + B band D; +max_band(A, B, C, D, M) -> + if + B band (bnot D) band M =/= 0 -> + case (B band (bnot M)) bor (M - 1) of + NewB when NewB >= A -> + max_band(A, NewB, C, D, 0); + _ -> + max_band(A, B, C, D, M bsr 1) + end; + (bnot B) band D band M =/= 0 -> + case (D band (bnot M)) bor (M - 1) of + NewD when NewD >= C -> + max_band(A, B, C, NewD, 0); + _ -> + max_band(A, B, C, D, M bsr 1) + end; + true -> + max_band(A, B, C, D, M bsr 1) + end. + +min_bor(A, B, C, D) -> + M = 1 bsl upper_bit(A bxor C), + min_bor(A, B, C, D, M). + +min_bor(A, _B, C, _D, 0) -> + A bor C; +min_bor(A, B, C, D, M) -> + if + (bnot A) band C band M =/= 0 -> + case (A bor M) band -M of + NewA when NewA =< B -> + min_bor(NewA, B, C, D, 0); + _ -> + min_bor(A, B, C, D, M bsr 1) + end; + A band (bnot C) band M =/= 0 -> + case (C bor M) band -M of + NewC when NewC =< D -> + min_bor(A, B, NewC, D, 0); + _ -> + min_bor(A, B, C, D, M bsr 1) + end; + true -> + min_bor(A, B, C, D, M bsr 1) + end. + +max_bor(A, B, C, D) -> + Intersection = B band D, + M = 1 bsl upper_bit(Intersection), + max_bor(Intersection, A, B, C, D, M). + +max_bor(_Intersection, _A, B, _C, D, 0) -> + B bor D; +max_bor(Intersection, A, B, C, D, M) -> + if + Intersection band M =/= 0 -> + case (B - M) bor (M - 1) of + NewB when NewB >= A -> + max_bor(Intersection, A, NewB, C, D, 0); + _ -> + case (D - M) bor (M - 1) of + NewD when NewD >= C -> + max_bor(Intersection, A, B, C, NewD, 0); + _ -> + max_bor(Intersection, A, B, C, D, M bsr 1) + end + end; + true -> + max_bor(Intersection, A, B, C, D, M bsr 1) + end. + +max_bxor(A, B, C, D) -> + M = 1 bsl upper_bit(B band D), + max_bxor(A, B, C, D, M). + +max_bxor(_A, B, _C, D, 0) -> + B bxor D; +max_bxor(A, B, C, D, M) -> + if + B band D band M =/= 0 -> + case (B - M) bor (M - 1) of + NewB when NewB >= A -> + max_bxor(A, NewB, C, D, M bsr 1); + _ -> + case (D - M) bor (M - 1) of + NewD when NewD >= C -> + max_bxor(A, B, C, NewD, M bsr 1); + _ -> + max_bxor(A, B, C, D, M bsr 1) + end + end; + true -> + max_bxor(A, B, C, D, M bsr 1) + end. + +upper_bit(Val) -> + upper_bit_1(Val, 0). + +upper_bit_1(Val0, N) -> + case Val0 bsr 1 of + 0 -> N; + Val -> upper_bit_1(Val, N + 1) + end. |