1%% -*- erlang-indent-level: 2 -*- 2%% 3%% Licensed under the Apache License, Version 2.0 (the "License"); 4%% you may not use this file except in compliance with the License. 5%% You may obtain a copy of the License at 6%% 7%% http://www.apache.org/licenses/LICENSE-2.0 8%% 9%% Unless required by applicable law or agreed to in writing, software 10%% distributed under the License is distributed on an "AS IS" BASIS, 11%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12%% See the License for the specific language governing permissions and 13%% limitations under the License. 14%% 15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16%% File : hipe_rtl_ssapre.erl 17%% Author : He Bingwen and Frédéric Haziza 18%% Description : Performs Partial Redundancy Elimination on SSA form. 19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 20%% @doc 21%% 22%% This module implements the <a href="http://cs.wheaton.edu/%7Etvandrun/writings/spessapre.pdf">Anticipation-SSAPRE algorithm</a>, 23%% with several modifications for Partial Redundancy Elimination on SSA form. 24%% We actually found problems in this algorithm, so 25%% we implement another version with several advantages: 26%% - No loop for Xsi insertions 27%% - No fix point iteration for the downsafety part 28%% - Less computations for Will Be Available part 29%% - Complexity of the overall algorithm is improved 30%% 31%% We were supposed to publish these results anyway :D 32%% 33%% @end 34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 35 36-module(hipe_rtl_ssapre). 37 38-export([rtl_ssapre/2]). 39 40-include("../main/hipe.hrl"). 41-include("hipe_rtl.hrl"). 42 43%%-define(SSAPRE_DEBUG, true ). %% When uncommented, produces debug printouts 44-define( SETS, ordsets ). %% Which set implementation module to use 45-define( CFG, hipe_rtl_cfg ). 46-define( RTL, hipe_rtl ). 47-define( BB, hipe_bb ). 48-define( ARCH, hipe_rtl_arch ). 49-define( GRAPH, digraph ). 50 51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 52%% Debugging stuff 53%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 54 55-ifndef(SSAPRE_DEBUG). 56-define(pp_debug(_Str, _Args), ok). 57-else. 58-define(pp_debug(Str, Args), io:format(standard_io, Str, Args)). 59-endif. 60 61%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 62%% Records / Structures 63%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 64 65-record(xsi_link, {num}). %% Number is the index of the temporary (a Key into the Xsi Tree) 66-record(temp, {key, var}). 67-record(bottom, {key, var}). 68-record(xsi, {inst, %% Associated instruction 69 def, %% Hypothetical temporary variable 70 %% that stores the result of the computation 71 label, %% Block Label where the xsi is inserted 72 opList, %% List of operands 73 cba, %% 74 later, %% 75 wba 76 }). 77 78-record(pre_candidate, {alu, def}). 79-record(xsi_op, {pred, op}). 80 81-record(mp, {xsis, maps, preds, defs, uses, ndsSet}). 82-record(block, {type, attributes}). 83 84-record(eop, {expr, var, stopped_by}). 85-record(insertion, {code, from}). 86 87-record(const_expr, {var, value}). 88 89%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 90%% Main function 91%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 92 93rtl_ssapre(RtlSSACfg, Options) -> 94 %% io:format("\n################ Original CFG ################\n"), 95 %% hipe_rtl_cfg:pp(RtlSSACfg), 96 %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",[hipe_rtl_ssa:check(RtlSSACfg)]), 97 98 {CFG2,XsiGraph,CFGGraph,MPs} = perform_Xsi_insertion(RtlSSACfg,Options), 99 %%?pp_debug("~n~n################ Xsi CFG ################\n",[]),pp_cfg(CFG2,XsiGraph), 100 XsiList = ?GRAPH:vertices(XsiGraph), 101 case XsiList of 102 [] -> 103 %% No Xsi 104 ?pp_debug("~n~n################ No Xsi Inserted ################~n",[]), 105 ok; 106 _ -> 107 ?pp_debug("~n############ Downsafety ##########~n",[]), 108 ?option_time(perform_downsafety(MPs,CFGGraph,XsiGraph),"RTL A-SSAPRE Downsafety",Options), 109 ?pp_debug("~n~n################ CFG Graph ################~n",[]),pp_cfggraph(CFGGraph), 110 ?pp_debug("~n############ Will Be Available ##########~n",[]), 111 ?option_time(perform_will_be_available(XsiGraph,CFGGraph,Options),"RTL A-SSAPRE WillBeAvailable",Options) 112 end, 113 114 ?pp_debug("~n############ No more need for the CFG Graph....Deleting...",[]),?GRAPH:delete(CFGGraph), 115 ?pp_debug("~n~n################ Xsi Graph ################~n",[]),pp_xsigraph(XsiGraph), 116 117 ?pp_debug("~n############ Code Motion ##########~n",[]), 118 Labels = ?CFG:preorder(CFG2), 119 120 ?pp_debug("~n~n################ Xsi CFG ################~n",[]),pp_cfg(CFG2,XsiGraph), 121 122 init_redundancy_count(), 123 FinalCFG = ?option_time(perform_code_motion(Labels,CFG2,XsiGraph),"RTL A-SSAPRE Code Motion",Options), 124 125 ?pp_debug("\n############ No more need for the Xsi Graph....Deleting...",[]),?GRAPH:delete(XsiGraph), 126 127 %% io:format("\n################ Final CFG ################\n"), 128 %% hipe_rtl_cfg:pp(FinalCFG), 129 %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n", 130 %% [hipe_rtl_ssa:check(FinalCFG)]), 131 ?pp_debug("\nSSAPRE : ~w redundancies were found\n",[get_redundancy_count()]), 132 133 FinalCFG. 134 135%% ########################################################################## 136%% ######################## XSI INSERTION ################################### 137%% ########################################################################## 138 139perform_Xsi_insertion(Cfg, Options) -> 140 init_counters(), %% Init counters for Bottoms and Temps 141 DigraphOpts = [cyclic, private], 142 XsiGraph = digraph:new(DigraphOpts), 143 %% Be careful, the digraph component is NOT garbage collected, 144 %% so don't create 20 millions of instances! 145 %% finds the longest depth 146 %% Depth-first, preorder traversal over Basic Blocks. 147 %%Labels = ?CFG:reverse_postorder(Cfg), 148 Labels = ?CFG:preorder(Cfg), 149 150 ?pp_debug("~n~n############# Finding definitions for computation~n~n",[]), 151 {Cfg2,XsiGraph} = ?option_time(find_definition_for_computations(Labels,Cfg,XsiGraph),"RTL A-SSAPRE Xsi Insertion, searching from instructions",Options), 152 153 %% Active List creation 154 GeneratorXsiList = lists:sort(?GRAPH:vertices(XsiGraph)), 155 ?pp_debug("~n~n############# Inserted Xsis ~w",[GeneratorXsiList]), 156 ?pp_debug("~n~n############# Finding operands~n",[]), 157 {Cfg3,XsiGraph} = ?option_time(find_operands(Cfg2,XsiGraph,GeneratorXsiList,0),"RTL A-SSAPRE Xsi Insertion, finding operands",Options), 158 159 %% Creating the CFGGraph 160 ?pp_debug("~n~n############# Creating CFG Graph",[]), 161 ?pp_debug("~n############# Labels = ~w",[Labels]), 162 CFGGraph = digraph:new(DigraphOpts), 163 [StartLabel|Others] = Labels, % adding the start label as a leaf 164 ?pp_debug("~nAdding a vertex for the start label: ~w",[StartLabel]), 165 ?GRAPH:add_vertex(CFGGraph, StartLabel, #block{type = top}), 166 % Doing the others 167 MPs = ?option_time(create_cfggraph(Others,Cfg3,CFGGraph,[],[],[],XsiGraph),"RTL A-SSAPRE Xsi Insertion, creating intermediate 'SSAPRE Graph'",Options), 168 169 %% Return the collected information 170 {Cfg3,XsiGraph,CFGGraph,MPs}. 171 172%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 173 174find_definition_for_computations([], Cfg, XsiGraph) -> 175 {Cfg,XsiGraph}; %% No more block to inspect in the depth-first order 176find_definition_for_computations([Label|Rest], Cfg, XsiGraph) -> 177 Code = ?BB:code(?CFG:bb(Cfg,Label)), 178 {NewCfg,XsiGraph} = find_definition_for_computations_in_block(Label,Code,Cfg,[],XsiGraph), 179 find_definition_for_computations(Rest, NewCfg, XsiGraph). 180 181%%=========================================================================== 182%% Searches from instruction for one block BlockLabel. 183%% We process forward over instructions. 184 185find_definition_for_computations_in_block(BlockLabel,[],Cfg, 186 VisitedInstructions,XsiGraph)-> 187 Code = lists:reverse(VisitedInstructions), 188 NewBB = ?BB:mk_bb(Code), 189 NewCfg = ?CFG:bb_add(Cfg,BlockLabel,NewBB), 190 {NewCfg,XsiGraph}; %% No more instructions to inspect in this block 191find_definition_for_computations_in_block(BlockLabel,[Inst|Rest],Cfg, 192 VisitedInstructions,XsiGraph) -> 193 %% ?pp_debug(" Inspecting instruction: ",[]),pp_instr(Inst,nil), 194 case Inst of 195 #alu{} -> 196 %% Is Inst interesting for SSAPRE? 197 %% i.e., is Inst an arithmetic operation which doesn't deal with precoloured? 198 %% Note that since we parse forward, we have no 'pre_candidate'-type so far. 199 case check_definition(Inst,VisitedInstructions,BlockLabel,Cfg,XsiGraph) of 200 {def_found,Def} -> 201 %% Replacing Inst in Cfg 202 NewInst = #pre_candidate{alu=Inst,def=Def}, 203 NewVisited = [NewInst|VisitedInstructions], 204 %% Recurse forward over instructions, same CFG, same XsiGraph 205 find_definition_for_computations_in_block(BlockLabel,Rest,Cfg, 206 NewVisited,XsiGraph); 207 {merge_point,Xsi} -> 208 Def = Xsi#xsi.def, 209 Key = Def#temp.key, 210 NewInst = #pre_candidate{alu=Inst,def=Def}, 211 XsiLink = #xsi_link{num=Key}, 212 213 %% Add a vertex to the Xsi Graph 214 ?GRAPH:add_vertex(XsiGraph,Key,Xsi), 215 ?pp_debug(" Inserting Xsi: ",[]),pp_xsi(Xsi), 216 217 Label = Xsi#xsi.label, 218 {NewCfg, NewVisited} = 219 case BlockLabel =:= Label of 220 false -> 221 %% Insert the Xsi in the appropriate block 222 Code = hipe_bb:code(?CFG:bb(Cfg,Label)), 223 {BeforeCode,AfterCode} = split_for_xsi(lists:reverse(Code),[]), 224 NewCode = BeforeCode++[XsiLink|AfterCode], 225 NewBB = hipe_bb:mk_bb(NewCode), 226 {?CFG:bb_add(Cfg,Label,NewBB), [NewInst|VisitedInstructions]}; 227 _-> 228 {BeforeCode,AfterCode} = split_for_xsi(VisitedInstructions,[]), 229 TempVisited = BeforeCode++[XsiLink|AfterCode], 230 TempVisited2 = lists:reverse(TempVisited), 231 {Cfg, [NewInst|TempVisited2]} 232 end, 233 find_definition_for_computations_in_block(BlockLabel, Rest, NewCfg, 234 NewVisited, XsiGraph) 235 end; 236 _ -> 237 %%?pp_debug("~n [L~w] Not concerned with: ~w",[BlockLabel,Inst]), 238 %% If the instruction is not a SSAPRE candidate, we skip it and keep on 239 %% processing instructions 240 %% Prepend Inst, so that we have all in reverse order. 241 %% Easy to parse backwards 242 find_definition_for_computations_in_block(BlockLabel, Rest, Cfg, 243 [Inst|VisitedInstructions], XsiGraph) 244 end. 245 246%% ############################################################################ 247%% We have E as an expression, I has an alu (arithmetic operation), and 248%% we inspect backwards the previous instructions to find a definition for E. 249%% Since we parse in forward order, we know that the previous SSAPRE 250%% instruction will have a definition. 251 252check_definition(E,[],BlockLabel,Cfg,XsiGraph)-> 253 %% No more instructions in that block 254 %% No definition found in that block 255 %% Search is previous blocks 256 Preds = ?CFG:pred(Cfg, BlockLabel), 257 %% ?pp_debug("~n CHECKING DEFINITION ####### Is L~w a merge block? It has ~w preds. So far E=",[BlockLabel,length(Preds)]),pp_expr(E), 258 case Preds of 259 [] -> 260 %% Entry Point 261 {def_found,bottom}; 262 [P] -> 263 %% One predecessor only, we just keep looking for a definition in that block 264 VisitedInstructions = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))), 265 check_definition(E,VisitedInstructions,P,Cfg,XsiGraph); 266 _ -> 267 Temp = new_temp(), 268 %% It's a merge point 269 OpList = [#xsi_op{pred=X} || X<-Preds], 270 Xsi = #xsi{inst=E,def=Temp,label=BlockLabel,opList=OpList}, 271 {merge_point,Xsi} 272 end; 273check_definition(E,[CC|Rest],BlockLabel,Cfg,XsiGraph) -> 274 SRC1 = ?RTL:alu_src1(E), 275 SRC2 = ?RTL:alu_src2(E), 276 case CC of 277 #alu{} -> 278 exit({?MODULE,should_not_be_an_alu, 279 {"Why the hell do we still have an alu???",CC}}); 280 #pre_candidate{} -> 281 %% C is the previous instruction 282 C = CC#pre_candidate.alu, 283 DST = ?RTL:alu_dst(C), 284 case DST =:= SRC1 orelse DST =:= SRC2 of 285 false -> 286 case check_match(E,C) of 287 true -> %% It's a computation of E! 288 %% Get the dst of the alu 289 {def_found,DST}; 290 _-> 291 check_definition(E,Rest,BlockLabel,Cfg,XsiGraph) 292 end; 293 true -> 294 %% Get the definition of C, since C is PRE-candidate AND has been processed before 295 DEF = CC#pre_candidate.def, 296 case DEF of 297 bottom -> 298 %% Def(E)=bottom, STOP 299 {def_found,bottom}; 300 _ -> 301 %% Emend E with this def(C) 302 %%?pp_debug("Parameters are E=~w, DST=~w, DEF=~w",[E,DST,DEF]), 303 F = emend(E,DST,DEF), 304 check_definition(F,Rest,BlockLabel,Cfg,XsiGraph) %% Continue the search 305 end 306 end; 307 #move{} -> 308 %% It's a move, we emend E, and continue the definition search 309 DST = ?RTL:move_dst(CC), 310 F = case SRC1 =:= DST orelse SRC2 =:= DST of 311 true -> 312 SRC = ?RTL:move_src(CC), 313 emend(E,DST,SRC); 314 _ -> 315 E 316 end, 317 check_definition(F,Rest,BlockLabel,Cfg,XsiGraph); %% Continue the search 318 #xsi_link{} -> 319 {_K,Xsi} = ?GRAPH:vertex(XsiGraph,CC#xsi_link.num), 320 C = Xsi#xsi.inst, 321 case check_match(C,E) of 322 true -> %% There is a Xsi already with a computation of E! 323 %% fetch definition of C, and give it to E 324 {def_found,Xsi#xsi.def}; 325 _-> 326 check_definition(E,Rest,BlockLabel,Cfg,XsiGraph) 327 end; 328 #phi{} -> 329 %% skip them. NOTE: Important to separate this case from the next one 330 check_definition(E,Rest,BlockLabel,Cfg,XsiGraph); 331 _ -> 332 %% Note: the function calls or some other instructions can change the pre-coloured registers 333 %% which are able to be redefined. This breaks of course the SSA form. 334 %% If there is a redefinition we can give bottom to the computation, and no xsi will be inserted. 335 %% (In some sens, the result of the computation is new at that point.) 336 PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2), 337 338 %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2), 339 RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), %% That means we cannot reuse the result held in this register... 340 341 case PreColouredTest orelse RegisterTest of 342 true -> 343 {def_found,bottom}; 344 false -> 345 DC = ?RTL:defines(CC), 346 case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of 347 true -> 348 {def_found,bottom}; 349 false -> 350 %% Orthogonal to E, we continue the search 351 check_definition(E,Rest,BlockLabel,Cfg,XsiGraph) 352 end 353 end 354 end. 355 356%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 357 358check_match(E, C) -> 359 OpE = ?RTL:alu_op(E), 360 OpC = ?RTL:alu_op(C), 361 case OpE =:= OpC of 362 false -> 363 false; 364 true -> 365 Src1E = ?RTL:alu_src1(E), 366 Src2E = ?RTL:alu_src2(E), 367 Src1C = ?RTL:alu_src1(C), 368 Src2C = ?RTL:alu_src2(C), 369 case Src1E =:= Src1C of 370 true -> 371 Src2E =:= Src2C; 372 false -> 373 Src1E =:= Src2C andalso Src2E =:= Src1C 374 end 375 end. 376 377%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 378 379expr_is_const(E) -> 380 ?RTL:is_imm(?RTL:alu_src1(E)) andalso ?RTL:is_imm(?RTL:alu_src2(E)). 381%% is_number(?RTL:alu_src1(E)) andalso is_number(?RTL:alu_src2(E)). 382 383%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 384%% Must be an arithmetic operation, i.e. #alu{} 385emend(Expr, S, Var) -> 386 SRC1 = ?RTL:alu_src1(Expr), 387 NewExpr = case SRC1 =:= S of 388 true -> ?RTL:alu_src1_update(Expr,Var); 389 false -> Expr 390 end, 391 SRC2 = ?RTL:alu_src2(NewExpr), 392 case SRC2 =:= S of 393 true -> ?RTL:alu_src2_update(NewExpr,Var); 394 false -> NewExpr 395 end. 396 397%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 398 399split_for_xsi([], Acc) -> 400 {[], Acc}; % no_xsi_no_phi_found; 401split_for_xsi([I|Is] = Code, Acc) -> %% [I|Is] in backward order, Acc in order 402 case I of 403 #xsi_link{} -> 404 {lists:reverse(Code), Acc}; 405 #phi{} -> 406 {lists:reverse(Code), Acc}; 407 _ -> 408 split_for_xsi(Is, [I|Acc]) 409 end. 410 411%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 412%% Phase 1.B : Search for operands 413%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 414 415find_operands(Cfg,XsiGraph,[],_Count) -> 416 {Cfg,XsiGraph}; 417find_operands(Cfg,XsiGraph,ActiveList,Count) -> 418 {NewCfg,TempActiveList} = find_operands_for_active_list(Cfg,XsiGraph,ActiveList,[]), 419 NewActiveList = lists:reverse(TempActiveList), 420 ?pp_debug("~n################ Finding operands (iteration ~w): ~w have been introduced. Now ~w in total~n", 421 [Count+1, length(NewActiveList), length(?GRAPH:vertices(XsiGraph))]), 422 find_operands(NewCfg,XsiGraph,NewActiveList,Count+1). 423 424find_operands_for_active_list(Cfg,_XsiGraph,[],ActiveListAcc) -> 425 {Cfg,ActiveListAcc}; 426find_operands_for_active_list(Cfg,XsiGraph,[K|Ks],ActiveListAcc) -> 427 {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,K), 428 ?pp_debug("~n Inspecting operands of : ~n",[]),pp_xsi(Xsi), 429 Preds = ?CFG:pred(Cfg, Xsi#xsi.label), 430 {NewCfg,NewActiveListAcc}=determine_operands(Xsi,Preds,Cfg,K,XsiGraph,ActiveListAcc), 431 {_Key2,Xsi2} = ?GRAPH:vertex(XsiGraph,K), 432 ?pp_debug("~n ** Final Xsi: ~n",[]),pp_xsi(Xsi2), 433 ?pp_debug("~n #####################################################~n",[]), 434 find_operands_for_active_list(NewCfg,XsiGraph,Ks,NewActiveListAcc). 435 436determine_operands(_Xsi,[],Cfg,_K,_XsiGraph,ActiveAcc) -> 437 %% All operands have been determined. 438 %% The CFG is not updated, only the XsiGraph 439 {Cfg,ActiveAcc}; 440determine_operands(Xsi,[P|Ps],Cfg,K,XsiGraph,ActiveAcc) -> 441 Label = Xsi#xsi.label, 442 ReverseCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,Label))), 443 VisitedInstructions = get_visited_instructions(Xsi,ReverseCode), 444 Res = determine_e_prime(Xsi#xsi.inst,VisitedInstructions,P,XsiGraph), 445 case Res of 446 operand_is_bottom -> 447 NewXsi = xsi_arg_update(Xsi,P,new_bottom()), 448 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 449 determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); 450 operand_is_const_expr -> 451 NewXsi = xsi_arg_update(Xsi,P,new_bottom()), 452 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 453 determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); 454 {sharing_operand,Op} -> 455 NewXsi = xsi_arg_update(Xsi,P,Op), 456 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 457 determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); 458 {revised_expression,E_prime} -> 459 ?pp_debug(" E' is determined : ",[]),pp_expr(E_prime), 460 ?pp_debug(" and going along the edge L~w~n",[P]), 461 %% Go along the edge P 462 RevCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))), 463 case check_one_operand(E_prime,RevCode,P,Cfg,K,XsiGraph) of 464 {def_found,Def} -> 465 NewXsi = xsi_arg_update(Xsi,P,Def), 466 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 467 determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); 468 469 {expr_found,ChildExpr} -> 470 NewXsi = xsi_arg_update(Xsi,P,ChildExpr), 471 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 472 determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); 473 474 {expr_is_const, Op} -> 475 %% We detected that the expression is of the form: 'N op M' 476 %% where N and M are constant. 477 NewXsi = xsi_arg_update(Xsi,P,Op), 478 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 479 determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); 480 481 {merge_point,XsiChild} -> 482 %% Update that Xsi, give its definition as Operand for the 483 %% search, and go on 484 XsiChildDef = XsiChild#xsi.def, 485 NewXsi = xsi_arg_update(Xsi,P,XsiChildDef), 486 ?GRAPH:add_vertex(XsiGraph,K,NewXsi), 487 488 KeyChild = XsiChildDef#temp.key, 489 XsiChildLink = #xsi_link{num=KeyChild}, 490 ?GRAPH:add_vertex(XsiGraph,KeyChild,XsiChild), 491 492 %% Should not be the same block !!!!!!! 493 RCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,XsiChild#xsi.label))), 494 {BCode,ACode} = split_code_for_xsi(RCode,[]), 495 496 NewCode = BCode++[XsiChildLink|ACode], 497 NewBB = hipe_bb:mk_bb(NewCode), 498 NewCfg = ?CFG:bb_add(Cfg, XsiChild#xsi.label, NewBB), 499 500 ?pp_debug(" -- ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" causes insertion of: ~n",[]),pp_xsi(XsiChild), 501 ?pp_debug(" -- Adding an edge ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" -> ",[]),pp_arg(XsiChild#xsi.def), 502 503 %% Adding an edge... 504 %%?GRAPH:add_edge(XsiGraph,K,KeyChild,"family"), 505 ?GRAPH:add_edge(XsiGraph,K,KeyChild), 506 determine_operands(NewXsi,Ps,NewCfg,K,XsiGraph,[KeyChild|ActiveAcc]) 507 end 508 end. 509 510determine_e_prime(Expr,VisitedInstructions,Pred,XsiGraph) -> 511 %% MUST FETCH FROM THE XSI TREE, since Xsis are not updated yet in the CFG 512 NewExpr = emend_with_phis(Expr,VisitedInstructions,Pred), 513 emend_with_processed_xsis(NewExpr,VisitedInstructions,Pred,XsiGraph). 514 515emend_with_phis(EmendedE, [], _) -> 516 EmendedE; 517emend_with_phis(E, [I|Rest], Pred) -> 518 case I of 519 #phi{} -> 520 Dst = ?RTL:phi_dst(I), 521 UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead? 522 case lists:member(Dst, UE) of 523 false -> 524 emend_with_phis(E, Rest, Pred); 525 true -> 526 NewE = emend(E, Dst, ?RTL:phi_arg(I,Pred)), 527 emend_with_phis(NewE, Rest, Pred) 528 end; 529 _ -> 530 emend_with_phis(E, Rest, Pred) 531 end. 532 533emend_with_processed_xsis(EmendedE, [], _, _) -> 534 {revised_expression,EmendedE}; 535emend_with_processed_xsis(E, [I|Rest], Pred, XsiGraph) -> 536 case I of 537 #xsi_link{} -> 538 Key = I#xsi_link.num, 539 {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key), 540 Def = Xsi#xsi.def, 541 UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead? 542 case lists:member(Def,UE) of 543 false -> 544 CE = Xsi#xsi.inst, 545 case check_match(E,CE) of 546 true -> %% It's a computation of E! 547 case xsi_arg(Xsi,Pred) of 548 undetermined_operand -> 549 exit({?MODULE,check_operand_sharing,"######## Ôh Dear, we trusted Kostis !!!!!!!!! #############"}); 550 XsiOp -> 551 {sharing_operand,XsiOp} %% They share operands 552 end; 553 _-> 554 emend_with_processed_xsis(E,Rest,Pred,XsiGraph) 555 end; 556 true -> 557 A = xsi_arg(Xsi,Pred), 558 %% ?pp_debug(" ######### xsi_arg(I:~w,Pred:~w) = ~w~n",[I,Pred,A]), 559 case A of 560 #bottom{} -> 561 operand_is_bottom; 562 #const_expr{} -> 563 operand_is_const_expr; 564 #eop{} -> 565 NewE = emend(E,Def,A#eop.var), 566 emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph); 567 undetermined_operand -> 568 exit({?MODULE,emend_with_processed_xsis,"######## Ôh Dear, we trusted Kostis, again !!!!!!!!! #############"}); 569 XsiOp -> 570 NewE = emend(E,Def,XsiOp), 571 emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph) 572 end 573 end; 574 _ -> 575 emend_with_processed_xsis(E,Rest,Pred,XsiGraph) 576 end. 577 578%% get_visited_instructions(Xsi,[]) -> 579%% ?pp_debug("~nWe don't find this xsi with def ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" in L~w : ",[Xsi#xsi.label]), 580%% exit({?MODULE,no_such_xsi_in_block,"We didn't find that Xsi in the block"}); 581get_visited_instructions(Xsi, [I|Is]) -> 582 case I of 583 #xsi_link{} -> 584 XsiDef = Xsi#xsi.def, 585 Key = XsiDef#temp.key, 586 case I#xsi_link.num =:= Key of 587 true -> 588 Is; 589 false -> 590 get_visited_instructions(Xsi, Is) 591 end; 592 _ -> 593 get_visited_instructions(Xsi, Is) 594 end. 595 596split_code_for_xsi([], Acc) -> 597 {[],Acc}; 598split_code_for_xsi([I|Is] = Code, Acc) -> 599 case I of 600 #xsi_link{} -> 601 {lists:reverse(Code), Acc}; 602 #phi{} -> 603 {lists:reverse(Code), Acc}; 604 _ -> 605 split_code_for_xsi(Is, [I|Acc]) 606 end. 607 608check_one_operand(E, [], BlockLabel, Cfg, XsiKey, XsiGraph) -> 609 %% No more instructions in that block 610 %% No definition found in that block 611 %% Search is previous blocks 612 Preds = ?CFG:pred(Cfg, BlockLabel), 613 case Preds of 614 [] -> 615 %% Entry Point 616 {def_found,new_bottom()}; 617 [P] -> 618 %% One predecessor only, we just keep looking for a definition in that block 619 case expr_is_const(E) of 620 true -> 621 ?pp_debug("\n\n############## Wow expr is constant: ~w",[E]), 622 Var = ?RTL:mk_new_var(), 623 Value = eval_expr(E), 624 Op = #const_expr{var = Var, value = Value}, 625 {expr_is_const, Op}; 626 false -> 627 VisitedInstructions = lists:reverse(?BB:code(?CFG:bb(Cfg,P))), 628 check_one_operand(E, VisitedInstructions, P, Cfg, XsiKey, XsiGraph) 629 end; 630 _ -> 631 %% It's a merge point 632 case expr_is_const(E) of 633 true -> 634 ?pp_debug("\n\n############## Wow expr is constant at merge point: ~w",[E]), 635 Var = ?RTL:mk_new_var(), 636 Value = eval_expr(E), 637 Op = #const_expr{var = Var, value = Value}, 638 {expr_is_const, Op}; 639 false -> 640 Temp = new_temp(), 641 OpList = [#xsi_op{pred = X} || X <- Preds], 642 Xsi = #xsi{inst = E, def = Temp, label = BlockLabel, opList = OpList}, 643 {merge_point, Xsi} 644 end 645 end; 646check_one_operand(E, [CC|Rest], BlockLabel, Cfg, XsiKey, XsiGraph) -> 647 SRC1 = ?RTL:alu_src1(E), 648 SRC2 = ?RTL:alu_src2(E), 649 %% C is the previous instruction 650 case CC of 651 #alu{} -> 652 exit({?MODULE,should_not_be_an_alu, 653 {"Why the hell do we still have an alu???",CC}}); 654 #xsi{} -> 655 exit({?MODULE,should_not_be_a_xsi, 656 {"Why the hell do we still have a xsi???",CC}}); 657 #pre_candidate{} -> 658 C = CC#pre_candidate.alu, 659 DST = ?RTL:alu_dst(C), 660 case DST =:= SRC1 orelse DST =:= SRC2 of 661 true -> 662 %% Get the definition of C, since C is PRE-candidate AND has 663 %% been processed before 664 DEF = CC#pre_candidate.def, 665 case DEF of 666 bottom -> 667 %% Def(E)=bottom, STOP 668 %% No update of the XsiGraph 669 {def_found,new_bottom()}; 670 _-> 671 %% Simply emend 672 F = emend(E,DST,DEF), 673 ?pp_debug("~nEmendation : E= ",[]),pp_expr(E),?pp_debug(" ==> E'= ",[]),pp_expr(F),?pp_debug("~n",[]), 674 check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) 675 end; 676 false -> 677 case check_match(C,E) of 678 true -> %% It's a computation of E! 679 %% It should give DST and not Def 680 %% No update of the XsiGraph, cuz we use DST and not Def 681 %% The operand is therefore gonna be a real variable 682 {def_found,DST}; 683 _-> 684 %% Nothing to do with E 685 check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) 686 end 687 end; 688 #move{} -> 689 %% It's a move, we emend E, and continue the definition search 690 DST = ?RTL:move_dst(CC), 691 case SRC1 =:= DST orelse SRC2 =:= DST of 692 true -> 693 SRC = ?RTL:move_src(CC), 694 F = emend(E,DST,SRC), 695 check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); %% Continue the search 696 _ -> 697 check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) %% Continue the search 698 end; 699 #xsi_link{} -> 700 Key = CC#xsi_link.num, 701 %% Is Key a family member of XsiDef ? 702 {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key), 703 C = Xsi#xsi.inst, 704 case check_match(E,C) of 705 true -> %% There is a Xsi already with a computation of E! 706 %% fetch definition of C, and give it to E 707 %% Must update an edge in the XsiGraph, and here, we know it's a Temp 708 %% Note: this can create a loop (= a cycle of length 1) 709 ?pp_debug(" -- Found a cycle with match: Adding an edge t~w -> t~w",[XsiKey,Key]), 710 ?GRAPH:add_edge(XsiGraph,XsiKey,Key), 711 {def_found,Xsi#xsi.def}; 712 _ -> 713 case ?GRAPH:get_path(XsiGraph,Key,XsiKey) of 714 false -> 715 %% Is it a loop back to itself??? 716 case Key =:= XsiKey of 717 false -> 718 check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); 719 _ -> 720 {expr_found,#eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}} 721 end; 722 _ -> 723 %% Returning the expression instead of looping 724 %% And in case of no match 725 ExprOp = #eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}, 726 {expr_found,ExprOp} 727 end 728 end; 729 #phi{} -> %% skip them 730 check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); 731 _ -> 732 PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2), 733 734 %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2), 735 RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), 736 case PreColouredTest orelse RegisterTest of 737 true -> 738 {def_found,new_bottom()}; 739 _-> 740 DC = ?RTL:defines(CC), 741 case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of 742 true -> 743 {def_found,new_bottom()}; 744 _ -> 745 %% Orthogonal to E, we continue the search 746 check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) 747 end 748 end 749 end. 750 751eval_expr(E) -> 752 ?pp_debug("~n Evaluating the result of ~w~n", [E]), 753 Op1 = ?RTL:alu_src1(E), 754 Op2 = ?RTL:alu_src2(E), 755 true = ?RTL:is_imm(Op1), 756 Val1 = ?RTL:imm_value(Op1), 757 true = ?RTL:is_imm(Op2), 758 Val2 = ?RTL:imm_value(Op2), 759 {Result, _Sign, _Zero, _Overflow, _Carry} = ?ARCH:eval_alu(?RTL:alu_op(E), Val1, Val2), 760 ?pp_debug("~n Result is then ~w~n", [Result]), 761 ?RTL:mk_imm(Result). 762 763%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 764%%%%%%%%%%%%%%%%%%%%%%%%%% CREATTING CFGGRAPH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 765%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 766 767create_cfggraph([],_Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,_XsiGraph) -> 768 ?pp_debug("~n~n ############# PostProcessing ~n~w~n",[LateEdges]), 769 post_process(LateEdges,CFGGraph), 770 ?pp_debug("~n~n ############# Factorizing ~n~w~n",[ToBeFactorizedAcc]), 771 factorize(ToBeFactorizedAcc,CFGGraph), 772 MPAcc; 773create_cfggraph([Label|Ls],Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph) -> 774 Preds = ?CFG:pred(Cfg, Label), 775 case Preds of 776 [] -> 777 exit({?MODULE,do_not_call_on_top,{"Why the hell do we call that function on the start label???",Label}}); 778 [P] -> 779 Code = ?BB:code(?CFG:bb(Cfg, Label)), 780 Defs = get_defs_in_non_merge_block(Code, []), 781 ?pp_debug("~nAdding a vertex for ~w", [Label]), 782 Succs = ?CFG:succ(Cfg, Label), 783 NewToBeFactorizedAcc = 784 case Succs of 785 [] -> %% Exit point 786 ?GRAPH:add_vertex(CFGGraph, Label, #block{type = exit}), 787 ToBeFactorizedAcc; 788 _ -> %% Split point 789 ?GRAPH:add_vertex(CFGGraph,Label,#block{type=not_mp,attributes={P,Succs}}), 790 [Label|ToBeFactorizedAcc] 791 end, 792 ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[P,Label,Defs]), 793 case ?GRAPH:add_edge(CFGGraph,P,Label,Defs) of 794 {error,Reason} -> 795 exit({?MODULE,forget_that_for_christs_sake_bingwen_please,{"Bad edge",Reason}}); 796 _ -> 797 ok 798 end, 799 create_cfggraph(Ls,Cfg,CFGGraph,NewToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph); 800 _ -> %% Merge point 801 Code = ?BB:code(?CFG:bb(Cfg,Label)), 802 {Defs,Xsis,Maps,Uses} = get_info_in_merge_block(Code,XsiGraph,[],[],gb_trees:empty(),gb_trees:empty()), 803 Attributes = #mp{preds=Preds,xsis=Xsis,defs=Defs,maps=Maps,uses=Uses}, 804 MergeBlock = #block{type=mp,attributes=Attributes}, 805 ?pp_debug("~nAdding a vertex for ~w with Defs= ~w",[Label,Defs]), 806 ?GRAPH:add_vertex(CFGGraph,Label,MergeBlock), 807 %% Add edges 808 NewLateEdges = add_edges_for_mp(Preds,Label,LateEdges), 809 create_cfggraph(Ls,Cfg,CFGGraph,ToBeFactorizedAcc,[Label|MPAcc],NewLateEdges,XsiGraph) 810 end. 811 812get_defs_in_non_merge_block([], Acc) -> 813 ?SETS:from_list(Acc); 814get_defs_in_non_merge_block([Inst|Rest], Acc) -> 815 case Inst of 816 #pre_candidate{} -> 817 Def = Inst#pre_candidate.def, 818 case Def of 819 #temp{} -> 820 %% {temp,Key,_Var} -> 821 %% get_defs_in_non_merge_block(Rest,[Key|Acc]); 822 get_defs_in_non_merge_block(Rest, [Def#temp.key|Acc]); 823 _-> %% Real variables or bottom 824 get_defs_in_non_merge_block(Rest, Acc) 825 end; 826 _ -> 827 get_defs_in_non_merge_block(Rest, Acc) 828 end. 829 830get_info_in_merge_block([],_XsiGraph,Defs,Xsis,Maps,Uses) -> 831 {?SETS:from_list(Defs),Xsis,Maps,Uses}; %% Xsis are in backward order 832get_info_in_merge_block([Inst|Rest],XsiGraph,Defs,Xsis,Maps,Uses) -> 833 case Inst of 834 #pre_candidate{} -> 835 Def = Inst#pre_candidate.def, 836 case Def of 837 #temp{} -> 838 get_info_in_merge_block(Rest,XsiGraph,[Def#temp.key|Defs],Xsis,Maps,Uses); 839 _ -> 840 get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses) 841 end; 842 #xsi_link{} -> 843 Key = Inst#xsi_link.num, 844 {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,Key), 845 OpList = xsi_oplist(Xsi), 846 {NewMaps,NewUses} = add_map_and_uses(OpList,Key,Maps,Uses), 847 get_info_in_merge_block(Rest,XsiGraph,Defs,[Key|Xsis],NewMaps,NewUses); 848 _ -> 849 get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses) 850 end. 851 852add_edges_for_mp([], _Label, LateEdges) -> 853 LateEdges; 854add_edges_for_mp([P|Ps], Label, LateEdges) -> 855 add_edges_for_mp(Ps,Label,[{P,Label}|LateEdges]). 856 857%% Doesn't do anything so far 858add_map_and_uses([], _Key, Maps, Uses) -> 859 {Maps, Uses}; 860add_map_and_uses([XsiOp|Ops], Key, Maps, Uses) -> 861 {NewMaps, NewUses} = 862 case XsiOp#xsi_op.op of 863 #bottom{} -> 864 Set = case gb_trees:lookup(XsiOp, Maps) of 865 {value, V} -> 866 ?SETS:add_element(Key, V); 867 none -> 868 ?SETS:from_list([Key]) 869 end, 870 {gb_trees:enter(XsiOp, Set, Maps), Uses}; 871 #temp{} -> 872 Set = case gb_trees:lookup(XsiOp, Maps) of 873 {value, V} -> 874 ?SETS:add_element(Key, V); 875 none -> 876 ?SETS:from_list([Key]) 877 end, 878 Pred = XsiOp#xsi_op.pred, 879 OOP = XsiOp#xsi_op.op, 880 SSet = case gb_trees:lookup(Pred, Uses) of 881 {value, VV} -> 882 ?SETS:add_element(OOP#temp.key, VV); 883 none -> 884 ?SETS:from_list([OOP#temp.key]) 885 end, 886 {gb_trees:enter(XsiOp, Set, Maps), gb_trees:enter(Pred, SSet, Uses)}; 887 #eop{} -> 888 Set = case gb_trees:lookup(XsiOp, Maps) of 889 {value, V} -> 890 ?SETS:add_element(Key, V); 891 none -> 892 ?SETS:from_list([Key]) 893 end, 894 Pred = XsiOp#xsi_op.pred, 895 Op = XsiOp#xsi_op.op, 896 SSet = case gb_trees:lookup(Pred, Uses) of 897 {value, VV} -> 898 ?SETS:add_element(Op#eop.stopped_by, VV); 899 none -> 900 ?SETS:from_list([Op#eop.stopped_by]) 901 end, 902 {gb_trees:enter(XsiOp, Set, Maps), gb_trees:enter(Pred, SSet, Uses)}; 903 _-> 904 {Maps, Uses} 905 end, 906 add_map_and_uses(Ops, Key, NewMaps, NewUses). 907 908post_process([], _CFGGraph) -> ok; 909post_process([E|Es], CFGGraph) -> 910 {Pred,Label} = E, 911 {_PP,Block} = ?GRAPH:vertex(CFGGraph,Label), 912 Att = Block#block.attributes, 913 Uses = Att#mp.uses, 914 SetToAdd = case gb_trees:lookup(Pred,Uses) of 915 {value, Set} -> 916 Set; 917 none -> 918 ?SETS:new() 919 end, 920 %% ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[Pred,Label,SetToAdd]), 921 ?GRAPH:add_edge(CFGGraph, Pred, Label, SetToAdd), 922 post_process(Es, CFGGraph). 923 924factorize([], _CFGGraph) -> ok; 925factorize([P|Ps], CFGGraph) -> 926 [OE|OEs] = ?GRAPH:out_edges(CFGGraph,P), 927 %% ?pp_debug("~nIn_degrees ~w : ~w",[P,?GRAPH:in_degree(CFGGraph,P)]), 928 [InEdge] = ?GRAPH:in_edges(CFGGraph,P), 929 {E,V1,V2,Label} = ?GRAPH:edge(CFGGraph,InEdge), 930 {_OEE,_OEV1,_OEV2,LOE} = ?GRAPH:edge(CFGGraph,OE), 931 List = shoot_info_upwards(OEs,LOE,CFGGraph), 932 NewLabel = ?SETS:union(Label,List), 933 ?GRAPH:add_edge(CFGGraph,E,V1,V2,NewLabel), 934 factorize(Ps, CFGGraph). 935 936shoot_info_upwards([], Acc, _CFGGraph) -> Acc; 937shoot_info_upwards([E|Es], Acc, CFGGraph) -> 938 {_E,_V1,_V2,Set} = ?GRAPH:edge(CFGGraph,E), 939 NewAcc = ?SETS:intersection(Acc, Set), 940 case ?SETS:size(NewAcc) of 941 0 -> NewAcc; 942 _ -> shoot_info_upwards(Es,NewAcc,CFGGraph) 943 end. 944 945%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 946%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DOWNSAFETY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 947%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 948 949perform_downsafety([], _G, _XsiG) -> 950 ok; 951perform_downsafety([MP|MPs], G, XG) -> 952 {V,Block} = ?GRAPH:vertex(G, MP), 953 NDS = ?SETS:new(), 954 Att = Block#block.attributes, 955 Maps = Att#mp.maps, 956 Defs = Att#mp.defs, 957 OutEdges = ?GRAPH:out_edges(G, MP), 958 %% ?pp_debug("~n Inspection Maps : ~w",[Maps]), 959 NewNDS = parse_keys(gb_trees:keys(Maps),Maps,OutEdges,G,Defs,NDS,XG), 960 NewAtt = Att#mp{ndsSet = NewNDS}, 961 ?GRAPH:add_vertex(G, V, Block#block{attributes = NewAtt}), 962 ?pp_debug("~n Not Downsafe at L~w: ~w", [V, NewNDS]), 963 %%io:format(standard_io,"~n Not Downsafe at L~w: ~w",[V,NewNDS]), 964 perform_downsafety(MPs, G, XG). 965 966parse_keys([], _Maps, _OutEdges, _G, _Defs, NDS, _XsiG) -> 967 NDS; 968parse_keys([M|Ms], Maps, OutEdges, G, Defs, NDS, XsiG) -> 969 KillerSet = gb_trees:get(M,Maps), 970 %% ?pp_debug("~n Inspection ~w -> ~w",[M,KillerSet]), 971 TempSet = ?SETS:intersection(KillerSet,Defs), 972 NewNDS = case ?SETS:size(TempSet) of 973 0 -> getNDS(M,KillerSet,NDS,OutEdges,G,XsiG); 974 _ -> 975 %% One Xsi which has M as operand has killed it 976 %% M is then Downsafe 977 %% and is not added to the NotDownsafeSet (NDS) 978 NDS 979 end, 980 parse_keys(Ms, Maps, OutEdges, G, Defs, NewNDS, XsiG). 981 982getNDS(_M, _KillerSet, NDS, [], _G, _XsiG) -> 983 NDS; 984getNDS(M, KillerSet, NDS, [E|Es], G, XsiG) -> 985 {_EE,_V1,_V2,Label} = ?GRAPH:edge(G, E), 986 Set = ?SETS:intersection(KillerSet, Label), 987 %% ?pp_debug("~n ######## Intersection between KillerSet: ~w and Label: ~w",[KillerSet,Label]), 988 %% ?pp_debug("~n ######## ~w",[Set]), 989 case ?SETS:size(Set) of 990 0 -> 991 %% M is not downsafe 992 ?SETS:add_element(M, NDS); 993 _ -> 994 %% Try the other edges 995 getNDS(M, KillerSet, NDS, Es, G, XsiG) 996 end. 997 998%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 999%%%%%%%%%%%%%%%%%%%%%%%%%%%%% WILL BE AVAILABLE %%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1000%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1001 1002perform_will_be_available(XsiGraph,CFGGraph,Options) -> 1003 Keys = ?GRAPH:vertices(XsiGraph), 1004 ?pp_debug("~n############ Can Be Available ##########~n",[]), 1005 ?option_time(perform_can_be_available(Keys,XsiGraph,CFGGraph),"RTL A-SSAPRE WillBeAvailable - Compute CanBeAvailable",Options), 1006 ?pp_debug("~n############ Later ##########~n",[]), 1007 ?option_time(perform_later(Keys,XsiGraph),"RTL A-SSAPRE WillBeAvailable - Compute Later",Options). 1008 1009perform_can_be_available([],_XsiGraph,_CFGGraph) -> ok; 1010perform_can_be_available([Key|Keys],XsiGraph,CFGGraph) -> 1011 {V,Xsi} = ?GRAPH:vertex(XsiGraph,Key), 1012 case Xsi#xsi.cba of 1013 undefined -> 1014 {_VV,Block} = ?GRAPH:vertex(CFGGraph,Xsi#xsi.label), 1015 Att = Block#block.attributes, 1016 NDS = Att#mp.ndsSet, 1017 OpList = ?SETS:from_list(xsi_oplist(Xsi)), 1018 Set = ?SETS:intersection(NDS,OpList), 1019 case ?SETS:size(Set) of 1020 0 -> 1021 ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = true}), 1022 perform_can_be_available(Keys, XsiGraph, CFGGraph); 1023 _ -> 1024 LIST = [X || #temp{key=X} <- ?SETS:to_list(Set)], 1025 case LIST of 1026 [] -> 1027 ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = false}), 1028 ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, Key), 1029 propagate_cba(ImmediateParents,XsiGraph,Xsi#xsi.def,CFGGraph); 1030 _ -> 1031 ok 1032 end, 1033 perform_can_be_available(Keys, XsiGraph, CFGGraph) 1034 end; 1035 _ -> %% True or False => recurse 1036 perform_can_be_available(Keys, XsiGraph, CFGGraph) 1037 end. 1038 1039propagate_cba([],_XG,_Def,_CFGG) -> ok; 1040propagate_cba([IPX|IPXs],XsiGraph,XsiDef,CFGGraph) -> 1041 {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX), 1042 {_VV,Block} = ?GRAPH:vertex(CFGGraph,IPXsi#xsi.label), 1043 Att = Block#block.attributes, 1044 NDS = Att#mp.ndsSet, 1045 List = ?SETS:to_list(?SETS:intersection(NDS,?SETS:from_list(xsi_oplist(IPXsi)))), 1046 case IPXsi#xsi.cba of 1047 false -> ok; 1048 _ -> 1049 case lists:keymember(XsiDef, #xsi_op.op, List) of 1050 true -> 1051 ?GRAPH:add_vertex(XsiGraph, V, IPXsi#xsi{cba = false}), 1052 ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, IPX), 1053 propagate_cba(ImmediateParents,XsiGraph,IPXsi#xsi.def,CFGGraph); 1054 _ -> 1055 ok 1056 end 1057 end, 1058 propagate_cba(IPXs,XsiGraph,XsiDef,CFGGraph). 1059 1060perform_later([], _XsiGraph) -> ok; 1061perform_later([Key|Keys], XsiGraph) -> 1062 {V, Xsi} = ?GRAPH:vertex(XsiGraph, Key), 1063 %% ?pp_debug("~n DEBUG : inspecting later of ~w (~w)~n",[Key,Xsi#xsi.later]), 1064 case Xsi#xsi.later of 1065 undefined -> 1066 OpList = xsi_oplist(Xsi), 1067 case parse_ops(OpList,fangpi) of %% It means "fart" in chinese :D 1068 has_temp -> 1069 perform_later(Keys,XsiGraph); 1070 has_real -> 1071 case Xsi#xsi.cba of 1072 true -> 1073 ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true}); 1074 undefined -> 1075 ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true}); 1076 _ -> 1077 ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=false}) 1078 end, 1079 AllParents = digraph_utils:reaching([Key], XsiGraph), 1080 ?pp_debug("~nPropagating to all parents of t~w: ~w",[Key,AllParents]), 1081 propagate_later(AllParents,XsiGraph), 1082 perform_later(Keys,XsiGraph); 1083 _ -> %% Just contains bottoms and/or expressions 1084 ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=true}), 1085 perform_later(Keys,XsiGraph) 1086 end; 1087 _ -> %% True or False => recurse 1088 perform_later(Keys,XsiGraph) 1089 end. 1090 1091propagate_later([], _XG) -> ok; 1092propagate_later([IPX|IPXs], XsiGraph) -> 1093 {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX), 1094 case IPXsi#xsi.later of 1095 false -> 1096 ?pp_debug("~nThrough propagation, later of t~w is already reset",[IPX]), 1097 propagate_later(IPXs,XsiGraph); 1098 _ -> 1099 ?pp_debug("~nThrough propagation, resetting later of t~w",[IPX]), 1100 case IPXsi#xsi.cba of 1101 true -> 1102 ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true}); 1103 undefined -> 1104 ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true}); 1105 _ -> 1106 ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=false}) 1107 end, 1108 propagate_later(IPXs,XsiGraph) 1109 end. 1110 1111parse_ops([], Res) -> 1112 Res; 1113parse_ops([Op|Ops], Res) -> 1114 case Op#xsi_op.op of 1115 #temp{} -> 1116 NewRes = has_temp, 1117 parse_ops(Ops,NewRes); 1118 #bottom{} -> 1119 parse_ops(Ops,Res); 1120 #eop{} -> 1121 parse_ops(Ops,Res); 1122 _ -> 1123 has_real 1124 end. 1125 1126%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1127%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CODE MOTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1128%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1129 1130perform_code_motion([], Cfg, _XsiG) -> 1131 Cfg; 1132perform_code_motion([L|Labels], Cfg, XsiG) -> 1133 Code=?BB:code(?CFG:bb(Cfg,L)), 1134 ?pp_debug("~n################ Code Motion in L~w~n",[L]), 1135 ?pp_debug("~nCode to move ~n",[]), 1136 pp_instrs(Code,XsiG), 1137 NewCfg = code_motion_in_block(L,Code,Cfg,XsiG,[],gb_trees:empty()), 1138 ?pp_debug("~n################ Code Motion successful in L~w~n",[L]), 1139 perform_code_motion(Labels,NewCfg,XsiG). 1140 1141code_motion_in_block(Label,[],Cfg,_XsiG,Visited,InsertionsAcc) -> 1142 InsertionsAlong = gb_trees:keys(InsertionsAcc), 1143 Code = lists:reverse(Visited), 1144 NewBB = ?BB:mk_bb(Code), 1145 Cfg2 = ?CFG:bb_add(Cfg,Label,NewBB), 1146 %% Must come after the bb_add, since redirect will update the Phis too... 1147 Cfg3 = make_insertions(Label,InsertionsAlong,InsertionsAcc,Cfg2), 1148 %% ?pp_debug("~nChecking the Code at L~w:~n~p",[Label,?BB:code(?CFG:bb(Cfg3,Label))]), 1149 Cfg3; 1150code_motion_in_block(L,[Inst|Insts],Cfg,XsiG,Visited,InsertionsAcc) -> 1151 ?pp_debug("~nInspecting Inst : ~n",[]),pp_instr(Inst,XsiG), 1152 case Inst of 1153 #pre_candidate{} -> 1154 Def = Inst#pre_candidate.def, 1155 Alu = Inst#pre_candidate.alu, 1156 InstToAdd = 1157 case Def of 1158 bottom -> 1159 Alu; 1160 #temp{} -> 1161 Key = Def#temp.key, 1162 {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), 1163 case Xsi#xsi.wba of 1164 true -> 1165 %% Turn into a move 1166 Dst = ?RTL:alu_dst(Alu), 1167 Move = ?RTL:mk_move(Dst,Def#temp.var), 1168 pp_instr(Inst#pre_candidate.alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil), 1169 %% Counting redundancies 1170 redundancy_add(), 1171 Move; 1172 _ -> 1173 Alu 1174 end; 1175 _ -> %% Def is a real variable 1176 %% Turn into a move 1177 Dst = ?RTL:alu_dst(Alu), 1178 Move = ?RTL:mk_move(Dst,Def), 1179 pp_instr(Alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil), 1180 %% Counting redundancies 1181 redundancy_add(), 1182 Move 1183 end, 1184 code_motion_in_block(L,Insts,Cfg,XsiG,[InstToAdd|Visited],InsertionsAcc); 1185 #xsi_link{} -> 1186 Key = Inst#xsi_link.num, 1187 {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), 1188 case Xsi#xsi.wba of 1189 true -> 1190 %% Xsi is a WBA, it might trigger insertions 1191 OpList = xsi_oplist(Xsi), 1192 ?pp_debug(" This Xsi is a 'Will be available'",[]), 1193 %% Cleaning the instruction 1194 Expr = prepare_inst(Xsi#xsi.inst), 1195 {NewOpList,NewInsertionsAcc} = get_insertions(OpList,[],InsertionsAcc,Visited,Expr,XsiG), 1196 %% Making Xsi a Phi with Oplist 1197 PhiOpList = [{Pred,Var} || #xsi_op{pred=Pred,op=Var} <- NewOpList], 1198 Def = Xsi#xsi.def, 1199 Phi = ?RTL:phi_arglist_update(?RTL:mk_phi(Def#temp.var),PhiOpList), 1200 ?pp_debug("~n Xsi is turned into Phi : ~w",[Phi]), 1201 code_motion_in_block(L,Insts,Cfg,XsiG,[Phi|Visited],NewInsertionsAcc); 1202 _ -> 1203 ?pp_debug(" This Xsi is not a 'Will be available'",[]), 1204 code_motion_in_block(L,Insts,Cfg,XsiG,Visited,InsertionsAcc) 1205 end; 1206%% phi -> 1207%% code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc); 1208 _ -> 1209 %% Other instructions.... Phis too 1210 code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc) 1211 end. 1212 1213prepare_inst(Expr) -> 1214 S1 = ?RTL:alu_src1(Expr), 1215 S2 = ?RTL:alu_src2(Expr), 1216 NewInst = case S1 of 1217 #temp{} -> ?RTL:alu_src1_update(Expr,S1#temp.var); 1218 _ -> Expr 1219 end, 1220 case S2 of 1221 #temp{} -> ?RTL:alu_src2_update(NewInst,S2#temp.var); 1222 _ -> NewInst 1223 end. 1224 1225get_insertions([],OpAcc,InsertionsAcc,_Visited,_Expr,_XsiG) -> 1226 {OpAcc,InsertionsAcc}; 1227get_insertions([XsiOp|Ops],OpAcc,InsertionsAcc,Visited,Expr,XsiG) -> 1228 Pred = XsiOp#xsi_op.pred, 1229 Op = XsiOp#xsi_op.op, 1230 {Dst, NewInsertionsAcc} = 1231 case Op of 1232 #bottom{} -> 1233 case gb_trees:lookup(Pred,InsertionsAcc) of 1234 {value,Insertion} -> 1235 From = Insertion#insertion.from, 1236 case lists:keyfind(Op, 1, From) of 1237 false -> 1238 ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), 1239 D = Op#bottom.var, 1240 Expr2 = ?RTL:alu_dst_update(Expr,D), 1241 Inst = manufacture_computation(Pred,Expr2,Visited), 1242 Code = Insertion#insertion.code, 1243 NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]}, 1244 {D, gb_trees:update(Pred, NewInsertion, InsertionsAcc)}; 1245 {_, Val} -> 1246 ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op), 1247 {Val, InsertionsAcc} 1248 end; 1249 none -> 1250 ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op), 1251 D = Op#bottom.var, 1252 Expr2 = ?RTL:alu_dst_update(Expr, D), 1253 Inst = manufacture_computation(Pred,Expr2,Visited), 1254 NewInsertion = #insertion{from=[{Op,D}],code=[Inst]}, 1255 {D, gb_trees:insert(Pred,NewInsertion, InsertionsAcc)} 1256 end; 1257 #const_expr{} -> 1258 case gb_trees:lookup(Pred,InsertionsAcc) of 1259 {value,Insertion} -> 1260 From = Insertion#insertion.from, 1261 case lists:keyfind(Op, 1, From) of 1262 false -> 1263 ?pp_debug("~nThere have been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), 1264 D = Op#const_expr.var, 1265 Val = Op#const_expr.value, 1266 Inst = ?RTL:mk_move(D, Val), 1267 Code = Insertion#insertion.code, 1268 NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]}, 1269 {D, gb_trees:update(Pred,NewInsertion,InsertionsAcc)}; 1270 {_, Val} -> 1271 ?pp_debug("~nThere have been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op), 1272 {Val, InsertionsAcc} 1273 end; 1274 none -> 1275 ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op), 1276 D = Op#const_expr.var, 1277 Val = Op#const_expr.value, 1278 Inst = ?RTL:mk_move(D, Val), 1279 NewInsertion = #insertion{from=[{Op,D}],code=[Inst]}, 1280 {D, gb_trees:insert(Pred,NewInsertion, InsertionsAcc)} 1281 end; 1282 #eop{} -> 1283 %% We treat expressions like bottoms 1284 %% The value must be recomputed, and therefore not available... 1285 case gb_trees:lookup(Pred,InsertionsAcc) of 1286 {value,Insertion} -> 1287 From = Insertion#insertion.from, 1288 case lists:keyfind(Op, 1, From) of 1289 false -> 1290 ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), 1291 D = Op#eop.var, 1292 Expr2 = ?RTL:alu_dst_update(Expr, D), 1293 Inst = manufacture_computation(Pred,Expr2,Visited), 1294 Code = Insertion#insertion.code, 1295 NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]}, 1296 {D, gb_trees:update(Pred,NewInsertion, InsertionsAcc)}; 1297 {_, Val} -> 1298 ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op), 1299 {Val, InsertionsAcc} 1300 end; 1301 none -> 1302 ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op), 1303 D = Op#eop.var, 1304 Expr2 = ?RTL:alu_dst_update(Expr, D), 1305 Inst = manufacture_computation(Pred,Expr2,Visited), 1306 NewInsertion = #insertion{from=[{Op,D}],code=[Inst]}, 1307 {D, gb_trees:insert(Pred, NewInsertion, InsertionsAcc)} 1308 end; 1309 #temp{} -> 1310 case gb_trees:lookup(Pred,InsertionsAcc) of 1311 {value,Insertion} -> 1312 From = Insertion#insertion.from, 1313 case lists:keyfind(Op, 1, From) of 1314 false -> 1315 ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), 1316 Key = Op#temp.key, 1317 {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), 1318 case Xsi#xsi.wba of 1319 true -> 1320 ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]), 1321 {Op#temp.var, InsertionsAcc}; 1322 _ -> 1323 ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]), 1324 D = ?RTL:mk_new_var(), 1325 Expr2 = ?RTL:alu_dst_update(Expr, D), 1326 Inst = manufacture_computation(Pred,Expr2,Visited), 1327 Code = Insertion#insertion.code, 1328 NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]}, 1329 {D, gb_trees:update(Pred, NewInsertion, InsertionsAcc)} 1330 end; 1331 {_, Val} -> 1332 ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too (Op=~w)",[Pred,Op]), 1333 ?pp_debug("~nThis means, this temp is a WBA Xsi's definition",[]), 1334 {Val, InsertionsAcc} 1335 end; 1336 none -> 1337 ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course | Op=",[Pred]),pp_arg(Op), 1338 Key = Op#temp.key, 1339 {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), 1340 case Xsi#xsi.wba of 1341 true -> 1342 ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]), 1343 {Op#temp.var, InsertionsAcc}; 1344 _ -> 1345 ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]), 1346 D = ?RTL:mk_new_var(), 1347 Expr2 = ?RTL:alu_dst_update(Expr, D), 1348 Inst = manufacture_computation(Pred,Expr2,Visited), 1349 NewInsertion = #insertion{from=[{Op,D}],code=[Inst]}, 1350 {D, gb_trees:insert(Pred, NewInsertion, InsertionsAcc)} 1351 end 1352 end; 1353 _ -> 1354 ?pp_debug("~nThe operand (Op=",[]),pp_arg(Op),?pp_debug(") is a real variable, no need for insertion along L~w",[Pred]), 1355 {Op, InsertionsAcc} 1356 end, 1357 NewXsiOp = XsiOp#xsi_op{op=Dst}, 1358 get_insertions(Ops, [NewXsiOp|OpAcc], NewInsertionsAcc, Visited, Expr, XsiG). 1359 1360manufacture_computation(_Pred, Expr, []) -> 1361 ?pp_debug("~n Manufactured computation : ~w", [Expr]), 1362 Expr; 1363manufacture_computation(Pred, Expr, [I|Rest]) -> 1364 %% ?pp_debug("~n Expr = ~w",[Expr]), 1365 SRC1 = ?RTL:alu_src1(Expr), 1366 SRC2 = ?RTL:alu_src2(Expr), 1367 case I of 1368 #xsi_link{} -> 1369 exit({?MODULE,should_not_be_a_xsi_link,{"Why the hell do we still have a xsi link???",I}}); 1370 #xsi{} -> 1371 exit({?MODULE,should_not_be_a_xsi,{"Why the hell do we still have a xsi ???",I}}); 1372 #phi{} -> 1373 DST = ?RTL:phi_dst(I), 1374 Arg = ?RTL:phi_arg(I,Pred), 1375 NewInst = case DST =:= SRC1 of 1376 true -> ?RTL:alu_src1_update(Expr,Arg); 1377 false -> Expr 1378 end, 1379 NewExpr = case DST =:= SRC2 of 1380 true -> ?RTL:alu_src2_update(NewInst,Arg); 1381 false -> NewInst 1382 end, 1383 manufacture_computation(Pred,NewExpr,Rest) 1384 end. 1385 1386make_insertions(_L, [], _ITree, Cfg) -> 1387 Cfg; 1388make_insertions(L, [OldPred|Is], ITree, Cfg) -> 1389 NewPred = ?RTL:label_name(?RTL:mk_new_label()), 1390 I = gb_trees:get(OldPred, ITree), 1391 CodeToInsert = lists:reverse([?RTL:mk_goto(L)|I#insertion.code]), 1392 BBToInsert = ?BB:mk_bb(CodeToInsert), 1393 NewCfg = ?CFG:bb_insert_between(Cfg, NewPred, BBToInsert, OldPred, L), 1394 make_insertions(L, Is, ITree, NewCfg). 1395 1396%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1397%%%%%%%%%%%%%%%%%%%%%%%%%%%%% XSI INTERFACE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1398%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1399 1400xsi_oplist(#xsi{opList=OpList}) -> 1401 case OpList of undefined -> [] ; _ -> OpList end. 1402xsi_arg(Xsi, Pred) -> 1403 case lists:keyfind(Pred, #xsi_op.pred, xsi_oplist(Xsi)) of 1404 false -> 1405 undetermined_operand; 1406 R -> 1407 R#xsi_op.op 1408 end. 1409xsi_arg_update(Xsi, Pred, Op) -> 1410 NewOpList = lists:keyreplace(Pred, #xsi_op.pred, xsi_oplist(Xsi), 1411 #xsi_op{pred=Pred,op=Op}), 1412 Xsi#xsi{opList=NewOpList}. 1413 1414%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1415%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1416%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1417 1418-ifndef(SSAPRE_DEBUG). 1419 1420%%pp_cfg(Cfg,_) -> ?CFG:pp(Cfg). 1421pp_cfg(_,_) -> ok. 1422pp_instr(_,_) -> ok. 1423pp_instrs(_,_) -> ok. 1424pp_expr(_) -> ok. 1425pp_xsi(_) -> ok. 1426pp_arg(_) -> ok. 1427pp_xsigraph(_) -> ok. 1428pp_cfggraph(_) -> ok. 1429%% pp_xsigraph(G) -> 1430%% Vertices = lists:sort(?GRAPH:vertices(G)), 1431%% io:format(standard_io, "Size of the Xsi Graph: ~w", [length(Vertices)]). 1432%% pp_cfggraph(G) -> 1433%% Vertices = lists:sort(?GRAPH:vertices(G)), 1434%% io:format(standard_io, "Size of the CFG Graph: ~w", [length(Vertices)]). 1435 1436-else. 1437 1438pp_cfg(Cfg, Graph) -> 1439 Labels = ?CFG:preorder(Cfg), 1440 pp_blocks(Labels, Cfg, Graph). 1441 1442pp_blocks([], _, _) -> 1443 ok; 1444pp_blocks([L|Ls], Cfg, Graph) -> 1445 Code = hipe_bb:code(?CFG:bb(Cfg,L)), 1446 io:format(standard_io,"~n########## Label L~w~n", [L]), 1447 pp_instrs(Code, Graph), 1448 pp_blocks(Ls, Cfg, Graph). 1449 1450pp_instrs([], _) -> 1451 ok; 1452pp_instrs([I|Is], Graph) -> 1453 pp_instr(I, Graph), 1454 pp_instrs(Is, Graph). 1455 1456pp_xsi_link(Key, Graph) -> 1457 {_Key,Xsi} = ?GRAPH:vertex(Graph, Key), 1458 pp_xsi(Xsi). 1459 1460pp_xsi(Xsi) -> 1461 io:format(standard_io, " [L~w] ", [Xsi#xsi.label]), 1462 io:format(standard_io, "[", []), pp_expr(Xsi#xsi.inst), 1463 io:format(standard_io, "] Xsi(", []), pp_xsi_args(xsi_oplist(Xsi)), 1464 io:format(standard_io, ") (", []), pp_xsi_def(Xsi#xsi.def), 1465 io:format(standard_io, ") cba=~w, later=~w | wba=~w~n", [Xsi#xsi.cba,Xsi#xsi.later,Xsi#xsi.wba]). 1466 1467pp_instr(I, Graph) -> 1468 case I of 1469 #alu{} -> 1470 io:format(standard_io, " ", []), 1471 pp_arg(?RTL:alu_dst(I)), 1472 io:format(standard_io, " <- ", []), 1473 pp_expr(I), 1474 io:format(standard_io, "~n", []); 1475 _ -> 1476 try ?RTL:pp_instr(standard_io, I) 1477 catch _:_ -> 1478 case I of 1479 #pre_candidate{} -> 1480 pp_pre(I); 1481 #xsi{} -> 1482 pp_xsi(I); 1483 #xsi_link{} -> 1484 pp_xsi_link(I#xsi_link.num, Graph); 1485 _-> 1486 io:format(standard_io,"*** ~w ***~n", [I]) 1487 end 1488 end 1489 end. 1490 1491pp_pre(I) -> 1492 A = I#pre_candidate.alu, 1493 io:format(standard_io, " ", []), 1494 pp_arg(?RTL:alu_dst(A)), 1495 io:format(standard_io, " <- ", []),pp_expr(A), 1496 io:format(standard_io, " [ ", []),pp_arg(I#pre_candidate.def), 1497 %%io:format(standard_io, "~w", [I#pre_candidate.def]), 1498 io:format(standard_io, " ]~n",[]). 1499 1500pp_expr(I) -> 1501 pp_arg(?RTL:alu_dst(I)), 1502 io:format(standard_io, " <- ", []), 1503 pp_arg(?RTL:alu_src1(I)), 1504 io:format(standard_io, " ~w ", [?RTL:alu_op(I)]), 1505 pp_arg(?RTL:alu_src2(I)). 1506 1507pp_arg(Arg) -> 1508 case Arg of 1509 bottom -> 1510 io:format(standard_io, "_|_", []); 1511 #bottom{} -> 1512 io:format(standard_io, "_|_:~w (", [Arg#bottom.key]),pp_arg(Arg#bottom.var),io:format(standard_io,")",[]); 1513 #temp{} -> 1514 pp_xsi_def(Arg); 1515 #eop{} -> 1516 io:format(standard_io,"#",[]),pp_expr(Arg#eop.expr),io:format(standard_io,"(",[]),pp_arg(Arg#eop.var),io:format(standard_io,")#",[]); 1517 #const_expr{} -> 1518 io:format(standard_io,"*",[]),pp_arg(Arg#const_expr.var),io:format(standard_io," -> ",[]),pp_arg(Arg#const_expr.value),io:format(standard_io,"*",[]); 1519 undefined -> 1520 io:format(standard_io, "...", []); %%"undefined", []); 1521 _-> 1522 case Arg of 1523 #alu{} -> 1524 pp_expr(Arg); 1525 _-> 1526 ?RTL:pp_arg(standard_io, Arg) 1527 end 1528 end. 1529 1530pp_args([]) -> 1531 ok; 1532pp_args(undefined) -> 1533 io:format(standard_io, "...,...,...", []); 1534pp_args([A]) -> 1535 pp_arg(A); 1536pp_args([A|As]) -> 1537 pp_arg(A), 1538 io:format(standard_io, ", ", []), 1539 pp_args(As). 1540 1541pp_xsi_args([]) -> ok; 1542pp_xsi_args([XsiOp]) -> 1543 io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]), 1544 pp_arg(XsiOp#xsi_op.op), 1545 io:format(standard_io, "}", []); 1546pp_xsi_args([XsiOp|Args]) -> 1547 io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]), 1548 pp_arg(XsiOp#xsi_op.op), 1549 io:format(standard_io, "}, ", []), 1550 pp_xsi_args(Args); 1551pp_xsi_args(Args) -> 1552 pp_args(Args). 1553 1554pp_xsi_def(Arg) -> 1555 D = Arg#temp.key, 1556 V = Arg#temp.var, 1557 io:format(standard_io, "t~w (", [D]),pp_arg(V),io:format(standard_io,")",[]). 1558 1559pp_cfggraph(G) -> 1560 Vertices = lists:sort(?GRAPH:vertices(G)), 1561 io:format(standard_io, "Size of the CFG Graph: ~w ~n", [length(Vertices)]), 1562 pp_cfgvertex(Vertices, G). 1563 1564pp_xsigraph(G) -> 1565 Vertices = lists:sort(?GRAPH:vertices(G)), 1566 io:format(standard_io, "Size of the Xsi Graph: ~w ~n", [length(Vertices)]), 1567 pp_xsivertex(Vertices,G). 1568 1569pp_xsivertex([], _G) -> 1570 ok; 1571pp_xsivertex([Key|Keys], G) -> 1572 {V,Xsi} = ?GRAPH:vertex(G, Key), 1573 OutNeighbours = ?GRAPH:out_neighbours(G, V), 1574 ?pp_debug(" ~w -> ~w", [V,OutNeighbours]), pp_xsi(Xsi), 1575 pp_xsivertex(Keys, G). 1576 1577pp_cfgvertex([], _G) -> 1578 ok; 1579pp_cfgvertex([Key|Keys], G) -> 1580 {V,Block} = ?GRAPH:vertex(G,Key), 1581 case Block#block.type of 1582 mp -> 1583 ?pp_debug("~n Block ~w's attributes: ~n", [V]), 1584 pp_attributes(Block), 1585 ?pp_debug("~n Block ~w's edges: ~n", [V]), 1586 pp_edges(G, ?GRAPH:in_edges(G,Key), ?GRAPH:out_edges(G,Key)); 1587 _-> 1588 ok 1589 end, 1590 pp_cfgvertex(Keys, G). 1591 1592pp_attributes(Block) -> 1593 Att = Block#block.attributes, 1594 case Att of 1595 undefined -> 1596 ok; 1597 _ -> 1598 ?pp_debug(" Maps: ~n",[]),pp_maps(gb_trees:keys(Att#mp.maps),Att#mp.maps), 1599 ?pp_debug(" Uses: ~n",[]),pp_uses(gb_trees:keys(Att#mp.uses),Att#mp.uses), 1600 ?pp_debug(" Defs: ~w~n",[Att#mp.defs]), 1601 ?pp_debug(" Xsis: ~w~n",[Att#mp.xsis]), 1602 ?pp_debug(" NDS : ",[]),pp_nds(?SETS:to_list(Att#mp.ndsSet)) 1603 end. 1604 1605pp_maps([], _Maps) -> ok; 1606pp_maps([K|Ks], Maps) -> 1607 ?pp_debug(" ",[]),pp_arg(K#xsi_op.op),?pp_debug("-> ~w~n",[?SETS:to_list(gb_trees:get(K,Maps))]), 1608 pp_maps(Ks, Maps). 1609 1610pp_uses([], _Maps) -> ok; 1611pp_uses([K|Ks], Maps) -> 1612 ?pp_debug(" ~w -> ~w~n",[K,?SETS:to_list(gb_trees:get(K,Maps))]), 1613 pp_uses(Ks, Maps). 1614 1615pp_nds([]) -> ?pp_debug("~n",[]); 1616pp_nds(undefined) -> ?pp_debug("None",[]); 1617pp_nds([K]) -> 1618 pp_arg(K#xsi_op.op), ?pp_debug("~n",[]); 1619pp_nds([K|Ks]) -> 1620 pp_arg(K#xsi_op.op), ?pp_debug(", ",[]), 1621 pp_nds(Ks). 1622 1623pp_edges(_G, [], []) -> ok; 1624pp_edges(G, [], [OUT|OUTs]) -> 1625 {_E,V1,V2,Label} = ?GRAPH:edge(G,OUT), 1626 ?pp_debug(" Out edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]), 1627 pp_edges(G, [], OUTs); 1628pp_edges(G, [IN|INs], Outs) -> 1629 {_E,V1,V2,Label} = ?GRAPH:edge(G,IN), 1630 ?pp_debug(" In edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]), 1631 pp_edges(G, INs, Outs). 1632 1633-endif. 1634 1635%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1636%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1637%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1638 1639init_counters() -> 1640 put({ssapre_temp,temp_count}, 0), 1641 put({ssapre_index,index_count}, 0). 1642 1643new_bottom() -> 1644 IndxCountPair = {ssapre_index, index_count}, 1645 V = get(IndxCountPair), 1646 put(IndxCountPair, V+1), 1647 #bottom{key = V, var = ?RTL:mk_new_var()}. 1648 1649new_temp() -> 1650 TmpCountPair = {ssapre_temp, temp_count}, 1651 V = get(TmpCountPair), 1652 put(TmpCountPair, V+1), 1653 #temp{key = V, var = ?RTL:mk_new_var()}. 1654 1655init_redundancy_count() -> 1656 put({ssapre_redundancy,redundancy_count}, 0). 1657 1658redundancy_add() -> 1659 RedCountPair = {ssapre_redundancy, redundancy_count}, 1660 V = get(RedCountPair), 1661 put(RedCountPair, V+1). 1662 1663-ifdef(SSAPRE_DEBUG). 1664get_redundancy_count() -> 1665 get({ssapre_redundancy,redundancy_count}). 1666-endif. 1667