diff: output module dependency ordering

[Simon Taylor]

Hi,

Could someone please review this?

Simon.


Estimated hours taken: 1

Added option --generate-module-ordering which prints out the module 
during dependency generation. This is useful for improving the 
effectiveness of termination analysis. 

compiler/options.m
compiler/handle_options.m
	Added option --generate-module-ordering.

compiler/modules.m
	Compute and print out the ordering.	

doc/user_guide.texi
	Document --generate-module-ordering.


Index: handle_options.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/handle_options.m,v
retrieving revision 1.32
diff -u -r1.32 handle_options.m
--- handle_options.m	1997/10/09 09:38:36	1.32
+++ handle_options.m	1997/10/15 00:45:26
@@ -303,6 +303,11 @@
 	option_implies(make_optimization_interface, optimize_unused_args,
 		bool(no)),
 
+	% The information needed for generating the module ordering
+	% is only available while generating the dependencies.
+	option_implies(generate_module_order, generate_dependencies,
+		bool(yes)),
+
 	% If --use-search-directories-for-intermod is true, append the
 	% search directories to the list of directories to search for
 	% .opt files.
Index: modules.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/modules.m,v
retrieving revision 1.41
diff -u -r1.41 modules.m
--- modules.m	1997/10/09 09:38:59	1.41
+++ modules.m	1997/10/15 02:27:29
@@ -147,7 +147,7 @@
 :- import_module passes_aux, prog_out, mercury_to_mercury.
 :- import_module prog_io_util, globals, options, intermod, module_qual.
 :- import_module bool, string, set, map, term, varset, dir, std_util, library.
-
+:- import_module assoc_list, relation.
 
 	% Read in the .int3 files that the current module depends on,
 	% and use these to qualify all items in the interface as much as
@@ -610,6 +610,7 @@
 	% check whether we couldn't read the main `.m' file
 	%
 	{ map__lookup(DepsMap, Module, deps(_, Error, _, _, _)) },
+	globals__io_lookup_bool_option(verbose, Verbose),
 	( { Error = fatal } ->
 	    { string__append_list(["fatal error reading module `",
 				Module, "'."], Message) },
@@ -619,22 +620,54 @@
 	    % now, write the `.dep' file
 	    %
 	    { string__append(Module, ".dep", DepFileName) },
-	    globals__io_lookup_bool_option(verbose, Verbose),
 	    maybe_write_string(Verbose, "% Creating auto-dependency file `"),
 	    maybe_write_string(Verbose, DepFileName),
 	    maybe_write_string(Verbose, "'...\n"),
-	    io__open_output(DepFileName, Result),
-	    ( { Result = ok(DepStream) } ->
+	    io__open_output(DepFileName, DepResult),
+	    ( { DepResult = ok(DepStream) } ->
 		generate_dep_file(Module, DepsMap, DepStream),
 		io__close_output(DepStream),
 		maybe_write_string(Verbose, "% done\n")
 	    ;
 		{ string__append_list(["can't open file `", DepFileName,
-				"' for output."], Message) },
-		report_error(Message)
+				"' for output."], DepMessage) },
+		report_error(DepMessage)
+	    ),
+	    globals__io_lookup_bool_option(generate_module_order, Order),
+	    ( { Order = yes } ->
+	  	{ string__append(Module, ".order", OrdFileName) },
+		maybe_write_string(Verbose, "% Creating module order file `"),
+		maybe_write_string(Verbose, OrdFileName),
+		maybe_write_string(Verbose, "'...\n"),
+		io__open_output(OrdFileName, OrdResult),
+		( { OrdResult = ok(OrdStream) } ->
+		    { relation__init(DepsRel0) },
+		    { map__to_assoc_list(DepsMap, DepsList) },
+		    { deps_map_to_deps_rel(DepsList, DepsMap, 
+				DepsRel0, DepsRel) },
+		    { relation__atsort(DepsRel, DepsOrdering) },
+		    io__write_list(OrdStream, DepsOrdering, "\n\n", 
+		    		write_module_scc(OrdStream)),
+		    io__close_output(OrdStream),
+		    maybe_write_string(Verbose, "% done\n")
+		;
+		    { string__append_list(["can't open file `", 
+				OrdFileName, "' for output."], OrdMessage) },
+		    report_error(OrdMessage)
+		)
+	    ;
+		[]
 	    )
 	).
 
+:- pred write_module_scc(io__output_stream::in, set(module_name)::in,
+		io__state::di, io__state::uo) is det.
+
+write_module_scc(Stream, SCC0) -->
+	{ set__to_sorted_list(SCC0, SCC) },
+	io__write_list(Stream, SCC, "\n", io__write_string).
+
+
 % This is the data structure we use to record the dependencies.
 % We keep a map from module name to information about the module.
 
