[m-dev.] diff: fix a bug in handling redoips

Zoltan Somogyi zs at cs.mu.OZ.AU
Tue Nov 16 19:31:53 AEDT 1999 

Fergus can decide whether he wants to review this or not.

Estimated hours taken: 10

Fix a bug reported by Warwick, which exposed a design error in failure
handling. We use to assume in several places that either the address
to jump to on failure was unknown (meaning we must generate a redo()),
or that the address was known *and* stored in the redoip slot of the top
nondet stack frame contained this address. This change takes care of the
third possibility: the address is known but the top redoip slot does not
(necessarily) contain that address.

compiler/code_info.m:
	Make the above distinction in the failure handling state of the
	code generator, and make use of it appropriately.

compiler/disj_gen.m:
	When reaching the end of a disjunct in a model_det or model_semi
	disjunction, reset this part of the state to what it was on entering
	the disjuct. The failure continuation was known, pointing to the
	next disjunct, during the generation of code for the disjunct,
	but the code after the disjunction as a whole should fail the
	same way as the disjunction itself should fail.

	In the absence of this reset, the merging of the failure states
	of the ends of the different branches may produce incorrect info.

compiler/notes/failure.html:
	State that the changed design is not yet documented :-(

tests/hard_coded/redoip_clobber.{m,exp}:
	A test case for the bug.

tests/hard_coded/Mmakefile:
	Enable the test case.

Zoltan.

cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/code_info.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/code_info.m,v
retrieving revision 1.244
diff -u -b -r1.244 code_info.m
--- code_info.m	1999/11/15 00:42:12	1.244
+++ code_info.m	1999/11/15 11:16:58
@@ -904,6 +904,9 @@
 :- pred code_info__reset_to_position(position_info, code_info, code_info).
 :- mode code_info__reset_to_position(in, in, out) is det.
 
+:- pred code_info__reset_resume_known(position_info, code_info, code_info).
+:- mode code_info__reset_resume_known(in, in, out) is det.
+
 :- pred code_info__generate_branch_end(store_map, branch_end, branch_end,
 	code_tree, code_info, code_info).
 :- mode code_info__generate_branch_end(in, in, out, out, in, out) is det.
@@ -940,6 +943,17 @@
 	NextCI = code_info(SA, SB, SC, SD, SE, SF, SG, SH,
 		LA, LB, LC, LD, LE, LF, PA, PB, PC, PD, PE, PF, PG).
 
+code_info__reset_resume_known(BranchStart) -->
+	{ BranchStart = position_info(BranchStartCI) },
+	{ code_info__get_fail_info(BranchStartFailInfo, BranchStartCI, _) },
+	{ BranchStartFailInfo = fail_info(_, BSResumeKnown, _, _, _) },
+	code_info__get_fail_info(CurFailInfo),
+	{ CurFailInfo = fail_info(CurFailStack, _,
+		CurCurfMaxfr, CurCondEnv, CurHijack) },
+	{ NewFailInfo = fail_info(CurFailStack, BSResumeKnown,
+		CurCurfMaxfr, CurCondEnv, CurHijack) },
+	code_info__set_fail_info(NewFailInfo).
+
 code_info__generate_branch_end(StoreMap, MaybeEnd0, MaybeEnd, Code) -->
 	code_info__get_exprn_info(Exprn0),
 	{ map__to_assoc_list(StoreMap, VarLocs) },
@@ -961,10 +975,12 @@
 		FailInfo1 = fail_info(R, ResumeKnown1, CurfrMaxfr1,
 			CondEnv1, Hijack1),
 		(
-			ResumeKnown0 = resume_point_known,
-			ResumeKnown1 = resume_point_known
+			ResumeKnown0 = resume_point_known(Redoip0),
+			ResumeKnown1 = resume_point_known(Redoip1)
 		->
-			ResumeKnown = resume_point_known
+			ResumeKnown = resume_point_known(Redoip0),
+			require(unify(Redoip0, Redoip1),
+				"redoip mismatch in generate_branch_end")
 		;
 			ResumeKnown = resume_point_unknown
 		),
@@ -1272,8 +1288,11 @@
 	% point to the locations in which they will be.
 
 :- type resume_map		==	map(prog_var, set(rval)).
+
+:- type redoip_update		--->	has_been_done
+				;	wont_be_done.
 
-:- type resume_point_known	--->	resume_point_known
+:- type resume_point_known	--->	resume_point_known(redoip_update)
 				;	resume_point_unknown.
 
 :- type curfr_vs_maxfr		--->	must_be_equal
@@ -1321,7 +1340,7 @@
 			"prepare for disjunction", Code)
 	;
 		{ CurfrMaxfr = must_be_equal },
