[m-rev.] for (postcommit) review: Tracing allocated regions
Quan Phan
quan.phan at cs.kuleuven.be
Tue Apr 21 00:55:56 AEST 2009
Hi,
As this change is internal to region-based memory management I'm allowed
to go ahead and commit. But because I haven't done a commit for quite
some it would be nice if someone can take a quick look at the diff.
Thanks and regards,
Quan.
-------------- next part --------------
Estimated hours taken: 25
Branch: main
1) Tracing the 'allocated' status of regions in region points-to analysis.
This piece of information will give us a more precise estimate of which
regions are allocated in procedure calls.
The information has not been exploited yet.
2) Improve the code related to the region points-to analysis: structure, naming,
comments and so on but there is no change in terms of algorithms.
compiler/rbmm.rbmm_goal_infos.m:
compiler/rbmm.live_region_analysis.m:
compiler/rbmm.points_to_info.m:
compiler/rbmm.region_instruction.m:
Conform to the changes.
compiler/rbmm.points_to_graph.m:
Add a field to the data structure of node content so that a node
can be marked allocated. Trace it in unify operator.
Change of terminology: use edge instead of arc; define some new types.
Improve naming (e.g. add prefix rptg_ to exported preds), comments.
Simplify the structure of code.
compiler/rbmm.points_to_analysis.m:
Trace whether regions are allocated into.
Improve various aspects of code (no change to algorithms):
- Remove some functions that just do forwarding.
- Use state variables for clear code at several places.
- Conform to the changes in rbmm.points_to_graph.m.
compiler/rbmm.region_transformation.m:
Conform to the changes.
Provide a specialized transformation to from_ground_term scopes.
-------------- next part --------------
Index: rbmm.add_rbmm_goal_infos.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.add_rbmm_goal_infos.m,v
retrieving revision 1.5
diff -u -r1.5 rbmm.add_rbmm_goal_infos.m
--- rbmm.add_rbmm_goal_infos.m 23 Dec 2008 01:37:40 -0000 1.5
+++ rbmm.add_rbmm_goal_infos.m 20 Apr 2009 11:54:07 -0000
@@ -433,7 +433,7 @@
)
;
Unification = deconstruct(DeconsCellVar, _, _, _, _, _),
- get_node_by_variable(Graph, DeconsCellVar, Node),
+ rptg_get_node_by_variable(Graph, DeconsCellVar, Node),
NodeType = rptg_lookup_node_type(Graph, Node),
( if type_not_stored_in_region(NodeType, ModuleInfo)
then
Index: rbmm.live_region_analysis.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.live_region_analysis.m,v
retrieving revision 1.3
diff -u -r1.3 rbmm.live_region_analysis.m
--- rbmm.live_region_analysis.m 30 Dec 2007 04:20:11 -0000 1.3
+++ rbmm.live_region_analysis.m 20 Apr 2009 11:54:07 -0000
@@ -178,7 +178,7 @@
set.difference(InputR, OutputR, DeadR),
svmap.set(PPId, DeadR, !DeadRTable),
% localR
- Nodes = rptg_get_nodes(Graph),
+ Nodes = rptg_get_nodes_as_list(Graph),
set.difference(
set.difference(set.from_list(Nodes), InputR),
OutputR, LocalR),
@@ -242,7 +242,7 @@
;
% Collect reachable regions at this program point.
set.init(LRSet0),
- set.fold(reach_from_a_variable(Graph, ModuleInfo, ProcInfo),
+ set.fold(rptg_reach_from_a_variable(Graph, ModuleInfo, ProcInfo),
LVSet, LRSet0, LRSet)
).
Index: rbmm.points_to_analysis.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.points_to_analysis.m,v
retrieving revision 1.9
diff -u -r1.9 rbmm.points_to_analysis.m
--- rbmm.points_to_analysis.m 27 Feb 2008 07:23:14 -0000 1.9
+++ rbmm.points_to_analysis.m 20 Apr 2009 11:54:07 -0000
@@ -179,9 +179,10 @@
%-----------------------------------------------------------------------------%
- % For construction and deconstruction unifications, add an edge from the
- % variable on the LHS to each variable on the RHS.
- %
+ % For construction and deconstruction unifications, add an edge from
+ % the node of the variable on the LHS to that of each variable on the RHS.
+ % For construction, also mark the node of lhs variable allocated.
+ %
% For assignment unifications we merge the nodes corresponding to
% the variables on either side.
%
@@ -190,25 +191,32 @@
:- pred intra_analyse_unification(unification::in,
rpta_info::in, rpta_info::out) is det.
- % For construction and deconstruction, add edges from LVar to
- % each of RVars.
-intra_analyse_unification(Unification, !RptaInfo) :-
- ( Unification = construct(LVar, ConsId, RVars, _, _, _, _)
- ; Unification = deconstruct(LVar, ConsId, RVars, _, _, _)
- ),
- list.foldl2(process_cons_and_decons(LVar, ConsId), RVars, 1, _, !RptaInfo).
-intra_analyse_unification(assign(ToVar, FromVar), !RptaInfo) :-
- !.RptaInfo = rpta_info(Graph0, AlphaMapping),
- get_node_by_variable(Graph0, ToVar, ToNode),
- get_node_by_variable(Graph0, FromVar, FromNode),
+intra_analyse_unification(construct(LVar, ConsId, RVars, _, _, _, _),
+ rpta_info(!.Graph, AlphaMapping), rpta_info(!:Graph, AlphaMapping)) :-
+ % Mark allocated.
+ rptg_get_node_by_variable(!.Graph, LVar, LNode),
+ LNodeContent0 = rptg_get_node_content(!.Graph, LNode),
+ LNodeContent0 = rptg_node_content(A, B, C, D, _IsAlloc),
+ LNodeContent = rptg_node_content(A, B, C, D, bool.yes),
+ rptg_set_node_content(LNode, LNodeContent, !Graph),
+
+ % Add edges.
+ list.foldl2(process_cons_and_decons(LVar, ConsId), RVars, 1, _, !Graph).
+
+intra_analyse_unification(deconstruct(LVar, ConsId, RVars, _, _, _),
+ rpta_info(!.Graph, AlphaMapping), rpta_info(!:Graph, AlphaMapping)) :-
+ list.foldl2(process_cons_and_decons(LVar, ConsId), RVars, 1, _, !Graph).
+intra_analyse_unification(assign(ToVar, FromVar),
+ rpta_info(!.Graph, AlphaMapping), rpta_info(!:Graph, AlphaMapping)) :-
+ rptg_get_node_by_variable(!.Graph, ToVar, ToNode),
+ rptg_get_node_by_variable(!.Graph, FromVar, FromNode),
( ToNode = FromNode ->
true
;
- unify_operator(ToNode, FromNode, Graph0, Graph),
- !:RptaInfo = rpta_info(Graph, AlphaMapping),
+ unify_operator(ToNode, FromNode, !Graph),
% After merging the two nodes, apply rule P1 to restore the
% RPTG's invariants.
- apply_rule_1(ToNode, !RptaInfo)
+ rule_1(ToNode, !Graph)
).
intra_analyse_unification(simple_test(_, _), !RptaInfo).
intra_analyse_unification(complicated_unify(_, _, _), _, _) :-
@@ -216,33 +224,32 @@
"complicated_unify in region points-to analysis.").
:- pred process_cons_and_decons(prog_var::in, cons_id::in, prog_var::in,
- int::in, int::out, rpta_info::in, rpta_info::out) is det.
+ int::in, int::out, rpt_graph::in, rpt_graph::out) is det.
-process_cons_and_decons(LVar, ConsId, RVar, !Component, !RptaInfo) :-
- !.RptaInfo = rpta_info(Graph0, AlphaMapping),
- get_node_by_variable(Graph0, LVar, L_Node),
- get_node_by_variable(Graph0, RVar, R_Node),
+process_cons_and_decons(LVar, ConsId, RVar, !Component, !Graph) :-
+ rptg_get_node_by_variable(!.Graph, LVar, LNode),
+ rptg_get_node_by_variable(!.Graph, RVar, RNode),
Sel = [termsel(ConsId, !.Component)],
- EdgeLabel = rptg_arc_content(Sel),
+ EdgeLabel = rptg_edge_content(Sel),
- % Only add the edge if it is not in the graph
+ % Only add the edge if it is not in the graph.
% It is more suitable to the edge_operator's semantics if we check
% this inside the edge_operator. But we also want to know if the edge
% is actually added or not so it is convenient to check the edge's
% existence outside edge_operator. Otherwise we can extend edge_operator
% with one more argument to indicate that.
- ( edge_in_graph(L_Node, EdgeLabel, R_Node, Graph0) ->
+ ( rptg_edge_in_graph(LNode, EdgeLabel, RNode, !.Graph) ->
true
;
- edge_operator(L_Node, R_Node, EdgeLabel, Graph0, Graph1),
- !:RptaInfo = rpta_info(Graph1, AlphaMapping),
+ edge_operator(LNode, RNode, EdgeLabel, !Graph),
% After an edge is added, rules P2 and P3 are applied to ensure
% the invariants of the graph.
- apply_rule_2(L_Node, R_Node, ConsId, !.Component, !RptaInfo),
- !.RptaInfo = rpta_info(Graph2, _),
- get_node_by_variable(Graph2, RVar, RVarNode),
- apply_rule_3(RVarNode, !RptaInfo)
+ rule_2(LNode, RNode, ConsId, !.Component, !Graph),
+
+ % In case the node containing RVar might have changed.
+ rptg_get_node_by_variable(!.Graph, RVar, RVarNode),
+ rule_3(RVarNode, !Graph)
),
!:Component = !.Component + 1.
@@ -340,7 +347,7 @@
%-----------------------------------------------------------------------------%
%
-% Code for interprocedural analysis of goals
+% Code for interprocedural analysis of goals.
%
% Analyse a given goal, with module_info and fixpoint table
@@ -529,54 +536,35 @@
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
%
-% Invariants for RPTGs
-%
-
-%-----------------------------------------------------------------------------%
-%
-% Rule P1
+% Invariants for RPTGs.
%
-:- pred apply_rule_1(rptg_node::in, rpta_info::in, rpta_info::out) is det.
-
-apply_rule_1(Node, !RptaInfo) :-
- some [!Graph] (
- !.RptaInfo = rpta_info(!:Graph, AlphaMapping),
- Content = rptg_node_contents(!.Graph, Node),
- Vars = Content ^ rptg_nc_vars,
- rule_1(Vars, !Graph),
- !:RptaInfo = rpta_info(!.Graph, AlphaMapping)
- ).
-
- % Rule 1:
+ % Rule P1:
% After two nodes are unified, it can happen that the unified node has
% two edges with the same label pointing to 2 different nodes. This rule
- % ensures that it happens the 2 nodes will also be unified.
- %
- % After a node is unified, the node itself was probably removed from
- % the graph so we need to trace "it" by the variables assigned to it.
- % That is why the first argument is the set of variables associated
- % with the unified node.
+ % ensures that if it happens the 2 nodes will also be unified.
%
% The algorithm is as follows.
- % 1. If the node has no or one out-arc we have to do nothing and the
- % predicate quits.
- % 2. The node has > 1 out-arc, take one of them, find in the rest
- % another arc that has a same label, unify the end nodes of the two arcs.
- % Because of this unification of the end nodes, more unifications are
- % probably triggered.
- % 3. Start all over again with the same node and the *updated* graph.
- %
-:- pred rule_1(set(prog_var)::in, rpt_graph::in, rpt_graph::out) is det.
-
-rule_1(Vars, !Graph) :-
- get_node_by_vars(!.Graph, Vars, UnifiedNode),
- EdgeMap = rptg_get_edgemap(!.Graph),
- map.lookup(EdgeMap, UnifiedNode, OutEdgesOfUnifiedNode),
- map.keys(OutEdgesOfUnifiedNode, OutArcsUnifiedNode),
+ % 1. If the node has no or one outedge we have to do nothing and the
+ % predicate quits.
+ % 2. The node has > 1 outedges, take one of them,
+ % find in the rest another edge that has the same label,
+ % unify the end nodes of the two edges.
+ % Because of this unification of the end nodes,
+ % more unifications are probably triggered.
+ % 3. If a unification happens, start all over again with the same node
+ % and the *updated* graph that has one less outedge from the node.
+ %
+:- pred rule_1(rptg_node::in, rpt_graph::in, rpt_graph::out) is det.
+
+rule_1(Node, !Graph) :-
+ % XXX This might not be needed because we have just unified into Node.
+ rptg_get_node_by_node(!.Graph, Node, UnifiedNode),
+
+ OutEdgesOfUnifiedNode = rptg_lookup_list_outedges(!.Graph, UnifiedNode),
(
- OutArcsUnifiedNode = [A | As],
- merge_nodes_reached_by_same_labelled_arcs(A, As, As, !Graph,
+ OutEdgesOfUnifiedNode = [E | Es],
+ merge_nodes_reached_by_same_labelled_edges(E, Es, Es, !Graph,
Happened),
(
Happened = bool.no
@@ -585,89 +573,65 @@
% smaller than that of !.Graph and at some point this predicate
% will end up in the then-branch.
Happened = bool.yes,
- rule_1(Vars, !Graph)
+ rule_1(UnifiedNode, !Graph)
)
;
- OutArcsUnifiedNode = []
+ OutEdgesOfUnifiedNode = []
).
- % This predicate unifies the end nodes of the input arc and of an arc
- % in the list which has the same label as the input arc. When one such
- % an arc found, the predicate will not look further in the list.
- % The unification of nodes, if happends, will be propagated by calling
- % rule_1 predicate mutually recursively.
- %
-:- pred merge_nodes_reached_by_same_labelled_arcs(rptg_arc::in,
- list(rptg_arc)::in, list(rptg_arc)::in, rpt_graph::in, rpt_graph::out,
- bool::out) is det.
-
+ % merge_nodes_reached_by_same_labelled_edges(Edge, EdgeList, Rest,
+ % !Graph, Happened) unifies the end nodes of Edge and of an edge
+ % in EdgeList that has the same label as the input edge.
+ % When one such an edge found,
+ % the predicate will not look further in the list.
+ % The unification of nodes, if happends (Happened = yes),
+ % will be propagated by calling rule_1 predicate mutually recursively.
+ %
% The loop in this predicate is similar to
% for i = ... to N - 1
% for j = i+1 to N ...
% ...
- % this clause is reached at the end of the inner loop. No unification
- % has happened so far therefore the list of arcs (Rest = [A | As])
- % are still safe to use.
%
+:- pred merge_nodes_reached_by_same_labelled_edges(rptg_edge::in,
+ list(rptg_edge)::in, list(rptg_edge)::in, rpt_graph::in, rpt_graph::out,
+ bool::out) is det.
- % reach this clause means that no unification of nodes happened and
- % all the out-arcs have been processed (Rest = []).
+ % This clause is reached when no unification of nodes happened and
+ % all the out-edges have been considered (Rest = []).
%
-merge_nodes_reached_by_same_labelled_arcs(_, [], [], !Graph, bool.no).
+merge_nodes_reached_by_same_labelled_edges(_, [], [], !Graph, bool.no).
- % Some out-arcs still need to be processed
+ % This clause is reached when some out-edges still need to be processed.
%
-merge_nodes_reached_by_same_labelled_arcs(_, [], [A | As], !Graph,
+merge_nodes_reached_by_same_labelled_edges(_, [], [E | Es], !Graph,
Happened) :-
- merge_nodes_reached_by_same_labelled_arcs(A, As, As, !Graph, Happened).
+ merge_nodes_reached_by_same_labelled_edges(E, Es, Es, !Graph, Happened).
-merge_nodes_reached_by_same_labelled_arcs(Arc, [A | As], Rest, !Graph,
+merge_nodes_reached_by_same_labelled_edges(Edge, [Ed | Eds], Rest, !Graph,
Happened) :-
- % For a node, we do not allow two arcs with the same label to another node.
+ % We do not allow two edges with the same label from one node to another.
% So End and E below must be definitely different nodes and we only need
% to compare labels.
- rptg_arc_contents(!.Graph, Arc, _Start, End, ArcContent),
- rptg_arc_contents(!.Graph, A, _S, E, AC),
+ rptg_get_edge_contents(!.Graph, Edge, _Start, End, EdgeContent),
+ rptg_get_edge_contents(!.Graph, Ed, _S, E, EdC),
( if
- ArcContent = AC
+ EdgeContent = EdC
then
% Unify the two end nodes.
unify_operator(End, E, !.Graph, Graph1),
% Apply rule 1 after the above unification.
- Content = rptg_node_contents(Graph1, End),
- rule_1(Content ^ rptg_nc_vars, Graph1, !:Graph),
+ rule_1(End, Graph1, !:Graph),
Happened = bool.yes
else
- % Still not found an arc with the same label, continue the
+ % Still not found an edge with the same label, continue the
% inner loop.
- merge_nodes_reached_by_same_labelled_arcs(Arc, As, Rest, !Graph,
+ merge_nodes_reached_by_same_labelled_edges(Edge, Eds, Rest, !Graph,
Happened)
).
-%-----------------------------------------------------------------------------%
-%
-% Rule P2
-%
-
- % This predicate wraps rule_2 to work with rpta_info type.
- %
-:- pred apply_rule_2(rptg_node::in, rptg_node::in, cons_id::in, int::in,
- rpta_info::in, rpta_info::out) is det.
-
-apply_rule_2(Start, End, ConsId, Component, !RptaInfo) :-
- some [!Graph] (
- !.RptaInfo = rpta_info(!:Graph, AlphaMapping),
- StartContent = rptg_node_contents(!.Graph, Start),
- EndContent = rptg_node_contents(!.Graph, End),
- StartVars = StartContent ^ rptg_nc_vars,
- EndVars = EndContent ^ rptg_nc_vars,
- rule_2(StartVars, EndVars, ConsId, Component, !Graph),
- !:RptaInfo = rpta_info(!.Graph, AlphaMapping)
- ).
-
- % Rule 2:
- % After an edge <N, Label, M) is added to a graph, it may happen
+ % Rule P2:
+ % After an edge (N, Label, M) is added to a graph, it may happen
% that there exists another edge from N with the same label but
% pointing to a node different from M. This rule ensures that if that
% the case the node will be unified with M.
@@ -677,47 +641,38 @@
% the same label to a different node. Because of that the predicate
% need not be recursive.
%
-:- pred rule_2(set(prog_var)::in, set(prog_var)::in, cons_id::in, int::in,
+:- pred rule_2(rptg_node::in, rptg_node::in, cons_id::in, int::in,
rpt_graph::in, rpt_graph::out) is det.
-rule_2(SVars, EVars, ConsId, Component, !Graph) :-
- get_node_by_vars(!.Graph, SVars, N),
- get_node_by_vars(!.Graph, EVars, M),
+rule_2(Node1, Node2, ConsId, Component, !Graph) :-
+ rptg_get_node_by_node(!.Graph, Node1, N),
+ rptg_get_node_by_node(!.Graph, Node2, M),
Sel = [termsel(ConsId, Component)],
- EdgeMap = rptg_get_edgemap(!.Graph),
- map.lookup(EdgeMap, N, OutEdgesN),
- map.keys(OutEdgesN, OutArcsN),
- merge_nodes_reached_by_same_labelled_arc(Sel, M, OutArcsN, !Graph).
-
- % If an A(rc) in OutArcsN has the same label Sel then merge M
- % with the node (MPrime) that the A(rc) points to.
- %
-:- pred merge_nodes_reached_by_same_labelled_arc(selector::in,
- rptg_node::in, list(rptg_arc)::in, rpt_graph::in, rpt_graph::out) is det.
-
-merge_nodes_reached_by_same_labelled_arc(_, _, [], !Graph).
-merge_nodes_reached_by_same_labelled_arc(Sel, M, [A | As], !Graph) :-
- rptg_arc_contents(!.Graph, A, _, MPrime, ArcContent),
+ OutEdgeList = rptg_lookup_list_outedges(!.Graph, N),
+ merge_nodes_reached_by_same_labelled_edge(Sel, M, OutEdgeList, !Graph).
+
+ % If an edge (E) in OutEdgeList has the same label Sel then merge M
+ % with the node (MPrime) that E points to.
+ %
+:- pred merge_nodes_reached_by_same_labelled_edge(selector::in,
+ rptg_node::in, list(rptg_edge)::in, rpt_graph::in, rpt_graph::out) is det.
+
+merge_nodes_reached_by_same_labelled_edge(_, _, [], !Graph).
+merge_nodes_reached_by_same_labelled_edge(Sel, M, [Ed | Eds], !Graph) :-
+ rptg_get_edge_contents(!.Graph, Ed, _, MPrime, EdgeContent),
( if
- ArcContent = rptg_arc_content(Selector),
+ EdgeContent = rptg_edge_content(Selector),
Selector = Sel,
MPrime \= M
then
unify_operator(M, MPrime, !Graph),
- Content = rptg_node_contents(!.Graph, M),
- Vars = rptg_node_content_get_vars(Content),
- rule_1(Vars, !Graph)
+ rule_1(M, !Graph)
else
- % still not found an arc with the same label, continue the loop
- merge_nodes_reached_by_same_labelled_arc(Sel, M, As, !Graph)
+ % Still not found an edge with the same label, continue the loop.
+ merge_nodes_reached_by_same_labelled_edge(Sel, M, Eds, !Graph)
).
-%-----------------------------------------------------------------------------%
-%
-% Rule P3
-%
-
- % Rule 3:
+ % Rule P3:
% This rule is applied after an edge is added TO the Node to enforce
% the invariant that a subterm of the same type as the compounding
% term is stored in the same region as the compounding term. In
@@ -737,14 +692,14 @@
:- pred rule_3(rptg_node::in, rpt_graph::in, rpt_graph::out) is det.
rule_3(Node, !Graph) :-
- NodeMap = rptg_get_nodemap(!.Graph),
+ NodeMap = rptg_get_nodes(!.Graph),
map.keys(NodeMap, Nodes),
(
Nodes = [_N | _NS],
% The graph has some node(s), so check each node to see if it
% satisfies the condition of rule 3 or not, if yes unify it
- % with NY (NY is the node that Node may be merged into.)
- get_node_by_node(!.Graph, Node, NY),
+ % with NY. (NY is the node that Node may be merged into.)
+ rptg_get_node_by_node(!.Graph, Node, NY),
rule_3_2(Nodes, NY, !Graph, Happened),
% This predicate will quit when Happened = no, i.e. no more
@@ -759,13 +714,13 @@
% of !:Graph).
rule_3(Node, !Graph)
;
- % no node in Nodes has been unified with NY, which means that
+ % No node in Nodes has been unified with NY, which means that
% no more nodes need to be unified, so just quit.
Happened = bool.no
)
;
Nodes = [],
- % no node in the graph, impossible
+ % No node in the graph, impossible.
unexpected(this_file, "rule_3: impossible having no node in graph")
).
@@ -785,15 +740,13 @@
( if
rule_3_condition(NZ, NY, !.Graph, NZ1)
then
- unify_operator(NZ, NZ1, !.Graph, Graph1),
+ unify_operator(NZ, NZ1, !Graph),
- % apply rule 1
- Content = rptg_node_contents(Graph1, NZ),
- Vars = rptg_node_content_get_vars(Content),
- rule_1(Vars, Graph1, !:Graph),
+ % Apply rule 1.
+ rule_1(NZ, !Graph),
Happened = bool.yes
else
- % try with the rest, namely NS
+ % Try with the rest, namely NS.
rule_3_2(NZs, NY, !Graph, Happened)
).
@@ -804,23 +757,13 @@
rptg_path(Graph, NZ, NY, _),
rptg_lookup_node_type(Graph, NZ) = NZType,
% A node reachable from NY, with the same type as NZ, the node can
- % be exactly NY
- reachable_and_having_type(Graph, NY, NZType, NZ1),
+ % be exactly NY.
+ rptg_reachable_and_having_type(Graph, NY, NZType, NZ1),
NZ \= NZ1.
- % This predicate is just to wrap the call to rule_3 so that the
- % changed graph is put into rpta_info structure.
- %
-:- pred apply_rule_3(rptg_node::in, rpta_info::in, rpta_info::out) is det.
-
-apply_rule_3(Node, !RptaInfo) :-
- !.RptaInfo = rpta_info(Graph0, AlphaMapping),
- rule_3(Node, Graph0, Graph),
- !:RptaInfo = rpta_info(Graph, AlphaMapping).
-
%-----------------------------------------------------------------------------%
%
-% Rule P4 and alpha mapping
+% Rule P4 and alpha mapping.
%
% Build up the alpha mapping (node -> node) and apply rule P4
@@ -841,8 +784,8 @@
%
alpha_mapping_at_call_site([Xi | Xs], [Yi | Ys], CalleeGraph,
!CallerGraph, !AlphaMap) :-
- get_node_by_variable(CalleeGraph, Xi, N_Xi),
- get_node_by_variable(!.CallerGraph, Yi, N_Yi),
+ rptg_get_node_by_variable(CalleeGraph, Xi, N_Xi),
+ rptg_get_node_by_variable(!.CallerGraph, Yi, N_Yi),
( map.search(!.AlphaMap, N_Xi, N_Y) ->
% alpha(N_Xi) = N_Y, alpha(N_Xi) = N_Yi, N_Y != N_Yi.
%
@@ -851,14 +794,16 @@
unify_operator(N_Y, N_Yi, !CallerGraph),
% Apply rule P1 after some nodes are unified.
- Content = rptg_node_contents(!.CallerGraph, N_Y),
- N_Y_Vars = rptg_node_content_get_vars(Content),
- rule_1(N_Y_Vars, !CallerGraph)
+ rule_1(N_Y, !CallerGraph)
;
true
)
;
- svmap.set(N_Xi, N_Yi, !AlphaMap)
+ svmap.set(N_Xi, N_Yi, !AlphaMap),
+
+ % N_Yi inherits N_Xi's is_allocated.
+ IsAlloc = rptg_lookup_node_is_allocated(CalleeGraph, N_Xi),
+ rptg_set_node_is_allocated(N_Yi, IsAlloc, !CallerGraph)
),
alpha_mapping_at_call_site(Xs, Ys, CalleeGraph, !CallerGraph, !AlphaMap).
@@ -909,99 +854,103 @@
CalleeRptaInfo = rpta_info(CalleeGraph, _),
% Apply rules P5-P8 for each out-edge of CalleeNode.
- EdgeMap = rptg_get_edgemap(CalleeGraph),
- map.lookup(EdgeMap, CalleeNode, CalleeNodeOutEdges),
- map.keys(CalleeNodeOutEdges, CalleeNodeOutArcs),
- apply_rules_arcs(CalleeNodeOutArcs, CallerNode, CallSite,
+ CalleeNodeOutEdges = rptg_lookup_list_outedges(CalleeGraph, CalleeNode),
+ apply_rules_outedges(CalleeNodeOutEdges, CallerNode, CallSite,
CalleeRptaInfo, !CallerRptaInfo).
-:- pred apply_rules_arcs(list(rptg_arc)::in, rptg_node::in,
+:- pred apply_rules_outedges(list(rptg_edge)::in, rptg_node::in,
program_point::in, rpta_info::in, rpta_info::in, rpta_info::out) is det.
-apply_rules_arcs([], _, _, _, !RptaInfoR).
-apply_rules_arcs([Arc | Arcs], CallerNode, CallSite, CalleeRptaInfo,
+apply_rules_outedges([], _, _, _, !RptaInfoR).
+apply_rules_outedges([Edge | Edges], CallerNode, CallSite, CalleeRptaInfo,
!CallerRptaInfo) :-
- rule_5(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
- rule_6(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
- rule_7(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
- rule_8(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
- apply_rules_arcs(Arcs, CallerNode, CallSite, CalleeRptaInfo,
+ rule_5(Edge, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
+ rule_6(Edge, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
+ rule_7(Edge, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
+ rule_8(Edge, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo),
+ apply_rules_outedges(Edges, CallerNode, CallSite, CalleeRptaInfo,
!CallerRptaInfo).
-:- pred rule_5(rptg_arc::in, program_point::in, rpta_info::in,
+:- pred rule_5(rptg_edge::in, program_point::in, rpta_info::in,
rptg_node::in, rpta_info::in, rpta_info::out) is det.
-rule_5(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo) :-
- % Find an out-arc in the caller's graph that has a same label
- % the label of the out-arc in callee's graph
+rule_5(Edge, CallSite, CalleeRptaInfo, CallerNode,
+ rpta_info(!.CallerGraph, CallerAlphaMapping),
+ rpta_info(!:CallerGraph, CallerAlphaMapping)) :-
+ % Find an out-edge in the caller's graph that has a same label
+ % the label of the out-edge in callee's graph.
CalleeRptaInfo = rpta_info(CalleeGraph, _),
- rptg_arc_contents(CalleeGraph, Arc, _CalleeNode, CalleeM, Label),
- !.CallerRptaInfo = rpta_info(CallerGraph0, CallerAlphaMapping0),
- get_node_by_node(CallerGraph0, CallerNode, RealCallerNode),
+ rptg_get_edge_contents(CalleeGraph, Edge, _CalleeNode, CalleeM, Label),
+ %!.CallerRptaInfo = rpta_info(CallerGraph0, CallerAlphaMapping),
+ rptg_get_node_by_node(!.CallerGraph, CallerNode, RealCallerNode),
( if
- find_arc_from_node_with_same_label(RealCallerNode, Label,
- CallerGraph0, CallerMPrime),
- map.search(CallerAlphaMapping0, CallSite, AlphaAtCallSite),
+ rptg_find_edge_from_node_with_same_content(RealCallerNode, Label,
+ !.CallerGraph, CallerMPrime),
+ map.search(CallerAlphaMapping, CallSite, AlphaAtCallSite),
map.search(AlphaAtCallSite, CalleeM, CallerM),
- get_node_by_node(CallerGraph0, CallerM, RealCallerM),
+ rptg_get_node_by_node(!.CallerGraph, CallerM, RealCallerM),
CallerMPrime \= RealCallerM
then
- % When the premises of rule P5 are satisfied, nodes are unified and
+ % When the conditions of rule P5 are satisfied, nodes are unified and
% rule P1 applied to ensure invariants.
- unify_operator(RealCallerM, CallerMPrime,
- CallerGraph0, CallerGraph1),
- CallerRptaInfo1 = rpta_info(CallerGraph1, CallerAlphaMapping0),
- apply_rule_1(RealCallerM, CallerRptaInfo1, !:CallerRptaInfo)
+ unify_operator(RealCallerM, CallerMPrime, !CallerGraph),
+
+ % Apply rule P1 after the unification.
+ rule_1(RealCallerM, !CallerGraph)
else
true
).
-:- pred rule_6(rptg_arc::in, program_point::in, rpta_info::in,
+:- pred rule_6(rptg_edge::in, program_point::in, rpta_info::in,
rptg_node::in, rpta_info::in, rpta_info::out) is det.
-rule_6(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo) :-
- % Find an out-arc in the caller's graph that has a same label
- % the label of the out-arc in callee's graph.
+rule_6(Edge, CallSite, CalleeRptaInfo, CallerNode,
+ rpta_info(!.CallerGraph, !.CallerAlphaMapping),
+ rpta_info(!:CallerGraph, !:CallerAlphaMapping)) :-
+ % Find an out-edge in the caller's graph that has a same label
+ % the label of the out-edge in callee's graph.
CalleeRptaInfo = rpta_info(CalleeGraph, _),
- rptg_arc_contents(CalleeGraph, Arc, _CalleeNode, CalleeM, Label),
- !.CallerRptaInfo = rpta_info(CallerGraph, CallerAlphaMapping0),
- get_node_by_node(CallerGraph, CallerNode, RealCallerNode),
+ rptg_get_edge_contents(CalleeGraph, Edge, _CalleeNode, CalleeM, Label),
+ rptg_get_node_by_node(!.CallerGraph, CallerNode, RealCallerNode),
( if
- find_arc_from_node_with_same_label(RealCallerNode, Label,
- CallerGraph, CallerM)
+ rptg_find_edge_from_node_with_same_content(RealCallerNode, Label,
+ !.CallerGraph, CallerM)
then
% (CallerNode, sel, CallerM) in the graph.
- map.lookup(CallerAlphaMapping0, CallSite, AlphaAtCallSite0),
+ map.lookup(!.CallerAlphaMapping, CallSite, AlphaAtCallSite0),
( if
map.search(AlphaAtCallSite0, CalleeM, _)
then
% alpha(CalleeM) = CallerM so ignore.
true
else
- % Apply rule P6 when its premises are satisfied
+ % Apply rule P6: when its conditions are satisfied
% record alpha(CalleeM) = CallerM.
svmap.set(CalleeM, CallerM, AlphaAtCallSite0, AlphaAtCallSite1),
- svmap.set(CallSite, AlphaAtCallSite1, CallerAlphaMapping0,
- CallerAlphaMapping),
- !:CallerRptaInfo = rpta_info(CallerGraph, CallerAlphaMapping)
+ svmap.set(CallSite, AlphaAtCallSite1, !CallerAlphaMapping),
+
+ % CallerM inherits CalleeM's is_allocated.
+ IsAlloc = rptg_lookup_node_is_allocated(CalleeGraph, CalleeM),
+ rptg_set_node_is_allocated(CallerM, IsAlloc, !CallerGraph)
)
else
true
).
-:- pred rule_7(rptg_arc::in, program_point::in, rpta_info::in,
+:- pred rule_7(rptg_edge::in, program_point::in, rpta_info::in,
rptg_node::in, rpta_info::in, rpta_info::out) is det.
-rule_7(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo) :-
- % Find an out-arc in the caller's graph that has a same label
- % the label of the out-arc in callee's graph.
+rule_7(Edge, CallSite, CalleeRptaInfo, CallerNode,
+ rpta_info(!.CallerGraph, CallerAlphaMapping),
+ rpta_info(!:CallerGraph, CallerAlphaMapping)) :-
+ % Find an out-edge in the caller's graph that has a same label
+ % the label of the out-edge in callee's graph.
CalleeRptaInfo = rpta_info(CalleeGraph, _),
- rptg_arc_contents(CalleeGraph, Arc, _CalleeNode, CalleeM, Label),
- !.CallerRptaInfo = rpta_info(CallerGraph0, CallerAlphaMapping),
- get_node_by_node(CallerGraph0, CallerNode, RealCallerNode),
+ rptg_get_edge_contents(CalleeGraph, Edge, _CalleeNode, CalleeM, Label),
+ rptg_get_node_by_node(!.CallerGraph, CallerNode, RealCallerNode),
( if
- find_arc_from_node_with_same_label(RealCallerNode, Label,
- CallerGraph0, _)
+ rptg_find_edge_from_node_with_same_content(RealCallerNode, Label,
+ !.CallerGraph, _)
then
true
else
@@ -1010,39 +959,38 @@
map.lookup(CallerAlphaMapping, CallSite, AlphaAtCallSite),
map.search(AlphaAtCallSite, CalleeM, CallerM)
then
- % Reach here means all the premises of rule P7 are satisfied,
+ % Reach here means all the conditions of rule P7 are satisfied,
% add (CallerNode, sel, CallerM).
- get_node_by_node(CallerGraph0, CallerM, RealCallerM),
- edge_operator(RealCallerNode, RealCallerM, Label,
- CallerGraph0, CallerGraph1),
+ rptg_get_node_by_node(!.CallerGraph, CallerM, RealCallerM),
+ edge_operator(RealCallerNode, RealCallerM, Label, !CallerGraph),
% Need to apply rule 3.
- rule_3(RealCallerM, CallerGraph1, CallerGraph2),
- !:CallerRptaInfo = rpta_info(CallerGraph2, CallerAlphaMapping)
+ rule_3(RealCallerM, !CallerGraph)
else
true
)
).
-:- pred rule_8(rptg_arc::in, program_point::in, rpta_info::in,
+:- pred rule_8(rptg_edge::in, program_point::in, rpta_info::in,
rptg_node::in, rpta_info::in, rpta_info::out) is det.
-rule_8(Arc, CallSite, CalleeRptaInfo, CallerNode, !CallerRptaInfo) :-
- % Find an out-arc in the caller's graph that has a same label
- % the label of the out-arc in callee's graph
+rule_8(Edge, CallSite, CalleeRptaInfo, CallerNode,
+ rpta_info(!.CallerGraph, !.CallerAlphaMapping),
+ rpta_info(!:CallerGraph, !:CallerAlphaMapping)) :-
+ % Find an out-edge in the caller's graph that has a same label
+ % the label of the out-edge in callee's graph.
CalleeRptaInfo = rpta_info(CalleeGraph, _),
- rptg_arc_contents(CalleeGraph, Arc, _CalleeNode, CalleeM, Label),
- !.CallerRptaInfo = rpta_info(CallerGraph0, CallerAlphaMapping0),
- get_node_by_node(CallerGraph0, CallerNode, RealCallerNode),
+ rptg_get_edge_contents(CalleeGraph, Edge, _CalleeNode, CalleeM, Label),
+ rptg_get_node_by_node(!.CallerGraph, CallerNode, RealCallerNode),
( if
- find_arc_from_node_with_same_label(RealCallerNode, Label,
- CallerGraph0, _)
+ rptg_find_edge_from_node_with_same_content(RealCallerNode, Label,
+ !.CallerGraph, _)
then
true
else
% No edge from CallerNode with the label exists.
( if
- map.lookup(CallerAlphaMapping0, CallSite, AlphaAtCallSite0),
+ map.lookup(!.CallerAlphaMapping, CallSite, AlphaAtCallSite0),
map.search(AlphaAtCallSite0, CalleeM, _)
then
true
@@ -1050,29 +998,26 @@
% rule 8: add node CallerM, alpha(CalleeM) = CallerM,
% edge(CallerNode, sel, CallerM)
%
- CallerNextNodeNumber = rptg_get_next_node_number(CallerGraph0),
- string.append("R", string.int_to_string(CallerNextNodeNumber),
+ CallerNextNodeId = rptg_get_next_node_id(!.CallerGraph),
+ string.append("R", string.int_to_string(CallerNextNodeId),
RegName),
CallerMContent = rptg_node_content(set.init, RegName, set.init,
- rptg_lookup_node_type(CalleeGraph, CalleeM)),
- rptg_set_node(CallerMContent, CallerM,
- CallerGraph0, CallerGraph1),
- edge_operator(RealCallerNode, CallerM, Label,
- CallerGraph1, CallerGraph2),
+ rptg_lookup_node_type(CalleeGraph, CalleeM),
+ rptg_lookup_node_is_allocated(CalleeGraph, CalleeM)),
+ rptg_add_node(CallerMContent, CallerM, !CallerGraph),
+ edge_operator(RealCallerNode, CallerM, Label, !CallerGraph),
- map.lookup(CallerAlphaMapping0, CallSite, AlphaAtCallSite0),
+ map.lookup(!.CallerAlphaMapping, CallSite, AlphaAtCallSite0),
svmap.set(CalleeM, CallerM, AlphaAtCallSite0, AlphaAtCallSite),
- svmap.set(CallSite, AlphaAtCallSite,
- CallerAlphaMapping0, CallerAlphaMapping),
+ svmap.set(CallSite, AlphaAtCallSite, !CallerAlphaMapping),
- rule_3(CallerM, CallerGraph2, CallerGraph),
- !:CallerRptaInfo = rpta_info(CallerGraph, CallerAlphaMapping)
+ rule_3(CallerM, !CallerGraph)
)
).
%-----------------------------------------------------------------------------%
%
-% Fixpoint table used in region points-to analysis
+% Fixpoint table used in region points-to analysis.
%
% The fixpoint table used by the region points-to analysis.
Index: rbmm.points_to_graph.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.points_to_graph.m,v
retrieving revision 1.3
diff -u -r1.3 rbmm.points_to_graph.m
--- rbmm.points_to_graph.m 30 Dec 2007 04:20:11 -0000 1.3
+++ rbmm.points_to_graph.m 20 Apr 2009 11:54:08 -0000
@@ -21,169 +21,130 @@
:- import_module parse_tree.
:- import_module parse_tree.prog_data.
+:- import_module bool.
:- import_module int.
:- import_module list.
:- import_module map.
:- import_module set.
:- import_module string.
+%-----------------------------------------------------------------------------%
+% The region points-to graph.
+%
:- type rpt_graph.
+:- type rptg_nodes == map(rptg_node, rptg_node_content).
+:- type rptg_edges == map(rptg_edge, rptg_edge_info).
+:- type rptg_outedges == map(rptg_node, map(rptg_edge, rptg_node)).
+
+:- func rptg_get_nodes(rpt_graph) = rptg_nodes.
+:- func rptg_get_nodes_as_list(rpt_graph) = list(rptg_node).
+:- func rptg_get_edges(rpt_graph) = rptg_edges.
+:- func rptg_get_outedges(rpt_graph) = rptg_outedges.
-:- func rptg_get_nodemap(rpt_graph) = map(rptg_node, rptg_node_content).
-:- func rptg_get_arcmap(rpt_graph) = map(rptg_arc, rptg_arc_info).
-:- func rptg_get_edgemap(rpt_graph) = map(rptg_node, map(rptg_arc, rptg_node)).
-
-:- pred rptg_set_nodemap(map(rptg_node, rptg_node_content)::in,
- rpt_graph::in, rpt_graph::out) is det.
-:- pred rptg_set_arcmap(map(rptg_arc, rptg_arc_info)::in,
- rpt_graph::in, rpt_graph::out) is det.
-:- pred rptg_set_edgemap(map(rptg_node, map(rptg_arc, rptg_node))::in,
- rpt_graph::in, rpt_graph::out) is det.
-
- % XXX: This function should be unnecessary.
-:- func rptg_get_next_node_number(rpt_graph) = int.
-
-:- type rptg_node
- ---> rptg_node(int).
-
-:- type rptg_node_content
- ---> rptg_node_content(
- % The set of procedure variables assigned to this node.
- rptg_nc_vars :: set(prog_var),
-
- % The region variable that names this node.
- rptg_nc_reg_var_name :: string,
-
- rptg_nc_merged_from :: set(rptg_node),
- rptg_nc_node_type :: mer_type
- ).
-
-:- func rptg_node_content_get_vars(rptg_node_content) = set(prog_var).
-:- func rptg_node_content_get_region_name(rptg_node_content) = string.
-:- func rptg_node_content_get_merged_from(rptg_node_content) = set(rptg_node).
-:- func rptg_node_content_get_node_type(rptg_node_content) = mer_type.
-
-:- pred rptg_node_content_set_vars(set(prog_var)::in,
- rptg_node_content::in, rptg_node_content::out) is det.
-:- pred rptg_node_content_set_region_name(string::in,
- rptg_node_content::in, rptg_node_content::out) is det.
-:- pred rptg_node_content_set_merged_from(set(rptg_node)::in,
- rptg_node_content::in, rptg_node_content::out) is det.
-:- pred rptg_node_content_set_node_type(mer_type::in,
- rptg_node_content::in, rptg_node_content::out) is det.
-
-:- type rptg_arc
- ---> rptg_arc(int).
-
-:- type rptg_arc_content
- ---> rptg_arc_content(
- rptg_ac_label :: selector % the label of an edge
- ).
-
-:- func rptg_arc_content_get_label(rptg_arc_content) = selector.
-:- pred rptg_arc_content_set_label(selector::in,
- rptg_arc_content::in, rptg_arc_content::out) is det.
-
-:- type rptg_arc_info
- ---> rptg_arc_info(
- rptg_ai_from_node :: rptg_node,
- rptg_ai_to_node :: rptg_node,
- rptg_ai_label :: rptg_arc_content
- ).
+:- func rptg_get_next_node_id(rpt_graph) = int.
% rpt_graph_init(Graph) binds Graph to an empty graph containing
- % no nodes and no arcs. (The graph contains a counter of the number
- % of nodes allocated in it, so it is possible for a graph to contain
- % no nodes or arcs and still fail to unify with the binding of Graph from
- % rpt_graph_init.)
+ % no nodes and no edges.
%
:- func rpt_graph_init = rpt_graph.
- % rptg_set_node(NodeInfo, Node, OldGraph, NewGraph) takes OldGraph and
- % NodeInfo which is the information to be stored in a new node, and
- % returns a key "Node" which refers to that node, and the new graph
- % NewGraph containing all of the nodes and arcs in OldGraph as well as
- % the new node. It is possible to have two nodes in the graph with the
- % same information stored in them.
+ % rptg_get_node_content(Graph, Node) takes Graph and Node
+ % and returns the information NodeContent associated with Node.
%
% This operation is O(lgN) for a graph containing N nodes.
%
-:- pred rptg_set_node(rptg_node_content::in, rptg_node::out,
+:- func rptg_get_node_content(rpt_graph, rptg_node) = rptg_node_content.
+
+ % Overwrite the content of a node.
+ %
+:- pred rptg_set_node_content(rptg_node::in, rptg_node_content::in,
rpt_graph::in, rpt_graph::out) is det.
- % rptg_node_contents(Graph, Node, NodeContent) takes Graph and Node
- % and returns the information NodeContent stored in Node.
+ % Overwrite the allocated status of a node.
+ %
+:- pred rptg_set_node_is_allocated(rptg_node::in, bool::in,
+ rpt_graph::in, rpt_graph::out) is det.
+
+ % rptg_add_node(NodeInfo, Node, OldGraph, NewGraph) takes OldGraph and
+ % NodeInfo that is the information to be stored in a new node, and
+ % returns a key "Node" which refers to that node, and the new graph
+ % NewGraph containing all of the nodes and edges in OldGraph as well as
+ % the new node. It is possible to have two nodes in the graph with the
+ % same content.
%
% This operation is O(lgN) for a graph containing N nodes.
%
-:- func rptg_node_contents(rpt_graph, rptg_node) = rptg_node_content.
+:- pred rptg_add_node(rptg_node_content::in, rptg_node::out,
+ rpt_graph::in, rpt_graph::out) is det.
- % rptg_successors(Graph, Node, Nodes) takes a graph Graph and a node Node
- % and returns the set of nodes Nodes that are reachable (directly -
- % not transitively) from Node.
+ % rptg_get_edge_contents(Graph, Edge, Start, End, EdgeInfo) takes
+ % Graph and Edge and returns the start and end nodes and the
+ % content associated with Edge.
+ %
+:- pred rptg_get_edge_contents(rpt_graph::in, rptg_edge::in, rptg_node::out,
+ rptg_node::out, rptg_edge_content::out) is det.
+
+ % rptg_set_edge(Start, End, EdgeContent, Edge, OldGraph, NewGraph)
+ % takes a graph OldGraph and adds an edge from Start to End with
+ % the information EdgeContent, and returns the edge as Edge
+ % and the new graph as NewGraph.
+ % If an identical edge already exists then this operation has no effect.
+ %
+ % This operation is O(lgN+lgM) for a graph with N nodes and M edges.
+ %
+:- pred rptg_set_edge(rptg_node::in, rptg_node::in, rptg_edge_content::in,
+ rptg_edge::out, rpt_graph::in, rpt_graph::out) is det.
+
+ % rptg_successors(Graph, Node) takes a graph Graph and a node Node
+ % and returns the set of nodes Nodes that are *directly* reachable
+ % (not transitively) from Node.
%
% This operation is O(NlgN) for a graph containing N nodes.
%
:- func rptg_successors(rpt_graph, rptg_node) = set(rptg_node).
- % rptg_get_nodes(Graph, Nodes) binds Nodes to the set of nodes in Graph.
- %
-:- func rptg_get_nodes(rpt_graph) = list(rptg_node).
-
- % rptg_set_edge(Start, End, ArcInfo, Arc, OldGraph, NewGraph)
- % takes a graph OldGraph and adds an arc from Start to End with
- % the information ArcInfo stored in it, and returns a key for that arc Arc,
- % and the new graph NewGraph.
- % If an identical arc already exists then this operation has no effect.
- %
- % This operation is O(lgN+lgM) for a graph with N nodes and M arcs.
- %
-:- pred rptg_set_edge(rptg_node::in, rptg_node::in, rptg_arc_content::in,
- rptg_arc::out, rpt_graph::in, rpt_graph::out) is det.
-
- % rptg_arc_contents(Graph, Arc, Start, End, ArcInfo) takes a graph Graph
- % and an arc Arc and returns the start and end nodes and the content
- % stored in that arc.
- %
-:- pred rptg_arc_contents(rpt_graph::in, rptg_arc::in, rptg_node::out,
- rptg_node::out, rptg_arc_content::out) is det.
-
% rptg_path(Graph, Start, End, Path) is true iff there is a path
- % from the node Start to the node End in Graph that goes through
- % the sequence of arcs Arcs.
+ % from the node Start to the node End in Graph.
+ % When succeed it returns the path as Path, a list of edges.
+ %
% The algorithm will return paths containing at most one cycle.
%
-:- pred rptg_path(rpt_graph, rptg_node, rptg_node, list(rptg_arc)).
+:- pred rptg_path(rpt_graph, rptg_node, rptg_node, list(rptg_edge)).
:- mode rptg_path(in, in, in, out) is nondet.
:- mode rptg_path(in, in, out, out) is nondet.
-:- pred reachable_and_having_type(rpt_graph::in, rptg_node::in, mer_type::in,
- rptg_node::out) is semidet.
+ % rptg_reachable_and_having_type(Graph, Start, EType, Node)
+ % finds a node that is reachable from Start and has type EType.
+ % If not found, fails.
+ %
+:- pred rptg_reachable_and_having_type(rpt_graph::in, rptg_node::in,
+ mer_type::in, rptg_node::out) is semidet.
% Get a node given the region name (region variable) assigned to it.
% There is one and only one node with a given region name.
% Therefore the predicate returns the node as soon as it finds.
%
-:- pred get_node_by_region_name(rpt_graph::in, string::in,
+:- pred rptg_get_node_by_region_name(rpt_graph::in, string::in,
rptg_node::out) is det.
% Get a node given a set of Mercury variables assigned to it.
% There is one and only one node corresponding to a set of variables.
% Therefore the predicate returns the node as soon as it finds.
%
-:- pred get_node_by_vars(rpt_graph::in, set(prog_var)::in,
+:- pred rptg_get_node_by_vars(rpt_graph::in, set(prog_var)::in,
rptg_node::out) is det.
% Get a node given a Mercury variable assigned to it.
% There is one and only one node of a variable.
% Therefore the predicate returns the node as soon as it finds.
%
-:- pred get_node_by_variable(rpt_graph::in, prog_var::in,
+:- pred rptg_get_node_by_variable(rpt_graph::in, prog_var::in,
rptg_node::out) is det.
% Get a node given a node that has been merged into the first one.
%
-:- pred get_node_by_node(rpt_graph::in, rptg_node::in, rptg_node::out) is det.
+:- pred rptg_get_node_by_node(rpt_graph::in, rptg_node::in, rptg_node::out)
+ is det.
% Compare two graphs.
%
@@ -192,37 +153,114 @@
% This predicate returns a set of nodes (regions) reachable from a
% variable X.
%
-:- pred reach_from_a_variable(rpt_graph::in, module_info::in, proc_info::in,
- prog_var::in, set(rptg_node)::in, set(rptg_node)::out) is det.
+:- pred rptg_reach_from_a_variable(rpt_graph::in, module_info::in,
+ proc_info::in, prog_var::in, set(rptg_node)::in, set(rptg_node)::out)
+ is det.
+
+ % rptg_find_edge_from_node_with_same_content(N, EdgeContent, Graph, M)
+ % finds in Graph, an edge that has the given EdgeContent.
+ % If found, it returns the node which the edge points to as M.
+ % Fails if no such an edge exists.
+ %
+ % Note: this predicate is used when we do not know the end node. If we
+ % know the start node, the label and the end node, we may want to use
+ % rptg_edge_in_graph instead.
+ %
+:- pred rptg_find_edge_from_node_with_same_content(rptg_node::in,
+ rptg_edge_content::in, rpt_graph::in, rptg_node::out) is semidet.
+
+ % Check if an edge (Start, Label, End) is in the Graph or not.
+ %
+:- pred rptg_edge_in_graph(rptg_node::in, rptg_edge_content::in, rptg_node::in,
+ rpt_graph::in) is semidet.
:- func rptg_lookup_region_name(rpt_graph, rptg_node) = string.
:- func rptg_lookup_node_type(rpt_graph, rptg_node) = mer_type.
+:- func rptg_lookup_node_vars(rpt_graph, rptg_node) = set(prog_var).
+:- func rptg_lookup_node_is_allocated(rpt_graph, rptg_node) = bool.
+
+ % Return the list of edges (edge id's).
+ %
+:- func rptg_lookup_list_outedges(rpt_graph, rptg_node) = list(rptg_edge).
+
+ % Return the list of nodes reached directly from a node.
+ %
+:- func rptg_lookup_list_endnodes(rpt_graph, rptg_node) = list(rptg_node).
+
+ % Return the outedges map.
+ %
+:- func rptg_lookup_map_outedges(rpt_graph, rptg_node) =
+ map(rptg_edge, rptg_node).
% The unify operator.
+ % We merge the second node into the first one.
%
:- pred unify_operator(rptg_node::in, rptg_node::in,
rpt_graph::in, rpt_graph::out) is det.
% The edge operator.
%
-:- pred edge_operator(rptg_node::in, rptg_node::in, rptg_arc_content::in,
+:- pred edge_operator(rptg_node::in, rptg_node::in, rptg_edge_content::in,
rpt_graph::in, rpt_graph::out) is det.
- % This predicate finds, in the graph, an edge which has the given label.
- % If found, it returns the node which the edge points to.
- % Fails if no such an edge exists.
- %
- % Note: this predicate is used when we do not know the end node. If we
- % know the start node, the label and the end node, we may want to use
- % edge_in_graph instead.
- %
-:- pred find_arc_from_node_with_same_label(rptg_node::in,
- rptg_arc_content::in, rpt_graph::in, rptg_node::out) is semidet.
+%-----------------------------------------------------------------------------%
+% A node in region points-to graphs.
+%
+:- type rptg_node
+ ---> rptg_node(int).
- % Check if an edge (Start, Label, End) is in the Graph or not.
- %
-:- pred edge_in_graph(rptg_node::in, rptg_arc_content::in, rptg_node::in,
- rpt_graph::in) is semidet.
+:- type rptg_node_content
+ ---> rptg_node_content(
+ % The set of procedure variables assigned to this node.
+ rptg_nc_vars :: set(prog_var),
+
+ % The region variable that names this node.
+ rptg_nc_reg_var_name :: string,
+
+ rptg_nc_merged_from :: set(rptg_node),
+ rptg_nc_node_type :: mer_type,
+ rptg_nc_is_allocated :: bool
+ ).
+
+:- func rptg_node_content_get_vars(rptg_node_content) = set(prog_var).
+:- func rptg_node_content_get_region_name(rptg_node_content) = string.
+:- func rptg_node_content_get_merged_from(rptg_node_content) = set(rptg_node).
+:- func rptg_node_content_get_node_type(rptg_node_content) = mer_type.
+:- func rptg_node_content_get_is_allocated(rptg_node_content) = bool.
+
+:- pred rptg_node_content_set_vars(set(prog_var)::in,
+ rptg_node_content::in, rptg_node_content::out) is det.
+:- pred rptg_node_content_set_region_name(string::in,
+ rptg_node_content::in, rptg_node_content::out) is det.
+:- pred rptg_node_content_set_merged_from(set(rptg_node)::in,
+ rptg_node_content::in, rptg_node_content::out) is det.
+:- pred rptg_node_content_set_node_type(mer_type::in,
+ rptg_node_content::in, rptg_node_content::out) is det.
+:- pred rptg_node_content_set_is_allocated(bool::in,
+ rptg_node_content::in, rptg_node_content::out) is det.
+
+%-----------------------------------------------------------------------------%
+% An edge in region points-to graphs.
+%
+:- type rptg_edge
+ ---> rptg_edge(int).
+
+:- type rptg_edge_content
+ ---> rptg_edge_content(
+ rptg_ec_label :: selector
+ % The label of an edge.
+ ).
+
+:- func rptg_edge_content_get_label(rptg_edge_content) = selector.
+:- pred rptg_edge_content_set_label(selector::in,
+ rptg_edge_content::in, rptg_edge_content::out) is det.
+
+:- type rptg_edge_info
+ ---> rptg_edge_info(
+ rptg_edge_from_node :: rptg_node,
+ rptg_edge_to_node :: rptg_node,
+ rptg_edge_label :: rptg_edge_content
+ ).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -233,161 +271,180 @@
:- import_module libs.compiler_util.
:- import_module transform_hlds.smm_common.
-:- import_module counter.
:- import_module assoc_list.
+:- import_module counter.
:- import_module pair.
:- import_module solutions.
:- import_module svmap.
:- import_module svset.
:- import_module term.
- % A region points-to graph rpt_graph(Node, Arc) represents a directed
- % graph with information type Node associated with each node, and
- % information of type Arc associated with each arc.
+ % A region points-to graph (rpt_graph) is a directed graph in which
+ % 1. Each node is associated with some pieces of info represented by
+ % rptg_node_content. The set of nodes is presented as a map
+ % from rptg_node, which is the node id, to rptg_node_content.
+ % 2. Each edge is a tuple (start node, label, end node) that is represented
+ % by rtpg_edge_info. The set of edges is presented as a map
+ % from rptg_edge, which is the edge id, to rptg_edge_info.
+ % We refer to label as some information associated with an edge. We
+ % represent it by rptg_edge_content.
+ %
+ % Two above maps (for sets of nodes and edges) store enough *information*
+ % about an rpt graph. But in terms of *accessibility* it is unconvenient.
+ % We often access an rpt graph from a node, and then follow
+ % the node's outedges to other nodes, then from those nodes through their
+ % outedges to other nodes, and so on. To facilitate this, we maintain
+ % (redundantly) the outedges of a node. This is represented by
+ % a map from rptg_node to all of the node's outedges, which are represented
+ % by a map from rptg_edge to rptg_node (end node).
%
:- type rpt_graph
---> rpt_graph(
% The source of node ids.
rptg_node_supply :: counter,
- % The source of arc ids.
- rptg_arc_supply :: counter,
+ % The source of edge ids.
+ rptg_edge_supply :: counter,
- rptg_nodemap :: map(rptg_node, rptg_node_content),
- rptg_arcmap :: map(rptg_arc, rptg_arc_info),
- rptg_edgemap :: map(rptg_node,
- map(rptg_arc, rptg_node))
+ rptg_nodes :: rptg_nodes,
+ rptg_edges :: rptg_edges,
+ rptg_outedges :: rptg_outedges
).
rpt_graph_init = Graph :-
counter.init(1, NodeSupply),
- counter.init(1, ArcSupply),
- Graph = rpt_graph(NodeSupply, ArcSupply, Nodes, Arcs, Edges),
+ counter.init(1, EdgeSupply),
map.init(Nodes),
- map.init(Arcs),
- map.init(Edges).
+ map.init(Edges),
+ map.init(OutEdges),
+ Graph = rpt_graph(NodeSupply, EdgeSupply, Nodes, Edges, OutEdges).
:- func rptg_get_node_supply(rpt_graph) = counter.
-:- func rptg_get_arc_supply(rpt_graph) = counter.
-
-:- pred rptg_set_node_supply(counter::in,
- rpt_graph::in, rpt_graph::out)is det.
-:- pred rptg_set_arc_supply(counter::in,
- rpt_graph::in, rpt_graph::out) is det.
rptg_get_node_supply(G) = G ^ rptg_node_supply.
-rptg_get_arc_supply(G) = G ^ rptg_arc_supply.
-rptg_get_nodemap(G) = G ^ rptg_nodemap.
-rptg_get_arcmap(G) = G ^ rptg_arcmap.
-rptg_get_edgemap(G) = G ^ rptg_edgemap.
+
+:- pred rptg_set_node_supply(counter::in, rpt_graph::in, rpt_graph::out)is det.
rptg_set_node_supply(NS, !G) :-
- !:G = !.G ^ rptg_node_supply := NS.
-rptg_set_arc_supply(AS, !G) :-
- !:G = !.G ^ rptg_arc_supply := AS.
-rptg_set_nodemap(N, !G) :-
- !:G = !.G ^ rptg_nodemap := N.
-rptg_set_arcmap(A, !G) :-
- !:G = !.G ^ rptg_arcmap := A.
-rptg_set_edgemap(E, !G) :-
- !:G = !.G ^ rptg_edgemap := E.
+ !G ^ rptg_node_supply := NS.
-rptg_node_content_get_vars(NC) = NC ^ rptg_nc_vars.
-rptg_node_content_get_region_name(NC) = NC ^ rptg_nc_reg_var_name.
-rptg_node_content_get_merged_from(NC) = NC ^ rptg_nc_merged_from.
-rptg_node_content_get_node_type(NC) = NC ^ rptg_nc_node_type.
+:- func rptg_get_edge_supply(rpt_graph) = counter.
-rptg_get_next_node_number(G) = NextNodeNumber :-
+rptg_get_edge_supply(G) = G ^ rptg_edge_supply.
+
+:- pred rptg_set_edge_supply(counter::in,
+ rpt_graph::in, rpt_graph::out) is det.
+
+rptg_set_edge_supply(ES, !G) :-
+ !G ^ rptg_edge_supply := ES.
+
+rptg_get_nodes(G) = G ^ rptg_nodes.
+rptg_get_edges(G) = G ^ rptg_edges.
+rptg_get_outedges(G) = G ^ rptg_outedges.
+
+rptg_get_next_node_id(G) = NextNodeId :-
NodeSupply = rptg_get_node_supply(G),
- counter.allocate(NextNodeNumber, NodeSupply, _).
+ counter.allocate(NextNodeId, NodeSupply, _).
+
+:- pred rptg_set_nodes(rptg_nodes::in, rpt_graph::in, rpt_graph::out) is det.
+
+rptg_set_nodes(Nodes, !G) :-
+ !G ^ rptg_nodes := Nodes.
+
+:- pred rptg_set_edges(rptg_edges::in, rpt_graph::in, rpt_graph::out) is det.
- % After adding a node with Content into the graph, we need to update the
- % Content so that the merged_from set of the node contains itself.
+rptg_set_edges(Edges, !G) :-
+ !G ^ rptg_edges := Edges.
+
+:- pred rptg_set_outedges(rptg_outedges::in, rpt_graph::in, rpt_graph::out)
+ is det.
+
+rptg_set_outedges(OutEdges, !G) :-
+ !G ^ rptg_outedges := OutEdges.
+
+ % After adding a node, we need to update Content0 so that the merged_from
+ % set of the node contains itself.
% Doing it this way is not completely satisfied because we are adding a
% node with the given content but we change the content after all.
% But without adding the node first, the node is nonexistant and we
- % cannot make add it to the merged_from set.
+ % cannot add it to the merged_from set.
%
-rptg_set_node(Content0, rptg_node(N), !G) :-
+rptg_add_node(Content0, rptg_node(NodeId), !G) :-
NS0 = rptg_get_node_supply(!.G),
- counter.allocate(N, NS0, NS),
+ counter.allocate(NodeId, NS0, NS),
rptg_set_node_supply(NS, !G),
+ Node = rptg_node(NodeId),
+
+ % Make the merged_from set contain this node.
+ MergedFrom = set.make_singleton_set(Node),
+ rptg_node_content_set_merged_from(MergedFrom, Content0, Content),
+
+ % Add the node.
+ NodeMap0 = !.G ^ rptg_nodes,
+ svmap.set(Node, Content, NodeMap0, NodeMap),
+ rptg_set_nodes(NodeMap, !G),
+
+ % We can assume there is no outedge for this node yet.
+ OutEdges0 = rptg_get_outedges(!.G),
+ svmap.set(Node, map.init, OutEdges0, OutEdges),
+ rptg_set_outedges(OutEdges, !G).
- % make the merged_from set contain this node
- set.init(MergedFrom0),
- svset.insert(rptg_node(N), MergedFrom0, MergedFrom1),
- rptg_node_content_set_merged_from(MergedFrom1, Content0, Content),
-
- NodeMap0 = rptg_get_nodemap(!.G),
- svmap.set(rptg_node(N), Content, NodeMap0, NodeMap),
- rptg_set_nodemap(NodeMap, !G),
-
- % set edge
- EdgeMap0 = rptg_get_edgemap(!.G),
- svmap.set(rptg_node(N), map.init, EdgeMap0, EdgeMap),
- rptg_set_edgemap(EdgeMap, !G).
-
-rptg_node_contents(G, N) = NodeContents :-
- map.lookup(rptg_get_nodemap(G), N, NodeContents).
-
-rptg_get_nodes(G) = Nodes :-
- map.keys(rptg_get_nodemap(G), Nodes).
-
-rptg_successors(G, N) = Successors :-
- EdgeMap = rptg_get_edgemap(G),
- map.lookup(EdgeMap, N, OutEdges),
- map.values(OutEdges, SuccessorList),
+rptg_get_node_content(Graph, Node) = NodeContent :-
+ map.lookup(rptg_get_nodes(Graph), Node, NodeContent).
+
+rptg_get_nodes_as_list(Graph) = NodeList :-
+ map.keys(rptg_get_nodes(Graph), NodeList).
+
+rptg_successors(Graph, Node) = Successors :-
+ SuccessorList = rptg_lookup_list_endnodes(Graph, Node),
set.list_to_set(SuccessorList, Successors).
-rptg_set_edge(Start, End, Info, Arc, !G) :-
- AS0 = rptg_get_arc_supply(!.G),
- counter.allocate(A, AS0, AS),
- rptg_set_arc_supply(AS, !G),
-
- Arc = rptg_arc(A),
-
- ArcMap0 = rptg_get_arcmap(!.G),
- map.set(ArcMap0, Arc, rptg_arc_info(Start, End, Info), ArcMap),
- rptg_set_arcmap(ArcMap, !G),
-
- % register into edge set of the Start node
- EdgeMap0 = rptg_get_edgemap(!.G),
- map.lookup(EdgeMap0, Start, OutEdges0),
- map.set(OutEdges0, Arc, End, OutEdges),
- map.set(EdgeMap0, Start, OutEdges, EdgeMap),
- rptg_set_edgemap(EdgeMap, !G).
-
-rptg_arc_contents(G, Arc, S, E, Content) :-
- ArcMap = rptg_get_arcmap(G),
- map.lookup(ArcMap, Arc, I),
- I = rptg_arc_info(S, E, Content).
+rptg_set_edge(Start, End, EdgeContent, Edge, !G) :-
+ ES0 = rptg_get_edge_supply(!.G),
+ counter.allocate(EdgeId, ES0, ES),
+ rptg_set_edge_supply(ES, !G),
+
+ Edge = rptg_edge(EdgeId),
+
+ Edges0 = rptg_get_edges(!.G),
+ map.set(Edges0, Edge, rptg_edge_info(Start, End, EdgeContent), Edges),
+ rptg_set_edges(Edges, !G),
+
+ % Update the outedges of the Start node.
+ OutEdges0 = rptg_get_outedges(!.G),
+ map.lookup(OutEdges0, Start, StartOutEdges0),
+ svmap.set(Edge, End, StartOutEdges0, StartOutEdges),
+ svmap.set(Start, StartOutEdges, OutEdges0, OutEdges),
+ rptg_set_outedges(OutEdges, !G).
+
+rptg_get_edge_contents(G, Edge, Start, End, Content) :-
+ Edges = rptg_get_edges(G),
+ map.lookup(Edges, Edge, EdgeInfo),
+ EdgeInfo = rptg_edge_info(Start, End, Content).
rptg_path(G, S, E, Path) :-
rptg_path_2(G, S, E, [], Path).
:- pred rptg_path_2(rpt_graph, rptg_node, rptg_node, list(rptg_node),
- list(rptg_arc)).
+ list(rptg_edge)).
:- mode rptg_path_2(in, in, in, in, out) is nondet.
:- mode rptg_path_2(in, in, out, in, out) is nondet.
rptg_path_2(G, S, E, Nodes0, Path) :-
- EdgeMap = rptg_get_edgemap(G),
- map.lookup(EdgeMap, S, OutEdgesOfS),
+ OutEdges = rptg_get_outedges(G),
+ map.lookup(OutEdges, S, OutEdgesOfS),
(
- map.member(OutEdgesOfS, A, E),
+ map.member(OutEdgesOfS, Edge, E),
\+ list.member(E, Nodes0),
- Path = [A]
+ Path = [Edge]
;
- map.member(OutEdgesOfS, A, N),
+ map.member(OutEdgesOfS, Edge, N),
\+ list.member(N, Nodes0),
rptg_path_2(G, N, E, [N | Nodes0], Path0),
- Path = [A | Path0]
+ Path = [Edge | Path0]
).
- % Find a node that is reachable from Start and has type EType.
- % If not found, fails.
- %
-reachable_and_having_type(Graph, Start, EType, E) :-
+rptg_reachable_and_having_type(Graph, Start, EType, E) :-
rptg_lookup_node_type(Graph, Start) = Type,
( if
Type = EType
@@ -405,9 +462,7 @@
reachable_and_having_type_2(Graph, [StartNode | StartNodes0], VisitedNodes0,
EType, E) :-
- EdgeMap = rptg_get_edgemap(Graph),
- map.lookup(EdgeMap, StartNode, OutArcs),
- map.values(OutArcs, Ends),
+ Ends = rptg_lookup_list_endnodes(Graph, StartNode),
( if
find_node_with_same_type(Ends, Graph, EType, E1)
then
@@ -439,56 +494,40 @@
find_node_with_same_type(Ns, Graph, Type, End)
).
-rptg_node_content_set_vars(Vars, !NC) :-
- !:NC = !.NC ^ rptg_nc_vars := Vars.
-rptg_node_content_set_region_name(Name, !NC) :-
- !:NC = !.NC ^ rptg_nc_reg_var_name := Name.
-rptg_node_content_set_merged_from(Nodes, !NC) :-
- !:NC = !.NC ^ rptg_nc_merged_from := Nodes.
-rptg_node_content_set_node_type(NodeType, !NC) :-
- !:NC = !.NC ^ rptg_nc_node_type := NodeType.
-
-rptg_arc_content_get_label(AC) = AC ^ rptg_ac_label.
-rptg_arc_content_set_label(Label, !AC) :-
- !.AC ^ rptg_ac_label := Label = !:AC.
-
-get_node_by_region_name(Graph, RegName, Node) :-
- % from all nodes in the graph find a node corresponding to the
- % region name
- AllNodes = rptg_get_nodes(Graph),
+rptg_get_node_by_region_name(Graph, RegionName, Node) :-
+ AllNodes = rptg_get_nodes_as_list(Graph),
( if
- get_node_by_region_name_from_list(Graph, AllNodes, RegName, NodePrime)
+ get_node_by_region_name_from_list(Graph, AllNodes, RegionName,
+ NodePrime)
then
Node = NodePrime
else
- unexpected(this_file, "get_node_by_region_name: No such a node exists")
+ unexpected(this_file,
+ "rptg_get_node_by_region_name: No such a node exists")
).
:- pred get_node_by_region_name_from_list(rpt_graph::in, list(rptg_node)::in,
string::in, rptg_node::out) is semidet.
-get_node_by_region_name_from_list(Graph, List, RegName, Node) :-
- List = [ANode | Rest],
- NodeContents = rptg_node_contents(Graph, ANode),
+get_node_by_region_name_from_list(Graph, NodeList, RegName, Node) :-
+ NodeList = [ANode | Rest],
+ RegionANode = rptg_lookup_region_name(Graph, ANode),
( if
- NodeContents ^ rptg_nc_reg_var_name = RegName
+ RegionANode = RegName
then
Node = ANode
else
get_node_by_region_name_from_list(Graph, Rest, RegName, Node)
).
- % find a node in the graph using a set of variables.
- % Because a variable is assigned to only one node.
- %
-get_node_by_vars(Graph, Vars, Node) :-
- AllNodes = rptg_get_nodes(Graph),
+rptg_get_node_by_vars(Graph, Vars, Node) :-
+ Nodes = rptg_get_nodes_as_list(Graph),
( if
- get_node_by_vars_from_list(Graph, AllNodes, Vars, NodePrime)
+ get_node_by_vars_from_list(Graph, Nodes, Vars, NodePrime)
then
Node = NodePrime
else
- unexpected(this_file, "get_node_by_vars: No such a node exists")
+ unexpected(this_file, "rptg_get_node_by_vars: No such a node exists")
).
:- pred get_node_by_vars_from_list(rpt_graph::in, list(rptg_node)::in,
@@ -496,31 +535,26 @@
get_node_by_vars_from_list(Graph, List, Vars, Node) :-
List = [ANode | Rest],
- NodeContents = rptg_node_contents(Graph, ANode),
- ( set.subset(Vars, NodeContents ^ rptg_nc_vars) ->
+ NodeContent = rptg_get_node_content(Graph, ANode),
+ ( set.subset(Vars, NodeContent ^ rptg_nc_vars) ->
Node = ANode
;
get_node_by_vars_from_list(Graph, Rest, Vars, Node)
).
- % find a node in the graph using a variable assigned to it.
- % simply call get_node_by_vars.
+ % Find a node in the graph using a variable assigned to it.
%
-get_node_by_variable(Graph, Var, Node) :-
- % make a set(prog_var) containing the variable
- set.init(Vars0),
- set.insert(Vars0, Var, Vars),
- % find the node
- get_node_by_vars(Graph, Vars, Node).
-
-get_node_by_node(Graph, Node, MergedNode) :-
- % first the node in the NodeMap
- NodeMap = rptg_get_nodemap(Graph),
+rptg_get_node_by_variable(Graph, Var, Node) :-
+ Vars = set.make_singleton_set(Var),
+ rptg_get_node_by_vars(Graph, Vars, Node).
+
+rptg_get_node_by_node(Graph, Node, MergedNode) :-
+ NodeMap = rptg_get_nodes(Graph),
( map.search(NodeMap, Node, _NodeContent) ->
MergedNode = Node
;
- % not directly in the NodeMap, checked if it has been merged
- AllNodes = rptg_get_nodes(Graph),
+ % Not directly in the NodeMap, checked if it has been merged.
+ AllNodes = rptg_get_nodes_as_list(Graph),
( get_node_by_node_from_list(Graph, AllNodes, Node, MergedNode0) ->
MergedNode = MergedNode0
;
@@ -532,18 +566,71 @@
rptg_node::in, rptg_node::out) is semidet.
get_node_by_node_from_list(Graph, [N | Ns], Node, MergedNode) :-
- NodeContent = rptg_node_contents(Graph, N),
+ NodeContent = rptg_get_node_content(Graph, N),
( set.member(Node, NodeContent ^ rptg_nc_merged_from) ->
MergedNode = N
;
get_node_by_node_from_list(Graph, Ns, Node, MergedNode)
).
-rptg_lookup_region_name(Graph, Node) =
- rptg_node_contents(Graph, Node) ^ rptg_nc_reg_var_name.
+rptg_lookup_region_name(Graph, Node) = RegionName :-
+ NodeContent = rptg_get_node_content(Graph, Node),
+ RegionName = rptg_node_content_get_region_name(NodeContent).
+
+rptg_lookup_node_type(Graph, Node) = NodeType :-
+ NodeContent = rptg_get_node_content(Graph, Node),
+ NodeType = rptg_node_content_get_node_type(NodeContent).
+
+rptg_lookup_node_vars(Graph, Node) = Vars :-
+ NodeContent = rptg_get_node_content(Graph, Node),
+ Vars = rptg_node_content_get_vars(NodeContent).
+
+rptg_lookup_node_is_allocated(Graph, Node) = IsAllocated :-
+ NodeContent = rptg_get_node_content(Graph, Node),
+ IsAllocated = rptg_node_content_get_is_allocated(NodeContent).
+
+rptg_lookup_list_outedges(Graph, Node) = EdgeList :-
+ OutEdgesOfNode = rptg_lookup_map_outedges(Graph, Node),
+ map.keys(OutEdgesOfNode, EdgeList).
+
+rptg_lookup_map_outedges(Graph, Node) = OutEdgesOfNode :-
+ OutEdges = rptg_get_outedges(Graph),
+ map.lookup(OutEdges, Node, OutEdgesOfNode).
+
+rptg_lookup_list_endnodes(Graph, Node) = EndNodeList :-
+ OutEdgesOfNode = rptg_lookup_map_outedges(Graph, Node),
+ map.values(OutEdgesOfNode, EndNodeList).
+
+rptg_set_node_content(Node, NodeContent, !Graph) :-
+ Nodes0 = rptg_get_nodes(!.Graph),
+ map.det_update(Nodes0, Node, NodeContent, Nodes),
+ rptg_set_nodes(Nodes, !Graph).
+
+rptg_set_node_is_allocated(Node, IsAlloc, !Graph) :-
+ NodeContent0 = rptg_get_node_content(!.Graph, Node),
+ rptg_node_content_set_is_allocated(IsAlloc, NodeContent0, NodeContent),
+ rptg_set_node_content(Node, NodeContent, !Graph).
+
+rptg_node_content_get_vars(NC) = NC ^ rptg_nc_vars.
+rptg_node_content_get_region_name(NC) = NC ^ rptg_nc_reg_var_name.
+rptg_node_content_get_merged_from(NC) = NC ^ rptg_nc_merged_from.
+rptg_node_content_get_node_type(NC) = NC ^ rptg_nc_node_type.
+rptg_node_content_get_is_allocated(NC) = NC ^ rptg_nc_is_allocated.
-rptg_lookup_node_type(Graph, Node) =
- rptg_node_contents(Graph, Node) ^ rptg_nc_node_type.
+rptg_node_content_set_vars(Vars, !NC) :-
+ !NC ^ rptg_nc_vars := Vars.
+rptg_node_content_set_region_name(Name, !NC) :-
+ !NC ^ rptg_nc_reg_var_name := Name.
+rptg_node_content_set_merged_from(Nodes, !NC) :-
+ !NC ^ rptg_nc_merged_from := Nodes.
+rptg_node_content_set_node_type(NodeType, !NC) :-
+ !NC ^ rptg_nc_node_type := NodeType.
+rptg_node_content_set_is_allocated(IsAllocated, !NC) :-
+ !NC ^ rptg_nc_is_allocated := IsAllocated.
+
+rptg_edge_content_get_label(AC) = AC ^ rptg_ec_label.
+rptg_edge_content_set_label(Label, !AC) :-
+ !AC ^ rptg_ec_label := Label.
%-----------------------------------------------------------------------------%
%
@@ -551,21 +638,31 @@
%
unify_operator(Node1, Node2, !Graph) :-
- % The vars need to be unioned.
- NodeMap0 = rptg_get_nodemap(!.Graph),
- NodeContent1 = rptg_node_contents(!.Graph, Node1),
- NodeContent2 = rptg_node_contents(!.Graph, Node2),
+ Nodes0 = rptg_get_nodes(!.Graph),
+ NodeContent1 = rptg_get_node_content(!.Graph, Node1),
+ NodeContent2 = rptg_get_node_content(!.Graph, Node2),
+ % The vars need to be unioned.
set.union(NodeContent1 ^ rptg_nc_vars, NodeContent2 ^ rptg_nc_vars,
UnionVars),
rptg_node_content_set_vars(UnionVars, NodeContent1, NewContent0),
+
+ % Union the merged_from sets.
set.union(NodeContent1 ^ rptg_nc_merged_from,
NodeContent2 ^ rptg_nc_merged_from, UnionMergedFrom),
rptg_node_content_set_merged_from(UnionMergedFrom,
NewContent0, NewContent1),
- map.det_update(NodeMap0, Node1, NewContent1, NodeMap1),
- rptg_set_nodemap(NodeMap1, !Graph),
+ % The unified node is marked allocated if
+ % at least one of them is allocated.
+ IsAllocated = bool.or(NodeContent1 ^ rptg_nc_is_allocated,
+ NodeContent2 ^ rptg_nc_is_allocated),
+ rptg_node_content_set_is_allocated(IsAllocated,
+ NewContent1, NewContent),
+
+ map.det_update(Nodes0, Node1, NewContent, Nodes),
+
+ !Graph ^ rptg_nodes := Nodes,
% Copy all out-edges of node 2 to node 1.
transfer_out_edges(Node1, Node2, !Graph),
@@ -585,36 +682,35 @@
transfer_out_edges(Node1, Node2, !Graph) :-
% Out-edges from node 2.
- EdgeMap = rptg_get_edgemap(!.Graph),
- map.lookup(EdgeMap, Node2, OutEdges2Map),
- map.keys(OutEdges2Map, OutArcs),
- % Transfer them to node 1
- transfer_out_edges_2(OutArcs, Node1, !Graph).
+ EdgeList = rptg_lookup_list_outedges(!.Graph, Node2),
+
+ % Transfer them to node 1.
+ transfer_out_edges_2(EdgeList, Node1, !Graph).
% This predicate receives a list of out-edges of node2 and returns a
% graph with all the edges in the list copied to Node1, but it
- % maintains the invariant that "there is only one arc with a
+ % maintains the invariant that "there is only one edge with a
% specific label from a specific node to another specific node".
% The algorithm is as follows.
- % for each arc (Node2, Content, Node) in OutArcs2 list:
+ % for each edge (Node2, Content, Node) in EdgeList:
% if (Node1, Content, Node) exists
- % ignore the arc
+ % ignore the edge.
% else
- % copy the arc to Node1.
+ % copy the edge to Node1.
%
-:- pred transfer_out_edges_2(list(rptg_arc)::in, rptg_node::in,
+:- pred transfer_out_edges_2(list(rptg_edge)::in, rptg_node::in,
rpt_graph::in, rpt_graph::out) is det.
transfer_out_edges_2([], _, !Graph).
-transfer_out_edges_2([Arc | Arcs], Node1, !Graph) :-
- rptg_arc_contents(!.Graph, Arc, _Node2, Node, ArcContent),
- ( edge_in_graph(Node1, ArcContent, Node, !.Graph) ->
+transfer_out_edges_2([Edge | Edges], Node1, !Graph) :-
+ rptg_get_edge_contents(!.Graph, Edge, _Node2, Node, EdgeContent),
+ ( rptg_edge_in_graph(Node1, EdgeContent, Node, !.Graph) ->
true
;
- % not existed, copy the Arc as an out-edge of Node1
- rptg_set_edge(Node1, Node, ArcContent, _Arc, !Graph)
+ % Not existed, copy the Edge as an out-edge of Node1.
+ rptg_set_edge(Node1, Node, EdgeContent, _Edge, !Graph)
),
- transfer_out_edges_2(Arcs, Node1, !Graph).
+ transfer_out_edges_2(Edges, Node1, !Graph).
% This predicate receives a graph and returns a new graph in which
% all the in-edges of node2 in the first graph are copied as in-edges
@@ -624,122 +720,122 @@
rpt_graph::out) is det.
transfer_in_edges(Node1, Node2, !Graph) :-
- % in-edges of node 2
- rptg_get_in_arcs(!.Graph, Node2, InArcs),
- % copy them to node 1
- transfer_in_edges_2(InArcs, Node1, !Graph).
+ % In-edges of node 2.
+ rptg_get_in_edges(!.Graph, Node2, InEdges),
+
+ % Copy them to node 1.
+ transfer_in_edges_2(InEdges, Node1, !Graph).
- % Finding incoming arcs to a node is not direct as finding outcoming
- % ones, we have to scan all the arcs in the graph and explicitly
+ % Finding incoming edges to a node is not direct as finding outcoming
+ % ones, we have to scan all the edges in the graph and explicitly
% check their ending node.
+ % XXX This potentially is very inefficient. We might consider storing
+ % InEdges explicitly like OutEdges.
%
-:- pred rptg_get_in_arcs(rpt_graph::in, rptg_node::in, list(rptg_arc)::out)
+:- pred rptg_get_in_edges(rpt_graph::in, rptg_node::in, list(rptg_edge)::out)
is det.
-rptg_get_in_arcs(Graph, Node, Arcs) :-
- ArcMap = rptg_get_arcmap(Graph),
- map.foldl(arc_points_to_node(Node), ArcMap, [], Arcs).
+rptg_get_in_edges(Graph, Node, InEdges) :-
+ Edges = rptg_get_edges(Graph),
+ map.foldl(edge_points_to_node(Node), Edges, [], InEdges).
-:- pred arc_points_to_node(rptg_node::in, rptg_arc::in, rptg_arc_info::in,
- list(rptg_arc)::in, list(rptg_arc)::out) is det.
+:- pred edge_points_to_node(rptg_node::in, rptg_edge::in, rptg_edge_info::in,
+ list(rptg_edge)::in, list(rptg_edge)::out) is det.
-arc_points_to_node(End, Arc, ArcInfo, !L) :-
- ArcInfo = rptg_arc_info(_S, E, _C),
+edge_points_to_node(End, Edge, EdgeInfo, !L) :-
+ EdgeInfo = rptg_edge_info(_S, E, _C),
( E = End ->
- !:L = [Arc | !.L]
+ !:L = [Edge | !.L]
;
true
).
% This predicate is very similar to transfer_out_edges_2, except that
- % the arcs now point to Node1, instead of going out from it.
+ % the edges now point to Node1, instead of going out from it.
%
-:- pred transfer_in_edges_2(list(rptg_arc)::in, rptg_node::in, rpt_graph::in,
+:- pred transfer_in_edges_2(list(rptg_edge)::in, rptg_node::in, rpt_graph::in,
rpt_graph::out) is det.
transfer_in_edges_2([], _, !Graph).
-transfer_in_edges_2([Arc | Arcs], Node1, !Graph) :-
- rptg_arc_contents(!.Graph, Arc, Node, _Node2, ArcContent),
- ( edge_in_graph(Node, ArcContent, Node1, !.Graph) ->
+transfer_in_edges_2([Edge | Edges], Node1, !Graph) :-
+ rptg_get_edge_contents(!.Graph, Edge, Node, _Node2, EdgeContent),
+ ( rptg_edge_in_graph(Node, EdgeContent, Node1, !.Graph) ->
true
;
- % No, copy the Arc as an in-edge of Node1
- rptg_set_edge(Node, Node1, ArcContent, _Arc, !Graph)
+ % No, copy the Edge as an in-edge of Node1.
+ rptg_set_edge(Node, Node1, EdgeContent, _Edge, !Graph)
),
- transfer_in_edges_2(Arcs, Node1, !Graph).
+ transfer_in_edges_2(Edges, Node1, !Graph).
% Delete a node from the graph.
- % We also need to delete all the edges and arcs from the Node,
- % and delete all edges and arcs to the Node.
+ % We also need to delete all the edges from and to the Node.
%
:- pred delete_node(rptg_node::in, rpt_graph::in, rpt_graph::out) is det.
-delete_node(Node, Graph0, Graph) :-
- Graph0 = rpt_graph(NS, AS, NodeMap0, ArcMap0, EdgeMap0),
- map.delete(NodeMap0, Node, NodeMap),
- delete_all_outedges_and_arcs(Node, ArcMap0, ArcMap1, EdgeMap0, EdgeMap1),
- delete_all_inedges_and_arcs(Node, ArcMap1, ArcMap, EdgeMap1, EdgeMap),
- Graph = rpt_graph(NS, AS, NodeMap, ArcMap, EdgeMap).
+delete_node(Node,
+ rpt_graph(NS, AS, !.Nodes, !.Edges, !.OutEdges),
+ rpt_graph(NS, AS, !:Nodes, !:Edges, !:OutEdges)) :-
+ svmap.delete(Node, !Nodes),
+ delete_all_outedges_and_edges(Node, !Edges, !OutEdges),
+ delete_all_inedges_and_edges(Node, !Edges, !OutEdges).
- % This predicate deletes all the edges which start from the input
- % node Node.
+ % This predicate deletes all the outedges of Node.
% Note: it works as a helper for delete_node so it does not proceed
- % on a graph but on the edge map and the arc map.
+ % on a graph but on the edges map and outedges map.
%
-:- pred delete_all_outedges_and_arcs(rptg_node::in,
- map(rptg_arc, rptg_arc_info)::in,
- map(rptg_arc, rptg_arc_info)::out,
- map(rptg_node, map(rptg_arc, rptg_node))::in,
- map(rptg_node, map(rptg_arc, rptg_node))::out) is det.
-
-delete_all_outedges_and_arcs(Node, !ArcMap, !EdgeMap) :-
- % Delete the corresponding arcs from arc map.
- map.lookup(!.EdgeMap, Node, EdgesFromNodeMap),
- map.keys(EdgesFromNodeMap, OutArcs),
- svmap.delete_list(OutArcs, !ArcMap),
- % Delete all outcoming edges of the Node from edge map.
- svmap.delete(Node, !EdgeMap).
+:- pred delete_all_outedges_and_edges(rptg_node::in,
+ rptg_edges::in, rptg_edges::out,
+ rptg_outedges::in, rptg_outedges::out) is det.
+
+delete_all_outedges_and_edges(Node, !Edges, !OutEdges) :-
+ % Delete the edges themselves.
+ map.lookup(!.OutEdges, Node, OutEdgesOfNode),
+ map.keys(OutEdgesOfNode, TheEdges),
+ svmap.delete_list(TheEdges, !Edges),
+
+ % Delete the info about outcoming edges.
+ svmap.delete(Node, !OutEdges).
% This predicate deletes all the incoming edges of the input node (Node).
% We only store outcoming edges therefore to remove incoming ones of Node
% we need to check all the outcoming edges and remove those point to Node.
%
-:- pred delete_all_inedges_and_arcs(rptg_node::in,
- map(rptg_arc, rptg_arc_info)::in,
- map(rptg_arc, rptg_arc_info)::out,
- map(rptg_node, map(rptg_arc, rptg_node))::in,
- map(rptg_node, map(rptg_arc, rptg_node))::out) is det.
+:- pred delete_all_inedges_and_edges(rptg_node::in,
+ rptg_edges::in, rptg_edges::out, rptg_outedges::in, rptg_outedges::out)
+ is det.
-delete_all_inedges_and_arcs(Node, !ArcMap, !EdgeMap) :-
- map.keys(!.EdgeMap, StartNodes),
+delete_all_inedges_and_edges(Node, !Edges, !OutEdges) :-
+ map.keys(!.OutEdges, StartNodes),
% For each node: find the outcoming edges from it
% and delete ones pointing to Node.
- delete_all_inedges_and_arcs_2(StartNodes, Node, !ArcMap, !EdgeMap).
+ delete_all_inedges_and_edges_2(StartNodes, Node, !Edges, !OutEdges).
% This predicate receives a node (Node) and a list of (start) nodes.
- % It deletes all the start nodes' outcoming edges and corresponding arcs
+ % It deletes all the start nodes' outcoming edges and corresponding edges
% which point to the Node.
%
-:- pred delete_all_inedges_and_arcs_2(list(rptg_node)::in, rptg_node::in,
- map(rptg_arc, rptg_arc_info)::in, map(rptg_arc, rptg_arc_info)::out,
- map(rptg_node, map(rptg_arc, rptg_node))::in,
- map(rptg_node, map(rptg_arc, rptg_node))::out) is det.
-
-delete_all_inedges_and_arcs_2([], _, !ArcMap, !EdgeMap).
-delete_all_inedges_and_arcs_2([N | Ns], Node, !ArcMap, !EdgeMap) :-
- % Find the mapping with end node = Node, there will be only one,
- % but we do as below because inverse_search is non-det.
- map.lookup(!.EdgeMap, N, EdgesFromN0),
- solutions(map.inverse_search(EdgesFromN0, Node), ArcsFromNPointToNode),
-
- svmap.delete_list(ArcsFromNPointToNode, !ArcMap),
- svmap.delete_list(ArcsFromNPointToNode, EdgesFromN0, EdgesFromN),
- svmap.set(N, EdgesFromN, !EdgeMap),
- delete_all_inedges_and_arcs_2(Ns, Node, !ArcMap, !EdgeMap).
+:- pred delete_all_inedges_and_edges_2(list(rptg_node)::in, rptg_node::in,
+ rptg_edges::in, rptg_edges::out, rptg_outedges::in, rptg_outedges::out)
+ is det.
+
+delete_all_inedges_and_edges_2([], _, !Edges, !OutEdges).
+delete_all_inedges_and_edges_2([N | Ns], Node, !Edges, !OutEdges) :-
+ map.lookup(!.OutEdges, N, OutEdgesOfN0),
+
+ % Find the edges that point to Node.
+ solutions(map.inverse_search(OutEdgesOfN0, Node), EdgesFromNPointToNode),
+
+ % Delete the edges themselves.
+ svmap.delete_list(EdgesFromNPointToNode, !Edges),
+
+ % Delete the info about outedges.
+ svmap.delete_list(EdgesFromNPointToNode, OutEdgesOfN0, OutEdgesOfN),
+ svmap.set(N, OutEdgesOfN, !OutEdges),
+ delete_all_inedges_and_edges_2(Ns, Node, !Edges, !OutEdges).
edge_operator(Start, End, Info, !G) :-
- rptg_set_edge(Start, End, Info, _Arc, !G).
+ rptg_set_edge(Start, End, Info, _Edge, !G).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -747,28 +843,28 @@
% For finding and checking edges in graph.
%
-find_arc_from_node_with_same_label(N, ArcContent, G, M) :-
- EdgeMap = rptg_get_edgemap(G),
- map.lookup(EdgeMap, N, OutEdges),
- map.keys(OutEdges, OutArcs),
- find_arc_with_same_label(ArcContent, OutArcs, G, M).
-
-:- pred find_arc_with_same_label(rptg_arc_content::in,
- list(rptg_arc)::in, rpt_graph::in, rptg_node::out) is semidet.
-
-find_arc_with_same_label(ArcContent, [Arc | Arcs], G, M) :-
- rptg_arc_contents(G, Arc, _N, M0, ArcContent0),
- ( ArcContent0 = ArcContent ->
+rptg_find_edge_from_node_with_same_content(N, EdgeContent, G, M) :-
+ EdgeList = rptg_lookup_list_outedges(G, N),
+ find_edge_with_same_content(EdgeContent, EdgeList, G, M).
+
+:- pred find_edge_with_same_content(rptg_edge_content::in,
+ list(rptg_edge)::in, rpt_graph::in, rptg_node::out) is semidet.
+
+find_edge_with_same_content(EdgeContent, [Edge | Edges], G, M) :-
+ rptg_get_edge_contents(G, Edge, _N, M0, EdgeContent0),
+ ( EdgeContent0 = EdgeContent ->
M = M0
;
- find_arc_with_same_label(ArcContent, Arcs, G, M)
+ find_edge_with_same_content(EdgeContent, Edges, G, M)
).
-edge_in_graph(Start, Label, End, Graph) :-
- EdgeMap = rptg_get_edgemap(Graph),
- map.lookup(EdgeMap, Start, OutEdges),
- solutions(map.inverse_search(OutEdges, End), ArcList),
- find_arc_with_same_label(Label, ArcList, Graph, _).
+rptg_edge_in_graph(Start, Label, End, Graph) :-
+ OutEdgesOfStart = rptg_lookup_map_outedges(Graph, Start),
+
+ % Out of the above, find those that point to End.
+ solutions(map.inverse_search(OutEdgesOfStart, End), EdgePointToEndList),
+
+ find_edge_with_same_content(Label, EdgePointToEndList, Graph, _).
%-----------------------------------------------------------------------------%
@@ -778,13 +874,13 @@
%
rptg_equal(Graph1, Graph2) :-
- Graph1 = rpt_graph(NS1, AS1, Nodes1, Arcs1, Edges1),
- Graph2 = rpt_graph(NS2, AS2, Nodes2, Arcs2, Edges2),
+ Graph1 = rpt_graph(NS1, AS1, Nodes1, Edges1, OutEdges1),
+ Graph2 = rpt_graph(NS2, AS2, Nodes2, Edges2, OutEdges2),
NS1 = NS2,
AS1 = AS2,
simple_map_equal(Nodes1, Nodes2),
- simple_map_equal(Arcs1, Arcs2),
- complex_map_equal(Edges1, Edges2).
+ simple_map_equal(Edges1, Edges2),
+ complex_map_equal(OutEdges1, OutEdges2).
% The comparisons below may not be necessary, unification can help if it is
% sure that the elements are added to the maps in the same order.
@@ -852,8 +948,8 @@
% The regions must be reached by edges with labels (type selectors)
% which are valid with the type of X.
%
-reach_from_a_variable(Graph, HLDS, ProcInfo, X, !Reach_X) :-
- get_node_by_variable(Graph, X, N_X),
+rptg_reach_from_a_variable(Graph, HLDS, ProcInfo, X, !Reach_X) :-
+ rptg_get_node_by_variable(Graph, X, N_X),
Node_Selector = pair(N_X, []),
proc_info_get_vartypes(ProcInfo, VarTypes),
@@ -868,7 +964,7 @@
% from the node of X.
% Algorithm:
% 1. each node is recorded into the reach_from_x set,
- % 2. if an target of a node's out-arc can be reached by a valid
+ % 2. if an target of a node's out-edge can be reached by a valid
% selector, we "remember" the target as reachable from X but not
% record it yet,
% 3. do until the remembered list is empty.
@@ -890,32 +986,33 @@
% is in there it will not be in the to-be-processed list.
Processed = [Node | Processed0],
- % Take out-arcs of the Node and update the remembered list
- EdgeMap = rptg_get_edgemap(Graph),
- map.lookup(EdgeMap, Node, OutEdges),
- map.keys(OutEdges, OutArcs),
+ % Take out-edges of the Node and update the remembered list.
+ %OutEdges = rptg_get_outedges(Graph),
+ %map.lookup(OutEdges, Node, OutEdgesOfNode),
+ %map.keys(OutEdgesOfNode, EdgeList),
+ EdgeList = rptg_lookup_list_outedges(Graph, Node),
list.foldl(
update_remembered_list(Selector, HLDS, TypeX, Graph, Processed),
- OutArcs, Node_Selectors0, Node_Selectors),
+ EdgeList, Node_Selectors0, Node_Selectors),
reach_from_a_variable_2(Node_Selectors, Graph, HLDS, TypeX,
Processed, !Reach_X).
- % A target is remembered as reachable from X if its arc's selector
+ % A target is remembered as reachable from X if its edge's selector
% is valid. The remembered list is appended, so it is a breadth-first
% process.
%
:- pred update_remembered_list(selector::in, module_info::in,
- mer_type::in, rpt_graph::in, list(rptg_node)::in, rptg_arc::in,
+ mer_type::in, rpt_graph::in, list(rptg_node)::in, rptg_edge::in,
assoc_list(rptg_node, selector)::in,
assoc_list(rptg_node, selector)::out) is det.
-update_remembered_list(Selector0, HLDS, TypeX, Graph, Processed, OutArc,
+update_remembered_list(Selector0, HLDS, TypeX, Graph, Processed, OutEdge,
!List) :-
- rptg_arc_contents(Graph, OutArc, _Start, End, ArcContent),
- ArcSelector = ArcContent ^ rptg_ac_label,
- Selector = Selector0 ++ ArcSelector,
+ rptg_get_edge_contents(Graph, OutEdge, _Start, End, EdgeContent),
+ EdgeSelector = rptg_edge_content_get_label(EdgeContent),
+ Selector = Selector0 ++ EdgeSelector,
( check_type_of_node(HLDS, TypeX, Selector) ->
- % The arc's selector is a valid one.
+ % The edge's selector is a valid one.
( list.member(End, Processed) ->
% Already processed, ignore.
true
Index: rbmm.points_to_info.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.points_to_info.m,v
retrieving revision 1.3
diff -u -r1.3 rbmm.points_to_info.m
--- rbmm.points_to_info.m 23 Jul 2007 05:06:14 -0000 1.3
+++ rbmm.points_to_info.m 20 Apr 2009 11:54:08 -0000
@@ -66,6 +66,7 @@
:- import_module parse_tree.prog_data.
:- import_module assoc_list.
+:- import_module bool.
:- import_module int.
:- import_module list.
:- import_module set.
@@ -102,8 +103,8 @@
set.insert(Varset0, Var, Varset),
Reg = Reg0 + 1,
string.append("R", string.int_to_string(Reg0), RegName),
- NodeInfo = rptg_node_content(Varset, RegName, set.init, NodeType),
- rptg_set_node(NodeInfo, _Node, !Graph).
+ NodeInfo = rptg_node_content(Varset, RegName, set.init, NodeType, bool.no),
+ rptg_add_node(NodeInfo, _Node, !Graph).
rpta_info_equal(RptaInfoA, RptaInfoB):-
RptaInfoA = rpta_info(GraphA, AlphaA),
Index: rbmm.region_instruction.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.region_instruction.m,v
retrieving revision 1.5
diff -u -r1.5 rbmm.region_instruction.m
--- rbmm.region_instruction.m 8 Apr 2008 20:12:17 -0000 1.5
+++ rbmm.region_instruction.m 20 Apr 2009 11:54:08 -0000
@@ -345,7 +345,7 @@
->
RptaInfo = rpta_info(Graph, _AlphaMapping),
% Need to be regions reachable from X.
- reach_from_a_variable(Graph, ModuleInfo, ProcInfo, X,
+ rptg_reach_from_a_variable(Graph, ModuleInfo, ProcInfo, X,
set.init, Reach_X),
set.intersect(Reach_X, ToBeCreatedAndAllowed,
Index: rbmm.region_transformation.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.region_transformation.m,v
retrieving revision 1.8
diff -u -r1.8 rbmm.region_transformation.m
--- rbmm.region_transformation.m 23 Dec 2008 01:37:40 -0000 1.8
+++ rbmm.region_transformation.m 20 Apr 2009 11:54:08 -0000
@@ -547,9 +547,18 @@
!NameToVar, !VarSet, !VarTypes),
!:GoalExpr = negation(Goal)
;
- !.GoalExpr = scope(Reason, Goal0),
+ !.GoalExpr = scope(Reason0, Goal0),
% XXX We should special-case the handling of from_ground_term_construct
% scopes.
+ % qph: A safe but potentially inefficient way is to turn these scopes
+ % into from_ground_term_other, i.e., we expect that some region
+ % instructions are added in these scopes. This expectation seems
+ % reasonable because a region is often created before a heap
+ % allocation.
+ ( Reason0 = from_ground_term(Var, _Kind) ->
+ Reason = from_ground_term(Var, from_ground_term_other)
+ ; Reason = Reason0
+ ),
region_transform_goal(ModuleInfo, Graph, ResurRenamingProc,
IteRenamingProc, ActualRegionArgProc, RegionInstructionProc,
ResurRenamingAnnoProc, IteRenamingAnnoProc, Goal0, Goal,
@@ -598,7 +607,7 @@
IteRenaming, !Unification, !NameToVar, !VarSet, !VarTypes) :-
!.Unification = construct(Var, ConsId, Args, ArgModes, _HowToConstruct0,
IsUnique, SubInfo),
- get_node_by_variable(Graph, Var, Node),
+ rptg_get_node_by_variable(Graph, Var, Node),
NodeType = rptg_lookup_node_type(Graph, Node),
( type_not_stored_in_region(NodeType, ModuleInfo) ->
true
More information about the reviews
mailing list