[m-rev.] for review: further work on trail usage analysis/optimization

Julien Fischer juliensf at cs.mu.OZ.AU
Mon Nov 14 16:02:15 AEDT 2005
Previous message: [m-rev.] diff: fix bug in overloading resolution
Next message: [m-rev.] for review: further work on trail usage analysis/optimization
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
I've done some more timings for this.  The raw results are in
/home/saturn/juliensf/trailing/results.  For the hlc grades we definitely get
an improvement.  The following table shows the percentage time and space
increases for hlc.gc.tr (with and without the trail usage optimization)
relative to hlc.gc.

without intermodule-optimization
--------------------------------
hlc.gc vs. hlc.gc.tr (no opt)
	- 37.2% increase in time
	- 10.1% increase in space

hlc.gc vs. hlc.gc.tr (with opt)
	- 13.0% increase in time
	-  7.0% increase in space

with `--intermodule-optimization'
--------------------------------
hlc.gc vs. hlc.gc.tr (no opt)
	- 41.9% increase in time
	- 12.4% increase in space

hlc.gc vs. hlc.gc.tr (with opt)
	- 14.9% increase in time
	-  6.4% increase in space

with `--transitive-intermodule-optimization'
-------------------------------------------
hlc.gc vs. hlc.gc.tr (no opt)
	- 42.0% increase in time
	- 12.4% increase in space

hlc.gc. vs. hlc.gc.tr (with opt)
	- 14.4% increase in time
	-  6.3% increase in space


Estimated hours taken: 5
Branches: main

Further work on trail usage analysis and optimization.

compiler/mercury_compile.m:
	Move trail usage analysis from stage 123 to stage 167.
	The advantage of having it later is that compiler
	introduced predicates are also added to the trailing_info table.

compiler/trailing_analysis.m:
	Do not run this analysis unless we are compiling in a trailing grade.

	Add a table of (non-builtin) procedures from the standard library
	whose trailing status can be assumed to be known.  This works around
	some limitations in our current intermodule analysis framework and
	also improves trail usage optimization when we are compiling without
	any intermodule optimization.

	Fix some typos.

doc/user_guide.texi.m:
compiler/options.m:
	Document `--analyse-trail-usage' and `--optimize-trail-usage'.

doc/reference_manual.texi:
	Document the `will_not_modify_trail' and `may_modify_trail'
	foreign code attributes.

compiler/notes/compiler_design.html:
	Mention the trailing_analysis module.

Julien.

Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.360
diff -u -r1.360 mercury_compile.m
--- compiler/mercury_compile.m	12 Nov 2005 10:16:47 -0000	1.360
+++ compiler/mercury_compile.m	14 Nov 2005 03:29:21 -0000
@@ -2233,7 +2233,7 @@
     maybe_termination2(Verbose, Stats, !HLDS, !IO),
     maybe_dump_hlds(!.HLDS, 121, "termination_2", !DumpInfo, !IO),
     maybe_analyse_trail_usage(Verbose, Stats, !HLDS, !IO),