-		{ ResumeKnown = resume_point_known }
+		{ ResumeKnown = resume_point_known(has_been_done) }
 	->
 		{ HijackInfo = disj_quarter_hijack },
 		{ Code = node([
@@ -1331,7 +1350,8 @@
 	;
 		{ CurfrMaxfr = must_be_equal }
 	->
-		% Here ResumeKnown must be resume_point_unknown.
+		% Here ResumeKnown must be resume_point_unknown
+		% or resume_point_known(wont_be_done).
 		code_info__acquire_temp_slot(lval(redoip(lval(curfr))),
 			RedoipSlot),
 		{ HijackInfo = disj_half_hijack(RedoipSlot) },
@@ -1371,8 +1391,6 @@
 		]) }
 	;
 		{ HijackInfo = disj_quarter_hijack },
-		{ require(unify(ResumeKnown, resume_point_known),
-			"resume point not known in disj_quarter_hijack") },
 		{ require(unify(CurfrMaxfr, must_be_equal),
 			"maxfr may differ from curfr in disj_quarter_hijack") },
 		{ stack__top_det(ResumePoints, ResumePoint) },
@@ -1471,7 +1489,7 @@
 		{ Code = tree(TempFrameCode, MaxfrCode) }
 	;
 		{ CurfrMaxfr = must_be_equal },
-		{ ResumeKnown = resume_point_known }
+		{ ResumeKnown = resume_point_known(_) }
 	->
 		{ HijackType = ite_quarter_hijack },
 		{ Code = node([
@@ -1522,7 +1540,7 @@
 	{ FailInfo0 = fail_info(ResumePoints0, ResumeKnown0, CurfrMaxfr,
 		_, Allow) },
 	{ stack__pop_det(ResumePoints0, _, ResumePoints) },
-	{ HijackInfo = ite_info(ResumeKnown1, OldCondEnv, HijackType) },
+	{ HijackInfo = ite_info(HijackResumeKnown, OldCondEnv, HijackType) },
 	{
 		HijackType = ite_no_hijack,
 		ThenCode = empty,
@@ -1580,13 +1598,10 @@
 				- "restore redofr for full ite hijack"
 		])
 	},
-	{
-		ResumeKnown0 = resume_point_known,
-		ResumeKnown1 = resume_point_known
-	->
-		ResumeKnown = resume_point_known
-	;
+	{ ResumeKnown0 = resume_point_unknown ->
 		ResumeKnown = resume_point_unknown
+	;
+		ResumeKnown = HijackResumeKnown
 	},
 	{ FailInfo = fail_info(ResumePoints, ResumeKnown, CurfrMaxfr,
 		OldCondEnv, Allow) },
@@ -1718,8 +1733,8 @@
 	{ stack__top_det(ResumePoints0, TopResumePoint) },
 	code_info__clone_resume_point(TopResumePoint, NewResumePoint),
 	{ stack__push(ResumePoints0, NewResumePoint, ResumePoints) },
-	{ FailInfo = fail_info(ResumePoints, ResumeKnown, CurfrMaxfr,
-		CondEnv, Allow) },
+	{ FailInfo = fail_info(ResumePoints, resume_point_known(has_been_done),
+		CurfrMaxfr, CondEnv, Allow) },
 	code_info__set_fail_info(FailInfo),
 
 	{ code_info__pick_stack_resume_point(NewResumePoint, _, StackLabel) },
@@ -1768,7 +1783,7 @@
 		},
 		{ HijackCode = tree(MaxfrCode, tree(TempFrameCode, MarkCode)) }
 	;
-		{ ResumeKnown = resume_point_known },
+		{ ResumeKnown = resume_point_known(has_been_done) },
 		{ CurfrMaxfr = must_be_equal }
 	->
 		{ HijackInfo = commit_quarter_hijack },
@@ -1779,7 +1794,8 @@
 	;
 		{ CurfrMaxfr = must_be_equal }
 	->
-		% Here ResumeKnown must be resume_point_unknown.
+		% Here ResumeKnown must be resume_point_unknown or
+		% resume_point_known(wont_be_done).
 
 		code_info__acquire_temp_slot(lval(redoip(lval(curfr))),
 			RedoipSlot),
@@ -1979,9 +1995,6 @@
 	},
 
 	{ stack__push(ResumePoints0, ResumePoint, ResumePoints) },
