From 7e66eb6a07928448b7c1a6f265d782bebacd4e6b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magnus=20L=C3=A5ng?= Date: Mon, 20 Feb 2017 14:57:16 +0100 Subject: 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. --- lib/hipe/icode/hipe_icode_type.erl | 21 ++++---- lib/hipe/rtl/hipe_tagscheme.erl | 71 +++++++++---------------- lib/hipe/test/basic_SUITE_data/basic_tuples.erl | 14 +++++ 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) 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. -- cgit v1.2.3