switch detection of if-then-elses

[Fergus Henderson]

Hi,

I just wrote the code for doing switch detection of if-then-elses,
as suggested by Henk.

What does everyone think about making this change to the language?
It does complicate the language a little bit.  Opinions?

Tom, can you please review the code for this one?

Estimated hours taken: 6

Improve switch detection: where possible, convert if-then-elses into switches.

compiler/switch_detection.m:
	If the condition of an if-then-else tests an input variable for
	having a particular functor, and the `else' part tests or
	switches on the same variable having a different functor or set
	of functors, then convert the if-then-else into a switch.

	Note that although this change does convert chained
	if-then-elses into a single switch, examples where the final
	`else' part is a default case, e.g.

		( X = a -> Y = 1
		; X = b -> Y = 2
		; X = c -> Y = 3
		; Y = 4
		)
	
	will not be turned into switches, because the `else' part
	does not test the variable.  Transforming examples into
	if-then-elses whose condition is a switch would be a lot
	trickier, particularly because of the requirement that
	the condition of an if-then-else not bind non-local variables,
	and also because it could introduce spurious uniqueness errors.
	The fact that we don't transform such cases does not
	cause determinism errors, but doing the transformation
	might improve the efficiency of the generated code.

--- switch_detection.m.old	Sat Feb 22 20:18:33 1997
+++ switch_detection.m	Sun Feb 23 15:18:04 1997
@@ -146,12 +146,46 @@
 	detect_switches_in_goal(Goal0, InstMap0, VarTypes, ModuleInfo, Goal).
 
 detect_switches_in_goal_2(if_then_else(Vars, Cond0, Then0, Else0, SM),
-		_GoalInfo, InstMap0, VarTypes, ModuleInfo,
-		if_then_else(Vars, Cond, Then, Else, SM)) :-
+		GoalInfo, InstMap0, VarTypes, ModuleInfo, Goal) :-
+	%
+	% First detect switches in the subgoals.
+	%
 	detect_switches_in_goal_1(Cond0, InstMap0, VarTypes, ModuleInfo, Cond,
 		InstMap1),
 	detect_switches_in_goal(Then0, InstMap1, VarTypes, ModuleInfo, Then),
-	detect_switches_in_goal(Else0, InstMap0, VarTypes, ModuleInfo, Else).
+	detect_switches_in_goal(Else0, InstMap0, VarTypes, ModuleInfo, Else),
+	IfThenElse = if_then_else(Vars, Cond, Then, Else, SM),
+
+	%
+	% Then see if we can change the if-then-else into a switch.
+	%
+
+	% get the nonlocals for the whole if-then-else
+	goal_info_get_nonlocals(GoalInfo, NonLocals),
+	set__to_sorted_list(NonLocals, NonLocalsList),
+
+	% get the variables that we might be able to switch on
+	Cond = _CondGoal - CondGoalInfo,
+	Else = _ElseGoal - ElseGoalInfo,
+	goal_info_get_nonlocals(CondGoalInfo, CondNonLocals),
+	goal_info_get_nonlocals(ElseGoalInfo, ElseNonLocals),
+	set__intersect(CondNonLocals, ElseNonLocals, PotentialSwitchVars),
+	set__to_sorted_list(PotentialSwitchVars, PotentialSwitchVarsList),
+
+	% treat the if-then-else as a singleton disjunction and
+	% see if we can turn it into a switch (by splitting up
+	% the if-then and then else parts into separate cases)
+	(
+		detect_full_switch_in_disj(PotentialSwitchVarsList,
+			[IfThenElse - GoalInfo],
+			GoalInfo, SM, InstMap0, VarTypes, NonLocalsList,
+			ModuleInfo, [], SwitchGoal),
+		SwitchGoal = switch(_, _, _, _)
+	->
+		Goal = SwitchGoal
+	;
+		Goal = IfThenElse
+	).
 
 detect_switches_in_goal_2(some(Vars, Goal0), _GoalInfo, InstMap0,
 		VarTypes, ModuleInfo, some(Vars, Goal)) :-
@@ -249,6 +283,31 @@
 		Goals = [SwitchGoal - GoalInfo | LeftList]
 	).
 
+:- pred detect_full_switch_in_disj(list(var), list(hlds_goal), hlds_goal_info,
+	store_map, instmap, map(var, type), list(var), module_info,
+	list(again), hlds_goal_expr).
+:- mode detect_full_switch_in_disj(in, in, in, in, in, in, in, in, in, out)
+	is semidet.
+
+detect_full_switch_in_disj([Var | Vars], Goals0, GoalInfo, SM, InstMap,
+		VarTypes, AllVars, ModuleInfo, Again0, Goal) :-
+	% can we do a switch on this variable, with no disjuncts left over?
+	(
+		instmap__lookup_var(InstMap, Var, VarInst0),
+		inst_is_bound(ModuleInfo, VarInst0),
+		partition_disj(Goals0, Var, GoalInfo, LeftOver, CasesList),
+		LeftOver = []
+	->
+		cases_to_switch(CasesList, Var, VarTypes, GoalInfo,
+			SM, InstMap, ModuleInfo, Goal)
+	;
+		% otherwise try switching on some other variable
+		detect_full_switch_in_disj(Vars, Goals0, GoalInfo, SM, InstMap,
+			VarTypes, AllVars, ModuleInfo, Again0, Goal)
+	).
+
+%-----------------------------------------------------------------------------%
+
 :- pred select_best_switch(list(again), again, again).
 :- mode select_best_switch(in, in, out) is det.
 
@@ -305,7 +364,8 @@
 
 	% partition_disj(Goals, Var, GoalInfo, VarTypes, ModuleInfo,
 	%	Left, Cases):
-	% Attempts to partition the disjunction `Goals' into a switch on `Var'.
+	% Attempts to partition the disjunction `Goals' into a switch on `Var',
+	% converting if-then-elses in `Goals' into switches if necessary.
 	% If at least partially successful, returns the resulting `Cases', with
 	% any disjunction goals not fitting into the switch in Left.
 