@@ -648,6 +681,9 @@
 		list(string)	% fact table dependencies
 	).
 
+	% deps_rel(Module1, Module2) means Module1 is imported by Module2.
+:- type deps_rel == relation(string).
+
 % This is the predicate which creates the above data structure.
 
 :- pred generate_deps_map(list(string), deps_map, deps_map,
@@ -686,6 +722,30 @@
 		% Recursively process the remaining modules
 	generate_deps_map(Modules2, DepsMap3, DepsMap).
 
+
+	% Construct a dependency relation of all the modules in the program.
+:- pred deps_map_to_deps_rel(assoc_list(string, deps), deps_map,
+		deps_rel, deps_rel).
+:- mode deps_map_to_deps_rel(in, in, in, out) is det.
+
+deps_map_to_deps_rel([], _, Rel, Rel).
+deps_map_to_deps_rel([Module - Deps | DepsList], DepsMap, Rel0, Rel) :-
+	Deps = deps(_, ModuleError, IntDeps, ImplDeps, _),
+	( ModuleError \= fatal ->
+		relation__add_element(Rel0, Module, ModuleRelKey, Rel1),
+		AddDeps =
+		    lambda([Dep::in, Relation0::in, Relation::out] is det, (
+			relation__add_element(Relation0, Dep,
+				DepRelKey, Relation1),
+			relation__add(Relation1, DepRelKey,
+				ModuleRelKey, Relation)
+		    )),
+		list__foldl(AddDeps, IntDeps, Rel1, Rel2),
+		list__foldl(AddDeps, ImplDeps, Rel2, Rel3)
+	;
+		Rel3 = Rel0
+	),
+	deps_map_to_deps_rel(DepsList, DepsMap, Rel3, Rel).
 
 % Write out the `.dep' file, using the information collected in the
 % deps_map data structure.
Index: options.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/options.m,v
retrieving revision 1.207
diff -u -r1.207 options.m
--- options.m	1997/10/09 09:39:02	1.207
+++ options.m	1997/10/15 02:20:57
@@ -74,6 +74,7 @@
 		;	make_optimization_interface
 		;	make_transitive_opt_interface
 		;	generate_dependencies
+		;	generate_module_order
 		;	convert_to_mercury
 		;	convert_to_goedel
 		;	typecheck_only
@@ -301,6 +302,7 @@
 option_defaults_2(output_option, [
 		% Output Options (mutually exclusive)
 	generate_dependencies	-	bool(no),
+	generate_module_order 	-	bool(no),
 	make_short_interface	-	bool(no),
 	make_interface		-	bool(no),
 	make_optimization_interface -	bool(no),
@@ -578,6 +580,7 @@
 
 % output options (mutually exclusive)
 long_option("generate-dependencies",	generate_dependencies).
+long_option("generate-module-order",	generate_module_order).
 long_option("make-short-interface",	make_short_interface).
 long_option("make-short-int",		make_short_interface).
 long_option("make-interface",		make_interface).
@@ -1144,6 +1147,11 @@
 	io__write_string("\t-M, --generate-dependencies\n"),
 	io__write_string("\t\tOutput `Make'-style dependencies for the module\n"),
 	io__write_string("\t\tand all of its dependencies to `<module>.dep'.\n"),
+	io__write_string("\t--generate-module-order\n"),
+	io__write_string("\t\tOutput the strongly connected components of the module\n"),
+	io__write_string("\t\tdependency graph in top-down order to `<module>.order'.\n"),
+	io__write_string("\t\tImplies --generate-dependencies.\n"),
+
 	io__write_string("\t-i, --make-int, --make-interface\n"),
 	io__write_string("\t\tWrite the module interface to `<module>.int',\n"),
 	io__write_string("\t\tand write the short interface to `<module>.int2'\n"),
Index: user_guide.texi
===================================================================
RCS file: /home/staff/zs/imp/mercury/doc/user_guide.texi,v
retrieving revision 1.100
diff -u -r1.100 user_guide.texi
--- user_guide.texi	1997/10/09 09:39:41	1.100
+++ user_guide.texi	1997/10/15 02:20:11
@@ -1292,6 +1292,11 @@
 Output ``Make''-style dependencies for the module
 and all of its dependencies to @file{@var{module}.dep}.
 
+ at item --generate-module-order
+Output the strongly connected components of the module 
+dependency graph in top-down order to @file{@var{module}.order}.
+Implies --generate-dependencies.
+
 @sp 1
 @item -i
 @itemx --make-int