for review: cache references to free(alias) variables in the code generator

David Matthew Overton dmo at cs.mu.OZ.AU
Thu Aug 13 13:14:55 AEST 1998


Zoltan,

Could you please review this?


-David

Estimated hours taken: 10

Implement caching of references to free variables in the code generator.
E.g. after unification 

	Y = f(X)

if Y is live, we don't need to keep a reference to X, we just need
to remember that the X is located in the first field of Y.

Note: this is not a complete solution to minimising the number of
references because references will still be evaluated and saved in
stack slots e.g. across calls and at branch ends.  A better approach
will probably be to re-order constructions and deconstructions in
saved_vars.m and to allow partial deconstructions when only some of the
fields are needed.

compiler/code_exprn.m:
	Extend the var_info data type to allow references to be cached
	as a particular field of a variable.  Add predicates for
	caching and uncaching references.

compiler/code_info.m:
	Add an extra argument to `code_info__post_goal_update' which
	returns code to uncache all references when the reference
	refers to a field in the PostDeaths set for the goal.
	Also return this extra code from `code_info__call_simple_neg'
	which calls `code_info__post_goal_update'.

compiler/code_gen.m:
compiler/middle_rec.m:
	Add an extra argument to the call to `code_info__post_goal_update'.

compiler/hlds_pred.m:
	Fix errors in a couple of comments.

compiler/ite_gen.m:
	Add an extra argument to the call to `code_info__leave_simple_neg'.

compiler/tree.m:
	Add a new higher order polymorphic predicate `tree__construct' which
	is somewhat analogous to `list__map_foldl'.

compiler/unify_gen.m:
	In `unify_gen___aliased_vars_set_location', cache references
	to free(alias) vars in constructions instead of producing code
	to evaluate them.

Index: code_exprn.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/code_exprn.m,v
retrieving revision 1.51.4.6
diff -u -r1.51.4.6 code_exprn.m
--- 1.51.4.6	1998/06/29 06:23:19
+++ code_exprn.m	1998/08/12 05:49:24
@@ -120,6 +120,17 @@
 :- pred code_exprn__cache_exprn(var, rval, exprn_info, exprn_info).
 :- mode code_exprn__cache_exprn(in, in, in, out) is det.
 
+%       code_exprn__cache_reference(Var, Lvar, Tag, FieldNum,
+%		       ExprnInfo0, ExprnInfo)
+%	       Produces a modified ExprnInfo0, ExprnInfo which
+%	       indicates that when a reference to Var is needed, it can
+%	       be found by obtaining the address of field FieldNum of
+%	       variable Lvar using tag Tag.
+
+:- pred code_exprn__cache_reference(var, var, tag, int,
+		exprn_info, exprn_info).
+:- mode code_exprn__cache_reference(in, in, in, in, in, out) is det.
+
 %	code_exprn__place_var(Var, Lval, Code, ExprnInfo0, ExprnInfo)
 %		Produces Code and a modified version of ExprnInfo0,
 %		ExprnInfo which places the value of Var in Lval.
@@ -140,10 +151,19 @@
 % 		If the Var has a set of reference locations associated with
 %		it, place it in these locations and remove them from the
 %		locations set.
+
 :- pred code_exprn__place_var_in_references(var, code_tree,
 		exprn_info, exprn_info).
 :- mode code_exprn__place_var_in_references(in, out, in, out) is det.
 
+	% code_exprn__uncache_references(Vars, Code, ExprnInfo0, ExprnInfo)
+	%       Output Code to produce references to any variables that 
+	%       are cached as references to fields of variables in Vars.
+	%       Update the references in the ExprnInfo to show that
+	%       these references have been evaluated.
+:- pred code_exprn__uncache_references(set(var), code_tree,
+		exprn_info, exprn_info).
+:- mode code_exprn__uncache_references(in, out, in, out) is det.
 
 %	code_exprn__place_var_reference(Var, Lval, Code, ExprnInfo0, ExprnInfo)
 %		Produces code to place the reference to Var's location
@@ -287,10 +307,10 @@
 :- import_module code_util, exprn_aux, tree.
 :- import_module bool, bag, require, int, term, string, std_util.
 
-:- type var_stat	--->	evaled(set(rval))
-			;	cached(rval)
-			;	none
-			.
+:- type var_stat
+	--->	evaled(set(rval))
+	;	cached(rval)
+	;	none.
 
 
 %	var_info stores information about the current status of a variable
@@ -303,10 +323,19 @@
 					% Current status of variable value.
 			).
 
-% Locations where the value needs to be placed.  Each lval in a
-% set(lval) should point to the same place.  The bool is yes if the
-% value is already in this location, otherwise it is no.
-:- type var_refs == set(pair(bool, set(lval))).
+% 	Locations where the value needs to be placed.  Each lval in a
+% 	set(lval) should point to the same place.  The bool is yes if the
+% 	value is already in this location, otherwise it is no.
+:- type var_refs == set(pair(bool, var_ref_stat)).
+
+:- type var_ref_stat
+	--->	evaled(set(lval))
+	;	cached(
+			var,	% Var where this reference occurs.
+			tag,	% Tag to use for dereferencing Var.
+			int	% Field number of reference.
+		).
+	%;	list(set(rval)).	% AAA  A linked list of references.
 
 :- type var_map	==	map(var, var_info).
 
