[m-rev.] Re: --optimize-dups bug

[Zoltan Somogyi]

On 14-Nov-2006, Ian MacLarty <maclarty at csse.unimelb.edu.au> wrote:
> The following code results in a non-terminating executable when compiled
> at -O2 in grade asm_fast.gc with ROTD 2006-11-12.

Here is the fix; I will commit it after bootcheck.

Zoltan.

Fix a bug reported by Ian.

compiler/peephole.m:
	Document the restriction on the application of the patterns concerning
	assignments to redoips.

compiler/opt_util.m:
	Fix the bug in the utility predicate used by peephole.m.

tests/hard_coded/opt_dup_bug.{m,exp}:
	The test case provided by Ian, with an explanation of the bug.

tests/hard_coded/Mmakefile:
tests/hard_coded/Mercury.options:
	Enable the new test case, and run it with the options that expose the
	bug if it exists.

cvs diff: Diffing .
cvs diff: Diffing analysis
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/doc
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing boehm_gc/windows-untested
cvs diff: Diffing boehm_gc/windows-untested/vc60
cvs diff: Diffing boehm_gc/windows-untested/vc70
cvs diff: Diffing boehm_gc/windows-untested/vc71
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/opt_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/opt_util.m,v
retrieving revision 1.156
diff -u -b -r1.156 opt_util.m
--- compiler/opt_util.m	1 Nov 2006 02:31:09 -0000	1.156
+++ compiler/opt_util.m	14 Nov 2006 01:06:05 -0000
@@ -57,7 +57,8 @@
 
     % Find the next assignment to the redoip of the frame whose address
     % is given by the base addresses in the second argument, provided
