[m-rev.] for reviews: fix optimization in unify_proc.m

Zoltan Somogyi zs at cs.mu.OZ.AU
Wed Mar 31 19:10:30 AEST 2004
Previous message: [m-rev.] diff: more cleanups
Next message: [m-rev.] for reviews: fix optimization in unify_proc.m
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
For review by Fergus.

Zoltan.

compiler/unify_proc.m:
	Reenable an optimization of unify procedures for general du types
	after fixing the problem that caused it to be disabled. This required
	placing a feature on casts from constants to integers that ask the mode
	checker to preserve any binding information it has about the constant
	as the equivalent binding information about the integer.

compiler/hlds_goal.m:
	Add this feature to the list of goal features.

compiler/modecheck_call.m:
	When processing unsafe_cast goals, respect this feature.

tests/hard_coded/det_complicated_unify2.m:
	Make this test case, which was the test case for the original problem
	with the optimization, even tougher, to make sure the new version
	works. Update the test case documentation.

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/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/hlds_goal.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.113
diff -u -b -r1.113 hlds_goal.m
--- compiler/hlds_goal.m	31 Mar 2004 08:52:22 -0000	1.113
+++ compiler/hlds_goal.m	31 Mar 2004 09:00:10 -0000
@@ -742,8 +742,16 @@
 				% be hidden. This is used e.g. by the tabling
 				% transformation to preserve the set of events
 				% generated by a tabled procedure.
-	;	tailcall.	% This goal represents a tail call. This marker
+	;	tailcall	% This goal represents a tail call. This marker
 				% is used by deep profiling.
+	;	keep_constant_binding.
+				% This feature should only be attached to
+				% unsafe_cast goals that cast a value of an
+				% user-defined type to an integer. It tells
+				% the mode checker that if the first variable
+				% is known to be bound to a given constant,
+				% then the second variable should be set
+				% to the corresponding local tag value.
 
 	% We can think of the goal that defines a procedure to be a tree,
 	% whose leaves are primitive goals and whose interior nodes are
Index: compiler/modes.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/modes.m,v
retrieving revision 1.276
diff -u -b -r1.276 modes.m
--- compiler/modes.m	31 Mar 2004 08:52:23 -0000	1.276
+++ compiler/modes.m	31 Mar 2004 09:06:36 -0000
@@ -190,7 +190,8 @@
 
 % The following predicates are used by unique_modes.m.
 
-:- import_module check_hlds__mode_info, hlds__hlds_data.
+:- import_module check_hlds__mode_info.
+:- import_module hlds__hlds_data.
 
 	% Modecheck a unification.
 
@@ -1193,9 +1194,43 @@
 		error("modecheck_goal_expr: class_method_call")
 	;
 		GenericCall = unsafe_cast,
