aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src/sys_core_inline.erl
blob: 1e3a735e9b99ee426aa3badec8f3dad11228ead1 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2000-2010. All Rights Reserved.
%%
%% The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved online at http://www.erlang.org/.
%%
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%%
%% %CopyrightEnd%
%%
%% Purpose : Function inlining optimisation for Core.

%% This simple function inliner works in two stages:
%%
%% 1. First it extracts all the inlineable functions, either given
%% explicitly or of light enough weight, and inlines them with
%% themselves.  This inlining only uses lighter functions to save
%% recursion and a real code explosion.
%%
%% 2. Run through the rest of the functions inlining all calls to
%% inlineable functions.
%%
%% The weight function is VERY simple, we count the number of nodes in
%% the function body.  We would like to remove non-exported,
%% inlineable functions but this is not trivial as they may be
%% (mutually) recursive.
%%
%% This module will catch many access functions and allow code to use
%% extra functions for clarity which are then explicitly inlined for
%% speed with a compile attribute.  See the example below.
%%
%% It is not clear that inlining will give you very much.

-module(sys_core_inline).

-export([module/2]).

-import(lists, [member/2,map/2,foldl/3,mapfoldl/3,keydelete/3]).

-include("core_parse.hrl").

%% Inline status.
-record(inline, {exports=[],thresh=0,inline=[]}).

%% General function info.
-record(fstat, {func  :: atom(),		%Function name
		arity :: byte(),		%         arity
		def,				%Original definition
		weight=0,			%Weight
		inline=false   :: boolean(),	%Inline func flag
		modified=false :: boolean()}).	%Mod flag

%% Inlineable function info.
-record(ifun, {func  :: atom(),			%Function name
	       arity :: byte(),			%         arity
	       vars,				%Fun vars
	       body,				%    body
	       weight}).			%Weight

