[m-rev.] for review: speed up trailing in high-level C grades

Julien Fischer juliensf at cs.mu.OZ.AU
Thu Dec 15 17:50:57 AEDT 2005


Estimated hours taken: 6
Branches: main

Speed up trailing in high-level C grades.  The code for adding trailing
operations to the HLDS (in add_trail_ops.m) worked by inserting calls to the
trailing predicates defined in private_builtin.m.  These predicates in turn
call the macros defined in runtime/mercury_trailing.h.  The compiler was not
inlining the trailing predicates which was imposing a significant penalty on
the performance of trailing in the high-level C grades.

This diff modifies add_trail_ops.m so that it optionally generates inline
foreign_procs that call the trailing macros rather than generating calls to
library predicates.  For the compiler in grade hlc.gc.tr this results in a
23.4% speed increase at the cost of a 4% increase in executable size.  (Since
the two methods are compatible with each other there is scope for further
exploring this space/time tradeoff.)

XXX This needs to be documented properly.  Subject to further testing
    I intend to make the inlined foreign_proc method the default one, so
    I'll document it all properly then.

XXX The non-C backends will need to use the library call method at the
    moment but since trailing isn't really implemented for them that
    won't be too much of a problem ;-)

compiler/options.m:
	Add a new option `--generate-trail-ops-inline' that causes
	add_trail_ops.m to insert trail ops as inlined foreign_procs rather
	than calls to library predicates.

	XXX This still needs to be documented.

compiler/add_trail_ops.m:
	Support adding trailing operations directly to the HLDS as inlined
	foreign_procs rather than library calls.

	Give some predicates distinct names.

	Add myself to the list of authors for this module.

compiler/mercury_compile.m:
	Minor changes to conform to the above.

Julien.

Index: compiler/add_trail_ops.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/add_trail_ops.m,v
retrieving revision 1.28
diff -u -r1.28 add_trail_ops.m
--- compiler/add_trail_ops.m	14 Dec 2005 06:10:10 -0000	1.28
+++ compiler/add_trail_ops.m	15 Dec 2005 06:33:11 -0000
@@ -7,13 +7,23 @@
 %-----------------------------------------------------------------------------%

 % File: add_trail_ops.m.
-% Author: fjh.
+% Authors: fjh, juliensf.

 % This module is an HLDS-to-HLDS transformation that inserts code to
-% handle trailing.  The transformation involves adding calls to impure
-% predicates defined in library/private_builtin.m, which in turn call
-% macros defined in runtime/mercury_trail.h.
+% handle trailing.  The module implements two ways of doing this:
+%
+% (1) by adding calls to impure predicates defined in
+%     library/private_builtin.m, which in turn call macros defined in
+%     runtime/mercury_trail.h.
 %
+% (2) by inserting foreign_procs that call the macros defined in
+%     runtime/mercury_trail.h.
+%
+% There is a space/time tradeoff between these two methods, the second
+% is generally faster but results in larger executables.  The
+% `--generate-trail-ops-inline' option can be used to control which
+% of the methods is used.
+
 % This pass is currently only used for the MLDS back-end.
 % For some reason (perhaps efficiency?? or more likely just historical?),
 % the LLDS back-end inserts the trail operations as it is generating
@@ -21,14 +31,19 @@
 %
 % See compiler/notes/trailing.html for more information about trailing
 % in the Mercury implementation.
-%
-% This pass is very similar to add_heap_ops.m.
+
+% This module also implements trail usage optimization for those backends
+% that use it to implement trailing (see trailing_analysis.m for details).

 % NOTE: it is important that passes following this one do not attempt
 %       to reorder disjunctions.  If trail usage optimization is being
 %       performed and a disjunction is reordered then the trail might
 %       be corrupted.

+% TODO:
+%       - explore the space/time tradeoff between the inlining and
+%         non-inlining methods of implementing trailing.
+
 %-----------------------------------------------------------------------------%

 % XXX check goal_infos for correctness
@@ -43,7 +58,7 @@

 :- import_module bool.

