[m-dev.] diff for review

[Simon TAYLOR]

Hi Fergus,

> > 	Fix a code generator abort for if-then-elses with conditions
> > 	that cannot succeed by fixing and enabling the code to optimise
> > 	away such cases.
> 
> Why did the code generator abort for such conditions?
> 

The condition of the if-then-else always failed, so the instmap after the
condition was not_reached. The code generator didn't produce any code for
the then part, but then attempted to produce the variables that the then
part should have created when generating the branch end. 

> Fixing things only in simplify.m means that every optimization that
> transforms the code needs to be careful to not introduce such constructs. 

Simplify is run just before code generation to remove constructs that the
code generator can't handle. 

> Hence in general, it is better if the code generator can handle such things.

OK.

Here's the updated diff:


Estimated hours taken: 4

Bug fixes.

compiler/code_info.m
	Fix a code generator abort for if-then-elses with conditions
	that cannot succeed by having code_info__generate_branch_end
	do nothing if the instmap is unreachable.

compiler/simplify.m
	Fix and enable the code to optimize if-then-elses that cannot
	succeed.
	Stop warnings appearing multiple times, make sure the warnings
	appear in the correct order.
	Produce warnings for all cases of a negated goal not succeeding
	or failing, not just \+ true and \+ fail.

compiler/modes.m
	Remove code to optimize if-then-elses with conditions that cannot
	succeed, since that is now done in simplify.m. Also the code in 
	modes.m was buggy, in that it set the instmap_delta of the negated
	condition to reachable, even if the condition's determinism turned
	out to be erroneous. This couldn't be fixed easily, because
	determinism information is not available in modes.m

compiler/unique_modes.m
	Removed the commented out version of the if-then-else optimization
	removed from mode analysis.

tests/warnings/simple_code.{m, exp}
	Test cases for the warnings from simplify.m

tests/valid/fail_ite.m
	Regression test for the abort.


Index: code_info.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/code_info.m,v
retrieving revision 1.198
diff -u -r1.198 code_info.m
--- code_info.m	1997/04/04 04:41:08	1.198
+++ code_info.m	1997/04/22 07:06:28
@@ -2493,15 +2493,22 @@
 %---------------------------------------------------------------------------%
 
 code_info__generate_branch_end(CodeModel, StoreMap, Code) -->
