Fix slow compilation of complex guards

beam_utils:is_not_used_at/3 could be very slow for complex guards,
because the cached result for previously encountered labels were
neither used nor updated within blocks.

Reported-by: Magnus Müller

2 files changed, 81 insertions, 46 deletions

diff --git a/lib/compiler/src/beam_utils.erl b/lib/compiler/src/beam_utils.erl
index 8af0447f63..554c14f57a 100644
--- a/lib/compiler/src/beam_utils.erl
+++ b/lib/compiler/src/beam_utils.erl
@@ -61,7 +61,7 @@ is_killed_block(R, Is) ->
 %%  to determine the kill state across branches.
 
 is_killed(R, Is, D) ->
-    St = #live{bl=fun check_killed_block/2,lbl=D,res=gb_trees:empty()},
+    St = #live{bl=check_killed_block_fun(),lbl=D,res=gb_trees:empty()},
     case check_liveness(R, Is, St) of
 	{killed,_} -> true;
 	{used,_} -> false;
@@ -72,7 +72,7 @@ is_killed(R, Is, D) ->
 %%  Determine whether Reg is killed at label Lbl.
 
 is_killed_at(R, Lbl, D) when is_integer(Lbl) ->
-    St0 = #live{bl=fun check_killed_block/2,lbl=D,res=gb_trees:empty()},
+    St0 = #live{bl=check_killed_block_fun(),lbl=D,res=gb_trees:empty()},
     case check_liveness_at(R, Lbl, St0) of
 	{killed,_} -> true;
 	{used,_} -> false;
@@ -87,7 +87,7 @@ is_killed_at(R, Lbl, D) when is_integer(Lbl) ->
 %%  across branches.
 
 is_not_used(R, Is, D) ->
-    St = #live{bl=check_used_block_fun(D),lbl=D,res=gb_trees:empty()},
+    St = #live{bl=fun check_used_block/3,lbl=D,res=gb_trees:empty()},
     case check_liveness(R, Is, St) of
 	{killed,_} -> true;
 	{used,_} -> false;
@@ -102,7 +102,7 @@ is_not_used(R, Is, D) ->
 %%  across branches.
 
 is_not_used_at(R, Lbl, D) ->
-    St = #live{bl=check_used_block_fun(D),lbl=D,res=gb_trees:empty()},
+    St = #live{bl=fun check_used_block/3,lbl=D,res=gb_trees:empty()},
     case check_liveness_at(R, Lbl, St) of
 	{killed,_} -> true;
 	{used,_} -> false;
@@ -246,10 +246,10 @@ combine_heap_needs(H1, H2) when is_integer(H1), is_integer(H2) ->
 
 check_liveness(R, [{set,_,_,_}=I|_], St) ->
     erlang:error(only_allowed_in_blocks, [R,I,St]);
