v3_life: Optimize updating of the variable data base

Updating of the variable data base takes most of the time.

1 files changed, 53 insertions, 64 deletions

diff --git a/lib/compiler/src/v3_life.erl b/lib/compiler/src/v3_life.erl
index 75bd188479..4b1f1c3f71 100644
--- a/lib/compiler/src/v3_life.erl
+++ b/lib/compiler/src/v3_life.erl
@@ -45,7 +45,7 @@
 
 -export([vdb_find/2]).
 
--import(lists, [member/2,map/2,foldl/3,reverse/1,sort/1]).
+-import(lists, [member/2,map/2,reverse/1,sort/1]).
 -import(ordsets, [add_element/2,intersection/2,union/2]).
 
 -include("v3_kernel.hrl").
@@ -68,7 +68,7 @@ functions([], Acc) -> reverse(Acc).
 function(#k_fdef{anno=#k{a=Anno},func=F,arity=Ar,vars=Vs,body=Kb}) ->
     try
 	As = var_list(Vs),
-	Vdb0 = foldl(fun ({var,N}, Vdb) -> new_var(N, 0, Vdb) end, [], As),
+	Vdb0 = init_vars(As),
 	%% Force a top-level match!
 	B0 = case Kb of
 		 #k_match{} -> Kb;
@@ -94,14 +94,14 @@ function(#k_fdef{anno=#k{a=Anno},func=F,arity=Ar,vars=Vs,body=Kb}) ->
 body(#k_seq{arg=Ke,body=Kb}, I, Vdb0) ->
     %%ok = io:fwrite("life ~w:~p~n", [?LINE,{Ke,I,Vdb0}]),
     A = get_kanno(Ke),
-    Vdb1 = use_vars(A#k.us, I, new_vars(A#k.ns, I, Vdb0)),
+    Vdb1 = use_vars(union(A#k.us, A#k.ns), I, Vdb0),
     {Es,MaxI,Vdb2} = body(Kb, I+1, Vdb1),
     E = expr(Ke, I, Vdb2),
     {[E|Es],MaxI,Vdb2};
 body(Ke, I, Vdb0) ->
     %%ok = io:fwrite("life ~w:~p~n", [?LINE,{Ke,I,Vdb0}]),
     A = get_kanno(Ke),
-    Vdb1 = use_vars(A#k.us, I, new_vars(A#k.ns, I, Vdb0)),
+    Vdb1 = use_vars(union(A#k.us, A#k.ns), I, Vdb0),
     E = expr(Ke, I, Vdb1),
     {[E],I,Vdb1}.
 
@@ -150,12 +150,12 @@ expr(#k_try_enter{anno=A,arg=Ka,vars=Vs,body=Kb,evars=Evs,handler=Kh}, I, Vdb) -
     %% the body and handler. Add try tag 'variable'.
     Ab = get_kanno(Kb),
     Ah = get_kanno(Kh),
-    Tdb1 = use_vars(Ab#k.us, I+3, use_vars(Ah#k.us, I+3, Tdb0)),
+    Tdb1 = use_vars(union(Ab#k.us, Ah#k.us), I+3, Tdb0),
     Tdb2 = vdb_sub(I, I+2, Tdb1),
     Vnames = fun (Kvar) -> Kvar#k_var.name end,	%Get the variable names
     {Aes,_,Adb} = body(Ka, I+2, add_var({catch_tag,I+1}, I+1, 1000000, Tdb2)),
-    {Bes,_,Bdb} = body(Kb, I+4, new_vars(map(Vnames, Vs), I+3, Tdb2)),
-    {Hes,_,Hdb} = body(Kh, I+4, new_vars(map(Vnames, Evs), I+3, Tdb2)),
+    {Bes,_,Bdb} = body(Kb, I+4, new_vars(sort(map(Vnames, Vs)), I+3, Tdb2)),
+    {Hes,_,Hdb} = body(Kh, I+4, new_vars(sort(map(Vnames, Evs)), I+3, Tdb2)),
     #l{ke={try_enter,#l{ke={block,Aes},i=I+1,vdb=Adb,a=[]},
 	   var_list(Vs),#l{ke={block,Bes},i=I+3,vdb=Bdb,a=[]},
 	   var_list(Evs),#l{ke={block,Hes},i=I+3,vdb=Hdb,a=[]}},
@@ -171,7 +171,7 @@ expr(#k_receive{anno=A,var=V,body=Kb,timeout=T,action=Ka,ret=Rs}, I, Vdb) ->
     %% Work out imported variables which need to be locked.
     Rdb = vdb_sub(I, I+1, Vdb),
     M = match(Kb, add_element(V#k_var.name, A#k.us), I+1, [],
- 	      new_var(V#k_var.name, I, Rdb)),
+	      new_vars([V#k_var.name], I, Rdb)),
     {Tes,_,Adb} = body(Ka, I+1, Rdb),
     #l{ke={receive_loop,atomic(T),variable(V),M,
 	   #l{ke=Tes,i=I+1,vdb=Adb,a=[]},var_list(Rs)},
@@ -199,12 +199,12 @@ body_try(#k_try{anno=A,arg=Ka,vars=Vs,body=Kb,evars=Evs,handler=Kh,ret=Rs},
     %% the body and handler. Add try tag 'variable'.
     Ab = get_kanno(Kb),
     Ah = get_kanno(Kh),
-    Tdb1 = use_vars(Ab#k.us, I+3, use_vars(Ah#k.us, I+3, Tdb0)),
+    Tdb1 = use_vars(union(Ab#k.us, Ah#k.us), I+3, Tdb0),
     Tdb2 = vdb_sub(I, I+2, Tdb1),
     Vnames = fun (Kvar) -> Kvar#k_var.name end,	%Get the variable names
     {Aes,_,Adb} = body(Ka, I+2, add_var({catch_tag,I+1}, I+1, locked, Tdb2)),
-    {Bes,_,Bdb} = body(Kb, I+4, new_vars(map(Vnames, Vs), I+3, Tdb2)),
-    {Hes,_,Hdb} = body(Kh, I+4, new_vars(map(Vnames, Evs), I+3, Tdb2)),
+    {Bes,_,Bdb} = body(Kb, I+4, new_vars(sort(map(Vnames, Vs)), I+3, Tdb2)),
+    {Hes,_,Hdb} = body(Kh, I+4, new_vars(sort(map(Vnames, Evs)), I+3, Tdb2)),
     #l{ke={'try',#l{ke={block,Aes},i=I+1,vdb=Adb,a=[]},
 	   var_list(Vs),#l{ke={block,Bes},i=I+3,vdb=Bdb,a=[]},
 	   var_list(Evs),#l{ke={block,Hes},i=I+3,vdb=Hdb,a=[]},
@@ -400,79 +400,68 @@ is_gc_bif(Bif, Arity) ->
 	 erl_internal:new_type_test(Bif, Arity) orelse
 	 erl_internal:comp_op(Bif, Arity)).
 
-%% new_var(VarName, I, Vdb) -> Vdb.
+%% Keep track of life time for variables.
+%%
+%% init_vars([{var,VarName}]) -> Vdb.
 %% new_vars([VarName], I, Vdb) -> Vdb.
-%% use_var(VarName, I, Vdb) -> Vdb.
 %% use_vars([VarName], I, Vdb) -> Vdb.
 %% add_var(VarName, F, L, Vdb) -> Vdb.
+%%
+%% The list of variable names for new_vars/3 and use_vars/3
+%% must be sorted.
 
-new_var(V, I, Vdb) ->
-    vdb_store_new(V, I, I, Vdb).
+init_vars(Vs) ->
+    sort([{V,0,0} || {var,V} <- Vs]).
 
-new_vars(Vs, I, Vdb0) ->
-    foldl(fun (V, Vdb) -> new_var(V, I, Vdb) end, Vdb0, Vs).
+new_vars([], _, Vdb) -> Vdb;
+new_vars([V], I, Vdb) -> vdb_store_new(V, {V,I,I}, Vdb);
+new_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I).
 
-use_var(V, I, Vdb) ->
+use_vars([], _, Vdb) ->
+    Vdb;
+use_vars([V], I, Vdb) ->
     case vdb_find(V, Vdb) of
-	{V,F,L} when I > L -> vdb_update(V, F, I, Vdb);
+	{V,F,L} when I > L -> vdb_update(V, {V,F,I}, Vdb);
 	{V,_,_} -> Vdb;
-	error -> vdb_store_new(V, I, I, Vdb)
-    end.
-
-use_vars([], _, Vdb) -> Vdb;
-use_vars([V], I, Vdb) -> use_var(V, I, Vdb);
-use_vars(Vs, I, Vdb) ->
-    Res = use_vars_1(sort(Vs), Vdb, I),
-    %% The following line can be used as an assertion.
-    %%   Res = foldl(fun (V, Vdb) -> use_var(V, I, Vdb) end, Vdb, Vs),
-    Res.
-
-%% Measurements show that it is worthwhile having this special
-%% function that updates/inserts several variables at once.
-
-use_vars_1([V|_]=Vs, [{V1,_,_}=Vd|Vdb], I) when V > V1 ->
-    [Vd|use_vars_1(Vs, Vdb, I)];
-use_vars_1([V|Vs], [{V1,_,_}|_]=Vdb, I) when V < V1 ->
-    %% New variable.
-    [{V,I,I}|use_vars_1(Vs, Vdb, I)];
-use_vars_1([V|Vs], [{_,F,L}=Vd|Vdb], I) ->
-    %% Existing variable.
-    if
-	I > L ->[{V,F,I}|use_vars_1(Vs, Vdb, I)];
-	true -> [Vd|use_vars_1(Vs, Vdb, I)]
+	error -> vdb_store_new(V, {V,I,I}, Vdb)
     end;
-use_vars_1([V|Vs], [], I) ->
-    %% New variable.
-    [{V,I,I}|use_vars_1(Vs, [], I)];
-use_vars_1([], Vdb, _) -> Vdb.
+use_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I).
 
 add_var(V, F, L, Vdb) ->
-    vdb_store_new(V, F, L, Vdb).
+    vdb_store_new(V, {V,F,L}, Vdb).
 
 vdb_find(V, Vdb) ->
-    %% Performance note: Profiling shows that this function accounts for
-    %% a lot of the execution time when huge constant terms are built.
-    %% Using the BIF lists:keyfind/3 is a lot faster than the
-    %% original Erlang version.
     case lists:keyfind(V, 1, Vdb) of
 	false -> error;
 	Vd -> Vd
     end.
 
-%vdb_find(V, [{V1,F,L}=Vd|Vdb]) when V < V1 -> error;
-%vdb_find(V, [{V1,F,L}=Vd|Vdb]) when V == V1 -> Vd;
-%vdb_find(V, [{V1,F,L}=Vd|Vdb]) when V > V1 -> vdb_find(V, Vdb);
-%vdb_find(V, []) -> error.
+vdb_update(V, Update, [{V,_,_}|Vdb]) ->
+    [Update|Vdb];
+vdb_update(V, Update, [Vd|Vdb]) ->
+    [Vd|vdb_update(V, Update, Vdb)].
 
-vdb_update(V, F, L, [{V1,_,_}=Vd|Vdb]) when V > V1 ->
-    [Vd|vdb_update(V, F, L, Vdb)];
-vdb_update(V, F, L, [{V1,_,_}|Vdb]) when V == V1 ->
-    [{V,F,L}|Vdb].
+vdb_store_new(V, New, [{V1,_,_}=Vd|Vdb]) when V > V1 ->
+    [Vd|vdb_store_new(V, New, Vdb)];
+vdb_store_new(V, New, [{V1,_,_}|_]=Vdb) when V < V1 ->
+    [New|Vdb];
+vdb_store_new(_, New, []) -> [New].
 
-vdb_store_new(V, F, L, [{V1,_,_}=Vd|Vdb]) when V > V1 ->
-    [Vd|vdb_store_new(V, F, L, Vdb)];
-vdb_store_new(V, F, L, [{V1,_,_}|_]=Vdb) when V < V1 -> [{V,F,L}|Vdb];
-vdb_store_new(V, F, L, []) -> [{V,F,L}].
+vdb_update_vars([V|_]=Vs, [{V1,_,_}=Vd|Vdb], I) when V > V1 ->
+    [Vd|vdb_update_vars(Vs, Vdb, I)];
+vdb_update_vars([V|Vs], [{V1,_,_}|_]=Vdb, I) when V < V1 ->
+    %% New variable.
+    [{V,I,I}|vdb_update_vars(Vs, Vdb, I)];
+vdb_update_vars([V|Vs], [{_,F,L}=Vd|Vdb], I) ->
+    %% Existing variable.
+    if
+	I > L -> [{V,F,I}|vdb_update_vars(Vs, Vdb, I)];
+	true ->  [Vd|vdb_update_vars(Vs, Vdb, I)]
+    end;
+vdb_update_vars([V|Vs], [], I) ->
+    %% New variable.
+    [{V,I,I}|vdb_update_vars(Vs, [], I)];
+vdb_update_vars([], Vdb, _) -> Vdb.
 
 %% vdb_sub(Min, Max, Vdb) -> Vdb.
 %%  Extract variables which are used before and after Min.  Lock