@@ -377,10 +406,10 @@
 	; VVal = reference(Lval),
 		set__singleton_set(Lvals, Lval),
 		( map__search(Vars0, V, var_info(Locs0, Stat)) ->
-			set__insert(Locs0, no - Lvals, Locs),
+			set__insert(Locs0, no - evaled(Lvals), Locs),
 			map__det_update(Vars0, V, var_info(Locs, Stat), Vars1)
 		;
-			set__singleton_set(Locs, no - Lvals),
+			set__singleton_set(Locs, no - evaled(Lvals)),
 			map__det_insert(Vars0, V, var_info(Locs, none),
 				Vars1)
 		),
@@ -479,7 +508,7 @@
 	),
 	code_exprn__filter_out_reg_depending_refs(Refs0, OldVars, Refs),
 	(
-		set__member(_ - Ref, Refs),
+		set__member(_ - evaled(Ref), Refs),
 		set__empty(Ref),
 		list__member(V, Critical)
 	->
@@ -592,14 +621,15 @@
 code_exprn__filter_out_reg_depending_refs(Refs0, Vars, Refs) :-
 	set__to_sorted_list(Refs0, RefList0),
 	list__map(lambda([Ref0::in, Ref::out] is det,
-		(
-			Ref0 = Placed - Lvals0,
+		( Ref0 = Placed - evaled(Lvals0),
 			set__to_sorted_list(Lvals0, LvalList0),
 			list__filter(lambda([Lval::in] is semidet,
 				\+ code_exprn__lval_depends_on_reg(Lval, Vars)),
 				LvalList0, LvalList),
 			set__list_to_set(LvalList, Lvals),
-			Ref = Placed - Lvals
+			Ref = Placed - evaled(Lvals)
+		; Ref0 = _ - cached(_, _, _),
+			Ref = Ref0
 		)), RefList0, RefList),
 	set__list_to_set(RefList, Refs).
 
@@ -635,10 +665,10 @@
 	{ set__singleton_set(Lvals, Lval) },
 	{ map__search(Vars0, Var, var_info(Refs0, Stat0)) ->
 		Stat = Stat0,
-		set__insert(Refs0, no - Lvals, Refs)
+		set__insert(Refs0, no - evaled(Lvals), Refs)
 	;
 		Stat = none,
-		set__singleton_set(Refs, no - Lvals)
+		set__singleton_set(Refs, no - evaled(Lvals))
 	},
 	{ map__set(Vars0, Var, var_info(Refs, Stat), Vars) },
 	code_exprn__set_vars(Vars).
@@ -669,7 +699,7 @@
 		set__member(Rval, Rvals),
 		exprn_aux__rval_contains_lval(Rval, Lval)
 	;
-		set__member(_Placed - Lvals, Refs),
+		set__member(_Placed - evaled(Lvals), Refs),
 		set__member(Lval0, Lvals),
 		exprn_aux__lval_contains_lval(Lval0, Lval)
 	).
@@ -1004,6 +1034,13 @@
 		error("code_exprn__select_rval: cosmic rays strike again")
 	).
 
+:- pred code_exprn__select_rval_from_set(set(rval), rval).
+:- mode code_exprn__select_rval_from_set(in, out) is det.
+
+code_exprn__select_rval_from_set(RvalSet, Rval) :-
+	set__to_sorted_list(RvalSet, RvalList),
+	code_exprn__select_rval(RvalList, Rval).
+
 :- pred code_exprn__select_reg(list(rval), rval).
 :- mode code_exprn__select_reg(in, out) is semidet.
 
@@ -1163,15 +1200,28 @@
 		code_exprn__set_vars(Vars)
 	).
 
+code_exprn__cache_reference(Var, LHSVar, Tag, FieldNum) -->
+	code_exprn__get_vars(Vars0),
+	{ RefStat = no - cached(LHSVar, Tag, FieldNum) },
+	{ map__search(Vars0, Var, var_info(Locs0, Stat0)) ->
+		Stat = Stat0,
+		set__insert(Locs0, RefStat, Locs)
+	;
+		Stat = none,
+		set__singleton_set(Locs, RefStat)
+	},
+	{ map__set(Vars0, Var, var_info(Locs, Stat), Vars) },
+	code_exprn__set_vars(Vars).
+
 %------------------------------------------------------------------------------%
 
 code_exprn__place_vars([], empty) --> [].
-code_exprn__place_vars([Var - store_info(ValOrRef, Lval) | StoreMap], Code) -->
+code_exprn__place_vars([Var - StoreInfo | StoreMap], Code) -->
 	(
-		{ ValOrRef = val },
+		{ StoreInfo = store_info(val, Lval) },
 		code_exprn__place_var(Var, Lval, FirstCode)
 	;
-		{ ValOrRef = ref },
+		{ StoreInfo = store_info(ref, Lval) },
 		code_exprn__place_var_reference(Var, Lval, FirstCode)
 	),
 	code_exprn__place_vars(StoreMap, RestCode),
@@ -1247,9 +1297,12 @@
 	set__to_sorted_list(Refs0, RefsList0),
 	Filter = lambda([X::in] is semidet,
 		( 
-			X = _ - Lvals1,
-			set__member(L, Lvals0),
-			set__member(L, Lvals1)
+			X = _ - RefStat,
+			( RefStat = evaled(Lvals1),
+				set__member(L, Lvals0),
+				set__member(L, Lvals1)
+			; RefStat = cached(_, _, _)
+			)
 		)),
 	list__filter(Filter, RefsList0, RefsList),
 	set__sorted_list_to_set(RefsList, Refs).