-check_liveness(R, [{block,Blk}|Is], #live{bl=BlockCheck}=St) ->
-    case BlockCheck(R, Blk) of
-	transparent -> check_liveness(R, Is, St);
-	Other when is_atom(Other) -> {Other,St}
+check_liveness(R, [{block,Blk}|Is], #live{bl=BlockCheck}=St0) ->
+    case BlockCheck(R, Blk, St0) of
+	{transparent,St} -> check_liveness(R, Is, St);
+	{Other,_}=Res when is_atom(Other) -> Res
     end;
 check_liveness(R, [{label,_}|Is], St) ->
     check_liveness(R, Is, St);
@@ -533,6 +533,9 @@ check_liveness_fail(R, Op, Args, Fail, St) ->
 %%  
 %%    (Unknown instructions will cause an exception.)
 
+check_killed_block_fun() ->
+    fun(R, Is, St) -> {check_killed_block(R, Is),St} end.
+
 check_killed_block({x,X}, [{set,_,_,{alloc,Live,_}}|_]) ->
     if 
 	X >= Live -> killed;
@@ -563,50 +566,51 @@ check_killed_block(_, []) -> transparent.
 %%  
 %%    (Unknown instructions will cause an exception.)
 
-check_used_block_fun(D) ->
-    fun(R, Is) -> check_used_block(R, Is, D) end.
-
-check_used_block({x,X}=R, [{set,Ds,Ss,{alloc,Live,Op}}|Is], D) ->
+check_used_block({x,X}=R, [{set,Ds,Ss,{alloc,Live,Op}}|Is], St) ->
     if 
-	X >= Live -> killed;
+	X >= Live -> {killed,St};
+	true -> check_used_block_1(R, Ss, Ds, Op, Is, St)
+    end;
+check_used_block(R, [{set,Ds,Ss,Op}|Is], St) ->
+    check_used_block_1(R, Ss, Ds, Op, Is, St);
+check_used_block(R, [{'%live',Live}|Is], St) ->
+    case R of
+	{x,X} when X >= Live -> {killed,St};
+	_ -> check_used_block(R, Is, St)
+    end;
+check_used_block(_, [], St) -> {transparent,St}.
+
+check_used_block_1(R, Ss, Ds, Op, Is, St0) ->
+    case member(R, Ss) of
 	true ->
-	    case member(R, Ss) orelse
-		is_reg_used_at(R, Op, D) of
-		true -> used;
-		false ->
+	    {used,St0};
+	false ->
+	    case is_reg_used_at(R, Op, St0) of
+		{true,St} ->
+		    {used,St};
+		{false,St} ->
 		    case member(R, Ds) of
-			true -> killed;
-			false -> check_used_block(R, Is, D)
+			true -> {killed,St};
+			false -> check_used_block(R, Is, St)
 		    end
 	    end
-    end;
-check_used_block(R, [{set,Ds,Ss,Op}|Is], D) ->
-    case member(R, Ss) orelse
-	is_reg_used_at(R, Op, D) of
-	true -> used;
-	false ->
-	    case member(R, Ds) of
-		true -> killed;
-		false -> check_used_block(R, Is, D)
-	    end
-    end;
-check_used_block(R, [{'%live',Live}|Is], D) ->
-    case R of
-	{x,X} when X >= Live -> killed;
-	_ -> check_used_block(R, Is, D)
-    end;
-check_used_block(_, [], _) -> transparent.
+    end.
 
-is_reg_used_at(R, {gc_bif,_,{f,Lbl}}, D) ->
-    is_reg_used_at_1(R, Lbl, D);
-is_reg_used_at(R, {bif,_,{f,Lbl}}, D) ->
-    is_reg_used_at_1(R, Lbl, D);
-is_reg_used_at(_, _, _) -> false.
+is_reg_used_at(R, {gc_bif,_,{f,Lbl}}, St) ->
+    is_reg_used_at_1(R, Lbl, St);
+is_reg_used_at(R, {bif,_,{f,Lbl}}, St) ->
+    is_reg_used_at_1(R, Lbl, St);
+is_reg_used_at(_, _, St) ->
+    {false,St}.
 
-is_reg_used_at_1(_, 0, _) ->
-    false;
-is_reg_used_at_1(R, Lbl, D) ->
-    not is_not_used_at(R, Lbl, D).
+is_reg_used_at_1(_, 0, St) ->
+    {false,St};
+is_reg_used_at_1(R, Lbl, St0) ->
+    case check_liveness_at(R, Lbl, St0) of
+	{killed,St} -> {false,St};
+	{used,St} -> {true,St};
+	{unknown,St} -> {true,St}
+    end.
 
 index_labels_1([{label,Lbl}|Is0], Acc) ->
     Is = lists:dropwhile(fun({label,_}) -> true;
diff --git a/lib/compiler/test/andor_SUITE.erl b/lib/compiler/test/andor_SUITE.erl
index 0d00769704..4ffbe07e32 100644
--- a/lib/compiler/test/andor_SUITE.erl
+++ b/lib/compiler/test/andor_SUITE.erl
@@ -21,7 +21,8 @@
 -export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1, 
 	 init_per_group/2,end_per_group/2,
 	 t_case/1,t_and_or/1,t_andalso/1,t_orelse/1,inside/1,overlap/1,
-	 combined/1,in_case/1,before_and_inside_if/1]).
+	 combined/1,in_case/1,before_and_inside_if/1,
+	 slow_compilation/1]).
 	 
 -include_lib("test_server/include/test_server.hrl").
 
@@ -472,6 +473,36 @@ before_and_inside_if_2(XDo1, XDo2, Do3) ->
 	  end,
     {CH1,CH2}.
 
+
+-record(state, {stack = []}).
+
+slow_compilation(_) ->
+    %% The function slow_compilation_1 used to compile very slowly.
+    ok = slow_compilation_1({a}, #state{}).
+
+slow_compilation_1(T1, #state{stack = [T2|_]})
+    when element(1, T2) == a, element(1, T1) == b, element(1, T1) == c ->
+    ok;
+slow_compilation_1(T, _)
+    when element(1, T) == a1; element(1, T) == b1; element(1, T) == c1 ->
+    ok;
+slow_compilation_1(T, _)
+    when element(1, T) == a2; element(1, T) == b2; element(1, T) == c2 ->
+    ok;
+slow_compilation_1(T, _) when element(1, T) == a ->
+    ok;
+slow_compilation_1(T, _)
+    when
+        element(1, T) == a,
+        (element(1, T) == b) and (element(1, T) == c) ->
+    ok;
+slow_compilation_1(_, T) when element(1, T) == a ->
+    ok;
+slow_compilation_1(_, T) when element(1, T) == b ->
+    ok;
+slow_compilation_1(T, _) when element(1, T) == a ->
+    ok.
+
 %% Utilities.
 
 check(V1, V0) ->