[m-rev.] [reuse] diff: move lifo to graph-based approach

[Nancy Mazur]

Hi,


===================================================================


Estimated hours taken: 2
Branches: reuse

Move the lifo selection criterium to be part of the sr_choice_graphing
implementation. The only difference between a lifo approach and a full graph
approach now is that if there are multiple possible reuses in each child of a
conjunction, then you need to pick the first one, instead of the one with the
largest value. 
This change makes the lifo to be a hybrid form between what it used to be, and
the full graph-based approach. The main difference is that after
matching-construction-deconstructions have been identified, we still first
select the one with the best value, instead of picking the first match that was
found. As this can only improve the lifo-heuristic, it is kept this way. 

The next step consists in removing the "random"-selection strategy, and with
it, module "sr_choice". 

compiler/sr_choice.m:
compiler/sr_choice_graphing.m:
compiler/sr_direct.m:


Index: compiler/sr_choice.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_choice.m,v
retrieving revision 1.1.2.26
diff -u -r1.1.2.26 sr_choice.m
--- compiler/sr_choice.m	2 Jun 2004 10:30:52 -0000	1.1.2.26
+++ compiler/sr_choice.m	5 Jul 2004 03:08:33 -0000
@@ -573,6 +573,7 @@
 				Locals ++ list__condense(Globals), Candidates) }
 	;
 		{ Selection = random },