@@ -1259,24 +1312,39 @@
 	{ map__lookup(Vars0, Var, var_info(Refs0, Stat)) },
 
 	% Remove an lval from the set and recursively call place_var.
-	( { get_next_ref_to_place(Refs0, Lvals, Refs1) } ->
-		{ code_exprn__remove_lval_references(Refs1, Lvals, Refs2) },
-		{ set__insert(Refs2, yes - Lvals, Refs) },
-		{ map__det_update(Vars0, Var, var_info(Refs, Stat), Vars) },
+	( { get_next_ref_to_place(Refs0, RefStat, Refs1) } ->
+		( { RefStat = evaled(Lvals) },
+			{ code_exprn__remove_lval_references(Refs1, Lvals,
+				Refs2) },
+			{ code_exprn__select_lval(Lvals, Lval) },
+			{ Location = mem_ref(lval(Lval)) },
+			{ Code0 = empty }
+		; { RefStat = cached(LVar, Tag, FieldNum) },
+			% There is no need to evaluate the ref, so leave it
+			% cached and place the value of Var directly into
+			% the cached location.
+			code_exprn__produce_var(LVar, Rval, Code0),
+			{ Location = field(yes(Tag), Rval,
+				const(int_const(FieldNum))) },
+			{ Refs2 = Refs1 }
+		),
+		code_exprn__get_vars(Vars1),
+		{ set__insert(Refs2, yes - RefStat, Refs) },
+		{ map__det_update(Vars1, Var, var_info(Refs, Stat), Vars) },
 		code_exprn__set_vars(Vars),
-		{ code_exprn__select_lval(Lvals, Lval) },
-		code_exprn__place_var(Var, mem_ref(lval(Lval)), Code)
+		code_exprn__place_var(Var, Location, Code1),
+		{ Code = tree(Code0, Code1) }
 	;
 		{ Code = empty }
 	).
 
-:- pred get_next_ref_to_place(var_refs, set(lval), var_refs).
+:- pred get_next_ref_to_place(var_refs, var_ref_stat, var_refs).
 :- mode get_next_ref_to_place(in, out, out) is semidet.
 
-get_next_ref_to_place(Refs0, Lvals, Refs) :-
+get_next_ref_to_place(Refs0, RefStat, Refs) :-
 	set__to_sorted_list(Refs0, RefList0),
 	list__takewhile(lambda([X::in] is semidet, X = yes - _),
-		RefList0, RefList1, [no - Lvals | RefList2]),
+		RefList0, RefList1, [no - RefStat | RefList2]),
 	list__append(RefList1, RefList2, RefList),
 	set__sorted_list_to_set(RefList, Refs).
 		
@@ -1400,7 +1468,24 @@
 		{ Lval = Lval0 },
 		% move stuff out of the way, and heed any changes
 		% this produces in the form of the expression
-		code_exprn__clear_lval(Lval, Rval1, Rval2, ClearCode)
+		code_exprn__clear_lval(Lval, Rval1, Rval2a, ClearCode0),
+
+		% If we've got a mem_ref Lval and a create Rval that has
+		% fields that need to be filled in, then place exprn in
+		% a register as well as Lval to avoid repeated pointer
+		% dereferences.
+		(
+			{ Lval = mem_ref(_) },
+			{ Rval2a = create(_, [_|_], _, _, _) }
+		->
+			code_exprn__place_exprn(no, MaybeVar, Rval2a,
+				StandAlone, IsConst, Lval1, RefCode),
+			{ Rval2 = lval(Lval1) },
+			{ ClearCode = tree(ClearCode0, RefCode) }
+		;
+			{ Rval2 = Rval2a },
+			{ ClearCode = ClearCode0 }
+		)
 	;
 		code_exprn__get_spare_reg(r, Lval),
 		{ Rval2 = Rval1 },
@@ -1469,26 +1554,69 @@
 
 %------------------------------------------------------------------------------%
 
+code_exprn__uncache_references(Lvars, Code) -->
+	code_exprn__get_vars(VarMap0),
+	{ map__keys(VarMap0, Vars) },
+	{ set__to_sorted_list(Lvars, LvarsList) },
+	tree__construct(code_exprn__uncache_references_2(LvarsList),
+		Vars, Code).
+
+:- pred code_exprn__uncache_references_2(list(var), var, code_tree,
+		exprn_info, exprn_info).
+:- mode code_exprn__uncache_references_2(in, in, out, in, out) is det.
+
+code_exprn__uncache_references_2(Lvars, Var, Code) -->
+	tree__construct(code_exprn__uncache_reference(Var), Lvars, Code).
+
+%------------------------------------------------------------------------------%
+
 code_exprn__place_var_reference(Var, Lval, Code) -->
 	code_exprn__get_vars(Vars0),