-spec module(#c_module{}, [_]) -> {'ok', #c_module{}}.

module(#c_module{exports=Es,defs=Ds0}=Mod, Opts) ->
    case inline_option(Opts) of
	{Thresh,Fs} when is_integer(Thresh), Thresh > 0; Fs =/= [] ->
	    case proplists:get_bool(verbose, Opts) of
		true ->
		    io:format("Old inliner: threshold=~p functions=~p\n",
			      [Thresh,Fs]);
		false -> ok
	    end,
	    Ds1 = inline(Ds0, #inline{exports=Es,thresh=Thresh,inline=Fs}),
	    {ok,Mod#c_module{defs=Ds1}};
	_Other -> {ok,Mod}
    end.
    
inline_option(Opts) ->
    foldl(fun ({inline,{_,_}=Val}, {T,Fs}) ->
		  {T,[Val|Fs]};
	      ({inline,Val}, {T,Fs}) when is_list(Val) ->
		  {T,Val ++ Fs};
	      ({inline,Val}, {_,Fs}) when is_integer(Val) ->
		  {Val,Fs};
	      (_Opt, {_,_}=Def) -> Def
	  end, {0,[]}, Opts).

%% inline([Func], Stat) -> [Func].
%%  Here we do all the work.

inline(Fs0, St0) ->
    %% Generate list of augmented functions.
    Fs1 = map(fun ({#c_var{name={F,A}},#c_fun{body=B}}=Def) ->
		      Weight = cerl_trees:fold(fun weight_func/2, 0, B),
		      #fstat{func=F,arity=A,def=Def,weight=Weight}
	      end, Fs0),
    %% Get inlineable functions, and inline them with themselves.
    {Fs2,Is0} = mapfoldl(fun (Fst, Ifs) ->
			      case is_inlineable(Fst, St0#inline.thresh,
						 St0#inline.inline) of
				  true ->
				      {_,Ffun} = Fst#fstat.def,
				      If = #ifun{func=Fst#fstat.func,
						 arity=Fst#fstat.arity,
						 vars=Ffun#c_fun.vars,
						 body=Ffun#c_fun.body,
						 weight=Fst#fstat.weight},
				      {Fst#fstat{inline=true},[If|Ifs]};
				  false -> {Fst,Ifs}
			      end
		      end, [], Fs1),
    Is1 = map(fun (#ifun{body=B}=If) ->
		      If#ifun{body=cerl_trees:map(match_fail_fun(), B)}
	      end, Is0),
    Is2 = [inline_inline(If, Is1) || If <- Is1],
    %% We would like to remove inlined, non-exported functions here,
    %% but this can be difficult as they may be recursive.
    %% Use fixed inline functions on all functions.
    Fs = [inline_func(F, Is2) || F <- Fs2],
    %% Regenerate module body.
    [Def || #fstat{def=Def} <- Fs].

%% is_inlineable(Fstat, Thresh, [Inline]) -> boolean().

is_inlineable(#fstat{weight=W}, Thresh, _Ofs) when W =< Thresh -> true;
is_inlineable(#fstat{func=F,arity=A}, _Thresh, Ofs) ->
    member({F,A}, Ofs).

%% inline_inline(Ifun, [Inline]) -> Ifun.
%%  Try to inline calls in an inlineable function.  To save us from a
%%  to great code explosion we only inline functions "smaller" than
%%  ourselves.

inline_inline(#ifun{body=B,weight=Iw}=If, Is) ->
    Inline = fun (#c_apply{op=#c_var{name={F,A}},args=As}=Call) ->
		     case find_inl(F, A, Is) of
			 #ifun{vars=Vs,body=B2,weight=W} when W < Iw ->
			     #c_let{vars=Vs,
				     arg=core_lib:make_values(As),
				    body=kill_id_anns(B2)};
			 _Other -> Call
		     end;
		 (Core) -> Core
	     end,
    If#ifun{body=cerl_trees:map(Inline, B)}.

%% inline_func(Fstat, [Inline]) -> Fstat.
%%  Try to inline calls in a normal function.  Here we inline anything
%%  in the inline list.

inline_func(#fstat{def={Name,F0}}=Fstat, Is) ->
    Inline = fun (#c_apply{op=#c_var{name={F,A}},args=As}=Call, Mod) ->
		     case find_inl(F, A, Is) of
			 #ifun{vars=Vs,body=B} ->
			     {#c_let{vars=Vs,
				     arg=core_lib:make_values(As),
				     body=kill_id_anns(B)},
			      true};			%Have modified
			 _Other -> {Call,Mod}
		     end;
		 (Core, Mod) -> {Core,Mod}
	     end,
    {F1,Mod} = cerl_trees:mapfold(Inline, false, F0),
    Fstat#fstat{def={Name,F1},modified=Mod}.

weight_func(_Core, Acc) -> Acc + 1.

%% match_fail_fun() -> fun/1.
%% Return a function to use with map to fix inlineable functions
%% function_clause match_fail (if they have one).

match_fail_fun() ->
    fun (#c_primop{anno=Anno0,name=#c_literal{val=match_fail}}=P) ->
	    Anno = keydelete(function_name, 1, Anno0),
	    P#c_primop{anno=Anno};
	(Other) -> Other
    end.

%% find_inl(Func, Arity, [Inline]) -> #ifun{} | no.

find_inl(F, A, [#ifun{func=F,arity=A}=If|_]) -> If;
find_inl(F, A, [_|Is]) -> find_inl(F, A, Is);
find_inl(_, _, []) -> no.

%% kill_id_anns(Body) -> Body'

kill_id_anns(Body) ->
    cerl_trees:map(fun(#c_fun{anno=A0}=CFun) ->
			   A = kill_id_anns_1(A0),
			   CFun#c_fun{anno=A};
		      (Expr) ->
			   %% Mark everything as compiler generated to
			   %% suppress bogus warnings.
			   A = compiler_generated(cerl:get_ann(Expr)),
			   cerl:set_ann(Expr, A)
		   end, Body).

kill_id_anns_1([{'id',_}|As]) ->
    kill_id_anns_1(As);
kill_id_anns_1([A|As]) ->
    [A|kill_id_anns_1(As)];
kill_id_anns_1([]) -> [].

compiler_generated([compiler_generated|_]=Anno) ->
    Anno;
compiler_generated(Anno) ->
    [compiler_generated|Anno -- [compiler_generated]].