Merge branch 'margnus1/hipe/maps-is_key-opts/PR-1069/OTP-13625'

* margnus1/hipe/maps-is_key-opts/PR-1069/OTP-13625:
  hipe: Add test suite for verifying optimisations
  Added elimination of maps:is_key/2 calls to HiPE

11 files changed, 247 insertions, 22 deletions

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 <[email protected]>,
+%%           Magnus Lång <[email protected]>
+%% Created : 14 Apr 2014 by Magnus Lång <[email protected]>
+%% 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", 
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 64c5c0a7c9..03ec7adfd0 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.