-	(
-		{ map__search(Vars0, Var, var_info(Refs0, Stat)) },
-
-		% XXX for now we only allow one reference per variable.
-		{ set__singleton_set(Refs0, Placed - Lvals0) }
-	->
-		( { set__member(Lval, Lvals0) } ->
-			{ Code = empty }
-		; 
-			{ code_exprn__select_lval(Lvals0, SelectedLval) },
-			code_exprn__place_exprn(yes(Lval), no,
+	( { map__search(Vars0, Var, var_info(Refs0, Stat)) } ->
+		(
+		    % XXX for now we only allow one reference per variable.
+		    { set__singleton_set(Refs0, Placed - RefStat0) }
+		->
+		    ( { RefStat0 = evaled(Lvals0) },
+			( { set__member(Lval, Lvals0) } ->
+			    { Code = empty },
+			    { Lvals = Lvals0 }
+			; 
+			    { code_exprn__select_lval(Lvals0, SelectedLval) },
+			    code_exprn__place_exprn(yes(Lval), no,
 				lval(SelectedLval), no, no, _Lval, Code),
-			code_exprn__get_vars(Vars1),
-			{ set__insert(Lvals0, Lval, Lvals) },
-			{ set__delete(Refs0, Placed - Lvals0, Refs1) },
-			{ set__insert(Refs1, Placed - Lvals, Refs) },
-			{ map__set(Vars1, Var, var_info(Refs, Stat), Vars) },
-			code_exprn__set_vars(Vars)
+			    { set__insert(Lvals0, Lval, Lvals) }
+			)
+		    ; { RefStat0 = cached(LHSVar, Tag, FieldNum) },
+			code_exprn__uncache_reference_in_lval(LHSVar,
+				Tag, FieldNum, Lval, Code),
+			{ set__singleton_set(Lvals, Lval) }
+		/* AAA
+		    ; { RefStat0 = list(Rvals0) },
+			( { set__member(lval(Lval), Rvals0) } ->
+			    { Code = empty },
+			    { Rvals = Rvals0 }
+			;
+			    { code_exprn__select_rval_from_set(Rvals0, Rval) },
+			    code_exprn__place_exprn(yes(Lval), no, Rval,
+			    	no, no, _Lval, Code),
+			    { set__insert(Rvals0, lval(Lval), Rvals) }
+			)
+		*/
+		    ),
+		    { set__delete(Refs0, Placed - RefStat0, Refs1) },
+		    { set__insert(Refs1, Placed - evaled(Lvals), Refs)},
+		    code_exprn__get_vars(Vars1),
+		    { map__det_update(Vars1, Var, var_info(Refs, Stat), Vars)},
+		    code_exprn__set_vars(Vars)
+		;
+		    code_exprn__get_var_name(Var, Name),
+		    { term__var_to_int(Var, Num) },
+		    { string__int_to_string(Num, NumStr) },
+		    { string__append_list([
+			"code_exprn__place_var_reference: variable ",
+			Name, " (", NumStr, ") has >1 references"], Msg) },
+		    { error(Msg) }
 		)
 	;
 		code_exprn__get_var_name(Var, Name),
@@ -1496,7 +1624,7 @@
 		{ string__int_to_string(Num, NumStr) },
 		{ string__append_list([
 			"code_exprn__place_var_reference: variable ",
-			Name, " (", NumStr, ") has 0 or >1 references"], Msg) },
+			Name, " (", NumStr, ") has 0 references"], Msg) },
 		{ error(Msg) }
 	).
 
@@ -1672,6 +1800,65 @@
 
 %------------------------------------------------------------------------------%
 
