From b9068c94921e97cc918e9c8664c252af33bfaf39 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Magnus=20L=C3=A5ng?= Date: Mon, 14 Apr 2014 18:10:31 +0200 Subject: Added elimination of maps:is_key/2 calls to HiPE * Implemented removal of maps:is_key/2 calls of which the result is known in a new pass during the typed phase, called hipe_icode_call_elim. * Added the option icode_call_elim that enables the hipe_icode_call_elim pass, and made it default for o2. --- lib/hipe/icode/Makefile | 2 +- lib/hipe/icode/hipe_icode_call_elim.erl | 78 +++++++++++++++++++++++++++++++++ lib/hipe/main/hipe.app.src | 1 + lib/hipe/main/hipe.erl | 7 ++- lib/hipe/main/hipe_main.erl | 14 +++++- 5 files changed, 98 insertions(+), 4 deletions(-) create mode 100644 lib/hipe/icode/hipe_icode_call_elim.erl (limited to 'lib') diff --git a/lib/hipe/icode/Makefile b/lib/hipe/icode/Makefile index a5edb10d90..c86562a981 100644 --- a/lib/hipe/icode/Makefile +++ b/lib/hipe/icode/Makefile @@ -59,7 +59,7 @@ DOC_MODULES = hipe_beam_to_icode \ hipe_icode_pp hipe_icode_primops \ hipe_icode_range \ hipe_icode_split_arith \ - hipe_icode_ssa hipe_icode_ssa_const_prop \ + hipe_icode_ssa hipe_icode_ssa_const_prop hipe_icode_call_elim \ hipe_icode_ssa_copy_prop hipe_icode_ssa_struct_reuse \ hipe_icode_type $(HIPE_MODULES) diff --git a/lib/hipe/icode/hipe_icode_call_elim.erl b/lib/hipe/icode/hipe_icode_call_elim.erl new file mode 100644 index 0000000000..6a22133962 --- /dev/null +++ b/lib/hipe/icode/hipe_icode_call_elim.erl @@ -0,0 +1,78 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2016. 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% +%% +%%---------------------------------------------------------------------- +%% File : hipe_icode_call_elim.erl +%% Authors : Daniel S. McCain , +%% Magnus Lång +%% Created : 14 Apr 2014 by Magnus Lång +%% Purpose : Eliminate calls to BIFs that are side-effect free only when +%% executed on some argument types. +%%---------------------------------------------------------------------- +-module(hipe_icode_call_elim). +-export([cfg/1]). + +-include("hipe_icode.hrl"). +-include("../flow/cfg.hrl"). + +-spec cfg(cfg()) -> cfg(). + +cfg(IcodeSSA) -> + lists:foldl(fun (Lbl, CFG1) -> + BB1 = hipe_icode_cfg:bb(CFG1, Lbl), + Code1 = hipe_bb:code(BB1), + Code2 = lists:map(fun elim_insn/1, Code1), + BB2 = hipe_bb:code_update(BB1, Code2), + hipe_icode_cfg:bb_add(CFG1, Lbl, BB2) + end, IcodeSSA, hipe_icode_cfg:labels(IcodeSSA)). + +-spec elim_insn(icode_instr()) -> icode_instr(). +elim_insn(Insn=#icode_call{'fun'={_,_,_}=MFA, args=Args, type=remote, + dstlist=[Dst=#icode_variable{ + annotation={type_anno, RetType, _}}]}) -> + Opaques = 'universe', + case erl_types:t_is_singleton(RetType, Opaques) of + true -> + ArgTypes = [case Arg of + #icode_variable{annotation={type_anno, Type, _}} -> Type; + #icode_const{} -> + erl_types:t_from_term(hipe_icode:const_value(Arg)) + end || Arg <- Args], + case can_be_eliminated(MFA, ArgTypes) of + true -> + Const = hipe_icode:mk_const( + erl_types:t_singleton_to_term(RetType, Opaques)), + #icode_move{dst=Dst, src=Const}; + false -> Insn + end; + false -> Insn + end; +elim_insn(Insn) -> Insn. + + +%% A function can be eliminated for some argument types if it has no side +%% effects when run on arguments of those types. + +-spec can_be_eliminated(mfa(), [erl_types:erl_type()]) -> boolean(). + +can_be_eliminated({maps, is_key, 2}, [_K, M]) -> + erl_types:t_is_map(M); +can_be_eliminated(_, _) -> + false. diff --git a/lib/hipe/main/hipe.app.src b/lib/hipe/main/hipe.app.src index aa86b6dc5b..f8487151d7 100644 --- a/lib/hipe/main/hipe.app.src +++ b/lib/hipe/main/hipe.app.src @@ -88,6 +88,7 @@ hipe_icode2rtl, hipe_icode_bincomp, hipe_icode_callgraph, + hipe_icode_call_elim, hipe_icode_cfg, hipe_icode_coordinator, hipe_icode_ebb, diff --git a/lib/hipe/main/hipe.erl b/lib/hipe/main/hipe.erl index 0e32da1d36..c026329276 100644 --- a/lib/hipe/main/hipe.erl +++ b/lib/hipe/main/hipe.erl @@ -1165,6 +1165,9 @@ option_text(caller_save_spill_restore) -> "Activates caller save register spills and restores"; option_text(debug) -> "Outputs internal debugging information during compilation"; +option_text(icode_call_elim) -> + "Performs call elimination of BIFs that are side-effect free\n" ++ + "only on some argument types"; option_text(icode_range) -> "Performs integer range analysis on the Icode level"; option_text(icode_ssa_check) -> @@ -1318,6 +1321,7 @@ opt_keys() -> get_called_modules, split_arith, split_arith_unsafe, + icode_call_elim, icode_inline_bifs, icode_ssa_check, icode_ssa_copy_prop, @@ -1399,7 +1403,7 @@ o1_opts(TargetArch) -> o2_opts(TargetArch) -> Common = [icode_ssa_const_prop, icode_ssa_copy_prop, % icode_ssa_struct_reuse, - icode_type, icode_inline_bifs, rtl_lcm, + icode_type, icode_inline_bifs, icode_call_elim, rtl_lcm, rtl_ssa, rtl_ssa_const_prop, spillmin_color, use_indexing, remove_comments, concurrent_comp, binary_opt | o1_opts(TargetArch)], @@ -1429,6 +1433,7 @@ opt_negations() -> {no_icode_inline_bifs, icode_inline_bifs}, {no_icode_range, icode_range}, {no_icode_split_arith, icode_split_arith}, + {no_icode_call_elim, icode_call_elim}, {no_icode_ssa_check, icode_ssa_check}, {no_icode_ssa_copy_prop, icode_ssa_copy_prop}, {no_icode_ssa_const_prop, icode_ssa_const_prop}, diff --git a/lib/hipe/main/hipe_main.erl b/lib/hipe/main/hipe_main.erl index be5050e155..b9d783d20a 100644 --- a/lib/hipe/main/hipe_main.erl +++ b/lib/hipe/main/hipe_main.erl @@ -284,8 +284,9 @@ icode_ssa_type(IcodeSSA, MFA, Options, Servers) -> false -> AnnIcode1 end, AnnIcode3 = icode_range_analysis(AnnIcode2, MFA, Options, Servers), - pp(AnnIcode3, MFA, icode, pp_range_icode, Options, Servers), - hipe_icode_type:unannotate_cfg(AnnIcode3) + AnnIcode4 = icode_eliminate_safe_calls(AnnIcode3, Options), + pp(AnnIcode4, MFA, icode, pp_range_icode, Options, Servers), + hipe_icode_type:unannotate_cfg(AnnIcode4) end. icode_ssa_convert(IcodeCfg, Options) -> @@ -334,6 +335,15 @@ icode_range_analysis(IcodeSSA, MFA, Options, Servers) -> IcodeSSA end. +icode_eliminate_safe_calls(IcodeSSA, Options) -> + case proplists:get_bool(icode_call_elim, Options) of + true -> + ?option_time(hipe_icode_call_elim:cfg(IcodeSSA), + "Icode SSA safe call elimination", Options); + false -> + IcodeSSA + end. + icode_ssa_dead_code_elimination(IcodeSSA, Options) -> IcodeSSA1 = ?option_time(hipe_icode_ssa:remove_dead_code(IcodeSSA), "Icode SSA dead code elimination pass 2", -- cgit v1.2.3 From f833a900897faae48230bc8c1e7572fb470a4a6f Mon Sep 17 00:00:00 2001 From: Erik Norgren Date: Mon, 9 Jun 2014 14:12:08 +0200 Subject: hipe: Add test suite for verifying optimisations * Added a suite opt_verify_SUITE.erl to HiPE that tests for the results of optimisations, with a single testcase that checks that the icode_call_elim optimisation pass does remove calls to maps:is_key/2 where sound and not otherwise. * Made hipe_testsuite_driver only create explicitly listed suites. --- lib/hipe/test/Makefile | 5 +- lib/hipe/test/hipe_testsuite_driver.erl | 24 +++------ lib/hipe/test/opt_verify_SUITE.erl | 62 ++++++++++++++++++++++ .../test/opt_verify_SUITE_data/call_elim_test.erl | 12 +++++ .../call_elim_test_branches_no_opt_poss.erl | 32 +++++++++++ .../call_elim_test_branches_opt_poss.erl | 32 +++++++++++ 6 files changed, 149 insertions(+), 18 deletions(-) create mode 100644 lib/hipe/test/opt_verify_SUITE.erl create mode 100644 lib/hipe/test/opt_verify_SUITE_data/call_elim_test.erl create mode 100644 lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_no_opt_poss.erl create mode 100644 lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_opt_poss.erl (limited to 'lib') diff --git a/lib/hipe/test/Makefile b/lib/hipe/test/Makefile index 09f4fd2129..544888719f 100644 --- a/lib/hipe/test/Makefile +++ b/lib/hipe/test/Makefile @@ -6,7 +6,8 @@ include $(ERL_TOP)/make/$(TARGET)/otp.mk # ---------------------------------------------------- MODULES= \ - hipe_SUITE + hipe_SUITE \ + opt_verify_SUITE # .erl files for these modules are automatically generated GEN_MODULES= \ @@ -79,4 +80,4 @@ release_tests_spec: make_emakefile @tar cf - *_SUITE_data | (cd "$(RELSYSDIR)"; tar xf -) cd "$(RELSYSDIR)";\ erlc hipe_testsuite_driver.erl;\ - erl -noshell -run hipe_testsuite_driver create_all_suites -s erlang halt + erl -noshell -run hipe_testsuite_driver create_all_suites $(GEN_MODULES) -s erlang halt diff --git a/lib/hipe/test/hipe_testsuite_driver.erl b/lib/hipe/test/hipe_testsuite_driver.erl index 9f5d7421b4..15b267b72e 100644 --- a/lib/hipe/test/hipe_testsuite_driver.erl +++ b/lib/hipe/test/hipe_testsuite_driver.erl @@ -1,6 +1,6 @@ -module(hipe_testsuite_driver). --export([create_all_suites/0, run/3]). +-export([create_all_suites/1, run/3]). -include_lib("kernel/include/file.hrl"). @@ -16,25 +16,17 @@ outputfile :: file:io_device(), testcases :: [testcase()]}). --spec create_all_suites() -> 'ok'. +-spec create_all_suites([string()]) -> 'ok'. -create_all_suites() -> - {ok, Cwd} = file:get_cwd(), - Suites = get_suites(Cwd), +create_all_suites(SuitesWithSuiteSuffix) -> + Suites = get_suites(SuitesWithSuiteSuffix), lists:foreach(fun create_suite/1, Suites). --spec get_suites(file:filename()) -> [string()]. +-spec get_suites([string()]) -> [string()]. -get_suites(Dir) -> - case file:list_dir(Dir) of - {error, _} -> []; - {ok, Filenames} -> - FullFilenames = [filename:join(Dir, F) || F <- Filenames], - Dirs = [suffix(filename:basename(F), ?suite_data) || - F <- FullFilenames, - file_type(F) =:= {ok, 'directory'}], - [S || {yes, S} <- Dirs] - end. +get_suites(SuitesWithSuiteSuffix) -> + Prefixes = [suffix(F, ?suite_suffix) || F <- SuitesWithSuiteSuffix], + [S || {yes, S} <- Prefixes]. suffix(String, Suffix) -> case string:rstr(String, Suffix) of diff --git a/lib/hipe/test/opt_verify_SUITE.erl b/lib/hipe/test/opt_verify_SUITE.erl new file mode 100644 index 0000000000..61952e81d7 --- /dev/null +++ b/lib/hipe/test/opt_verify_SUITE.erl @@ -0,0 +1,62 @@ +-module(opt_verify_SUITE). + +-compile([export_all]). + +all() -> + [call_elim]. + +groups() -> + []. + +init_per_suite(Config) -> + case erlang:system_info(hipe_architecture) of + undefined -> {skip, "HiPE not available or enabled"}; + _ -> Config + end. + +end_per_suite(_Config) -> + ok. + +init_per_group(_GroupName, Config) -> + Config. + +end_per_group(_GroupName, Config) -> + Config. + +call_elim_test_file(Config, FileName, Option) -> + PrivDir = test_server:lookup_config(priv_dir, Config), + TempOut = test_server:temp_name(filename:join(PrivDir, "call_elim_out")), + {ok, TestCase} = compile:file(FileName), + {ok, TestCase} = hipe:c(TestCase, [Option, {pp_range_icode, {file, TempOut}}]), + {ok, Icode} = file:read_file(TempOut), + ok = file:delete(TempOut), + Icode. + +substring_count(Icode, Substring) -> + substring_count(Icode, Substring, 0). +substring_count(Icode, Substring, N) -> + case string:str(Icode, Substring) of + 0 -> N; + I -> substring_count(lists:nthtail(I, Icode), Substring, N+1) + end. + +call_elim() -> + [{doc, "Test that the call elimination optimization pass is ok"}]. +call_elim(Config) -> + DataDir = test_server:lookup_config(data_dir, Config), + F1 = filename:join(DataDir, "call_elim_test.erl"), + Icode1 = call_elim_test_file(Config, F1, icode_call_elim), + 0 = substring_count(binary:bin_to_list(Icode1), "is_key"), + Icode2 = call_elim_test_file(Config, F1, no_icode_call_elim), + true = (0 /= substring_count(binary:bin_to_list(Icode2), "is_key")), + F2 = filename:join(DataDir, "call_elim_test_branches_no_opt_poss.erl"), + Icode3 = call_elim_test_file(Config, F2, icode_call_elim), + 3 = substring_count(binary:bin_to_list(Icode3), "is_key"), + Icode4 = call_elim_test_file(Config, F2, no_icode_call_elim), + 3 = substring_count(binary:bin_to_list(Icode4), "is_key"), + F3 = filename:join(DataDir, "call_elim_test_branches_opt_poss.erl"), + Icode5 = call_elim_test_file(Config, F3, icode_call_elim), + 0 = substring_count(binary:bin_to_list(Icode5), "is_key"), + Icode6 = call_elim_test_file(Config, F3, no_icode_call_elim), + 3 = substring_count(binary:bin_to_list(Icode6), "is_key"), + ok. diff --git a/lib/hipe/test/opt_verify_SUITE_data/call_elim_test.erl b/lib/hipe/test/opt_verify_SUITE_data/call_elim_test.erl new file mode 100644 index 0000000000..8b725f8ffe --- /dev/null +++ b/lib/hipe/test/opt_verify_SUITE_data/call_elim_test.erl @@ -0,0 +1,12 @@ +-module(call_elim_test). + +-export([test/0]). + +test() -> + true = has_1_field(#{1=>true}), + true = has_1_field(#{1=>"hej", b=>2}), + true = has_1_field(#{b=>3, 1=>4}), + ok. + +has_1_field(#{1:=_}) -> true; +has_1_field(#{}) -> false. diff --git a/lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_no_opt_poss.erl b/lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_no_opt_poss.erl new file mode 100644 index 0000000000..7ffae86797 --- /dev/null +++ b/lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_no_opt_poss.erl @@ -0,0 +1,32 @@ +-module(call_elim_test_branches_no_opt_poss). + +-export([test/1]). + +test(A) -> + if A > 0 -> + false = has_a_field(#{b=>true}), + true = has_a_field(#{b=>1, a=>"2"}), + false = has_a_field(#{b=>5, c=>4}), + false = has_tuple_field(#{{ab, 2}=><<"qq">>, 1 =>0}), + false = has_tuple_field(#{up =>down, {ab, 2}=>[]}), + false = has_tuple_field(#{{ab, 2}=>42}); + A =< 0 -> + true = has_a_field(#{a=>q, 'A' =>nej}), + true = has_a_field(#{a=>"hej", false=>true}), + true = has_a_field(#{a=>3}), + true = has_tuple_field(#{{ab, 1}=>q, 'A' =>nej}), + true = has_tuple_field(#{{ab, 1}=>"hej", false=>true}), + true = has_tuple_field(#{{ab, 1}=>3}) + end, + true = has_nil_field(#{[] =>3, b=>"seven"}), + true = has_nil_field(#{"seventeen"=>17}), + ok. + +has_tuple_field(#{{ab, 1}:=_}) -> true; +has_tuple_field(#{}) -> false. + +has_a_field(#{a:=_}) -> true; +has_a_field(#{}) -> false. + +has_nil_field(#{[]:=_}) -> true; +has_nil_field(#{}) -> false. diff --git a/lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_opt_poss.erl b/lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_opt_poss.erl new file mode 100644 index 0000000000..c8ddfa1e75 --- /dev/null +++ b/lib/hipe/test/opt_verify_SUITE_data/call_elim_test_branches_opt_poss.erl @@ -0,0 +1,32 @@ +-module(call_elim_test_branches_opt_poss). + +-export([test/1]). + +test(A) -> + if A > 0 -> + true = has_a_field(#{a=>true}), + true = has_a_field(#{b=>1, a=>"2"}), + true = has_a_field(#{a=>5, c=>4}), + true = has_tuple_field(#{{ab, 1}=><<"qq">>, 1 =>0}), + true = has_tuple_field(#{up =>down, {ab, 1}=>[]}), + true = has_tuple_field(#{{ab, 1}=>42}); + A =< 0 -> + true = has_a_field(#{a=>q, 'A' =>nej}), + true = has_a_field(#{a=>"hej", false=>true}), + true = has_a_field(#{a=>3}), + true = has_tuple_field(#{{ab, 1}=>q, 'A' =>nej}), + true = has_tuple_field(#{{ab, 1}=>"hej", false=>true}), + true = has_tuple_field(#{{ab, 1}=>3}) + end, + true = has_nil_field(#{[] =>3, b =>"seven"}), + true = has_nil_field(#{"seventeen"=>17, []=>nil}), + ok. + +has_tuple_field(#{{ab, 1}:=_}) -> true; +has_tuple_field(#{}) -> false. + +has_a_field(#{a:=_}) -> true; +has_a_field(#{}) -> false. + +has_nil_field(#{[]:=_}) -> true; +has_nil_field(#{}) -> false. -- cgit v1.2.3