[m-dev.] [reuse] diff: new structure reuse structure

Peter Ross petdr at miscrit.be
Wed Oct 4 23:59:28 AEDT 2000
Previous message: [m-dev.] for review: two new kul papers
Next message: [m-dev.] [reuse] diff: lfu and lbu passes
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Hi,


===================================================================


Estimated hours taken: 2

The new structure for the structure reuse analysis, currently these
modules are just stubs.

mercury_compile.m:
    Call the new module, but disregard its output.

structure_reuse.m:
    The top level module, its work is divided into two phases: sr_direct
    and sr_indirect.

sr_direct.m:
    Do the direct reuse analysis.

sr_indirect.m:
    Do the indirect reuse analysis.

sr_dead.m:
    Phase 1 of the direct reuse analysis where we determine which cells
    become available for reuse.

sr_choice.m:
    Phase 2 of the the direct reuse analysis where we determine which
    cells will be reused.
    
sr_data.m:
    Common data structures shared between the various modules.


Index: mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.175.2.5
diff -u -r1.175.2.5 mercury_compile.m
--- mercury_compile.m	2000/10/02 11:44:42	1.175.2.5
+++ mercury_compile.m	2000/10/04 12:54:49
@@ -43,7 +43,7 @@
 :- import_module check_typeclass, intermod, trans_opt, table_gen, (lambda).
 :- import_module type_ctor_info, termination, higher_order, accumulator.
 :- import_module inlining, deforest, dnf, magic, dead_proc_elim.
-:- import_module unused_args, unneeded_code, lco.
+:- import_module unused_args, unneeded_code, lco, structure_reuse.
 
 	% the LLDS back-end
 :- import_module saved_vars, liveness.
@@ -1662,6 +1662,10 @@
 		maybe_write_string(Verbose, "% Structure-reuse analysis...\n"),
 		maybe_flush_output(Verbose),
 		sr_run__structure_reuse_pass( HLDS0, HLDS), 
+
+			% XXX plug in the new structure reuse framework
+		structure_reuse(HLDS0, _),
+
 		maybe_write_string(Verbose, "% done.\n"),
 		maybe_report_stats(Stats)
 	;