+:- pred code_exprn__uncache_reference(var, var, code_tree,
+		exprn_info, exprn_info).
+:- mode code_exprn__uncache_reference(in, in, out, in, out) is det.
+
+code_exprn__uncache_reference(Var, Lvar, Code) -->
+	code_exprn__get_vars(VarMap0),
+	{ map__lookup(VarMap0, Var, var_info(Refs0, Stat)) },
+
+	% Removed the cached references from the var_info.
+	{ set__to_sorted_list(Refs0, RefsList0) },
+	{ list__filter(lambda([RefStat::in] is semidet, 
+		RefStat = _ - cached(Lvar, _, _)), RefsList0, CachedRefs,
+		RefsList1) },
+	{ set__sorted_list_to_set(RefsList1, Refs1) },
+	{ map__det_update(VarMap0, Var, var_info(Refs1, Stat), Vars1) },
+	code_exprn__set_vars(Vars1),
+
+	tree__construct(code_exprn__uncache_reference_2(Lvar, Var), CachedRefs,
+		Code).
+
+:- pred code_exprn__uncache_reference_2(var, var, pair(bool, var_ref_stat),
+		code_tree, exprn_info, exprn_info).
+:- mode code_exprn__uncache_reference_2(in, in, in, out, in, out) is det.
+
+code_exprn__uncache_reference_2(Lvar, Var, Placed - RefStat0, Code) -->
+	( { RefStat0 = cached(Lvar, Tag, FieldNum) } ->
+		code_exprn__select_preferred_reg(Var, PrefLval),
+		( { PrefLval = reg(PrefRegType, PrefRegNum) } ->
+			code_exprn__acquire_reg_prefer_given(PrefRegType,
+				PrefRegNum, Lval)
+		;
+			{ Lval = PrefLval }
+		),
+		code_exprn__get_vars(Vars0),
+		{ map__lookup(Vars0, Var, var_info(Refs0, Stat)) },
+		{ set__singleton_set(Lvals, Lval) },
+		{ set__insert(Refs0, Placed - evaled(Lvals), Refs) },
+		{ map__det_update(Vars0, Var, var_info(Refs, Stat), Vars) },
+		code_exprn__set_vars(Vars),
+		code_exprn__uncache_reference_in_lval(Lvar, Tag, FieldNum, Lval,
+			Code)
+	;
+		{ error("code_exprn__uncache_reference_2: oops") }
+	).
+
+:- pred code_exprn__uncache_reference_in_lval(var, tag, int, lval,
+		code_tree, exprn_info, exprn_info).
+:- mode code_exprn__uncache_reference_in_lval(in, in, in, in, out, in, out)
+		is det.
+
+code_exprn__uncache_reference_in_lval(Lvar, Tag, FieldNum, Lval, Code) -->
+	code_exprn__produce_var(Lvar, Rval, Code0),
+	{ Code1 = node([assign(Lval,
+		mem_addr(heap_ref(Rval, Tag, FieldNum))) -
+		"place reference"]) },
+	{ Code = tree(Code0, Code1) }.
+
+%------------------------------------------------------------------------------%
+
 code_exprn__produce_var_in_reg(Var, Rval, Code) -->
 	code_exprn__get_var_status(Var, Stat),
 	(
@@ -1705,28 +1892,23 @@
 code_exprn__produce_ref_in_reg_or_stack(Var, Lval, Code) -->
 	code_exprn__get_vars(Vars0),
 	(
-		{ map__search(Vars0, Var, var_info(RefLocs0, Stat)) },
-		{ set__singleton_set(RefLocs0, Placed - Lvals0) }
+		{ map__search(Vars0, Var, var_info(RefLocs0, _Stat)) },
+		{ set__singleton_set(RefLocs0, _Placed - RefStat0) }
 	->
 		(
+			{ RefStat0 = evaled(Lvals0) },
 			{ set__to_sorted_list(Lvals0, LvalList) },
 			{ code_exprn__select_reg_or_stack_lval(LvalList, Lval0)}
 		->
 			{ Code = empty },
-			{ Lval = Lval0 },
-			{ Vars = Vars0 }
+			{ Lval = Lval0 }
 		;
 			code_exprn__select_preferred_lval(Var, Lval),
-			code_exprn__place_var_reference(Var, Lval, Code),
-			{ set__insert(Lvals0, Lval, Lvals) },
-			{ set__singleton_set(RefLocs, Placed - Lvals) },
-			{ map__det_update(Vars0, Var, var_info(RefLocs, Stat),
-				Vars) }
+			code_exprn__place_var_reference(Var, Lval, Code)
 		)
 	;
 		{ error("code_exprn__produce_ref_in_reg_or_stack: internal error") }
-	),
-	code_exprn__set_vars(Vars).
+	).
 
 
 %------------------------------------------------------------------------------%
@@ -1955,8 +2137,9 @@
 code_exprn__relocate_lval_in_refs(Old, New, Refs0, Refs) -->
 	{ set__to_sorted_list(Refs0, RefsList0) },
 	list__map_foldl(lambda([R0::in, R::out, Exprn0::in, Exprn::out] is det,
-	    (
-		R0 = Placed - Lvals0,
+	(
+	    R0 = Placed - RefStat0,
+	    ( RefStat0 = evaled(Lvals0),
 		set__to_sorted_list(Lvals0, LvalsList0),
 		list__map_foldl(lambda([L0::in, L::out, E0::in, E::out] is det,
 		    (
@@ -1965,8 +2148,12 @@
 			code_exprn__add_lval_reg_dependencies(L, E1, E)
 		    )), LvalsList0, LvalsList, Exprn0, Exprn),
 		set__list_to_set(LvalsList, Lvals),
-		R = Placed - Lvals
-	    )), RefsList0, RefsList),
+		R = Placed - evaled(Lvals)
+	    ; RefStat0 = cached(_, _, _),
+		R = R0,
+		Exprn = Exprn0
+	    )
+	)), RefsList0, RefsList),
 	{ set__list_to_set(RefsList, Refs) }.
 
 
@@ -2185,10 +2372,11 @@
 code_exprn__max_reg_in_use_refs(Refs, Max0, Max) :-
 	set__to_sorted_list(Refs, RefsList),
 	list__foldl(lambda([Ref::in, N0::in, N::out] is det,
-		(
-			Ref = _Placed - Lvals,
+		( Ref = _Placed - evaled(Lvals),
 			set__to_sorted_list(Lvals, LvalsList),
 			code_exprn__max_reg_in_use_lvals(LvalsList, N0, N)
+		; Ref = _Placed - cached(_, _, _),
+			N = N0
 		)), RefsList, Max0, Max).
 
 %------------------------------------------------------------------------------%
Index: code_gen.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/code_gen.m,v
retrieving revision 1.33.2.11
diff -u -r1.33.2.11 code_gen.m
--- 1.33.2.11	1998/08/12 03:30:56
+++ code_gen.m	1998/08/12 05:49:24
@@ -751,12 +751,13 @@
 			)
 		},
 
-		code_gen__generate_goal_2(Goal, GoalInfo, CodeModel, Code),
+		code_gen__generate_goal_2(Goal, GoalInfo, CodeModel, GoalCode),
 
 			% Make live any variables which subsequent goals
 			% will expect to be live, but were not generated
 		code_info__set_instmap(Instmap),
-		code_info__post_goal_update(GoalInfo)
+		code_info__post_goal_update(GoalInfo, UpdateCode),
+		{ Code = tree(GoalCode, UpdateCode) }
 	;
 		{ Code = empty }
 	),