-:- pred add_trail_ops(bool::in, module_info::in,
+:- pred add_trail_ops(bool::in, bool::in, module_info::in,
     proc_info::in, proc_info::out) is det.

 %-----------------------------------------------------------------------------%
@@ -59,9 +74,11 @@
 :- import_module hlds.instmap.
 :- import_module hlds.quantification.
 :- import_module libs.compiler_util.
+:- import_module libs.globals.
 :- import_module mdbcomp.prim_data.
 :- import_module parse_tree.modules.
 :- import_module parse_tree.prog_data.
+:- import_module parse_tree.prog_mode.
 :- import_module parse_tree.prog_type.
 :- import_module parse_tree.prog_util.

@@ -88,20 +105,21 @@
     %
 :- type trail_ops_info
     --->    trail_ops_info(
-                varset        :: prog_varset,
-                var_types     :: vartypes,
-                module_info   :: module_info,
-                opt_trail_usage :: bool
+                varset          :: prog_varset,
+                var_types       :: vartypes,
+                module_info     :: module_info,
+                opt_trail_usage :: bool,
+                inline_ops      :: bool
             ).

-add_trail_ops(OptTrailUsage, ModuleInfo0, !Proc) :-
+add_trail_ops(OptTrailUsage, GenerateInline, ModuleInfo0, !Proc) :-
     proc_info_goal(!.Proc, Goal0),
     proc_info_varset(!.Proc, VarSet0),
     proc_info_vartypes(!.Proc, VarTypes0),
     TrailOpsInfo0 = trail_ops_info(VarSet0, VarTypes0, ModuleInfo0,
-        OptTrailUsage),
+        OptTrailUsage, GenerateInline),
     goal_add_trail_ops(Goal0, Goal, TrailOpsInfo0, TrailOpsInfo),
-    TrailOpsInfo = trail_ops_info(VarSet, VarTypes, _, _),
+    TrailOpsInfo = trail_ops_info(VarSet, VarTypes, _, _, _),
     proc_info_set_goal(Goal, !Proc),
     proc_info_set_varset(VarSet, !Proc),
     proc_info_set_vartypes(VarTypes, !Proc),
@@ -290,8 +308,8 @@
         % "Sorry, not implemented" error message.
         ModuleInfo = !.Info^ module_info,
         goal_info_get_context(GoalInfo, Context),
-        generate_call("trailed_nondet_pragma_foreign_code", erroneous, [], [],
-            [], ModuleInfo, Context, SorryNotImplementedCode),
+        trail_generate_call("trailed_nondet_pragma_foreign_code", erroneous,
+            [], [], [], ModuleInfo, Context, SorryNotImplementedCode),
         Goal = SorryNotImplementedCode
     ;
         Goal = PragmaForeign - GoalInfo
@@ -406,64 +424,161 @@
     trail_ops_info::in) is det.

 gen_store_ticket(TicketVar, Context, SaveTicketGoal, Info) :-