-		modecheck_builtin_cast(Modes0, Args0, Args, Det, ExtraGoals,
+		(
+			goal_info_has_feature(GoalInfo0,
+				keep_constant_binding),
+			mode_info_get_instmap(!.ModeInfo, InstMap),
+			(
+				Args0 = [Arg1Prime, _Arg2Prime],
+				Modes0 = [Mode1Prime, Mode2Prime]
+			->
+				Arg1 = Arg1Prime,
+				Mode1 = Mode1Prime,
+				Mode2 = Mode2Prime
+			;
+				error("modecheck_goal_expr: bad unsafe_cast")
+			),
+			Mode1 = in_mode,
+			Mode2 = out_mode,
+			instmap__lookup_var(InstMap, Arg1, Inst1),
+			Inst1 = bound(Unique, [functor(ConsId, [])]),
+			mode_info_get_module_info(!.ModeInfo, ModuleInfo),
+			module_info_types(ModuleInfo, TypeTable),
+			mode_info_get_var_types(!.ModeInfo, VarTypes),
+			map__lookup(VarTypes, Arg1, ArgType1),
+			type_to_ctor_and_args(ArgType1, ArgTypeCtor1, _),
+			map__lookup(TypeTable, ArgTypeCtor1, CtorDefn),
+			get_type_defn_body(CtorDefn, Body),
+			ConsTagValues = Body ^ du_type_cons_tag_values,
+			map__lookup(ConsTagValues, ConsId, ConsTag),
+			ConsTag = shared_local_tag(_, LocalTag)
+		->
+			BoundInst = functor(int_const(LocalTag), []),
+			NewMode2 = (free -> bound(Unique, [BoundInst])),
+			Modes = [Mode1, NewMode2]
+		;
+			Modes = Modes0
+		),
+		modecheck_builtin_cast(Modes, Args0, Args, Det, ExtraGoals,
 			!ModeInfo),
-		Modes = Modes0,
 		AllArgs0 = Args0,
 		AllArgs = Args
 	;
Index: compiler/saved_vars.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/saved_vars.m,v
retrieving revision 1.37
diff -u -b -r1.37 saved_vars.m
--- compiler/saved_vars.m	24 Oct 2003 06:17:48 -0000	1.37
+++ compiler/saved_vars.m	28 Mar 2004 18:45:50 -0000
@@ -208,6 +208,7 @@
 ok_to_duplicate(preserve_backtrack_into) = no.
 ok_to_duplicate(hide_debug_event) = no.
 ok_to_duplicate(tailcall) = no.
+ok_to_duplicate(keep_constant_binding) = no.
 
 % Divide a list of goals into an initial subsequence of goals that
 % construct constants, and all other goals.
Index: compiler/unify_proc.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/unify_proc.m,v
retrieving revision 1.134
diff -u -b -r1.134 unify_proc.m
--- compiler/unify_proc.m	23 Mar 2004 06:56:42 -0000	1.134
+++ compiler/unify_proc.m	28 Mar 2004 21:07:06 -0000
@@ -680,23 +680,22 @@
 unify_proc__generate_clause_info(SpecialPredId, Type, TypeBody, Context,
 		ModuleInfo, ClauseInfo) :-
 	special_pred_interface(SpecialPredId, Type, ArgTypes, _Modes, _Det),
-	unify_proc__info_init(ModuleInfo, VarTypeInfo0),
+	unify_proc__info_init(ModuleInfo, Info0),
 	unify_proc__make_fresh_named_vars_from_types(ArgTypes, "HeadVar__", 1,
-		Args, VarTypeInfo0, VarTypeInfo1),
+		Args, Info0, Info1),
 	( SpecialPredId = unify, Args = [H1, H2] ->
 		unify_proc__generate_unify_clauses(ModuleInfo, Type, TypeBody,
-			H1, H2, Context, Clauses, VarTypeInfo1, VarTypeInfo)
+			H1, H2, Context, Clauses, Info1, Info)
 	; SpecialPredId = index, Args = [X, Index] ->
 		unify_proc__generate_index_clauses(ModuleInfo, TypeBody,
-			X, Index, Context, Clauses, VarTypeInfo1, VarTypeInfo)
+			X, Index, Context, Clauses, Info1, Info)
 	; SpecialPredId = compare, Args = [Res, X, Y] ->
 		unify_proc__generate_compare_clauses(ModuleInfo, Type,
-			TypeBody, Res, X, Y, Context, Clauses,
-			VarTypeInfo1, VarTypeInfo)
+			TypeBody, Res, X, Y, Context, Clauses, Info1, Info)
 	;
 		error("unknown special pred")
 	),
-	unify_proc__info_extract(VarTypeInfo, VarSet, Types),
+	unify_proc__info_extract(Info, VarSet, Types),
 	map__init(TVarNameMap),
 	map__init(TI_VarMap),
 	map__init(TCI_VarMap),
@@ -1193,23 +1192,15 @@
 %	__Unify__(X, Y) :-
 %		(
 %			X = a1,
-% #if 0
 %			Y = X
 %			% Actually, to avoid infinite recursion,
 %			% the above unification is done as type int:
 %			%	CastX = unsafe_cast(X) `with_type` int,
 %			%	CastY = unsafe_cast(Y) `with_type` int,
 %			%	CastX = CastY
-% #else
-%			Y = a1
-% #endif
 %		;
 %			X = a2,
-% #if 0
 %			Y = X	% Likewise, done as type int
-% #else
-%			Y = a2
-% #endif
 %		;
 %			X = b(X1),
 %			Y = b(Y2),
@@ -1226,21 +1217,20 @@
 %			X3 = Y3
 %		).
 %
-% Note that in the disjuncts handling constants, we want to unify Y with X
-% (as shown in the "#if 0 ... #else" parts), not with the constant
-% (as shown in the "#else" ... "#endif" parts).
-% Doing this allows dupelim to take the code fragments implementing
-% the switch arms for constants and eliminate all but one of them.
+% Note that in the disjuncts handling constants, we want to unify Y with X,
+% not with the constant. Doing this allows dupelim to take the code fragments
+% implementing the switch arms for constants and eliminate all but one of them.
 % This can be a significant code size saving for types with lots of constants,
 % such as the one representing Aditi bytecodes, which can lead to significant
 % reductions in C compilation time.