+		% XXX If you ask me, I don't see much randomness around here. 
 		{ P = (pred(Choice::out) is nondet :- 
 			list__member(Choice, PossibleCandidates),
 			ChoiceVar = Choice ^ var,
@@ -637,98 +638,88 @@
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
-:- type cgc_info
-	--->	cgc_info.
-
 :- pred determine_cgc(set(prog_var)::in, hlds_goal::in, hlds_goal::out) is det.
 
-determine_cgc(ReuseVars, Goal0, Goal) :-
-	determine_cgc(ReuseVars, Goal0, Goal, cgc_info, _Info).
-
-:- pred determine_cgc(set(prog_var)::in, hlds_goal::in, hlds_goal::out,
-		cgc_info::in, cgc_info::out) is det.
+determine_cgc(_ReusedVars, Goal - GoalInfo, Goal - GoalInfo) :- 
+	Goal = call(_PredId, _ProcId, _Args, _Builtin, _MaybeCtxt, _Name).
 
-determine_cgc(_ReusedVars, Goal - GoalInfo, Goal - GoalInfo) -->
-	{ Goal = call(_PredId, _ProcId, _Args, _Builtin, _MaybeCtxt, _Name) }.
-
-determine_cgc(ReusedVars, Goal0 - GoalInfo0, Goal - GoalInfo) -->
-	{ Goal0 = unify(Var, Rhs, Mode, Unif0, Ctxt) },
+determine_cgc(ReusedVars, Goal0 - GoalInfo0, Goal - GoalInfo) :-
+	Goal0 = unify(Var, Rhs, Mode, Unif0, Ctxt),
 	determine_cgc_unification(ReusedVars, Unif0, Unif, GoalInfo0, GoalInfo),
-	{ Goal = unify(Var, Rhs, Mode, Unif, Ctxt) }.
+	Goal = unify(Var, Rhs, Mode, Unif, Ctxt).
 
-determine_cgc(_ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) -->
-	{ Goal0 = generic_call(_, _, _, _) },
-	{ Goal = Goal0 }.
-determine_cgc(_ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) -->
-	{ Goal0 = foreign_proc(_, _, _, _, _, _, _) },
-	{ Goal = Goal0 }.
-determine_cgc(_ReusedVars, Goal0 - _GoalInfo, _) -->
-	{ Goal0 = shorthand(_) },
-	{ error("structure_reuse: shorthand.\n") }.
+determine_cgc(_ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :- 
+	Goal0 = generic_call(_, _, _, _),
+	Goal = Goal0.
+determine_cgc(_ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :- 
+	Goal0 = foreign_proc(_, _, _, _, _, _, _),
+	Goal = Goal0.
+determine_cgc(_ReusedVars, Goal0 - _GoalInfo, _) :- 
+	Goal0 = shorthand(_),
+	error("structure_reuse: shorthand.\n").
 
-determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) -->
-	{ Goal0 = if_then_else(Vars, If0, Then0, Else0) },
+determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :- 
+	Goal0 = if_then_else(Vars, If0, Then0, Else0),
 	determine_cgc(ReusedVars, If0, If),
 	determine_cgc(ReusedVars, Then0, Then),
 	determine_cgc(ReusedVars, Else0, Else),
-	{ Goal = if_then_else(Vars, If, Then, Else) }.
+	Goal = if_then_else(Vars, If, Then, Else).
 
-determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) -->
-	{ Goal0 = switch(Var, CanFail, Cases0) },
+determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :-
+	Goal0 = switch(Var, CanFail, Cases0),
 	determine_cgc_cases(ReusedVars, Cases0, Cases),
-	{ Goal = switch(Var, CanFail, Cases) }.
+	Goal = switch(Var, CanFail, Cases).
 
-determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) -->
-	{ Goal0 = some(Vars, CanRemove, SomeGoal0) },
+determine_cgc(ReusedVars, Goal0 - GoalInfo, Goal - GoalInfo) :- 
+	Goal0 = some(Vars, CanRemove, SomeGoal0),
 	determine_cgc(ReusedVars, SomeGoal0, SomeGoal),
-	{ Goal = some(Vars, CanRemove, SomeGoal) }.
+	Goal = some(Vars, CanRemove, SomeGoal).
 
-determine_cgc(ReusedVars, not(Goal0) - GoalInfo, not(Goal) - GoalInfo) -->
+determine_cgc(ReusedVars, not(Goal0) - GoalInfo, not(Goal) - GoalInfo) :- 
 	determine_cgc(ReusedVars, Goal0, Goal).
 
 determine_cgc(ReusedVars, conj(Goal0s) - GoalInfo,
-		conj(Goals) - GoalInfo) -->
+		conj(Goals) - GoalInfo) :- 
 	determine_cgc_list(ReusedVars, Goal0s, Goals).
 
 determine_cgc(ReusedVars, disj(Goal0s) - GoalInfo,
-		disj(Goals) - GoalInfo) -->
+		disj(Goals) - GoalInfo) :- 
 	determine_cgc_list(ReusedVars, Goal0s, Goals).
 
 determine_cgc(ReusedVars, par_conj(Goal0s) - GoalInfo,
-		par_conj(Goals) - GoalInfo) -->
+		par_conj(Goals) - GoalInfo) :- 
 	determine_cgc_list(ReusedVars, Goal0s, Goals).
 
-:- pred determine_cgc_cases(set(prog_var)::in, list(case)::in, list(case)::out,
-		cgc_info::in, cgc_info::out) is det.
+:- pred determine_cgc_cases(set(prog_var)::in, list(case)::in, 
+		list(case)::out) is det.
 
-determine_cgc_cases(_ReusedVars, [], []) --> [].
-determine_cgc_cases(ReusedVars, [Case0 | Case0s], [Case | Cases]) -->
-	{ Case0 = case(ConsId, Goal0) },
+determine_cgc_cases(_ReusedVars, [], []).
+determine_cgc_cases(ReusedVars, [Case0 | Case0s], [Case | Cases]) :- 
+	Case0 = case(ConsId, Goal0),
 	determine_cgc(ReusedVars, Goal0, Goal),
-	{ Case = case(ConsId, Goal) },
+	Case = case(ConsId, Goal),
 	determine_cgc_cases(ReusedVars, Case0s, Cases).
 
-:- pred determine_cgc_list(set(prog_var)::in, hlds_goals::in, hlds_goals::out,
-		cgc_info::in, cgc_info::out) is det.
+:- pred determine_cgc_list(set(prog_var)::in, hlds_goals::in, 
+		hlds_goals::out) is det.
 