-    maybe_dump_hlds(!.HLDS, 123, "trailing analysis", !DumpInfo, !IO),
+    maybe_dump_hlds(!.HLDS, 167, "trail_usage", !DumpInfo, !IO),
     trans_opt__write_optfile(!.HLDS, !IO).

 :- pred frontend_pass_by_phases(module_info::in, module_info::out,
@@ -2347,12 +2347,6 @@

     maybe_termination2(Verbose, Stats, !HLDS, !IO),
     maybe_dump_hlds(!.HLDS, 121, "termination2", !DumpInfo, !IO),
-
-    % XXX We should actually do this after any optimizations
-    % that introduce new predicates, so that we can add them
-    % to the trailing_info table as well.
-    maybe_analyse_trail_usage(Verbose, Stats, !HLDS, !IO),
-    maybe_dump_hlds(!.HLDS, 123, "trail_usage", !DumpInfo, !IO),

     maybe_type_ctor_infos(Verbose, Stats, !HLDS, !IO),
     maybe_dump_hlds(!.HLDS, 125, "type_ctor_infos", !DumpInfo, !IO),
@@ -2397,6 +2391,9 @@

     maybe_unused_args(Verbose, Stats, !HLDS, !IO),
     maybe_dump_hlds(!.HLDS, 165, "unused_args", !DumpInfo, !IO),
+
+    maybe_analyse_trail_usage(Verbose, Stats, !HLDS, !IO),
+    maybe_dump_hlds(!.HLDS, 167, "trail_usage", !DumpInfo, !IO),

     maybe_unneeded_code(Verbose, Stats, !HLDS, !IO),
     maybe_dump_hlds(!.HLDS, 170, "unneeded_code", !DumpInfo, !IO),
Index: compiler/trailing_analysis.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/trailing_analysis.m,v
retrieving revision 1.1
diff -u -r1.1 trailing_analysis.m
--- compiler/trailing_analysis.m	8 Nov 2005 08:14:54 -0000	1.1
+++ compiler/trailing_analysis.m	14 Nov 2005 03:40:58 -0000
@@ -111,20 +111,26 @@
 %

 analyse_trail_usage(!ModuleInfo, !IO) :-
-    module_info_ensure_dependency_info(!ModuleInfo),
-    module_info_dependency_info(!.ModuleInfo, DepInfo),
-    hlds_dependency_info_get_dependency_ordering(DepInfo, SCCs),
-    globals.io_lookup_bool_option(debug_trail_usage, Debug, !IO),
-    list.foldl2(process_scc(Debug), SCCs, !ModuleInfo, !IO),
-    globals.io_lookup_bool_option(make_optimization_interface,
-        MakeOptInt, !IO),
+    globals.io_lookup_bool_option(use_trail, UseTrail, !IO),
     (
-        MakeOptInt = yes,
-        make_opt_int(!.ModuleInfo, !IO)
+        % Only run the analysis in trailing grades.
+        UseTrail = yes,
+        module_info_ensure_dependency_info(!ModuleInfo),
+        module_info_dependency_info(!.ModuleInfo, DepInfo),
+        hlds_dependency_info_get_dependency_ordering(DepInfo, SCCs),
+        globals.io_lookup_bool_option(debug_trail_usage, Debug, !IO),
+        list.foldl2(process_scc(Debug), SCCs, !ModuleInfo, !IO),
+        globals.io_lookup_bool_option(make_optimization_interface,
+            MakeOptInt, !IO),
+        (
+            MakeOptInt = yes,
+            make_opt_int(!.ModuleInfo, !IO)
+        ;
+            MakeOptInt = no
+        )
     ;
-        MakeOptInt = no
-    ).
-
+        UseTrail = no
+    ).
 %----------------------------------------------------------------------------%
 %
 % Perform trail usage analysis on a SCC
@@ -146,9 +152,8 @@
 process_scc(Debug, SCC, !ModuleInfo, !IO) :-
     ProcResults = check_procs_for_trail_mods(SCC, !.ModuleInfo),
     %
-    % The `Results' above are the results of analysing each
-    % individual procedure in the SCC - we now have to combine
-    % them in a meaningful way.
+    % The `Results' above are the results of analysing each individual
+    % procedure in the SCC - we now have to combine them in a meaningful way.
     %
     Status = combine_individual_proc_results(ProcResults),
     %
@@ -284,6 +289,17 @@
         % XXX This is far too conservative.
         Result = may_modify_trail
     ;
+        % Handle library predicates whose trailing status
+        % can be looked up in the known procedures table.
+        Name = pred_info_name(CallPredInfo),
+        PredOrFunc = pred_info_is_pred_or_func(CallPredInfo),
+        ModuleName = pred_info_module(CallPredInfo),
+        ModuleName = unqualified(ModuleNameStr),
+        Arity = pred_info_orig_arity(CallPredInfo),
+        known_procedure(PredOrFunc, ModuleNameStr, Name, Arity, Result0)
+    ->
+        Result = Result0
+    ;
         check_nonrecursive_call(ModuleInfo, VarTypes, CallPPId, CallArgs,
             Result)
     ).
