[m-rev.] for review: stack slot optimization, part 4
Zoltan Somogyi
zs at cs.mu.OZ.AU
Sat Mar 9 20:22:38 AEDT 2002
Index: compiler/matching.m
===================================================================
RCS file: compiler/matching.m
diff -N compiler/matching.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/matching.m 19 Feb 2002 13:43:14 -0000
@@ -0,0 +1,722 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2001-2002 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% Authors: pjs, zs
+% Stability: low
+%
+% Module `matching' - performs bipartite graph maximal matching computation
+% specialized for the stack slot optimization. The structure of the graph
+% on which the algorithm operates is documented in the paper "Using the heap
+% to eliminate stack accesses" by Zoltan Somogyi and Peter Stuckey.
+%
+%-----------------------------------------------------------------------------%
+
+:- module matching.
+
+:- interface.
+:- import_module prog_data.
+
+:- import_module bool, list, set.
+
+%-----------------------------------------------------------------------------%
+
+% find_via_cell_vars(CellVar, CandidateFieldVars, CellVarFlushedLater,
+% BeforeFlush, AfterFlush, CellVarStoreCost, CellVarLoadCost,
+% FieldVarStoreCost, FieldVarLoadCost,
+% OpRatio, NodeRatio, InclAllCand,
+% RealizedBenefitNodes, RealizedCostNodes, ViaCellVars)
+%
+% CellVar gives a variable that corresponds to a memory cell, while
+% CandidateArgVars gives a subset of the variables that are the fields
+% of that cell. BeforeFlush gives the set of variables the program accesses
+% in the segment before the first stack flush, while each element of AfterFlush
+% corresponds to a segment, and gives the set of variables accessed in that
+% segment. CellVarStoreCost, CellVarStoreCost, FieldVarStoreCost and
+% FieldVarStoreCost give the relative costs of the four kinds of operations
+% this optimization concerns itself with. OpRatio and NodeRatio are tuning
+% parameters; find_via_cell_vars will say that the optimization is inapplicable
+% (i.e. that none of the candidates should be accessed via the cell) unless
+% the ratios of benefit operations to cost operations and benefit nodes to cost
+% nodes are at or above the percentage thresholds specified by OpRatio
+% and NodeRatio respectively. The boolean InclAllCand says whether this
+% thresholding operation is to count the benefits obtainable from the candidate
+% variables that do not happen to be accessed in AfterFlush.
+%
+% The output ViaCellVars, gives the subset of CandidateArgVars that should be
+% accesed via CellVar. The outputs RealizedBenefitNodes and RealizedCostNodes
+% give the benefit and cost nodes realized by this choice.
+
+:- type benefit_node.
+:- type cost_node.
+
+:- pred find_via_cell_vars(prog_var::in, set(prog_var)::in, bool::in,
+ set(prog_var)::in, list(set(prog_var))::in, int::in, int::in,
+ int::in, int::in, int::in, int::in, bool::in, set(benefit_node)::out,
+ set(cost_node)::out, set(prog_var)::out) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+% Uncomment if you want to dump performance information into the .err file.
+% :- import_module unsafe.
+
+:- import_module term.
+:- import_module int, assoc_list, map, queue, std_util, require, io.
+
+% The stack optimization graph is a bipartite graph, whose two node types
+% are cost nodes and benefit nodes. Each node represents a copy of an
+% operation, a load or a store. We have LoadCost copies of each load operation
+% and StoreCost copies of each store operation, where LoadCost and StoreCost
+% are parameters of find_via_cell_vars.
+%
+% We represent the stack optimization graph in the usual manner: as two maps,
+% with each map one kind of node to the set of nodes of the other types to
+% which it is adjacent.
+
+:- type stack_slot_graph
+ ---> stack_slot_graph(
+ map(cost_node, set(benefit_node)),
+ map(benefit_node, set(cost_node))
+ ).
+
+:- type cost_operation
+ ---> cell_var_load(int) % segment number, >= 2
+ ; cell_var_store. % in initial segment
+
+:- type benefit_operation
+ ---> field_var_load(prog_var) % in initial segment
+ ; field_var_store(prog_var). % in initial segment
+
+% The integers differentiate the different copies of an operation.
+:- type cost_node ---> cost_node(cost_operation, int).
+:- type benefit_node ---> benefit_node(benefit_operation, int).
+
+% The field_costs_benefits structure records, for a given field variable,
+% the nodes of the cost we incur and the benefits we gain if we access that
+% field variable via the cell instead of via the stack.
+
+:- type field_costs_benefits
+ ---> field_costs_benefits(
+ prog_var,
+ set(cost_node),
+ set(benefit_node)
+ ).
+
+% Matchings are sets of edges, in which each node in the graph can occur at
+% most once. We represent the matching by mapping each node that is an endpoint
+% of an edge in the matching to the node at the other end of the edge.
+% If a node is not in the matching, it will not occur in the relevant map.
+
+:- type matching
+ ---> matching(
+ map(cost_node, benefit_node),
+ map(benefit_node, cost_node)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+% Uncomment if you want to dump performance information into the .err file.
+% :- pragma promise_pure(find_via_cell_vars/15).
+
+find_via_cell_vars(CellVar, CandidateFieldVars, CellVarFlushedLater,
+ BeforeFlush, AfterFlush, CellVarStoreCost, CellVarLoadCost,
+ FieldVarStoreCost, FieldVarLoadCost,
+ OpRatio, NodeRatio, InclAllCand,
+ RealizedBenefitNodes, RealizedCostNodes, ViaCellVars) :-
+ (
+ InclAllCand = no,
+ AllSegmentVars = set__union_list([BeforeFlush | AfterFlush]),
+ set__intersect(CandidateFieldVars, AllSegmentVars,
+ OccurringCandidateFieldVars),
+ set__difference(CandidateFieldVars, OccurringCandidateFieldVars,
+ NonOccurringCandidateFieldVars)
+ ;
+ InclAllCand = yes,
+ OccurringCandidateFieldVars = CandidateFieldVars,
+ NonOccurringCandidateFieldVars = set__init
+ ),
+ set__to_sorted_list(OccurringCandidateFieldVars,
+ OccurringCandidateFieldVarList),
+ list__filter_map(
+ simplify_segment(CellVar, OccurringCandidateFieldVars),
+ AfterFlush, FilteredAfterFlush),
+ NumberedAfterFlush = number_segments(2, FilteredAfterFlush),
+ CostsBenefits = list__map(
+ find_costs_benefits(CellVar, BeforeFlush, NumberedAfterFlush,
+ CellVarFlushedLater, CellVarStoreCost, CellVarLoadCost,
+ FieldVarStoreCost, FieldVarLoadCost),
+ OccurringCandidateFieldVarList),
+ list__foldl(gather_benefits, CostsBenefits, set__init, BenefitNodes),
+ list__foldl(gather_costs, CostsBenefits, set__init, CostNodes),
+ set__to_sorted_list(BenefitNodes, BenefitNodeList),
+ set__to_sorted_list(CostNodes, CostNodeList),
+ Graph = create_graph(CostsBenefits),
+ MaximalMatching = maximal_matching(BenefitNodeList, Graph),
+ MaximalMatching = matching(MaximalMatchingCostToBenefit, _),
+ UnMatchedCostNodes = get_unmatched_cost_nodes(CostNodeList,
+ MaximalMatchingCostToBenefit),
+ MarkedBenefitNodes = reachable_by_alternating_path(UnMatchedCostNodes,
+ Graph, MaximalMatching),
+ ViaCellOccurringVars0 =
+ compute_via_cell_vars(CostsBenefits, MarkedBenefitNodes),
+ list__filter(realized_costs_benefits(ViaCellOccurringVars0),
+ CostsBenefits, RealizedCostsBenefits),
+ list__foldl(gather_benefits, RealizedCostsBenefits,
+ set__init, RealizedBenefitNodes),
+ list__foldl(gather_costs, RealizedCostsBenefits,
+ set__init, RealizedCostNodes),
+ RealizedBenefitOps =
+ set__map(project_benefit_op, RealizedBenefitNodes),
+ RealizedCostOps =
+ set__map(project_cost_op, RealizedCostNodes),
+ set__to_sorted_list(RealizedBenefitNodes, RealizedBenefitNodeList),
+ set__to_sorted_list(RealizedCostNodes, RealizedCostNodeList),
+ set__to_sorted_list(RealizedBenefitOps, RealizedBenefitOpList),
+ set__to_sorted_list(RealizedCostOps, RealizedCostOpList),
+ list__length(RealizedBenefitNodeList, RealizedBenefitNodeCount),
+ list__length(RealizedBenefitOpList, RealizedBenefitOpCount),
+ list__length(RealizedCostNodeList, RealizedCostNodeCount),
+ list__length(RealizedCostOpList, RealizedCostOpCount),
+ (
+ RealizedBenefitOpCount * 100 >=
+ RealizedCostOpCount * OpRatio,
+ RealizedBenefitNodeCount * 100 >=
+ RealizedCostNodeCount * NodeRatio
+ ->
+ ViaCellOccurringVars = ViaCellOccurringVars0
+ % Uncomment if you want to dump performance information into
+ % the .err file.
+ % Nullified = no
+ ;
+ ViaCellOccurringVars = set__init
+ % Uncomment if you want to dump performance information into
+ % the .err file.
+ % Nullified = yes
+ ),
+ ViaCellVars = set__union(ViaCellOccurringVars,
+ NonOccurringCandidateFieldVars).
+ % Uncomment if you want to dump performance information into
+ % the .err file.
+ % impure unsafe_perform_io(dump_results(CellVar, CandidateFieldVars,
+ % OccurringCandidateFieldVarList, ViaCellOccurringVars0,
+ % Nullified, BeforeFlush, NumberedAfterFlush,
+ % RealizedBenefitNodeList, RealizedBenefitOpList,
+ % RealizedCostNodeList, RealizedCostOpList)).
+
+%-----------------------------------------------------------------------------%
+
+% Simplify_segment fails if the CellVar is in the SegmentVars since the cost
+% of executing such segments doesn't depend on whether we access field vars
+% via the cell var or via the stack. If CellVar is not in SegmentVars,
+% them simplify_segment succeeds after removing the non-candidate variables
+% from SegmentVars0.
+
+:- pred simplify_segment(prog_var::in, set(prog_var)::in, set(prog_var)::in,
+ set(prog_var)::out) is semidet.
+
+simplify_segment(CellVar, CandidateArgVars, SegmentVars0, SegmentVars) :-
+ \+ set__member(CellVar, SegmentVars0),
+ SegmentVars = set__intersect(SegmentVars0, CandidateArgVars).
+
+:- func number_segments(int, list(set(prog_var))) =
+ assoc_list(int, set(prog_var)).
+
+number_segments(_N, []) = [].
+number_segments(N, [Segment | Segments]) =
+ [N - Segment | number_segments(N + 1, Segments)].
+
+%-----------------------------------------------------------------------------%
+
+:- func find_costs_benefits(prog_var, set(prog_var),
+ assoc_list(int, set(prog_var)), bool, int, int, int, int, prog_var)
+ = field_costs_benefits.
+
+find_costs_benefits(CellVar, BeforeFlush, AfterFlush, CellVarFlushedLater,
+ CellVarStoreCost, CellVarLoadCost,
+ FieldVarStoreCost, FieldVarLoadCost, FieldVar)
+ = FieldCostsBenefits :-
+ find_cell_var_loads_for_field(AfterFlush, FieldVar, [], CostOps0),
+ (
+ CellVarFlushedLater = yes,
+ CostOps = CostOps0
+ ;
+ CellVarFlushedLater = no,
+ CostOps = [cell_var_store | CostOps0]
+ ),
+ BenefitOps0 = [field_var_store(FieldVar)],
+ ( set__member(CellVar, BeforeFlush) ->
+ BenefitOps = BenefitOps0
+ ;
+ BenefitOps = [field_var_load(FieldVar) | BenefitOps0]
+ ),
+
+ CostNodeLists = list__map(
+ replicate_cost_op(CellVarStoreCost, CellVarLoadCost),
+ CostOps),
+ list__condense(CostNodeLists, CostNodes),
+ set__list_to_set(CostNodes, CostNodeSet),
+ BenefitNodeLists = list__map(
+ replicate_benefit_op(FieldVarStoreCost, FieldVarLoadCost),
+ BenefitOps),
+ list__condense(BenefitNodeLists, BenefitNodes),
+ set__list_to_set(BenefitNodes, BenefitNodeSet),
+ FieldCostsBenefits = field_costs_benefits(FieldVar,
+ CostNodeSet, BenefitNodeSet).
+
+:- pred find_cell_var_loads_for_field(assoc_list(int, set(prog_var))::in,
+ prog_var::in, list(cost_operation)::in, list(cost_operation)::out)
+ is det.
+
+find_cell_var_loads_for_field([], _, CostOps, CostOps).
+find_cell_var_loads_for_field([SegmentNum - SegmentVars | AfterFlush],
+ FieldVar, CostOps0, CostOps) :-
+ ( set__member(FieldVar, SegmentVars) ->
+ CostOps1 = [cell_var_load(SegmentNum) | CostOps0]
+ ;
+ CostOps1 = CostOps0
+ ),
+ find_cell_var_loads_for_field(AfterFlush, FieldVar, CostOps1, CostOps).
+
+%-----------------------------------------------------------------------------%
+
+:- func replicate_cost_op(int, int, cost_operation) = list(cost_node).
+
+replicate_cost_op(_StoreCost, LoadCost, cell_var_load(Segment)) =
+ make_cost_op_copies(LoadCost, cell_var_load(Segment)).
+replicate_cost_op(StoreCost, _LoadCost, cell_var_store) =
+ make_cost_op_copies(StoreCost, cell_var_store).
+
+:- func make_cost_op_copies(int, cost_operation) = list(cost_node).
+
+make_cost_op_copies(Cur, Op) =
+ ( Cur > 0 ->
+ [cost_node(Op, Cur) | make_cost_op_copies(Cur - 1, Op)]
+ ;
+ []
+ ).
+
+:- func replicate_benefit_op(int, int, benefit_operation) = list(benefit_node).
+
+replicate_benefit_op(_StoreCost, LoadCost, field_var_load(FieldVar)) =
+ make_benefit_op_copies(LoadCost, field_var_load(FieldVar)).
+replicate_benefit_op(StoreCost, _LoadCost, field_var_store(FieldVar)) =
+ make_benefit_op_copies(StoreCost, field_var_store(FieldVar)).
+
+:- func make_benefit_op_copies(int, benefit_operation) = list(benefit_node).
+
+make_benefit_op_copies(Cur, Op) =
+ ( Cur > 0 ->
+ [benefit_node(Op, Cur) | make_benefit_op_copies(Cur - 1, Op)]
+ ;
+ []
+ ).
+
+%-----------------------------------------------------------------------------%
+
+% Accumulate all the benefit nodes.
+
+:- pred gather_benefits(field_costs_benefits::in, set(benefit_node)::in,
+ set(benefit_node)::out) is det.
+
+gather_benefits(field_costs_benefits(_, _, FieldBenefits),
+ Benefits0, Benefits) :-
+ set__union(Benefits0, FieldBenefits, Benefits).
+
+% Accumulate all the cost nodes.
+
+:- pred gather_costs(field_costs_benefits::in, set(cost_node)::in,
+ set(cost_node)::out) is det.
+
+gather_costs(field_costs_benefits(_, FieldCosts, _), Costs0, Costs) :-
+ set__union(Costs0, FieldCosts, Costs).
+
+%-----------------------------------------------------------------------------%
+
+:- func create_graph(list(field_costs_benefits)) = stack_slot_graph.
+
+create_graph(CostsBenefits) = Graph :-
+ list__foldl2(create_graph_links, CostsBenefits,
+ map__init, CostToBenefitsMap, map__init, BenefitToCostsMap),
+ Graph = stack_slot_graph(CostToBenefitsMap, BenefitToCostsMap).
+
+:- pred create_graph_links(field_costs_benefits::in,
+ map(cost_node, set(benefit_node))::in,
+ map(cost_node, set(benefit_node))::out,
+ map(benefit_node, set(cost_node))::in,
+ map(benefit_node, set(cost_node))::out) is det.
+
+create_graph_links(field_costs_benefits(_FieldVar, Costs, Benefits),
+ CostToBenefitsMap0, CostToBenefitsMap,
+ BenefitToCostsMap0, BenefitToCostsMap) :-
+ list__foldl(add_cost_benefit_links(Benefits),
+ set__to_sorted_list(Costs),
+ CostToBenefitsMap0, CostToBenefitsMap),
+ list__foldl(add_benefit_cost_links(Costs),
+ set__to_sorted_list(Benefits),
+ BenefitToCostsMap0, BenefitToCostsMap).
+
+:- pred add_cost_benefit_links(set(benefit_node)::in, cost_node::in,
+ map(cost_node, set(benefit_node))::in,
+ map(cost_node, set(benefit_node))::out) is det.
+
+add_cost_benefit_links(Benefits, Cost, CostToBenefitsMap0, CostToBenefitsMap) :-
+ ( map__search(CostToBenefitsMap0, Cost, CostBenefits0) ->
+ set__union(CostBenefits0, Benefits, CostBenefits),
+ map__det_update(CostToBenefitsMap0, Cost, CostBenefits,
+ CostToBenefitsMap)
+ ;
+ map__det_insert(CostToBenefitsMap0, Cost, Benefits,
+ CostToBenefitsMap)
+ ).
+
+:- pred add_benefit_cost_links(set(cost_node)::in, benefit_node::in,
+ map(benefit_node, set(cost_node))::in,
+ map(benefit_node, set(cost_node))::out) is det.
+
+add_benefit_cost_links(Costs, Benefit, BenefitToCostsMap0, BenefitToCostsMap) :-
+ ( map__search(BenefitToCostsMap0, Benefit, BenefitCosts0) ->
+ set__union(BenefitCosts0, Costs, BenefitCosts),
+ map__det_update(BenefitToCostsMap0, Benefit, BenefitCosts,
+ BenefitToCostsMap)
+ ;
+ map__det_insert(BenefitToCostsMap0, Benefit, Costs,
+ BenefitToCostsMap)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- func maximal_matching(list(benefit_node), stack_slot_graph) = matching.
+
+maximal_matching(BenefitNodes, Graph) = Matching :-
+ Matching0 = matching(map__init, map__init),
+ maximize_matching(BenefitNodes, Graph, Matching0, Matching).
+
+:- pred maximize_matching(list(benefit_node)::in, stack_slot_graph::in,
+ matching::in, matching::out) is det.
+
+maximize_matching(BenefitNodes, Graph, Matching0, Matching) :-
+ ( Path = find_augmenting_path(BenefitNodes, Graph, Matching0) ->
+ Matching1 = update_matches(Path, Matching0),
+ maximize_matching(BenefitNodes, Graph, Matching1, Matching)
+ ;
+ Matching = Matching0
+ ).
+
+:- func update_matches(edge_list, matching) = matching.
+
+update_matches([], Matching0) = Matching0.
+update_matches([BenefitNode - CostNode | Path], Matching0) = Matching :-
+ Matching0 = matching(CostToBenefitMap0, BenefitToCostMap0),
+ map__set(CostToBenefitMap0, CostNode, BenefitNode, CostToBenefitMap1),
+ map__set(BenefitToCostMap0, BenefitNode, CostNode, BenefitToCostMap1),
+ Matching1 = matching(CostToBenefitMap1, BenefitToCostMap1),
+ Matching = update_matches(Path, Matching1).
+
+:- func find_augmenting_path(list(benefit_node), stack_slot_graph, matching)
+ = edge_list is semidet.
+
+find_augmenting_path(BenefitNodes, Graph, Matching) = Path :-
+ Matching = matching(_, MatchingBenefitToCost),
+ UnMatchedBenefitNodes = get_unmatched_benefit_nodes(BenefitNodes,
+ MatchingBenefitToCost),
+ Path = find_first_path_bf(UnMatchedBenefitNodes, Graph, Matching).
+
+%-----------------------------------------------------------------------------%
+
+% Breadth-first search for an augmenting path.
+
+% Build an initial queue of all the unmatched benefit nodes, with empty paths.
+% Take the first element of the queue and see what nodes are reachable
+% from there. If one is unmatched return the path, otherwise add these nodes
+% to the queue if they haven't been visited before.
+
+:- type edge_list == assoc_list(benefit_node, cost_node).
+
+:- type benefit_node_and_edge_list == pair(benefit_node, edge_list).
+
+:- func find_first_path_bf(list(benefit_node), stack_slot_graph, matching)
+ = edge_list is semidet.
+
+find_first_path_bf(BenefitNodes, Graph, Matching) = Path :-
+ Queue = initial_queue(BenefitNodes, queue__init),
+ Path = augpath_bf(Queue, BenefitNodes, Graph, Matching).
+
+:- func initial_queue(list(benefit_node), queue(benefit_node_and_edge_list))
+ = queue(benefit_node_and_edge_list).
+
+initial_queue([], Q) = Q.
+initial_queue([N | Ns], Q0) = Q :-
+ Q1 = queue__put(Q0, N - []),
+ Q = initial_queue(Ns, Q1).
+
+:- func augpath_bf(queue(benefit_node_and_edge_list), list(benefit_node),
+ stack_slot_graph, matching) = edge_list is semidet.
+
+augpath_bf(Queue0, Seen0, Graph, Matching) = Path :-
+ queue__get(Queue0, NodePath, Queue1),
+ NodePath = BenefitNode - Path0,
+ Graph = stack_slot_graph(_, BenefitToCostsMap),
+ map__lookup(BenefitToCostsMap, BenefitNode, AdjCostNodes),
+ Matching = matching(CostToBenefitMap, _),
+ CostMatches = map_adjs_to_matched_cost(
+ set__to_sorted_list(AdjCostNodes), CostToBenefitMap),
+ ( find_unmatched_cost(CostMatches) = UnmatchedCostNode ->
+ Path = [BenefitNode - UnmatchedCostNode | Path0]
+ ;
+ add_alternates(CostMatches, Seen0, Seen, BenefitNode, Path0,
+ Queue1, Queue2),
+ Path = augpath_bf(Queue2, Seen, Graph, Matching)
+ ).
+
+:- func find_unmatched_cost(assoc_list(cost_node, maybe(benefit_node)))
+ = cost_node is semidet.
+
+find_unmatched_cost([CostNode - MaybeBenefitNode | Matches]) = Unmatched :-
+ ( MaybeBenefitNode = no ->
+ Unmatched = CostNode
+ ;
+ Unmatched = find_unmatched_cost(Matches)
+ ).
+
+:- pred add_alternates(assoc_list(cost_node, maybe(benefit_node))::in,
+ list(benefit_node)::in, list(benefit_node)::out, benefit_node::in,
+ edge_list::in, queue(benefit_node_and_edge_list)::in,
+ queue(benefit_node_and_edge_list)::out) is det.
+
+% For each node CostNode adjacent to BenefitNode, we have determined whether
+% they are matched (that information is in MaybeAdjBenefitNode).
+% If AdjBenefitNode has not been visited before (it is not in Seen0),
+% we add it to the queue with the path extended by the last arc
+% (BenefitNode - CostNode)
+
+add_alternates([], Seen, Seen, _, _, Queue, Queue).
+add_alternates([CostNode - MaybeAdjBenefitNode | CostMatches], Seen0, Seen,
+ BenefitNode, Path, Queue0, Queue) :-
+ (
+ MaybeAdjBenefitNode = yes(AdjBenefitNode),
+ not list__member(AdjBenefitNode, Seen0)
+ ->
+ Seen1 = [AdjBenefitNode | Seen0],
+ Queue1 = queue__put(Queue0,
+ AdjBenefitNode - [BenefitNode - CostNode | Path])
+ ;
+ Seen1 = Seen0,
+ Queue1 = Queue0
+ ),
+ add_alternates(CostMatches, Seen1, Seen, BenefitNode, Path,
+ Queue1, Queue).
+
+%-----------------------------------------------------------------------------%
+
+% Find all the benefit nodes reachable from the cost nodes in the first
+% argument via alternating paths. The SelectedCostNodes are not matched,
+% so first we look for matched benefit nodes adjacent to them, since those
+% nodes are reachable. We then look at the cost nodes matched to those benefit
+% nodes, since the benefit nodes reachable from there are also reachable from
+% the original cost nodes.
+%
+% To ensure termination, we follow the matched link from a benefit node
+% only when that benefit node is first put into the reachable set.
+
+:- func reachable_by_alternating_path(list(cost_node), stack_slot_graph,
+ matching) = set(benefit_node).
+
+reachable_by_alternating_path(SelectedCostNodes, Graph, Matching)
+ = ReachableBenefitNodes :-
+ reachable_by_alternating_path(SelectedCostNodes, Graph, Matching,
+ set__init, ReachableBenefitNodes).
+
+:- pred reachable_by_alternating_path(list(cost_node)::in,
+ stack_slot_graph::in, matching::in, set(benefit_node)::in,
+ set(benefit_node)::out) is det.
+
+reachable_by_alternating_path(SelectedCostNodes, Graph, Matching,
+ BenefitNodes0, BenefitNodes) :-
+ ( SelectedCostNodes = [] ->
+ BenefitNodes = BenefitNodes0
+ ;
+ Graph = stack_slot_graph(CostToBenefitsMap, _),
+ list__foldl(adjacents(CostToBenefitsMap), SelectedCostNodes,
+ set__init, AdjBenefitNodes),
+ set__union(AdjBenefitNodes, BenefitNodes0, BenefitNodes1),
+ % XXX should reverse the first two args
+ set__difference(BenefitNodes0, AdjBenefitNodes,
+ NewBenefitNodes),
+ set__to_sorted_list(NewBenefitNodes, NewBenefitNodeList),
+ Matching = matching(_, BenefitToCostMap),
+ LinkedCostNodes = list__map(map__lookup(BenefitToCostMap),
+ NewBenefitNodeList),
+ reachable_by_alternating_path(LinkedCostNodes, Graph, Matching,
+ BenefitNodes1, BenefitNodes)
+ ).
+
+:- pred adjacents(map(cost_node, set(benefit_node))::in, cost_node::in,
+ set(benefit_node)::in, set(benefit_node)::out) is det.
+
+adjacents(CostToBenefitsMap, CostNode, BenefitNodes0, BenefitNodes) :-
+ map__lookup(CostToBenefitsMap, CostNode, AdjBenefitNodes),
+ set__union(BenefitNodes0, AdjBenefitNodes, BenefitNodes).
+
+%-----------------------------------------------------------------------------%
+
+% :- pragma memo(map_adjs_to_matched_cost/2).
+
+:- func map_adjs_to_matched_cost(list(cost_node),
+ map(cost_node, benefit_node))
+ = assoc_list(cost_node, maybe(benefit_node)).
+
+map_adjs_to_matched_cost(AdjCostNodes, CostToBenefitMap) = CostMatches :-
+ CostMatches = list__map(adj_to_matched_cost(CostToBenefitMap),
+ AdjCostNodes).
+
+:- func adj_to_matched_cost(map(cost_node, benefit_node), cost_node) =
+ pair(cost_node, maybe(benefit_node)).
+
+adj_to_matched_cost(CostToBenefitMap, CostNode) = Match :-
+ ( map__search(CostToBenefitMap, CostNode, BenefitNode) ->
+ Match = CostNode - yes(BenefitNode)
+ ;
+ Match = CostNode - no
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- func compute_via_cell_vars(list(field_costs_benefits), set(benefit_node))
+ = set(prog_var).
+
+compute_via_cell_vars([], _MarkedBenefits) = set__init.
+compute_via_cell_vars([FieldCostsBenefits | FieldsCostsBenefits],
+ MarkedBenefits) = ViaCellVars :-
+ ViaCellVars1 = compute_via_cell_vars(FieldsCostsBenefits,
+ MarkedBenefits),
+ FieldCostsBenefits = field_costs_benefits(FieldVar, _, FieldBenefits),
+ set__intersect(FieldBenefits, MarkedBenefits, MarkedFieldBenefits),
+ ( set__empty(MarkedFieldBenefits) ->
+ set__insert(ViaCellVars1, FieldVar, ViaCellVars)
+ ; set__equal(MarkedFieldBenefits, FieldBenefits) ->
+ ViaCellVars = ViaCellVars1
+ ;
+ error("compute_via_cell_vars: theorem violation: intersection neither empty nor full")
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- func get_unmatched_benefit_nodes(list(benefit_node),
+ map(benefit_node, cost_node)) = list(benefit_node).
+
+get_unmatched_benefit_nodes([], _) = [].
+get_unmatched_benefit_nodes([Node | Nodes], MatchingBC) = UnmatchedNodes :-
+ UnmatchedNodes1 = get_unmatched_benefit_nodes(Nodes, MatchingBC),
+ ( map__search(MatchingBC, Node, _Match) ->
+ UnmatchedNodes = UnmatchedNodes1
+ ;
+ UnmatchedNodes = [Node | UnmatchedNodes1]
+ ).
+
+:- func get_unmatched_cost_nodes(list(cost_node),
+ map(cost_node, benefit_node)) = list(cost_node).
+
+get_unmatched_cost_nodes([], _) = [].
+get_unmatched_cost_nodes([Node | Nodes], MatchingCB) = UnmatchedNodes :-
+ UnmatchedNodes1 = get_unmatched_cost_nodes(Nodes, MatchingCB),
+ ( map__search(MatchingCB, Node, _Match) ->
+ UnmatchedNodes = UnmatchedNodes1
+ ;
+ UnmatchedNodes = [Node | UnmatchedNodes1]
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- pred dump_results(prog_var::in, set(prog_var)::in, list(prog_var)::in,
+ set(prog_var)::in, bool::in, set(prog_var)::in,
+ assoc_list(int, set(prog_var))::in,
+ list(benefit_node)::in, list(benefit_operation)::in,
+ list(cost_node)::in, list(cost_operation)::in,
+ io__state::di, io__state::uo) is det.
+
+dump_results(CellVar, CandidateFieldVars, OccurringCandidateFieldVarList,
+ ViaCellOccurringVars, Nullified, BeforeFlush, AfterFlush,
+ BenefitNodes, BenefitOps, CostNodes, CostOps) -->
+ { term__var_to_int(CellVar, CellVarInt) },
+ { set__to_sorted_list(CandidateFieldVars, CandidateFieldVarList) },
+ { set__to_sorted_list(ViaCellOccurringVars, ViaCellVarList) },
+ { set__to_sorted_list(BeforeFlush, BeforeFlushList) },
+ { list__map(term__var_to_int, CandidateFieldVarList,
+ CandidateFieldVarInts) },
+ { list__map(term__var_to_int, OccurringCandidateFieldVarList,
+ OccurringCandidateFieldVarInts) },
+ { list__map(term__var_to_int, ViaCellVarList, ViaCellVarInts) },
+ { list__map(term__var_to_int, BeforeFlushList, BeforeFlushInts) },
+ io__write_string("%\n% FIND_VIA_CELL_VARS "),
+ io__write_int(CellVarInt),
+ io__write_string(" => f("),
+ io__write_list(CandidateFieldVarInts, ", ", io__write_int),
+ io__write_string(")\n"),
+ io__write_string("% occurring ["),
+ io__write_list(OccurringCandidateFieldVarInts, ", ", io__write_int),
+ io__write_string("]\n"),
+ io__write_string("% via cell ["),
+ io__write_list(ViaCellVarInts, ", ", io__write_int),
+ io__write_string("]"),
+ (
+ { Nullified = no },
+ io__write_string("\n")
+ ;
+ { Nullified = yes },
+ io__write_string(" nullified\n")
+ ),
+ io__write_string("% before flush, segment 1: ["),
+ io__write_list(BeforeFlushInts, ", ", io__write_int),
+ io__write_string("]\n"),
+ list__foldl(dump_after_flush, AfterFlush),
+ io__write_string("% realized benefits: "),
+ io__write_int(list__length(BenefitOps)),
+ io__write_string(" ops, "),
+ io__write_int(list__length(BenefitNodes)),
+ io__write_string(" nodes:\n"),
+ io__write_string("% "),
+ io__write(BenefitOps),
+ io__write_string("\n"),
+ io__write_string("% realized costs: "),
+ io__write_int(list__length(CostOps)),
+ io__write_string(" ops, "),
+ io__write_int(list__length(CostNodes)),
+ io__write_string(" nodes:\n"),
+ io__write_string("% "),
+ io__write(CostOps),
+ io__write_string("\n%\n").
+
+:- pred dump_after_flush(pair(int, set(prog_var))::in,
+ io__state::di, io__state::uo) is det.
+
+dump_after_flush(SegmentNum - SegmentVars) -->
+ { set__to_sorted_list(SegmentVars, SegmentVarList) },
+ { list__map(term__var_to_int, SegmentVarList, SegmentVarInts) },
+ io__write_string("% after flush, segment "),
+ io__write_int(SegmentNum),
+ io__write_string(": ["),
+ io__write_list(SegmentVarInts, ", ", io__write_int),
+ io__write_string("]\n").
+
+%-----------------------------------------------------------------------------%
+
+:- pred realized_costs_benefits(set(prog_var)::in, field_costs_benefits::in)
+ is semidet.
+
+realized_costs_benefits(ViaCellOccurringVars, FieldCostsBenefits) :-
+ FieldCostsBenefits = field_costs_benefits(FieldVar, _, _),
+ set__member(FieldVar, ViaCellOccurringVars).
+
+:- func project_benefit_op(benefit_node) = benefit_operation.
+
+project_benefit_op(benefit_node(BenefitOp, _CopyNum)) = BenefitOp.
+
+:- func project_cost_op(cost_node) = cost_operation.
+
+project_cost_op(cost_node(CostOp, _CopyNum)) = CostOp.
+
+%-----------------------------------------------------------------------------%
Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.238
diff -u -b -r1.238 mercury_compile.m
--- compiler/mercury_compile.m 8 Mar 2002 04:03:23 -0000 1.238
+++ compiler/mercury_compile.m 8 Mar 2002 04:04:32 -0000
@@ -43,8 +43,9 @@
:- import_module deep_profiling.
% the LLDS back-end
-:- import_module saved_vars, liveness.
-:- import_module follow_code, live_vars, arg_info, store_alloc, goal_path.
+:- import_module saved_vars, stack_opt, liveness.
+:- import_module follow_code, stack_alloc.
+:- import_module arg_info, store_alloc, goal_path.
:- import_module code_gen, optimize, foreign, export.
:- import_module base_typeclass_info.
:- import_module llds_common, transform_llds, llds_out.
@@ -1883,20 +1884,23 @@
globals__io_lookup_bool_option(verbose, Verbose),
globals__io_lookup_bool_option(statistics, Stats),
- mercury_compile__maybe_followcode(HLDS51, Verbose, Stats, HLDS52),
- mercury_compile__maybe_dump_hlds(HLDS52, "52", "followcode"),
+ mercury_compile__maybe_saved_vars(HLDS51, Verbose, Stats, HLDS53),
+ mercury_compile__maybe_dump_hlds(HLDS53, "53", "saved_vars_const"),
- mercury_compile__simplify(HLDS52, no, yes, Verbose, Stats,
- process_all_nonimported_nonaditi_procs, HLDS53),
- mercury_compile__maybe_dump_hlds(HLDS53, "53", "simplify2"),
+ mercury_compile__maybe_stack_opt(HLDS53, Verbose, Stats, HLDS55),
+ mercury_compile__maybe_dump_hlds(HLDS55, "55", "saved_vars_cell"),
- mercury_compile__maybe_saved_vars(HLDS53, Verbose, Stats, HLDS56),
- mercury_compile__maybe_dump_hlds(HLDS56, "56", "savedvars"),
+ mercury_compile__maybe_followcode(HLDS55, Verbose, Stats, HLDS57),
+ mercury_compile__maybe_dump_hlds(HLDS57, "57", "followcode"),
- mercury_compile__compute_liveness(HLDS56, Verbose, Stats, HLDS59),
- mercury_compile__maybe_dump_hlds(HLDS59, "59", "liveness"),
+ mercury_compile__simplify(HLDS57, no, yes, Verbose, Stats,
+ process_all_nonimported_nonaditi_procs, HLDS59),
+ mercury_compile__maybe_dump_hlds(HLDS59, "59", "simplify2"),
- mercury_compile__compute_stack_vars(HLDS59, Verbose, Stats, HLDS65),
+ mercury_compile__compute_liveness(HLDS59, Verbose, Stats, HLDS61),
+ mercury_compile__maybe_dump_hlds(HLDS61, "61", "liveness"),
+
+ mercury_compile__compute_stack_vars(HLDS61, Verbose, Stats, HLDS65),
mercury_compile__maybe_dump_hlds(HLDS65, "65", "stackvars"),
mercury_compile__allocate_store_map(HLDS65, Verbose, Stats, HLDS68),
@@ -2036,69 +2040,91 @@
in, out, out, di, uo) is det.
mercury_compile__backend_pass_by_preds_4(PredInfo, ProcInfo0, ProcId, PredId,
- ModuleInfo0, ModuleInfo, GlobalData0, GlobalData, Proc) -->
+ ModuleInfo0, ModuleInfo, GlobalData0, GlobalData, ProcCode) -->
{ module_info_globals(ModuleInfo0, Globals) },
+ { globals__lookup_bool_option(Globals, optimize_saved_vars_const,
+ SavedVarsConst) },
+ (
+ { SavedVarsConst = yes },
+ saved_vars_proc(PredId, ProcId, ProcInfo0, ProcInfoSavedConst,
+ ModuleInfo0, ModuleInfoSavedConst)
+ ;
+ { SavedVarsConst = no },
+ { ProcInfoSavedConst = ProcInfo0 },
+ { ModuleInfoSavedConst = ModuleInfo0 }
+ ),
+ { globals__lookup_bool_option(Globals, optimize_saved_vars_cell,
+ SavedVarsCell) },
+ (
+ { SavedVarsCell = yes },
+ stack_opt_cell(PredId, ProcId,
+ ProcInfoSavedConst, ProcInfoSavedCell,
+ ModuleInfoSavedConst, ModuleInfoSavedCell)
+ ;
+ { SavedVarsCell = no },
+ { ProcInfoSavedCell = ProcInfoSavedConst },
+ { ModuleInfoSavedCell = ModuleInfoSavedConst }
+ ),
{ globals__lookup_bool_option(Globals, follow_code, FollowCode) },
{ globals__lookup_bool_option(Globals, prev_code, PrevCode) },
( { FollowCode = yes ; PrevCode = yes } ->
- { move_follow_code_in_proc(PredInfo, ProcInfo0, ProcInfo1,
- ModuleInfo0, ModuleInfo1) }
+ { move_follow_code_in_proc(PredInfo,
+ ProcInfoSavedCell, ProcInfoFollowCode,
+ ModuleInfoSavedCell, ModuleInfoFollow) }
;
- { ProcInfo1 = ProcInfo0 },
- { ModuleInfo1 = ModuleInfo0 }
+ { ProcInfoFollowCode = ProcInfoSavedCell },
+ { ModuleInfoFollow = ModuleInfoSavedCell }
),
{ simplify__find_simplifications(no, Globals, Simplifications) },
simplify__proc([do_once | Simplifications], PredId, ProcId,
- ModuleInfo1, ModuleInfo2, ProcInfo1, ProcInfo2),
- { globals__lookup_bool_option(Globals, optimize_saved_vars,
- SavedVars) },
- ( { SavedVars = yes } ->
- saved_vars_proc(PredId, ProcId, ProcInfo2, ProcInfo3,
- ModuleInfo2, ModuleInfo3)
- ;
- { ProcInfo3 = ProcInfo2 },
- { ModuleInfo3 = ModuleInfo2 }
- ),
+ ModuleInfoFollow, ModuleInfoSimplify,
+ ProcInfoFollowCode, ProcInfoSimplify),
write_proc_progress_message("% Computing liveness in ", PredId, ProcId,
- ModuleInfo3),
- detect_liveness_proc(PredId, ProcId, ModuleInfo3,
- ProcInfo3, ProcInfo4),
+ ModuleInfoSimplify),
+ detect_liveness_proc(PredId, ProcId, ModuleInfoSimplify,
+ ProcInfoSimplify, ProcInfoLiveness),
write_proc_progress_message("% Allocating stack slots in ", PredId,
- ProcId, ModuleInfo3),
- { allocate_stack_slots_in_proc(ProcInfo4, PredId, ModuleInfo3,
- ProcInfo5) },
+ ProcId, ModuleInfoSimplify),
+ allocate_stack_slots_in_proc(PredId, ProcId, ModuleInfoSimplify,
+ ProcInfoLiveness, ProcInfoStackSlot),
write_proc_progress_message(
"% Allocating storage locations for live vars in ",
- PredId, ProcId, ModuleInfo3),
- { store_alloc_in_proc(ProcInfo5, PredId, ModuleInfo3, ProcInfo6) },
+ PredId, ProcId, ModuleInfoSimplify),
+ { allocate_store_maps(final_allocation, ProcInfoStackSlot,
+ PredId, ModuleInfoSimplify, ProcInfoStoreAlloc) },
globals__io_get_trace_level(TraceLevel),
( { trace_level_is_none(TraceLevel) = no } ->
write_proc_progress_message(
"% Calculating goal paths in ",
- PredId, ProcId, ModuleInfo3),
- { goal_path__fill_slots(ProcInfo6, ModuleInfo3, ProcInfo) }
+ PredId, ProcId, ModuleInfoSimplify),
+ { goal_path__fill_slots(ProcInfoStoreAlloc, ModuleInfoSimplify,
+ ProcInfo) }
;
- { ProcInfo = ProcInfo6 }
+ { ProcInfo = ProcInfoStoreAlloc }
),
write_proc_progress_message(
"% Generating low-level (LLDS) code for ",
- PredId, ProcId, ModuleInfo3),
- { module_info_get_cell_counter(ModuleInfo3, CellCounter0) },
- { generate_proc_code(PredInfo, ProcInfo, ProcId, PredId, ModuleInfo3,
- GlobalData0, GlobalData1, CellCounter0, CellCounter, Proc0) },
+ PredId, ProcId, ModuleInfoSimplify),
+ { module_info_get_cell_counter(ModuleInfoSimplify, CellCounter0) },
+ { generate_proc_code(PredInfo, ProcInfo, ProcId, PredId,
+ ModuleInfoSimplify, GlobalData0, GlobalData1,
+ CellCounter0, CellCounter, ProcCode0) },
{ globals__lookup_bool_option(Globals, optimize, Optimize) },
- ( { Optimize = yes } ->
- optimize__proc(Proc0, GlobalData1, Proc)
+ (
+ { Optimize = yes },
+ optimize__proc(ProcCode0, GlobalData1, ProcCode)
;
- { Proc = Proc0 }
+ { Optimize = no },
+ { ProcCode = ProcCode0 }
),
- { Proc = c_procedure(_, _, PredProcId, Instructions, _, _, _) },
+ { ProcCode = c_procedure(_, _, PredProcId, Instructions, _, _, _) },
write_proc_progress_message(
"% Generating call continuation information for ",
- PredId, ProcId, ModuleInfo3),
+ PredId, ProcId, ModuleInfoSimplify),
{ continuation_info__maybe_process_proc_llds(Instructions, PredProcId,
- ModuleInfo3, GlobalData1, GlobalData) },
- { module_info_set_cell_counter(ModuleInfo3, CellCounter, ModuleInfo) }.
+ ModuleInfoSimplify, GlobalData1, GlobalData) },
+ { module_info_set_cell_counter(ModuleInfoSimplify, CellCounter,
+ ModuleInfo) }.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -2837,9 +2863,10 @@
is det.
mercury_compile__maybe_saved_vars(HLDS0, Verbose, Stats, HLDS) -->
- globals__io_lookup_bool_option(optimize_saved_vars, SavedVars),
+ globals__io_lookup_bool_option(optimize_saved_vars_const, SavedVars),
( { SavedVars = yes } ->
- maybe_write_string(Verbose, "% Reordering to minimize variable saves...\n"),
+ maybe_write_string(Verbose,
+ "% Minimizing variable saves using constants...\n"),
maybe_flush_output(Verbose),
process_all_nonimported_procs(update_module_io(
saved_vars_proc), HLDS0, HLDS),
@@ -2849,6 +2876,23 @@
{ HLDS0 = HLDS }
).
+:- pred mercury_compile__maybe_stack_opt(module_info::in, bool::in, bool::in,
+ module_info::out, io__state::di, io__state::uo) is det.
+
+mercury_compile__maybe_stack_opt(HLDS0, Verbose, Stats, HLDS) -->
+ globals__io_lookup_bool_option(optimize_saved_vars_cell, SavedVars),
+ ( { SavedVars = yes } ->
+ maybe_write_string(Verbose,
+ "% Minimizing variable saves using cells...\n"),
+ maybe_flush_output(Verbose),
+ process_all_nonimported_procs(update_module_io(
+ stack_opt_cell), HLDS0, HLDS),
+ maybe_write_string(Verbose, "% done.\n"),
+ maybe_report_stats(Stats)
+ ;
+ { HLDS0 = HLDS }
+ ).
+
:- pred mercury_compile__maybe_followcode(module_info, bool, bool,
module_info, io__state, io__state).
:- mode mercury_compile__maybe_followcode(in, in, in, out, di, uo)
@@ -2889,7 +2933,7 @@
maybe_write_string(Verbose, "% Computing stack vars..."),
maybe_flush_output(Verbose),
process_all_nonimported_nonaditi_procs(
- update_proc_predid(allocate_stack_slots_in_proc),
+ update_proc_io(allocate_stack_slots_in_proc),
HLDS0, HLDS),
maybe_write_string(Verbose, " done.\n"),
maybe_report_stats(Stats).
@@ -2902,7 +2946,7 @@
maybe_write_string(Verbose, "% Allocating store map..."),
maybe_flush_output(Verbose),
process_all_nonimported_nonaditi_procs(
- update_proc_predid(store_alloc_in_proc),
+ update_proc_predid(allocate_store_maps(final_allocation)),
HLDS0, HLDS),
maybe_write_string(Verbose, " done.\n"),
maybe_report_stats(Stats).
Index: compiler/middle_rec.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/middle_rec.m,v
retrieving revision 1.87
diff -u -b -r1.87 middle_rec.m
--- compiler/middle_rec.m 24 Apr 2001 03:58:59 -0000 1.87
+++ compiler/middle_rec.m 14 Dec 2001 02:21:44 -0000
@@ -25,7 +25,8 @@
:- implementation.
-:- import_module builtin_ops, hlds_module, hlds_data, prog_data, prog_out.
+:- import_module builtin_ops, hlds_module, hlds_data, hlds_llds.
+:- import_module prog_data, prog_out.
:- import_module code_gen, unify_gen, code_util, code_aux, opt_util.
:- import_module code_model.
@@ -37,7 +38,7 @@
middle_rec__match_and_generate(Goal, Instrs, CodeInfo0, CodeInfo) :-
Goal = GoalExpr - GoalInfo,
(
- GoalExpr = switch(Var, cannot_fail, [Case1, Case2], SM),
+ GoalExpr = switch(Var, cannot_fail, [Case1, Case2]),
Case1 = case(ConsId1, Goal1),
Case2 = case(ConsId2, Goal2),
(
@@ -46,19 +47,19 @@
CodeInfo0, _)
->
middle_rec__generate_switch(Var, ConsId1, Goal1, Goal2,
- SM, GoalInfo, Instrs, CodeInfo0, CodeInfo)
+ GoalInfo, Instrs, CodeInfo0, CodeInfo)
;
code_aux__contains_only_builtins(Goal2),
code_aux__contains_simple_recursive_call(Goal1,
CodeInfo0, _)
->
middle_rec__generate_switch(Var, ConsId2, Goal2, Goal1,
- SM, GoalInfo, Instrs, CodeInfo0, CodeInfo)
+ GoalInfo, Instrs, CodeInfo0, CodeInfo)
;
fail
)
;
- GoalExpr = if_then_else(Vars, Cond, Then, Else, SM),
+ GoalExpr = if_then_else(Vars, Cond, Then, Else),
(
code_aux__contains_only_builtins(Cond),
code_aux__contains_only_builtins(Then),
@@ -67,7 +68,7 @@
->
semidet_fail,
middle_rec__generate_ite(Vars, Cond, Then, Else,
- in_else, SM, GoalInfo, Instrs,
+ in_else, GoalInfo, Instrs,
CodeInfo0, CodeInfo)
;
code_aux__contains_only_builtins(Cond),
@@ -77,7 +78,7 @@
->
semidet_fail,
middle_rec__generate_ite(Vars, Cond, Then, Else,
- in_then, SM, GoalInfo, Instrs,
+ in_then, GoalInfo, Instrs,
CodeInfo0, CodeInfo)
;
fail
@@ -89,12 +90,12 @@
%---------------------------------------------------------------------------%
:- pred middle_rec__generate_ite(list(prog_var), hlds_goal, hlds_goal,
- hlds_goal, ite_rec, store_map, hlds_goal_info,
+ hlds_goal, ite_rec, hlds_goal_info,
code_tree, code_info, code_info).
-:- mode middle_rec__generate_ite(in, in, in, in, in, in, in, out, in, out)
+:- mode middle_rec__generate_ite(in, in, in, in, in, in, out, in, out)
is det.
-middle_rec__generate_ite(_Vars, _Cond, _Then, _Else, _Rec, _IteGoalInfo, _SM,
+middle_rec__generate_ite(_Vars, _Cond, _Then, _Else, _Rec, _IteGoalInfo,
Instrs) -->
( { semidet_fail } ->
{ Instrs = empty }
@@ -105,12 +106,12 @@
%---------------------------------------------------------------------------%
:- pred middle_rec__generate_switch(prog_var, cons_id, hlds_goal, hlds_goal,
- store_map, hlds_goal_info, code_tree, code_info, code_info).
-:- mode middle_rec__generate_switch(in, in, in, in, in, in, out, in, out)
+ hlds_goal_info, code_tree, code_info, code_info).
+:- mode middle_rec__generate_switch(in, in, in, in, in, out, in, out)
is semidet.
-middle_rec__generate_switch(Var, BaseConsId, Base, Recursive, StoreMap,
- SwitchGoalInfo, Instrs) -->
+middle_rec__generate_switch(Var, BaseConsId, Base, Recursive, SwitchGoalInfo,
+ Instrs) -->
code_info__get_stack_slots(StackSlots),
code_info__get_varset(VarSet),
{ code_aux__explain_stack_slots(StackSlots, VarSet, SlotsComment) },
@@ -126,6 +127,7 @@
{ tree__flatten(EntryTestCode, EntryTestListList) },
{ list__condense(EntryTestListList, EntryTestList) },
+ { goal_info_get_store_map(SwitchGoalInfo, StoreMap) },
code_info__remember_position(BranchStart),
code_gen__generate_goal(model_det, Base, BaseGoalCode),
code_info__generate_branch_end(StoreMap, no, MaybeEnd1,
@@ -190,11 +192,7 @@
label(Loop2Label))
- "test on upward loop"]
;
- predicate_module(ModuleInfo, PredId, ModuleName),
- prog_out__sym_name_to_string(ModuleName, ModuleNameString),
- predicate_name(ModuleInfo, PredId, PredName),
- string__append_list([ModuleNameString, ":", PredName],
- PushMsg),
+ PushMsg = code_gen__push_msg(ModuleInfo, PredId, ProcId),
MaybeIncrSp = [incr_sp(FrameSize, PushMsg) - ""],
MaybeDecrSp = [decr_sp(FrameSize) - ""],
InitAuxReg = [assign(AuxReg, lval(sp))
Index: compiler/ml_code_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_code_gen.m,v
retrieving revision 1.110
diff -u -b -r1.110 ml_code_gen.m
--- compiler/ml_code_gen.m 5 Mar 2002 10:59:19 -0000 1.110
+++ compiler/ml_code_gen.m 8 Mar 2002 04:04:34 -0000
@@ -1978,7 +1978,7 @@
ml_gen_info, ml_gen_info).
:- mode ml_gen_goal_expr(in, in, in, out, out, in, out) is det.
-ml_gen_goal_expr(switch(Var, CanFail, CasesList, _), CodeModel, Context,
+ml_gen_goal_expr(switch(Var, CanFail, CasesList), CodeModel, Context,
MLDS_Decls, MLDS_Statements) -->
ml_gen_switch(Var, CanFail, CasesList, CodeModel, Context,
MLDS_Decls, MLDS_Statements).
@@ -1987,7 +1987,7 @@
MLDS_Decls, MLDS_Statements) -->
ml_gen_commit(Goal, CodeModel, Context, MLDS_Decls, MLDS_Statements).
-ml_gen_goal_expr(if_then_else(_Vars, Cond, Then, Else, _),
+ml_gen_goal_expr(if_then_else(_Vars, Cond, Then, Else),
CodeModel, Context, MLDS_Decls, MLDS_Statements) -->
ml_gen_ite(CodeModel, Cond, Then, Else, Context,
MLDS_Decls, MLDS_Statements).
@@ -2000,11 +2000,11 @@
MLDS_Decls, MLDS_Statements) -->
ml_gen_conj(Goals, CodeModel, Context, MLDS_Decls, MLDS_Statements).
-ml_gen_goal_expr(disj(Goals, _), CodeModel, Context,
+ml_gen_goal_expr(disj(Goals), CodeModel, Context,
MLDS_Decls, MLDS_Statements) -->
ml_gen_disj(Goals, CodeModel, Context, MLDS_Decls, MLDS_Statements).
-ml_gen_goal_expr(par_conj(Goals, _SM), CodeModel, Context,
+ml_gen_goal_expr(par_conj(Goals), CodeModel, Context,
MLDS_Decls, MLDS_Statements) -->
%
% XXX currently we treat parallel conjunction the same as
Index: compiler/mode_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mode_util.m,v
retrieving revision 1.140
diff -u -b -r1.140 mode_util.m
--- compiler/mode_util.m 7 Mar 2002 08:30:07 -0000 1.140
+++ compiler/mode_util.m 8 Mar 2002 04:04:43 -0000
@@ -1307,9 +1307,8 @@
recompute_info, recompute_info).
:- mode recompute_instmap_delta_2(in, in, in, out, in, in, out, in, out) is det.
-recompute_instmap_delta_2(Atomic, switch(Var, Det, Cases0, SM), GoalInfo,
- switch(Var, Det, Cases, SM), VarTypes, InstMap, InstMapDelta)
- -->
+recompute_instmap_delta_2(Atomic, switch(Var, Det, Cases0), GoalInfo,
+ switch(Var, Det, Cases), VarTypes, InstMap, InstMapDelta) -->
{ goal_info_get_nonlocals(GoalInfo, NonLocals) },
recompute_instmap_delta_cases(Atomic, Var, Cases0, Cases,
VarTypes, InstMap, NonLocals, InstMapDelta).
@@ -1319,13 +1318,13 @@
recompute_instmap_delta_conj(Atomic, Goals0, Goals,
VarTypes, InstMap, InstMapDelta).
-recompute_instmap_delta_2(Atomic, par_conj(Goals0, SM), GoalInfo,
- par_conj(Goals, SM), VarTypes, InstMap, InstMapDelta) -->
+recompute_instmap_delta_2(Atomic, par_conj(Goals0), GoalInfo,
+ par_conj(Goals), VarTypes, InstMap, InstMapDelta) -->
{ goal_info_get_nonlocals(GoalInfo, NonLocals) },
recompute_instmap_delta_par_conj(Atomic, Goals0, Goals,
VarTypes, InstMap, NonLocals, InstMapDelta).
-recompute_instmap_delta_2(Atomic, disj(Goals0, SM), GoalInfo, disj(Goals, SM),
+recompute_instmap_delta_2(Atomic, disj(Goals0), GoalInfo, disj(Goals),
VarTypes, InstMap, InstMapDelta) -->
{ goal_info_get_nonlocals(GoalInfo, NonLocals) },
recompute_instmap_delta_disj(Atomic, Goals0, Goals,
@@ -1336,8 +1335,8 @@
{ instmap_delta_init_reachable(InstMapDelta) },
recompute_instmap_delta_1(Atomic, Goal0, Goal, VarTypes, InstMap, _).
-recompute_instmap_delta_2(Atomic, if_then_else(Vars, A0, B0, C0, SM), GoalInfo,
- if_then_else(Vars, A, B, C, SM), VarTypes, InstMap0,
+recompute_instmap_delta_2(Atomic, if_then_else(Vars, A0, B0, C0), GoalInfo,
+ if_then_else(Vars, A, B, C), VarTypes, InstMap0,
InstMapDelta) -->
recompute_instmap_delta_1(Atomic, A0, A, VarTypes, InstMap0,
InstMapDelta1),
Index: compiler/modecheck_unify.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/modecheck_unify.m,v
retrieving revision 1.48
diff -u -b -r1.48 modecheck_unify.m
--- compiler/modecheck_unify.m 7 Mar 2002 08:30:09 -0000 1.48
+++ compiler/modecheck_unify.m 8 Mar 2002 04:04:44 -0000
@@ -565,8 +565,7 @@
%,
% Unifying two preds is not erroneous as far as the
% mode checker is concerned, but a mode _error_.
- map__init(Empty),
- Goal = disj([], Empty),
+ Goal = disj([]),
FinalModeInfo = ModeInfo
;
Functor = functor(ConsId, ArgVars),
@@ -823,8 +822,7 @@
%
% Unifying two preds is not erroneous as far as the
% mode checker is concerned, but a mode _error_.
- map__init(Empty),
- Unify = disj([], Empty)
+ Unify = disj([])
;
Unify = unify(X, var(Y), ModeOfX - ModeOfY, Unification,
UnifyContext)
Index: compiler/modes.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/modes.m,v
retrieving revision 1.255
diff -u -b -r1.255 modes.m
--- compiler/modes.m 7 Mar 2002 08:30:09 -0000 1.255
+++ compiler/modes.m 8 Mar 2002 04:04:45 -0000
@@ -1096,17 +1096,17 @@
% empty.
% A stack of these structures is maintained to handle nested parallel
% conjunctions properly.
-modecheck_goal_expr(par_conj(List0, SM), GoalInfo0, par_conj(List, SM)) -->
+modecheck_goal_expr(par_conj(List0), GoalInfo0, par_conj(List)) -->
mode_checkpoint(enter, "par_conj"),
{ goal_info_get_nonlocals(GoalInfo0, NonLocals) },
modecheck_par_conj_list(List0, List, NonLocals, InstMapNonlocalList),
instmap__unify(NonLocals, InstMapNonlocalList),
mode_checkpoint(exit, "par_conj").
-modecheck_goal_expr(disj(List0, SM), GoalInfo0, Goal) -->
+modecheck_goal_expr(disj(List0), GoalInfo0, Goal) -->
mode_checkpoint(enter, "disj"),
( { List0 = [] } -> % for efficiency, optimize common case
- { Goal = disj(List0, SM) },
+ { Goal = disj(List0) },
{ instmap__init_unreachable(InstMap) },
mode_info_set_instmap(InstMap)
;
@@ -1117,7 +1117,7 @@
),
mode_checkpoint(exit, "disj").
-modecheck_goal_expr(if_then_else(Vs, A0, B0, C0, SM), GoalInfo0, Goal) -->
+modecheck_goal_expr(if_then_else(Vs, A0, B0, C0), GoalInfo0, Goal) -->
mode_checkpoint(enter, "if-then-else"),
{ goal_info_get_nonlocals(GoalInfo0, NonLocals) },
{ goal_get_nonlocals(B0, B_Vars) },
@@ -1147,7 +1147,7 @@
mode_info_dcg_get_instmap(InstMapC),
mode_info_set_instmap(InstMap0),
instmap__merge(NonLocals, [InstMapB, InstMapC], if_then_else),
- { Goal = if_then_else(Vs, A, B, C, SM) },
+ { Goal = if_then_else(Vs, A, B, C) },
mode_checkpoint(exit, "if-then-else").
modecheck_goal_expr(not(A0), GoalInfo0, not(A)) -->
@@ -1253,8 +1253,8 @@
mode_info_unset_call_context,
mode_checkpoint(exit, "unify").
-modecheck_goal_expr(switch(Var, CanFail, Cases0, SM), GoalInfo0,
- switch(Var, CanFail, Cases, SM)) -->
+modecheck_goal_expr(switch(Var, CanFail, Cases0), GoalInfo0,
+ switch(Var, CanFail, Cases)) -->
mode_checkpoint(enter, "switch"),
( { Cases0 = [] } ->
{ Cases = [] },
Index: compiler/optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/optimize.m,v
retrieving revision 1.28
diff -u -b -r1.28 optimize.m
--- compiler/optimize.m 31 May 2001 05:59:50 -0000 1.28
+++ compiler/optimize.m 8 Nov 2001 00:19:54 -0000
@@ -364,8 +364,10 @@
[]
),
globals__io_lookup_int_option(num_real_r_regs, NumRealRRegs),
+ globals__io_lookup_int_option(local_var_access_threshold,
+ AccessThreshold),
{ use_local_vars__main(Instrs3, Instrs,
- ProcLabel, NumRealRRegs, C2, C) },
+ ProcLabel, NumRealRRegs, AccessThreshold, C2, C) },
optimize__maybe_opt_debug(Instrs, C, "after use_local_vars",
OptDebugInfo3, OptDebugInfo)
;
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.360
diff -u -b -r1.360 options.m
--- compiler/options.m 8 Mar 2002 04:03:26 -0000 1.360
+++ compiler/options.m 8 Mar 2002 13:07:56 -0000
@@ -89,6 +89,7 @@
; debug_rl_opt
; debug_il_asm % il_asm = IL generation via asm
; debug_liveness
+ ; debug_stack_opt
; debug_make
% Output options
; make_short_interface
@@ -349,6 +350,7 @@
; gcc_local_labels
; prefer_switch
+ ; opt_no_return_calls
% Optimization Options
; opt_level
@@ -384,6 +386,20 @@
; optimize_duplicate_calls
; constant_propagation
; excess_assign
+ ; optimize_saved_vars_const
+ ; optimize_saved_vars_cell
+ ; optimize_saved_vars_cell_loop
+ ; optimize_saved_vars_cell_full_path
+ ; optimize_saved_vars_cell_on_stack
+ ; optimize_saved_vars_cell_candidate_headvars
+ ; optimize_saved_vars_cell_cv_store_cost
+ ; optimize_saved_vars_cell_cv_load_cost
+ ; optimize_saved_vars_cell_fv_store_cost
+ ; optimize_saved_vars_cell_fv_load_cost
+ ; optimize_saved_vars_cell_op_ratio
+ ; optimize_saved_vars_cell_node_ratio
+ ; optimize_saved_vars_cell_all_path_node_ratio
+ ; optimize_saved_vars_cell_include_all_candidates
; optimize_saved_vars
; delay_construct
; follow_code
@@ -429,6 +445,7 @@
; pessimize_tailcalls
; checked_nondet_tailcalls
; use_local_vars
+ ; local_var_access_threshold
; optimize_labels
; optimize_dups
%%% unused: ; optimize_copyprop
@@ -594,6 +611,7 @@
debug_rl_opt - bool(no),
debug_il_asm - bool(no),
debug_liveness - int(-1),
+ debug_stack_opt - int(-1),
debug_make - bool(no)
]).
option_defaults_2(output_option, [
@@ -794,7 +812,8 @@
fact_table_max_array_size - int(1024),
fact_table_hash_percent_full - int(90),
gcc_local_labels - bool(no),
- prefer_switch - bool(yes)
+ prefer_switch - bool(yes),
+ opt_no_return_calls - bool(yes)
]).
option_defaults_2(special_optimization_option, [
% Special optimization options.
@@ -840,7 +859,21 @@
optimize_duplicate_calls - bool(no),
constant_propagation - bool(no),
excess_assign - bool(no),
- optimize_saved_vars - bool(no),
+ optimize_saved_vars_const - bool(no),
+ optimize_saved_vars_cell - bool(no),
+ optimize_saved_vars_cell_loop - bool(yes),
+ optimize_saved_vars_cell_full_path - bool(yes),
+ optimize_saved_vars_cell_on_stack - bool(yes),
+ optimize_saved_vars_cell_candidate_headvars - bool(yes),
+ optimize_saved_vars_cell_cv_store_cost - int(1),
+ optimize_saved_vars_cell_cv_load_cost - int(1),
+ optimize_saved_vars_cell_fv_store_cost - int(1),
+ optimize_saved_vars_cell_fv_load_cost - int(1),
+ optimize_saved_vars_cell_op_ratio - int(100),
+ optimize_saved_vars_cell_node_ratio - int(100),
+ optimize_saved_vars_cell_all_path_node_ratio - int(100),
+ optimize_saved_vars_cell_include_all_candidates - bool(yes),
+ optimize_saved_vars - bool_special,
delay_construct - bool(no),
prev_code - bool(no),
follow_code - bool(no),
@@ -850,7 +883,7 @@
higher_order_size_limit - int(20),
higher_order_arg_limit - int(10),
unneeded_code - bool(no),
- unneeded_code_copy_limit - int(10),
+ unneeded_code_copy_limit- int(10),
type_specialization - bool(no),
user_guided_type_specialization - bool(no),
introduce_accumulators - bool(no),
@@ -892,6 +925,7 @@
pessimize_tailcalls - bool(no),
checked_nondet_tailcalls - bool(no),
use_local_vars - bool(no),
+ local_var_access_threshold - int(2),
optimize_labels - bool(no),
optimize_dups - bool(no),
%%% optimize_copyprop - bool(no),
@@ -1079,6 +1113,7 @@
% system built into .NET improves.
long_option("debug-il-asm", debug_il_asm).
long_option("debug-liveness", debug_liveness).
+long_option("debug-stack-opt", debug_stack_opt).
long_option("debug-make", debug_make).
% output options (mutually exclusive)
@@ -1278,6 +1313,7 @@
fact_table_hash_percent_full).
long_option("gcc-local-labels", gcc_local_labels).
long_option("prefer-switch", prefer_switch).
+long_option("opt-no-return-calls", opt_no_return_calls).
% optimization options
@@ -1315,6 +1351,22 @@
long_option("optimize-constant-propagation", constant_propagation).
long_option("optimize-saved-vars", optimize_saved_vars).
long_option("optimise-saved-vars", optimize_saved_vars).
+long_option("optimize-saved-vars-const", optimize_saved_vars_const).
+long_option("optimise-saved-vars-const", optimize_saved_vars_const).
+long_option("optimize-saved-vars-cell", optimize_saved_vars_cell).
+long_option("optimise-saved-vars-cell", optimize_saved_vars_cell).
+long_option("osv-loop", optimize_saved_vars_cell_loop).
+long_option("osv-full-path", optimize_saved_vars_cell_full_path).
+long_option("osv-on-stack", optimize_saved_vars_cell_on_stack).
+long_option("osv-cand-head", optimize_saved_vars_cell_candidate_headvars).
+long_option("osv-cvstore-cost", optimize_saved_vars_cell_cv_store_cost).
+long_option("osv-cvload-cost", optimize_saved_vars_cell_cv_load_cost).
+long_option("osv-fvstore-cost", optimize_saved_vars_cell_fv_store_cost).
+long_option("osv-fvload-cost", optimize_saved_vars_cell_fv_load_cost).
+long_option("osv-op-ratio", optimize_saved_vars_cell_op_ratio).
+long_option("osv-node-ratio", optimize_saved_vars_cell_node_ratio).
+long_option("osv-allpath-node-ratio", optimize_saved_vars_cell_all_path_node_ratio).
+long_option("osv-all-cand", optimize_saved_vars_cell_include_all_candidates).
long_option("delay-construct", delay_construct).
long_option("delay-constructs", delay_construct).
long_option("prev-code", prev_code).
@@ -1410,6 +1462,7 @@
long_option("pessimize-tailcalls", pessimize_tailcalls).
long_option("checked-nondet-tailcalls", checked_nondet_tailcalls).
long_option("use-local-vars", use_local_vars).
+long_option("local-var-access-threshold", local_var_access_threshold).
long_option("optimize-labels", optimize_labels).
long_option("optimise-labels", optimize_labels).
long_option("optimize-dups", optimize_dups).
@@ -1627,6 +1680,12 @@
N = N0
),
set_opt_level(N, OptionTable0, OptionTable).
+special_handler(optimize_saved_vars, bool(Optimize),
+ OptionTable0, ok(OptionTable)) :-
+ map__set(OptionTable0, optimize_saved_vars_const, bool(Optimize),
+ OptionTable1),
+ map__set(OptionTable1, optimize_saved_vars_cell, bool(Optimize),
+ OptionTable).
special_handler(mercury_library_directory_special, string(Dir),
OptionTable0, ok(OptionTable)) :-
OptionTable = option_table_add_mercury_library_directory(
@@ -1785,7 +1844,7 @@
opt_level(3, _, [
%%% optimize_copyprop - bool(yes),
- optimize_saved_vars - bool(yes),
+ optimize_saved_vars_const - bool(yes),
optimize_unused_args - bool(yes),
optimize_higher_order - bool(yes),
deforestation - bool(yes),
@@ -2678,6 +2737,8 @@
% "\tThis option has no effect unless the `--high-level-code' option",
% "\tis enabled. It also has no effect if the `--target' option is",
% "\tset to `il'.",
+% "--no-opt-no-return-calls",
+% "\tDo not optimize the stack usage of calls that cannot return.",
]),
@@ -2804,9 +2865,17 @@
"--delay-constructs",
"\tReorder goals to move construction unifications after",
"\tprimitive goals that can fail.",
+ % "--optimize-saved-vars-const",
+ % "\tMinimize the number of variables saved across calls by",
+ % "\tintroducing duplicate copies of variables bound to",
+ % "\tconstants in each interval between flushes where they",
+ % "\tare needed.",
+ % "--optimize-saved-vars-cell",
+ % "\tMinimize the number of variables saved across calls by",
+ % "\ttrying to use saved variables pointing to cells to reach",
+ % "\tthe variables stored in those cells.",
"--optimize-saved-vars",
- "\tReorder goals to minimize the number of variables",
- "\tthat have to be saved across calls.",
+ "\tMinimize the number of variables saved across calls.",
"--optimize-unused-args",
"\tRemove unused predicate arguments.",
"\tThis will cause the compiler to generate more",
Index: compiler/par_conj_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/par_conj_gen.m,v
retrieving revision 1.8
diff -u -b -r1.8 par_conj_gen.m
--- compiler/par_conj_gen.m 23 Nov 2000 04:32:46 -0000 1.8
+++ compiler/par_conj_gen.m 15 Dec 2001 16:12:54 -0000
@@ -99,9 +99,9 @@
:- import_module hlds_goal, code_model, llds, code_info.
:- import_module list.
-:- pred par_conj_gen__generate_par_conj(list(hlds_goal), hlds_goal_info,
- code_model, code_tree, code_info, code_info).
-:- mode par_conj_gen__generate_par_conj(in, in, in, out, in, out) is det.
+:- pred par_conj_gen__generate_par_conj(list(hlds_goal)::in,
+ hlds_goal_info::in, code_model::in, code_tree::out,
+ code_info::in, code_info::out) is det.
%---------------------------------------------------------------------------%
@@ -110,7 +110,7 @@
:- import_module hlds_data, code_gen, code_util, options, globals, prog_data.
:- import_module hlds_module, (inst), instmap, mode_util, code_info.
:- import_module continuation_info.
-:- import_module set, tree, list, map, std_util, require, int.
+:- import_module bool, set, tree, list, map, std_util, require, int.
%---------------------------------------------------------------------------%
@@ -152,12 +152,12 @@
- "store the sync-term on the stack"
]) },
code_info__release_reg(RegLval),
- code_info__clear_all_registers,
+ code_info__clear_all_registers(no),
par_conj_gen__generate_det_par_conj_2(Goals, 0, SyncSlot, SpSlot,
Initial, no, GoalCode),
code_info__release_temp_slot(SyncSlot),
{ Code = tree(tree(SaveCode, MakeTerm), GoalCode) },
- code_info__clear_all_registers,
+ code_info__clear_all_registers(no),
par_conj_gen__place_all_outputs(Outputs).
:- pred par_conj_gen__generate_det_par_conj_2(list(hlds_goal), int, lval, lval,
Index: compiler/pd_cost.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/pd_cost.m,v
retrieving revision 1.12
diff -u -b -r1.12 pd_cost.m
--- compiler/pd_cost.m 7 Apr 2001 14:04:53 -0000 1.12
+++ compiler/pd_cost.m 16 Jul 2001 17:25:17 -0000
@@ -43,19 +43,19 @@
pd_cost__goal(conj(Goals) - _, Cost) :-
pd_cost__goals(Goals, 0, Cost).
-pd_cost__goal(par_conj(Goals, _SM) - _, Cost) :-
+pd_cost__goal(par_conj(Goals) - _, Cost) :-
pd_cost__goals(Goals, 0, Cost).
-pd_cost__goal(disj(Goals, _) - _, Cost) :-
+pd_cost__goal(disj(Goals) - _, Cost) :-
pd_cost__goals(Goals, 0, Cost0),
pd_cost__stack_flush(Cost1),
Cost is Cost0 + Cost1.
-pd_cost__goal(switch(_, _, Cases, _) - _, Cost) :-
+pd_cost__goal(switch(_, _, Cases) - _, Cost) :-
pd_cost__simple_test(Cost0),
pd_cost__cases(Cases, Cost0, Cost).
-pd_cost__goal(if_then_else(_, Cond, Then, Else, _) - _, Cost) :-
+pd_cost__goal(if_then_else(_, Cond, Then, Else) - _, Cost) :-
pd_cost__goal(Cond, Cost1),
pd_cost__goal(Then, Cost2),
pd_cost__goal(Else, Cost3),
Index: compiler/pd_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/pd_util.m,v
retrieving revision 1.16
diff -u -b -r1.16 pd_util.m
--- compiler/pd_util.m 12 Oct 2001 05:23:45 -0000 1.16
+++ compiler/pd_util.m 12 Oct 2001 08:40:17 -0000
@@ -558,11 +558,11 @@
pd_util__get_branch_instmap_deltas(Goal, [CondDelta, ThenDelta, ElseDelta]) :-
Goal = if_then_else(_, _ - CondInfo, _ - ThenInfo,
- _ - ElseInfo, _) - _,
+ _ - ElseInfo) - _,
goal_info_get_instmap_delta(CondInfo, CondDelta),
goal_info_get_instmap_delta(ThenInfo, ThenDelta),
goal_info_get_instmap_delta(ElseInfo, ElseDelta).
-pd_util__get_branch_instmap_deltas(switch(_, _, Cases, _) - _,
+pd_util__get_branch_instmap_deltas(switch(_, _, Cases) - _,
InstMapDeltas) :-
GetCaseInstMapDelta =
lambda([Case::in, InstMapDelta::out] is det, (
@@ -570,7 +570,7 @@
goal_info_get_instmap_delta(CaseInfo, InstMapDelta)
)),
list__map(GetCaseInstMapDelta, Cases, InstMapDeltas).
-pd_util__get_branch_instmap_deltas(disj(Disjuncts, _) - _, InstMapDeltas) :-
+pd_util__get_branch_instmap_deltas(disj(Disjuncts) - _, InstMapDeltas) :-
GetDisjunctInstMapDelta =
lambda([Disjunct::in, InstMapDelta::out] is det, (
Disjunct = _ - DisjInfo,
@@ -586,7 +586,7 @@
set(prog_var)::in, set(prog_var)::out) is det.
pd_util__get_left_vars(Goal, Vars0, Vars) :-
- ( Goal = switch(Var, _, _, _) - _ ->
+ ( Goal = switch(Var, _, _) - _ ->
set__insert(Vars0, Var, Vars)
;
Vars = Vars0
@@ -626,7 +626,7 @@
% We have extra information about a switched-on variable
% at the end of each branch.
- ( Goal = switch(SwitchVar, _, _, _) - _ ->
+ ( Goal = switch(SwitchVar, _, _) - _ ->
( map__search(ExtraVars1, SwitchVar, SwitchVarSet0) ->
set__insert(SwitchVarSet0, BranchNo, SwitchVarSet)
;
@@ -650,7 +650,7 @@
pd_util__get_sub_branch_vars_goal(ModuleInfo0, ProcArgInfo, [Goal | GoalList],
VarTypes, InstMap0, Vars0, SubVars, ModuleInfo) :-
Goal = GoalExpr - GoalInfo,
- ( GoalExpr = if_then_else(_, Cond, Then, Else, _) ->
+ ( GoalExpr = if_then_else(_, Cond, Then, Else) ->
Cond = _ - CondInfo,
goal_info_get_instmap_delta(CondInfo, CondDelta),
instmap__apply_instmap_delta(InstMap0, CondDelta, InstMap1),
@@ -661,11 +661,11 @@
pd_util__examine_branch(ModuleInfo0, ProcArgInfo, 2, ElseList,
VarTypes, InstMap0, Vars1, Vars2),
ModuleInfo1 = ModuleInfo0
- ; GoalExpr = disj(Goals, _) ->
+ ; GoalExpr = disj(Goals) ->
pd_util__examine_branch_list(ModuleInfo0, ProcArgInfo,
1, Goals, VarTypes, InstMap0, Vars0, Vars2),
ModuleInfo1 = ModuleInfo0
- ; GoalExpr = switch(Var, _, Cases, _) ->
+ ; GoalExpr = switch(Var, _, Cases) ->
pd_util__examine_case_list(ModuleInfo0, ProcArgInfo, 1, Var,
Cases, VarTypes, InstMap0, Vars0, Vars2, ModuleInfo1)
;
Index: compiler/polymorphism.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/polymorphism.m,v
retrieving revision 1.219
diff -u -b -r1.219 polymorphism.m
--- compiler/polymorphism.m 7 Mar 2002 08:30:13 -0000 1.219
+++ compiler/polymorphism.m 8 Mar 2002 04:04:49 -0000
@@ -1145,22 +1145,22 @@
polymorphism__process_goal_expr(conj(Goals0), GoalInfo,
conj(Goals) - GoalInfo) -->
polymorphism__process_goal_list(Goals0, Goals).
-polymorphism__process_goal_expr(par_conj(Goals0, SM), GoalInfo,
- par_conj(Goals, SM) - GoalInfo) -->
+polymorphism__process_goal_expr(par_conj(Goals0), GoalInfo,
+ par_conj(Goals) - GoalInfo) -->
polymorphism__process_goal_list(Goals0, Goals).
-polymorphism__process_goal_expr(disj(Goals0, SM), GoalInfo,
- disj(Goals, SM) - GoalInfo) -->
+polymorphism__process_goal_expr(disj(Goals0), GoalInfo,
+ disj(Goals) - GoalInfo) -->
polymorphism__process_goal_list(Goals0, Goals).
polymorphism__process_goal_expr(not(Goal0), GoalInfo, not(Goal) - GoalInfo) -->
polymorphism__process_goal(Goal0, Goal).
-polymorphism__process_goal_expr(switch(Var, CanFail, Cases0, SM), GoalInfo,
- switch(Var, CanFail, Cases, SM) - GoalInfo) -->
+polymorphism__process_goal_expr(switch(Var, CanFail, Cases0), GoalInfo,
+ switch(Var, CanFail, Cases) - GoalInfo) -->
polymorphism__process_case_list(Cases0, Cases).
polymorphism__process_goal_expr(some(Vars, CanRemove, Goal0), GoalInfo,
some(Vars, CanRemove, Goal) - GoalInfo) -->
polymorphism__process_goal(Goal0, Goal).
-polymorphism__process_goal_expr(if_then_else(Vars, A0, B0, C0, SM), GoalInfo,
- if_then_else(Vars, A, B, C, SM) - GoalInfo) -->
+polymorphism__process_goal_expr(if_then_else(Vars, A0, B0, C0), GoalInfo,
+ if_then_else(Vars, A, B, C) - GoalInfo) -->
polymorphism__process_goal(A0, A),
polymorphism__process_goal(B0, B),
polymorphism__process_goal(C0, C).
Index: compiler/pragma_c_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/pragma_c_gen.m,v
retrieving revision 1.48
diff -u -b -r1.48 pragma_c_gen.m
--- compiler/pragma_c_gen.m 13 Feb 2002 09:56:25 -0000 1.48
+++ compiler/pragma_c_gen.m 14 Feb 2002 06:32:04 -0000
@@ -31,7 +31,7 @@
:- pred pragma_c_gen__generate_pragma_c_code(code_model::in,
pragma_foreign_proc_attributes::in, pred_id::in, proc_id::in,
list(prog_var)::in, list(maybe(pair(string, mode)))::in, list(type)::in,
- hlds_goal_info::in, pragma_foreign_code_impl::in, code_tree::out,
+ pragma_foreign_code_impl::in, hlds_goal_info::in, code_tree::out,
code_info::in, code_info::out) is det.
:- pred pragma_c_gen__struct_name(module_name::in, string::in, int::in,
@@ -41,8 +41,8 @@
:- implementation.
-:- import_module hlds_module, hlds_pred, llds_out, trace, tree.
-:- import_module code_util, foreign.
+:- import_module hlds_module, hlds_pred, hlds_llds, llds_out, trace, tree.
+:- import_module instmap, code_util, foreign.
:- import_module options, globals.
:- import_module bool, string, int, assoc_list, set, map, require, term.
@@ -311,8 +311,8 @@
% Of course we also need to #undef it afterwards.
pragma_c_gen__generate_pragma_c_code(CodeModel, Attributes,
- PredId, ProcId, ArgVars, ArgDatas, OrigArgTypes, GoalInfo,
- PragmaImpl, Code) -->
+ PredId, ProcId, ArgVars, ArgDatas, OrigArgTypes, PragmaImpl,
+ GoalInfo, Code) -->
(
{ PragmaImpl = ordinary(C_Code, Context) },
pragma_c_gen__ordinary_pragma_c_code(CodeModel, Attributes,
@@ -526,7 +526,13 @@
( { MayCallMercury = will_not_call_mercury } ->
[]
;
- code_info__clear_all_registers
+ { goal_info_get_instmap_delta(GoalInfo, InstMapDelta) },
+ { instmap_delta_is_reachable(InstMapDelta) ->
+ OkToDelete = no
+ ;
+ OkToDelete = yes
+ },
+ code_info__clear_all_registers(OkToDelete)
),
%
Index: compiler/prog_rep.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/prog_rep.m,v
retrieving revision 1.9
diff -u -b -r1.9 prog_rep.m
--- compiler/prog_rep.m 20 Feb 2002 03:14:18 -0000 1.9
+++ compiler/prog_rep.m 20 Feb 2002 04:26:46 -0000
@@ -147,18 +147,17 @@
prog_rep__represent_goal_expr(conj(Goals), _, InstMap0, Info, Rep) :-
prog_rep__represent_conj(Goals, InstMap0, Info, Reps),
Rep = conj_rep(Reps).
-prog_rep__represent_goal_expr(par_conj(_, _), _, _, _, _) :-
+prog_rep__represent_goal_expr(par_conj(_), _, _, _, _) :-
error("Sorry, not yet implemented:\n\
parallel conjunctions and declarative debugging").
-prog_rep__represent_goal_expr(disj(Goals, _SM), _, InstMap0, Info, Rep)
- :-
+prog_rep__represent_goal_expr(disj(Goals), _, InstMap0, Info, Rep) :-
prog_rep__represent_disj(Goals, InstMap0, Info, DisjReps),
Rep = disj_rep(DisjReps).
prog_rep__represent_goal_expr(not(Goal), _GoalInfo, InstMap0, Info, Rep)
:-
prog_rep__represent_goal(Goal, InstMap0, Info, InnerRep),
Rep = negation_rep(InnerRep).
-prog_rep__represent_goal_expr(if_then_else(_, Cond, Then, Else, _SM),
+prog_rep__represent_goal_expr(if_then_else(_, Cond, Then, Else),
_, InstMap0, Info, Rep) :-
prog_rep__represent_goal(Cond, InstMap0, Info, CondRep),
Cond = _ - CondGoalInfo,
@@ -167,7 +166,7 @@
prog_rep__represent_goal(Then, InstMap1, Info, ThenRep),
prog_rep__represent_goal(Else, InstMap0, Info, ElseRep),
Rep = ite_rep(CondRep, ThenRep, ElseRep).
-prog_rep__represent_goal_expr(switch(_, _, Cases, _SM), _,
+prog_rep__represent_goal_expr(switch(_, _, Cases), _,
InstMap0, Info, Rep) :-
prog_rep__represent_cases(Cases, InstMap0, Info, CaseReps),
Rep = switch_rep(CaseReps).
Index: compiler/purity.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/purity.m,v
retrieving revision 1.43
diff -u -b -r1.43 purity.m
--- compiler/purity.m 22 Feb 2002 01:20:54 -0000 1.43
+++ compiler/purity.m 22 Feb 2002 05:17:55 -0000
@@ -602,7 +602,7 @@
compute_expr_purity(conj(Goals0), conj(Goals), _, InClosure, Purity) -->
compute_goals_purity(Goals0, Goals, InClosure, pure, Purity).
-compute_expr_purity(par_conj(Goals0, SM), par_conj(Goals, SM), _,
+compute_expr_purity(par_conj(Goals0), par_conj(Goals), _,
InClosure, Purity) -->
compute_goals_purity(Goals0, Goals, InClosure, pure, Purity).
compute_expr_purity(call(PredId0,ProcId,Vars,BIState,UContext,Name0),
@@ -664,8 +664,8 @@
{ GoalExpr = generic_call(GenericCall, Args, Modes, Det) }
).
-compute_expr_purity(switch(Var,Canfail,Cases0,Storemap),
- switch(Var,Canfail,Cases,Storemap), _, InClosure, Purity) -->
+compute_expr_purity(switch(Var, Canfail, Cases0),
+ switch(Var, Canfail, Cases), _, InClosure, Purity) -->
compute_cases_purity(Cases0, Cases, InClosure, pure, Purity).
compute_expr_purity(Unif0, GoalExpr, GoalInfo, InClosure,
ActualPurity) -->
@@ -749,8 +749,7 @@
{ GoalExpr = Unif0 },
{ ActualPurity = pure }
).
-compute_expr_purity(disj(Goals0,Store), disj(Goals,Store), _,
- InClosure, Purity) -->
+compute_expr_purity(disj(Goals0), disj(Goals), _, InClosure, Purity) -->
compute_goals_purity(Goals0, Goals, InClosure, pure, Purity).
compute_expr_purity(not(Goal0), NotGoal, GoalInfo0, InClosure, Purity) -->
%
@@ -767,12 +766,12 @@
compute_expr_purity(some(Vars, CanRemove, Goal0), some(Vars, CanRemove, Goal),
_, InClosure, Purity) -->
compute_goal_purity(Goal0, Goal, InClosure, Purity).
-compute_expr_purity(if_then_else(Vars,Goali0,Goalt0,Goale0,Store),
- if_then_else(Vars,Goali,Goalt,Goale,Store), _,
+compute_expr_purity(if_then_else(Vars, Cond0, Then0, Else0),
+ if_then_else(Vars, Cond, Then, Else), _,
InClosure, Purity) -->
- compute_goal_purity(Goali0, Goali, InClosure, Purity1),
- compute_goal_purity(Goalt0, Goalt, InClosure, Purity2),
- compute_goal_purity(Goale0, Goale, InClosure, Purity3),
+ compute_goal_purity(Cond0, Cond, InClosure, Purity1),
+ compute_goal_purity(Then0, Then, InClosure, Purity2),
+ compute_goal_purity(Else0, Else, InClosure, Purity3),
{ worst_purity(Purity1, Purity2, Purity12) },
{ worst_purity(Purity12, Purity3, Purity) }.
compute_expr_purity(ForeignProc0, ForeignProc, _, _, Purity) -->
Index: compiler/quantification.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/quantification.m,v
retrieving revision 1.80
diff -u -b -r1.80 quantification.m
--- compiler/quantification.m 7 Apr 2001 14:04:56 -0000 1.80
+++ compiler/quantification.m 9 Nov 2001 10:46:41 -0000
@@ -339,14 +339,14 @@
implicitly_quantify_goal_2(conj(List0), _, conj(List)) -->
implicitly_quantify_conj(List0, List).
-implicitly_quantify_goal_2(par_conj(List0, SM), _, par_conj(List, SM)) -->
+implicitly_quantify_goal_2(par_conj(List0), _, par_conj(List)) -->
implicitly_quantify_conj(List0, List).
-implicitly_quantify_goal_2(disj(Goals0, SM), _, disj(Goals, SM)) -->
+implicitly_quantify_goal_2(disj(Goals0), _, disj(Goals)) -->
implicitly_quantify_disj(Goals0, Goals).
-implicitly_quantify_goal_2(switch(Var, Det, Cases0, SM), _,
- switch(Var, Det, Cases, SM)) -->
+implicitly_quantify_goal_2(switch(Var, Det, Cases0), _,
+ switch(Var, Det, Cases)) -->
implicitly_quantify_cases(Cases0, Cases),
% The switch variable is guaranteed to be non-local to the
% switch, since it has to be bound elsewhere, so we put it
@@ -375,8 +375,8 @@
% have been renamed apart. So we don't keep them.
% Thus we replace `if_then_else(Vars, ....)' with
% `if_then_else([], ...)'.
-implicitly_quantify_goal_2(if_then_else(Vars0, Cond0, Then0, Else0, SM),
- Context, if_then_else([], Cond, Then, Else, SM)) -->
+implicitly_quantify_goal_2(if_then_else(Vars0, Cond0, Then0, Else0),
+ Context, if_then_else([], Cond, Then, Else)) -->
quantification__get_quant_vars(QuantVars),
quantification__get_outside(OutsideVars),
quantification__get_lambda_outside(LambdaOutsideVars),
@@ -949,17 +949,17 @@
goal_list_vars_2(NonLocalsToRecompute, Goals,
Set0, LambdaSet0, Set, LambdaSet).
-quantification__goal_vars_2(NonLocalsToRecompute, par_conj(Goals, _SM),
+quantification__goal_vars_2(NonLocalsToRecompute, par_conj(Goals),
Set0, LambdaSet0, Set, LambdaSet) :-
goal_list_vars_2(NonLocalsToRecompute, Goals,
Set0, LambdaSet0, Set, LambdaSet).
-quantification__goal_vars_2(NonLocalsToRecompute, disj(Goals, _),
+quantification__goal_vars_2(NonLocalsToRecompute, disj(Goals),
Set0, LambdaSet0, Set, LambdaSet) :-
goal_list_vars_2(NonLocalsToRecompute, Goals, Set0, LambdaSet0,
Set, LambdaSet).
-quantification__goal_vars_2(NonLocalsToRecompute, switch(Var, _Det, Cases, _),
+quantification__goal_vars_2(NonLocalsToRecompute, switch(Var, _Det, Cases),
Set0, LambdaSet0, Set, LambdaSet) :-
insert(Set0, Var, Set1),
case_list_vars_2(NonLocalsToRecompute, Cases,
@@ -980,7 +980,7 @@
Set0, LambdaSet0, Set, LambdaSet).
quantification__goal_vars_2(NonLocalsToRecompute,
- if_then_else(Vars, A, B, C, _),
+ if_then_else(Vars, A, B, C),
Set0, LambdaSet0, Set, LambdaSet) :-
% This code does the following:
% Set = Set0 + ( (vars(A) + vars(B)) \ Vars ) + vars(C)
Index: compiler/rl_exprn.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/rl_exprn.m,v
retrieving revision 1.23
diff -u -b -r1.23 rl_exprn.m
--- compiler/rl_exprn.m 7 Mar 2002 08:30:17 -0000 1.23
+++ compiler/rl_exprn.m 8 Mar 2002 04:04:53 -0000
@@ -827,7 +827,7 @@
tree(Fail,
node([rl_PROC_label(EndLabel)])
)) }.
-rl_exprn__goal(if_then_else(_, Cond, Then, Else, _) - _, Fail, Code) -->
+rl_exprn__goal(if_then_else(_, Cond, Then, Else) - _, Fail, Code) -->
rl_exprn_info_get_next_label_id(StartElse),
rl_exprn_info_get_next_label_id(EndIte),
{ CondFail = node([rl_EXP_jmp(StartElse)]) },
@@ -843,16 +843,16 @@
)))) }.
rl_exprn__goal(conj(Goals) - _, Fail, Code) -->
rl_exprn__goals(Goals, Fail, Code).
-rl_exprn__goal(par_conj(_, _) - _, _, _) -->
+rl_exprn__goal(par_conj(_) - _, _, _) -->
{ error("rl_exprn__goal: par_conj not yet implemented") }.
-rl_exprn__goal(disj(Goals, _) - _Info, Fail, Code) -->
+rl_exprn__goal(disj(Goals) - _Info, Fail, Code) -->
% Nondet disjunctions should have been transformed into
% separate Aditi predicates by dnf.m.
rl_exprn_info_get_next_label_id(EndDisj),
{ GotoEnd = node([rl_EXP_jmp(EndDisj)]) },
rl_exprn__disj(Goals, GotoEnd, Fail, DisjCode),
{ Code = tree(DisjCode, node([rl_PROC_label(EndDisj)])) }.
-rl_exprn__goal(switch(Var, _, Cases, _) - _, Fail, Code) -->
+rl_exprn__goal(switch(Var, _, Cases) - _, Fail, Code) -->
rl_exprn_info_get_next_label_id(EndSwitch),
{ GotoEnd = node([rl_EXP_jmp(EndSwitch)]) },
rl_exprn__cases(Var, Cases, GotoEnd, Fail, SwitchCode),
Index: compiler/rl_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/rl_gen.m,v
retrieving revision 1.5
diff -u -b -r1.5 rl_gen.m
--- compiler/rl_gen.m 13 Jul 1999 08:53:28 -0000 1.5
+++ compiler/rl_gen.m 16 Jul 2001 17:30:09 -0000
@@ -1655,7 +1655,7 @@
insert_tuple(output_rel(OutputRel, []),
OutputRel0, TupleGoal) - ""
]) }
- ; { Goal = disj(_, _) - _ } ->
+ ; { Goal = disj(_) - _ } ->
% create an empty relation
rl_info_get_new_temporary(schema(OutputArgTypes), OutputRel),
{ Code = node([init(output_rel(OutputRel, [])) - ""]) }
Index: compiler/rl_key.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/rl_key.m,v
retrieving revision 1.9
diff -u -b -r1.9 rl_key.m
--- compiler/rl_key.m 7 Mar 2002 08:30:18 -0000 1.9
+++ compiler/rl_key.m 8 Mar 2002 04:04:54 -0000
@@ -609,16 +609,16 @@
rl_key__extract_key_range_unify(Unify)
; { Goal = call(PredId, ProcId, CallArgs, _, _, _) - _ } ->
rl_key__extract_key_range_call(PredId, ProcId, CallArgs)
- ; { Goal = disj(Goals, _) - _ } ->
+ ; { Goal = disj(Goals) - _ } ->
key_info_get_constraints(Cnstrs0),
rl_key__extract_key_range_disj(Cnstrs0, Goals, [], Cnstrs),
key_info_set_constraints(Cnstrs)
- ; { Goal = switch(Var, _CanFail, Cases, _) - _ } ->
+ ; { Goal = switch(Var, _CanFail, Cases) - _ } ->
key_info_get_constraints(Cnstrs0),
rl_key__extract_key_range_switch(Cnstrs0, Var, Cases,
[], Cnstrs),
key_info_set_constraints(Cnstrs)
- ; { Goal = if_then_else(_, Cond, Then, Else, _) - _ } ->
+ ; { Goal = if_then_else(_, Cond, Then, Else) - _ } ->
key_info_get_constraints(Cnstrs0),
rl_key__extract_key_range(Cond),
rl_key__extract_key_range(Then),
Index: compiler/saved_vars.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/saved_vars.m,v
retrieving revision 1.31
diff -u -b -r1.31 saved_vars.m
--- compiler/saved_vars.m 7 Apr 2001 14:04:57 -0000 1.31
+++ compiler/saved_vars.m 16 Jul 2001 17:31:30 -0000
@@ -92,30 +92,30 @@
Goals, SlotInfo),
conj_list_to_goal(Goals, GoalInfo0, Goal)
;
- GoalExpr0 = par_conj(Goals0, SM),
+ GoalExpr0 = par_conj(Goals0),
% saved_vars_in_disj treats its goal list as
% an independent list of goals, so we can use
% it to process the list of parallel conjuncts too.
saved_vars_in_disj(Goals0, SlotInfo0, Goals, SlotInfo),
- Goal = par_conj(Goals, SM) - GoalInfo0
+ Goal = par_conj(Goals) - GoalInfo0
;
- GoalExpr0 = disj(Goals0, SM),
+ GoalExpr0 = disj(Goals0),
saved_vars_in_disj(Goals0, SlotInfo0, Goals, SlotInfo),
- Goal = disj(Goals, SM) - GoalInfo0
+ Goal = disj(Goals) - GoalInfo0
;
GoalExpr0 = not(NegGoal0),
saved_vars_in_goal(NegGoal0, SlotInfo0, NegGoal, SlotInfo),
Goal = not(NegGoal) - GoalInfo0
;
- GoalExpr0 = switch(Var, CanFail, Cases0, SM),
+ GoalExpr0 = switch(Var, CanFail, Cases0),
saved_vars_in_switch(Cases0, SlotInfo0, Cases, SlotInfo),
- Goal = switch(Var, CanFail, Cases, SM) - GoalInfo0
+ Goal = switch(Var, CanFail, Cases) - GoalInfo0
;
- GoalExpr0 = if_then_else(Vars, Cond0, Then0, Else0, SM),
+ GoalExpr0 = if_then_else(Vars, Cond0, Then0, Else0),
saved_vars_in_goal(Cond0, SlotInfo0, Cond, SlotInfo1),
saved_vars_in_goal(Then0, SlotInfo1, Then, SlotInfo2),
saved_vars_in_goal(Else0, SlotInfo2, Else, SlotInfo),
- Goal = if_then_else(Vars, Cond, Then, Else, SM) - GoalInfo0
+ Goal = if_then_else(Vars, Cond, Then, Else) - GoalInfo0
;
GoalExpr0 = some(Var, CanRemove, SubGoal0),
saved_vars_in_goal(SubGoal0, SlotInfo0, SubGoal, SlotInfo),
@@ -221,12 +221,12 @@
;
FirstExpr = not(_)
;
- FirstExpr = disj(_, _)
+ FirstExpr = disj(_)
;
- FirstExpr = switch(SwitchVar, _, _, _),
+ FirstExpr = switch(SwitchVar, _, _),
Var \= SwitchVar
;
- FirstExpr = if_then_else(_, _, _, _, _)
+ FirstExpr = if_then_else(_, _, _, _)
)
;
true
@@ -306,7 +306,7 @@
saved_vars_delay_goal(Goals1, Construct, Var,
IsNonLocal, SlotInfo0, Goals, SlotInfo)
;
- Goal0Expr = par_conj(_ParConj, _SM),
+ Goal0Expr = par_conj(_ParConj),
saved_vars_delay_goal(Goals0, Construct, Var,
IsNonLocal, SlotInfo0, Goals1, SlotInfo),
Goals = [Goal0|Goals1]
@@ -338,15 +338,15 @@
IsNonLocal, SlotInfo2, Goals1, SlotInfo),
Goals = [Goal1 | Goals1]
;
- Goal0Expr = disj(Disjuncts0, SM),
+ Goal0Expr = disj(Disjuncts0),
push_into_goals_rename(Disjuncts0, Construct, Var,
SlotInfo0, Disjuncts, SlotInfo1),
- Goal1 = disj(Disjuncts, SM) - Goal0Info,
+ Goal1 = disj(Disjuncts) - Goal0Info,
saved_vars_delay_goal(Goals0, Construct, Var,
IsNonLocal, SlotInfo1, Goals1, SlotInfo),
Goals = [Goal1 | Goals1]
;
- Goal0Expr = switch(SwitchVar, CF, Cases0, SM),
+ Goal0Expr = switch(SwitchVar, CF, Cases0),
( SwitchVar = Var ->
saved_vars_delay_goal(Goals0, Construct, Var,
IsNonLocal, SlotInfo0,
@@ -355,7 +355,7 @@
;
push_into_cases_rename(Cases0, Construct, Var,
SlotInfo0, Cases, SlotInfo1),
- Goal1 = switch(SwitchVar, CF, Cases, SM)
+ Goal1 = switch(SwitchVar, CF, Cases)
- Goal0Info,
saved_vars_delay_goal(Goals0, Construct, Var,
IsNonLocal, SlotInfo1,
@@ -363,14 +363,14 @@
Goals = [Goal1 | Goals1]
)
;
- Goal0Expr = if_then_else(V, Cond0, Then0, Else0, SM),
+ Goal0Expr = if_then_else(V, Cond0, Then0, Else0),
push_into_goal_rename(Cond0, Construct, Var,
SlotInfo0, Cond, SlotInfo1),
push_into_goal_rename(Then0, Construct, Var,
SlotInfo1, Then, SlotInfo2),
push_into_goal_rename(Else0, Construct, Var,
SlotInfo2, Else, SlotInfo3),
- Goal1 = if_then_else(V, Cond, Then, Else, SM)
+ Goal1 = if_then_else(V, Cond, Then, Else)
- Goal0Info,
saved_vars_delay_goal(Goals0, Construct, Var,
IsNonLocal, SlotInfo3, Goals1, SlotInfo),
Index: compiler/simplify.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/simplify.m,v
retrieving revision 1.99
diff -u -b -r1.99 simplify.m
--- compiler/simplify.m 7 Mar 2002 08:30:19 -0000 1.99
+++ compiler/simplify.m 8 Mar 2002 04:04:56 -0000
@@ -331,8 +331,10 @@
goal_info_get_context(GoalInfo0, Context),
(
simplify_do_warn(Info0),
- \+ (goal_contains_goal(Goal0, SubGoal),
- SubGoal = disj([], _) - _)
+ \+ (
+ goal_contains_goal(Goal0, SubGoal),
+ SubGoal = disj([]) - _
+ )
->
simplify_info_add_msg(Info0,
goal_cannot_succeed(Context), Info1)
@@ -519,7 +521,7 @@
GoalInfo = GoalInfo0
).
-simplify__goal_2(par_conj(Goals0, SM), GoalInfo0, Goal,
+simplify__goal_2(par_conj(Goals0), GoalInfo0, Goal,
GoalInfo, Info0, Info) :-
(
Goals0 = []
@@ -537,10 +539,10 @@
;
GoalInfo = GoalInfo0,
simplify__par_conj(Goals0, Goals, Info0, Info0, Info),
- Goal = par_conj(Goals, SM)
+ Goal = par_conj(Goals)
).
-simplify__goal_2(disj(Disjuncts0, SM), GoalInfo0,
+simplify__goal_2(disj(Disjuncts0), GoalInfo0,
Goal, GoalInfo, Info0, Info) :-
simplify_info_get_instmap(Info0, InstMap0),
simplify__disj(Disjuncts0, [], Disjuncts, [], InstMaps,
@@ -555,7 +557,7 @@
simplify__maybe_wrap_goal(GoalInfo0, GoalInfo1,
Goal1, Goal, GoalInfo, Info1, Info2)
;
- Goal = disj(Disjuncts, SM),
+ Goal = disj(Disjuncts),
simplify_info_get_module_info(Info1, ModuleInfo1),
goal_info_get_nonlocals(GoalInfo0, NonLocals),
simplify_info_get_var_types(Info1, VarTypes),
@@ -585,7 +587,7 @@
Info = Info2
).
-simplify__goal_2(switch(Var, SwitchCanFail0, Cases0, SM),
+simplify__goal_2(switch(Var, SwitchCanFail0, Cases0),
GoalInfo0, Goal, GoalInfo, Info0, Info) :-
simplify_info_get_instmap(Info0, InstMap0),
simplify_info_get_module_info(Info0, ModuleInfo0),
@@ -630,7 +632,7 @@
type_util__is_existq_cons(ModuleInfo1,
Type, ConsId)
->
- Goal = switch(Var, SwitchCanFail, Cases, SM),
+ Goal = switch(Var, SwitchCanFail, Cases),
goal_info_get_nonlocals(GoalInfo0, NonLocals),
simplify_info_get_var_types(Info1, VarTypes),
merge_instmap_deltas(InstMap0, NonLocals, VarTypes,
@@ -679,7 +681,7 @@
pd_cost__eliminate_switch(CostDelta),
simplify_info_incr_cost_delta(Info4, CostDelta, Info5)
;
- Goal = switch(Var, SwitchCanFail, Cases, SM),
+ Goal = switch(Var, SwitchCanFail, Cases),
simplify_info_get_module_info(Info1, ModuleInfo1),
goal_info_get_nonlocals(GoalInfo0, NonLocals),
simplify_info_get_var_types(Info1, VarTypes),
@@ -970,7 +972,7 @@
% conjunction construct. This will change when constraint pushing
% is finished, or when we start doing coroutining.
-simplify__goal_2(if_then_else(Vars, Cond0, Then0, Else0, SM),
+simplify__goal_2(if_then_else(Vars, Cond0, Then0, Else0),
GoalInfo0, Goal, GoalInfo, Info0, Info) :-
Cond0 = _ - CondInfo0,
goal_info_get_determinism(CondInfo0, CondDetism0),
@@ -1028,7 +1030,7 @@
goal_info_get_context(GoalInfo0, Context),
simplify_info_add_msg(Info1, ite_cond_cannot_succeed(Context),
Info)
- ; Else0 = disj([], _) - _ ->
+ ; Else0 = disj([]) - _ ->
% (A -> C ; fail) is equivalent to (A, C)
goal_to_conj_list(Cond0, CondList),
goal_to_conj_list(Then0, ThenList),
@@ -1063,7 +1065,7 @@
ModuleInfo0, ModuleInfo1),
simplify_info_set_module_info(Info6, ModuleInfo1, Info7),
goal_info_set_instmap_delta(GoalInfo0, NewDelta, GoalInfo1),
- IfThenElse = if_then_else(Vars, Cond, Then, Else, SM),
+ IfThenElse = if_then_else(Vars, Cond, Then, Else),
goal_info_get_determinism(GoalInfo0, IfThenElseDetism0),
determinism_components(IfThenElseDetism0, IfThenElseCanFail,
@@ -1081,7 +1083,7 @@
%
( CondCanFail = cannot_fail
; CondSolns = at_most_zero
- ; Else = disj([], _) - _
+ ; Else = disj([]) - _
)
->
simplify_info_undo_goal_updates(Info0, Info7, Info8),
@@ -1142,7 +1144,7 @@
Info = Info3
;
% replace `not fail' with `true'
- Goal1 = disj([], _) - _GoalInfo2
+ Goal1 = disj([]) - _GoalInfo2
->
true_goal(Context, Goal - GoalInfo),
Info = Info3
@@ -1598,7 +1600,7 @@
simplify__conjoin_goal_and_rev_goal_list(Goal1,
RevGoals0, RevGoals1),
- ( (Goal1 = disj([], _) - _ ; Goals0 = []) ->
+ ( (Goal1 = disj([]) - _ ; Goals0 = []) ->
RevGoals = RevGoals1
;
% We insert an explicit failure at the end
@@ -1779,7 +1781,7 @@
simplify__goal(Goal0, Goal, Info3, Info4),
% Remove failing branches.
- ( Goal = disj([], _) - _ ->
+ ( Goal = disj([]) - _ ->
RevCases = RevCases0,
InstMaps1 = InstMaps0,
CanFail1 = can_fail,
@@ -1887,7 +1889,7 @@
% since that can result from mode analysis
% pruning away cases in a switch which cannot
% succeed due to sub-typing in the modes.
- Goal0 \= disj([], _) - _
+ Goal0 \= disj([]) - _
->
goal_info_get_context(GoalInfo, Context),
simplify_info_add_msg(Info2,
@@ -1902,7 +1904,7 @@
(
(
- Goal0 = disj([], _) - _
+ Goal0 = disj([]) - _
;
% Only remove disjuncts that might loop
% or call error/1 if --no-fully-strict.
@@ -1957,19 +1959,18 @@
OutputVars = yes
),
simplify__fixup_disj(Disjuncts, Detism, OutputVars,
- GoalInfo, SM, InstMap0, DetInfo, Goal,
+ GoalInfo, InstMap0, DetInfo, Goal,
MsgsA, Msgs)
;
****/
:- pred simplify__fixup_disj(list(hlds_goal), determinism, bool,
- hlds_goal_info, store_map, hlds_goal_expr,
+ hlds_goal_info, hlds_goal_expr,
simplify_info, simplify_info).
-:- mode simplify__fixup_disj(in, in, in, in, in, out, in, out) is det.
+:- mode simplify__fixup_disj(in, in, in, in, out, in, out) is det.
-simplify__fixup_disj(Disjuncts, _, _OutputVars, GoalInfo, SM,
- Goal, Info0, Info) :-
- det_disj_to_ite(Disjuncts, GoalInfo, SM, IfThenElse),
+simplify__fixup_disj(Disjuncts, _, _OutputVars, GoalInfo, Goal, Info0, Info) :-
+ det_disj_to_ite(Disjuncts, GoalInfo, IfThenElse),
simplify__goal(IfThenElse, Simplified, Info0, Info),
Simplified = Goal - _.
@@ -1990,13 +1991,12 @@
% Disjunct3
% ).
-:- pred det_disj_to_ite(list(hlds_goal), hlds_goal_info, store_map,
- hlds_goal).
-:- mode det_disj_to_ite(in, in, in, out) is det.
+:- pred det_disj_to_ite(list(hlds_goal), hlds_goal_info, hlds_goal).
+:- mode det_disj_to_ite(in, in, out) is det.
-det_disj_to_ite([], _GoalInfo, _SM, _) :-
+det_disj_to_ite([], _GoalInfo, _) :-
error("reached base case of det_disj_to_ite").
-det_disj_to_ite([Disjunct | Disjuncts], GoalInfo, SM, Goal) :-
+det_disj_to_ite([Disjunct | Disjuncts], GoalInfo, Goal) :-
( Disjuncts = [] ->
Goal = Disjunct
;
@@ -2005,7 +2005,7 @@
true_goal(Then),
- det_disj_to_ite(Disjuncts, GoalInfo, SM, Rest),
+ det_disj_to_ite(Disjuncts, GoalInfo, Rest),
Rest = _RestGoal - RestGoalInfo,
goal_info_get_nonlocals(CondGoalInfo, CondNonLocals),
@@ -2032,7 +2032,7 @@
determinism_components(Detism, CanFail, MaxSoln),
goal_info_set_determinism(NewGoalInfo1, Detism, NewGoalInfo),
- Goal = if_then_else([], Cond, Then, Rest, SM) - NewGoalInfo
+ Goal = if_then_else([], Cond, Then, Rest) - NewGoalInfo
).
%-----------------------------------------------------------------------------%
@@ -2318,7 +2318,7 @@
simplify_info_maybe_clear_structs(BeforeAfter, Goal, Info0, Info) :-
(
- ( code_util__cannot_stack_flush(Goal)
+ ( code_util__cannot_flush(Goal)
; simplify_do_more_common(Info0)
)
->
Index: compiler/stack_alloc.m
===================================================================
RCS file: compiler/stack_alloc.m
diff -N compiler/stack_alloc.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ compiler/stack_alloc.m 19 Feb 2002 09:30:47 -0000
@@ -0,0 +1,194 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2002 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File live_vars.m
+%
+% Authors: zs, conway.
+%
+% This module allocates stack slots to the variables that need to be saved
+% across a call, across a goal that may fail, or in a parallel conjunction.
+%
+% The jobs is done in two steps. First we traverse the predicate definition
+% looking for sets of variables that must be saved on the stack at the same
+% time. If --optimize-stack-slots is set, then this phase is done by
+% stack_opt.m; if --optimize-stack-slots is not set, then it is done by
+% this module. Then we use a graph colouring algorithm to find an allocation
+% of stack slots (colours) to variables such that in each set of variables
+% that must be saved at the same time, each variable has a different colour.
+
+%-----------------------------------------------------------------------------%
+
+:- module stack_alloc.
+
+:- interface.
+
+:- import_module hlds_module, hlds_pred.
+:- import_module io.
+
+:- pred allocate_stack_slots_in_proc(pred_id::in, proc_id::in, module_info::in,
+ proc_info::in, proc_info::out, io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module llds, prog_data, hlds_goal, hlds_llds, hlds_data.
+:- import_module code_model, trace.
+:- import_module liveness, live_vars, stack_opt, goal_path, graph_colour.
+:- import_module globals, options, trace_params.
+
+:- import_module bool, int, list, assoc_list, map, set, std_util, require.
+
+%-----------------------------------------------------------------------------%
+
+allocate_stack_slots_in_proc(PredId, _ProcId, ModuleInfo, ProcInfo0, ProcInfo,
+ IO, IO) :-
+ initial_liveness(ProcInfo0, PredId, ModuleInfo, Liveness0),
+ module_info_globals(ModuleInfo, Globals),
+ globals__get_trace_level(Globals, TraceLevel),
+ ( trace_level_needs_input_vars(TraceLevel) = yes ->
+ trace__fail_vars(ModuleInfo, ProcInfo0, FailVars)
+ ;
+ set__init(FailVars)
+ ),
+ module_info_pred_info(ModuleInfo, PredId, PredInfo),
+ body_should_use_typeinfo_liveness(PredInfo, Globals, TypeInfoLiveness),
+ globals__lookup_bool_option(Globals, opt_no_return_calls,
+ OptNoReturnCalls),
+ AllocData = alloc_data(ModuleInfo, ProcInfo0, TypeInfoLiveness,
+ OptNoReturnCalls),
+ set__init(NondetLiveness0),
+ SimpleStackAlloc0 = stack_alloc(set__make_singleton_set(FailVars)),
+ proc_info_goal(ProcInfo0, Goal0),
+ build_live_sets_in_goal(Goal0, SimpleStackAlloc0,
+ Liveness0, NondetLiveness0, FailVars, AllocData,
+ Goal, SimpleStackAlloc, _Liveness, _NondetLiveness),
+ proc_info_set_goal(ProcInfo0, Goal, ProcInfo3),
+ SimpleStackAlloc = stack_alloc(LiveSets0),
+
+ trace__do_we_need_maxfr_slot(Globals, ProcInfo3, ProcInfo4),
+ trace__reserved_slots(ModuleInfo, ProcInfo4, Globals, NumReservedSlots,
+ MaybeReservedVarInfo),
+ (
+ MaybeReservedVarInfo = yes(ResVar - _),
+ set__singleton_set(ResVarSet, ResVar),
+ set__insert(LiveSets0, ResVarSet, LiveSets)
+ ;
+ MaybeReservedVarInfo = no,
+ LiveSets = LiveSets0
+ ),
+ graph_colour__group_elements(LiveSets, ColourSets),
+ set__to_sorted_list(ColourSets, ColourList),
+ proc_info_interface_code_model(ProcInfo4, CodeModel),
+ allocate_stack_slots(ColourList, CodeModel, NumReservedSlots,
+ MaybeReservedVarInfo, StackSlots),
+
+ proc_info_set_stack_slots(ProcInfo4, StackSlots, ProcInfo).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- type stack_alloc
+ ---> stack_alloc(
+ set(set(prog_var)) % The sets of vars that need to
+ % be on the stack at the same
+ % time.
+ ).
+
+:- instance stack_alloc_info(stack_alloc) where [
+ pred(at_call_site/4) is alloc_at_call_site,
+ pred(at_resume_site/4) is alloc_at_resume_site,
+ pred(at_par_conj/4) is alloc_at_par_conj
+].
+
+:- pred alloc_at_call_site(need_across_call::in, hlds_goal_info::in,
+ stack_alloc::in, stack_alloc::out) is det.
+
+alloc_at_call_site(NeedAtCall, _GoalInfo, StackAlloc0, StackAlloc) :-
+ NeedAtCall = need_across_call(ForwardVars, ResumeVars, NondetLiveVars),
+ LiveSet = set__union_list([ForwardVars, ResumeVars, NondetLiveVars]),
+ StackAlloc0 = stack_alloc(LiveSets0),
+ LiveSets = set__insert(LiveSets0, LiveSet),
+ StackAlloc = stack_alloc(LiveSets).
+
+:- pred alloc_at_resume_site(need_in_resume::in, hlds_goal_info::in,
+ stack_alloc::in, stack_alloc::out) is det.
+
+alloc_at_resume_site(NeedAtResume, _GoalInfo, StackAlloc0, StackAlloc) :-
+ NeedAtResume = need_in_resume(ResumeOnStack, ResumeVars,
+ NondetLiveVars),
+ (
+ ResumeOnStack = no,
+ StackAlloc = StackAlloc0
+ ;
+ ResumeOnStack = yes,
+ LiveSet = set__union(ResumeVars, NondetLiveVars),
+ StackAlloc0 = stack_alloc(LiveSets0),
+ LiveSets = set__insert(LiveSets0, LiveSet),
+ StackAlloc = stack_alloc(LiveSets)
+ ).
+
+:- pred alloc_at_par_conj(need_in_par_conj::in, hlds_goal_info::in,
+ stack_alloc::in, stack_alloc::out) is det.
+
+alloc_at_par_conj(NeedParConj, _GoalInfo, StackAlloc0, StackAlloc) :-
+ NeedParConj = need_in_par_conj(StackVars),
+ StackAlloc0 = stack_alloc(LiveSets0),
+ LiveSets = set__insert(LiveSets0, StackVars),
+ StackAlloc = stack_alloc(LiveSets).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- pred allocate_stack_slots(list(set(prog_var))::in, code_model::in, int::in,
+ maybe(pair(prog_var, int))::in, stack_slots::out) is det.
+
+allocate_stack_slots(ColourList, CodeModel, NumReservedSlots,
+ MaybeReservedVarInfo, StackSlots) :-
+ map__init(StackSlots0),
+ % The reserved slots are referred to by fixed number
+ % (e.g. framevar(1)) in trace__setup.
+ FirstVarSlot = NumReservedSlots + 1,
+ allocate_stack_slots_2(ColourList, CodeModel, FirstVarSlot,
+ MaybeReservedVarInfo, StackSlots0, StackSlots).
+
+:- pred allocate_stack_slots_2(list(set(prog_var))::in, code_model::in,
+ int::in, maybe(pair(prog_var, int))::in,
+ stack_slots::in, stack_slots::out) is det.
+
+allocate_stack_slots_2([], _, _, _, StackSlots, StackSlots).
+allocate_stack_slots_2([Vars | VarSets], CodeModel, N0, MaybeReservedVarInfo,
+ StackSlots0, StackSlots) :-
+ (
+ MaybeReservedVarInfo = yes(ResVar - ResSlotNum),
+ set__member(ResVar, Vars)
+ ->
+ SlotNum = ResSlotNum,
+ N1 = N0
+ ;
+ SlotNum = N0,
+ N1 = N0 + 1
+ ),
+ ( CodeModel = model_non ->
+ Slot = framevar(SlotNum)
+ ;
+ Slot = stackvar(SlotNum)
+ ),
+ set__to_sorted_list(Vars, VarList),
+ allocate_same_stack_slot(VarList, Slot, StackSlots0, StackSlots1),
+ allocate_stack_slots_2(VarSets, CodeModel, N1, MaybeReservedVarInfo,
+ StackSlots1, StackSlots).
+
+:- pred allocate_same_stack_slot(list(prog_var)::in, lval::in, stack_slots::in,
+ stack_slots::out) is det.
+
+allocate_same_stack_slot([], _Slot, StackSlots, StackSlots).
+allocate_same_stack_slot([Var | Vars], Slot, StackSlots0, StackSlots) :-
+ map__det_insert(StackSlots0, Var, Slot, StackSlots1),
+ allocate_same_stack_slot(Vars, Slot, StackSlots1, StackSlots).
+
+%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list