diff options
Diffstat (limited to 'lib/hipe/rtl/hipe_rtl_ssapre.erl')
| -rw-r--r-- | lib/hipe/rtl/hipe_rtl_ssapre.erl | 1679 |
1 files changed, 1679 insertions, 0 deletions
diff --git a/lib/hipe/rtl/hipe_rtl_ssapre.erl b/lib/hipe/rtl/hipe_rtl_ssapre.erl new file mode 100644 index 0000000000..a9e92e5688 --- /dev/null +++ b/lib/hipe/rtl/hipe_rtl_ssapre.erl @@ -0,0 +1,1679 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2005-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% File : hipe_rtl_ssapre.erl +%% Author : He Bingwen and Fr�d�ric Haziza +%% Description : Performs Partial Redundancy Elimination on SSA form. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% @doc +%% +%% This module implements the <a href="http://cs.wheaton.edu/%7Etvandrun/writings/spessapre.pdf">Anticipation-SSAPRE algorithm</a>, +%% with several modifications for Partial Redundancy Elimination on SSA form. +%% We actually found problems in this algorithm, so +%% we implement another version with several advantages: +%% - No loop for Xsi insertions +%% - No fix point iteration for the downsafety part +%% - Less computations for Will Be Available part +%% - Complexity of the overall algorithm is improved +%% +%% We were supposed to publish these results anyway :D +%% +%% @end +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_rtl_ssapre). + +-export([rtl_ssapre/2]). + +-include("../main/hipe.hrl"). +-include("hipe_rtl.hrl"). + +%%-define(SSAPRE_DEBUG, true ). %% When uncommented, produces debug printouts +-define( SETS, ordsets ). %% Which set implementation module to use +-define( CFG, hipe_rtl_cfg ). +-define( RTL, hipe_rtl ). +-define( BB, hipe_bb ). +-define( ARCH, hipe_rtl_arch ). +-define( GRAPH, digraph ). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Debugging stuff +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-ifndef(SSAPRE_DEBUG). +-define(pp_debug(_Str, _Args), ok). +-else. +-define(pp_debug(Str, Args), io:format(standard_io, Str, Args)). +-endif. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Records / Structures +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-record(xsi_link, {num}). %% Number is the index of the temporary (a Key into the Xsi Tree) +-record(temp, {key, var}). +-record(bottom, {key, var}). +-record(xsi, {inst, %% Associated instruction + def, %% Hypothetical temporary variable + %% that stores the result of the computation + label, %% Block Label where the xsi is inserted + opList, %% List of operands + cba, %% + later, %% + wba + }). + +-record(pre_candidate, {alu, def}). +-record(xsi_op, {pred, op}). + +-record(mp, {xsis, maps, preds, defs, uses, ndsSet}). +-record(block, {type, attributes}). + +-record(eop, {expr, var, stopped_by}). +-record(insertion, {code, from}). + +-record(const_expr, {var, value}). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Main function +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +rtl_ssapre(RtlSSACfg, Options) -> + %% io:format("\n################ Original CFG ################\n"), + %% hipe_rtl_cfg:pp(RtlSSACfg), + %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",[hipe_rtl_ssa:check(RtlSSACfg)]), + + {CFG2,XsiGraph,CFGGraph,MPs} = perform_Xsi_insertion(RtlSSACfg,Options), + %%?pp_debug("~n~n################ Xsi CFG ################\n",[]),pp_cfg(CFG2,XsiGraph), + XsiList = ?GRAPH:vertices(XsiGraph), + case XsiList of + [] -> + %% No Xsi + ?option_time(?pp_debug("~n~n################ No Xsi Inserted ################~n",[]),"RTL A-SSAPRE No Xsi inserted (skip Downsafety and Will Be Available)",Options), + ok; + _ -> + ?pp_debug("~n############ Downsafety ##########~n",[]), + ?option_time(perform_downsafety(MPs,CFGGraph,XsiGraph),"RTL A-SSAPRE Downsafety",Options), + ?pp_debug("~n~n################ CFG Graph ################~n",[]),pp_cfggraph(CFGGraph), + ?pp_debug("~n############ Will Be Available ##########~n",[]), + ?option_time(perform_will_be_available(XsiGraph,CFGGraph,Options),"RTL A-SSAPRE WillBeAvailable",Options) + end, + + ?pp_debug("~n############ No more need for the CFG Graph....Deleting...",[]),?GRAPH:delete(CFGGraph), + ?pp_debug("~n~n################ Xsi Graph ################~n",[]),pp_xsigraph(XsiGraph), + + ?pp_debug("~n############ Code Motion ##########~n",[]), + Labels = ?CFG:preorder(CFG2), + + ?pp_debug("~n~n################ Xsi CFG ################~n",[]),pp_cfg(CFG2,XsiGraph), + + init_redundancy_count(), + ?option_time(FinalCFG=perform_code_motion(Labels,CFG2,XsiGraph),"RTL A-SSAPRE Code Motion",Options), + + ?pp_debug("\n############ No more need for the Xsi Graph....Deleting...",[]),?GRAPH:delete(XsiGraph), + + %% io:format("\n################ Final CFG ################\n"), + %% hipe_rtl_cfg:pp(FinalCFG), + %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n", + %% [hipe_rtl_ssa:check(FinalCFG)]), + ?pp_debug("\nSSAPRE : ~w redundancies were found\n",[get_redundancy_count()]), + + FinalCFG. + +%% ########################################################################## +%% ######################## XSI INSERTION ################################### +%% ########################################################################## + +perform_Xsi_insertion(Cfg, Options) -> + init_counters(), %% Init counters for Bottoms and Temps + DigraphOpts = [cyclic, private], + XsiGraph = digraph:new(DigraphOpts), + %% Be carefull, the digraph component is NOT garbage collected, + %% so don't create 20 millions of instances! + %% finds the longest depth + %% Depth-first, preorder traversal over Basic Blocks. + %%Labels = ?CFG:reverse_postorder(Cfg), + Labels = ?CFG:preorder(Cfg), + + ?pp_debug("~n~n############# Finding definitions for computation~n~n",[]), + ?option_time({Cfg2,XsiGraph} = find_definition_for_computations(Labels,Cfg,XsiGraph),"RTL A-SSAPRE Xsi Insertion, searching from instructions",Options), + + %% Active List creation + GeneratorXsiList = lists:sort(?GRAPH:vertices(XsiGraph)), + ?pp_debug("~n~n############# Inserted Xsis ~w",[GeneratorXsiList]), + ?pp_debug("~n~n############# Finding operands~n",[]), + ?option_time({Cfg3,XsiGraph} = find_operands(Cfg2,XsiGraph,GeneratorXsiList,0),"RTL A-SSAPRE Xsi Insertion, finding operands",Options), + + %% Creating the CFGGraph + ?pp_debug("~n~n############# Creating CFG Graph",[]), + ?pp_debug("~n############# Labels = ~w",[Labels]), + CFGGraph = digraph:new(DigraphOpts), + [StartLabel|Others] = Labels, % adding the start label as a leaf + ?pp_debug("~nAdding a vertex for the start label: ~w",[StartLabel]), + ?GRAPH:add_vertex(CFGGraph, StartLabel, #block{type = top}), + % Doing the others + ?option_time(MPs=create_cfggraph(Others,Cfg3,CFGGraph,[],[],[],XsiGraph),"RTL A-SSAPRE Xsi Insertion, creating intermediate 'SSAPRE Graph'",Options), + + %% Return the bloody collected information + {Cfg3,XsiGraph,CFGGraph,MPs}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +find_definition_for_computations([], Cfg, XsiGraph) -> + {Cfg,XsiGraph}; %% No more block to inspect in the depth-first order +find_definition_for_computations([Label|Rest], Cfg, XsiGraph) -> + Code = ?BB:code(?CFG:bb(Cfg,Label)), + {NewCfg,XsiGraph} = find_definition_for_computations_in_block(Label,Code,Cfg,[],XsiGraph), + find_definition_for_computations(Rest, NewCfg, XsiGraph). + +%%=========================================================================== +%% Searches from instruction for one block BlockLabel. +%% We process forward over instructions. + +find_definition_for_computations_in_block(BlockLabel,[],Cfg, + VisitedInstructions,XsiGraph)-> + Code = lists:reverse(VisitedInstructions), + NewBB = ?BB:mk_bb(Code), + NewCfg = ?CFG:bb_add(Cfg,BlockLabel,NewBB), + {NewCfg,XsiGraph}; %% No more instructions to inspect in this block +find_definition_for_computations_in_block(BlockLabel,[Inst|Rest],Cfg, + VisitedInstructions,XsiGraph) -> + %% ?pp_debug(" Inspecting instruction: ",[]),pp_instr(Inst,nil), + case Inst of + #alu{} -> + %% Is Inst interesting for SSAPRE? + %% i.e., is Inst an arithmetic operation which doesn't deal with precoloured? + %% Note that since we parse forward, we have no 'pre_candidate'-type so far. + case check_definition(Inst,VisitedInstructions,BlockLabel,Cfg,XsiGraph) of + {def_found,Def} -> + %% Replacing Inst in Cfg + NewInst = #pre_candidate{alu=Inst,def=Def}, + NewVisited = [NewInst|VisitedInstructions], + %% Recurse forward over instructions, same CFG, same XsiGraph + find_definition_for_computations_in_block(BlockLabel,Rest,Cfg, + NewVisited,XsiGraph); + {merge_point,Xsi} -> + Def = Xsi#xsi.def, + Key = Def#temp.key, + NewInst = #pre_candidate{alu=Inst,def=Def}, + XsiLink = #xsi_link{num=Key}, + + %% Add a vertex to the Xsi Graph + ?GRAPH:add_vertex(XsiGraph,Key,Xsi), + ?pp_debug(" Inserting Xsi: ",[]),pp_xsi(Xsi), + + Label = Xsi#xsi.label, + case BlockLabel =:= Label of + false -> + %% Insert the Xsi in the appropriate block + Code = hipe_bb:code(?CFG:bb(Cfg,Label)), + {BeforeCode,AfterCode} = split_for_xsi(lists:reverse(Code),[]), + NewCode = BeforeCode++[XsiLink|AfterCode], + NewBB = hipe_bb:mk_bb(NewCode), + NewCfg = ?CFG:bb_add(Cfg,Label,NewBB), + NewVisited = [NewInst|VisitedInstructions]; + _-> + {BeforeCode,AfterCode} = split_for_xsi(VisitedInstructions,[]), + TempVisited = BeforeCode++[XsiLink|AfterCode], + TempVisited2 = lists:reverse(TempVisited), + NewVisited = [NewInst|TempVisited2], + NewCfg = Cfg + end, + find_definition_for_computations_in_block(BlockLabel, Rest, NewCfg, + NewVisited, XsiGraph) + end; + _ -> + %%?pp_debug("~n [L~w] Not concerned with: ~w",[BlockLabel,Inst]), + %% If the instruction is not a SSAPRE candidate, we skip it and keep on + %% processing instructions + %% Prepend Inst, so that we have all in reverse order. + %% Easy to parse backwards + find_definition_for_computations_in_block(BlockLabel, Rest, Cfg, + [Inst|VisitedInstructions], XsiGraph) + end. + +%% ############################################################################ +%% We have E as an expression, I has an alu (arithmetic operation), and +%% we inspect backwards the previous instructions to find a definition for E. +%% Since we parse in forward order, we know that the previous SSAPRE +%% instruction will have a definition. + +check_definition(E,[],BlockLabel,Cfg,XsiGraph)-> + %% No more instructions in that block + %% No definition found in that block + %% Search is previous blocks + Preds = ?CFG:pred(Cfg, BlockLabel), + %% ?pp_debug("~n CHECKING DEFINITION ####### Is L~w a merge block? It has ~w preds. So far E=",[BlockLabel,length(Preds)]),pp_expr(E), + case Preds of + [] -> + %% Entry Point + {def_found,bottom}; + [P] -> + %% One predecessor only, we just keep looking for a definition in that block + VisitedInstructions = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))), + check_definition(E,VisitedInstructions,P,Cfg,XsiGraph); + _ -> + Temp = new_temp(), + %% It's a merge point + OpList = [#xsi_op{pred=X} || X<-Preds], + Xsi = #xsi{inst=E,def=Temp,label=BlockLabel,opList=OpList}, + {merge_point,Xsi} + end; +check_definition(E,[CC|Rest],BlockLabel,Cfg,XsiGraph) -> + SRC1 = ?RTL:alu_src1(E), + SRC2 = ?RTL:alu_src2(E), + case CC of + #alu{} -> + exit({?MODULE,should_not_be_an_alu, + {"Why the hell do we still have an alu???",CC}}); + #pre_candidate{} -> + %% C is the previous instruction + C = CC#pre_candidate.alu, + DST = ?RTL:alu_dst(C), + case DST =:= SRC1 orelse DST =:= SRC2 of + false -> + case check_match(E,C) of + true -> %% It's a computation of E! + %% Get the dst of the alu + {def_found,DST}; + _-> + check_definition(E,Rest,BlockLabel,Cfg,XsiGraph) + end; + true -> + %% Get the definition of C, since C is PRE-candidate AND has been processed before + DEF = CC#pre_candidate.def, + case DEF of + bottom -> + %% Def(E)=bottom, STOP + {def_found,bottom}; + _ -> + %% Emend E with this def(C) + %%?pp_debug("Parameters are E=~w, DST=~w, DEF=~w",[E,DST,DEF]), + F = emend(E,DST,DEF), + check_definition(F,Rest,BlockLabel,Cfg,XsiGraph) %% Continue the search + end + end; + #move{} -> + %% It's a move, we emend E, and continue the definition search + DST = ?RTL:move_dst(CC), + F = case SRC1 =:= DST orelse SRC2 =:= DST of + true -> + SRC = ?RTL:move_src(CC), + emend(E,DST,SRC); + _ -> + E + end, + check_definition(F,Rest,BlockLabel,Cfg,XsiGraph); %% Continue the search + #xsi_link{} -> + {_K,Xsi} = ?GRAPH:vertex(XsiGraph,CC#xsi_link.num), + C = Xsi#xsi.inst, + case check_match(C,E) of + true -> %% There is a Xsi already with a computation of E! + %% fetch definition of C, and give it to E + {def_found,Xsi#xsi.def}; + _-> + check_definition(E,Rest,BlockLabel,Cfg,XsiGraph) + end; + #phi{} -> + %% skip them. NOTE: Important to separate this case from the next one + check_definition(E,Rest,BlockLabel,Cfg,XsiGraph); + _ -> + %% Note: the function calls or some other instructions can change the pre-coloured registers + %% which are able to be redefined. This breaks of course the SSA form. + %% If there is a redefinition we can give bottom to the computation, and no xsi will be inserted. + %% (In some sens, the result of the computation is new at that point.) + PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2), + + %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2), + RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), %% That means we cannot reuse the result held in this register... + + case PreColouredTest orelse RegisterTest of + true -> + {def_found,bottom}; + false -> + DC = ?RTL:defines(CC), + case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of + true -> + {def_found,bottom}; + false -> + %% Orthogonal to E, we continue the search + check_definition(E,Rest,BlockLabel,Cfg,XsiGraph) + end + end + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +check_match(E, C) -> + OpE = ?RTL:alu_op(E), + OpC = ?RTL:alu_op(C), + case OpE =:= OpC of + false -> + false; + true -> + Src1E = ?RTL:alu_src1(E), + Src2E = ?RTL:alu_src2(E), + Src1C = ?RTL:alu_src1(C), + Src2C = ?RTL:alu_src2(C), + case Src1E =:= Src1C of + true -> + Src2E =:= Src2C; + false -> + Src1E =:= Src2C andalso Src2E =:= Src1C + end + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +expr_is_const(E) -> + ?RTL:is_imm(?RTL:alu_src1(E)) andalso ?RTL:is_imm(?RTL:alu_src2(E)). +%% is_number(?RTL:alu_src1(E)) andalso is_number(?RTL:alu_src2(E)). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Must be an arithmetic operation, i.e. #alu{} +emend(Expr, S, Var) -> + SRC1 = ?RTL:alu_src1(Expr), + NewExpr = case SRC1 =:= S of + true -> ?RTL:alu_src1_update(Expr,Var); + false -> Expr + end, + SRC2 = ?RTL:alu_src2(NewExpr), + case SRC2 =:= S of + true -> ?RTL:alu_src2_update(NewExpr,Var); + false -> NewExpr + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +split_for_xsi([], Acc) -> + {[], Acc}; % no_xsi_no_phi_found; +split_for_xsi([I|Is] = Code, Acc) -> %% [I|Is] in backward order, Acc in order + case I of + #xsi_link{} -> + {lists:reverse(Code), Acc}; + #phi{} -> + {lists:reverse(Code), Acc}; + _ -> + split_for_xsi(Is, [I|Acc]) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Phase 1.B : Search for operands +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +find_operands(Cfg,XsiGraph,[],_Count) -> + {Cfg,XsiGraph}; +find_operands(Cfg,XsiGraph,ActiveList,Count) -> + {NewCfg,TempActiveList} = find_operands_for_active_list(Cfg,XsiGraph,ActiveList,[]), + NewActiveList = lists:reverse(TempActiveList), + ?pp_debug("~n################ Finding operands (iteration ~w): ~w have been introduced. Now ~w in total~n", + [Count+1, length(NewActiveList), length(?GRAPH:vertices(XsiGraph))]), + find_operands(NewCfg,XsiGraph,NewActiveList,Count+1). + +find_operands_for_active_list(Cfg,_XsiGraph,[],ActiveListAcc) -> + {Cfg,ActiveListAcc}; +find_operands_for_active_list(Cfg,XsiGraph,[K|Ks],ActiveListAcc) -> + {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,K), + ?pp_debug("~n Inspecting operands of : ~n",[]),pp_xsi(Xsi), + Preds = ?CFG:pred(Cfg, Xsi#xsi.label), + {NewCfg,NewActiveListAcc}=determine_operands(Xsi,Preds,Cfg,K,XsiGraph,ActiveListAcc), + {_Key2,Xsi2} = ?GRAPH:vertex(XsiGraph,K), + ?pp_debug("~n ** Final Xsi: ~n",[]),pp_xsi(Xsi2), + ?pp_debug("~n #####################################################~n",[]), + find_operands_for_active_list(NewCfg,XsiGraph,Ks,NewActiveListAcc). + +determine_operands(_Xsi,[],Cfg,_K,_XsiGraph,ActiveAcc) -> + %% All operands have been determined. + %% The CFG is not updated, only the XsiGraph + {Cfg,ActiveAcc}; +determine_operands(Xsi,[P|Ps],Cfg,K,XsiGraph,ActiveAcc) -> + Label = Xsi#xsi.label, + ReverseCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,Label))), + VisitedInstructions = get_visited_instructions(Xsi,ReverseCode), + Res = determine_e_prime(Xsi#xsi.inst,VisitedInstructions,P,XsiGraph), + case Res of + operand_is_bottom -> + NewXsi = xsi_arg_update(Xsi,P,new_bottom()), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); + operand_is_const_expr -> + NewXsi = xsi_arg_update(Xsi,P,new_bottom()), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); + {sharing_operand,Op} -> + NewXsi = xsi_arg_update(Xsi,P,Op), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); + {revised_expression,E_prime} -> + ?pp_debug(" E' is determined : ",[]),pp_expr(E_prime), + ?pp_debug(" and going along the edge L~w~n",[P]), + %% Go along the edge P + RevCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))), + case check_one_operand(E_prime,RevCode,P,Cfg,K,XsiGraph) of + {def_found,Def} -> + NewXsi = xsi_arg_update(Xsi,P,Def), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); + + {expr_found,ChildExpr} -> + NewXsi = xsi_arg_update(Xsi,P,ChildExpr), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); + + {expr_is_const, Op} -> + %% We detected that the expression is of the form: 'N op M' + %% where N and M are constant. + NewXsi = xsi_arg_update(Xsi,P,Op), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc); + + {merge_point,XsiChild} -> + %% Update that Xsi, give its definition as Operand for the + %% search, and go on + XsiChildDef = XsiChild#xsi.def, + NewXsi = xsi_arg_update(Xsi,P,XsiChildDef), + ?GRAPH:add_vertex(XsiGraph,K,NewXsi), + + KeyChild = XsiChildDef#temp.key, + XsiChildLink = #xsi_link{num=KeyChild}, + ?GRAPH:add_vertex(XsiGraph,KeyChild,XsiChild), + + %% Should not be the same block !!!!!!! + RCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,XsiChild#xsi.label))), + {BCode,ACode} = split_code_for_xsi(RCode,[]), + + NewCode = BCode++[XsiChildLink|ACode], + NewBB = hipe_bb:mk_bb(NewCode), + NewCfg = ?CFG:bb_add(Cfg, XsiChild#xsi.label, NewBB), + + ?pp_debug(" -- ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" causes insertion of: ~n",[]),pp_xsi(XsiChild), + ?pp_debug(" -- Adding an edge ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" -> ",[]),pp_arg(XsiChild#xsi.def), + + %% Adding an edge... + %%?GRAPH:add_edge(XsiGraph,K,KeyChild,"family"), + ?GRAPH:add_edge(XsiGraph,K,KeyChild), + determine_operands(NewXsi,Ps,NewCfg,K,XsiGraph,[KeyChild|ActiveAcc]) + end + end. + +determine_e_prime(Expr,VisitedInstructions,Pred,XsiGraph) -> + %% MUST FETCH FROM THE XSI TREE, since Xsis are not updated yet in the CFG + NewExpr = emend_with_phis(Expr,VisitedInstructions,Pred), + emend_with_processed_xsis(NewExpr,VisitedInstructions,Pred,XsiGraph). + +emend_with_phis(EmendedE, [], _) -> + EmendedE; +emend_with_phis(E, [I|Rest], Pred) -> + case I of + #phi{} -> + Dst = ?RTL:phi_dst(I), + UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead? + case lists:member(Dst, UE) of + false -> + emend_with_phis(E, Rest, Pred); + true -> + NewE = emend(E, Dst, ?RTL:phi_arg(I,Pred)), + emend_with_phis(NewE, Rest, Pred) + end; + _ -> + emend_with_phis(E, Rest, Pred) + end. + +emend_with_processed_xsis(EmendedE, [], _, _) -> + {revised_expression,EmendedE}; +emend_with_processed_xsis(E, [I|Rest], Pred, XsiGraph) -> + case I of + #xsi_link{} -> + Key = I#xsi_link.num, + {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key), + Def = Xsi#xsi.def, + UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead? + case lists:member(Def,UE) of + false -> + CE = Xsi#xsi.inst, + case check_match(E,CE) of + true -> %% It's a computation of E! + case xsi_arg(Xsi,Pred) of + undetermined_operand -> + exit({?MODULE,check_operand_sharing,"######## �h Dear, we trusted Kostis !!!!!!!!! #############"}); + XsiOp -> + {sharing_operand,XsiOp} %% They share operands + end; + _-> + emend_with_processed_xsis(E,Rest,Pred,XsiGraph) + end; + true -> + A = xsi_arg(Xsi,Pred), + %% ?pp_debug(" ######### xsi_arg(I:~w,Pred:~w) = ~w~n",[I,Pred,A]), + case A of + #bottom{} -> + operand_is_bottom; + #const_expr{} -> + operand_is_const_expr; + #eop{} -> + NewE = emend(E,Def,A#eop.var), + emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph); + undetermined_operand -> + exit({?MODULE,emend_with_processed_xsis,"######## �h Dear, we trusted Kostis, again !!!!!!!!! #############"}); + XsiOp -> + NewE = emend(E,Def,XsiOp), + emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph) + end + end; + _ -> + emend_with_processed_xsis(E,Rest,Pred,XsiGraph) + end. + +%% get_visited_instructions(Xsi,[]) -> +%% ?pp_debug("~nWe don't find this xsi with def ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" in L~w : ",[Xsi#xsi.label]), +%% exit({?MODULE,no_such_xsi_in_block,"We didn't find that Xsi in the block"}); +get_visited_instructions(Xsi, [I|Is]) -> + case I of + #xsi_link{} -> + XsiDef = Xsi#xsi.def, + Key = XsiDef#temp.key, + case I#xsi_link.num =:= Key of + true -> + Is; + false -> + get_visited_instructions(Xsi, Is) + end; + _ -> + get_visited_instructions(Xsi, Is) + end. + +split_code_for_xsi([], Acc) -> + {[],Acc}; +split_code_for_xsi([I|Is] = Code, Acc) -> + case I of + #xsi_link{} -> + {lists:reverse(Code), Acc}; + #phi{} -> + {lists:reverse(Code), Acc}; + _ -> + split_code_for_xsi(Is, [I|Acc]) + end. + +check_one_operand(E, [], BlockLabel, Cfg, XsiKey, XsiGraph) -> + %% No more instructions in that block + %% No definition found in that block + %% Search is previous blocks + Preds = ?CFG:pred(Cfg, BlockLabel), + case Preds of + [] -> + %% Entry Point + {def_found,new_bottom()}; + [P] -> + %% One predecessor only, we just keep looking for a definition in that block + case expr_is_const(E) of + true -> + ?pp_debug("\n\n############## Wow expr is constant: ~w",[E]), + Var = ?RTL:mk_new_var(), + Value = eval_expr(E), + Op = #const_expr{var = Var, value = Value}, + {expr_is_const, Op}; + false -> + VisitedInstructions = lists:reverse(?BB:code(?CFG:bb(Cfg,P))), + check_one_operand(E, VisitedInstructions, P, Cfg, XsiKey, XsiGraph) + end; + _ -> + %% It's a merge point + case expr_is_const(E) of + true -> + ?pp_debug("\n\n############## Wow expr is constant at merge point: ~w",[E]), + Var = ?RTL:mk_new_var(), + Value = eval_expr(E), + Op = #const_expr{var = Var, value = Value}, + {expr_is_const, Op}; + false -> + Temp = new_temp(), + OpList = [#xsi_op{pred = X} || X <- Preds], + Xsi = #xsi{inst = E, def = Temp, label = BlockLabel, opList = OpList}, + {merge_point, Xsi} + end + end; +check_one_operand(E, [CC|Rest], BlockLabel, Cfg, XsiKey, XsiGraph) -> + SRC1 = ?RTL:alu_src1(E), + SRC2 = ?RTL:alu_src2(E), + %% C is the previous instruction + case CC of + #alu{} -> + exit({?MODULE,should_not_be_an_alu, + {"Why the hell do we still have an alu???",CC}}); + #xsi{} -> + exit({?MODULE,should_not_be_a_xsi, + {"Why the hell do we still have a xsi???",CC}}); + #pre_candidate{} -> + C = CC#pre_candidate.alu, + DST = ?RTL:alu_dst(C), + case DST =:= SRC1 orelse DST =:= SRC2 of + true -> + %% Get the definition of C, since C is PRE-candidate AND has + %% been processed before + DEF = CC#pre_candidate.def, + case DEF of + bottom -> + %% Def(E)=bottom, STOP + %% No update of the XsiGraph + {def_found,new_bottom()}; + _-> + %% Simply emend + F = emend(E,DST,DEF), + ?pp_debug("~nEmendation : E= ",[]),pp_expr(E),?pp_debug(" ==> E'= ",[]),pp_expr(F),?pp_debug("~n",[]), + check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) + end; + false -> + case check_match(C,E) of + true -> %% It's a computation of E! + %% It should give DST and not Def + %% No update of the XsiGraph, cuz we use DST and not Def + %% The operand is therefore gonna be a real variable + {def_found,DST}; + _-> + %% Nothing to do with E + check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) + end + end; + #move{} -> + %% It's a move, we emend E, and continue the definition search + DST = ?RTL:move_dst(CC), + case SRC1 =:= DST orelse SRC2 =:= DST of + true -> + SRC = ?RTL:move_src(CC), + F = emend(E,DST,SRC), + check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); %% Continue the search + _ -> + check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) %% Continue the search + end; + #xsi_link{} -> + Key = CC#xsi_link.num, + %% Is Key a family member of XsiDef ? + {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key), + C = Xsi#xsi.inst, + case check_match(E,C) of + true -> %% There is a Xsi already with a computation of E! + %% fetch definition of C, and give it to E + %% Must update an edge in the XsiGraph, and here, we know it's a Temp + %% Note: this can create a loop (= a cycle of length 1) + ?pp_debug(" -- Found a cycle with match: Adding an edge t~w -> t~w",[XsiKey,Key]), + ?GRAPH:add_edge(XsiGraph,XsiKey,Key), + {def_found,Xsi#xsi.def}; + _ -> + case ?GRAPH:get_path(XsiGraph,Key,XsiKey) of + false -> + %% Is it a loop back to itself??? + case Key =:= XsiKey of + false -> + check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); + _ -> + {expr_found,#eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}} + end; + _ -> + %% Returning the expression instead of looping + %% And in case of no match + ExprOp = #eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}, + {expr_found,ExprOp} + end + end; + #phi{} -> %% skip them + check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); + _ -> + PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2), + + %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2), + RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), + case PreColouredTest orelse RegisterTest of + true -> + {def_found,new_bottom()}; + _-> + DC = ?RTL:defines(CC), + case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of + true -> + {def_found,new_bottom()}; + _ -> + %% Orthogonal to E, we continue the search + check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) + end + end + end. + +eval_expr(E) -> + ?pp_debug("~n Evaluating the result of ~w~n", [E]), + Op1 = ?RTL:alu_src1(E), + Op2 = ?RTL:alu_src2(E), + true = ?RTL:is_imm(Op1), + Val1 = ?RTL:imm_value(Op1), + true = ?RTL:is_imm(Op2), + Val2 = ?RTL:imm_value(Op2), + {Result, _Sign, _Zero, _Overflow, _Carry} = ?ARCH:eval_alu(?RTL:alu_op(E), Val1, Val2), + ?pp_debug("~n Result is then ~w~n", [Result]), + ?RTL:mk_imm(Result). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%% CREATTING CFGGRAPH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +create_cfggraph([],_Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,_XsiGraph) -> + ?pp_debug("~n~n ############# PostProcessing ~n~w~n",[LateEdges]), + post_process(LateEdges,CFGGraph), + ?pp_debug("~n~n ############# Factorizing ~n~w~n",[ToBeFactorizedAcc]), + factorize(ToBeFactorizedAcc,CFGGraph), + MPAcc; +create_cfggraph([Label|Ls],Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph) -> + Preds = ?CFG:pred(Cfg, Label), + case Preds of + [] -> + exit({?MODULE,do_not_call_on_top,{"Why the hell do we call that function on the start label???",Label}}); + [P] -> + Code = ?BB:code(?CFG:bb(Cfg, Label)), + Defs = get_defs_in_non_merge_block(Code, []), + ?pp_debug("~nAdding a vertex for ~w", [Label]), + Succs = ?CFG:succ(Cfg, Label), + case Succs of + [] -> %% Exit point + ?GRAPH:add_vertex(CFGGraph, Label, #block{type = exit}), + NewToBeFactorizedAcc = ToBeFactorizedAcc; + _ -> %% Split point + ?GRAPH:add_vertex(CFGGraph,Label,#block{type=not_mp,attributes={P,Succs}}), + NewToBeFactorizedAcc = [Label|ToBeFactorizedAcc] + end, + ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[P,Label,Defs]), + case ?GRAPH:add_edge(CFGGraph,P,Label,Defs) of + {error,Reason} -> + exit({?MODULE,forget_that_for_christs_sake_bingwen_please,{"Bad edge",Reason}}); + _ -> + ok + end, + create_cfggraph(Ls,Cfg,CFGGraph,NewToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph); + _ -> %% Merge point + Code = ?BB:code(?CFG:bb(Cfg,Label)), + {Defs,Xsis,Maps,Uses} = get_info_in_merge_block(Code,XsiGraph,[],[],gb_trees:empty(),gb_trees:empty()), + Attributes = #mp{preds=Preds,xsis=Xsis,defs=Defs,maps=Maps,uses=Uses}, + MergeBlock = #block{type=mp,attributes=Attributes}, + ?pp_debug("~nAdding a vertex for ~w with Defs= ~w",[Label,Defs]), + ?GRAPH:add_vertex(CFGGraph,Label,MergeBlock), + %% Add edges + NewLateEdges = add_edges_for_mp(Preds,Label,LateEdges), + create_cfggraph(Ls,Cfg,CFGGraph,ToBeFactorizedAcc,[Label|MPAcc],NewLateEdges,XsiGraph) + end. + +get_defs_in_non_merge_block([], Acc) -> + ?SETS:from_list(Acc); +get_defs_in_non_merge_block([Inst|Rest], Acc) -> + case Inst of + #pre_candidate{} -> + Def = Inst#pre_candidate.def, + case Def of + #temp{} -> + %% {temp,Key,_Var} -> + %% get_defs_in_non_merge_block(Rest,[Key|Acc]); + get_defs_in_non_merge_block(Rest, [Def#temp.key|Acc]); + _-> %% Real variables or bottom + get_defs_in_non_merge_block(Rest, Acc) + end; + _ -> + get_defs_in_non_merge_block(Rest, Acc) + end. + +get_info_in_merge_block([],_XsiGraph,Defs,Xsis,Maps,Uses) -> + {?SETS:from_list(Defs),Xsis,Maps,Uses}; %% Xsis are in backward order +get_info_in_merge_block([Inst|Rest],XsiGraph,Defs,Xsis,Maps,Uses) -> + case Inst of + #pre_candidate{} -> + Def = Inst#pre_candidate.def, + case Def of + #temp{} -> + get_info_in_merge_block(Rest,XsiGraph,[Def#temp.key|Defs],Xsis,Maps,Uses); + _ -> + get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses) + end; + #xsi_link{} -> + Key = Inst#xsi_link.num, + {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,Key), + OpList = xsi_oplist(Xsi), + {NewMaps,NewUses} = add_map_and_uses(OpList,Key,Maps,Uses), + get_info_in_merge_block(Rest,XsiGraph,Defs,[Key|Xsis],NewMaps,NewUses); + _ -> + get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses) + end. + +add_edges_for_mp([], _Label, LateEdges) -> + LateEdges; +add_edges_for_mp([P|Ps], Label, LateEdges) -> + add_edges_for_mp(Ps,Label,[{P,Label}|LateEdges]). + +%% Doesn't do anything so far +add_map_and_uses([], _Key, Maps, Uses) -> + {Maps,Uses}; +add_map_and_uses([XsiOp|Ops], Key, Maps, Uses) -> + case XsiOp#xsi_op.op of + #bottom{} -> + Set = case gb_trees:lookup(XsiOp,Maps) of + {value, V} -> + ?SETS:add_element(Key,V); + none -> + ?SETS:from_list([Key]) + end, + NewMaps = gb_trees:enter(XsiOp,Set,Maps), + NewUses = Uses; + #temp{} -> + Set = case gb_trees:lookup(XsiOp,Maps) of + {value, V} -> + ?SETS:add_element(Key,V); + none -> + ?SETS:from_list([Key]) + end, + NewMaps = gb_trees:enter(XsiOp,Set,Maps), + Pred = XsiOp#xsi_op.pred, + OOP = XsiOp#xsi_op.op, + SSet = case gb_trees:lookup(Pred,Uses) of + {value, VV} -> + ?SETS:add_element(OOP#temp.key,VV); + none -> + ?SETS:from_list([OOP#temp.key]) + end, + NewUses = gb_trees:enter(Pred,SSet,Uses); + #eop{} -> + Set = case gb_trees:lookup(XsiOp,Maps) of + {value, V} -> + ?SETS:add_element(Key,V); + none -> + ?SETS:from_list([Key]) + end, + NewMaps = gb_trees:enter(XsiOp,Set,Maps), + Pred = XsiOp#xsi_op.pred, + Op = XsiOp#xsi_op.op, + SSet = case gb_trees:lookup(Pred,Uses) of + {value, VV} -> + ?SETS:add_element(Op#eop.stopped_by,VV); + none -> + ?SETS:from_list([Op#eop.stopped_by]) + end, + NewUses = gb_trees:enter(Pred,SSet,Uses); + _-> + NewMaps = Maps, + NewUses = Uses + end, + add_map_and_uses(Ops, Key, NewMaps, NewUses). + +post_process([], _CFGGraph) -> ok; +post_process([E|Es], CFGGraph) -> + {Pred,Label} = E, + {_PP,Block} = ?GRAPH:vertex(CFGGraph,Label), + Att = Block#block.attributes, + Uses = Att#mp.uses, + SetToAdd = case gb_trees:lookup(Pred,Uses) of + {value, Set} -> + Set; + none -> + ?SETS:new() + end, + %% ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[Pred,Label,SetToAdd]), + ?GRAPH:add_edge(CFGGraph, Pred, Label, SetToAdd), + post_process(Es, CFGGraph). + +factorize([], _CFGGraph) -> ok; +factorize([P|Ps], CFGGraph) -> + [OE|OEs] = ?GRAPH:out_edges(CFGGraph,P), + %% ?pp_debug("~nIn_degrees ~w : ~w",[P,?GRAPH:in_degree(CFGGraph,P)]), + [InEdge] = ?GRAPH:in_edges(CFGGraph,P), + {E,V1,V2,Label} = ?GRAPH:edge(CFGGraph,InEdge), + {_OEE,_OEV1,_OEV2,LOE} = ?GRAPH:edge(CFGGraph,OE), + List = shoot_info_upwards(OEs,LOE,CFGGraph), + NewLabel = ?SETS:union(Label,List), + ?GRAPH:add_edge(CFGGraph,E,V1,V2,NewLabel), + factorize(Ps, CFGGraph). + +shoot_info_upwards([], Acc, _CFGGraph) -> Acc; +shoot_info_upwards([E|Es], Acc, CFGGraph) -> + {_E,_V1,_V2,Set} = ?GRAPH:edge(CFGGraph,E), + NewAcc = ?SETS:intersection(Acc, Set), + case ?SETS:size(NewAcc) of + 0 -> NewAcc; + _ -> shoot_info_upwards(Es,NewAcc,CFGGraph) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DOWNSAFETY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +perform_downsafety([], _G, _XsiG) -> + ok; +perform_downsafety([MP|MPs], G, XG) -> + {V,Block} = ?GRAPH:vertex(G, MP), + NDS = ?SETS:new(), + Att = Block#block.attributes, + Maps = Att#mp.maps, + Defs = Att#mp.defs, + OutEdges = ?GRAPH:out_edges(G, MP), + %% ?pp_debug("~n Inspection Maps : ~w",[Maps]), + NewNDS = parse_keys(gb_trees:keys(Maps),Maps,OutEdges,G,Defs,NDS,XG), + NewAtt = Att#mp{ndsSet = NewNDS}, + ?GRAPH:add_vertex(G, V, Block#block{attributes = NewAtt}), + ?pp_debug("~n Not Downsafe at L~w: ~w", [V, NewNDS]), + %%io:format(standard_io,"~n Not Downsafe at L~w: ~w",[V,NewNDS]), + perform_downsafety(MPs, G, XG). + +parse_keys([], _Maps, _OutEdges, _G, _Defs, NDS, _XsiG) -> + NDS; +parse_keys([M|Ms], Maps, OutEdges, G, Defs, NDS, XsiG) -> + KillerSet = gb_trees:get(M,Maps), + %% ?pp_debug("~n Inspection ~w -> ~w",[M,KillerSet]), + TempSet = ?SETS:intersection(KillerSet,Defs), + NewNDS = case ?SETS:size(TempSet) of + 0 -> getNDS(M,KillerSet,NDS,OutEdges,G,XsiG); + _ -> + %% One Xsi which has M as operand has killed it + %% M is then Downsafe + %% and is not added to the NotDownsafeSet (NDS) + NDS + end, + parse_keys(Ms, Maps, OutEdges, G, Defs, NewNDS, XsiG). + +getNDS(_M, _KillerSet, NDS, [], _G, _XsiG) -> + NDS; +getNDS(M, KillerSet, NDS, [E|Es], G, XsiG) -> + {_EE,_V1,_V2,Label} = ?GRAPH:edge(G, E), + Set = ?SETS:intersection(KillerSet, Label), + %% ?pp_debug("~n ######## Intersection between KillerSet: ~w and Label: ~w",[KillerSet,Label]), + %% ?pp_debug("~n ######## ~w",[Set]), + case ?SETS:size(Set) of + 0 -> + %% M is not downsafe + ?SETS:add_element(M, NDS); + _ -> + %% Try the other edges + getNDS(M, KillerSet, NDS, Es, G, XsiG) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%% WILL BE AVAILABLE %%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +perform_will_be_available(XsiGraph,CFGGraph,Options) -> + Keys = ?GRAPH:vertices(XsiGraph), + ?pp_debug("~n############ Can Be Available ##########~n",[]), + ?option_time(perform_can_be_available(Keys,XsiGraph,CFGGraph),"RTL A-SSAPRE WillBeAvailable - Compute CanBeAvailable",Options), + ?pp_debug("~n############ Later ##########~n",[]), + ?option_time(perform_later(Keys,XsiGraph),"RTL A-SSAPRE WillBeAvailable - Compute Later",Options). + +perform_can_be_available([],_XsiGraph,_CFGGraph) -> ok; +perform_can_be_available([Key|Keys],XsiGraph,CFGGraph) -> + {V,Xsi} = ?GRAPH:vertex(XsiGraph,Key), + case Xsi#xsi.cba of + undefined -> + {_VV,Block} = ?GRAPH:vertex(CFGGraph,Xsi#xsi.label), + Att = Block#block.attributes, + NDS = Att#mp.ndsSet, + OpList = ?SETS:from_list(xsi_oplist(Xsi)), + Set = ?SETS:intersection(NDS,OpList), + case ?SETS:size(Set) of + 0 -> + ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = true}), + perform_can_be_available(Keys, XsiGraph, CFGGraph); + _ -> + LIST = [X || #temp{key=X} <- ?SETS:to_list(Set)], + case LIST of + [] -> + ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = false}), + ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, Key), + propagate_cba(ImmediateParents,XsiGraph,Xsi#xsi.def,CFGGraph); + _ -> + ok + end, + perform_can_be_available(Keys, XsiGraph, CFGGraph) + end; + _ -> %% True or False => recurse + perform_can_be_available(Keys, XsiGraph, CFGGraph) + end. + +propagate_cba([],_XG,_Def,_CFGG) -> ok; +propagate_cba([IPX|IPXs],XsiGraph,XsiDef,CFGGraph) -> + {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX), + {_VV,Block} = ?GRAPH:vertex(CFGGraph,IPXsi#xsi.label), + Att = Block#block.attributes, + NDS = Att#mp.ndsSet, + List = ?SETS:to_list(?SETS:intersection(NDS,?SETS:from_list(xsi_oplist(IPXsi)))), + case IPXsi#xsi.cba of + false -> ok; + _ -> + case lists:keymember(XsiDef, #xsi_op.op, List) of + true -> + ?GRAPH:add_vertex(XsiGraph, V, IPXsi#xsi{cba = false}), + ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, IPX), + propagate_cba(ImmediateParents,XsiGraph,IPXsi#xsi.def,CFGGraph); + _ -> + ok + end + end, + propagate_cba(IPXs,XsiGraph,XsiDef,CFGGraph). + +perform_later([], _XsiGraph) -> ok; +perform_later([Key|Keys], XsiGraph) -> + {V, Xsi} = ?GRAPH:vertex(XsiGraph, Key), + %% ?pp_debug("~n DEBUG : inspecting later of ~w (~w)~n",[Key,Xsi#xsi.later]), + case Xsi#xsi.later of + undefined -> + OpList = xsi_oplist(Xsi), + case parse_ops(OpList,fangpi) of %% It means "fart" in chinese :D + has_temp -> + perform_later(Keys,XsiGraph); + has_real -> + case Xsi#xsi.cba of + true -> + ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true}); + undefined -> + ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true}); + _ -> + ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=false}) + end, + AllParents = digraph_utils:reaching([Key], XsiGraph), + ?pp_debug("~nPropagating to all parents of t~w: ~w",[Key,AllParents]), + propagate_later(AllParents,XsiGraph), + perform_later(Keys,XsiGraph); + _ -> %% Just contains bottoms and/or expressions + ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=true}), + perform_later(Keys,XsiGraph) + end; + _ -> %% True or False => recurse + perform_later(Keys,XsiGraph) + end. + +propagate_later([], _XG) -> ok; +propagate_later([IPX|IPXs], XsiGraph) -> + {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX), + case IPXsi#xsi.later of + false -> + ?pp_debug("~nThrough propagation, later of t~w is already reset",[IPX]), + propagate_later(IPXs,XsiGraph); + _ -> + ?pp_debug("~nThrough propagation, resetting later of t~w",[IPX]), + case IPXsi#xsi.cba of + true -> + ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true}); + undefined -> + ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true}); + _ -> + ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=false}) + end, + propagate_later(IPXs,XsiGraph) + end. + +parse_ops([], Res) -> + Res; +parse_ops([Op|Ops], Res) -> + case Op#xsi_op.op of + #temp{} -> + NewRes = has_temp, + parse_ops(Ops,NewRes); + #bottom{} -> + parse_ops(Ops,Res); + #eop{} -> + parse_ops(Ops,Res); + _ -> + has_real + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CODE MOTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +perform_code_motion([], Cfg, _XsiG) -> + Cfg; +perform_code_motion([L|Labels], Cfg, XsiG) -> + Code=?BB:code(?CFG:bb(Cfg,L)), + ?pp_debug("~n################ Code Motion in L~w~n",[L]), + ?pp_debug("~nCode to move ~n",[]), + pp_instrs(Code,XsiG), + NewCfg = code_motion_in_block(L,Code,Cfg,XsiG,[],gb_trees:empty()), + ?pp_debug("~n################ Code Motion successful in L~w~n",[L]), + perform_code_motion(Labels,NewCfg,XsiG). + +code_motion_in_block(Label,[],Cfg,_XsiG,Visited,InsertionsAcc) -> + InsertionsAlong = gb_trees:keys(InsertionsAcc), + Code = lists:reverse(Visited), + NewBB = ?BB:mk_bb(Code), + Cfg2 = ?CFG:bb_add(Cfg,Label,NewBB), + %% Must come after the bb_add, since redirect will update the Phis too... + Cfg3 = make_insertions(Label,InsertionsAlong,InsertionsAcc,Cfg2), + %% ?pp_debug("~nChecking the Code at L~w:~n~p",[Label,?BB:code(?CFG:bb(Cfg3,Label))]), + Cfg3; +code_motion_in_block(L,[Inst|Insts],Cfg,XsiG,Visited,InsertionsAcc) -> + ?pp_debug("~nInspecting Inst : ~n",[]),pp_instr(Inst,XsiG), + case Inst of + #pre_candidate{} -> + Def = Inst#pre_candidate.def, + Alu = Inst#pre_candidate.alu, + case Def of + bottom -> + InstToAdd = Alu; + #temp{} -> + Key = Def#temp.key, + {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), + case Xsi#xsi.wba of + true -> + %% Turn into a move + Dst = ?RTL:alu_dst(Alu), + Move = ?RTL:mk_move(Dst,Def#temp.var), + pp_instr(Inst#pre_candidate.alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil), + %% Counting redundancies + redundancy_add(), + InstToAdd = Move; + _ -> + InstToAdd = Alu + end; + _ -> %% Def is a real variable + %% Turn into a move + Dst = ?RTL:alu_dst(Alu), + Move = ?RTL:mk_move(Dst,Def), + pp_instr(Alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil), + %% Counting redundancies + redundancy_add(), + InstToAdd = Move + end, + code_motion_in_block(L,Insts,Cfg,XsiG,[InstToAdd|Visited],InsertionsAcc); + #xsi_link{} -> + Key = Inst#xsi_link.num, + {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), + case Xsi#xsi.wba of + true -> + %% Xsi is a WBA, it might trigger insertions + OpList = xsi_oplist(Xsi), + ?pp_debug(" This Xsi is a 'Will be available'",[]), + %% Cleaning the instruction + Expr = prepare_inst(Xsi#xsi.inst), + {NewOpList,NewInsertionsAcc} = get_insertions(OpList,[],InsertionsAcc,Visited,Expr,XsiG), + %% Making Xsi a Phi with Oplist + PhiOpList = [{Pred,Var} || #xsi_op{pred=Pred,op=Var} <- NewOpList], + Def = Xsi#xsi.def, + Phi = ?RTL:phi_arglist_update(?RTL:mk_phi(Def#temp.var),PhiOpList), + ?pp_debug("~n Xsi is turned into Phi : ~w",[Phi]), + code_motion_in_block(L,Insts,Cfg,XsiG,[Phi|Visited],NewInsertionsAcc); + _ -> + ?pp_debug(" This Xsi is not a 'Will be available'",[]), + code_motion_in_block(L,Insts,Cfg,XsiG,Visited,InsertionsAcc) + end; +%% phi -> +%% code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc); + _ -> + %% Other instructions.... Phis too + code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc) + end. + +prepare_inst(Expr) -> + S1 = ?RTL:alu_src1(Expr), + S2 = ?RTL:alu_src2(Expr), + NewInst = case S1 of + #temp{} -> ?RTL:alu_src1_update(Expr,S1#temp.var); + _ -> Expr + end, + case S2 of + #temp{} -> ?RTL:alu_src2_update(NewInst,S2#temp.var); + _ -> NewInst + end. + +get_insertions([],OpAcc,InsertionsAcc,_Visited,_Expr,_XsiG) -> + {OpAcc,InsertionsAcc}; +get_insertions([XsiOp|Ops],OpAcc,InsertionsAcc,Visited,Expr,XsiG) -> + Pred = XsiOp#xsi_op.pred, + Op = XsiOp#xsi_op.op, + case Op of + #bottom{} -> + case gb_trees:lookup(Pred,InsertionsAcc) of + {value,Insertion} -> + From = Insertion#insertion.from, + case lists:keyfind(Op, 1, From) of + false -> + ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), + Dst = Op#bottom.var, + Expr2 = ?RTL:alu_dst_update(Expr,Dst), + Inst = manufacture_computation(Pred,Expr2,Visited), + Code = Insertion#insertion.code, + NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]}, + NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc); + {_, Val} -> + ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op), + Dst = Val, + NewInsertionsAcc = InsertionsAcc + end; + none -> + ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op), + Dst = Op#bottom.var, + Expr2 = ?RTL:alu_dst_update(Expr,Dst), + Inst = manufacture_computation(Pred,Expr2,Visited), + NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]}, + NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc) + end; + #const_expr{} -> + case gb_trees:lookup(Pred,InsertionsAcc) of + {value,Insertion} -> + From = Insertion#insertion.from, + case lists:keyfind(Op, 1, From) of + false -> + ?pp_debug("~nThere have been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), + Dst = Op#const_expr.var, + Val = Op#const_expr.value, + Inst = ?RTL:mk_move(Dst,Val), + Code = Insertion#insertion.code, + NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]}, + NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc); + {_, Val} -> + ?pp_debug("~nThere have been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op), + Dst = Val, + NewInsertionsAcc = InsertionsAcc + end; + none -> + ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op), + Dst = Op#const_expr.var, + Val = Op#const_expr.value, + Inst = ?RTL:mk_move(Dst,Val), + NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]}, + NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc) + end; + #eop{} -> + %% We treat expressions like bottoms + %% The value must be recomputed, and therefore not available... + case gb_trees:lookup(Pred,InsertionsAcc) of + {value,Insertion} -> + From = Insertion#insertion.from, + case lists:keyfind(Op, 1, From) of + false -> + ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), + Dst = Op#eop.var, + Expr2 = ?RTL:alu_dst_update(Expr,Dst), + Inst = manufacture_computation(Pred,Expr2,Visited), + Code = Insertion#insertion.code, + NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]}, + NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc); + {_, Val} -> + ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op), + Dst = Val, + NewInsertionsAcc = InsertionsAcc + end; + none -> + ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op), + Dst = Op#eop.var, + Expr2 = ?RTL:alu_dst_update(Expr,Dst), + Inst = manufacture_computation(Pred,Expr2,Visited), + NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]}, + NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc) + end; + #temp{} -> + case gb_trees:lookup(Pred,InsertionsAcc) of + {value,Insertion} -> + From = Insertion#insertion.from, + case lists:keyfind(Op, 1, From) of + false -> + ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op), + Key = Op#temp.key, + {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), + case Xsi#xsi.wba of + true -> + ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]), + Dst = Op#temp.var, + NewInsertionsAcc = InsertionsAcc; + _ -> + ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]), + Dst = ?RTL:mk_new_var(), + Expr2 = ?RTL:alu_dst_update(Expr,Dst), + Inst = manufacture_computation(Pred,Expr2,Visited), + Code = Insertion#insertion.code, + NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]}, + NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc) + end; + {_, Val} -> + ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too (Op=~w)",[Pred,Op]), + ?pp_debug("~nThis means, this temp is a WBA Xsi's definition",[]), + Dst = Val, + NewInsertionsAcc = InsertionsAcc + end; + none -> + ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course | Op=",[Pred]),pp_arg(Op), + Key = Op#temp.key, + {_V,Xsi} = ?GRAPH:vertex(XsiG,Key), + case Xsi#xsi.wba of + true -> + ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]), + Dst = Op#temp.var, + NewInsertionsAcc = InsertionsAcc; + _ -> + ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]), + Dst = ?RTL:mk_new_var(), + Expr2 = ?RTL:alu_dst_update(Expr,Dst), + Inst = manufacture_computation(Pred,Expr2,Visited), + NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]}, + NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc) + end + end; + _ -> + ?pp_debug("~nThe operand (Op=",[]),pp_arg(Op),?pp_debug(") is a real variable, no need for insertion along L~w",[Pred]), + Dst = Op, + NewInsertionsAcc = InsertionsAcc + end, + NewXsiOp = XsiOp#xsi_op{op=Dst}, + get_insertions(Ops, [NewXsiOp|OpAcc], NewInsertionsAcc, Visited, Expr, XsiG). + +manufacture_computation(_Pred, Expr, []) -> + ?pp_debug("~n Manufactured computation : ~w", [Expr]), + Expr; +manufacture_computation(Pred, Expr, [I|Rest]) -> + %% ?pp_debug("~n Expr = ~w",[Expr]), + SRC1 = ?RTL:alu_src1(Expr), + SRC2 = ?RTL:alu_src2(Expr), + case I of + #xsi_link{} -> + exit({?MODULE,should_not_be_a_xsi_link,{"Why the hell do we still have a xsi link???",I}}); + #xsi{} -> + exit({?MODULE,should_not_be_a_xsi,{"Why the hell do we still have a xsi ???",I}}); + #phi{} -> + DST = ?RTL:phi_dst(I), + Arg = ?RTL:phi_arg(I,Pred), + NewInst = case DST =:= SRC1 of + true -> ?RTL:alu_src1_update(Expr,Arg); + false -> Expr + end, + NewExpr = case DST =:= SRC2 of + true -> ?RTL:alu_src2_update(NewInst,Arg); + false -> NewInst + end, + manufacture_computation(Pred,NewExpr,Rest) + end. + +make_insertions(_L, [], _ITree, Cfg) -> + Cfg; +make_insertions(L, [OldPred|Is], ITree, Cfg) -> + NewPred = ?RTL:label_name(?RTL:mk_new_label()), + I = gb_trees:get(OldPred, ITree), + CodeToInsert = lists:reverse([?RTL:mk_goto(L)|I#insertion.code]), + BBToInsert = ?BB:mk_bb(CodeToInsert), + NewCfg = ?CFG:bb_insert_between(Cfg, NewPred, BBToInsert, OldPred, L), + make_insertions(L, Is, ITree, NewCfg). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%% XSI INTERFACE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +xsi_oplist(#xsi{opList=OpList}) -> + case OpList of undefined -> [] ; _ -> OpList end. +xsi_arg(Xsi, Pred) -> + case lists:keyfind(Pred, #xsi_op.pred, xsi_oplist(Xsi)) of + false -> + undetermined_operand; + R -> + R#xsi_op.op + end. +xsi_arg_update(Xsi, Pred, Op) -> + NewOpList = lists:keyreplace(Pred, #xsi_op.pred, xsi_oplist(Xsi), + #xsi_op{pred=Pred,op=Op}), + Xsi#xsi{opList=NewOpList}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-ifndef(SSAPRE_DEBUG). + +%%pp_cfg(Cfg,_) -> ?CFG:pp(Cfg). +pp_cfg(_,_) -> ok. +pp_instr(_,_) -> ok. +pp_instrs(_,_) -> ok. +pp_expr(_) -> ok. +pp_xsi(_) -> ok. +pp_arg(_) -> ok. +pp_xsigraph(_) -> ok. +pp_cfggraph(_) -> ok. +%% pp_xsigraph(G) -> +%% Vertices = lists:sort(?GRAPH:vertices(G)), +%% io:format(standard_io, "Size of the Xsi Graph: ~w", [length(Vertices)]). +%% pp_cfggraph(G) -> +%% Vertices = lists:sort(?GRAPH:vertices(G)), +%% io:format(standard_io, "Size of the CFG Graph: ~w", [length(Vertices)]). + +-else. + +pp_cfg(Cfg, Graph) -> + Labels = ?CFG:preorder(Cfg), + pp_blocks(Labels, Cfg, Graph). + +pp_blocks([], _, _) -> + ok; +pp_blocks([L|Ls], Cfg, Graph) -> + Code = hipe_bb:code(?CFG:bb(Cfg,L)), + io:format(standard_io,"~n########## Label L~w~n", [L]), + pp_instrs(Code, Graph), + pp_blocks(Ls, Cfg, Graph). + +pp_instrs([], _) -> + ok; +pp_instrs([I|Is], Graph) -> + pp_instr(I, Graph), + pp_instrs(Is, Graph). + +pp_xsi_link(Key, Graph) -> + {_Key,Xsi} = ?GRAPH:vertex(Graph, Key), + pp_xsi(Xsi). + +pp_xsi(Xsi) -> + io:format(standard_io, " [L~w] ", [Xsi#xsi.label]), + io:format(standard_io, "[", []), pp_expr(Xsi#xsi.inst), + io:format(standard_io, "] Xsi(", []), pp_xsi_args(xsi_oplist(Xsi)), + io:format(standard_io, ") (", []), pp_xsi_def(Xsi#xsi.def), + io:format(standard_io, ") cba=~w, later=~w | wba=~w~n", [Xsi#xsi.cba,Xsi#xsi.later,Xsi#xsi.wba]). + +pp_instr(I, Graph) -> + case I of + #alu{} -> + io:format(standard_io, " ", []), + pp_arg(?RTL:alu_dst(I)), + io:format(standard_io, " <- ", []), + pp_expr(I), + io:format(standard_io, "~n", []); + _ -> + try ?RTL:pp_instr(standard_io, I) + catch _:_ -> + case I of + #pre_candidate{} -> + pp_pre(I); + #xsi{} -> + pp_xsi(I); + #xsi_link{} -> + pp_xsi_link(I#xsi_link.num, Graph); + _-> + io:format(standard_io,"*** ~w ***~n", [I]) + end + end + end. + +pp_pre(I) -> + A = I#pre_candidate.alu, + io:format(standard_io, " ", []), + pp_arg(?RTL:alu_dst(A)), + io:format(standard_io, " <- ", []),pp_expr(A), + io:format(standard_io, " [ ", []),pp_arg(I#pre_candidate.def), + %%io:format(standard_io, "~w", [I#pre_candidate.def]), + io:format(standard_io, " ]~n",[]). + +pp_expr(I) -> + pp_arg(?RTL:alu_dst(I)), + io:format(standard_io, " <- ", []), + pp_arg(?RTL:alu_src1(I)), + io:format(standard_io, " ~w ", [?RTL:alu_op(I)]), + pp_arg(?RTL:alu_src2(I)). + +pp_arg(Arg) -> + case Arg of + bottom -> + io:format(standard_io, "_|_", []); + #bottom{} -> + io:format(standard_io, "_|_:~w (", [Arg#bottom.key]),pp_arg(Arg#bottom.var),io:format(standard_io,")",[]); + #temp{} -> + pp_xsi_def(Arg); + #eop{} -> + io:format(standard_io,"#",[]),pp_expr(Arg#eop.expr),io:format(standard_io,"(",[]),pp_arg(Arg#eop.var),io:format(standard_io,")#",[]); + #const_expr{} -> + io:format(standard_io,"*",[]),pp_arg(Arg#const_expr.var),io:format(standard_io," -> ",[]),pp_arg(Arg#const_expr.value),io:format(standard_io,"*",[]); + undefined -> + io:format(standard_io, "...", []); %%"undefined", []); + _-> + case Arg of + #alu{} -> + pp_expr(Arg); + _-> + ?RTL:pp_arg(standard_io, Arg) + end + end. + +pp_args([]) -> + ok; +pp_args(undefined) -> + io:format(standard_io, "...,...,...", []); +pp_args([A]) -> + pp_arg(A); +pp_args([A|As]) -> + pp_arg(A), + io:format(standard_io, ", ", []), + pp_args(As). + +pp_xsi_args([]) -> ok; +pp_xsi_args([XsiOp]) -> + io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]), + pp_arg(XsiOp#xsi_op.op), + io:format(standard_io, "}", []); +pp_xsi_args([XsiOp|Args]) -> + io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]), + pp_arg(XsiOp#xsi_op.op), + io:format(standard_io, "}, ", []), + pp_xsi_args(Args); +pp_xsi_args(Args) -> + pp_args(Args). + +pp_xsi_def(Arg) -> + D = Arg#temp.key, + V = Arg#temp.var, + io:format(standard_io, "t~w (", [D]),pp_arg(V),io:format(standard_io,")",[]). + +pp_cfggraph(G) -> + Vertices = lists:sort(?GRAPH:vertices(G)), + io:format(standard_io, "Size of the CFG Graph: ~w ~n", [length(Vertices)]), + pp_cfgvertex(Vertices, G). + +pp_xsigraph(G) -> + Vertices = lists:sort(?GRAPH:vertices(G)), + io:format(standard_io, "Size of the Xsi Graph: ~w ~n", [length(Vertices)]), + pp_xsivertex(Vertices,G). + +pp_xsivertex([], _G) -> + ok; +pp_xsivertex([Key|Keys], G) -> + {V,Xsi} = ?GRAPH:vertex(G, Key), + OutNeighbours = ?GRAPH:out_neighbours(G, V), + ?pp_debug(" ~w -> ~w", [V,OutNeighbours]), pp_xsi(Xsi), + pp_xsivertex(Keys, G). + +pp_cfgvertex([], _G) -> + ok; +pp_cfgvertex([Key|Keys], G) -> + {V,Block} = ?GRAPH:vertex(G,Key), + case Block#block.type of + mp -> + ?pp_debug("~n Block ~w's attributes: ~n", [V]), + pp_attributes(Block), + ?pp_debug("~n Block ~w's edges: ~n", [V]), + pp_edges(G, ?GRAPH:in_edges(G,Key), ?GRAPH:out_edges(G,Key)); + _-> + ok + end, + pp_cfgvertex(Keys, G). + +pp_attributes(Block) -> + Att = Block#block.attributes, + case Att of + undefined -> + ok; + _ -> + ?pp_debug(" Maps: ~n",[]),pp_maps(gb_trees:keys(Att#mp.maps),Att#mp.maps), + ?pp_debug(" Uses: ~n",[]),pp_uses(gb_trees:keys(Att#mp.uses),Att#mp.uses), + ?pp_debug(" Defs: ~w~n",[Att#mp.defs]), + ?pp_debug(" Xsis: ~w~n",[Att#mp.xsis]), + ?pp_debug(" NDS : ",[]),pp_nds(?SETS:to_list(Att#mp.ndsSet)) + end. + +pp_maps([], _Maps) -> ok; +pp_maps([K|Ks], Maps) -> + ?pp_debug(" ",[]),pp_arg(K#xsi_op.op),?pp_debug("-> ~w~n",[?SETS:to_list(gb_trees:get(K,Maps))]), + pp_maps(Ks, Maps). + +pp_uses([], _Maps) -> ok; +pp_uses([K|Ks], Maps) -> + ?pp_debug(" ~w -> ~w~n",[K,?SETS:to_list(gb_trees:get(K,Maps))]), + pp_uses(Ks, Maps). + +pp_nds([]) -> ?pp_debug("~n",[]); +pp_nds(undefined) -> ?pp_debug("None",[]); +pp_nds([K]) -> + pp_arg(K#xsi_op.op), ?pp_debug("~n",[]); +pp_nds([K|Ks]) -> + pp_arg(K#xsi_op.op), ?pp_debug(", ",[]), + pp_nds(Ks). + +pp_edges(_G, [], []) -> ok; +pp_edges(G, [], [OUT|OUTs]) -> + {_E,V1,V2,Label} = ?GRAPH:edge(G,OUT), + ?pp_debug(" Out edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]), + pp_edges(G, [], OUTs); +pp_edges(G, [IN|INs], Outs) -> + {_E,V1,V2,Label} = ?GRAPH:edge(G,IN), + ?pp_debug(" In edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]), + pp_edges(G, INs, Outs). + +-endif. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +init_counters() -> + put({ssapre_temp,temp_count}, 0), + put({ssapre_index,index_count}, 0). + +new_bottom() -> + IndxCountPair = {ssapre_index, index_count}, + V = get(IndxCountPair), + put(IndxCountPair, V+1), + #bottom{key = V, var = ?RTL:mk_new_var()}. + +new_temp() -> + TmpCountPair = {ssapre_temp, temp_count}, + V = get(TmpCountPair), + put(TmpCountPair, V+1), + #temp{key = V, var = ?RTL:mk_new_var()}. + +init_redundancy_count() -> + put({ssapre_redundancy,redundancy_count}, 0). + +redundancy_add() -> + RedCountPair = {ssapre_redundancy, redundancy_count}, + V = get(RedCountPair), + put(RedCountPair, V+1). + +-ifdef(SSAPRE_DEBUG). +get_redundancy_count() -> + get({ssapre_redundancy,redundancy_count}). +-endif. |