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%%%-------------------------------------------------------------------
14%%% File    : hipe_rtl_ssa_avail_expr.erl
15%%% Author  : Per Gustafsson <pergu@it.uu.se>
16%%% Description : A couple of optimizations on rtl_ssa
17%%%               1. Remove unnecessary loads (Global)
18%%%               2. Remove unnecessary stores (Local)
19%%%               3. Remove unnecessary tag/untag operations
20%%%
21%%% Changed :  7 Feb 2007 by Per Gustafsson <pergu@it.uu.se>
22%%%-------------------------------------------------------------------
23-module(hipe_rtl_ssa_avail_expr).
24
25-export([cfg/1]).
26
27-include("../main/hipe.hrl").
28-include("hipe_rtl.hrl").
29
30cfg(CFG) ->
31  CFG1 = remove_loads(CFG),
32  CFG2 = remove_stores(CFG1),
33  CFG3 = optimize_fixnums(CFG2),
34  hipe_rtl_ssa:remove_dead_code(CFG3).
35
36%%%=============================================================================
37%%%
38%%% Remove unnecessary loads
39%%%
40%%%=============================================================================
41
42remove_loads(CFG) ->
43  LoadsFun = fun spread_info/2,
44  Info=fix_point(CFG, LoadsFun),
45  pass_through(CFG, LoadsFun, Info).
46
47spread_info(Code, Info) ->
48  lists:foldl(fun do_instr/2, {[],Info}, Code).
49
50do_instr(Instr, {Acc,Info}) ->
51  case Instr of
52    #call{} ->
53      {Acc++[Instr], new_env()};
54    #store{} ->
55      {Acc++[Instr], new_env()};
56    #gctest{} ->
57      {Acc++[Instr], new_env()};
58    #load{} ->
59      Dst = hipe_rtl:load_dst(Instr),
60      LoadType = {hipe_rtl:load_src(Instr), hipe_rtl:load_offset(Instr),
61	      hipe_rtl:load_size(Instr), hipe_rtl:load_sign(Instr)},
62      NewInstr =
63	case lookup_y(LoadType, Info) of
64	  none ->
65	    Instr;
66	  Var ->
67	    hipe_rtl:mk_move(Dst, Var)
68	end,
69      Fun = fun load_filter_fun/2,
70      {Acc++[NewInstr], insert(Dst,LoadType,remove_defines(Instr,Info,Fun))};
71    _ ->
72      {Acc++[Instr],remove_defines(Instr,Info,fun load_filter_fun/2)}
73  end.
74
75load_filter_fun({X1,{X2,X3,_,_}},PreColDefs) ->
76  not (lists:member(X1,PreColDefs) or
77       lists:member(X2,PreColDefs) or
78       lists:member(X3,PreColDefs)).
79
80%%%=============================================================================
81%%%
82%%% Remove unnecessary stores (local optimization)
83%%%
84%%%=============================================================================
85
86remove_stores(CFG) ->
87  pass_through(CFG, fun remove_store/2, new_info()).
88
89remove_store(Code,_) ->
90  remove_store_from_bb(Code).
91
92remove_store_from_bb(Code) ->
93  remove_store_from_bb(lists:reverse(Code), new_env(), []).
94
95remove_store_from_bb([Instr|Instrs], Env, Acc) ->
96  {NewAcc, NewEnv} =
97    case Instr of
98      #call{} ->
99	{[Instr|Acc],new_env()};
100      #gctest{} ->
101      {[Instr|Acc], new_env()};
102      #store{} ->
103	Base = hipe_rtl:store_base(Instr),
104	Offset = hipe_rtl:store_offset(Instr),
105	Size = hipe_rtl:store_size(Instr),
106	StoreType = {Base, Offset, Size},
107	case lookup_y(StoreType, Env) of
108	  none ->
109	    {[Instr|Acc], insert(StoreType, true, Env)};
110	  true ->
111	    {Acc, Env}
112	end;
113      #load{} ->
114	{[Instr|Acc],new_env()};
115      _ ->
116	{[Instr|Acc],remove_defines(Instr,Env,fun store_filter_fun/2)}
117    end,
118  remove_store_from_bb(Instrs, NewEnv, NewAcc);
119remove_store_from_bb([], Env, Acc) ->
120  {Acc,Env}.
121
122store_filter_fun({{X1,X2,_},_},PreColDefs) ->
123  not (lists:member(X1,PreColDefs) or
124       lists:member(X2,PreColDefs)).
125
126%%%=============================================================================
127%%%
128%%% Optimize Fixnum Operations
129%%%
130%%%=============================================================================
131
132optimize_fixnums(CFG) ->
133  FixFun = fun fixnum_opt/2,
134  Info=fix_point(CFG, FixFun),
135  pass_through(CFG, FixFun, Info).
136
137fixnum_opt(Code,Info) ->
138  lists:foldl(fun do_fixnums/2, {[],Info}, Code).
139
140do_fixnums(Instr, {Acc,Env}) ->
141  case Instr of
142    #call{} ->
143      {Acc++[Instr],Env};
144    #gctest{} ->
145      {Acc++[Instr],Env};
146    #fixnumop{dst=Dst,src=Src} ->
147      case lookup_y(Src,Env) of
148	none ->
149	  case lookup_x(Src,Env) of
150	    none ->
151	      case hipe_rtl_arch:is_precoloured(Src) or
152		hipe_rtl_arch:is_precoloured(Dst) of
153		true ->
154		  {Acc++[Instr],Env}; %% To Avoid non ssa problems
155		false ->
156		  {Acc++[Instr],insert(Dst,Src,Env)}
157	      end;
158	    OtherSrc ->
159	      {Acc++[hipe_rtl:mk_move(Dst,OtherSrc)],Env}
160	  end;
161	OtherDst ->
162	  {Acc++[hipe_rtl:mk_move(Dst,OtherDst)],Env}
163      end;
164    _ ->
165      {Acc++[Instr],Env}
166  end.
167
168%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
169%%
170%% Code handling functions
171%%
172
173get_code_from_label(Label,CFG) ->
174  CurrentBB = hipe_rtl_cfg:bb(CFG, Label),
175  hipe_bb:code(CurrentBB).
176
177put_code_at_label(Label,Code,CFG) ->
178  NewBB = hipe_bb:mk_bb(Code),
179  hipe_rtl_cfg:bb_add(CFG, Label, NewBB).
180
181
182%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
183%%
184%% The info environment.
185%% An info environment is a mapping from labels to info_out
186%%
187
188new_info() ->
189  gb_trees:empty().
190
191get_info(Label,Info) ->
192  case gb_trees:lookup(Label, Info) of
193      {value, V} -> V;
194      none -> none
195    end.
196
197add_info(Label, NewInfo, OldInfo) ->
198  gb_trees:enter(Label, NewInfo, OldInfo).
199
200%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
201%%
202%% Simple worklist utility
203%%
204
205add_succ_to_list(NewList, OldList) ->
206  RealNew = [New || New <- NewList, lists:member(New,OldList)],
207  OldList ++ RealNew.
208
209%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
210%%
211%% Generic Fixpoint Code
212%%
213
214fix_point(CFG, Fun) ->
215  Start = hipe_rtl_cfg:start_label(CFG),
216  Info = new_info(),
217  fix_point([Start], CFG, Fun, Info).
218
219fix_point([Label|Labels], CFG, Fun, Info) ->
220  case initial_stage(Label,CFG,Fun,Info) of
221    {true, _, _} ->
222      fix_point(Labels, CFG, Fun, Info);
223    {false, _, NewInfoOut} ->
224      Succ = hipe_rtl_cfg:succ(CFG, Label),
225      NewList = add_succ_to_list(Succ, Labels),
226      NewInfo = add_info(Label, NewInfoOut, Info),
227      fix_point(NewList, CFG, Fun, NewInfo)
228  end;
229fix_point([], _CFG, _Fun, Info) ->
230  Info.
231
232pass_through(CFG, Fun, Info) ->
233  pass_through(hipe_rtl_cfg:reverse_postorder(CFG),
234	       CFG, Fun, Info).
235
236pass_through([Label|Labels], CFG, Fun, Info) ->
237  {_, NewCode, _} = initial_stage(Label,CFG,Fun,Info),
238  NewCFG = put_code_at_label(Label,NewCode,CFG),
239  pass_through(Labels, NewCFG, Fun, Info);
240pass_through([], CFG, _Fun, _Info) ->
241  CFG.
242
243initial_stage(Label,CFG,Fun,Info) ->
244  OldInfoOut = get_info(Label,Info),
245  Pred = hipe_rtl_cfg:pred(CFG,Label),
246  InfoEnv = join([get_info(L,Info) || L <- Pred]),
247  OldCode = get_code_from_label(Label,CFG),
248  {PhiCode,Code} = split_code(OldCode),
249  InfoIn = join_phi(PhiCode,Info,InfoEnv),
250  {NewCode, NewInfoOut} = Fun(Code, InfoIn),
251  {OldInfoOut=:=NewInfoOut,PhiCode++NewCode, NewInfoOut}.
252
253join_phi([#phi{dst=Dst,arglist=AList}|Rest], Info, Env) ->
254  case lists:foldl(fun(Val,Acc) ->
255		       check_label(Val,Info,Acc)
256		   end, none, AList) of
257    no_val ->
258      join_phi(Rest,Info,Env);
259    none ->
260      join_phi(Rest,Info,Env);
261    Expr ->
262      join_phi(Rest,Info,insert(Dst,Expr,Env))
263  end;
264join_phi([], _Info, Env) ->
265  Env.
266
267check_label({Lbl,Var}, Info, Acc) ->
268  case gb_trees:lookup(Lbl,Info) of
269    none -> Acc;
270    {value,Env} ->
271      case lookup_x(Var,Env) of
272	none -> no_val;
273	Acc -> Acc;
274	V ->
275	  if Acc =:= none -> V;
276	     true -> no_val
277	  end
278      end
279  end.
280
281split_code(Code) ->
282  Phis = extract_phis(Code),
283  {Phis,Code--Phis}.
284
285extract_phis(Code) ->
286  [I || #phi{}=I <- Code].
287
288%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
289%%
290%% One2One Environment
291%%
292
293new_env() ->
294  {gb_trees:empty(),gb_trees:empty()}.
295
296insert(X,Y,{XtoY,YtoX}) ->
297  NewYtoX = remove_old_binding(X,XtoY,YtoX),
298  NewXtoY = remove_old_binding(Y,YtoX,XtoY),
299  {gb_trees:enter(X,Y,NewXtoY),
300   gb_trees:enter(Y,X,NewYtoX)}.
301
302remove_old_binding(Key,LookupTree,ChangeTree) ->
303  case gb_trees:lookup(Key,LookupTree) of
304    none ->
305      ChangeTree;
306    {value,V} ->
307      gb_trees:balance(gb_trees:delete(V,ChangeTree))
308  end.
309
310lookup_x(X,{XtoY,_YtoX}) ->
311  case gb_trees:lookup(X,XtoY) of
312    none -> none;
313    {value,Val} -> Val
314  end.
315
316lookup_y(Y,{_XtoY,YtoX}) ->
317  case gb_trees:lookup(Y,YtoX) of
318     none -> none;
319    {value,Val} -> Val
320  end.
321
322join([]) -> new_env();
323join([none]) -> new_env();
324join([E]) -> E;
325join([E1,E2|Rest]) -> join([join(E1,E2)|Rest]).
326
327join({MapXY1,MapYX1},{MapXY2,MapYX2}) ->
328  {join_maps(MapXY1,MapXY2),
329   join_maps(MapYX1,MapYX2)};
330join(none,E) -> E;
331join(E,none) -> E.
332
333join_maps(Map1,Map2) ->
334  OrdDict = ordsets:intersection(gb_trees:to_list(Map1),
335			   gb_trees:to_list(Map2)),
336  gb_trees:from_orddict(OrdDict).
337
338remove_defines(Instr,Info,Fun) ->
339  Defs = hipe_rtl:defines(Instr),
340  case [Def || Def <- Defs, hipe_rtl_arch:is_precoloured(Def)] of
341    [] ->
342      Info;
343    PreColDefs ->
344      filter_environments(PreColDefs,Info,Fun)
345  end.
346
347filter_environments(PreColDefs,{M1,_M2},Fun) ->
348  L1 = gb_trees:to_list(M1),
349  F1 = [Tup || Tup <- L1, Fun(Tup,PreColDefs)],
350  F2 = [{Y,X} || {X,Y} <- F1],
351  {gb_trees:from_orddict(F1),gb_trees:from_orddict(orddict:from_list(F2))}.
352