aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/ssa/hipe_ssa_const_prop.inc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/ssa/hipe_ssa_const_prop.inc')
-rw-r--r--lib/hipe/ssa/hipe_ssa_const_prop.inc522
1 files changed, 522 insertions, 0 deletions
diff --git a/lib/hipe/ssa/hipe_ssa_const_prop.inc b/lib/hipe/ssa/hipe_ssa_const_prop.inc
new file mode 100644
index 0000000000..2fce384197
--- /dev/null
+++ b/lib/hipe/ssa/hipe_ssa_const_prop.inc
@@ -0,0 +1,522 @@
+%% -*- Erlang -*-
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2004-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_ssa_const_prop.inc
+%% Author : Kostis Sagonas <[email protected]>
+%% Description : Supporting routines for sparse conditional constant
+%% propagation on SSA form.
+%%
+%% Created : 21 June 2004 by Kostis Sagonas <[email protected]>
+%%-----------------------------------------------------------------------------
+
+%%-----------------------------------------------------------------------------
+%% Procedure : propagate/1
+%% Purpose : Perform sparse conditional constant propagation on a
+%% control flow graph
+%% Arguments : CFG - The cfg to work on
+%% Returns : A new cfg.
+%%-----------------------------------------------------------------------------
+
+-spec propagate(#cfg{}) -> #cfg{}.
+
+propagate(CFG) ->
+ Environment = create_env(CFG),
+ StartEdge = {?CFG:start_label(CFG), ?CFG:start_label(CFG)},
+ NewEnvironment = scc([StartEdge], [], Environment),
+ NewCFG = update_cfg(NewEnvironment),
+ NewCFG.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : visit_expressions/2 & visit_expressions/4
+%% Purpose : visit each instruction in a list of instructions.
+%% Arguments : Instructions - the list of instructions to visit
+%% Environment - have a guess.
+%% FlowWork - list of destination part of flowgraph edges
+%% from the visited instructions
+%% SSAWork - resulting ssa-edges from visited instrs.
+%% Returns : {FlowWorkList, SSAWorkList, Environment}
+%%-----------------------------------------------------------------------------
+
+visit_expressions(Instructions, Environment) ->
+ visit_expressions(Instructions, Environment, [], []).
+
+visit_expressions([], Environment, FlowWork, SSAWork) ->
+ {FlowWork, SSAWork, Environment};
+visit_expressions([Inst | Insts], Environment, FlowWork, SSAWork) ->
+ {MoreFlowWork, MoreSSAWork, Environment1}
+ = visit_expression(Inst, Environment),
+ FlowWork1 = MoreFlowWork ++ FlowWork,
+ SSAWork1 = MoreSSAWork ++ SSAWork,
+ visit_expressions(Insts, Environment1, FlowWork1, SSAWork1).
+
+%%-----------------------------------------------------------------------------
+%% The environment record: Shared between incarnations of SCCP.
+%%-----------------------------------------------------------------------------
+
+-record(env, {cfg :: #cfg{},
+ executable_flags = gb_sets:empty() :: gb_set(),
+ handled_blocks = gb_sets:empty() :: gb_set(),
+ lattice_values = gb_trees:empty() :: gb_tree(),
+ ssa_edges = gb_trees:empty() :: gb_tree()
+ }).
+
+create_env(CFG) ->
+ #env{cfg = CFG,
+ executable_flags = gb_sets:empty(),
+ handled_blocks = gb_sets:empty(),
+ lattice_values = initialize_lattice(CFG),
+ ssa_edges = initialize_ssa_edges(CFG)
+ }.
+
+env__cfg(#env{cfg=CFG}) -> CFG.
+env__executable_flags(#env{executable_flags=Flags}) -> Flags.
+env__lattice_values(#env{lattice_values=Values}) -> Values.
+env__ssa_edges(#env{ssa_edges=Edges}) -> Edges.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : initialize_lattice/1
+%% Purpose : Compute the initial value-lattice for the CFG
+%% Arguments : CFG a control flow graph
+%% Returns : a value-latice (gb_tree)
+%%-----------------------------------------------------------------------------
+
+initialize_lattice(CFG) ->
+ Lattice = gb_trees:empty(),
+ Parameters = ?CFG:params(CFG),
+ Inserter = fun(Parameter, Tree) ->
+ gb_trees:insert(Parameter, bottom, Tree)
+ end,
+ lists:foldl(Inserter, Lattice, Parameters).
+
+%%-----------------------------------------------------------------------------
+%% Procedure : initialize_ssa_edges/1
+%% Purpose : Compute the SSA edges in the CFG. SSA edges are used to map
+%% the definition of a value to its uses.
+%% Arguments : CFG - the cfg
+%% Returns : A gb_tree of values (variables & registers) to
+%% lists of {Node, Instruction} pairs.
+%%-----------------------------------------------------------------------------
+
+initialize_ssa_edges(CFG) ->
+ IterateNodes =
+ fun(Node, Tree1) ->
+ IterateInstructions =
+ fun(Instruction, Tree2) ->
+ IterateArguments =
+ fun(Argument, Tree3) ->
+ Data = gb_trees:lookup(Argument, Tree3),
+ NewEdge = {Node, Instruction},
+ case Data of
+ none ->
+ %% insert assumes key is not present
+ gb_trees:insert(Argument, [NewEdge], Tree3);
+ {value, EdgeList} ->
+ %% update assumes key is present
+ gb_trees:update(Argument, [NewEdge|EdgeList], Tree3)
+ end
+ end,
+ Arguments = ?CODE:uses(Instruction),
+ lists:foldl(IterateArguments, Tree2, Arguments)
+ end,
+ Instructions = hipe_bb:code(?CFG:bb(CFG, Node)),
+ lists:foldl(IterateInstructions, Tree1, Instructions)
+ end,
+ NodeList = ?CFG:labels(CFG),
+ lists:foldl(IterateNodes, gb_trees:empty(), NodeList).
+
+%%-----------------------------------------------------------------------------
+%% Procedure : scc/3
+%% Purpose : Do the symbolic execution of a cfg and compute the resulting
+%% value-lattice, and reachability information (Environment).
+%% This is the main loop that does a fixpoint computation of the
+%% lattice-values for each variable and register.
+%% Arguments : FlowWorkList - work list of control-flow edges
+%% SSAWorkList - work list of ssa-edges
+%% Environment - the environment that have been computed so far.
+%% Returns : The environment after execution
+%%-----------------------------------------------------------------------------
+
+scc([], [], Environment) ->
+ Environment;
+%% Take an element from the FlowWorkList and process it
+scc([{Source,Destination} | FlowWorkList], SSAWorkList, Environment) ->
+ case executable({Source, Destination}, Environment) of
+ true ->
+ scc(FlowWorkList, SSAWorkList, Environment);
+ false ->
+ Environment1 = mark_as_executable({Source,Destination}, Environment),
+ Code = extract_code(Destination, Environment),
+ {Environment2, Code1, ExtraSSA} =
+ visit_phi_nodes(Code, Destination, Environment1, []),
+ case handled(Destination, Environment2) of
+ true ->
+ scc(FlowWorkList, ExtraSSA ++ SSAWorkList, Environment2);
+ false ->
+ {MoreFlowDests, MoreSSAWork, Environment3} =
+ visit_expressions(Code1, Environment2),
+ MoreFlowWork = [{Destination, Node} || Node <- MoreFlowDests],
+ FlowWorkList1 = MoreFlowWork ++ FlowWorkList,
+ SSAWorkList1 = ExtraSSA ++ MoreSSAWork ++ SSAWorkList,
+ Environment4 = mark_as_handled(Destination, Environment3),
+ scc(FlowWorkList1, SSAWorkList1, Environment4)
+ end
+ end;
+%% Take an element from the SSAWorkList and process it
+scc([], [{Node, Instruction} | SSAWorkList], Environment) ->
+ case reachable(Node, Environment) of
+ true ->
+ case ?CODE:is_phi(Instruction) of
+ true ->
+ {Environment1, MoreSSA} = visit_phi(Instruction, Node, Environment),
+ scc([], MoreSSA ++ SSAWorkList, Environment1);
+ false ->
+ {MoreFlowDests, MoreSSAWork, Environment1} =
+ visit_expression(Instruction, Environment),
+ SSAWorkList1 = MoreSSAWork ++ SSAWorkList,
+ MoreFlowWork = [{Node, Destination} || Destination<-MoreFlowDests],
+ scc(MoreFlowWork, SSAWorkList1, Environment1)
+ end;
+ false ->
+ scc([], SSAWorkList, Environment)
+ end.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : update_cfg/1
+%% Purpose : Transforms the cfg into something more pleasant.
+%% Here the mapping of variables & registers to lattice-values is
+%% used to actually change the code.
+%% Arguments : Environment - in which everything happens.
+%% Returns : A new CFG.
+%%-----------------------------------------------------------------------------
+
+update_cfg(Environment) ->
+ NodeList = get_nodelist(Environment),
+ CFG1 = update_nodes(NodeList, Environment),
+ %% why not hipe_???_ssa:remove_dead_code ?
+ CFG2 = ?CFG:remove_unreachable_code(CFG1),
+ CFG2.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : update_nodes/2
+%% Purpose : loop over all nodes in a list of nodes, ignoring any
+%% non-reachable node.
+%% Arguments : NodeList - the list of nodes.
+%% Environment - in which everything happens.
+%% Returns : a new cfg.
+%%-----------------------------------------------------------------------------
+
+update_nodes([], Environment) ->
+ env__cfg(Environment);
+update_nodes([Node | NodeList], Environment) ->
+ NewEnvironment =
+ case reachable(Node, Environment) of
+ true ->
+ Instructions = extract_code(Node, Environment),
+ Updater = fun(Instruction) ->
+ update_instruction(Instruction, Environment)
+ end,
+ NewInstructions = lists:flatmap(Updater, Instructions),
+ update_code(Node, NewInstructions, Environment);
+ false ->
+ Environment
+ end,
+ update_nodes(NodeList, NewEnvironment).
+
+%%-----------------------------------------------------------------------------
+%% Procedure : update_code/3
+%% Purpose : Insert a list of new instructions into the cfg in the
+%% environment
+%% Arguments : Node - name of the bb whose instructions we replace.
+%% NewInstructions - The list of new instructions
+%% Env - The environment
+%% Returns : A new environment
+%%-----------------------------------------------------------------------------
+
+update_code(Node, NewInstructions, Environment) ->
+ CFG = env__cfg(Environment),
+ BB = ?CFG:bb(CFG, Node),
+ OrderedInstructions = put_phi_nodes_first(NewInstructions),
+ NewBB = hipe_bb:code_update(BB, OrderedInstructions),
+ NewCFG = ?CFG:bb_add(CFG, Node, NewBB),
+ Environment#env{cfg = NewCFG}.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : put_phi_nodes_first/1
+%% Purpose : Move all phi-instructions to the beginning of the basic block.
+%% Arguments : Instructions - The list of instructions
+%% Returns : A list of instructions where the phi-nodes are first.
+%%-----------------------------------------------------------------------------
+
+put_phi_nodes_first(Instructions) ->
+ {PhiInstructions, OtherInstructions} =
+ partition(fun(X) -> ?CODE:is_phi(X) end, Instructions),
+ PhiInstructions ++ OtherInstructions.
+
+%%-----------------------------------------------------------------------------
+
+partition(Function, List) ->
+ partition(Function, List, [], []).
+
+partition(_Function, [], True, False) ->
+ {lists:reverse(True), lists:reverse(False)};
+
+partition(Function, [Hd | Tail], True, False) ->
+ case Function(Hd) of
+ true ->
+ partition(Function, Tail, [Hd | True], False);
+ false ->
+ partition(Function, Tail, True, [Hd | False])
+ end.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : visit_phi_nodes/4
+%% Purpose : visit all the phi-nodes in a bb and return the list of
+%% remaining instructions, new ssa-edges and a new environment.
+%% Arguments : [Inst|Insts] - The list of instructions in the bb
+%% Node - Name of the current node.
+%% Environment - the environment
+%% SSAWork - the ssawork found so far.
+%% Returns : {Environment, Instruction list, SSAWorkList}
+%%-----------------------------------------------------------------------------
+
+visit_phi_nodes([], CurrentNode, _Environment, _SSAWork) ->
+ ?EXIT({"~w: visit_phi_nodes/4 Basic block contains no code",
+ ?MODULE, CurrentNode});
+visit_phi_nodes(Is = [Inst | Insts], Node, Environment, SSAWork) ->
+ case ?CODE:is_phi(Inst) of
+ true ->
+ {Environment1, NewSSA} = visit_phi(Inst, Node, Environment),
+ visit_phi_nodes(Insts, Node, Environment1, NewSSA ++ SSAWork);
+ false ->
+ {Environment, Is, SSAWork}
+ end.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : visit_phi/3
+%% Purpose : visit a phi-node
+%% Arguments : PhiInstruction- The instruction
+%% CurrentNode - Name of the current node.
+%% Environment - the environment
+%% Returns : {NewEnvironment, SSAWork}
+%%-----------------------------------------------------------------------------
+
+visit_phi(PhiInstruction, CurrentNode, Environment) ->
+ ArgumentList = ?CODE:phi_arglist(PhiInstruction),
+ Value = get_phi_value(ArgumentList, CurrentNode, Environment, top),
+ Name = ?CODE:phi_dst(PhiInstruction),
+ {Environment1, SSAWork} = update_lattice_value({Name, Value}, Environment),
+ {Environment1, SSAWork}.
+
+%%-----------------------------------------------------------------------------
+%% Procedure : get_phi_value/4
+%% Purpose : compute the result of a phi-function, taking care to ignore
+%% edges that are not yet executable.
+%% Arguments : ArgList - the list of arguments {Node, Value pair}
+%% CurrentNode - the current node
+%% Environment - well...
+%% CurrentValue - the meet of the relevant already processed values
+%% Returns : Integer, top or bottom
+%%-----------------------------------------------------------------------------
+
+%% the arglist contains {predecessor, variable} elements. Remember
+%% to be optimistic in this part, hopefully, topvalues will fall down
+%% to become constants. Hence topvalues are more or less ignored here.
+get_phi_value([], _CurrentNode, _Environment, CurrentValue) ->
+ CurrentValue;
+get_phi_value([{PredecessorNode, Variable}| ArgList],
+ CurrentNode,
+ Environment,
+ CurrentValue) ->
+ case executable({PredecessorNode, CurrentNode}, Environment) of
+ true ->
+ NewValue = lookup_lattice_value(Variable, Environment),
+ case NewValue of
+ bottom ->
+ bottom;
+ top ->
+ get_phi_value(ArgList, CurrentNode, Environment, CurrentValue);
+ _ ->
+ case CurrentValue of
+ top ->
+ get_phi_value(ArgList, CurrentNode, Environment, NewValue);
+ _ ->
+ case (NewValue =:= CurrentValue) of
+ true ->
+ get_phi_value(ArgList, CurrentNode, Environment, NewValue);
+ false -> %% two different constants.
+ bottom
+ end
+ end
+ end;
+ false -> %% non-executable transitions don't affect the value.
+ get_phi_value(ArgList, CurrentNode, Environment, CurrentValue)
+ end.
+
+%%------------------------------ environment ----------------------------------
+
+reachable(Node, Environment) ->
+ Predecessors = predecessors(Node, Environment),
+ Executable = fun(Pred) -> executable({Pred, Node}, Environment) end,
+ lists:any(Executable, Predecessors).
+
+%%-----------------------------------------------------------------------------
+
+mark_as_executable(Edge, Environment) ->
+ ExecutableFlags = env__executable_flags(Environment),
+ ExecutableFlags1 = gb_sets:add(Edge, ExecutableFlags),
+ Environment#env{executable_flags = ExecutableFlags1}.
+
+%%-----------------------------------------------------------------------------
+
+mark_as_handled(Node, Environment = #env{handled_blocks=Handled}) ->
+ NewHandled = gb_sets:add_element(Node, Handled),
+ Environment#env{handled_blocks=NewHandled}.
+
+handled(Node, #env{handled_blocks=Handled}) ->
+ gb_sets:is_element(Node, Handled).
+
+%%-----------------------------------------------------------------------------
+
+extract_code(Node, Environment) ->
+ CFG = env__cfg(Environment),
+ case ?CFG:bb(CFG, Node) of
+ not_found -> ?WARNING_MSG("Could not find label ~w.\n", [Node]),
+ [];
+ BB -> hipe_bb:code(BB)
+ end.
+
+%%-----------------------------------------------------------------------------
+
+predecessors(Node, Environment) ->
+ CFG = env__cfg(Environment),
+ ?CFG:pred(CFG, Node).
+
+%%-----------------------------------------------------------------------------
+
+executable(Edge, Environment) ->
+ ExecutableFlags = env__executable_flags(Environment),
+ gb_sets:is_member(Edge, ExecutableFlags).
+
+%%-----------------------------------------------------------------------------
+
+update_lattice_value({[], _NewValue}, Environment) ->
+ {Environment, []};
+update_lattice_value({Names, NewValue}, Environment) when is_list(Names) ->
+ Update =
+ fun(Dst, {Env, SSA}) ->
+ {NewEnv, NewSSA} =
+ update_lattice_value({Dst, NewValue}, Env),
+ {NewEnv, SSA ++ NewSSA}
+ end,
+ lists:foldl(Update, {Environment, []}, Names);
+%% update_lattice_value({Name, {Res, N, Z, C, V} }, _) ->
+%% ?EXIT({"inserting dumt grejs", {Name, {Res, N, Z, C, V} } });
+update_lattice_value({Name, NewValue}, Environment) ->
+ LatticeValues = env__lattice_values(Environment),
+ {LatticeValues1, SSAWork} =
+ case gb_trees:lookup(Name, LatticeValues) of
+ none ->
+ {gb_trees:insert(Name, NewValue, LatticeValues),
+ lookup_ssa_edges(Name, Environment)};
+ {value, NewValue} ->
+ {LatticeValues, []};
+ {value, _} ->
+ {gb_trees:update(Name, NewValue, LatticeValues),
+ lookup_ssa_edges(Name, Environment)}
+ end,
+ {Environment#env{lattice_values = LatticeValues1}, SSAWork}.
+
+%%-----------------------------------------------------------------------------
+
+lookup_ssa_edges(Variable, Environment) ->
+ SSAEdges = env__ssa_edges(Environment),
+ case gb_trees:lookup(Variable, SSAEdges) of
+ {value, X} ->
+ X;
+ _ -> % Unused variable
+ []
+ end.
+
+%%-----------------------------------------------------------------------------
+
+get_nodelist(Environment) ->
+ CFG = env__cfg(Environment),
+ ?CFG:labels(CFG).
+
+%%-----------------------------------------------------------------------------
+
+-ifdef(DEBUG).
+
+%%-----------------------------------------------------------------------------
+%%---------------------------------- DEBUG ------------------------------------
+
+error(Text) ->
+ error(Text, []).
+
+error(Text, Data) ->
+ io:format("Internal compiler error in ~w\n",[?MODULE]),
+ io:format(Text, Data),
+ io:format("\n\n"),
+ halt().
+
+%%-----------------------------------------------------------------------------
+
+print_environment(Environment) ->
+ io:format("============================================================\n"),
+ io:format("Executable flags: "),
+ print_executable_flags(env__executable_flags(Environment)),
+ io:format("Lattice values --->\n"),
+ print_lattice_values(env__lattice_values(Environment)),
+ io:format("SSA edges --->\n"),
+ print_ssa_edges(env__ssa_edges(Environment)),
+ io:format("============================================================\n").
+
+%%-----------------------------------------------------------------------------
+
+print_executable_flags(ExecutableFlags) ->
+ ListOfFlags = gb_sets:to_list(ExecutableFlags),
+ Printer = fun ({Source, Destination}) ->
+ io:format("(~w, ~w), ", [Source, Destination]) end,
+ lists:foreach(Printer, ListOfFlags),
+ io:format("()\n").
+
+%%-----------------------------------------------------------------------------
+
+print_lattice_values(LatticeValues) ->
+ ListOfLatticeValues = gb_trees:to_list(LatticeValues),
+ Printer = fun ({Key, Value}) ->
+ io:format("~w = ~w\n", [Key, Value]) end,
+ lists:foreach(Printer, ListOfLatticeValues).
+
+%%-----------------------------------------------------------------------------
+
+print_ssa_edges(SSAEdges) ->
+ ListOfSSAEdges = gb_trees:to_list(SSAEdges),
+ Printer = fun ({Key, Value}) ->
+ io:format("~w: ~w\n", [Key, Value]) end,
+ lists:foreach(Printer, ListOfSSAEdges).
+
+%%-----------------------------------------------------------------------------
+
+-endif. %% DEBUG
+
+%%-----------------------------------------------------------------------------
+