[m-rev.] (Postcommit) For review: Fix a logical bug: create regions in deadR
Quan Phan
quan.phan at cs.kuleuven.be
Thu Apr 23 20:00:35 AEST 2009
Hi,
I committed this change because it is only RBMM-related.
Regards,
Quan.
-------------- next part --------------
Estimated hours taken: 8
Branch: main
Fix a theoretical bug: we thought that regions in deadR were not allowed to be
created, but actually they should if the local region liveness requires so.
Improve coding style in the related files.
compiler/rbmm.region_instruction.m:
Fix a theoretical bug: Other than the regions in bornR and localR, we
should also allow ones in deadR set to be created if its local liveness
requires so. Such a region variable can be removed, then created,
then re-removed and so on, depending on local liveness.
Other than introducing region instruction it now also computes and returns
'become live', 'become dead before', 'become dead after' sets of regions.
These sets are used to decide resurrection of regions after that.
compiler/rbmm.region_resurrection_renaming.m:
Change to use the sets returned from rbmm.region_instruction.m.
The fix of the theoretical bug results in changes here because that case
also requires resurrection renaming.
compiler/rbmm.m:
Conform to the changes in rbmm.region_instruction.m
-------------- next part --------------
Index: rbmm.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.m,v
retrieving revision 1.8
diff -u -r1.8 rbmm.m
--- rbmm.m 8 Apr 2008 20:12:17 -0000 1.8
+++ rbmm.m 23 Apr 2009 08:20:20 -0000
@@ -80,7 +80,9 @@
VoidVarRegionTable0, VoidVarRegionTable),
introduce_region_instructions(!.ModuleInfo, RptaInfoTable,
ExecPathTable, LRBeforeTable, LRAfterTable, VoidVarRegionTable,
- BornRTable, DeadRTable, LocalRTable, RegionInstructionTable),
+ BornRTable, DeadRTable, LocalRTable,
+ BecomeLiveTable, BecomeDeadBeforeTable, BecomeDeadAfterTable,
+ RegionInstructionTable),
record_actual_region_arguments(!.ModuleInfo, RptaInfoTable,
ConstantRTable, DeadRTable, BornRTable,
@@ -93,13 +95,14 @@
% Mercury variables.
% The calls below derive the necessary mapping to resolve the problem.
compute_resurrection_paths(ExecPathTable, LRBeforeTable, LRAfterTable,
- BornRTable, LocalRTable, CreatedBeforeTable,
+ BornRTable, DeadRTable, LocalRTable,
+ BecomeLiveTable, BecomeDeadBeforeTable, BecomeDeadAfterTable,
ResurrectionPathTable0),
collect_join_points(ResurrectionPathTable0, ExecPathTable,
JoinPointTable),
collect_paths_containing_join_points(ExecPathTable, JoinPointTable,
ResurrectionPathTable0, ResurrectionPathTable),
- collect_region_resurrection_renaming(CreatedBeforeTable, LocalRTable,
+ collect_region_resurrection_renaming(BecomeLiveTable, LocalRTable,
RptaInfoTable, ResurrectionPathTable, ResurrectionRenameTable),
collect_renaming_and_annotation(ResurrectionRenameTable, JoinPointTable,
LRBeforeTable, LRAfterTable, BornRTable, RptaInfoTable,
Index: rbmm.region_instruction.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.region_instruction.m,v
retrieving revision 1.6
diff -u -r1.6 rbmm.region_instruction.m
--- rbmm.region_instruction.m 21 Apr 2009 14:05:55 -0000 1.6
+++ rbmm.region_instruction.m 23 Apr 2009 08:20:20 -0000
@@ -1,7 +1,7 @@
%-----------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%-----------------------------------------------------------------------------%
-% Copyright (C) 2005-2007, 2009 The University of Melbourne.
+% Copyright (C) 2005-2007 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.
%-----------------------------------------------------------------------------%
@@ -70,11 +70,38 @@
; remove_region_instr
; renaming_region_instr.
+ % This predicate decides on where create and remove instructions need to
+ % be inserted. The decision is based on region points-to graphs and
+ % the region liveness information (both local and global).
+ %
+ % It also computes for each program point in a procedure
+ % the sets of regions that become live (always before), become dead before,
+ % become dead after the point.
+ %
+ % A region 'becomes live' before a program point means that
+ % *locally* it is not live before the point and live after the point and
+ % *globally* the procedure is allowed to give life to it.
+ %
+ % A region 'becomes dead before' a program point means that
+ % *locally* it is live after the previous program point and not live before
+ % the point and *globally* the procedure is allowed to terminate its life.
+ %
+ % A region 'becomes dead after' a program point means that
+ % *locally* it is live before the program point and not live after the
+ % point and *globally* the procedure is allowed to terminate its life.
+ %
+ % A procedure is 'allowed' to manipulate the regions belongs to either
+ % bornR or deadR or localR.
+ %
+ % These sets are needed for computing resurrection of regions later on.
+ %
:- pred introduce_region_instructions(module_info::in, rpta_info_table::in,
execution_path_table::in, proc_pp_region_set_table::in,
proc_pp_region_set_table::in, proc_pp_region_set_table::in,
proc_region_set_table::in, proc_region_set_table::in,
- proc_region_set_table::in, region_instr_table::out) is det.
+ proc_region_set_table::in,
+ proc_pp_region_set_table::out, proc_pp_region_set_table::out,
+ proc_pp_region_set_table::out, region_instr_table::out) is det.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -100,41 +127,55 @@
introduce_region_instructions(ModuleInfo, RptaInfoTable, ExecPathTable,
LRBeforeTable, LRAfterTable, VoidVarRegionTable, BornRTable,
- DeadRTable, LocalRTable, RegionInstructionTable) :-
+ DeadRTable, LocalRTable,
+ BecomeLiveTable, BecomeDeadBeforeTable, BecomeDeadAfterTable,
+ RegionInstructionTable) :-
module_info_predids(PredIds, ModuleInfo, _),
- map.init(RegionInstructionTable0),
- list.foldl(introduce_region_instructions_pred(ModuleInfo,
+ list.foldl4(introduce_region_instructions_pred(ModuleInfo,
RptaInfoTable, ExecPathTable, LRBeforeTable, LRAfterTable,
VoidVarRegionTable, BornRTable, DeadRTable, LocalRTable), PredIds,
- RegionInstructionTable0, RegionInstructionTable).
+ map.init, BecomeLiveTable,
+ map.init, BecomeDeadBeforeTable,
+ map.init, BecomeDeadAfterTable,
+ map.init, RegionInstructionTable).
:- pred introduce_region_instructions_pred(module_info::in,
rpta_info_table::in, execution_path_table::in,
proc_pp_region_set_table::in, proc_pp_region_set_table::in,
proc_pp_region_set_table::in, proc_region_set_table::in,
proc_region_set_table::in, proc_region_set_table::in, pred_id::in,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::out,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::out,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::out,
region_instr_table::in, region_instr_table::out) is det.
introduce_region_instructions_pred(ModuleInfo, RptaInfoTable, ExecPathTable,
LRBeforeTable, LRAfterTable, VoidVarRegionTable, BornRTable,
- DeadRTable, LocalRTable, PredId, !RegionInstructionTable) :-
+ DeadRTable, LocalRTable, PredId,
+ !BecomeLiveTable, !BecomeDeadBeforeTable, !BecomeDeadAfterTable,
+ !RegionInstructionTable) :-
module_info_pred_info(ModuleInfo, PredId, PredInfo),
pred_info_non_imported_procids(PredInfo) = ProcIds,
- list.foldl(introduce_region_instructions_proc(ModuleInfo, PredId,
+ list.foldl4(introduce_region_instructions_proc(ModuleInfo, PredId,
RptaInfoTable, ExecPathTable, LRBeforeTable, LRAfterTable,
VoidVarRegionTable, BornRTable, DeadRTable, LocalRTable),
- ProcIds, !RegionInstructionTable).
+ ProcIds, !BecomeLiveTable, !BecomeDeadBeforeTable,
+ !BecomeDeadAfterTable, !RegionInstructionTable).
:- pred introduce_region_instructions_proc(module_info::in, pred_id::in,
rpta_info_table::in, execution_path_table::in,
proc_pp_region_set_table::in, proc_pp_region_set_table::in,
proc_pp_region_set_table::in, proc_region_set_table::in,
proc_region_set_table::in, proc_region_set_table::in, proc_id::in,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::out,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::out,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::out,
region_instr_table::in, region_instr_table::out) is det.
introduce_region_instructions_proc(ModuleInfo, PredId, RptaInfoTable,
ExecPathTable, LRBeforeTable, LRAfterTable, VoidVarRegionTable,
BornRTable, DeadRTable, LocalRTable, ProcId,
+ !BecomeLiveTable, !BecomeDeadBeforeTable, !BecomeDeadAfterTable,
!RegionInstructionTable) :-
PPId = proc(PredId, ProcId),
( some_are_special_preds([PPId], ModuleInfo) ->
@@ -152,8 +193,14 @@
introduce_region_instructions_exec_paths(ExecPaths, RptaInfo,
BornR, DeadR, LocalR, ProcLRBefore, ProcLRAfter,
ProcVoidVarRegion, BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ map.init, BecomeLiveProc,
+ map.init, BecomeDeadBeforeProc,
+ map.init, BecomeDeadAfterProc,
map.init, RegionInstructionProc),
- svmap.set(PPId, RegionInstructionProc, !RegionInstructionTable)
+ svmap.set(PPId, RegionInstructionProc, !RegionInstructionTable),
+ svmap.set(PPId, BecomeLiveProc, !BecomeLiveTable),
+ svmap.set(PPId, BecomeDeadBeforeProc, !BecomeDeadBeforeTable),
+ svmap.set(PPId, BecomeDeadAfterProc, !BecomeDeadAfterTable)
).
% Follow each execution path of a procedure and introduce
@@ -164,72 +211,89 @@
pp_region_set_table::in, pp_region_set_table::in,
pp_region_set_table::in, proc_region_set_table::in,
proc_region_set_table::in, module_info::in, proc_info::in,
+ pp_region_set_table::in, pp_region_set_table::out,
+ pp_region_set_table::in, pp_region_set_table::out,
+ pp_region_set_table::in, pp_region_set_table::out,
region_instr_proc::in, region_instr_proc::out) is det.
introduce_region_instructions_exec_paths([], _, _, _, _, _, _, _, _, _, _, _,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
!RegionInstructionProc).
introduce_region_instructions_exec_paths([ExecPath|ExecPaths], RptaInfo,
BornR, DeadR, LocalR, ProcLRBefore, ProcLRAfter, ProcVoidVarRegion,
BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
!RegionInstructionProc) :-
introduce_region_instructions_exec_path(ExecPath, RptaInfo, BornR,
DeadR, LocalR, ProcLRBefore, ProcLRAfter, ProcVoidVarRegion,
- BornRTable, DeadRTable, ModuleInfo, ProcInfo, !RegionInstructionProc),
+ BornRTable, DeadRTable, ModuleInfo, ProcInfo, set.init,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
+ !RegionInstructionProc),
introduce_region_instructions_exec_paths(ExecPaths, RptaInfo, BornR,
DeadR, LocalR, ProcLRBefore, ProcLRAfter, ProcVoidVarRegion,
- BornRTable, DeadRTable, ModuleInfo, ProcInfo, !RegionInstructionProc).
+ BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
+ !RegionInstructionProc).
:- pred introduce_region_instructions_exec_path(execution_path::in,
- rpta_info::in, set(rptg_node)::in, set(rptg_node)::in, set(rptg_node)::in,
+ rpta_info::in, region_set::in, region_set::in, region_set::in,
pp_region_set_table::in, pp_region_set_table::in,
pp_region_set_table::in, proc_region_set_table::in,
- proc_region_set_table::in, module_info::in, proc_info::in,
+ proc_region_set_table::in, module_info::in, proc_info::in, region_set::in,
+ pp_region_set_table::in, pp_region_set_table::out,
+ pp_region_set_table::in, pp_region_set_table::out,
+ pp_region_set_table::in, pp_region_set_table::out,
region_instr_proc::in, region_instr_proc::out) is det.
-introduce_region_instructions_exec_path([], _, _, _, _, _, _, _, _, _, _, _,
+introduce_region_instructions_exec_path([], _, _, _, _, _, _, _, _, _, _, _, _,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
!RegionInstructionProc).
introduce_region_instructions_exec_path([ProgPoint - Goal | ProgPoint_Goals],
RptaInfo, BornR, DeadR, LocalR, ProcLRBefore, ProcLRAfter,
ProcVoidVarRegion, BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ BecomeDeadBeforeProgPoint,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
!RegionInstructionProc) :-
map.lookup(ProcLRBefore, ProgPoint, LRBefore),
map.lookup(ProcLRAfter, ProgPoint, LRAfter),
map.lookup(ProcVoidVarRegion, ProgPoint, VoidVarRegions),
+ set.union(set.union(LocalR, BornR), DeadR, Allowed),
+
% Because void variables at this program point are considered dead
% right after they get bound, the regions that are reached from them
% are also candidates to be removed. They will be destroyed after this
% program point if they are not live after the program point and they
% are either in DeadR or LocalR or BornR.
set.difference(VoidVarRegions, LRAfter, DeadVoidVarRegions0),
- set.union(LocalR, BornR, Local_Born),
- set.union(Local_Born, DeadR, Local_Born_Dead),
- set.intersect(Local_Born_Dead, DeadVoidVarRegions0, DeadVoidVarRegions),
+ set.intersect(Allowed, DeadVoidVarRegions0, DeadVoidVarRegions),
+
RptaInfo = rpta_info(CallerGraph, _),
- set.fold(
- record_instruction_after_prog_point(remove_region_instr,
+
+ set.intersect(Allowed, set.difference(LRBefore, LRAfter), BecomeDead),
+ set.intersect(Allowed, set.difference(LRAfter, LRBefore), BecomeLive),
+
+ Goal = hlds_goal(Expr, _),
+ svmap.set(ProgPoint, BecomeLive, !BecomeLiveProc),
+
+ annotate_expr(Expr, ProgPoint, BecomeLive,
+ BecomeDead, RptaInfo, BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ CreatedBeforeProgPoint, RemovedAfterProgPoint),
+
+ set.fold(record_instruction_before_prog_point(create_region_instr,
+ ProgPoint, CallerGraph),
+ CreatedBeforeProgPoint, !RegionInstructionProc),
+ set.fold(record_instruction_before_prog_point(remove_region_instr,
+ ProgPoint, CallerGraph),
+ BecomeDeadBeforeProgPoint, !RegionInstructionProc),
+ set.fold(record_instruction_after_prog_point(remove_region_instr,
ProgPoint, CallerGraph),
- DeadVoidVarRegions, !RegionInstructionProc),
+ RemovedAfterProgPoint, !RegionInstructionProc),
- set.difference(LRBefore, LRAfter, ToBeRemoved),
- set.intersect(ToBeRemoved, Local_Born_Dead, ToBeRemovedAndAllowed),
- ( Goal = hlds_goal(switch(_, _, _), _) ->
- % This is a switch, i.e. unification, only rule 4 applied.
- transformation_rule_4_2(ProgPoint, ToBeRemovedAndAllowed,
- RptaInfo, !RegionInstructionProc)
- ;
- Goal = hlds_goal(Expr, _),
- set.difference(LRAfter, LRBefore, ToBeCreated),
- set.intersect(ToBeCreated, Local_Born, ToBeCreatedAndAllowed),
- transformation_rule_1(Expr, ProgPoint, ToBeCreatedAndAllowed,
- RptaInfo, BornRTable, !RegionInstructionProc),
- transformation_rule_2(Expr, ProgPoint, ToBeCreatedAndAllowed,
- RptaInfo, ModuleInfo, ProcInfo, !RegionInstructionProc),
- transformation_rule_3(Expr, ProgPoint, ToBeRemovedAndAllowed,
- RptaInfo, DeadRTable, !RegionInstructionProc),
- transformation_rule_4(Expr, ProgPoint, ToBeRemovedAndAllowed,
- RptaInfo, !RegionInstructionProc)
- ),
+ svmap.set(ProgPoint, set.union(BecomeDead, DeadVoidVarRegions),
+ !BecomeDeadAfterProc),
+ svmap.set(ProgPoint, BecomeLive, !BecomeLiveProc),
+ svmap.set(ProgPoint, BecomeDeadBeforeProgPoint, !BecomeDeadBeforeProc),
(
ProgPoint_Goals = [NextProgPoint - _ | _],
@@ -239,47 +303,35 @@
% before the next program point if the current procedure is allowed
% to remove it.
map.lookup(ProcLRBefore, NextProgPoint, LRBeforeNext),
- set.difference(LRAfter, LRBeforeNext, ToBeRemovedBeforeNext),
- set.intersect(Local_Born_Dead, ToBeRemovedBeforeNext,
- ToBeRemovedBeforeNextAndAllowed),
- set.fold(record_instruction_before_prog_point(
- remove_region_instr, NextProgPoint, CallerGraph),
- ToBeRemovedBeforeNextAndAllowed,
- !RegionInstructionProc),
+
+ set.intersect(Allowed, set.difference(LRAfter, LRBeforeNext),
+ BecomeDeadBeforeNextProgPoint),
introduce_region_instructions_exec_path(ProgPoint_Goals, RptaInfo,
BornR, DeadR, LocalR,
ProcLRBefore, ProcLRAfter, ProcVoidVarRegion,
BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ BecomeDeadBeforeNextProgPoint,
+ !BecomeLiveProc, !BecomeDeadBeforeProc, !BecomeDeadAfterProc,
!RegionInstructionProc)
;
% This is the last program point, we finish.
ProgPoint_Goals = []
).
- % Rule 1: if an output region of q is not live, not created by q,
- % and p is allowed to create it, it is created before the call to q.
- %
- % There are two cases: either q is defined in this module or q is
- % imported.
- % The former is dealt with as per the rule.
- % The latter: for now, with the assumption that all source code is in
- % only one module, imported preds will only be ones from
- % Mercury's library. We do not intent to deal with the library's code
- % now therefore we have to assume here that the caller will always
- % *CREATE* the OUTPUT REGION for those procedures.
- %
-:- pred transformation_rule_1(hlds_goal_expr::in, program_point::in,
- region_set::in, rpta_info::in, proc_region_set_table::in,
- region_instr_proc::in, region_instr_proc::out) is det.
+:- pred annotate_expr(hlds_goal_expr::in, program_point::in,
+ region_set::in, region_set::in, rpta_info::in, proc_region_set_table::in,
+ proc_region_set_table::in, module_info::in, proc_info::in,
+ region_set::out, region_set::out) is det.
-transformation_rule_1(Expr, ProgPoint, ToBeCreatedAndAllowed, CallerRptaInfo,
- BornRTable, !RegionInstructionProc) :-
+annotate_expr(Expr, ProgPoint, BecomeLive, BecomeDead,
+ RptaInfo, BornRTable, DeadRTable, ModuleInfo, ProcInfo,
+ CreatedBeforeProgPoint, RemovedAfterProgPoint) :-
(
Expr = plain_call(CalleePredId, CalleeProcId, _, _, _, _)
->
CalleePPId = proc(CalleePredId, CalleeProcId),
- CallerRptaInfo = rpta_info(CallerGraph, AlphaMapping),
+ RptaInfo = rpta_info(_CallerGraph, AlphaMapping),
(
% Currently we do not collect BornR for non-defined-in-module
% procedure, so if we cannot find one here then q is an
@@ -287,203 +339,116 @@
map.search(BornRTable, CalleePPId, _)
->
map.lookup(AlphaMapping, ProgPoint, AlphaAtProgPoint),
+
+ % Rule 1: if an output region of q is not live, not created by q,
+ % and p is allowed to create it, it is created before the call to
+ % q.
map.lookup(BornRTable, CalleePPId, CalleeBornR),
map.foldl(
- process_mapping_rule_1(ProgPoint, ToBeCreatedAndAllowed,
- CalleeBornR, CallerGraph),
- AlphaAtProgPoint, !RegionInstructionProc)
+ process_mapping_rule_1(BecomeLive, CalleeBornR),
+ AlphaAtProgPoint, set.init, CreatedBeforeProgPoint),
+
+ % Rule 3: add remove(R) after the call.
+ % Transformation rule 3: if a region is live before q but it is not
+ % live after q and it is not removed by q, the caller will remove
+ % it after calling q.
+ map.lookup(DeadRTable, CalleePPId, CalleeDeadR),
+ map.foldl(process_mapping_rule_3(BecomeDead, CalleeDeadR),
+ AlphaAtProgPoint, set.init, RemovedAfterProgPoint)
;
- % q is from an imported module, therefore we consider BornR of
- % q empty, so just create whatever regions becoming live
- % provided that they are in BornR or LocalR, i.e., p is allowed
- % to create them.
- set.fold(
- record_instruction_before_prog_point(create_region_instr,
- ProgPoint, CallerGraph),
- ToBeCreatedAndAllowed, !RegionInstructionProc)
+ % XXX q is from an imported module. We do not support module
+ % system yet.
+ % For now we consider BornR and DeadR of q empty,
+ % therefore just create and remove whatever regions becoming live
+ % and dead.
+ CreatedBeforeProgPoint = BecomeLive,
+ RemovedAfterProgPoint = BecomeDead
)
;
- ( Expr = conj(_, [])
- ; Expr = disj([])
- ; Expr = unify(_, _, _, _, _)
- )
- ->
- true
- ;
- unexpected(this_file, "transformation_rule_1: found non-atomic goal")
- ).
-
-:- pred process_mapping_rule_1(program_point::in, region_set::in,
- region_set::in, rpt_graph::in, rptg_node::in, rptg_node::in,
- region_instr_proc::in, region_instr_proc::out) is det.
-
-process_mapping_rule_1(ProgPoint, ToBeCreatedAndAllowed, CalleeBornR,
- CallerGraph, SourceRegion, TargetRegion, !RegionInstructionProc) :-
- (
- set.contains(ToBeCreatedAndAllowed, TargetRegion),
- not set.contains(CalleeBornR, SourceRegion)
- ->
- record_instruction_before_prog_point(create_region_instr,
- ProgPoint, CallerGraph, TargetRegion, !RegionInstructionProc)
- ;
- true
- ).
-
- % Transformation rule 2: if a region reachable from the left variable
- % of a construction is not live before the construction but it is live
- % after and is a local region or in a BornR set, then the region is
- % created before the unification.
- %
-:- pred transformation_rule_2(hlds_goal_expr::in, program_point::in,
- region_set::in, rpta_info::in, module_info::in, proc_info::in,
- region_instr_proc::in, region_instr_proc::out) is det.
-
-transformation_rule_2(Expr, ProgPoint, ToBeCreatedAndAllowed, RptaInfo,
- ModuleInfo, ProcInfo, !RegionInstructionProc) :-
- (
- Expr = unify(X, _, _, construct(_, _, _, _, _, _, _), _)
+ Expr = unify(X, _, _, Kind, _)
->
RptaInfo = rpta_info(Graph, _AlphaMapping),
- % Need to be regions reachable from X.
- rptg_reach_from_a_variable(Graph, ModuleInfo, ProcInfo, X,
- set.init, Reach_X),
-
- set.intersect(Reach_X, ToBeCreatedAndAllowed,
- ToBeCreatedAllowedAndReached),
- set.fold(
- record_instruction_before_prog_point(create_region_instr,
- ProgPoint, Graph),
- ToBeCreatedAllowedAndReached, !RegionInstructionProc)
- ;
- ( Expr = unify(_, _, _, deconstruct(_, _, _, _, _, _), _)
- ; Expr = unify(_, _, _, assign(_, _), _)
- ; Expr = unify(_, _, _, simple_test(_, _), _)
- ; Expr = unify(_, _, _, complicated_unify(_, _, _), _)
- ; Expr = plain_call(_, _, _, _, _, _)
- ; Expr = conj(_, [])
- ; Expr = disj([])
- )
- ->
- true
- ;
- unexpected(this_file, "transformation_rule_2: non-atomic goal found")
- ).
-
- % Transformation rule 3: if a region is live before q but it is not
- % live after q and it is not removed by q, the caller will remove it
- % after calling q.
- %
- % There are two cases: either q is defined in this module or q is
- % imported.
- % The former is straightforward because we have the analysis information
- % for q.
- % The latter for now, with the assumption that all source code is in
- % only one module, imported preds will only be ones from
- % Mercury's library. We do not intent to deal with the library's code
- % now therefore we have to assume here that the caller will always
- % REMOVE the REGIONs for those procedures.
- %
-:- pred transformation_rule_3(hlds_goal_expr::in, program_point::in,
- region_set::in, rpta_info::in, proc_region_set_table::in,
- region_instr_proc::in, region_instr_proc::out) is det.
-
-transformation_rule_3(Expr, ProgPoint, ToBeRemovedAndAllowed, CallerRptaInfo,
- DeadRTable, !RegionInstructionProc) :-
- (
- Expr = plain_call(CalleePredId, CalleeProcId, _, _, _, _)
- ->
- CalleePPId = proc(CalleePredId, CalleeProcId),
- CallerRptaInfo = rpta_info(CallerGraph, AlphaMapping),
- ( map.search(DeadRTable, CalleePPId, _) ->
- map.lookup(AlphaMapping, ProgPoint, AlphaAtProgPoint),
+ (
+ Kind = construct(_, _, _, _, _, _, _),
+ % Rule 2: if a region reachable from the left variable of a
+ % construction is not live before the construction but it is live
+ % after and p is allowed to create it, then the region is
+ % created before the unification.
+
+ % Regions reachable from X.
+ rptg_reach_from_a_variable(Graph, ModuleInfo, ProcInfo, X,
+ set.init, Reach_X),
- map.lookup(DeadRTable, CalleePPId, CalleeDeadR),
- map.foldl(
- process_mapping_rule_3(ProgPoint, ToBeRemovedAndAllowed,
- CalleeDeadR, CallerGraph),
- AlphaAtProgPoint, !RegionInstructionProc)
+ set.intersect(Reach_X, BecomeLive, CreatedBeforeProgPoint)
;
- % q is from an imported module. So just remove whatever regions
- % become dead provided that p is allowed to remove those
- % regions.
- set.fold(
- record_instruction_after_prog_point(remove_region_instr,
- ProgPoint, CallerGraph),
- ToBeRemovedAndAllowed, !RegionInstructionProc)
- )
+ ( Kind = deconstruct(_, _, _, _, _, _)
+ ; Kind = assign(_, _)
+ ; Kind = simple_test(_, _)
+ ; Kind = complicated_unify(_, _, _)
+ ),
+ CreatedBeforeProgPoint = set.init
+ ),
+ % Rule 4: if a region is live before a unification but
+ % it is not live after and p is allowed to remove it,
+ % then it is removed after the unification.
+ %
+ RemovedAfterProgPoint = BecomeDead
+ ;
+ Expr = switch(_, _, _)
+ ->
+ % Special treatment for an atomic switch, i.e. a deconstruction
+ % unification that has been removed by MMC. We record the remove
+ % annotations after the program point.
+ %
+ CreatedBeforeProgPoint = set.init,
+ RemovedAfterProgPoint = BecomeDead
;
- ( Expr = unify(_, _, _, _, _)
- ; Expr = conj(_, [])
+ ( Expr = conj(_, [])
; Expr = disj([])
)
->
- true
+ CreatedBeforeProgPoint = set.init,
+ RemovedAfterProgPoint = set.init
;
- unexpected(this_file, "transformation_rule_3: non-atomic goal found")
+ unexpected(this_file, "annotate_expr: non-atomic goal found")
).
-:- pred process_mapping_rule_3(program_point::in, region_set::in,
- region_set::in, rpt_graph::in, rptg_node::in, rptg_node::in,
- region_instr_proc::in, region_instr_proc::out) is det.
+ % This predicate ensures that, out of the regions that become live at
+ % the call, we only explicitly create ones that are not created by the
+ % call.
+ %
+:- pred process_mapping_rule_1(region_set::in, region_set::in, rptg_node::in,
+ rptg_node::in, region_set::in, region_set::out) is det.
-process_mapping_rule_3(ProgPoint, ToBeRemovedAndAllowed, CalleeDeadR,
- CallerGraph, SourceRegion, TargetRegion, !RegionInstructionProc) :-
+process_mapping_rule_1(BecomeLive, CalleeBornR,
+ SourceRegion, TargetRegion, !CreatedBeforeProgPoint) :-
(
- set.contains(ToBeRemovedAndAllowed, TargetRegion),
- not set.contains(CalleeDeadR, SourceRegion)
+ set.contains(BecomeLive, TargetRegion),
+ not set.contains(CalleeBornR, SourceRegion)
->
- record_instruction_after_prog_point(remove_region_instr,
- ProgPoint, CallerGraph, TargetRegion, !RegionInstructionProc)
+ svset.insert(TargetRegion, !CreatedBeforeProgPoint)
;
true
).
- % Transformation rule 4: if a region is live before a unification but
- % it is not live after and it is in the dead region set or is a local
- % region, then it is removed after the unification if the current
- % procedure is allowed to remove it.
+ % This predicate ensures that, out of the regions that become dead at
+ % the call, we only explicitly remove ones that are not removed by the
+ % call.
%
-:- pred transformation_rule_4(hlds_goal_expr::in, program_point::in,
- region_set::in, rpta_info::in, region_instr_proc::in,
- region_instr_proc::out) is det.
+:- pred process_mapping_rule_3(region_set::in, region_set::in,
+ rptg_node::in, rptg_node::in, region_set::in, region_set::out) is det.
-transformation_rule_4(Expr, ProgPoint, ToBeRemovedAndAllowed, RptaInfo,
- !RegionInstructionProc) :-
+process_mapping_rule_3(BecomeDead, CalleeDeadR, SourceRegion,
+ TargetRegion, !RemovedAfterProgPoint) :-
(
- Expr = unify(_, _, _, _, _)
+ set.contains(BecomeDead, TargetRegion),
+ not set.contains(CalleeDeadR, SourceRegion)
->
- RptaInfo = rpta_info(Graph, _),
- set.fold(
- record_instruction_after_prog_point(remove_region_instr,
- ProgPoint, Graph),
- ToBeRemovedAndAllowed, !RegionInstructionProc)
+ svset.insert(TargetRegion, !RemovedAfterProgPoint)
;
- ( Expr = plain_call(_, _, _, _, _, _)
- ; Expr = conj(_, [])
- ; Expr = disj([])
- )
- ->
true
- ;
- unexpected(this_file, "transformation_rule_4: non-atomic goal found")
).
- % This is for the case rule 4 applied for a unification in a switch,
- % the unification has been removed by MMC.
- % We will record the annotations after the program point.
- %
-:- pred transformation_rule_4_2(program_point::in, region_set::in,
- rpta_info::in, region_instr_proc::in, region_instr_proc::out)
- is det.
-
-transformation_rule_4_2(ProgPoint, ToBeRemovedAndAllowed, RptaInfo,
- !RegionInstructionProc) :-
- RptaInfo = rpta_info(Graph, _),
- set.fold(
- record_instruction_after_prog_point(remove_region_instr,
- ProgPoint, Graph),
- ToBeRemovedAndAllowed, !RegionInstructionProc).
-
:- pred record_instruction_after_prog_point(region_instr_type::in,
program_point::in, rpt_graph::in, rptg_node::in,
region_instr_proc::in, region_instr_proc::out) is det.
Index: rbmm.region_resurrection_renaming.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/rbmm.region_resurrection_renaming.m,v
retrieving revision 1.6
diff -u -r1.6 rbmm.region_resurrection_renaming.m
--- rbmm.region_resurrection_renaming.m 8 Apr 2008 20:12:17 -0000 1.6
+++ rbmm.region_resurrection_renaming.m 23 Apr 2009 08:20:20 -0000
@@ -66,21 +66,19 @@
:- type join_point_region_name_table ==
map(pred_proc_id, map(program_point, string)).
- % This predicate traveses execution paths and computes two pieces of
- % information:
- % 1. The set of regions that become live before a program point
- % (for each program point in a procedure).
- % 2. For each procedure, compute the execution paths in which
- % resurrections of regions happen. For such an execution path
- % it also calculates the regions which resurrect. Only procedures
- % which contain resurrection are kept in the results. And for such
- % procedures only execution paths that contain resurrection are
- % kept.
+ % This predicate traveses execution paths and detects ones in which
+ % resurrections of regions happen.
+ % For such an execution path it also calculates the regions which
+ % resurrect. Only procedures which contain resurrection are kept in the
+ % results. And for such procedures only execution paths that contain
+ % resurrection are kept.
%
:- pred compute_resurrection_paths(execution_path_table::in,
proc_pp_region_set_table::in, proc_pp_region_set_table::in,
proc_region_set_table::in, proc_region_set_table::in,
- proc_pp_region_set_table::out, proc_resurrection_path_table::out) is det.
+ proc_region_set_table::in,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::in,
+ proc_pp_region_set_table::in, proc_resurrection_path_table::out) is det.
% Collect join points in procedures.
% The purpose of finding join points in a procedure is because if a region
@@ -169,43 +167,45 @@
%-----------------------------------------------------------------------------%
- % This predicate traveses execution paths and computes 2 pieces of
- % information:
- % 1. The set of regions that become live before a program point
- % (for each program point in a procedure).
- % 2. For each procedure, compute the execution paths in which
- % resurrections of regions happen. For such an execution path
- % it also calculates the regions which resurrect. Only procedures
- % which contain resurrection are kept in the results. And for such
- % procedures only execution paths that contain resurrection are
- % kept.
+ % This predicate traveses execution paths and detects ones in which
+ % resurrections of regions happen.
+ % For such an execution path it also calculates the regions which
+ % resurrect. Only procedures which contain resurrection are kept in the
+ % results. And for such procedures only execution paths that contain
+ % resurrection are kept.
%
compute_resurrection_paths(ExecPathTable, LRBeforeTable, LRAfterTable,
- BornRTable, LocalRTable, CreatedBeforeTable,
+ BornRTable, DeadRTable, LocalRTable,
+ BecomeLiveTable, BecomeDeadBeforeTable, BecomeDeadAfterTable,
PathContainsResurrectionTable) :-
- map.foldl2(compute_resurrection_paths_proc(LRBeforeTable, LRAfterTable,
- BornRTable, LocalRTable), ExecPathTable,
- map.init, CreatedBeforeTable,
- map.init, PathContainsResurrectionTable).
+ map.foldl(compute_resurrection_paths_proc(LRBeforeTable, LRAfterTable,
+ BornRTable, DeadRTable, LocalRTable,
+ BecomeLiveTable, BecomeDeadBeforeTable, BecomeDeadAfterTable),
+ ExecPathTable, map.init, PathContainsResurrectionTable).
:- pred compute_resurrection_paths_proc(proc_pp_region_set_table::in,
proc_pp_region_set_table::in, proc_region_set_table::in,
- proc_region_set_table::in, pred_proc_id::in, list(execution_path)::in,
- proc_pp_region_set_table::in, proc_pp_region_set_table::out,
+ proc_region_set_table::in, proc_region_set_table::in,
+ proc_pp_region_set_table::in, proc_pp_region_set_table::in,
+ proc_pp_region_set_table::in, pred_proc_id::in, list(execution_path)::in,
proc_resurrection_path_table::in, proc_resurrection_path_table::out)
is det.
-compute_resurrection_paths_proc(LRBeforeTable, LRAfterTable, BornRTable,
- LocalRTable, PPId, ExecPaths, !CreatedBeforeTable,
- !PathContainsResurrectionTable) :-
+compute_resurrection_paths_proc(LRBeforeTable, LRAfterTable,
+ BornRTable, DeadRTable, LocalRTable,
+ BecomeLiveTable, BecomeDeadBeforeTable, BecomeDeadAfterTable,
+ PPId, ExecPaths, !PathContainsResurrectionTable) :-
map.lookup(LRBeforeTable, PPId, LRBeforeProc),
map.lookup(LRAfterTable, PPId, LRAfterProc),
- map.lookup(BornRTable, PPId, BornRProc),
- map.lookup(LocalRTable, PPId, LocalRProc),
- list.foldl2(compute_resurrection_paths_exec_path(LRBeforeProc,
- LRAfterProc, set.union(BornRProc, LocalRProc)), ExecPaths,
- map.init, CreatedBeforeProc, map.init, PathContainsResurrectionProc),
- svmap.set(PPId, CreatedBeforeProc, !CreatedBeforeTable),
+ map.lookup(BornRTable, PPId, _BornR),
+ map.lookup(DeadRTable, PPId, _DeadR),
+ map.lookup(LocalRTable, PPId, _LocalR),
+ map.lookup(BecomeLiveTable, PPId, BecomeLiveProc),
+ map.lookup(BecomeDeadBeforeTable, PPId, BecomeDeadBeforeProc),
+ map.lookup(BecomeDeadAfterTable, PPId, BecomeDeadAfterProc),
+ list.foldl(compute_resurrection_paths_exec_path(LRBeforeProc, LRAfterProc,
+ BecomeLiveProc, BecomeDeadBeforeProc, BecomeDeadAfterProc), ExecPaths,
+ map.init, PathContainsResurrectionProc),
% We only want to include procedures in which resurrection happens in this
% map.
( map.count(PathContainsResurrectionProc) = 0 ->
@@ -216,16 +216,17 @@
).
:- pred compute_resurrection_paths_exec_path(pp_region_set_table::in,
- pp_region_set_table::in, region_set::in, execution_path::in,
- pp_region_set_table::in, pp_region_set_table::out,
+ pp_region_set_table::in, pp_region_set_table::in,
+ pp_region_set_table::in, pp_region_set_table::in, execution_path::in,
exec_path_region_set_table::in, exec_path_region_set_table::out) is det.
-compute_resurrection_paths_exec_path(LRBeforeProc, LRAfterProc, Born_Local,
- ExecPath, !CreatedBeforeProc, !ResurrectedRegionProc) :-
+compute_resurrection_paths_exec_path(LRBeforeProc, LRAfterProc,
+ BecomeLiveProc, BecomeDeadBeforeProc, BecomeDeadAfterProc,
+ ExecPath, !ResurrectedRegionProc) :-
list.foldl3(compute_resurrection_paths_prog_point(LRBeforeProc,
- LRAfterProc, Born_Local), ExecPath,
- set.init, _, !CreatedBeforeProc,
- set.init, ResurrectedRegionsInExecPath),
+ LRAfterProc, BecomeLiveProc, BecomeDeadBeforeProc,
+ BecomeDeadAfterProc), ExecPath,
+ set.init, _, set.init, _, set.init, ResurrectedRegionsInExecPath),
% We want to record only execution paths in which resurrections happen.
( set.empty(ResurrectedRegionsInExecPath) ->
true
@@ -235,32 +236,41 @@
).
:- pred compute_resurrection_paths_prog_point(pp_region_set_table::in,
- pp_region_set_table::in, region_set::in,
+ pp_region_set_table::in, pp_region_set_table::in,
+ pp_region_set_table::in, pp_region_set_table::in,
pair(program_point, hlds_goal)::in, region_set::in, region_set::out,
- pp_region_set_table::in, pp_region_set_table::out,
- region_set::in, region_set::out) is det.
+ region_set::in, region_set::out, region_set::in, region_set::out) is det.
-compute_resurrection_paths_prog_point(LRBeforeProc, LRAfterProc, Born_Local,
- ProgPoint - _, !Candidates, !CreatedBeforeProc,
+compute_resurrection_paths_prog_point(LRBeforeProc, LRAfterProc,
+ BecomeLiveProc, BecomeDeadBeforeProc, BecomeDeadAfterProc,
+ ProgPoint - _, !CreatedCandidates, !RemovedCandidates,
!ResurrectedRegionsInExecPath) :-
- map.lookup(LRBeforeProc, ProgPoint, LRBeforeProgPoint),
- map.lookup(LRAfterProc, ProgPoint, LRAfterProgPoint),
+ map.lookup(LRBeforeProc, ProgPoint, _LRBeforeProgPoint),
+ map.lookup(LRAfterProc, ProgPoint, _LRAfterProgPoint),
+ map.lookup(BecomeLiveProc, ProgPoint, BecomeLiveProgPoint),
+ map.lookup(BecomeDeadBeforeProc, ProgPoint, BecomeDeadBeforeProgPoint),
+ map.lookup(BecomeDeadAfterProc, ProgPoint, BecomeDeadAfterProgPoint),
+ set.union(BecomeDeadAfterProgPoint, BecomeDeadBeforeProgPoint,
+ BecomeDeadAtProgPoint),
+
+ % Resurrected regions:
+ % either become live at more than one program point
+ % or become dead at more than one program point in an execution path.
+ set.intersect(!.CreatedCandidates, BecomeLiveProgPoint,
+ CreatedResurrectedRegions),
+ set.union(CreatedResurrectedRegions, !ResurrectedRegionsInExecPath),
+
+ set.intersect(!.RemovedCandidates, BecomeDeadAtProgPoint,
+ RemovedResurrectedRegions),
+ set.union(RemovedResurrectedRegions, !ResurrectedRegionsInExecPath),
+
+ % When a region is known to become live or become dead
+ % at one program point, it is considered a candidate for resurrection.
+ set.difference(set.union(!.CreatedCandidates, BecomeLiveProgPoint),
+ !.ResurrectedRegionsInExecPath, !:CreatedCandidates),
- % Regions which are created before this program point.
- set.intersect(Born_Local,
- set.difference(LRAfterProgPoint, LRBeforeProgPoint),
- CreatedBeforeProgPoint),
- svmap.set(ProgPoint, CreatedBeforeProgPoint, !CreatedBeforeProc),
-
- % Resurrected regions become live at more than one program point in an
- % execution path.
- set.intersect(!.Candidates, CreatedBeforeProgPoint, ResurrectedRegions),
- set.union(ResurrectedRegions, !ResurrectedRegionsInExecPath),
-
- % When a region is known to become live at one program point, it is
- % considered a candidate for resurrection.
- set.difference(set.union(!.Candidates, CreatedBeforeProgPoint),
- !.ResurrectedRegionsInExecPath, !:Candidates).
+ set.difference(set.union(!.RemovedCandidates, BecomeDeadAtProgPoint),
+ !.ResurrectedRegionsInExecPath, !:RemovedCandidates).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -424,10 +434,10 @@
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
-collect_region_resurrection_renaming(CreatedBeforeTable, LocalRTable,
+collect_region_resurrection_renaming(BecomeLiveTable, LocalRTable,
RptaInfoTable, PathContainsResurrectionTable,
ResurrectionRenameTable) :-
- map.foldl(collect_region_resurrection_renaming_proc(CreatedBeforeTable,
+ map.foldl(collect_region_resurrection_renaming_proc(BecomeLiveTable,
LocalRTable, RptaInfoTable), PathContainsResurrectionTable,
map.init, ResurrectionRenameTable).
@@ -437,15 +447,15 @@
map(execution_path, region_set)::in, renaming_table::in,
renaming_table::out) is det.
-collect_region_resurrection_renaming_proc(CreatedBeforeTable, _LocalRTable,
+collect_region_resurrection_renaming_proc(BecomeLiveTable, _LocalRTable,
RptaInfoTable, PPId, PathsContainResurrection,
!ResurrectionRenameTable) :-
- map.lookup(CreatedBeforeTable, PPId, CreatedBeforeProc),
+ map.lookup(BecomeLiveTable, PPId, BecomeLiveProc),
map.lookup(RptaInfoTable, PPId, RptaInfo),
RptaInfo = rpta_info(Graph, _),
map.foldl(
collect_region_resurrection_renaming_exec_path(Graph,
- CreatedBeforeProc),
+ BecomeLiveProc),
PathsContainResurrection, map.init, ResurrectionRenameProc),
svmap.set(PPId, ResurrectionRenameProc, !ResurrectionRenameTable).
@@ -454,11 +464,11 @@
region_set::in, renaming_proc::in,
renaming_proc::out) is det.
-collect_region_resurrection_renaming_exec_path(Graph, CreatedBeforeProc,
+collect_region_resurrection_renaming_exec_path(Graph, BecomeLiveProc,
ExecPath, ResurrectedRegions, !ResurrectionRenameProc) :-
list.foldl2(
collect_region_resurrection_renaming_prog_point(Graph,
- CreatedBeforeProc, ResurrectedRegions),
+ BecomeLiveProc, ResurrectedRegions),
ExecPath, counter.init(0), _, !ResurrectionRenameProc).
:- pred collect_region_resurrection_renaming_prog_point(rpt_graph::in,
@@ -466,11 +476,11 @@
pair(program_point, hlds_goal)::in, counter::in, counter::out,
renaming_proc::in, renaming_proc::out) is det.
-collect_region_resurrection_renaming_prog_point(Graph, CreatedBeforeProc,
+collect_region_resurrection_renaming_prog_point(Graph, BecomeLiveProc,
ResurrectedRegions, ProgPoint - _, !RenamingCounter,
!ResurrectionRenameProc) :-
- map.lookup(CreatedBeforeProc, ProgPoint, CreatedBeforeProgPoint),
- set.intersect(ResurrectedRegions, CreatedBeforeProgPoint,
+ map.lookup(BecomeLiveProc, ProgPoint, BecomeLiveProgPoint),
+ set.intersect(ResurrectedRegions, BecomeLiveProgPoint,
ToBeRenamedRegions),
% We only record the program points where resurrection renaming exists.
( set.empty(ToBeRenamedRegions) ->
@@ -506,7 +516,7 @@
% Collect renaming at each program point.
%
% A renaming at a program point will be applied to annotations attached
-% to before and after it. If the associated (atomic) goal is procedure call
+% to before and after it. If the associated (atomic) goal is a procedure call
% then the renaming is also applied to its actual region arguments. If the
% goal is a construction the renaming is applied to the regions of the left
% variable.
More information about the reviews
mailing list