Index: code_info.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/code_info.m,v
retrieving revision 1.211.2.16
diff -u -r1.211.2.16 code_info.m
--- 1.211.2.16	1998/08/12 03:31:07
+++ code_info.m	1998/08/12 05:49:24
@@ -539,8 +539,9 @@
 	% code_info__post_goal_update(GoalInfo, OldCodeInfo, NewCodeInfo)
 	% updates OldCodeInfo to produce NewCodeInfo with the changes described
 	% by GoalInfo.
-:- pred code_info__post_goal_update(hlds_goal_info, code_info, code_info).
-:- mode code_info__post_goal_update(in, in, out) is det.
+:- pred code_info__post_goal_update(hlds_goal_info, code_tree, 
+		code_info, code_info).
+:- mode code_info__post_goal_update(in, out, in, out) is det.
 
 	% Find out the type of the given variable.
 :- pred code_info__variable_type(var, type, code_info, code_info).
@@ -685,10 +686,11 @@
 	).
 
 	% Update the code info structure to be consistent
-	% immediately after generating a goal.
-code_info__post_goal_update(GoalInfo) -->
+	% immediately after generating a goal
+code_info__post_goal_update(GoalInfo, Code) -->
 	% note: we must be careful to apply deaths before births
 	{ goal_info_get_post_deaths(GoalInfo, PostDeaths) },
+	code_info__uncache_references(PostDeaths, Code),
 	code_info__rem_forward_live_vars(PostDeaths),
 	code_info__make_vars_forward_dead(PostDeaths),
 	{ goal_info_get_post_births(GoalInfo, PostBirths) },
@@ -1050,7 +1052,7 @@
 	simple_neg_info::out, code_info::in, code_info::out) is det.
 
 :- pred code_info__leave_simple_neg(hlds_goal_info::in, simple_neg_info::in,
-	code_info::in, code_info::out) is det.
+	code_tree::out, code_info::in, code_info::out) is det.
 
 	% `prepare_for_det_commit' and `generate_det_commit' should be
 	% called before and after generating the code for the multi goal
@@ -1551,8 +1553,8 @@
 	{ require(unify(Code, empty), "nonempty code for simple neg") },
 	code_info__pre_goal_update(GoalInfo, yes).
 
-code_info__leave_simple_neg(GoalInfo, FailInfo) -->
-	code_info__post_goal_update(GoalInfo),
+code_info__leave_simple_neg(GoalInfo, FailInfo, Code) -->
+	code_info__post_goal_update(GoalInfo, Code),
 	code_info__set_fail_info(FailInfo).
 
 :- pred code_info__make_fake_resume_map(list(var)::in,
@@ -2817,6 +2819,9 @@
 :- pred code_info__cache_expression(var, rval, code_info, code_info).
 :- mode code_info__cache_expression(in, in, in, out) is det.
 
+:- pred code_info__cache_reference(var, var, tag, int, code_info, code_info).
+:- mode code_info__cache_reference(in, in, in, in, in, out) is det.
+
 :- pred code_info__place_var(var, lval, code_tree, code_info, code_info).
 :- mode code_info__place_var(in, in, out, in, out) is det.
 
@@ -2832,6 +2837,10 @@
 :- mode code_info__produce_variable_in_references(in, out,
 	in, out) is det.
 
+:- pred code_info__uncache_references(set(var), code_tree, 
+	code_info, code_info).
+:- mode code_info__uncache_references(in, out, in, out) is det.
+
 :- pred code_info__produce_variable_in_reg(var, code_tree, rval,
 	code_info, code_info).
 :- mode code_info__produce_variable_in_reg(in, out, out, in, out) is det.
@@ -2930,6 +2939,12 @@
 	{ code_exprn__cache_exprn(Var, Rval, Exprn0, Exprn) },
 	code_info__set_exprn_info(Exprn).
 
+code_info__cache_reference(Var, LVar, Tag, FieldNum) -->
+	code_info__get_exprn_info(Exprn0),
+	{ code_exprn__cache_reference(Var, LVar, Tag, FieldNum,
+		Exprn0, Exprn) },
+	code_info__set_exprn_info(Exprn).
+
 code_info__place_var(Var, Lval, Code) -->
 	code_info__get_exprn_info(Exprn0),
 	{ code_exprn__place_var(Var, Lval, Code, Exprn0, Exprn) },
@@ -2974,6 +2989,11 @@
 	{ code_exprn__place_var_in_references(Var, Code, Exprn0, Exprn) },
 	code_info__set_exprn_info(Exprn).
 
+code_info__uncache_references(Vars, Code) -->
+	code_info__get_exprn_info(Exprn0),
+	{ code_exprn__uncache_references(Vars, Code, Exprn0, Exprn) },
+	code_info__set_exprn_info(Exprn).
+
 code_info__produce_variable_in_reg(Var, Code, Rval) -->
 	code_info__get_exprn_info(Exprn0),
 	{ code_exprn__produce_var_in_reg(Var, Rval, Code, Exprn0, Exprn) },
Index: hlds_pred.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/hlds_pred.m,v
retrieving revision 1.35.4.13
diff -u -r1.35.4.13 hlds_pred.m
--- 1.35.4.13	1998/08/07 05:17:18
+++ hlds_pred.m	1998/08/12 05:49:24
@@ -498,7 +498,7 @@
 arg_mode_is_input(ArgMode) :-
 	arg_mode_is_input_2(ArgMode, yes).
 
-	% Allow determinism checker to remind us of any new functor
+	% Allow determinism checker to remind us of any new functors
 	% that are added to the arg_mode type.
 :- pred arg_mode_is_input_2(arg_mode, bool).
 :- mode arg_mode_is_input_2(in, out) is det.
@@ -512,7 +512,7 @@
 arg_mode_is_output(ArgMode) :-
 	arg_mode_is_output_2(ArgMode, yes).
 
-	% Allow determinism checker to remind us of any new functor
+	% Allow determinism checker to remind us of any new functors
 	% that are added to the arg_mode type.
 :- pred arg_mode_is_output_2(arg_mode, bool).
 :- mode arg_mode_is_output_2(in, out) is det.
Index: ite_gen.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/ite_gen.m,v
retrieving revision 1.47.2.5
diff -u -r1.47.2.5 ite_gen.m
--- 1.47.2.5	1998/07/31 06:28:57
+++ ite_gen.m	1998/08/12 05:49:24
@@ -234,8 +234,8 @@
 			if_val(binop(Op, ValL, ValR), CodeAddr) -
 				"test inequality"
 		]) },