-	code_info__get_exprn_info(Exprn0),
-	{ map__to_assoc_list(StoreMap, VarLocs) },
-	{ code_exprn__place_vars(VarLocs, PlaceCode, Exprn0, Exprn) },
-	code_info__set_exprn_info(Exprn),
-	( { CodeModel = model_non } ->
-		code_info__unset_failure_cont(FlushCode),
-		{ Code = tree(PlaceCode, FlushCode) }
+	code_info__get_instmap(InstMap),
+	( { instmap__is_unreachable(InstMap) } ->
+		% Execution never reaches here, don't generate code
+		% to place the variables.
+		{ Code = empty }
 	;
-		{ Code = PlaceCode }
+		code_info__get_exprn_info(Exprn0),
+		{ map__to_assoc_list(StoreMap, VarLocs) },
+		{ code_exprn__place_vars(VarLocs, PlaceCode, Exprn0, Exprn) },
+		code_info__set_exprn_info(Exprn),
+		( { CodeModel = model_non } ->
+			code_info__unset_failure_cont(FlushCode),
+			{ Code = tree(PlaceCode, FlushCode) }
+		;
+			{ Code = PlaceCode }
+		)
 	).
 
 code_info__remake_with_store_map(StoreMap) -->
Index: modes.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/modes.m,v
retrieving revision 1.197
diff -u -r1.197 modes.m
--- modes.m	1997/04/21 13:40:05	1.197
+++ modes.m	1997/04/22 04:42:19
@@ -719,7 +719,6 @@
 	modecheck_goal(A0, A),
 	mode_info_remove_live_vars(B_Vars),
 	mode_info_unlock_vars(NonLocals),
-	mode_info_dcg_get_instmap(InstMapA),
 	modecheck_goal(B0, B),
 	mode_info_dcg_get_instmap(InstMapB),
 	mode_info_set_instmap(InstMap0),
@@ -727,29 +726,7 @@
 	mode_info_dcg_get_instmap(InstMapC),
 	mode_info_set_instmap(InstMap0),
 	instmap__merge(NonLocals, [InstMapB, InstMapC], if_then_else),
-	( { instmap__is_unreachable(InstMapA) } ->
-		% if the condition can never succeed, we delete the
-		% unreachable `then' part by replacing
-		%	if some [Vs] A then B else C
-		% with
-		%	(not some [Vs] A), C
-		{ goal_get_nonlocals(A, A_Vars) },
-		{ goal_get_nonlocals(C, C_Vars) },
-		{ set__union(NonLocals, C_Vars, OutsideVars) },
-		{ set__delete_list(OutsideVars, Vs, OutsideVars1) },
-		{ set__intersect(OutsideVars1, A_Vars, SomeA_NonLocals) },
-		{ goal_info_init(EmptyGoalInfo) },
-		{ goal_info_set_nonlocals(EmptyGoalInfo, SomeA_NonLocals,
-			SomeA_GoalInfo) },
-		{ instmap_delta_init_reachable(EmptyInstmapDelta) },
-		{ goal_info_set_instmap_delta(SomeA_GoalInfo,
-			EmptyInstmapDelta, NotSomeA_GoalInfo) },
-		
-		{ Goal = conj([not(some(Vs, A) - SomeA_GoalInfo) -
-				NotSomeA_GoalInfo, C]) }
-	;
-		{ Goal = if_then_else(Vs, A, B, C, SM) }
-	),
+	{ Goal = if_then_else(Vs, A, B, C, SM) },
 	mode_checkpoint(exit, "if-then-else").
 
 modecheck_goal_expr(not(A0), GoalInfo0, not(A)) -->
Index: simplify.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/simplify.m,v
retrieving revision 1.29
diff -u -r1.29 simplify.m
--- simplify.m	1997/04/08 02:26:34	1.29
+++ simplify.m	1997/04/22 08:33:38
@@ -80,9 +80,8 @@
 		VarSet0, VarTypes0, Info0),
 	write_pred_progress_message("% Simplifying ", PredId, ModuleInfo0,
 		State1, State2),
+	Simplify = simplify(Warn, WarnCalls, Once, Switch, _, Excess, Calls),
 	( simplify_do_common(Info0) ->
-		Simplify = simplify(Warn, WarnCalls, Once, 
-				Switch, _, Excess, Calls),
 		% On the first pass do common structure elimination and
 		% branch merging.
 		simplify_info_set_simplify(Info0,
@@ -94,7 +93,7 @@
 		proc_info_variables(Proc1, VarSet1),
 		proc_info_vartypes(Proc1, VarTypes1),
 		simplify_info_init(DetInfo,
-			simplify(Warn, WarnCalls, Once, no, no, Excess, no),
+			simplify(no, no, Once, no, no, Excess, no),
 			InstMap0, VarSet1, VarTypes1, Info3),
 		simplify_info_set_msgs(Info3, Msgs1, Info4),
 		%proc_info_goal(Proc1, OutGoal),
@@ -113,8 +112,8 @@
 	simplify__proc_2(Proc1, Proc, ModuleInfo1, ModuleInfo,
 			Info4, Info, State4, State5),
 	simplify_info_get_msgs(Info, Msgs2),
-	set__to_sorted_list(Msgs2, Msgs),
-	( simplify_do_warn(Info) ->
+	list__reverse(Msgs2, Msgs),
+	( (Warn = yes ; WarnCalls = yes) ->
 		det_report_msgs(Msgs, ModuleInfo, WarnCnt,
 			ErrCnt, State5, State)
 	;
@@ -472,40 +471,55 @@
 	% is finished, or when we start doing coroutining.
 
 simplify__goal_2(if_then_else(Vars, Cond0, Then0, Else0, SM),
-		GoalInfo, Goal, GoalInfo, Info0, Info) :-
+		GoalInfo0, Goal, GoalInfo, Info0, Info) :-
 	Cond0 = _ - CondInfo0,
 
 	goal_info_get_determinism(CondInfo0, CondDetism),
-	determinism_components(CondDetism, CondCanFail, _CondSolns),
+	determinism_components(CondDetism, CondCanFail, CondSolns),
 	( CondCanFail = cannot_fail ->
 		goal_to_conj_list(Cond0, CondList),
 		goal_to_conj_list(Then0, ThenList),
 		list__append(CondList, ThenList, List),
-		simplify__goal(conj(List) - GoalInfo, Goal - _,
+		simplify__goal(conj(List) - GoalInfo0, Goal - GoalInfo,
 			Info0, Info1),
 		simplify_info_add_msg(Info1, ite_cond_cannot_fail(GoalInfo),
 			Info)
-/*********
-	The following optimization is disabled, because it is
-	buggy (see the XXX below).  It's not important, since
-	most of these cases will be optimized by modes.m anyway.
 	; CondSolns = at_most_zero ->
 		% Optimize away the condition and the `then' part.
+		goal_info_get_determinism(CondInfo0, Detism),
+		det_negation_det(Detism, MaybeNegDetism),
+		(
+			MaybeNegDetism = yes(NegDetism1),
+			(
+				NegDetism1 = erroneous,
+				instmap_delta_init_unreachable(
+					NegInstMapDelta1)
+			;
+				NegDetism1 = det,
+				instmap_delta_init_reachable(NegInstMapDelta1)
+			)
+		->
+			NegDetism = NegDetism1,
+			NegInstMapDelta = NegInstMapDelta1
+		;
+			error("simplify__goal_2: cannot get negated determinism")
+		),
+		goal_info_set_determinism(CondInfo0, NegDetism, NegCondInfo0),
+		goal_info_set_instmap_delta(NegCondInfo0, 
+			NegInstMapDelta, NegCondInfo),
 		goal_to_conj_list(Else0, ElseList),
-		% XXX Using CondInfo without updating the determinism is a bug.
-		% We should probably update other goal_info fields as well,
-		% e.g. the instmap_delta.
-		List = [not(Cond0) - CondInfo | ElseList],
-		simplify__goal(conj(List) - GoalInfo, InstMap0, DetInfo,
-			Goal - _, Msgs1),
-		Msgs = [ite_cond_cannot_succeed(GoalInfo) | Msgs1]
-**********/
+		List = [not(Cond0) - NegCondInfo | ElseList],
+		simplify__goal(conj(List) - GoalInfo0, Goal - GoalInfo,
+			Info0, Info1),
+		simplify_info_add_msg(Info1, ite_cond_cannot_succeed(GoalInfo),
+			Info)
 	; Else0 = disj([], _) - _ ->
 		% (A -> C ; fail) is equivalent to (A, C)
 		goal_to_conj_list(Cond0, CondList),
 		goal_to_conj_list(Then0, ThenList),
 		list__append(CondList, ThenList, List),
-		simplify__goal(conj(List) - GoalInfo, Goal - _, Info0, Info)
+		simplify__goal(conj(List) - GoalInfo0, Goal - GoalInfo,
+			Info0, Info)
 	;
 		simplify__goal(Cond0, Cond, Info0, Info1),
 		simplify_info_update_instmap(Info1, Cond, Info2),
@@ -523,7 +537,8 @@
 		goal_info_get_instmap_delta(ElseInfo, ElseDelta),
 		simplify_info_create_branch_info(Info0, Info6,
 			[ElseDelta, CondThenDelta], Info),
-		Goal = if_then_else(Vars, Cond, Then, Else, SM)
+		Goal = if_then_else(Vars, Cond, Then, Else, SM),
+		GoalInfo = GoalInfo0
 	).
 
 simplify__goal_2(not(Goal0), GoalInfo, Goal, GoalInfo, Info0, Info) :-
@@ -532,24 +547,36 @@
 	simplify_info_get_common_info(Info0, Common),
 	simplify__goal(Goal0, Goal1, Info0, Info1),
 	simplify_info_set_common_info(Info1, Common, Info2),
+	Goal1 = _ - GoalInfo1,
+	goal_info_get_determinism(GoalInfo1, Detism),
+	determinism_components(Detism, CanFail, MaxSoln),
+	( CanFail = cannot_fail ->
+		simplify_info_add_msg(Info2,
+			negated_goal_cannot_fail(GoalInfo), Info)
+	; MaxSoln = at_most_zero ->
+		simplify_info_add_msg(Info2,
+			negated_goal_cannot_succeed(GoalInfo), Info)
+	;
+		Info = Info2
+	),
 	(
 		% replace `not true' with `fail'
 		Goal1 = conj([]) - _GoalInfo
 	->
 		map__init(Empty),
-		Goal = disj([], Empty),
-		simplify_info_add_msg(Info2,
-			negated_goal_cannot_fail(GoalInfo), Info)
+		Goal = disj([], Empty)
 	;
 		% replace `not fail' with `true'
 		Goal1 = disj([], _) - _GoalInfo2
 	->
-		Goal = conj([]),
-		simplify_info_add_msg(Info1,
-			negated_goal_cannot_succeed(GoalInfo), Info)
+		Goal = conj([])
 	;
-		Goal = not(Goal1),
-		Info = Info2
+		% remove double negation
+		Goal1 = not(SubGoal - _) - _
+	->
+		Goal = SubGoal
+	;
+		Goal = not(Goal1)
 	).
 
 simplify__goal_2(some(Vars1, Goal1), SomeInfo, Goal, SomeInfo, Info0, Info) :-
@@ -1115,7 +1142,7 @@
 :- type simplify_info
 	--->	simplify_info(
 			det_info,
-			set(det_msg),
+			list(det_msg),
 			simplify,	% How much simplification to do.
 			common_info,	% Info about common subexpressions.
 			instmap,
@@ -1139,16 +1166,15 @@
 		).
 
 simplify_info_init(DetInfo, Simplify, InstMap, VarSet, VarTypes, Info) :-
-	set__init(Msgs),
 	common_info_init(CommonInfo),
-	Info = simplify_info(DetInfo, Msgs, Simplify, CommonInfo,
+	Info = simplify_info(DetInfo, [], Simplify, CommonInfo,
 			InstMap, VarSet, VarTypes, no, no, no). 
 
 	% exported for common.m
 :- interface.
 
 :- pred simplify_info_get_det_info(simplify_info::in, det_info::out) is det.
-:- pred simplify_info_get_msgs(simplify_info::in, set(det_msg)::out) is det.
+:- pred simplify_info_get_msgs(simplify_info::in, list(det_msg)::out) is det.
 :- pred simplify_info_get_instmap(simplify_info::in, instmap::out) is det.
 :- pred simplify_info_get_simplify(simplify_info::in, simplify::out) is det.
 :- pred simplify_info_get_common_info(simplify_info::in,
@@ -1192,7 +1218,7 @@
 :- pred simplify_info_set_det_info(simplify_info::in,
 		det_info::in, simplify_info::out) is det.
 :- pred simplify_info_set_msgs(simplify_info::in,
-		set(det_msg)::in, simplify_info::out) is det.
+		list(det_msg)::in, simplify_info::out) is det.
 :- pred simplify_info_set_simplify(simplify_info::in,
 		simplify::in, simplify_info::out) is det.
 :- pred simplify_info_set_instmap(simplify_info::in,
@@ -1245,8 +1271,7 @@
 simplify_info_add_msg(Info0, Msg, Info) :-
 	( simplify_do_warn(Info0) ->
 		simplify_info_get_msgs(Info0, Msgs0),
-		set__insert(Msgs0, Msg, Msgs),
-		simplify_info_set_msgs(Info0, Msgs, Info)
+		simplify_info_set_msgs(Info0, [Msg | Msgs0], Info)
 	;
 		Info = Info0
 	).
Index: unique_modes.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/unique_modes.m,v
retrieving revision 1.34
diff -u -r1.34 unique_modes.m
--- unique_modes.m	1997/04/08 02:26:43	1.34
+++ unique_modes.m	1997/04/15 07:10:19
@@ -452,32 +452,6 @@
 	mode_info_dcg_get_instmap(InstMapC),
 	mode_info_set_instmap(InstMap0),
 	instmap__merge(NonLocals, [InstMapB, InstMapC], if_then_else),
-/*
-% this optimization from modes.m does not need to be repeated here
-	( { InstMapA = unreachable } ->
-		% if the condition can never succeed, we delete the
-		% unreachable `then' part by replacing
-		%	if some [Vs] A then B else C
-		% with
-		%	(not some [Vs] A), C
-		{ A = _A_Goal - A_GoalInfo },
-		{ goal_info_get_nonlocals(A_GoalInfo, A_Vars) },
-		{ set__union(NonLocals, C_Vars, OutsideVars) },
-		{ set__delete_list(OutsideVars, Vs, OutsideVars1) },
-		{ set__intersect(OutsideVars1, A_Vars, SomeA_NonLocals) },
-		{ goal_info_init(EmptyGoalInfo) },
-		{ goal_info_set_nonlocals(EmptyGoalInfo, SomeA_NonLocals,
-			SomeA_GoalInfo) },
-		{ map__init(EmptyInstmapDelta) },
-		{ goal_info_set_instmap_delta(SomeA_GoalInfo,
-			reachable(EmptyInstmapDelta), NotSomeA_GoalInfo) },
-		
-		{ Goal = conj([not(some(Vs, A) - SomeA_GoalInfo) -
-				NotSomeA_GoalInfo, C]) }
-	;
-		{ Goal = if_then_else(Vs, A, B, C) }
-	),
-*/
 	{ Goal = if_then_else(Vs, A, B, C, SM) },
 	mode_checkpoint(exit, "if-then-else").
 

Index: tests/valid/Mmake
===================================================================
RCS file: /home/staff/zs/imp/tests/valid/Mmake,v
retrieving revision 1.33
diff -u -r1.33 Mmake
--- Mmake	1997/04/21 13:43:58	1.33
+++ Mmake	1997/04/22 04:43:46
@@ -19,6 +19,7 @@
 	easy_nondet_test_2.m \
 	empty_switch.m \
 	error.m \
+	fail_ite.m \
 	followcode_det_problem.m \
 	headvar_not_found.m \
 	higher_order.m \
Index: tests/warnings/Mmake
===================================================================
RCS file: /home/staff/zs/imp/tests/warnings/Mmake,v
retrieving revision 1.16
diff -u -r1.16 Mmake
--- Mmake	1997/04/21 07:09:10	1.16
+++ Mmake	1997/04/22 04:43:50
@@ -6,7 +6,7 @@
 
 PROGS=	unused_args_test singleton_test \
 	unused_import pragma_source_file missing_if double_underscore \
-	duplicate_call infinite_recursion
+	duplicate_call infinite_recursion simple_code
 
 #-----------------------------------------------------------------------------#
 
Index: tests/warnings/infinite_recursion.exp
===================================================================
RCS file: /home/staff/zs/imp/tests/warnings/infinite_recursion.exp,v
retrieving revision 1.1
diff -u -r1.1 infinite_recursion.exp
--- infinite_recursion.exp	1997/02/08 16:16:44	1.1
+++ infinite_recursion.exp	1997/04/15 04:46:12
@@ -1,5 +1,3 @@
 infinite_recursion.m:013: Warning: recursive call will lead to infinite recursion.
-infinite_recursion.m:013: Warning: recursive call will lead to infinite recursion.
 infinite_recursion.m:022: Warning: recursive call will lead to infinite recursion.
-infinite_recursion.m:034: Warning: recursive call will lead to infinite recursion.
 infinite_recursion.m:034: Warning: recursive call will lead to infinite recursion.


:- module fail_ite.
:- interface.
:- import_module io.
:- pred p(io__state::di, io__state::uo) is det.
:- implementation.
:- import_module require.
p --> 
	( { \+ det_pred } ->
		[]
	;
		[]
	),
	( { \+ fail_pred } ->
		[]
	;
		[]
	),
	( { error("blah") } ->
		[]
	;
		[]
	).


:- pred det_pred is det.

det_pred.

:- pred fail_pred is failure.

fail_pred :- fail.



:- module simple_code.
:- interface.
:- import_module io.
:- pred p(int::in, int::out) is erroneous.
:- implementation.
:- import_module require.
p --> 
	(
		[]
	;
		{ error("foo") }
	),
	( { true } ->
		{ Z = 2 }	
	;
		{ Z = 3 }
	),
	( { X = 3, X = 2, Z = 2 } ->
		[]
	;
		[]
	),
	( { \+ true } ->
		[]
	;
		[]
	),
	( { \+ det_pred } ->
		[]
	;
		[]
	),
	( { \+ fail_pred } ->
		[]
	;
		[]
	),
	{ \+ fail },
	{ obsolete },
	( { error("blah") } ->
		[]
	;
		[]
	).

:- pred det_pred is det.

det_pred.

:- pred fail_pred is failure.

fail_pred :- fail.

:- pred obsolete is det.
:- pragma obsolete(obsolete/0).

obsolete.



simple_code.m:010: Warning: this disjunct will never have any solutions.
simple_code.m:015: Warning: the condition of this if-then-else cannot fail.
simple_code.m:020: Warning: the condition of this if-then-else cannot succeed.
simple_code.m:025: Warning: the condition of this if-then-else cannot succeed.
simple_code.m:028: Warning: the negated goal cannot fail.
simple_code.m:028: Warning: the negated goal cannot succeed.
simple_code.m:030: Warning: the condition of this if-then-else cannot succeed.
simple_code.m:033: Warning: the negated goal cannot succeed.
simple_code.m:035: Warning: the condition of this if-then-else cannot fail.
simple_code.m:033: Warning: the negated goal cannot succeed.
simple_code.m:039: Warning: call to obsolete predicate `simple_code:obsolete/0'.
simple_code.m:042: Warning: the condition of this if-then-else cannot fail.