1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2000-2018. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20%% Purpose : Function inlining optimisation for Core.
21
22%% This simple function inliner works in two stages:
23%%
24%% 1. First it extracts all the inlineable functions, either given
25%% explicitly or of light enough weight, and inlines them with
26%% themselves.  This inlining only uses lighter functions to save
27%% recursion and a real code explosion.
28%%
29%% 2. Run through the rest of the functions inlining all calls to
30%% inlineable functions.
31%%
32%% The weight function is VERY simple, we count the number of nodes in
33%% the function body.  We would like to remove non-exported,
34%% inlineable functions but this is not trivial as they may be
35%% (mutually) recursive.
36%%
37%% This module will catch many access functions and allow code to use
38%% extra functions for clarity which are then explicitly inlined for
39%% speed with a compile attribute.  See the example below.
40%%
41%% It is not clear that inlining will give you very much.
42
43-module(sys_core_inline).
44
45-export([module/2]).
46
47-import(lists, [member/2,map/2,foldl/3,mapfoldl/3,keydelete/3]).
48
49-include("core_parse.hrl").
50
51%% Inline status.
52-record(inline, {exports=[],thresh=0,inline=[]}).
53
54%% General function info.
55-record(fstat, {func  :: atom(),		%Function name
56		arity :: byte(),		%         arity
57		def,				%Original definition
58		weight=0,			%Weight
59		inline=false   :: boolean(),	%Inline func flag
60		modified=false :: boolean()}).	%Mod flag
61
62%% Inlineable function info.
63-record(ifun, {func  :: atom(),			%Function name
64	       arity :: byte(),			%         arity
65	       vars,				%Fun vars
66	       body,				%    body
67	       weight}).			%Weight
68
69-spec module(#c_module{}, [_]) -> {'ok', #c_module{}}.
70
71module(#c_module{exports=Es,defs=Ds0}=Mod, Opts) ->
72    case inline_option(Opts) of
73	{Thresh,Fs} when is_integer(Thresh), Thresh > 0; Fs =/= [] ->
74	    case proplists:get_bool(verbose, Opts) of
75		true ->
76		    io:format("Old inliner: threshold=~p functions=~p\n",
77			      [Thresh,Fs]);
78		false -> ok
79	    end,
80	    Ds1 = inline(Ds0, #inline{exports=Es,thresh=Thresh,inline=Fs}),
81	    {ok,Mod#c_module{defs=Ds1}};
82	_Other -> {ok,Mod}
83    end.
84
85inline_option(Opts) ->
86    foldl(fun ({inline,{_,_}=Val}, {T,Fs}) ->
87		  {T,[Val|Fs]};
88	      ({inline,Val}, {T,Fs}) when is_list(Val) ->
89		  {T,Val ++ Fs};
90	      ({inline,Val}, {_,Fs}) when is_integer(Val) ->
91		  {Val,Fs};
92	      (_Opt, {_,_}=Def) -> Def
93	  end, {0,[]}, Opts).
94
95%% inline([Func], Stat) -> [Func].
96%%  Here we do all the work.
97
98inline(Fs0, St0) ->
99    %% Generate list of augmented functions.
100    Fs1 = map(fun ({#c_var{name={F,A}},#c_fun{body=B}}=Def) ->
101		      Weight = cerl_trees:fold(fun weight_func/2, 0, B),
102		      #fstat{func=F,arity=A,def=Def,weight=Weight}
103	      end, Fs0),
104    %% Get inlineable functions, and inline them with themselves.
105    {Fs2,Is0} = mapfoldl(fun (Fst, Ifs) ->
106			      case is_inlineable(Fst, St0#inline.thresh,
107						 St0#inline.inline) of
108				  true ->
109				      {_,Ffun} = Fst#fstat.def,
110				      If = #ifun{func=Fst#fstat.func,
111						 arity=Fst#fstat.arity,
112						 vars=Ffun#c_fun.vars,
113						 body=Ffun#c_fun.body,
114						 weight=Fst#fstat.weight},
115				      {Fst#fstat{inline=true},[If|Ifs]};
116				  false -> {Fst,Ifs}
117			      end
118		      end, [], Fs1),
119    Is1 = map(fun (#ifun{body=B}=If) ->
120		      If#ifun{body=cerl_trees:map(match_fail_fun(), B)}
121	      end, Is0),
122    Is2 = [inline_inline(If, Is1) || If <- Is1],
123    %% We would like to remove inlined, non-exported functions here,
124    %% but this can be difficult as they may be recursive.
125    %% Use fixed inline functions on all functions.
126    Fs = [inline_func(F, Is2) || F <- Fs2],
127    %% Regenerate module body.
128    [Def || #fstat{def=Def} <- Fs].
129
130%% is_inlineable(Fstat, Thresh, [Inline]) -> boolean().
131
132is_inlineable(#fstat{weight=W}, Thresh, _Ofs) when W =< Thresh -> true;
133is_inlineable(#fstat{func=F,arity=A}, _Thresh, Ofs) ->
134    member({F,A}, Ofs).
135
136%% inline_inline(Ifun, [Inline]) -> Ifun.
137%%  Try to inline calls in an inlineable function.  To save us from a
138%%  to great code explosion we only inline functions "smaller" than
139%%  ourselves.
140
141inline_inline(#ifun{body=B,weight=Iw}=If, Is) ->
142    Inline = fun (#c_apply{op=#c_var{name={F,A}},args=As}=Call) ->
143		     case find_inl(F, A, Is) of
144			 #ifun{vars=Vs,body=B2,weight=W} when W < Iw ->
145			     #c_let{vars=Vs,
146				     arg=kill_id_anns(core_lib:make_values(As)),
147				    body=kill_id_anns(B2)};
148			 _Other -> Call
149		     end;
150		 (Core) -> Core
151	     end,
152    If#ifun{body=cerl_trees:map(Inline, B)}.
153
154%% inline_func(Fstat, [Inline]) -> Fstat.
155%%  Try to inline calls in a normal function.  Here we inline anything
156%%  in the inline list.
157
158inline_func(#fstat{def={Name,F0}}=Fstat, Is) ->
159    Inline = fun (#c_apply{op=#c_var{name={F,A}},args=As}=Call, Mod) ->
160		     case find_inl(F, A, Is) of
161			 #ifun{vars=Vs,body=B} ->
162			     {#c_let{vars=Vs,
163				     arg=kill_id_anns(core_lib:make_values(As)),
164				     body=kill_id_anns(B)},
165			      true};			%Have modified
166			 _Other -> {Call,Mod}
167		     end;
168		 (Core, Mod) -> {Core,Mod}
169	     end,
170    {F1,Mod} = cerl_trees:mapfold(Inline, false, F0),
171    Fstat#fstat{def={Name,F1},modified=Mod}.
172
173weight_func(_Core, Acc) -> Acc + 1.
174
175%% match_fail_fun() -> fun/1.
176%% Return a function to use with map to fix inlineable functions
177%% function_clause match_fail (if they have one).
178
179match_fail_fun() ->
180    fun (#c_primop{anno=Anno0,name=#c_literal{val=match_fail}}=P) ->
181	    Anno = keydelete(function_name, 1, Anno0),
182	    P#c_primop{anno=Anno};
183	(Other) -> Other
184    end.
185
186%% find_inl(Func, Arity, [Inline]) -> #ifun{} | no.
187
188find_inl(F, A, [#ifun{func=F,arity=A}=If|_]) -> If;
189find_inl(F, A, [_|Is]) -> find_inl(F, A, Is);
190find_inl(_, _, []) -> no.
191
192%% kill_id_anns(Body) -> Body'
193
194kill_id_anns(Body) ->
195    cerl_trees:map(fun(#c_fun{anno=A0}=CFun) ->
196			   A = kill_id_anns_1(A0),
197			   CFun#c_fun{anno=A};
198		      (Expr) ->
199			   %% Mark everything as compiler generated to
200			   %% suppress bogus warnings.
201			   A = compiler_generated(cerl:get_ann(Expr)),
202			   cerl:set_ann(Expr, A)
203		   end, Body).
204
205kill_id_anns_1([{'id',_}|As]) ->
206    kill_id_anns_1(As);
207kill_id_anns_1([A|As]) ->
208    [A|kill_id_anns_1(As)];
209kill_id_anns_1([]) -> [].
210
211compiler_generated([compiler_generated|_]=Anno) ->
212    Anno;
213compiler_generated(Anno) ->
214    [compiler_generated|Anno -- [compiler_generated]].
215