-		code_info__leave_simple_neg(GoalInfo, SimpleNeg),
-		{ Code = tree(tree(CodeL, CodeR), TestCode) }
+		code_info__leave_simple_neg(GoalInfo, SimpleNeg, LeaveCode),
+		{ Code = tree(tree(CodeL, CodeR), tree(LeaveCode, TestCode)) }
 	;
 		generate_negation_general(CodeModel, Goal,
 			ResumeVars, ResumeLocs, Code)
Index: middle_rec.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/middle_rec.m,v
retrieving revision 1.66.2.6
diff -u -r1.66.2.6 middle_rec.m
--- 1.66.2.6	1998/07/31 06:29:21
+++ middle_rec.m	1998/08/12 05:49:24
@@ -134,7 +134,15 @@
 	code_info__generate_branch_end(StoreMap, MaybeEnd1, MaybeEnd,
 		RecSaveCode),
 
-	code_info__post_goal_update(SwitchGoalInfo),
+	code_info__post_goal_update(SwitchGoalInfo, UpdateCode),
+		% UpdateCode should be empty for switches because they
+		% are not atomic goals.
+	{ tree__is_empty(UpdateCode) ->
+		true
+	;
+		error("middle_rec__generate_switch: UpdateCode not empty")
+	},
+
 	code_info__after_all_branches(StoreMap, MaybeEnd),
 
 	code_info__get_arginfo(ArgModes),
Index: tree.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/tree.m,v
retrieving revision 1.9
diff -u -r1.9 tree.m
--- 1.9	1997/07/27 15:01:48
+++ tree.m	1998/08/12 05:49:25
@@ -29,6 +29,11 @@
 :- pred tree__is_empty(tree(T)).
 :- mode tree__is_empty(in) is semidet.
 
+:- pred tree__construct(pred(T1, tree(T2), T3, T3), list(T1), tree(T2),
+		T3, T3).
+:- mode tree__construct(pred(in, out, in, out) is det, in, out,
+		in, out) is det.
+
 %-----------------------------------------------------------------------------%
 
 :- implementation.
@@ -54,3 +59,25 @@
 	tree__is_empty(R).
 
 %-----------------------------------------------------------------------------%
+
+tree__construct(P, List, Tree) -->
+	tree__construct_2(P, List, empty, Tree).
+
+:- pred tree__construct_2(pred(T1, tree(T2), T3, T3), list(T1), tree(T2),
+		tree(T2), T3, T3).
+:- mode tree__construct_2(pred(in, out, in, out) is det, in, in, out, in, out)
+		is det.
+
+tree__construct_2(_P, [], Tree, Tree) --> [].
+tree__construct_2(P, [X | Xs], Tree0, Tree) -->
+	call(P, X, Tree1),
+	{ Tree1 = empty ->
+		Tree2 = Tree0
+	; Tree0 = empty ->
+		Tree2 = Tree1
+	;
+		Tree2 = tree(Tree0, Tree1)
+	},
+	tree__construct_2(P, Xs, Tree2, Tree).
+
+%-----------------------------------------------------------------------------%
Index: unify_gen.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/unify_gen.m,v
retrieving revision 1.83.2.10
diff -u -r1.83.2.10 unify_gen.m
--- 1.83.2.10	1998/08/05 08:09:08
+++ unify_gen.m	1998/08/12 05:49:25
@@ -311,10 +311,8 @@
 	{ Expr = create(SimpleTag, RVals, no, CellNo, VarTypeMsg) },
 	code_info__cache_expression(Var, Expr),
 	unify_gen__aliased_vars_set_location(Args, ArgTypes, Modes,
-		InstMap0, InstMap, InstTable, ModuleInfo, Var, SimpleTag,
-		0, Code0),
-	unify_gen__maybe_place_refs(Var, Code1),
-	{ Code = tree(Code0, Code1) }.
+		InstMap0, InstMap, InstTable, ModuleInfo, Var, SimpleTag, 0),
+	unify_gen__maybe_place_refs(Var, Code).
 unify_gen__generate_construction_2(complicated_tag(Bits0, Num0),
 		Var, Args, Modes, IMDelta, Code) -->
 	code_info__get_module_info(ModuleInfo),
