[m-dev.] for review: trailing for the MLDS back-end
Fergus Henderson
fjh at cs.mu.OZ.AU
Wed Dec 13 01:56:05 AEDT 2000
On 12-Dec-2000, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> I'll post another diff when I've tested it a bit more.
Here it is.
The last three items on the log message are new.
I've enclosed a relative diff below.
I changed the behaviour for nondet pragma c_code so that
rather than calling error/1, it instead generates code
which calls error/1. With that change, and others
described below, I can build the compiler in grade
hlc.gc.tr and pass the tests in extras/trailed_update.
I'm just running a bootcheck now.
----------
Estimated hours taken: 20
Implement trailing for the MLDS back-end.
library/private_builtin.m:
Define impure Mercury procedures corresponding to the
trailing operations in runtime/mercury_trail.h.
compiler/add_trail_ops.m:
A new HLDS->HLDS pass.
This implements trailing by inserting calls to the
trailing primitives declared in library/private_builtin.m.
compiler/mercury_compile.m:
Change the code for mercury_compile__mlds_backend so that
if trailing is enabled, it invokes the new add_trail_ops pass.
compiler/notes/compiler_design.html:
Document the new pass.
runtime/mercury_wrapper.c:
For high-level C grades, call MR_init_memory() (which sets up
the redzone signal handlers, etc.) and if trailing is enabled,
initialize the trail.
library/benchmarking.m:
Change the code in report_stats for printing out the size of
the trail so that it gets the trail zone from MR_trail_zone
rather than via the MercuryEngine, so that it works in
high-level C grades (which don't have any MercuryEngine).
diff -u add_trail_ops.m add_trail_ops.m
--- add_trail_ops.m
+++ add_trail_ops.m
@@ -42,10 +44,18 @@
%
-% As we traverse the goal, we add new variables
-% keep track of XXX
-% construct it.
+% As we traverse the goal, we add new variables to hold the
+% trail tickets (i.e. saved values of the trail pointer)
+% and the saved values of the trail ticket counter.
+% So we need to thread a varset and a vartypes mapping through,
+% to record the names and types of the new variables.
+%
+% We also keep the module_info around, so that we can use
+% the predicate table that it contains to lookup the pred_ids
+% for the builtin procedures that we insert calls to.
+% We do not update the module_info as we're traversing the goal.
%
+
:- type trail_ops_info --->
trail_ops_info(
varset :: prog_varset,
@@ -54,7 +64,6 @@
).
add_trail_ops(Proc0, ModuleInfo0, Proc) :-
- % The ModuleInfo argument is there just for passes_aux
proc_info_goal(Proc0, Goal0),
proc_info_varset(Proc0, VarSet0),
proc_info_vartypes(Proc0, VarTypes0),
@@ -106,16 +115,28 @@
goal_expr_add_trail_ops(switch(A, B, Cases0, D), _, switch(A, B, Cases, D)) -->
cases_add_trail_ops(Cases0, Cases).
-goal_expr_add_trail_ops(not(Goal0), GoalInfo, Goal) -->
+goal_expr_add_trail_ops(not(InnerGoal), OuterGoalInfo, Goal) -->
%
- % We handle negations by converting them into if-then-elses.
+ % We handle negations by converting them into if-then-elses:
+ % not(G) ===> (if G then fail else true)
%
- { goal_info_get_context(GoalInfo, Context) },
+ { goal_info_get_context(OuterGoalInfo, Context) },
+ { InnerGoal = _ - InnerGoalInfo },
+ { goal_info_get_determinism(InnerGoalInfo, Determinism) },
+ { determinism_components(Determinism, _CanFail, NumSolns) },
{ true_goal(Context, True) },
{ fail_goal(Context, Fail) },
{ map__init(SM) },
- { IfThenElse = if_then_else([], Goal0, Fail, True, SM) },
- goal_expr_add_trail_ops(IfThenElse, GoalInfo, Goal).
+ { NumSolns = at_most_zero ->
+ % The "then" part of the if-then-else will be unreachable,
+ % but to preserve the invariants that the MLDS back-end
+ % relies on, we need to make sure that it can't fail.
+ % So we use `true' rather than `fail' for the "then" part.
+ NewOuterGoal = if_then_else([], InnerGoal, True, True, SM)
+ ;
+ NewOuterGoal = if_then_else([], InnerGoal, Fail, True, SM)
+ },
+ goal_expr_add_trail_ops(NewOuterGoal, OuterGoalInfo, Goal).
goal_expr_add_trail_ops(some(A, B, Goal0), OuterGoalInfo, Goal) -->
{ Goal0 = _ - InnerGoalInfo },
@@ -227,13 +248,25 @@
goal_expr_add_trail_ops(unify(A,B,C,D,E), _, unify(A,B,C,D,E)) --> [].
-goal_expr_add_trail_ops(PragmaForeign0, _, PragmaForeign) -->
+goal_expr_add_trail_ops(PragmaForeign0, GoalInfo, PragmaForeign) -->
{ PragmaForeign0 = pragma_foreign_code(_,_,_,_,_,_,Impl) },
- { Impl = nondet(_,_,_,_,_,_,_,_,_) ->
- error("sorry, not implemented: nondet pragma foreign_code with --use-trail --high-level-code")
+ ( { Impl = nondet(_,_,_,_,_,_,_,_,_) } ->
+ % XXX Implementing trailing for nondet pragma foreign_code
+ % via transformation is difficult, because there's nowhere
+ % in the HLDS pragma_foreign_code goal where we can insert
+ % trailing operations. For now, we don't support this.
+ % Instead, we just generate a call to a procedure which
+ % will at runtime call error/1 with an appropriate
+ % "Sorry, not implemented" error message.
+ ModuleInfo =^ module_info,
+ { goal_info_get_context(GoalInfo, Context) },
+ { generate_call("trailed_nondet_pragma_foreign_code",
+ [], det, no, [], ModuleInfo, Context,
+ SorryNotImplementedCode) },
+ { PragmaForeign - _GoalInfo = SorryNotImplementedCode }
;
- PragmaForeign = PragmaForeign0
- }.
+ { PragmaForeign = PragmaForeign0 }
+ ).
goal_expr_add_trail_ops(bi_implication(_, _), _, _) -->
% these should have been expanded out by now
diff -u library/private_builtin.m library/private_builtin.m
--- library/private_builtin.m
+++ library/private_builtin.m
@@ -475,7 +475,8 @@
:- type ticket == c_pointer.
:- type ticket_counter == c_pointer.
- % For documentation, see the corresponding LLDS
+ % For documentation, see the corresponding LLDS instructions
+ % in compiler/llds.m. See also compiler/notes/trailing.html.
:- impure pred store_ticket(ticket::out) is det.
:- impure pred reset_ticket_undo(ticket::in) is det.
@@ -486,6 +487,12 @@
:- impure pred mark_ticket_stack(ticket_counter::out) is det.
:- impure pred prune_tickets_to(ticket_counter::in) is det.
+ % XXX currently we don't support nondet pragma
+ % foreign_code when trailing is enabled.
+ % Instead we generate code which calls this procedure,
+ % which will call error/1 with an appropriate message.
+:- pred trailed_nondet_pragma_foreign_code is erroneous.
+
% N.B. interface continued below.
:- implementation.
@@ -557,6 +564,15 @@
MR_prune_tickets_to(TicketCounter);
#endif
").
+
+trailed_nondet_pragma_foreign_code :-
+ Msg = string__append_list([
+ "Sorry, not implemented:\n",
+ "for the MLDS back-end (`--high-level-code')\n",
+ "nondet `pragma c_code' or `pragma foreign_code'\n",
+ "is not supported when trailing (`--use_trail') is enabled."
+ ]),
+ error(Msg).
%-----------------------------------------------------------------------------%
only in patch2:
--- runtime/mercury_wrapper.c 2000/12/06 10:36:09 1.82
+++ runtime/mercury_wrapper.c 2000/12/12 04:13:40
@@ -43,6 +43,8 @@
#include "mercury_stack_layout.h"
#include "mercury_trace_base.h"
#include "mercury_memory.h" /* for MR_copy_string() */
+#include "mercury_memory_handlers.h" /* for MR_default_handler */
+#include "mercury_memory_zones.h" /* for MR_default_handler */
/* global variables concerned with testing (i.e. not with the engine) */
@@ -315,7 +317,18 @@
(*MR_address_of_mercury_init_io)();
-#ifndef MR_HIGHLEVEL_CODE
+#ifdef MR_HIGHLEVEL_CODE
+ MR_init_memory();
+ #ifdef MR_USE_TRAIL
+ /* initialize the trail */
+ MR_trail_zone = MR_create_zone("trail", 0,
+ MR_trail_size, MR_next_offset(),
+ MR_trail_zone_size, MR_default_handler);
+ MR_trail_ptr = (MR_TrailEntry *) MR_trail_zone->min;
+ MR_ticket_counter = 1;
+ MR_ticket_high_water = 1;
+ #endif
+#else
/* start up the Mercury engine */
#ifndef MR_THREAD_SAFE
MR_init_thread(MR_use_now);
only in patch2:
--- library/benchmarking.m 2000/11/28 05:51:58 1.37
+++ library/benchmarking.m 2000/12/11 17:01:49
@@ -188,7 +188,7 @@
fprintf(stderr,
"" Trail: %.3fk,"",
((char *) MR_trail_ptr - (char *)
- eng->context.trail_zone->min) / 1024.0
+ MR_trail_zone->min) / 1024.0
);
#endif
only in patch2:
--- compiler/notes/compiler_design.html 2000/12/06 06:05:33 1.54
+++ compiler/notes/compiler_design.html 2000/12/12 05:03:20
@@ -672,7 +672,11 @@
<dt> code generation
<dd>
- For code generation itself, the main module is code_gen.m.
+ Code generation converts HLDS into LLDS.
+ For the LLDS back-end, this is also the point at which we
+ insert code to handle debugging and trailing, and to do
+ heap reclamation on failure.
+ The main code generation module is code_gen.m.
It handles conjunctions and negations, but calls sub-modules
to do most of the other work:
@@ -910,7 +914,7 @@
This back-end uses the Medium Level Data Structure (mlds.m) as its
intermediate representation.
-<h4> 3b. pre-passes to annotate the HLDS </h4>
+<h4> 3b. pre-passes to annotate/transform the HLDS </h4>
Before code generation there is a pass which annotates the HLDS with
information used for code generation:
@@ -919,6 +923,20 @@
<li> mark_static_terms.m marks construction unifications
which can be implemented using static constants rather
than heap allocation.
+</ul>
+
+For the MLDS back-end, we've tried to keep the code generator simple.
+So we prefer to do things as HLDS to HLDS transformations where possible,
+rather than complicating the HLDS to MLDS code generator.
+So we have a pass which transforms the HLDS to handle trailing:
+
+<ul>
+<li> add_trail_ops.m inserts code to manipulate the trail,
+ in particular ensuring that we apply the appropriate
+ trail operations before each choice point, when execution
+ resumes after backtracking, and whenever we do a commit.
+ The trail operations are represented as (and implemented as)
+ calls to impure procedures defined in library/private_builtin.m.
</ul>
<h4> 4b. MLDS code generation </h4>
--
Fergus Henderson <fjh at cs.mu.oz.au> | "I have always known that the pursuit
| of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the developers
mailing list