-	{ FailInfo = fail_info(ResumePoints, resume_point_known, CurfrMaxfr,
-		CondEnv, Allow) },
-	code_info__set_fail_info(FailInfo),
 	( { CodeModel = model_non } ->
 		{ code_info__pick_stack_resume_point(ResumePoint,
 			_, StackLabel) },
@@ -1989,10 +2002,15 @@
 		{ Code = node([
 			assign(redoip(lval(maxfr)), LabelConst)
 				- "hijack redoip to effect resume point"
-		]) }
+		]) },
+		{ RedoipUpdate = has_been_done }
 	;
-		{ Code = empty }
-	).
+		{ Code = empty },
+		{ RedoipUpdate = wont_be_done }
+	),
+	{ FailInfo = fail_info(ResumePoints, resume_point_known(RedoipUpdate),
+		CurfrMaxfr, CondEnv, Allow) },
+	code_info__set_fail_info(FailInfo).
 
 %---------------------------------------------------------------------------%
 
@@ -2021,7 +2039,7 @@
 	code_info__get_fail_info(FailInfo),
 	{ FailInfo = fail_info(ResumePoints, ResumeKnown, _, _, _) },
 	(
-		{ ResumeKnown = resume_point_known },
+		{ ResumeKnown = resume_point_known(_) },
 		{ stack__top_det(ResumePoints, TopResumePoint) },
 		(
 			code_info__pick_matching_resume_addr(TopResumePoint,
@@ -2048,7 +2066,7 @@
 	code_info__get_fail_info(FailInfo),
 	{ FailInfo = fail_info(ResumePoints, ResumeKnown, _, _, _) },
 	(
-		{ ResumeKnown = resume_point_known },
+		{ ResumeKnown = resume_point_known(_) },
 		{ stack__top_det(ResumePoints, TopResumePoint) },
 		(
 			code_info__pick_matching_resume_addr(TopResumePoint,
@@ -2100,7 +2118,7 @@
 
 code_info__failure_is_direct_branch(CodeAddr) -->
 	code_info__get_fail_info(FailInfo),
-	{ FailInfo = fail_info(ResumePoints, resume_point_known, _, _, _) },
+	{ FailInfo = fail_info(ResumePoints, resume_point_known(_), _, _, _) },
 	{ stack__top(ResumePoints, TopResumePoint) },
 	code_info__pick_matching_resume_addr(TopResumePoint, CodeAddr).
 
@@ -2113,7 +2131,7 @@
 		ResumePoint1 = stack_only(_, do_fail)
 	->
 		(
-			ResumeKnown = resume_point_known,
+			ResumeKnown = resume_point_known(_),
 			TailCallStatus = unchecked_tail_call
 		;
 			ResumeKnown = resume_point_unknown,
@@ -2256,7 +2274,7 @@
 			% will be part of the procedure epilog.
 		code_info__get_next_label(ResumeLabel),
 		{ ResumeAddress = label(ResumeLabel) },
-		{ ResumeKnown = resume_point_known },
+		{ ResumeKnown = resume_point_known(wont_be_done) },
 		{ CurfrMaxfr = may_be_different }
 	;
 		{ CodeModel = model_non },
@@ -2266,7 +2284,7 @@
 		;
 			{ ResumeAddress = do_fail }
 		),
-		{ ResumeKnown = resume_point_known },
+		{ ResumeKnown = resume_point_known(has_been_done) },
 		{ CurfrMaxfr = must_be_equal }
 	),
 	( { MaybeFailVars = yes(FailVars) } ->
Index: compiler/disj_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/disj_gen.m,v
retrieving revision 1.68
diff -u -b -r1.68 disj_gen.m
--- disj_gen.m	1999/03/12 05:53:25	1.68
+++ disj_gen.m	1999/11/09 06:33:11
@@ -240,7 +240,9 @@
 			{ ResumeVarsCode = empty },
 
 			code_info__maybe_release_hp(MaybeHpSlot),
-			code_info__maybe_release_ticket(MaybeTicketSlot)
+			code_info__maybe_release_ticket(MaybeTicketSlot),
+
+			code_info__reset_resume_known(BranchStart)
 		),
 
 			% Put every variable whose value is needed after
cvs diff: Diffing compiler/notes
Index: compiler/notes/failure.html
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/notes/failure.html,v
retrieving revision 1.5
diff -u -b -r1.5 failure.html
--- failure.html	1998/08/07 05:12:29	1.5
+++ failure.html	1999/11/16 07:55:26
@@ -197,6 +197,13 @@
 the establishment of the tightest enclosing resume point
 and the start of the current goal.
 
+If the resume point is known,
+the compiler state also records whether
+the redoip slot of the top nondet stack frame
+is known to contain the address of this resume point.
+XXX The rest of this document has not been updated
+to reflect how we handle this extra component of the failure handling state.
+
 <p>
 
 <li>
cvs diff: Diffing debian
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/opium_m
cvs diff: Diffing extras/opium_m/non-regression-tests
cvs diff: Diffing extras/opium_m/scripts
cvs diff: Diffing extras/opium_m/source
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing library
cvs diff: Diffing profiler
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/hard_coded
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.72
diff -u -b -r1.72 Mmakefile
--- Mmakefile	1999/11/12 03:47:05	1.72
+++ Mmakefile	1999/11/16 07:45:17
@@ -86,6 +86,7 @@
 	quantifier2 \
 	quoting_bug_test \
 	rational_test \
+	redoip_clobber \
 	relation_test \
 	remove_file \
 	reorder_di \
@@ -122,6 +123,7 @@
 MCFLAGS-ho_order2	=	--optimize-higher-order
 MCFLAGS-no_fully_strict	=	--no-fully-strict
 MCFLAGS-nondet_ctrl_vn	=	--optimize-value-number
+MCFLAGS-redoip_clobber	=	--no-inlining
 MCFLAGS-rnd		=	-O6
 MCFLAGS-type_spec	=	--user-guided-type-specialization
 MCFLAGS-existential_types_test = --infer-all
Index: tests/hard_coded/redoip_clobber.exp
===================================================================
RCS file: redoip_clobber.exp
diff -N redoip_clobber.exp
--- /dev/null	Wed May 28 10:49:58 1997
+++ redoip_clobber.exp	Wed May 12 18:20:26 1999
@@ -0,0 +1 @@
+Failed.
Index: tests/hard_coded/redoip_clobber.m
===================================================================
RCS file: redoip_clobber.m
diff -N redoip_clobber.m
--- /dev/null	Wed May 28 10:49:58 1997
+++ redoip_clobber.m	Tue Nov 16 18:44:36 1999
@@ -0,0 +1,70 @@
+% This is a regression test for a code generation bug, fixed
+% on 16 november 1999.
+%
+% The bug was that if the failure continuation was a known address,
+% the code in code_info.m for implementing commits assumed that the
+% redoip slot of the top nondet stack frame had this address in it,
+% and that therefore it could override this slot without remembering
+% what was originally in it.
+%
+% The determinism declarations of foo and bar are intentionally too loose;
+% the bug does not reveal itself, even if it exists, with the correct, tight
+% determinism declarations. The test for the bug also requires compilation
+% with inlining turned off.
+
+:- module redoip_clobber.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io__state, io__state).
+:- mode main(di, uo) is det.
+
+:- implementation.
+
+:- import_module int, std_util.
+
+:- pred foo(int).
+:- mode foo(out) is nondet.
+
+foo(X) :- bar(X), fail.
+foo(X) :- X = 2.
+
+:- pred bar(int).
+:- mode bar(out) is nondet.
+
+bar(X) :- X = 1.
+
+:- pred use(int).
+:- mode use(in) is semidet.
+
+:- pragma c_code(use(X::in),
+	[will_not_call_mercury],
+"
+	/*
+	** To exhibit the bug, this predicate needs only to fail.
+	** However, the symptom of the bug is an infinite loop.
+	** To detect the presence of the bug in finite time,
+	** we abort execution if this code is executed too many times.
+	**
+	** We mention X here to shut up a warning.
+	*/
+
+	static int counter = 0;
+
+	if (++counter > 100) {
+		fatal_error(""the bug is back"");
+	}
+
+	SUCCESS_INDICATOR = FALSE;
+").
+
+main -->
+	( { foo(X), use(X) } ->
+		io__write_string("Succeeded."),
+		nl
+	;
+		io__write_string("Failed."),
+		nl
+	).
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing trial
cvs diff: Diffing util
--------------------------------------------------------------------------
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