-% XXX But the optimization doesn't work, because it breaks determinism
-% analysis.  In particular, if X and Y both have insts `bound(a2)', then
-% determinism analysis will infer that the unification can't fail and thus
-% that the procedure is det, but casting to int loses the binding information,
-% and so mode and determinism analysis can't tell that CastX = CastY is det.
-% (See e.g. tests/general/det_complicated_unify2.m.)
-% Hence this optimization is currently disabled.
+%
+% The keep_constant_binding feature on the cast goals is there to ask
+% mode analysis to copy any known bound inst on the cast-from variable
+% to the cast-to variable. This is necessary to keep determinism analysis
+% working for modes in which the inputs of the unify predicate are known
+% to be bound to the same constant, modes whose determinism should therefore
+% be inferred to be det. (tests/general/det_complicated_unify2.m tests
+% this case.)
 
 :- pred unify_proc__generate_du_unify_clauses(list(constructor)::in,
 	prog_var::in, prog_var::in, prog_context::in, list(clause)::out,
@@ -1253,8 +1243,6 @@
 	list__length(ArgTypes, FunctorArity),
 	FunctorConsId = cons(FunctorName, FunctorArity),
 	(
-		% XXX This optimization disabled, see XXX comment above.
-		semidet_fail,
 		ArgTypes = [],
 		can_compare_constants_as_ints(!.Info) = yes
 	->
@@ -1265,8 +1253,10 @@
 			!Info),
 		unify_proc__info_new_named_var(int_type, "CastY", CastY,
 			!Info),
-		generate_unsafe_cast(X, CastX, Context, CastXGoal),
-		generate_unsafe_cast(Y, CastY, Context, CastYGoal),
+		generate_unsafe_cast(X, CastX, Context, CastXGoal0),
+		generate_unsafe_cast(Y, CastY, Context, CastYGoal0),
+		goal_add_feature(CastXGoal0, keep_constant_binding, CastXGoal),
+		goal_add_feature(CastYGoal0, keep_constant_binding, CastYGoal),
 		create_atomic_unification(CastY, var(CastX), Context,
 			explicit, [], UnifyY_Goal),
 		GoalList = [UnifyX_Goal, CastXGoal, CastYGoal, UnifyY_Goal]
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
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/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/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/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
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/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/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing java
cvs diff: Diffing java/library
cvs diff: Diffing java/runtime
cvs diff: Diffing library
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 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
Index: tests/general/det_complicated_unify2.m
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/general/det_complicated_unify2.m,v
retrieving revision 1.1
diff -u -b -r1.1 det_complicated_unify2.m
--- tests/general/det_complicated_unify2.m	12 Feb 2004 04:06:50 -0000	1.1
+++ tests/general/det_complicated_unify2.m	28 Mar 2004 20:46:36 -0000
@@ -1,6 +1,7 @@
 % This tests that the compiler handles deterministic complicated
 % unifications on enums and compound types correctly.
-% (Version 0.4 of the compiler failed this test.)
+% Version 0.4 of the compiler failed this test, as did some versions of
+% an optimization in unify_proc__generate_du_unify_clauses.
 
 :- module det_complicated_unify2.
 :- interface.
@@ -12,19 +13,55 @@
 
 :- type foo ---> foo(bar).
 :- type foo2 ---> foo2(bar) ; yyy(int).
+:- type fum ---> fum(baz).
+:- type fum2 ---> fum2(baz) ; yyy(int).
 :- type bar ---> bar ; zzz(int).
+:- type baz ---> baz1 ; baz2 ; zzz(int).
 
-main -->
-	{ p(foo(bar),foo(bar)), p2(foo2(bar),foo2(bar)), q(bar, bar) },
-	io__write_string("worked\n").
+main(!IO) :-
+	p(foo(bar), foo(bar)),
+	p1(foo2(bar),foo2(bar)),
+	q(bar, bar),
+	r(fum(baz1), fum(baz1)),
+	r1(fum2(baz1),fum2(baz1)),
+	r2(fum2(baz2),fum2(baz2)),
+	s1(baz1, baz1),
+	s2(baz2, baz2),
+	io__write_string("worked\n", !IO).
 
 :- pred p(foo::in(bound(foo(bound(bar)))), foo::in(bound(foo(bound(bar)))))
 	is det.
+
 p(X, X).
 
-:- pred p2(foo2::in(bound(foo2(bound(bar)))),
+:- pred p1(foo2::in(bound(foo2(bound(bar)))),
 	foo2::in(bound(foo2(bound(bar))))) is det.
-p2(X, X).
+
+p1(X, X).
 
 :- pred q(bar::in(bound(bar)), bar::in(bound(bar))) is det.
+
 q(X, X).
+
+:- pred r(fum::in(bound(fum(bound(baz1)))), fum::in(bound(fum(bound(baz1)))))
+	is det.
+
+r(X, X).
+
+:- pred r1(fum2::in(bound(fum2(bound(baz1)))),
+	fum2::in(bound(fum2(bound(baz1))))) is det.
+
+r1(X, X).
+
+:- pred r2(fum2::in(bound(fum2(bound(baz2)))),
+	fum2::in(bound(fum2(bound(baz2))))) is det.
+
+r2(X, X).
+
+:- pred s1(baz::in(bound(baz1)), baz::in(bound(baz1))) is det.
+
+s1(X, X).
+
+:- pred s2(baz::in(bound(baz2)), baz::in(bound(baz2))) is det.
+
+s2(X, X).
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
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/recompilation
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 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:  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
--------------------------------------------------------------------------
Previous message: [m-rev.] diff: more cleanups
Next message: [m-rev.] for reviews: fix optimization in unify_proc.m
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the reviews mailing list