-determine_cgc_list(_ReusedVars, [], []) --> [].
-determine_cgc_list(ReusedVars, [Goal0 | Goal0s], [Goal | Goals]) -->
+determine_cgc_list(_ReusedVars, [], []).
+determine_cgc_list(ReusedVars, [Goal0 | Goal0s], [Goal | Goals]) :-
 	determine_cgc(ReusedVars, Goal0, Goal),
 	determine_cgc_list(ReusedVars, Goal0s, Goals).
 
 :- pred determine_cgc_unification(set(prog_var)::in,
 		unification::in, unification::out,
-		hlds_goal_info::in, hlds_goal_info::out,
-		cgc_info::in, cgc_info::out) is det.
+		hlds_goal_info::in, hlds_goal_info::out) is det.
 
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) -->
-	{ Unif = construct(_Var, _ConsId, _Vars, _Ms, _HTC, _IsUniq, _Aditi) }.
+determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :- 
+	Unif = construct(_Var, _ConsId, _Vars, _Ms, _HTC, _IsUniq, _Aditi).
 
-determine_cgc_unification(ReusedVars, Unif0, Unif, GoalInfo0, GoalInfo) -->
-	{ Unif0 = deconstruct(Var, ConsId, Vars, Modes, CanFail, _CanCGC) },
+determine_cgc_unification(ReusedVars, Unif0, Unif, GoalInfo0, GoalInfo) :- 
+	Unif0 = deconstruct(Var, ConsId, Vars, Modes, CanFail, _CanCGC),
 
-	{ goal_info_get_reuse(GoalInfo0, ReuseInfo) },
-	{ ReuseInfo = choice(deconstruct(MaybeDies)) ->
+	goal_info_get_reuse(GoalInfo0, ReuseInfo),
+	( ReuseInfo = choice(deconstruct(MaybeDies)) ->
 		(
 			MaybeDies = yes(Condition),
 			goal_info_set_reuse(
@@ -760,16 +751,16 @@
 		)
 	;
 		error("determine_cgc_unification")
-	},
-	{ Unif = deconstruct(Var, ConsId, Vars, Modes, CanFail, CanCGC) }.
+	),
+	Unif = deconstruct(Var, ConsId, Vars, Modes, CanFail, CanCGC).
 
 
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) -->
-	{ Unif = assign(_, _) }.
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) -->
-	{ Unif = simple_test(_, _) }.
-determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) -->
-	{ Unif = complicated_unify(_, _, _) }.
+determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :- 
+	Unif = assign(_, _).
+determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :- 
+	Unif = simple_test(_, _).
+determine_cgc_unification(_ReusedVars, Unif, Unif, GoalInfo, GoalInfo) :- 
+	Unif = complicated_unify(_, _, _).
 
 
 %-----------------------------------------------------------------------------%
Index: compiler/sr_choice_graphing.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_choice_graphing.m,v
retrieving revision 1.1.2.6
diff -u -r1.1.2.6 sr_choice_graphing.m
--- compiler/sr_choice_graphing.m	2 Jul 2004 05:17:59 -0000	1.1.2.6
+++ compiler/sr_choice_graphing.m	5 Jul 2004 03:08:36 -0000
@@ -116,7 +116,7 @@
 :- import_module io, std_util, list. 
 
 :- type background_info. 
