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