aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2017-02-20 14:57:16 +0100
committerMagnus Lång <[email protected]>2017-03-06 18:18:23 +0100
commit7e66eb6a07928448b7c1a6f265d782bebacd4e6b (patch)
treeb2b5f7bbd13103586c08d3fb4a7d425bebf73f71 /lib/hipe
parent11f1271b5b54a474bcd5ebc1e9c34549610a918b (diff)
downloadotp-7e66eb6a07928448b7c1a6f265d782bebacd4e6b.tar.gz
otp-7e66eb6a07928448b7c1a6f265d782bebacd4e6b.tar.bz2
otp-7e66eb6a07928448b7c1a6f265d782bebacd4e6b.zip
hipe: Improve code generation for element/2
* Omit bounds check in more cases. A test case that needs this change to omit bounds check is added. * Improve code generation by reformulating bounds check to decrease register pressure.
Diffstat (limited to 'lib/hipe')
-rw-r--r--lib/hipe/icode/hipe_icode_type.erl21
-rw-r--r--lib/hipe/rtl/hipe_tagscheme.erl71
-rw-r--r--lib/hipe/test/basic_SUITE_data/basic_tuples.erl14
3 files changed, 51 insertions, 55 deletions
diff --git a/lib/hipe/icode/hipe_icode_type.erl b/lib/hipe/icode/hipe_icode_type.erl
index 815d1e57a8..aafaeb5a0a 100644
--- a/lib/hipe/icode/hipe_icode_type.erl
+++ b/lib/hipe/icode/hipe_icode_type.erl
@@ -1410,9 +1410,10 @@ transform_element2(I) ->
NewIndex =
case test_type(integer, IndexType) of
true ->
- case t_number_vals(IndexType) of
- unknown -> unknown;
- [_|_] = Vals -> {number, Vals}
+ case {number_min(IndexType), number_max(IndexType)} of
+ {Lb0, Ub0} when is_integer(Lb0), is_integer(Ub0) ->
+ {number, Lb0, Ub0};
+ {_, _} -> unknown
end;
_ -> unknown
end,
@@ -1427,19 +1428,19 @@ transform_element2(I) ->
_ -> unknown
end,
case {NewIndex, MinSize} of
- {{number, [_|_] = Ns}, {tuple, A}} when is_integer(A) ->
- case lists:all(fun(X) -> 0 < X andalso X =< A end, Ns) of
+ {{number, Lb, Ub}, {tuple, A}} when is_integer(A) ->
+ case 0 < Lb andalso Ub =< A of
true ->
- case Ns of
- [Idx] ->
+ case {Lb, Ub} of
+ {Idx, Idx} ->
[_, Tuple] = hipe_icode:args(I),
update_call_or_enter(I, #unsafe_element{index = Idx}, [Tuple]);
- [_|_] ->
+ {_, _} ->
NewFun = {element, [MinSize, valid]},
update_call_or_enter(I, NewFun)
end;
false ->
- case lists:all(fun(X) -> hipe_tagscheme:is_fixnum(X) end, Ns) of
+ case lists:all(fun(X) -> hipe_tagscheme:is_fixnum(X) end, [Lb, Ub]) of
true ->
NewFun = {element, [MinSize, fixnums]},
update_call_or_enter(I, NewFun);
@@ -1454,7 +1455,7 @@ transform_element2(I) ->
NewFun = {element, [MinSize, fixnums]},
update_call_or_enter(I, NewFun);
false ->
- NewFun = {element, [MinSize, NewIndex]},
+ NewFun = {element, [MinSize, NewIndex]},
update_call_or_enter(I, NewFun)
end
end.
diff --git a/lib/hipe/rtl/hipe_tagscheme.erl b/lib/hipe/rtl/hipe_tagscheme.erl
index 133e36d409..e6e2816840 100644
--- a/lib/hipe/rtl/hipe_tagscheme.erl
+++ b/lib/hipe/rtl/hipe_tagscheme.erl
@@ -647,14 +647,13 @@ unsafe_update_element(Tuple, Index, Value) -> % Index is an immediate
element(Dst, Index, Tuple, FailLabName, {tuple, A}, IndexInfo) ->
FixnumOkLab = hipe_rtl:mk_new_label(),
IndexOkLab = hipe_rtl:mk_new_label(),
- Ptr = hipe_rtl:mk_new_reg(), % offset from Tuple
UIndex = hipe_rtl:mk_new_reg_gcsafe(),
Arity = hipe_rtl:mk_imm(A),
- InvIndex = hipe_rtl:mk_new_reg_gcsafe(),
- Offset = hipe_rtl:mk_new_reg_gcsafe(),
case IndexInfo of
valid ->
%% This is no branch, 1 load and 3 alus = 4 instr
+ Offset = hipe_rtl:mk_new_reg_gcsafe(),
+ Ptr = hipe_rtl:mk_new_reg(), % offset from Tuple
[untag_fixnum(UIndex, Index),
hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
hipe_rtl:mk_alu(Offset, UIndex, 'sll',
@@ -663,72 +662,56 @@ element(Dst, Index, Tuple, FailLabName, {tuple, A}, IndexInfo) ->
fixnums ->
%% This is 1 branch, 1 load and 4 alus = 6 instr
[untag_fixnum(UIndex, Index),
- hipe_rtl:mk_alu(Ptr, Tuple, 'sub',hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset, UIndex,
- FailLabName, IndexOkLab)];
+ gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab)];
_ ->
%% This is 3 branches, 1 load and 5 alus = 9 instr
[test_fixnum(Index, hipe_rtl:label_name(FixnumOkLab),
FailLabName, 0.99),
FixnumOkLab,
untag_fixnum(UIndex, Index),
- hipe_rtl:mk_alu(Ptr, Tuple, 'sub',hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset, UIndex,
- FailLabName, IndexOkLab)]
+ gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab)]
end;
element(Dst, Index, Tuple, FailLabName, tuple, IndexInfo) ->
FixnumOkLab = hipe_rtl:mk_new_label(),
IndexOkLab = hipe_rtl:mk_new_label(),
- Ptr = hipe_rtl:mk_new_reg(), % offset from Tuple
Header = hipe_rtl:mk_new_reg_gcsafe(),
UIndex = hipe_rtl:mk_new_reg_gcsafe(),
Arity = hipe_rtl:mk_new_reg_gcsafe(),
- InvIndex = hipe_rtl:mk_new_reg_gcsafe(),
- Offset = hipe_rtl:mk_new_reg_gcsafe(),
case IndexInfo of
fixnums ->
%% This is 1 branch, 2 loads and 5 alus = 8 instr
- [hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
- hipe_rtl:mk_load(Header, Ptr, hipe_rtl:mk_imm(0)),
+ [get_header(Header, Tuple),
untag_fixnum(UIndex, Index),
hipe_rtl:mk_alu(Arity,Header,'srl',hipe_rtl:mk_imm(?HEADER_ARITY_OFFS))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset, UIndex,
- FailLabName, IndexOkLab)];
+ gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab)];
Num when is_integer(Num) ->
%% This is 1 branch, 1 load and 3 alus = 5 instr
- [hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED))|
- gen_element_tail(Dst, Ptr, InvIndex, hipe_rtl:mk_imm(Num),
- Offset, UIndex, FailLabName, IndexOkLab)];
+ gen_element_tail(Dst, Tuple, hipe_rtl:mk_imm(Num), UIndex, FailLabName,
+ IndexOkLab);
_ ->
%% This is 2 branches, 2 loads and 6 alus = 10 instr
[test_fixnum(Index, hipe_rtl:label_name(FixnumOkLab), FailLabName, 0.99),
FixnumOkLab,
- hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
- hipe_rtl:mk_load(Header, Ptr, hipe_rtl:mk_imm(0)),
+ get_header(Header, Tuple),
untag_fixnum(UIndex, Index),
hipe_rtl:mk_alu(Arity,Header,'srl',hipe_rtl:mk_imm(?HEADER_ARITY_OFFS))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset, UIndex,
- FailLabName, IndexOkLab)]
+ gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab)]
end;
element(Dst, Index, Tuple, FailLabName, unknown, IndexInfo) ->
FixnumOkLab = hipe_rtl:mk_new_label(),
BoxedOkLab = hipe_rtl:mk_new_label(),
TupleOkLab = hipe_rtl:mk_new_label(),
IndexOkLab = hipe_rtl:mk_new_label(),
- Ptr = hipe_rtl:mk_new_reg(), % offset from Tuple
Header = hipe_rtl:mk_new_reg_gcsafe(),
UIndex = hipe_rtl:mk_new_reg_gcsafe(),
Arity = hipe_rtl:mk_new_reg_gcsafe(),
- InvIndex = hipe_rtl:mk_new_reg_gcsafe(),
- Offset = hipe_rtl:mk_new_reg_gcsafe(),
case IndexInfo of
fixnums ->
%% This is 3 branches, 2 loads and 5 alus = 10 instr
[test_is_boxed(Tuple, hipe_rtl:label_name(BoxedOkLab),
FailLabName, 0.99),
BoxedOkLab,
- hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
- hipe_rtl:mk_load(Header, Ptr, hipe_rtl:mk_imm(0)),
+ get_header(Header, Tuple),
hipe_rtl:mk_branch(Header, 'and',
hipe_rtl:mk_imm(?TAG_HEADER_MASK), 'eq',
hipe_rtl:label_name(TupleOkLab), FailLabName, 0.99),
@@ -736,23 +719,21 @@ element(Dst, Index, Tuple, FailLabName, unknown, IndexInfo) ->
untag_fixnum(UIndex, Index),
hipe_rtl:mk_alu(Arity, Header, 'srl',
hipe_rtl:mk_imm(?HEADER_ARITY_OFFS))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset,
- UIndex, FailLabName, IndexOkLab)];
+ gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab)];
Num when is_integer(Num) ->
%% This is 3 branches, 2 loads and 4 alus = 9 instr
[test_is_boxed(Tuple, hipe_rtl:label_name(BoxedOkLab),
FailLabName, 0.99),
BoxedOkLab,
- hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
- hipe_rtl:mk_load(Header, Ptr, hipe_rtl:mk_imm(0)),
+ get_header(Header, Tuple),
hipe_rtl:mk_branch(Header, 'and',
hipe_rtl:mk_imm(?TAG_HEADER_MASK), 'eq',
hipe_rtl:label_name(TupleOkLab), FailLabName, 0.99),
TupleOkLab,
hipe_rtl:mk_alu(Arity, Header, 'srl',
hipe_rtl:mk_imm(?HEADER_ARITY_OFFS))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset,
- hipe_rtl:mk_imm(Num), FailLabName, IndexOkLab)];
+ gen_element_tail(Dst, Tuple, Arity, hipe_rtl:mk_imm(Num), FailLabName,
+ IndexOkLab)];
_ ->
%% This is 4 branches, 2 loads, and 6 alus = 12 instr :(
[test_fixnum(Index, hipe_rtl:label_name(FixnumOkLab),
@@ -761,8 +742,7 @@ element(Dst, Index, Tuple, FailLabName, unknown, IndexInfo) ->
test_is_boxed(Tuple, hipe_rtl:label_name(BoxedOkLab),
FailLabName, 0.99),
BoxedOkLab,
- hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
- hipe_rtl:mk_load(Header, Ptr, hipe_rtl:mk_imm(0)),
+ get_header(Header, Tuple),
hipe_rtl:mk_branch(Header, 'and',
hipe_rtl:mk_imm(?TAG_HEADER_MASK), 'eq',
hipe_rtl:label_name(TupleOkLab), FailLabName, 0.99),
@@ -770,20 +750,21 @@ element(Dst, Index, Tuple, FailLabName, unknown, IndexInfo) ->
untag_fixnum(UIndex, Index),
hipe_rtl:mk_alu(Arity, Header, 'srl',
hipe_rtl:mk_imm(?HEADER_ARITY_OFFS))|
- gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset,
- UIndex, FailLabName, IndexOkLab)]
+ gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab)]
end.
-gen_element_tail(Dst, Ptr, InvIndex, Arity, Offset,
- UIndex, FailLabName, IndexOkLab) ->
+gen_element_tail(Dst, Tuple, Arity, UIndex, FailLabName, IndexOkLab) ->
+ ZeroIndex = hipe_rtl:mk_new_reg_gcsafe(),
+ Offset = hipe_rtl:mk_new_reg_gcsafe(),
+ Ptr = hipe_rtl:mk_new_reg(), % offset from Tuple
%% now check that 1 <= UIndex <= Arity
- %% if UIndex < 1, then (Arity - UIndex) >= Arity
- %% if UIndex > Arity, then (Arity - UIndex) < 0, which is >=u Arity
- %% otherwise, 0 <= (Arity - UIndex) < Arity
- [hipe_rtl:mk_alu(InvIndex, Arity, 'sub', UIndex),
- hipe_rtl:mk_branch(InvIndex, 'geu', Arity, FailLabName,
+ %% by checking the equivalent (except for when Arity>=2^(WordSize-1))
+ %% (UIndex - 1) <u Arity
+ [hipe_rtl:mk_alu(ZeroIndex, UIndex, 'sub', hipe_rtl:mk_imm(1)),
+ hipe_rtl:mk_branch(ZeroIndex, 'geu', Arity, FailLabName,
hipe_rtl:label_name(IndexOkLab), 0.01),
IndexOkLab,
+ hipe_rtl:mk_alu(Ptr, Tuple, 'sub', hipe_rtl:mk_imm(?TAG_PRIMARY_BOXED)),
hipe_rtl:mk_alu(Offset, UIndex, 'sll',
hipe_rtl:mk_imm(hipe_rtl_arch:log2_word_size())),
hipe_rtl:mk_load(Dst, Ptr, Offset)].
diff --git a/lib/hipe/test/basic_SUITE_data/basic_tuples.erl b/lib/hipe/test/basic_SUITE_data/basic_tuples.erl
index 94c187e364..96e39d565a 100644
--- a/lib/hipe/test/basic_SUITE_data/basic_tuples.erl
+++ b/lib/hipe/test/basic_SUITE_data/basic_tuples.erl
@@ -55,6 +55,8 @@ test_element(T0, T1, T2, N) ->
List = lists:seq(1, N),
Tuple = list_to_tuple(List),
ok = get_elements(List, Tuple, 1),
+ %% element/2 of larger tuple with omitted bounds test
+ true = lists:all(fun(I) -> I * I =:= square(I) end, lists:seq(1, 20)),
%% some cases that throw exceptions
{'EXIT', _} = (catch my_element(0, T2)),
{'EXIT', _} = (catch my_element(3, T2)),
@@ -73,6 +75,18 @@ get_elements([Element|Rest], Tuple, Pos) ->
get_elements([], _Tuple, _Pos) ->
ok.
+squares() ->
+ {1*1, 2*2, 3*3, 4*4, 5*5, 6*6, 7*7, 8*8, 9*9, 10*10,
+ 11*11, 12*12, 13*13, 14*14, 15*15, 16*16, 17*17, 18*18, 19*19, 20*20}.
+
+square(N) when is_integer(N), N >= 1, N =< 20 ->
+ %% The guard tests lets the range analysis conclude N to be an integer in the
+ %% 1..20 range. 20-1=19 is bigger than ?SET_LIMIT in erl_types.erl, and will
+ %% thus be represented by an ?int_range() rather than an ?int_set().
+ %% Because of the range analysis, the bounds test of this element/2 call
+ %% should be omitted.
+ element(N, squares()).
+
%%--------------------------------------------------------------------
%% Tests set_element/3.