@@ -321,39 +381,93 @@
 :- mode partition_disj(in, in, in, out, out) is semidet.
 
 partition_disj(Goals0, Var, GoalInfo, Left, CasesList) :-
-	map__init(Cases0),
-	partition_disj_trial(Goals0, Var, [], Left, Cases0, Cases),
-	map__to_assoc_list(Cases, CasesAssocList),
-	fix_case_list(CasesAssocList, GoalInfo, CasesList),
-	CasesList = [_, _ | _].	% there must be more than one case
+	map__init(CasesMap0),
+	partition_disj_trial(Goals0, Var, [], Left, CasesMap0, CasesMap),
+	map__to_assoc_list(CasesMap, CasesAssocList),
+	CasesAssocList = [_, _ | _],	% there must be more than one case
+	fix_case_list(CasesAssocList, GoalInfo, CasesList).
 
 :- pred partition_disj_trial(list(hlds_goal), var,
 	list(hlds_goal), list(hlds_goal), cases, cases).
 :- mode partition_disj_trial(in, in, in, out, in, out) is det.
 
-partition_disj_trial([], _Var, Left, Left, Cases, Cases).
-partition_disj_trial([Goal0 | Goals], Var, Left0, Left, Cases0, Cases) :-
-	goal_to_conj_list(Goal0, ConjList0),
-	Goal0 = _ - GoalInfo,
-	map__init(Substitution),
-	find_bind_var_for_switch(ConjList0, Substitution, Var,
-			ConjList, _NewSubstitution, MaybeFunctor),
+partition_disj_trial([], _Var, Left, Left, CasesMap, CasesMap).
+partition_disj_trial([Goal0 | Goals], Var, Left0, Left, CasesMap0, CasesMap) :-
 	(
-		MaybeFunctor = yes(Functor),
+		%
+		% First just try partitioning the goal into cases.
+		%
+		partition_into_cases(Goal0, Var, Cases)
+	->
 		Left1 = Left0,
-		conj_list_to_goal(ConjList, GoalInfo, Goal),
-		( map__search(Cases0, Functor, DisjList0) ->
-			DisjList1 = [Goal | DisjList0]
-		;
-			DisjList1 = [Goal]
-		),
-		map__set(Cases0, Functor, DisjList1, Cases1)
+		insert_cases_into_cases_map(CasesMap0, Cases, CasesMap1)
 	;
-		MaybeFunctor = no,
+		%
+		% if that didn't succeed, check if the goal is an
+		% if-then-else, and if so see if we can turn it into
+		% a switch by splitting up the `if-then' and the `else'.
+		% We can do that if the condition tests the variable,
+		% and the `else' part also tests or switches on the variable,
+		% but with a different functor or set of functors.
+		% (We don't handle the situation where the condition
+		% switches on the variable, because that would require
+		% duplicating the `then' part of the switch for each
+		% different case in the condition.)
+		%
+		Goal0 = if_then_else(_Vars, Cond0, Then0, Else0, _SM) -
+				GoalInfo,
+		partition_into_cases(Cond0, Var, CondCases),
+		CondCases = [case(CondFunctor, Cond)],
+		partition_into_cases(Else0, Var, ElseCases),
+		\+ list__member(case(CondFunctor, _), ElseCases)
+	->
+		Left1 = Left0,
+		goal_to_conj_list(Cond, CondList),
+		goal_to_conj_list(Then0, ThenList0),
+		list__append(CondList, ThenList0, CondAndThenList),
+		conj_list_to_goal(CondAndThenList, GoalInfo, CondAndThen),
+		insert_goal_into_cases_map(CasesMap0, CondFunctor, CondAndThen,
+			CasesMapCond),
+		insert_cases_into_cases_map(CasesMapCond, ElseCases, CasesMap1)
+	;
+		%
+		% we couldn't partition this disjunct; just insert
+		% it into the list of left-over disjuncts
+		%
 		Left1 = [Goal0 | Left0],