@@ -318,8 +334,8 @@
     goal_info_get_code_model(InnerGoalInfo, InnerCodeModel),
     goal_info_get_code_model(OuterGoalInfo, OuterCodeModel),
     (
-        % If we're at a commit for goal that might modify the trail then
-        % we will need to emit some trailing code around the scope goal.
+        % If we're at a commit for Goal that might modify the trail then we
+        % will need to emit some trailing code around the scope goal.
         InnerCodeModel = model_non,
         OuterCodeModel \= model_non,
         Result0 \= will_not_modify_trail
@@ -374,7 +390,7 @@
         Result0 = will_not_modify_trail,
         Result  = will_not_modify_trail
     ;
-        % One or or more fo the disjuncts may modify the trail, so
+        % One or or more of the disjuncts may modify the trail, so
         % we need to emit the trailing code - XXX could do better by
         % specialising conditional code.
         ( Result0 = conditional ; Result0 = may_modify_trail),
@@ -392,6 +408,23 @@

 %----------------------------------------------------------------------------%
 %
+% "Known" library procedures
+%
+
+% known_procedure/4 is a table of library predicates whose trailing
+% status is hardcoded into the analyser.  For a few predicates this
+% information can make a big difference (particularly in the absence
+% of any form of intermodule analysis).
+
+:- pred known_procedure(pred_or_func::in, string::in, string::in, int::in,
+    trailing_status::out) is semidet.
+
+known_procedure(predicate, "require", "error", 1, will_not_modify_trail).
+known_procedure(function,  "require", "func_error", 1, will_not_modify_trail).
+known_procedure(_, "exception", "throw", 1, will_not_modify_trail).
+
+%----------------------------------------------------------------------------%
+%
 % Further code to handle higher-order variables
 %
     % Extract those procedures whose trailing_status has been set to
Index: compiler/notes/compiler_design.html
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/notes/compiler_design.html,v
retrieving revision 1.108
diff -u -r1.108 compiler_design.html
--- compiler/notes/compiler_design.html	4 Nov 2005 03:41:09 -0000	1.108
+++ compiler/notes/compiler_design.html	14 Nov 2005 03:45:39 -0000
@@ -923,6 +923,17 @@

 <p>

+Trail usage analysis. (trailing_analysis.m)
+
+<ul>
+<li>
+	This pass annotates each module with information about whether
+	the procedures in the module modify the trail or not.  This
+	information can be used to avoid redundant trailing operations.
+</ul>
+
+<p>
+
 Most of the remaining HLDS-to-HLDS transformations are optimizations:

 <ul>
Index: doc/reference_manual.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/reference_manual.texi,v
retrieving revision 1.336
diff -u -r1.336 reference_manual.texi
--- doc/reference_manual.texi	7 Nov 2005 07:47:10 -0000	1.336
+++ doc/reference_manual.texi	14 Nov 2005 03:51:47 -0000
@@ -6176,7 +6176,7 @@
 It is an error to apply this attribute to procedures that have determinism
 erroneous.  This attribute is ignored for code that is declared as not
 making calls back to Mercury via the @samp{will_not_call_mercury} attribute.
-Note: Predicates or functions that have polymorphic arguments but
+Note: predicates or functions that have polymorphic arguments but
 do not explicitly throw an exception, via a call to exception.throw/1
 or require.error/1, may still throw exceptions because they may be
 called with arguments whose types have user-defined equality or
@@ -6191,6 +6191,14 @@
 @c @item @samp{low_level_backend}
 @c The foreign_proc will apply only on the low level backend.

+ at item @samp{will_not_modify_trail/may_modify_trail}
+This attribute declares whether or not a foreign procedure modifies
+the trail (see @ref{Trailing}).  Specifying that a foreign procedure
+will not modify the trail may allow the compiler to generate more
+efficient code for that procedure.  In compilation grades that do not
+support trailing this attribute is ignored.  The default, in case
+none is specified, is @samp{may_modify_trail}.
+
 @end table

 @c -----------------------------------------------------------------------

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
Previous message: [m-rev.] diff: fix bug in overloading resolution
Next message: [m-rev.] for review: further work on trail usage analysis/optimization
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the reviews mailing list