-    % it is guaranteed to be reached from here.
+    % it is guaranteed to be reached from here, and guaranteed not to be
+    % reached from anywhere else by a jump.
     %
 :- pred next_assign_to_redoip(list(instruction)::in, list(lval)::in,
     list(instruction)::in, code_addr::out, list(instruction)::out,
@@ -411,6 +412,11 @@
         Uinstr = mkframe(_, _)
     ->
         fail
+
+    ;
+        Uinstr = label(_)
+    ->
+        fail
     ;
         can_instr_branch_away(Uinstr, CanBranchAway),
         (
Index: compiler/peephole.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/peephole.m,v
retrieving revision 1.94
diff -u -b -r1.94 peephole.m
--- compiler/peephole.m	1 Nov 2006 02:31:09 -0000	1.94
+++ compiler/peephole.m	14 Nov 2006 01:05:26 -0000
@@ -213,8 +213,11 @@
 
     % If a `mkframe' is followed by an assignment to its redoip slot,
     % with the instructions in between containing only straight-line code,
-    % we can delete the assignment and instead just set the redoip
-    % directly in the `mkframe'.
+    % and no labels, we can delete the assignment and instead just set
+    % the redoip directly in the `mkframe'. (If the code between the
+    % mkframe and the redoip contains a label, then we need to keep the
+    % redoip assign, in case we reach it via the label and not from the
+    % mkframe above.
     %
     %   mkframe(NFI, _)             =>  mkframe(NFI, Redoip)
     %   <straightline instrs>           <straightline instrs>
@@ -336,8 +339,8 @@
     Instrs = [store_ticket(Lval) - Comment | Instrs2].
 
     % If an assignment to a redoip slot is followed by another, with
-    % the instructions in between containing only straight-line code,
-    % we can delete one of the asignments:
+    % the instructions in between containing only straight-line code
+    % without labels, we can delete one of the asignments:
     %
     %   assign(redoip(Fr), Redoip1) =>  assign(redoip(Fr), Redoip2)
     %   <straightline instrs>           <straightline instrs>
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing debian/patches
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
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/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_glut
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/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/stream
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
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 samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
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/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
Index: tests/hard_coded/Mercury.options
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mercury.options,v
retrieving revision 1.22
diff -u -b -r1.22 Mercury.options
--- tests/hard_coded/Mercury.options	8 Nov 2006 10:14:46 -0000	1.22
+++ tests/hard_coded/Mercury.options	14 Nov 2006 01:09:54 -0000
@@ -45,6 +45,7 @@
 MCFLAGS-no_inline_builtins =	--no-inline-builtins
 MCFLAGS-no_warn_singleton =	--halt-at-warn
 MCFLAGS-nondet_copy_out =	--no-inlining --nondet-copy-out
+MCFLAGS-opt_dup_bug	=	-O2 --optimize-dups --optimize-frames
 MCFLAGS-redoip_clobber	=	--no-inlining
 MCFLAGS-rnd		=	-O6
 MCFLAGS-split_c_files	=	--trace rep
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.301
diff -u -b -r1.301 Mmakefile
--- tests/hard_coded/Mmakefile	9 Nov 2006 00:47:25 -0000	1.301
+++ tests/hard_coded/Mmakefile	14 Nov 2006 01:13:04 -0000
@@ -15,6 +15,7 @@
 	boyer \
 	brace \
 	builtin_inst_rename \
+	c_write_string \
 	cc_and_non_cc_test \
 	cc_multi_bug \
 	cc_nondet_disj \
@@ -35,7 +36,6 @@
 	curry \
 	curry2 \
 	cut_test \
-	c_write_string \
 	cycles \
 	cycles2 \
 	deconstruct_arg \
@@ -65,8 +65,8 @@
 	existential_float \
 	existential_reordering \
 	existential_reordering_class \
-	existential_types_test \
 	existential_type_switch_opt \
+	existential_types_test \
 	expand \
 	export_test \
 	external_unification_pred \
@@ -109,6 +109,7 @@
 	impure_init_and_final \
 	impure_prune \
 	initialise_decl \
+	int_fold_up_down \
 	integer_test \
 	intermod_c_code \
 	intermod_foreign_type \
@@ -117,7 +118,6 @@
 	intermod_pragma_clause \
 	intermod_type_qual \
 	intermod_unused_args \
-	int_fold_up_down \
 	join_list \
 	list_series_int \
 	loop_inv_test \
@@ -134,13 +134,14 @@
 	no_fully_strict \
 	no_inline \
 	no_inline_builtins \
+	no_warn_singleton \
 	nonascii \
 	nondet_copy_out \
 	nondet_ctrl_vn \
-	no_warn_singleton \
-	nullary_ho_func \
 	null_char \
+	nullary_ho_func \
 	one_member \
+	opt_dup_bug \
 	ppc_bug \
 	pprint_test \
 	pprint_test2 \
@@ -152,9 +153,9 @@
 	pretty_printing \
 	prince_frameopt \
 	print_stream \
+	promise_equiv_with_svars \
 	promise_equivalent_clauses \
 	promise_equivalent_solutions_test \
-	promise_equiv_with_svars \
 	pure_mutable \
 	qual_adv_test \
 	qual_basic_test \
@@ -204,13 +205,13 @@
 	test_cord \
 	test_imported_no_tag \
 	test_promise_impure_implicit \
-	time_test \
 	tim_qual1 \
+	time_test \
 	trace_goal_1 \
 	trace_goal_2 \
 	trace_goal_3 \
-	transform_value \
 	trans_intermod_user_equality \
+	transform_value \
 	transitive_inst_type \
 	trigraphs \
 	tuple_test \
Index: tests/hard_coded/opt_dup_bug.exp
===================================================================
RCS file: tests/hard_coded/opt_dup_bug.exp
diff -N tests/hard_coded/opt_dup_bug.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/opt_dup_bug.exp	14 Nov 2006 01:17:03 -0000
@@ -0,0 +1,3 @@
+"a"
+"b"
+"c"
Index: tests/hard_coded/opt_dup_bug.m
===================================================================
RCS file: tests/hard_coded/opt_dup_bug.m
diff -N tests/hard_coded/opt_dup_bug.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/opt_dup_bug.m	14 Nov 2006 01:12:47 -0000
@@ -0,0 +1,42 @@
+% This is a regression test for a bug reported by Ian on 14 Nov 2006.
+% The bug manifests itself only if all three of --optimize-dups,
+% --optimize-frames and --optimize-peep are turned on, as they are
+% at the default optimization level. The bug was actually in peephole
+% optimization; the other two optimizations just created the circumstances
+% that tickled the bug. The bug is shown in this diff, created using
+% --debug-opt:
+%
+% -       mkframe(pred opt_dup_bug.t/2-0, 0, no, do_fail)
+% +       mkframe(pred opt_dup_bug.t/2-0, 0, no, local_8)
+%                 late setup
+%  local_14:
+% -       redoip_slot(maxfr) := code_addr_const(opt_dup_bug_t_2_0_i8)
+% -               hijack redoip to effect resume point
+%
+% The transformation is correct for code that enters the code above at the top,
+% but for code that enters by jumping to local_14, it changes the semantics of
+% the program, yielding an infinite loop.
+
+:- module opt_dup_bug.
+:- interface.
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+:- import_module solutions.
+
+main(!IO) :-
+    solutions(t("2"), Solutions),
+    io.write_list(Solutions, "\n", io.write, !IO),
+    io.nl(!IO).
+
+:- pred t(string, string).
+:- mode t(in, out) is nondet.
+
+t("2", "a").
+t("2", "b").
+t("2", "c").
+t("3", "b").
+t("3", "c").
+t("4", "c").
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------