-		Cases1 = Cases0
+		CasesMap1 = CasesMap0
 	),
-	partition_disj_trial(Goals, Var, Left1, Left, Cases1, Cases).
+	partition_disj_trial(Goals, Var, Left1, Left, CasesMap1, CasesMap).
+
+:- pred partition_into_cases(hlds_goal, var, list(case)).
+:- mode partition_into_cases(in, in, out) is semidet.
+
+partition_into_cases(Goal - GoalInfo, Var, Cases) :-
+	(
+		%
+		% check if the goal is a switch on the same
+		% variable (this can happen when converting
+		% nested/chained if-then-elses to switches)
+		%
+		Goal = switch(Var, _CanFail, NestedCases, _SM)
+	->
+		Cases = NestedCases
+	;
+		%
+		% check for the simple case where we can
+		% find a test on the switch var directly
+		%
+		goal_to_conj_list(Goal - GoalInfo, ConjList),
+		map__init(Substitution),
+		find_bind_var_for_switch(ConjList, Substitution, Var,
+				NewConjList, _NewSubstitution, MaybeFunctor),
+		MaybeFunctor = yes(Functor)
+	->
+		conj_list_to_goal(NewConjList, GoalInfo, NewGoal),
+		Cases = [case(Functor, NewGoal)]
+	;
+		fail
+	).
 
 	% find_bind_var_for_switch(Goals0, Subst0, Var, Goals, Subst,
 	%	MaybeFunctor):
@@ -425,6 +539,30 @@
 		MaybeFunctor = no
 	).
 
+	% insert_goal_into_cases_map inserts a case into the cases map
+	%
+:- pred insert_cases_into_cases_map(cases, list(case), cases).
+:- mode insert_cases_into_cases_map(in, in, out) is det.
+
+insert_cases_into_cases_map(CasesMap, [], CasesMap).
+insert_cases_into_cases_map(CasesMap0, [Case|Cases], CasesMap) :-
+	Case = case(Functor, Goal),
+	insert_goal_into_cases_map(CasesMap0, Functor, Goal, CasesMap1),
+	insert_cases_into_cases_map(CasesMap1, Cases, CasesMap).
+
+	% insert_goal_into_cases_map inserts a goal into the cases map
+	%
+:- pred insert_goal_into_cases_map(cases, cons_id, hlds_goal, cases).
+:- mode insert_goal_into_cases_map(in, in, in, out) is det.
+
+insert_goal_into_cases_map(Cases0, Functor, Goal, Cases) :-
+	( map__search(Cases0, Functor, DisjList0) ->
+		DisjList1 = [Goal | DisjList0]
+	;
+		DisjList1 = [Goal]
+	),
+	map__set(Cases0, Functor, DisjList1, Cases).
+
 :- pred cases_to_switch(sorted_case_list, var, map(var, type), hlds_goal_info,
 	store_map, instmap, module_info, hlds_goal_expr).
 :- mode cases_to_switch(in, in, in, in, in, in, in, out) is det.
@@ -450,8 +588,9 @@
 			CanFail = can_fail
 		)
 	),
-	detect_switches_in_cases(CasesList1, InstMap, VarTypes,
-		ModuleInfo, Cases),
+
+	detect_switches_in_cases(CasesList1, InstMap, VarTypes, ModuleInfo,
+		Cases),
 
 	% We turn switches with no arms into fail, since this avoids having
 	% the code generator flush the control variable of the switch.

-- 
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.