From 64a15f2979c4644298cdad1319919fe84103484e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 15 Nov 2018 03:22:53 +0100 Subject: beam_ssa_pre_codegen: Eliminate a bottleneck in linear scan The linear scan algorithm keeps unhandled intervals in two separate lists: one for intervals with reserved registers and one for intervals without reserved registers. When collecting the available free registers all unhandled intervals with reserved registers must be checked for overlap. Unhandled intervals that had a preferred register were put into the list of intervals with reserved registers, leading to a lot of unecessary overlap checking if there were many intervals with preferred registers. Changing the partition code to put intervals with preferred registers into the general list of unhandled intervals will reduce the compilation time if there are many preferred registers. On my computer, this change reduced the time of the linear scan pass from about 20 seconds down to about 0.5 seconds for this module: https://github.com/aggelgian/cuter/blob/master/src/cuter_binlib.erl Noticed-by: Kostis Sagonas --- lib/compiler/src/beam_ssa_pre_codegen.erl | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'lib/compiler/src/beam_ssa_pre_codegen.erl') diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index 9175931375..c60c6da9ea 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -2211,7 +2211,13 @@ linear_scan(#st{intervals=Intervals0,res=Res}=St0) -> Free = init_free(maps:to_list(Res)), Intervals1 = [init_interval(Int, Res) || Int <- Intervals0], Intervals = sort(Intervals1), - IsReserved = fun (#i{reg=Reg}) -> Reg =/= none end, + IsReserved = fun(#i{reg=Reg}) -> + case Reg of + none -> false; + {prefer,{_,_}} -> false; + {_,_} -> true + end + end, {UnhandledRes,Unhandled} = partition(IsReserved, Intervals), L = #l{unhandled_res=UnhandledRes, unhandled_any=Unhandled,free=Free}, -- cgit v1.2.3