[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