@@ -334,9 +332,8 @@
 	{ Expr = create(Bits0, RVals, no, CellNo, VarTypeMsg) },
 	code_info__cache_expression(Var, Expr),
 	unify_gen__aliased_vars_set_location(Args, ArgTypes, Modes, InstMap0,
-		InstMap, InstTable, ModuleInfo, Var, Bits0, 1, Code0),
-	unify_gen__maybe_place_refs(Var, Code1),
-	{ Code = tree(Code0, Code1) }.
+		InstMap, InstTable, ModuleInfo, Var, Bits0, 1),
+	unify_gen__maybe_place_refs(Var, Code).
 unify_gen__generate_construction_2(complicated_constant_tag(Bits1, Num1),
 		Var, _Args, _Modes, _IMDelta, Code) -->
 	unify_gen__cache_unification(Var,
@@ -506,10 +503,9 @@
 			unify_gen__var_types(ArgsPrime, ArgTypes),
 			unify_gen__aliased_vars_set_location(ArgsPrime,
 				ArgTypes, ModesPrime, InstMap0, InstMap,
-				InstTable, ModuleInfo, Var, 0, FirstField,
-				Code100)
+				InstTable, ModuleInfo, Var, 0, FirstField)
 		;
-			{ Code100 = empty }
+			[]
 		)
 	;
 		{ SkipFirstArg = no },
@@ -516,9 +512,9 @@
 		unify_gen__var_types(Args, ArgTypes),
 		unify_gen__aliased_vars_set_location(Args,
 			ArgTypes, Modes, InstMap0, InstMap, InstTable,
-			ModuleInfo, Var, 0, FirstField, Code100)
+			ModuleInfo, Var, 0, FirstField)
 	),
-	{ Code = tree(Code98, tree(Code99, Code100)) }.
+	{ Code = tree(Code98, Code99) }.
 
 % Cache a unification.  If the mode of the LHS variable is ref_in then
 % produce code to place it's value in the required locations.
@@ -624,18 +620,18 @@
 
 :- pred unify_gen__aliased_vars_set_location(list(var), list(type),
 		list(uni_mode), instmap, instmap, inst_table, module_info,
-		var, tag, int, code_tree, code_info, code_info).
+		var, tag, int, code_info, code_info).
 :- mode unify_gen__aliased_vars_set_location(in, in, in, in, in, in, in,
-		in, in, in, out, in, out) is det.
+		in, in, in, in, out) is det.
 
 unify_gen__aliased_vars_set_location(Args, Types, Modes, InstMap0, InstMap,
-		InstTable, ModuleInfo, Var, Tag, FieldNum, Code) -->
+		InstTable, ModuleInfo, Var, Tag, FieldNum) -->
 	( 
 		unify_gen__aliased_vars_set_location_2(Args, Types, Modes,
 			InstMap0, InstMap, InstTable, ModuleInfo, Var, Tag,
-			FieldNum, Code0)
+			FieldNum)
 	->
-		{ Code = Code0 }
+		[]
 	;
 		{ error("unify_gen__aliased_vars_set_location: length mismatch") }
 	).
@@ -642,35 +638,26 @@
 
 :- pred unify_gen__aliased_vars_set_location_2(list(var), list(type),
 		list(uni_mode), instmap, instmap, inst_table, module_info,
-		var, tag, int, code_tree, code_info, code_info).
+		var, tag, int, code_info, code_info).
 :- mode unify_gen__aliased_vars_set_location_2(in, in, in, in, in, in, in,
-		in, in, in, out, in, out) is semidet.
+		in, in, in, in, out) is semidet.
 
-unify_gen__aliased_vars_set_location_2([], [], [], _, _, _, _, _, _, _,
-		empty) --> [].
+unify_gen__aliased_vars_set_location_2([], [], [], _, _, _, _, _, _, _) --> [].
 unify_gen__aliased_vars_set_location_2([Var | Vars], [Type | Types],
 		[Mode | Modes], InstMap0, InstMap, InstTable, ModuleInfo,
-		LHSVar, Tag, FieldNum, Code) -->
+		LHSVar, Tag, FieldNum) -->
 	{ Mode = ((_LI - RI) -> (_LF - RF)) },
 	( 
 		{ insts_to_arg_mode(InstTable, ModuleInfo, RI, InstMap0,
 			RF, InstMap, Type, ref_out) }
 	->
-		code_info__acquire_reg_for_var(Var, Reg),
-		code_info__set_var_reference_location(Var, Reg),
-		code_info__produce_variable(LHSVar, Code0, RVal),
-		{ Code1 = node(
-			[assign(Reg, mem_addr(heap_ref(RVal, Tag, FieldNum))) -
-				"place reference in reg"]) },
-		{ Code2 = tree(Code0, Code1) }
+		code_info__cache_reference(Var, LHSVar, Tag, FieldNum)
 	;
-		{ Code2 = empty }
+		[]
 	),
 	{ NextFieldNum is FieldNum + 1 },
 	unify_gen__aliased_vars_set_location_2(Vars, Types, Modes, InstMap0,
-		InstMap, InstTable, ModuleInfo, LHSVar, Tag, NextFieldNum,
-		Code3),
-	{ Code = tree(Code2, Code3) }.
+		InstMap, InstTable, ModuleInfo, LHSVar, Tag, NextFieldNum).
 
 %---------------------------------------------------------------------------%
 
-- 
David Overton
MEngSc Student                       Email: dmo at cs.mu.oz.au     
Department of Computer Science       Web: http://www.cs.mu.oz.au/~dmo
The University of Melbourne          Phone: +61 3 9344 9159



More information about the developers mailing list