[m-dev.] for review: --delay-constructs

[Zoltan Somogyi]

On 09-Mar-2001, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> Actually, I think I will simply tighten the optimization to move only 
> construction unifications that construct ground terms.

Here is the interdiff of that change. Unless I hear an objection, I will commit
this tomorrow.

Zoltan.

--- delay_construct.m
+++ delay_construct.m
@@ -12,5 +12,5 @@
-% It looks for construction unification followed by primitive goals,
-% at least one of which can fail, and none of which take the variable
-% representing the cell as their input. Such code sequences cause the
-% cell to be constructed even if the following goal would fail, which is
-% wasteful. This module therefore reorders the sequence, moving the
+% It looks for a unification that constructs a ground term followed by
+% primitive goals, at least one of which can fail, and none of which take
+% the variable representing the cell as their input. Such code sequences
+% cause the cell to be constructed even if the following goal would fail,
+% which is wasteful. This module therefore reorders the sequence, moving the
@@ -40,0 +41 @@
+:- import_module instmap, inst_match.
@@ -50 +51 @@
-	{ delay_construct_proc_no_io(ProcInfo0, PredInfo, Globals,
+	{ delay_construct_proc_no_io(ProcInfo0, PredInfo, ModuleInfo, Globals,
@@ -53,2 +54,2 @@
-:- pred delay_construct_proc_no_io(proc_info::in, pred_info::in, globals::in,
-	proc_info::out) is det.
+:- pred delay_construct_proc_no_io(proc_info::in, pred_info::in,
+	module_info::in, globals::in, proc_info::out) is det.
@@ -56 +57,2 @@
-delay_construct_proc_no_io(ProcInfo0, PredInfo, Globals, ProcInfo) :-
+delay_construct_proc_no_io(ProcInfo0, PredInfo, ModuleInfo, Globals, ProcInfo)
+		:-
@@ -61 +63,2 @@
-	DelayInfo = delay_construct_info(BodyTypeinfoLiveness,
+	proc_info_get_initial_instmap(ProcInfo0, ModuleInfo, InstMap0),
+	DelayInfo = delay_construct_info(ModuleInfo, BodyTypeinfoLiveness,
@@ -64 +67 @@
-	delay_construct_in_goal(Goal0, DelayInfo, Goal),
+	delay_construct_in_goal(Goal0, InstMap0, DelayInfo, Goal),
@@ -68,0 +72 @@
+			module_info		:: module_info,
@@ -76,2 +80,2 @@
-:- pred delay_construct_in_goal(hlds_goal::in, delay_construct_info::in,
-	hlds_goal::out) is det.
+:- pred delay_construct_in_goal(hlds_goal::in, instmap::in,
+	delay_construct_info::in, hlds_goal::out) is det.
@@ -79 +83 @@
-delay_construct_in_goal(GoalExpr0 - GoalInfo0, DelayInfo, Goal) :-
+delay_construct_in_goal(GoalExpr0 - GoalInfo0, InstMap0, DelayInfo, Goal) :-
@@ -83,3 +87,24 @@
-		( determinism_components(Detism, can_fail, _) ->
-			delay_construct_in_conj(Goals0, DelayInfo,
-				set__init, [], Goals)
+		determinism_components(Detism, CanFail, MaxSoln),
+		(
+			% If the conjunction cannot fail, then its conjuncts
+			% cannot fail either, so we have no hope of pushing a
+			% construction past a failing goal.
+			%
+			% If the conjuntion contains goals that can succeed
+			% more than once, which is possible if MaxSoln is
+			% at_most_many or at_most_many_cc, then moving a
+			% construction to the right may increase the number of
+			% times the construction is executed. We are therefore
+			% careful to make sure delay_construct_in_conj doesn't
+			% move constructions across goals that succeed more
+			% than once.
+			%
+			% If the conjunction cannot succeed, i.e. MaxSoln is
+			% at_most_zero, there is no point in trying to speed it
+			% up.
+
+			CanFail = can_fail,
+			MaxSoln \= at_most_zero
+		->
+			delay_construct_in_conj(Goals0, InstMap0, DelayInfo,
+				set__init, [], Goals1)
@@ -87 +112 @@
-			delay_construct_in_goals(Goals0, DelayInfo, Goals)
+			Goals1 = Goals0
@@ -89 +114,2 @@
-		conj_list_to_goal(Goals, GoalInfo0, Goal)
+		delay_construct_in_goals(Goals1, InstMap0, DelayInfo, Goals),
+		Goal = conj(Goals) - GoalInfo0
@@ -92 +118 @@
-		delay_construct_in_goals(Goals0, DelayInfo, Goals),
+		delay_construct_in_goals(Goals0, InstMap0, DelayInfo, Goals),
@@ -96 +122 @@
-		delay_construct_in_goals(Goals0, DelayInfo, Goals),
+		delay_construct_in_goals(Goals0, InstMap0, DelayInfo, Goals),
@@ -100 +126 @@
-		delay_construct_in_goal(NegGoal0, DelayInfo, NegGoal),
+		delay_construct_in_goal(NegGoal0, InstMap0, DelayInfo, NegGoal),
@@ -104 +130 @@
-		delay_construct_in_cases(Cases0, DelayInfo, Cases),
+		delay_construct_in_cases(Cases0, InstMap0, DelayInfo, Cases),
@@ -108,3 +134,7 @@
-		delay_construct_in_goal(Cond0, DelayInfo, Cond),
-		delay_construct_in_goal(Then0, DelayInfo, Then),
-		delay_construct_in_goal(Else0, DelayInfo, Else),
+		Cond0 = _ - CondInfo0,
+		goal_info_get_instmap_delta(CondInfo0, CondInstMapDelta),
+		instmap__apply_instmap_delta(InstMap0, CondInstMapDelta,
+			InstMapThen),
+		delay_construct_in_goal(Cond0, InstMap0, DelayInfo, Cond),
+		delay_construct_in_goal(Then0, InstMapThen, DelayInfo, Then),
+		delay_construct_in_goal(Else0, InstMap0, DelayInfo, Else),
@@ -114 +144 @@
-		delay_construct_in_goal(SubGoal0, DelayInfo, SubGoal),
+		delay_construct_in_goal(SubGoal0, InstMap0, DelayInfo, SubGoal),
@@ -126 +156 @@
-		GoalExpr0 = pragma_foreign_code(_, _, _, _, _, _, _),
+		GoalExpr0 = foreign_proc(_, _, _, _, _, _, _),
@@ -129 +159 @@
-		GoalExpr0 = bi_implication(_, _),
+		GoalExpr0 = shorthand(_),
@@ -131 +161 @@
-		error("delay_construct_in_goal: unexpected bi_implication")
+		error("delay_construct_in_goal: unexpected shorthand")
@@ -136,2 +166,2 @@
-% We maintain a list of delayed construction unifications, and the set of
-% variables they define.
+% We maintain a list of delayed construction unifications that construct ground
+% terms, and the set of variables they define.
@@ -155,0 +186,4 @@
+%
+% The instmap we pass around is the one that we construct from the original
+% conjunction order. At each point, it reflects the bindings made by the
+% conjuncts so far *plus* the bindings made by the delayed goals.
@@ -157,2 +191,3 @@
-:- pred delay_construct_in_conj(list(hlds_goal)::in, delay_construct_info::in,
-	set(prog_var)::in, list(hlds_goal)::in, list(hlds_goal)::out) is det.
+:- pred delay_construct_in_conj(list(hlds_goal)::in, instmap::in,
+	delay_construct_info::in, set(prog_var)::in, list(hlds_goal)::in,
+	list(hlds_goal)::out) is det.
@@ -160 +195 @@
-delay_construct_in_conj([], _, _, RevDelayedGoals, DelayedGoals) :-
+delay_construct_in_conj([], _, _, _, RevDelayedGoals, DelayedGoals) :-
@@ -162 +197 @@
-delay_construct_in_conj([Goal0 | Goals0], DelayInfo,
+delay_construct_in_conj([Goal0 | Goals0], InstMap0, DelayInfo,
@@ -163,0 +199,3 @@
+	Goal0 = GoalExpr0 - GoalInfo0,
+	goal_info_get_instmap_delta(GoalInfo0, InstMapDelta0),
+	instmap__apply_instmap_delta(InstMap0, InstMapDelta0, InstMap1),
@@ -165 +203 @@
-		Goal0 = unify(_, _, _, Unif, _) - _,
+		GoalExpr0 = unify(_, _, _, Unif, _),
@@ -167 +205,5 @@
-		Args = [_ | _]	% We are constructing a cell, not a constant
+		Args = [_ | _],	% We are constructing a cell, not a constant
+		instmap__lookup_var(InstMap0, Var, Inst0),
+		inst_is_free(DelayInfo ^ module_info, Inst0),
+		instmap__lookup_var(InstMap1, Var, Inst1),
+		inst_is_ground(DelayInfo ^ module_info, Inst1)
@@ -171 +213 @@
-		delay_construct_in_conj(Goals0, DelayInfo,
+		delay_construct_in_conj(Goals0, InstMap1, DelayInfo,
@@ -175 +217 @@
-		delay_construct_skippable_expr(GoalExpr0),
+		delay_construct_skippable(GoalExpr0, GoalInfo0),
@@ -187,2 +229,2 @@
-		delay_construct_in_conj(Goals0, DelayInfo, ConstructedVars0,
-			RevDelayedGoals0, Goals1),
+		delay_construct_in_conj(Goals0, InstMap1, DelayInfo,
+			ConstructedVars0, RevDelayedGoals0, Goals1),
@@ -192,2 +234,2 @@
-		delay_construct_in_conj(Goals0, DelayInfo, set__init, [],
-			Goals1),
+		delay_construct_in_conj(Goals0, InstMap1, DelayInfo,
+			set__init, [], Goals1),
@@ -197 +239,2 @@
-:- pred delay_construct_skippable_expr(hlds_goal_expr::in) is semidet.
+:- pred delay_construct_skippable(hlds_goal_expr::in, hlds_goal_info::in)
+	is semidet.
@@ -199 +242 @@
-delay_construct_skippable_expr(GoalExpr) :-
+delay_construct_skippable(GoalExpr, GoalInfo) :-
@@ -204 +247,4 @@
-	).
+	),
+	goal_info_get_determinism(GoalInfo, Detism),
+	determinism_components(Detism, _CanFail, MaxSoln),
+	MaxSoln \= at_most_many.
@@ -208,2 +254,2 @@
-:- pred delay_construct_in_goals(list(hlds_goal)::in, delay_construct_info::in,
-	list(hlds_goal)::out) is det.
+:- pred delay_construct_in_goals(list(hlds_goal)::in, instmap::in,
+	delay_construct_info::in, list(hlds_goal)::out) is det.
@@ -211,4 +257,5 @@
-delay_construct_in_goals([], _, []).
-delay_construct_in_goals([Goal0 | Goals0], DelayInfo, [Goal | Goals]) :-
-	delay_construct_in_goal(Goal0, DelayInfo, Goal),
-	delay_construct_in_goals(Goals0, DelayInfo, Goals).
+delay_construct_in_goals([], _, _, []).
+delay_construct_in_goals([Goal0 | Goals0], InstMap0, DelayInfo,
+		[Goal | Goals]) :-
+	delay_construct_in_goal(Goal0, InstMap0, DelayInfo, Goal),
+	delay_construct_in_goals(Goals0, InstMap0, DelayInfo, Goals).
@@ -216,2 +263,2 @@
-:- pred delay_construct_in_cases(list(case)::in, delay_construct_info::in,
-	list(case)::out) is det.
+:- pred delay_construct_in_cases(list(case)::in, instmap::in,
+	delay_construct_info::in, list(case)::out) is det.
@@ -219,2 +266,2 @@
-delay_construct_in_cases([], _, []).
-delay_construct_in_cases([case(Cons, Goal0) | Cases0], DelayInfo,
+delay_construct_in_cases([], _, _, []).
+delay_construct_in_cases([case(Cons, Goal0) | Cases0], InstMap0, DelayInfo,
@@ -222,2 +269,2 @@
-	delay_construct_in_goal(Goal0, DelayInfo, Goal),
-	delay_construct_in_cases(Cases0, DelayInfo, Cases).
+	delay_construct_in_goal(Goal0, InstMap0, DelayInfo, Goal),
+	delay_construct_in_cases(Cases0, InstMap0, DelayInfo, Cases).
--- compiler/options.m
+++ compiler/options.m
@@ -1519 +1518,0 @@
-	delay_construct		-	bool(yes),
@@ -1538,0 +1538 @@
+	delay_construct		-	bool(yes),
@@ -2435,3 +2434,0 @@
-		"--delay-constructs",
-		"\tReorder goals to move construction unifications after",
-		"\tprimitive goals that can fail.",
@@ -2446,0 +2444,3 @@
+		"--delay-constructs",
+		"\tReorder goals to move construction unifications after",
+		"\tprimitive goals that can fail.",
--- doc/user_guide.texi
+++ doc/user_guide.texi
@@ -4130,5 +4129,0 @@
- at item --delay-constructs
-Reorder goals to move construction unifications after
-primitive goals that can fail.
-
- at sp 1
@@ -4145,0 +4141,5 @@
+
+ at sp 1
+ at item --delay-constructs
+Reorder goals to move construction unifications after
+primitive goals that can fail.
--- compiler/notes/compiler_design.html	2001/01/19 01:50:32	1.57
+++ compiler/notes/compiler_design.html	2001/04/23 05:05:08
@@ -581,6 +581,10 @@
 <li> issue warnings about unused arguments from predicates, and create
   specialized versions without them (unused_args.m); type_infos are
   often unused.
+
+<li> delay_construct.m pushes construction unifications to the right in
+  semidet conjunctions, in an effort to reduce the probability that it will
+  need to be executed.
 
 <li> unneeded_code.m looks for goals whose results are either not needed
   at all, or needed in some branches of computation but not others. Provided
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------