-    generate_call("store_ticket", det, [TicketVar], [impure_goal],
-        [TicketVar - ground_inst], Info ^ module_info, Context,
-        SaveTicketGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("store_ticket", det, [TicketVar], [impure_goal],
+            [TicketVar - trail_ground_inst], Info ^ module_info, Context,
+            SaveTicketGoal)
+    ;
+        GenerateInline =  yes,
+        Args = [foreign_arg(TicketVar, yes("Ticket" - out_mode),
+            ticket_type)],
+        ForeignCode = "MR_store_ticket(Ticket);",
+        trail_generate_foreign_proc("store_ticket", [impure_goal],
+            [TicketVar - trail_ground_inst], Info ^ module_info, Context,
+            Args, ForeignCode, SaveTicketGoal)
+    ).

 :- pred gen_reset_ticket_undo(prog_var::in, prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_reset_ticket_undo(TicketVar, Context, ResetTicketGoal, Info) :-
-    generate_call("reset_ticket_undo", det, [TicketVar], [impure_goal],
-        [], Info ^ module_info, Context, ResetTicketGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("reset_ticket_undo", det, [TicketVar],
+            [impure_goal], [], Info ^ module_info, Context, ResetTicketGoal)
+    ;
+        GenerateInline = yes,
+        Args = [foreign_arg(TicketVar, yes("Ticket" - in_mode),
+            ticket_type)],
+        ForeignCode = "MR_reset_ticket(Ticket, MR_undo);",
+        trail_generate_foreign_proc("reset_ticket_undo", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            ResetTicketGoal)
+    ).

 :- pred gen_reset_ticket_solve(prog_var::in, prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_reset_ticket_solve(TicketVar, Context, ResetTicketGoal, Info) :-
-    generate_call("reset_ticket_solve", det, [TicketVar], [impure_goal],
-        [], Info ^ module_info, Context, ResetTicketGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("reset_ticket_solve", det, [TicketVar],
+            [impure_goal], [], Info ^ module_info, Context, ResetTicketGoal)
+    ;
+        GenerateInline = yes,
+        Args = [foreign_arg(TicketVar, yes("Ticket" - in_mode),
+            ticket_type)],
+        ForeignCode = "MR_reset_ticket(Ticket, MR_solve);",
+        trail_generate_foreign_proc("reset_ticket_solve", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            ResetTicketGoal)
+    ).

 :- pred gen_reset_ticket_commit(prog_var::in, prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_reset_ticket_commit(TicketVar, Context, ResetTicketGoal, Info) :-
-    generate_call("reset_ticket_commit", det, [TicketVar], [impure_goal],
-        [], Info ^ module_info, Context, ResetTicketGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("reset_ticket_commit", det, [TicketVar],
+            [impure_goal], [], Info ^ module_info, Context, ResetTicketGoal)
+    ;
+        GenerateInline = yes,
+        Args = [foreign_arg(TicketVar, yes("Ticket" - in_mode),
+            ticket_type)],
+        ForeignCode = "MR_reset_ticket(Ticket, MR_commit);",
+        trail_generate_foreign_proc("reset_ticket_commit", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            ResetTicketGoal)
+    ).

 :- pred gen_prune_ticket(prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_prune_ticket(Context, PruneTicketGoal, Info) :-
-    generate_call("prune_ticket", det, [], [impure_goal],
-        [], Info ^ module_info, Context, PruneTicketGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("prune_ticket", det, [], [impure_goal],
+            [], Info ^ module_info, Context, PruneTicketGoal)
+    ;
+        GenerateInline = yes,
+        Args = [],
+        ForeignCode = "MR_prune_ticket();",
+        trail_generate_foreign_proc("prune_ticket", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            PruneTicketGoal)
+    ).

 :- pred gen_discard_ticket(prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_discard_ticket(Context, DiscardTicketGoal, Info) :-
-    generate_call("discard_ticket", det, [], [impure_goal], [],
-        Info ^ module_info, Context, DiscardTicketGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("discard_ticket", det, [], [impure_goal], [],
+            Info ^ module_info, Context, DiscardTicketGoal)
+    ;
+        GenerateInline = yes,
+        Args = [],
+        ForeignCode = "MR_discard_ticket();",
+        trail_generate_foreign_proc("discard_ticket", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            DiscardTicketGoal)
+    ).

 :- pred gen_mark_ticket_stack(prog_var::in, prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_mark_ticket_stack(SavedTicketCounterVar, Context, MarkTicketStackGoal,
         Info) :-
-    generate_call("mark_ticket_stack", det, [SavedTicketCounterVar],
-        [impure_goal], [], Info ^ module_info, Context, MarkTicketStackGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("mark_ticket_stack", det,
+            [SavedTicketCounterVar],
+            [impure_goal], [], Info ^ module_info, Context,
+            MarkTicketStackGoal)
+    ;
+        GenerateInline = yes,
+        Args = [foreign_arg(SavedTicketCounterVar,
+            yes("TicketCounter" - out_mode), ticket_counter_type)],
+        ForeignCode = "MR_mark_ticket_stack(TicketCounter);",
+        trail_generate_foreign_proc("mark_ticket_stack", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            MarkTicketStackGoal)
+    ).

 :- pred gen_prune_tickets_to(prog_var::in, prog_context::in, hlds_goal::out,
     trail_ops_info::in) is det.

 gen_prune_tickets_to(SavedTicketCounterVar, Context, PruneTicketsToGoal,
         Info) :-
-    generate_call("prune_tickets_to", det, [SavedTicketCounterVar],
-        [impure_goal], [], Info ^ module_info, Context, PruneTicketsToGoal).
+    GenerateInline = Info ^ inline_ops,
+    (
+        GenerateInline = no,
+        trail_generate_call("prune_tickets_to", det, [SavedTicketCounterVar],
+            [impure_goal], [], Info ^ module_info, Context,
+            PruneTicketsToGoal)
+    ;
+        GenerateInline = yes,
+        Args = [foreign_arg(SavedTicketCounterVar,
+            yes("TicketCounter" - in_mode), ticket_counter_type)],
+        ForeignCode = "MR_prune_tickets_to(TicketCounter);",
+        trail_generate_foreign_proc("prune_tickets_to", [impure_goal],
+            [], Info ^ module_info, Context, Args, ForeignCode,
+            PruneTicketsToGoal)
+    ).

-:- func ground_inst = mer_inst.
+:- func trail_ground_inst = mer_inst.

-ground_inst = ground(unique, none).
+trail_ground_inst = ground(unique, none).

 %-----------------------------------------------------------------------------%

@@ -502,11 +617,11 @@

 %-----------------------------------------------------------------------------%

-:- pred generate_call(string::in, determinism::in, list(prog_var)::in,
+:- pred trail_generate_call(string::in, determinism::in, list(prog_var)::in,
     list(goal_feature)::in, assoc_list(prog_var, mer_inst)::in,
     module_info::in, term__context::in, hlds_goal::out) is det.

-generate_call(PredName, Detism, Args, Features, InstMap, ModuleInfo,
+trail_generate_call(PredName, Detism, Args, Features, InstMap, ModuleInfo,
         Context, CallGoal) :-
     mercury_private_builtin_module(BuiltinModule),
     goal_util__generate_simple_call(BuiltinModule, PredName, predicate,
@@ -515,6 +630,32 @@

 %-----------------------------------------------------------------------------%

+:- pred trail_generate_foreign_proc(string::in,
+    list(goal_feature)::in, assoc_list(prog_var, mer_inst)::in,
+    module_info::in, term.context::in, list(foreign_arg)::in, string::in,
+    hlds_goal::out) is det.
+
+trail_generate_foreign_proc(PredName, Features, InstMap,
+        ModuleInfo, Context, Args, ForeignCode, ForeignProcGoal) :-
+    mercury_private_builtin_module(PrivateBuiltinModule),
+    Detism = det,
+    some [!ForeignProcAttrs] (
+        % XXX handle other target languages here.
+        !:ForeignProcAttrs = default_attributes(c),
+        set_may_call_mercury(will_not_call_mercury, !ForeignProcAttrs),
+        set_thread_safe(thread_safe, !ForeignProcAttrs),
+        FinalForeignProcAttrs = !.ForeignProcAttrs
+    ),
+    PrefixCode = "",
+    ExtraArgs  = [],
+    SuffixCode = "",
+    goal_util.generate_foreign_proc(PrivateBuiltinModule, PredName,
+        predicate, only_mode, Detism, FinalForeignProcAttrs,
+        Args, ExtraArgs, PrefixCode, ForeignCode, SuffixCode, Features,
+        InstMap, ModuleInfo, Context, ForeignProcGoal).
+
+%-----------------------------------------------------------------------------%
+
 :- func this_file = string.

 this_file = "add_trail_ops.m".
Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.367
diff -u -r1.367 mercury_compile.m
--- compiler/mercury_compile.m	7 Dec 2005 16:07:03 -0000	1.367
+++ compiler/mercury_compile.m	14 Dec 2005 13:12:03 -0000
@@ -3159,9 +3159,12 @@
     (
         UseTrail = yes,
         globals.io_lookup_bool_option(optimize_trail_usage, OptTrailUse, !IO),
+        globals.io_lookup_bool_option(generate_trail_ops_inline,
+            GenerateInline, !IO),
         maybe_write_string(Verbose, "% Adding trailing operations...\n", !IO),
         maybe_flush_output(Verbose, !IO),
-        process_all_nonimported_procs(update_proc(add_trail_ops(OptTrailUse)),
+        process_all_nonimported_procs(
+            update_proc(add_trail_ops(OptTrailUse, GenerateInline)),
             !HLDS, !IO),
         maybe_write_string(Verbose, "% done.\n", !IO),
         maybe_report_stats(Stats, !IO)
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.480
diff -u -r1.480 options.m
--- compiler/options.m	28 Nov 2005 04:11:50 -0000	1.480
+++ compiler/options.m	14 Dec 2005 12:59:01 -0000
@@ -318,6 +318,7 @@
     ;       nondet_copy_out
     ;       put_commit_in_own_func
     ;       put_nondet_env_on_heap
+    ;       generate_trail_ops_inline

     % IL back-end compilation model options
     ;       verifiable_code
@@ -1044,6 +1045,7 @@
     nondet_copy_out                     -   bool(no),
     put_commit_in_own_func              -   bool(no),
     put_nondet_env_on_heap              -   bool(no),
+    generate_trail_ops_inline           -   bool(no),

     % IL back-end compilation model options
     verifiable_code                     -   bool(no),
@@ -1751,6 +1753,7 @@
 long_option("nondet-copy-out",      nondet_copy_out).
 long_option("put-commit-in-own-func",   put_commit_in_own_func).
 long_option("put-nondet-env-on-heap",   put_nondet_env_on_heap).
+long_option("generate-trail-ops-inline", generate_trail_ops_inline).
 % IL back-end compilation model options
 long_option("verifiable-code",      verifiable_code).
 long_option("verifiable",           verifiable_code).



--------------------------------------------------------------------------
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