aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2018-11-15 03:22:53 +0100
committerBjörn Gustavsson <[email protected]>2018-11-15 14:07:50 +0100
commit64a15f2979c4644298cdad1319919fe84103484e (patch)
treefc8e55da51797f5b8f386b5742c6ebf00df5ea53 /lib/compiler/src
parent693cda7f01137eda93362a74abd6028c41d2f5c6 (diff)
downloadotp-64a15f2979c4644298cdad1319919fe84103484e.tar.gz
otp-64a15f2979c4644298cdad1319919fe84103484e.tar.bz2
otp-64a15f2979c4644298cdad1319919fe84103484e.zip
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
Diffstat (limited to 'lib/compiler/src')
-rw-r--r--lib/compiler/src/beam_ssa_pre_codegen.erl8
1 files changed, 7 insertions, 1 deletions
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},