%% -*- erlang-indent-level: 2 -*-
%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2005-2016. All Rights Reserved.
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%% http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions 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.