Index: sr_choice.m
===================================================================
RCS file: sr_choice.m
diff -N sr_choice.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ sr_choice.m	Wed Oct  4 23:54:58 2000
@@ -0,0 +1,39 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 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.
+%-----------------------------------------------------------------------------%
+%
+% Module:	sr_choice
+% Main authors: petdr
+% 
+% Given a goal annotated with information about which cells are
+% canditates for reuse and a strategy determine which cells will
+% actually be reused and the conditions that reuse implies on the head
+% variables.
+%
+%-----------------------------------------------------------------------------%
+
+:- module sr_choice.
+:- interface.
+
+:- import_module hlds_goal, sr_data.
+:- import_module list, std_util.
+
+:- type strategy
+	--->	same_cons_id.
+
+:- pred sr_choice__process_goal(strategy::in, hlds_goal::in, hlds_goal::out,
+		maybe(list(reuse_condition))::out) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+process_goal(_Strategy, Goal0, Goal, MaybeReuseConditions) :-
+	Goal = Goal0,
+	MaybeReuseConditions = no.
+	
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: sr_data.m
===================================================================
RCS file: sr_data.m
diff -N sr_data.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ sr_data.m	Wed Oct  4 23:54:59 2000
@@ -0,0 +1,39 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 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.
+%-----------------------------------------------------------------------------%
+%
+% Module:	sr_data
+% Main authors: nancy
+% 
+% The data structures which are shared between the various phases of the
+% structure reuse analysis.
+%
+%-----------------------------------------------------------------------------%
+
+:- module sr_data.
+:- interface.
+
+:- import_module pa_alias_as, pa_datastruct, prog_data.
+:- import_module list, set.
+
+	% A reuse, whether direct or indirect, is only allowed as long
+	% as the caller fulfills some conditions.  This type keeps track
+	% of the information needed to verify whether the condition for
+	% reuse is met or not. 
+:- type reuse_condition
+	--->	always
+	;	condition(
+		   nodes 		:: list(pa_datastruct__datastruct),
+		   local_use_headvars 	:: set(prog_var),
+		   local_alias_headvars :: alias_as 
+		).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: sr_dead.m
===================================================================
RCS file: sr_dead.m
diff -N sr_dead.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ sr_dead.m	Wed Oct  4 23:54:59 2000
@@ -0,0 +1,33 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 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.
+%-----------------------------------------------------------------------------%
+%
+% Module:	sr_dead
+% Main authors: nancy
+% 
+% Mark each cell that dies with its reuse_condition, and mark each
+% construction with the cells that construction could possibly reuse.
+% sr_choice is responsivle for deciding which cell will actually be
+% reused.
+%
+%-----------------------------------------------------------------------------%
+
+:- module sr_dead.
+:- interface.
+
+:- import_module hlds_goal.
+
+:- pred sr_dead__process_goal(hlds_goal::in, hlds_goal::out) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+process_goal(Goal0, Goal) :-
+	Goal = Goal0.
+	
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: sr_direct.m
===================================================================
RCS file: sr_direct.m
diff -N sr_direct.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ sr_direct.m	Wed Oct  4 23:54:59 2000
@@ -0,0 +1,46 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 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.
+%-----------------------------------------------------------------------------%
+%
+% Module:	sr_direct
+% Main authors: nancy, petdr
+% 
+% Determine the direct reuse in one procedure.  Direct reuse consists of
+% identifying which cells die.
+%
+%-----------------------------------------------------------------------------%
+
+:- module sr_direct.
+:- interface.
+
+:- import_module hlds_module, hlds_pred, io.
+
+:- pred sr_direct__process_proc(pred_id::in, proc_id::in, proc_info::in,
+		proc_info::out, module_info::in, module_info::out,
+		io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module sr_lfu, sr_lbu, sr_dead, sr_choice.
+
+process_proc(_PredId, _ProcId, ProcInfo0, ProcInfo, ModuleInfo0, ModuleInfo) -->
+	% Determine the LFU (local forward use)
+
+	% Determine the LBU (local backward use)
+
+	% Determine which cells die and can be reused and what the
+	% conditions on that reuse are
+
+	% Select which cells will be reused and which can be compile
+	% time garbage collected.
+
+	{ ProcInfo = ProcInfo0 },
+	{ ModuleInfo = ModuleInfo0 }.
+	
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: sr_indirect.m
===================================================================
RCS file: sr_indirect.m
diff -N sr_indirect.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ sr_indirect.m	Wed Oct  4 23:54:59 2000
@@ -0,0 +1,31 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 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.
+%-----------------------------------------------------------------------------%
+%
+% Module:	sr_indirect
+% Main authors: nancy
+% 
+% Determine the indirect reuse.  This requires a fixpoint computation.
+%
+%-----------------------------------------------------------------------------%
+
+:- module sr_indirect.
+:- interface.
+
+:- import_module hlds_module, io.
+
+:- pred sr_indirect__compute_fixpoint(module_info::in, module_info::out,
+		io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+compute_fixpoint(ModuleInfo0, ModuleInfo) -->
+	{ ModuleInfo = ModuleInfo0 }.
+	
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: structure_reuse.m
===================================================================
RCS file: structure_reuse.m
diff -N structure_reuse.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ structure_reuse.m	Wed Oct  4 23:54:59 2000
@@ -0,0 +1,66 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2000 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.
+%-----------------------------------------------------------------------------%
+%
+% Module:	structure_reuse
+% Main authors: nancy, petdr
+%
+% The top level module for placing structure reuse annotations onto the
+% HLDS.
+%
+% Structure reuse is broken up into two phases: the direct reuse
+% analysis (sr_direct) and the indirect analysis (sr_indirect).
+% 
+% list__append(H1, H2, H3) :-
+% 	(
+% 		H1 => [],
+% 		H3 := H2
+% 	;
+% 			% Cell H1 dies provided some condition about the
+% 			% aliasing of H1 is true.  This is a direct
+% 			% reuse.
+% 		H1 => [X | Xs],
+%
+% 			% If the condition about the aliasing of H1
+% 			% is true then we can call the version of
+% 			% list__append which does reuse.
+% 			% This is an indirect reuse.
+% 		list__append(Xs, H2, Zs),
+%
+%			% Reuse the dead cell H1.  This is a direct
+%			% reuse.
+% 		H3 <= [X | Zs]
+% 	).
+%
+%-----------------------------------------------------------------------------%
+
+:- module structure_reuse.
+:- interface.
+
+:- import_module hlds_module.
+:- import_module io.
+
+:- pred structure_reuse(module_info::in, module_info::out,
+		io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module passes_aux, sr_direct, sr_indirect.
+
+structure_reuse(HLDS0, HLDS) -->
+		% Do the direct reuse analysis phase.
+	process_all_nonimported_procs(
+			update_module_io(sr_direct__process_proc),
+			HLDS0, HLDS1),
+
+		% Do the fixpoint computation to determine all the indirect
+		% reuse, and the implied conditions.
+	sr_indirect__compute_fixpoint(HLDS1, HLDS).
+	
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
Previous message: [m-dev.] for review: two new kul papers
Next message: [m-dev.] [reuse] diff: lfu and lbu passes
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the developers mailing list