for review: nondet code gen bug fix
Fergus Henderson
fjh at cs.mu.OZ.AU
Tue Jun 2 01:55:13 AEST 1998
Hi,
Zoltan and Tom, can you please review this one?
--------------------
Estimated hours taken: 4
Fix some bugs in code generation for nondet disjunctions and
if-then-elses. The compiler was incorrectly releasing the temp stack
slots used to save the heap pointer and trail pointer at the start
of the else or the last clauses, thus allowing them to be reused not
only in the else case or the last clause, but also by goals following the
disjunction or if-then-else, even though the values in these slots might
be needed again on backtracking into the condition or the earlier
disjunctions.
Thanks to Warwick Harvey for reporting this bug.
compiler/code_info.m:
Add new predicate `code_info__maybe_reset_and_pop_ticket',
which is like `code_info__maybe_reset_and_discard_ticket',
except that it does not release the temp stack slot.
compiler/disj_gen.m:
compiler/ite_gen.m:
When generating code for nondet goals that save
and restore the hp and trail, if the saved
values might be needed again on backtracking
into the current goal from one that follows
(i.e. in nondet disjunctions and in if-then-elses
with nondet conditions), make sure we use
`code_info__maybe_reset_and_pop_ticket' and
`code_info__reset_hp' instead of
`code_info__maybe_reset_and_discard_ticket' and
`code_info__reset_and_discard_hp'.
compiler/code_info.m:
Include the temp_avail_slots in the set of things
that slap_code_info does not update. Temp slots
that were acquired (and not released) in one branch
of a branched goal need to be still reserved at the
end of the branched goal.
tests/hard_coded/Mmakefile:
tests/hard_coded/trail_test.m:
tests/hard_coded/trail_test.exp:
tests/hard_coded/trail_test_2.m:
tests/hard_coded/trail_test_2.exp:
Add a couple of regression tests.
Index: compiler/code_info.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/code_info.m,v
retrieving revision 1.220
diff -u -r1.220 code_info.m
--- code_info.m 1998/05/16 07:29:50 1.220
+++ code_info.m 1998/06/01 14:56:47
@@ -954,10 +954,12 @@
code_info__set_fail_stack(J, C3, C4),
code_info__get_max_temp_slot_count(PC, C1, _),
code_info__set_max_temp_slot_count(PC, C4, C5),
+ code_info__get_avail_temp_slots(TS, C1, _),
+ code_info__set_avail_temp_slots(TS, C5, C6),
code_info__get_layout_info(LayoutInfo, C1, _),
- code_info__set_layout_info(LayoutInfo, C5, C6),
+ code_info__set_layout_info(LayoutInfo, C6, C7),
code_info__get_cell_count(CellCount, C1, _),
- code_info__set_cell_count(CellCount, C6, C).
+ code_info__set_cell_count(CellCount, C7, C).
code_info__apply_instmap_delta(Delta) -->
code_info__get_instmap(InstMap0),
@@ -2322,6 +2324,13 @@
code_info, code_info).
:- mode code_info__reset_and_discard_ticket(in, in, out, in, out) is det.
+ % Same as reset_and_discard_ticket, but don't release the temp slot.
+ % Used for cases where the temp slot might still be needed again
+ % on backtracking and thus can't be reused in the code that follows.
+:- pred code_info__reset_and_pop_ticket(lval, reset_trail_reason,
+ code_tree, code_info, code_info).
+:- mode code_info__reset_and_pop_ticket(in, in, out, in, out) is det.
+
:- pred code_info__discard_ticket(lval, code_tree, code_info, code_info).
:- mode code_info__discard_ticket(in, out, in, out) is det.
@@ -2337,6 +2346,11 @@
reset_trail_reason, code_tree, code_info, code_info).
:- mode code_info__maybe_reset_and_discard_ticket(in, in, out, in, out) is det.
+:- pred code_info__maybe_reset_and_pop_ticket(maybe(lval),
+ reset_trail_reason, code_tree, code_info, code_info).
+:- mode code_info__maybe_reset_and_pop_ticket(in, in, out, in, out)
+ is det.
+
:- pred code_info__maybe_discard_ticket(maybe(lval), code_tree,
code_info, code_info).
:- mode code_info__maybe_discard_ticket(in, out, in, out) is det.
@@ -2406,6 +2420,13 @@
discard_ticket - "Pop ticket stack"
]) }.
+code_info__reset_and_pop_ticket(TicketSlot, Reason, Code) -->
+ { Code = node([
+ reset_ticket(lval(TicketSlot), Reason) -
+ "Restore trail (but don't release this stack slot)",
+ discard_ticket - "Pop ticket stack"
+ ]) }.
+
code_info__discard_ticket(TicketSlot, Code) -->
code_info__release_temp_slot(TicketSlot),
{ Code = node([discard_ticket - "Pop ticket stack"]) }.
@@ -2429,6 +2450,15 @@
code_info__maybe_reset_and_discard_ticket(MaybeTicketSlot, Reason, Code) -->
( { MaybeTicketSlot = yes(TicketSlot) } ->
code_info__reset_and_discard_ticket(TicketSlot, Reason, Code)
+ ;
+ { Code = empty }
+ ).
+
+code_info__maybe_reset_and_pop_ticket(MaybeTicketSlot, Reason, Code)
+ -->
+ ( { MaybeTicketSlot = yes(TicketSlot) } ->
+ code_info__reset_and_pop_ticket(TicketSlot, Reason,
+ Code)
;
{ Code = empty }
).
Index: compiler/disj_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/disj_gen.m,v
retrieving revision 1.63
diff -u -r1.63 disj_gen.m
--- disj_gen.m 1998/04/08 11:31:34 1.63
+++ disj_gen.m 1998/06/01 15:01:26
@@ -359,13 +359,23 @@
error("disj_gen__generate_non_disjuncts: last disjunct followed by others")
},
+ % Note that we can't release the temps used for the heap
+ % pointer and ticket, because those values may be required
+ % again after backtracking from goals that following
+ % the disjunction.
+ % If we were to reuse the same stack slot for something
+ % else when generating the code that follows this goal,
+ % then the values that earlier disjuncts need on
+ % backtracking would get clobbered.
+ % Thus we must not use the `_discard' versions of the two
+ % predicates below.
+
% Restore the heap pointer if necessary.
- code_info__maybe_restore_and_discard_hp(MaybeHpSlot,
- RestoreHPCode),
+ code_info__maybe_restore_hp(MaybeHpSlot, RestoreHPCode),
% Restore the solver state if necessary.
- code_info__maybe_reset_and_discard_ticket(MaybeTicketSlot,
- undo, RestorePopTicketCode),
+ code_info__maybe_reset_and_pop_ticket(
+ MaybeTicketSlot, undo, RestorePopTicketCode),
trace__maybe_generate_internal_event_code(Goal0, TraceCode),
code_gen__generate_goal(model_non, Goal0, GoalCode),
Index: compiler/ite_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ite_gen.m,v
retrieving revision 1.54
diff -u -r1.54 ite_gen.m
--- ite_gen.m 1998/04/08 11:31:47 1.54
+++ ite_gen.m 1998/06/01 15:06:02
@@ -264,9 +264,19 @@
% Generate the entry to the else branch
code_info__slap_code_info(CodeInfo),
code_info__restore_failure_cont(RestoreContCode),
- code_info__maybe_restore_and_discard_hp(MaybeHpSlot, RestoreHPCode),
- code_info__maybe_reset_and_discard_ticket(MaybeTicketSlot, undo,
- RestoreTicketCode),
+ ( { NondetCond = yes } ->
+ % We cannot release the stack slots used for
+ % the trail ticket and heap pointer if the
+ % condition can be backtracked into.
+ code_info__maybe_restore_hp(MaybeHpSlot, RestoreHPCode),
+ code_info__maybe_reset_and_pop_ticket(MaybeTicketSlot,
+ undo, RestoreTicketCode)
+ ;
+ code_info__maybe_restore_and_discard_hp(MaybeHpSlot,
+ RestoreHPCode),
+ code_info__maybe_reset_and_discard_ticket(MaybeTicketSlot,
+ undo, RestoreTicketCode)
+ ),
% Generate the else branch
trace__maybe_generate_internal_event_code(ElseGoal, ElseTraceCode),
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.31
diff -u -r1.31 Mmakefile
--- Mmakefile 1998/05/30 15:23:10 1.31
+++ Mmakefile 1998/06/01 15:47:13
@@ -73,6 +73,8 @@
string_loop \
test_imported_no_tag \
tim_qual1 \
+ trail_test \
+ trail_test_2 \
write \
write_reg1
@@ -107,6 +109,15 @@
GRADEFLAGS-integer_test_init = --gc conservative
GRADEFLAGS-rational_test = --gc conservative
GRADEFLAGS-rational_test_init = --gc conservative
+
+# the trail tests need to use the trail (duh)
+# We can't just pass `--use-trail', because these
+# test are run in lots of different grades, whereas
+# the trail library is only builtin in a few grades.
+GRADEFLAGS-trail_test = --grade asm_fast.gc.tr
+GRADEFLAGS-trail_test_init = --grade asm_fast.gc.tr
+GRADEFLAGS-trail_test_2 = --grade asm_fast.tr
+GRADEFLAGS-trail_test_2_init = --grade asm_fast.tr
# no_fully_strict is expected to fail (it calls error/1)
# so we need to ignore the exit status (hence the leading `-')
Index: tests/hard_coded/trail_test.exp
===================================================================
RCS file: trail_test.exp
diff -N trail_test.exp
--- /dev/null Tue Jun 2 01:51:15 1998
+++ trail_test.exp Tue Jun 2 01:47:30 1998
@@ -0,0 +1,46 @@
+before: 1 0
+>> enter (1)
+inside: 1 1
+<< leave (1)
+after: 1 1
+=> fail back inside: 1
+inside: 1 2
+<< leave (1)
+after: 1 2
+=> fail back inside: 1
+inside: 1 3
+<< leave (1)
+after: 1 3
+=> fail back inside: 1
+<= fail back outside: 1
+before: 2 0
+>> enter (2)
+inside: 2 1
+<< leave (2)
+after: 2 1
+=> fail back inside: 2
+inside: 2 2
+<< leave (2)
+after: 2 2
+=> fail back inside: 2
+inside: 2 3
+<< leave (2)
+after: 2 3
+=> fail back inside: 2
+<= fail back outside: 2
+before: 3 0
+>> enter (3)
+inside: 3 1
+<< leave (3)
+after: 3 1
+=> fail back inside: 3
+inside: 3 2
+<< leave (3)
+after: 3 2
+=> fail back inside: 3
+inside: 3 3
+<< leave (3)
+after: 3 3
+=> fail back inside: 3
+<= fail back outside: 3
+Failure
Index: tests/hard_coded/trail_test.m
===================================================================
RCS file: trail_test.m
diff -N trail_test.m
--- /dev/null Tue Jun 2 01:51:15 1998
+++ trail_test.m Tue Jun 2 01:44:54 1998
@@ -0,0 +1,108 @@
+:- module trail_test.
+:- interface.
+:- import_module io.
+
+:- impure pred main(io__state::di, io__state::uo) is det.
+
+:- implementation.
+
+:- import_module int.
+
+main -->
+ ( { impure trail_test } ->
+ io__write_string("Success\n")
+ ;
+ io__write_string("Failure\n")
+ ).
+
+
+:- impure pred trail_test is failure.
+
+trail_test :-
+ small_int(I),
+ impure trail_test_message("before", I, 0),
+ impure enter(I),
+ small_int(J),
+ impure trail_test_message("inside", I, J),
+ impure leave(I),
+ impure trail_test_message("after", I, J),
+ fail.
+
+
+:- pred small_int(int::out) is multi.
+
+small_int(1).
+small_int(2).
+small_int(3).
+
+:- impure pred trail_test_message(string::in, int::in, int::in) is det.
+
+:- impure pred enter(int::in) is det.
+:- impure pred leave(int::in) is det.
+
+:- pragma c_header_code("
+#include <stdio.h>
+").
+
+:- pragma c_code(trail_test_message(Prefix::in, I::in, J::in),
+ will_not_call_mercury, "
+ printf(""%s: %d %d\n"",
+ (char *)Prefix, (int)I, (int)J);
+").
+
+
+:- pragma c_header_code("
+#include <mercury_trail.h>
+
+
+void enter_failing(int handle, MR_untrail_reason reason);
+void leave_failing(int handle, MR_untrail_reason reason);
+
+
+#include <stdio.h>
+
+
+void enter_failing(int handle, MR_untrail_reason reason) {
+ switch (reason) {
+ case MR_exception:
+ case MR_undo:
+/* printf(""enter_failing: exception/undo\n""); */
+ printf(""=> fail back inside: %d\n"", handle);
+ break;
+ default:
+ printf(""enter_failing: default\n"");
+ break;
+ }
+}
+
+
+void leave_failing(int handle, MR_untrail_reason reason) {
+ switch (reason) {
+ case MR_exception:
+ case MR_undo:
+/* printf(""leave_failing: exception/undo\n""); */
+ printf(""<= fail back outside: %d\n"", handle);
+ break;
+ case MR_commit:
+ case MR_solve:
+ printf(""leave_failing: commit/solve\n"");
+ break;
+ default:
+ printf(""leave_failing: default\n"");
+ /* we may need to do something if reason == MR_gc */
+ break;
+ }
+}
+
+").
+
+:- pragma c_code(enter(I::in), will_not_call_mercury, "
+ printf("">> enter (%d)\n"", (int) I);
+ MR_trail_function(leave_failing, I);
+").
+
+
+:- pragma c_code(leave(I::in), will_not_call_mercury, "
+ printf(""<< leave (%d)\n"", (int) I);
+ MR_trail_function(enter_failing, I);
+").
Index: tests/hard_coded/trail_test_2.exp
===================================================================
RCS file: trail_test_2.exp
diff -N trail_test_2.exp
--- /dev/null Tue Jun 2 01:51:15 1998
+++ trail_test_2.exp Tue Jun 2 01:48:11 1998
@@ -0,0 +1,10 @@
+before: 1 0
+>> enter (1)
+<= fail: 1
+before: 2 0
+>> enter (2)
+<= fail: 2
+before: 3 0
+>> enter (3)
+<= fail: 3
+Failure
Index: tests/hard_coded/trail_test_2.m
===================================================================
RCS file: trail_test_2.m
diff -N trail_test_2.m
--- /dev/null Tue Jun 2 01:51:15 1998
+++ trail_test_2.m Tue Jun 2 01:47:19 1998
@@ -0,0 +1,115 @@
+:- module trail_test_2.
+:- interface.
+:- import_module io.
+
+:- impure pred main(io__state::di, io__state::uo) is det.
+
+:- implementation.
+
+:- import_module int.
+
+main -->
+ ( { impure trail_test } ->
+ io__write_string("Success\n")
+ ;
+ io__write_string("Failure\n")
+ ).
+
+
+:- impure pred trail_test is failure.
+
+trail_test :-
+ small_int(I),
+ impure trail_test_message("before", I, 0),
+ impure enter(I),
+ small_int_2(J),
+ small_int(J),
+ impure trail_test_message("inside", I, J),
+ impure leave(I),
+ impure trail_test_message("after", I, J),
+ fail.
+
+
+:- pred small_int(int::out) is multi.
+
+small_int(1).
+small_int(2).
+small_int(3).
+
+:- pred small_int_2(int::out) is multi.
+
+small_int_2(4).
+small_int_2(5).
+small_int_2(6).
+
+:- impure pred trail_test_message(string::in, int::in, int::in) is det.
+
+:- impure pred enter(int::in) is det.
+:- impure pred leave(int::in) is det.
+
+:- pragma c_header_code("
+#include <stdio.h>
+").
+
+:- pragma c_code(trail_test_message(Prefix::in, I::in, J::in),
+ will_not_call_mercury, "
+ printf(""%s: %d %d\n"",
+ (char *)Prefix, (int)I, (int)J);
+").
+
+
+:- pragma c_header_code("
+#include ""mercury_trail.h""
+
+
+void trace_redo(int handle, MR_untrail_reason reason);
+void trace_fail(int handle, MR_untrail_reason reason);
+
+
+#include <stdio.h>
+
+
+void trace_fail(int handle, MR_untrail_reason reason) {
+ switch (reason) {
+ case MR_exception:
+ case MR_undo:
+/* printf(""trace_fail: exception/undo\n""); */
+ printf(""<= fail: %d\n"", handle);
+ break;
+ default:
+ printf(""trace_fail: default\n"");
+ break;
+ }
+}
+
+
+void trace_redo(int handle, MR_untrail_reason reason) {
+ switch (reason) {
+ case MR_exception:
+ case MR_undo:
+/* printf(""trace_redo: exception/undo\n""); */
+ printf("">= redo: %d\n"", handle);
+ break;
+ case MR_commit:
+ case MR_solve:
+ printf(""trace_redo: commit/solve\n"");
+ break;
+ default:
+ printf(""trace_redo: default\n"");
+ /* we may need to do something if reason == MR_gc */
+ break;
+ }
+}
+
+").
+
+:- pragma c_code(enter(I::in), will_not_call_mercury, "
+ printf("">> enter (%d)\n"", (int) I);
+ MR_trail_function(trace_fail, I);
+").
+
+
+:- pragma c_code(leave(I::in), will_not_call_mercury, "
+ printf(""<< leave (%d)\n"", (int) I);
+ MR_trail_function(trace_redo, I);
+").
--
Fergus Henderson <fjh at cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3 | -- the last words of T. S. Garp.
More information about the developers
mailing list