-:- pred set_background_info(sr_choice_util__constraint::in, module_info::in, 
+:- pred set_background_info(sr_choice_util__strategy::in, module_info::in, 
 		vartypes::in, background_info::out) is det.
 
 	% Annotate each deconstruction/construction unification with
@@ -142,13 +142,13 @@
 %-----------------------------------------------------------------------------%
 :- type background_info 
 	---> 	background(
-			constraint	:: sr_choice_util__constraint,
+			strategy	:: sr_choice_util__strategy,
 			module_info	:: module_info, 
 			vartypes	:: vartypes
 		).
 
-set_background_info(Constraint, ModuleInfo, VarTypes, BG):-
-	BG = background(Constraint, ModuleInfo, VarTypes). 
+set_background_info(Strategy, ModuleInfo, VarTypes, BG):-
+	BG = background(Strategy, ModuleInfo, VarTypes). 
 
 %-----------------------------------------------------------------------------%
 
@@ -460,15 +460,33 @@
 		value::in, value::out) is det. 
 
 conjunction_value_of_dead_cel(Background, Deconstruction, 
-		Cont, Val0, Val):- 
+		Cont, !Value) :- 
+	Val0 = !.Value, 
 	list__map(
 		pred(G::in, V::out) is det:- 
 		    ( value_of_dead_cel_in_goal(Background, 
 			Deconstruction, G, Val0, V)), 
 		Cont, DisjunctiveVals), 
 	count_candidates(DisjunctiveVals, Degree), 
-	highest_value_in_list(DisjunctiveVals, Val0, Val1), 
-	Val = Val1 ^ degree := Degree. 
+	(
+		Background ^ strategy ^ selection = lifo,
+		(
+			value_empty(Val0), 
+			list__takewhile(value_empty, DisjunctiveVals, 
+				_EmptyVals, [FirstNonEmpty|_])
+		-> 
+			!:Value= FirstNonEmpty
+		; 
+			!:Value= Val0
+		)
+	; 
+		Background ^ strategy ^ selection = graph, 
+		highest_value_in_list(DisjunctiveVals, !Value)
+	; 
+		Background ^ strategy ^ selection = random, 
+		require__error("(sr_choice_graphing) blabla not supported.")
+	),
+	!:Value = !.Value ^ degree := Degree. 
 
 	% compute the value of a dead cell with respect to a 
 	% disjunction. If reuse is possible within the branches, the value
@@ -662,7 +680,7 @@
 
 compute_new_value(Background, NewVar, DeadVar, NewCons, DeadCons, 
 		NewCellArgs, DeadCellArgs, Weight, ReuseType) :- 
-	Constraint = Background ^ constraint, 
+	Constraint = Background ^ strategy ^ constraint, 
 	ModuleInfo = Background ^ module_info, 
 	Vartypes   = Background ^ vartypes, 
 	NewArity = list__length(NewCellArgs), 
@@ -969,6 +987,8 @@
 :- pred value_init(reuse_condition::in, value::out) is det.
 value_init(Cond, entry(Cond, no, [], 0)). 
 
+:- pred value_empty(value::in) is semidet.
+value_empty(entry(_, no, _, _)).
 
 :- func arity_diff(reuse_type) = int. 
 arity_diff(T) = R :- 
Index: compiler/sr_direct.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_direct.m,v
retrieving revision 1.1.2.22
diff -u -r1.1.2.22 sr_direct.m
--- compiler/sr_direct.m	30 Jun 2004 04:46:47 -0000	1.1.2.22
+++ compiler/sr_direct.m	5 Jul 2004 03:08:36 -0000
@@ -96,11 +96,11 @@
 	% arguments given to the mmc were correct. This is definitely not the
 	% right moment to check these arguments. Should be done way earlier. 
 	sr_choice_util__get_strategy(Strategy, !ModuleInfo, !IO), 
-	Strategy = strategy(Constraint, Selection),
+	Strategy = strategy(_Constraint, Selection),
 	(
-		Selection = graph 
+		( Selection = graph ; Selection = lifo )
 	->
-		sr_choice_graphing__set_background_info(Constraint, 
+		sr_choice_graphing__set_background_info(Strategy, 
 			!.ModuleInfo, VarTypes, Background), 
 		sr_choice_graphing__process_goal(Background, Goal1, Goal,
 			MaybeReuseConditions, !IO)


-- 
nancy.mazur at cs.kuleuven.ac.be ------------ Katholieke Universiteit Leuven -
tel: +32-16-327596 - fax: +32-16-327996 ------- Dept. of Computer Science -
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------