1%% ``Licensed under the Apache License, Version 2.0 (the "License");
2%% you may not use this file except in compliance with the License.
3%% You may obtain a copy of the License at
4%%
5%%     http://www.apache.org/licenses/LICENSE-2.0
6%%
7%% Unless required by applicable law or agreed to in writing, software
8%% distributed under the License is distributed on an "AS IS" BASIS,
9%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
10%% See the License for the specific language governing permissions and
11%% limitations under the License.
12%%
13%% The Initial Developer of the Original Code is Ericsson Utvecklings AB.
14%% Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
15%% AB. All Rights Reserved.''
16%%
17%%     $Id: beam_clean.erl,v 1.1 2008/12/17 09:53:41 mikpe Exp $
18%%
19%% Purpose : Clean up, such as removing unused labels and unused functions.
20
21-module(beam_clean).
22
23-export([module/2]).
24-import(lists, [member/2,map/2,foldl/3,mapfoldl/3,reverse/1]).
25
26module({Mod,Exp,Attr,Fs0,_}, _Opt) ->
27    Order = [Lbl || {function,_,_,Lbl,_} <- Fs0],
28    All = foldl(fun({function,_,_,Lbl,_}=Func,D) -> dict:store(Lbl, Func, D) end,
29		dict:new(), Fs0),
30    {WorkList,Used0} = exp_to_labels(Fs0, Exp),
31    Used = find_all_used(WorkList, All, Used0),
32    Fs1 = remove_unused(Order, Used, All),
33    {Fs,Lc} = clean_labels(Fs1),
34    {ok,{Mod,Exp,Attr,Fs,Lc}}.
35
36%% Convert the export list ({Name,Arity} pairs) to a list of entry labels.
37
38exp_to_labels(Fs, Exp) -> exp_to_labels(Fs, Exp, [], sets:new()).
39
40exp_to_labels([{function,Name,Arity,Lbl,_}|Fs], Exp, Acc, Used) ->
41    case member({Name,Arity}, Exp) of
42	true -> exp_to_labels(Fs, Exp, [Lbl|Acc], sets:add_element(Lbl, Used));
43	false -> exp_to_labels(Fs, Exp, Acc, Used)
44    end;
45exp_to_labels([], _, Acc, Used) -> {Acc,Used}.
46
47%% Remove the unused functions.
48
49remove_unused([F|Fs], Used, All) ->
50    case sets:is_element(F, Used) of
51	false -> remove_unused(Fs, Used, All);
52	true -> [dict:fetch(F, All)|remove_unused(Fs, Used, All)]
53    end;
54remove_unused([], _, _) -> [].
55
56%% Find all used functions.
57
58find_all_used([F|Fs0], All, Used0) ->
59    {function,_,_,_,Code} = dict:fetch(F, All),
60    {Fs,Used} = update_work_list(Code, {Fs0,Used0}),
61    find_all_used(Fs, All, Used);
62find_all_used([], _All, Used) -> Used.
63
64update_work_list([{call,_,{f,L}}|Is], Sets) ->
65    update_work_list(Is, add_to_work_list(L, Sets));
66update_work_list([{call_last,_,{f,L},_}|Is], Sets) ->
67    update_work_list(Is, add_to_work_list(L, Sets));
68update_work_list([{call_only,_,{f,L}}|Is], Sets) ->
69    update_work_list(Is, add_to_work_list(L, Sets));
70update_work_list([{make_fun,{f,L},_,_}|Is], Sets) ->
71    update_work_list(Is, add_to_work_list(L, Sets));
72update_work_list([{make_fun2,{f,L},_,_,_}|Is], Sets) ->
73    update_work_list(Is, add_to_work_list(L, Sets));
74update_work_list([_|Is], Sets) ->
75    update_work_list(Is, Sets);
76update_work_list([], Sets) -> Sets.
77
78add_to_work_list(F, {Fs,Used}=Sets) ->
79    case sets:is_element(F, Used) of
80	true -> Sets;
81	false -> {[F|Fs],sets:add_element(F, Used)}
82    end.
83
84
85%%%
86%%% Coalesce adjacent labels. Renumber all labels to eliminate gaps.
87%%% This cleanup will slightly reduce file size and slightly speed up loading.
88%%%
89%%% We also expand internal_is_record/3 to a sequence of instructions. It is done
90%%% here merely because this module will always be called even if optimization
91%%% is turned off. We don't want to do the expansion in beam_asm because we
92%%% want to see the expanded code in a .S file.
93%%%
94
95-record(st, {lmap,				%Translation tables for labels.
96	     entry,				%Number of entry label.
97	     lc					%Label counter
98	     }).
99
100clean_labels(Fs0) ->
101    St0 = #st{lmap=dict:new(),lc=1},
102    {Fs1,#st{lmap=Lmap,lc=Lc}} = mapfoldl(fun function_renumber/2, St0, Fs0),
103    {map(fun(F) -> function_replace(F, Lmap) end, Fs1),Lc}.
104
105function_renumber({function,Name,Arity,_Entry,Asm0}, St0) ->
106    {Asm,St} = renumber_labels(Asm0, [], St0),
107    {{function,Name,Arity,St#st.entry,Asm},St}.
108
109renumber_labels([{bif,internal_is_record,{f,_},
110		  [Term,Tag,{integer,Arity}],Dst}|Is], Acc, St) ->
111    ContLabel = 900000000+2*St#st.lc,
112    FailLabel = ContLabel+1,
113    Fail = {f,FailLabel},
114    Tmp = Dst,
115    renumber_labels([{test,is_tuple,Fail,[Term]},
116		     {test,test_arity,Fail,[Term,Arity]},
117		     {get_tuple_element,Term,0,Tmp},
118		     {test,is_eq_exact,Fail,[Tmp,Tag]},
119		     {move,{atom,true},Dst},
120		     {jump,{f,ContLabel}},
121		     {label,FailLabel},
122		     {move,{atom,false},Dst},
123		     {label,ContLabel}|Is], Acc, St);
124renumber_labels([{test,internal_is_record,{f,_}=Fail,
125		  [Term,Tag,{integer,Arity}]}|Is], Acc, St) ->
126    Tmp = {x,1023},
127    case Term of
128	{Reg,_} when Reg == x; Reg == y ->
129	    renumber_labels([{test,is_tuple,Fail,[Term]},
130			     {test,test_arity,Fail,[Term,Arity]},
131			     {get_tuple_element,Term,0,Tmp},
132			     {test,is_eq_exact,Fail,[Tmp,Tag]}|Is], Acc, St);
133	_ ->
134	    renumber_labels([{jump,Fail}|Is], Acc, St)
135    end;
136renumber_labels([{label,Old}|Is], [{label,New}|_]=Acc, #st{lmap=D0}=St) ->
137    D = dict:store(Old, New, D0),
138    renumber_labels(Is, Acc, St#st{lmap=D});
139renumber_labels([{label,Old}|Is], Acc, St0) ->
140    New = St0#st.lc,
141    D = dict:store(Old, New, St0#st.lmap),
142    renumber_labels(Is, [{label,New}|Acc], St0#st{lmap=D,lc=New+1});
143renumber_labels([{func_info,_,_,_}=Fi|Is], Acc, St0) ->
144    renumber_labels(Is, [Fi|Acc], St0#st{entry=St0#st.lc});
145renumber_labels([I|Is], Acc, St0) ->
146    renumber_labels(Is, [I|Acc], St0);
147renumber_labels([], Acc, St0) -> {Acc,St0}.
148
149function_replace({function,Name,Arity,Entry,Asm0}, Dict) ->
150    Asm = case catch replace(Asm0, [], Dict) of
151	      {'EXIT',_}=Reason ->
152		  exit(Reason);
153	      {error,{undefined_label,Lbl}=Reason} ->
154		  io:format("Function ~s/~w refers to undefined label ~w\n",
155			    [Name,Arity,Lbl]),
156		  exit(Reason);
157	      Asm1 when list(Asm1) -> Asm1
158	  end,
159    {function,Name,Arity,Entry,Asm}.
160
161replace([{test,Test,{f,Lbl},Ops}|Is], Acc, D) ->
162    replace(Is, [{test,Test,{f,label(Lbl, D)},Ops}|Acc], D);
163replace([{select_val,R,{f,Fail0},{list,Vls0}}|Is], Acc, D) ->
164    Vls1 = map(fun ({f,L}) -> {f,label(L, D)};
165		   (Other) -> Other end, Vls0),
166    Fail = label(Fail0, D),
167    case redundant_values(Vls1, Fail, []) of
168	[] ->
169	    %% Oops, no choices left. The loader will not accept that.
170	    %% Convert to a plain jump.
171	    replace(Is, [{jump,{f,Fail}}|Acc], D);
172	Vls ->
173	    replace(Is, [{select_val,R,{f,Fail},{list,Vls}}|Acc], D)
174    end;
175replace([{select_tuple_arity,R,{f,Fail},{list,Vls0}}|Is], Acc, D) ->
176    Vls = map(fun ({f,L}) -> {f,label(L, D)};
177		  (Other) -> Other end, Vls0),
178    replace(Is, [{select_tuple_arity,R,{f,label(Fail, D)},{list,Vls}}|Acc], D);
179replace([{'try',R,{f,Lbl}}|Is], Acc, D) ->
180    replace(Is, [{'try',R,{f,label(Lbl, D)}}|Acc], D);
181replace([{'catch',R,{f,Lbl}}|Is], Acc, D) ->
182    replace(Is, [{'catch',R,{f,label(Lbl, D)}}|Acc], D);
183replace([{jump,{f,Lbl}}|Is], Acc, D) ->
184    replace(Is, [{jump,{f,label(Lbl, D)}}|Acc], D);
185replace([{loop_rec,{f,Lbl},R}|Is], Acc, D) ->
186    replace(Is, [{loop_rec,{f,label(Lbl, D)},R}|Acc], D);
187replace([{loop_rec_end,{f,Lbl}}|Is], Acc, D) ->
188    replace(Is, [{loop_rec_end,{f,label(Lbl, D)}}|Acc], D);
189replace([{wait,{f,Lbl}}|Is], Acc, D) ->
190    replace(Is, [{wait,{f,label(Lbl, D)}}|Acc], D);
191replace([{wait_timeout,{f,Lbl},To}|Is], Acc, D) ->
192    replace(Is, [{wait_timeout,{f,label(Lbl, D)},To}|Acc], D);
193replace([{bif,Name,{f,Lbl},As,R}|Is], Acc, D) when Lbl =/= 0 ->
194    replace(Is, [{bif,Name,{f,label(Lbl, D)},As,R}|Acc], D);
195replace([{call,Ar,{f,Lbl}}|Is], Acc, D) ->
196    replace(Is, [{call,Ar,{f,label(Lbl,D)}}|Acc], D);
197replace([{call_last,Ar,{f,Lbl},N}|Is], Acc, D) ->
198    replace(Is, [{call_last,Ar,{f,label(Lbl,D)},N}|Acc], D);
199replace([{call_only,Ar,{f,Lbl}}|Is], Acc, D) ->
200    replace(Is, [{call_only,Ar,{f,label(Lbl, D)}}|Acc], D);
201replace([{make_fun,{f,Lbl},U1,U2}|Is], Acc, D) ->
202    replace(Is, [{make_fun,{f,label(Lbl, D)},U1,U2}|Acc], D);
203replace([{make_fun2,{f,Lbl},U1,U2,U3}|Is], Acc, D) ->
204    replace(Is, [{make_fun2,{f,label(Lbl, D)},U1,U2,U3}|Acc], D);
205replace([{bs_init2,{f,Lbl},Sz,Words,R,F,Dst}|Is], Acc, D) when Lbl =/= 0 ->
206    replace(Is, [{bs_init2,{f,label(Lbl, D)},Sz,Words,R,F,Dst}|Acc], D);
207replace([{bs_put_integer,{f,Lbl},Bits,Unit,Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
208    replace(Is, [{bs_put_integer,{f,label(Lbl, D)},Bits,Unit,Fl,Val}|Acc], D);
209replace([{bs_put_binary,{f,Lbl},Bits,Unit,Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
210    replace(Is, [{bs_put_binary,{f,label(Lbl, D)},Bits,Unit,Fl,Val}|Acc], D);
211replace([{bs_put_float,{f,Lbl},Bits,Unit,Fl,Val}|Is], Acc, D) when Lbl =/= 0 ->
212    replace(Is, [{bs_put_float,{f,label(Lbl, D)},Bits,Unit,Fl,Val}|Acc], D);
213replace([{bs_final,{f,Lbl},R}|Is], Acc, D) when Lbl =/= 0 ->
214    replace(Is, [{bs_final,{f,label(Lbl, D)},R}|Acc], D);
215replace([{bs_add,{f,Lbl},Src,Dst}|Is], Acc, D) when Lbl =/= 0 ->
216    replace(Is, [{bs_add,{f,label(Lbl, D)},Src,Dst}|Acc], D);
217replace([{bs_bits_to_bytes,{f,Lbl},Bits,Dst}|Is], Acc, D) when Lbl =/= 0 ->
218    replace(Is, [{bs_bits_to_bytes,{f,label(Lbl, D)},Bits,Dst}|Acc], D);
219replace([I|Is], Acc, D) ->
220    replace(Is, [I|Acc], D);
221replace([], Acc, _) -> Acc.
222
223label(Old, D) ->
224    case dict:find(Old, D) of
225	{ok,Val} -> Val;
226	error -> throw({error,{undefined_label,Old}})
227    end.
228
229redundant_values([_,{f,Fail}|Vls], Fail, Acc) ->
230    redundant_values(Vls, Fail, Acc);
231redundant_values([Val,Lbl|Vls], Fail, Acc) ->
232    redundant_values(Vls, Fail, [Lbl,Val|Acc]);
233redundant_values([], _, Acc) -> reverse(Acc).
234