[m-dev.] [reuse] for review: reuse cells with different tags

Peter Ross peter.ross at miscrit.be
Tue Mar 13 04:34:43 AEDT 2001


Hi,

For stayl or fjh to review.

Also it would be useful for the summer student doing the bytecode
interpreter to check my changes to the bytecode dir if possible.

I plan to also check the changes for the strip_tag operator onto the
main branch when this passes review.

Pete


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


Estimated hours taken: 6
Branches: reuse

Get structure reuse working correctly when the cell to be reused
possibly doesn't share the same tag as the cell we wish to replace it
with.

compiler/ml_unify_gen.m:
    Unless the cell to be reused and the current cell share the same
    tag, strip the old tag off and replace it with the correct tag.
    
compiler/sr_choice.m:
    When deciding which cell to reuse, also record the cons_ids that
    each cell could possibly have.

compiler/hlds_goal.m:
compiler/sr_data.m:
    Add fields to various data structures which record the possible
    cons_ids a cell could be instantiated with.

compiler/hlds_out.m:
    Print out the list of possible cons_ids in the cell_to_reuse.

compiler/sr_split.m:
    Update the how_to_construct field with the list of possible
    cons_ids.

compiler/sr_dead.m:
    Handle the change to the reuse_var type.

compiler/builtin_ops.m:
    Add the unary builtin operator strip_tag.

compiler/bytecode.m:
compiler/c_util.m:
compiler/java_util.m:
compiler/llds.m:
compiler/mlds_to_il.m:
compiler/opt_debug.m:
bytecode/mb_disasm.c:
bytecode/mb_exec.c:
    Handle the strip_tag operator.

Index: bytecode/mb_disasm.c
===================================================================
RCS file: /home/mercury1/repository/mercury/bytecode/mb_disasm.c,v
retrieving revision 1.2.4.2
diff -u -r1.2.4.2 mb_disasm.c
--- bytecode/mb_disasm.c	2001/02/20 10:14:56	1.2.4.2
+++ bytecode/mb_disasm.c	2001/03/12 17:11:07
@@ -920,7 +920,7 @@
 	"unmktag",
 	"mkbody",
 	"unmkbody",
-	"cast_to_unsigned",
+	"strip_tag",
 	"hash_string",
 	"bitwise_complement",
 	"not"
Index: bytecode/mb_exec.c
===================================================================
RCS file: /home/mercury1/repository/mercury/bytecode/mb_exec.c,v
retrieving revision 1.1.4.1
diff -u -r1.1.4.1 mb_exec.c
--- bytecode/mb_exec.c	2001/02/20 10:14:57	1.1.4.1
+++ bytecode/mb_exec.c	2001/03/12 17:11:08
@@ -1300,7 +1300,7 @@
 	unop_bad, 		/* unmktag */
 	unop_bad, 		/* mkbody */
 	unop_bad, 		/* unmkbody */
-	unop_bad,		/* cast_to_unsigned */
+	unop_bad,		/* strip_tag  */
 	unop_bad,		/* hash_string */
 	unop_bitwise_complement,
 	unop_not
Index: compiler/builtin_ops.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/builtin_ops.m,v
retrieving revision 1.2.4.2
diff -u -r1.2.4.2 builtin_ops.m
--- compiler/builtin_ops.m	2001/02/07 14:28:28	1.2.4.2
+++ compiler/builtin_ops.m	2001/03/12 17:11:08
@@ -24,6 +24,7 @@
 	--->	mktag
 	;	tag
 	;	unmktag
+	;	strip_tag
 	;	mkbody
 	;	unmkbody
 	;	hash_string
Index: compiler/bytecode.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/bytecode.m,v
retrieving revision 1.40.4.3
diff -u -r1.40.4.3 bytecode.m
--- compiler/bytecode.m	2001/02/20 10:15:09	1.40.4.3
+++ compiler/bytecode.m	2001/03/12 17:11:09
@@ -1126,8 +1126,7 @@
 unop_code(unmktag,		 2).
 unop_code(mkbody,		 3).
 unop_code(unmkbody,		 4).
-% We used to use value `5' for cast_to_unsigned.
-% This is now no longer used.
+unop_code(strip_tag,		 5).
 unop_code(hash_string,		 6).
 unop_code(bitwise_complement,	 7).
 unop_code((not),		 8).
@@ -1140,6 +1139,7 @@
 unop_debug(unmktag,		"unmktag").
 unop_debug(mkbody,		"mkbody").
 unop_debug(unmkbody,		"unmkbody").
+unop_debug(strip_tag,		"strip_tag").
 unop_debug(hash_string,		"has_string").
 unop_debug(bitwise_complement,	"bitwise_complement").
 unop_debug((not),		"not").
Index: compiler/c_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/c_util.m,v
retrieving revision 1.4.2.4
diff -u -r1.4.2.4 c_util.m
--- compiler/c_util.m	2001/03/05 12:05:37	1.4.2.4
+++ compiler/c_util.m	2001/03/12 17:11:09
@@ -212,6 +212,7 @@
 c_util__unary_prefix_op(unmktag,		"MR_unmktag").
 c_util__unary_prefix_op(mkbody,			"MR_mkbody").
 c_util__unary_prefix_op(unmkbody,		"MR_unmkbody").
+c_util__unary_prefix_op(strip_tag,		"MR_strip_tag").
 c_util__unary_prefix_op(hash_string,		"MR_hash_string").
 c_util__unary_prefix_op(bitwise_complement,	"~").
 c_util__unary_prefix_op(not,			"!").
Index: compiler/hlds_goal.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.76.2.9
diff -u -r1.76.2.9 hlds_goal.m
--- compiler/hlds_goal.m	2001/02/28 13:34:12	1.76.2.9
+++ compiler/hlds_goal.m	2001/03/12 17:11:10
@@ -524,7 +524,7 @@
 :- type cell_to_reuse
 	---> cell_to_reuse(
 		prog_var,
-		cons_id,
+		list(cons_id),
 		list(bool)      % A `no' entry means that the corresponding
 				% argument already has the correct value
 				% and does not need to be filled in.
Index: compiler/hlds_out.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/hlds_out.m,v
retrieving revision 1.243.2.16
diff -u -r1.243.2.16 hlds_out.m
--- compiler/hlds_out.m	2001/03/08 18:36:15	1.243.2.16
+++ compiler/hlds_out.m	2001/03/12 17:11:11
@@ -1179,13 +1179,17 @@
 				io__write_string("cell just died (deconstruction).\n") 
 			;
 				{ REUSE = reuse(cell_reused(ProgVar,
-						IntroducesCondition)) }
+						IntroducesCondition,
+						ConsIds)) }
 			->
 				io__write_string("cell "),
 				mercury_output_var(ProgVar, VarSet, 
 					AppendVarnums),
+				io__write_string(" with possible cons_ids: ["),
+				io__write_list(ConsIds, ", ",
+						hlds_out__write_cons_id),
 				io__write_string(
-					" just reused in a construction "),
+					"] just reused in a construction "),
 				( { IntroducesCondition = yes } ->
 					io__write_string("conditionally.")
 				;
Index: compiler/java_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/java_util.m,v
retrieving revision 1.1.2.1
diff -u -r1.1.2.1 java_util.m
--- compiler/java_util.m	2001/03/05 12:05:44	1.1.2.1
+++ compiler/java_util.m	2001/03/12 17:11:11
@@ -76,13 +76,15 @@
 
 %-----------------------------------------------------------------------------%
 
-% XXX I'm not sure what the first six of these should be
+% XXX I'm not sure what the first seven of these should be
 %     for the Java backend.
 java_util__unary_prefix_op(mktag, _) :-
 	unexpected(this_file, "Java backend does not support tags").
 java_util__unary_prefix_op(tag,	_) :-
 	unexpected(this_file, "Java backend does not support tags").
 java_util__unary_prefix_op(unmktag, _) :-
+	unexpected(this_file, "Java backend does not support tags").
+java_util__unary_prefix_op(strip_tag, _) :-
 	unexpected(this_file, "Java backend does not support tags").
 java_util__unary_prefix_op(mkbody, _) :-
 	unexpected(this_file, "Java backend does not support tags").
Index: compiler/llds.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/llds.m,v
retrieving revision 1.263.2.4
diff -u -r1.263.2.4 llds.m
--- compiler/llds.m	2001/02/07 14:29:20	1.263.2.4
+++ compiler/llds.m	2001/03/12 17:11:12
@@ -1157,6 +1157,7 @@
 llds__unop_return_type(mktag, word).
 llds__unop_return_type(tag, word).
 llds__unop_return_type(unmktag, word).
+llds__unop_return_type(strip_tag, word).
 llds__unop_return_type(mkbody, word).
 llds__unop_return_type(unmkbody, word).
 llds__unop_return_type(hash_string, integer).
@@ -1166,6 +1167,7 @@
 llds__unop_arg_type(mktag, word).
 llds__unop_arg_type(tag, word).
 llds__unop_arg_type(unmktag, word).
+llds__unop_arg_type(strip_tag, word).
 llds__unop_arg_type(mkbody, word).
 llds__unop_arg_type(unmkbody, word).
 llds__unop_arg_type(hash_string, word).
Index: compiler/ml_unify_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_unify_gen.m,v
retrieving revision 1.16.2.10
diff -u -r1.16.2.10 ml_unify_gen.m
--- compiler/ml_unify_gen.m	2001/03/09 14:11:46	1.16.2.10
+++ compiler/ml_unify_gen.m	2001/03/12 17:11:13
@@ -1041,7 +1041,7 @@
 		{ MLDS_Statements = [AssignStatement] }
 	;
 		{ HowToConstruct = reuse_cell(CellToReuse) },
-		{ CellToReuse = cell_to_reuse(ReuseVar, ReuseConsId, _) },
+		{ CellToReuse = cell_to_reuse(ReuseVar, ReuseConsIds, _) },
 
 		{ MaybeConsId = yes(ConsId0) ->
 			ConsId = ConsId0
@@ -1049,10 +1049,16 @@
 			error("ml_gen_new_object: unknown cons id")
 		},
 
-		ml_variable_type(ReuseVar, ReuseType),
-		ml_cons_id_to_tag(ReuseConsId, ReuseType, ReuseConsIdTag),
-		{ ml_tag_offset_and_argnum(ReuseConsIdTag,
-				ReusePrimaryTag, _ReuseOffSet, _ReuseArgNum) },
+		list__map_foldl(
+			(pred(ReuseConsId::in, ReusePrimaryTag::out,
+					in, out) is det -->
+				ml_variable_type(ReuseVar, ReuseType),
+				ml_cons_id_to_tag(ReuseConsId, ReuseType,
+						ReuseConsIdTag),
+				{ ml_tag_offset_and_argnum(ReuseConsIdTag,
+						ReusePrimaryTag,
+						_ReuseOffSet, _ReuseArgNum) }
+			), ReuseConsIds, ReusePrimaryTags),
 
 		ml_cons_id_to_tag(ConsId, Type, ConsIdTag),
 		ml_field_names_and_types(Type, ConsId, ArgTypes, Fields),
@@ -1061,12 +1067,16 @@
 
 		ml_gen_var(Var, Var1Lval),
 		ml_gen_var(ReuseVar, Var2Lval),
-		{ ReusePrimaryTag = PrimaryTag ->
+
+		{ list__filter((pred(ReuseTag::in) is semidet :-
+				ReuseTag \= PrimaryTag
+			), ReusePrimaryTags, DifferentTags) },
+		{ DifferentTags = [] ->
 			Var2Rval = lval(Var2Lval)
 		;
 			Var2Rval = mkword(PrimaryTag,
-					binop(body, lval(Var2Lval),
-					ml_gen_mktag(ReusePrimaryTag)))
+					unop(std_unop(strip_tag),
+					lval(Var2Lval)))
 		},
 
 		{ MLDS_Statement = ml_gen_assign(Var1Lval, Var2Rval, Context) },
Index: compiler/mlds_to_il.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_il.m,v
retrieving revision 1.6.2.4
diff -u -r1.6.2.4 mlds_to_il.m
--- compiler/mlds_to_il.m	2001/02/20 10:15:31	1.6.2.4
+++ compiler/mlds_to_il.m	2001/03/12 17:11:15
@@ -1299,6 +1299,7 @@
 unaryop_to_il(std_unop(tag), _, Instrs) --> 
 	load(const(int_const(0)), Instrs).
 unaryop_to_il(std_unop(unmktag), _, comment_node("unmktag (a no-op)")) --> [].
+unaryop_to_il(std_unop(strip_tag),_,comment_node("strip_tag (a no-op)")) --> [].
 unaryop_to_il(std_unop(mkbody),	_, comment_node("mkbody (a no-op)")) --> [].
 unaryop_to_il(std_unop(unmkbody), _, comment_node("unmkbody (a no-op)")) --> [].
 
Index: compiler/opt_debug.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/opt_debug.m,v
retrieving revision 1.105.2.4
diff -u -r1.105.2.4 opt_debug.m
--- compiler/opt_debug.m	2001/02/07 14:30:13	1.105.2.4
+++ compiler/opt_debug.m	2001/03/12 17:11:15
@@ -861,6 +861,7 @@
 opt_debug__dump_unop(mktag, "mktag").
 opt_debug__dump_unop(tag, "tag").
 opt_debug__dump_unop(unmktag, "unmktag").
+opt_debug__dump_unop(strip_tag, "strip_tag").
 opt_debug__dump_unop(mkbody, "mkbody").
 opt_debug__dump_unop(unmkbody, "unmkbody").
 opt_debug__dump_unop(not, "not").
Index: compiler/sr_choice.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_choice.m,v
retrieving revision 1.1.2.13
diff -u -r1.1.2.13 sr_choice.m
--- compiler/sr_choice.m	2001/03/07 17:20:33	1.1.2.13
+++ compiler/sr_choice.m	2001/03/12 17:11:17
@@ -192,10 +192,11 @@
 
 			% XXX recode this more efficiently at some stage.
 		{ P = (pred(Candidate::out) is nondet :- 
-			list__member(Candidate, PossibleCandidates),
-			CandidateVar = fst(Candidate),
+			list__member(Candidate0, PossibleCandidates),
+			CandidateVar = Candidate0 ^ var,
 			multi_map__search(Map, CandidateVar, ConsIds),
-			list__remove_dups(ConsIds, [ConsId])
+			list__remove_dups(ConsIds, [ConsId]),
+			Candidate = Candidate0 ^ cons_ids := yes(ConsIds)
 		)}
 	;
 		{ Constraint = within_n_cells_difference(Difference) },
@@ -206,8 +207,8 @@
 			% require storage of the corresponding type
 			% infos.
 		{ P = (pred(Candidate::out) is nondet :- 
-			list__member(Candidate, PossibleCandidates),
-			CandidateVar = fst(Candidate),
+			list__member(Candidate0, PossibleCandidates),
+			CandidateVar = Candidate0 ^ var,
 			multi_map__search(Map, CandidateVar, ConsIds),
 			cons_id_arity(ConsId, Arity),
 			all [ReuseConsId] (
@@ -217,7 +218,8 @@
 					cons_id_arity(ReuseConsId, ReuseArity),
 					ReuseArity - Arity =< Difference
 				)
-			)
+			),
+			Candidate = Candidate0 ^ cons_ids := yes(ConsIds)
 		)}
 	),
 	{ solutions(P, Candidates) },
@@ -485,9 +487,11 @@
 		{ Selection = lifo },
 		Locals =^ lifo ^ local,
 		Globals =^ lifo ^ global,
-		{ F = (pred(Var::in, Var - Cond::out) is semidet :-
-				assoc_list__search(PossibleCandidates,
-						Var, Cond),
+		{ F = (pred(Var::in, LocalReuseVar::out) is semidet :-
+				list__filter((pred(RV::in) is semidet :-
+						Var = RV ^ var
+					), PossibleCandidates,
+					[LocalReuseVar]),
 				\+ set__member(Var, LocalReused0),
 				\+ set__member(Var, GlobalReused)
 			)},
@@ -497,14 +501,21 @@
 		{ Selection = random },
 		{ P = (pred(Choice::out) is nondet :- 
 			list__member(Choice, PossibleCandidates),
-			ChoiceVar = fst(Choice),
+			ChoiceVar = Choice ^ var,
 			\+ set__member(ChoiceVar, LocalReused0),
 			\+ set__member(ChoiceVar, GlobalReused)
 		)},
 
 		{ solutions(P, Candidates) }
 	),
-	( { Candidates = [ReuseVar - ReuseCond | _] } ->
+	( { Candidates = [Candidate | _] } ->
+		{ ReuseVar = Candidate ^ var },
+		{ ReuseCond = Candidate ^ condition },
+		{ Candidate ^ cons_ids = yes(ConsIds0) ->
+			ConsIds = ConsIds0
+		;
+			error("select_reuses_unification: no cons_ids.")
+		},
 		{ set__insert(LocalReused0, ReuseVar, LocalReused) },
 		{
 			ReuseCond = always,
@@ -514,7 +525,8 @@
 			ConditionalReuse = yes
 		},
 		{ goal_info_set_reuse(GoalInfo0,
-				reuse(cell_reused(ReuseVar, ConditionalReuse)),
+				reuse(cell_reused(ReuseVar, ConditionalReuse,
+						ConsIds)),
 				GoalInfo) },
 		ReuseConditions =^ reuse_conds,
 		^ reuse_conds := [ReuseCond | ReuseConditions]
Index: compiler/sr_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_data.m,v
retrieving revision 1.1.2.15
diff -u -r1.1.2.15 sr_data.m
--- compiler/sr_data.m	2001/03/09 10:32:39	1.1.2.15
+++ compiler/sr_data.m	2001/03/12 17:11:17
@@ -18,7 +18,7 @@
 :- import_module bool, map, set, std_util, list, io, term.
 :- import_module pa_alias_as, pa_datastruct.
 :- import_module sr_live.
-:- import_module hlds_pred, hlds_module, prog_data.
+:- import_module hlds_data, hlds_pred, hlds_module, prog_data.
 
 	% The information placed in the goal info which is used by
 	% structure reuse.
@@ -36,8 +36,10 @@
 
 					% The variable we have selected
 					% for reuse and whether the
-					% reuse is conditional
-			; 	cell_reused(prog_var, bool)
+					% reuse is conditional and the
+					% possible cons_ids that
+					% variable may have.
+			; 	cell_reused(prog_var, bool, list(cons_id))
 
 					% Call the reuse version of the
 					% call and wheter calling the
@@ -45,7 +47,13 @@
 			; 	reuse_call(bool)
 			; 	missed_reuse_call(list(string)). 
 
-:- type reuse_var == pair(prog_var, reuse_condition).
+:- type reuse_var
+	--->	reuse_var(
+			var		:: prog_var,
+			condition	:: reuse_condition,
+			cons_ids	:: maybe(list(cons_id))
+		).
+
 :- type choice_info
 	--->	deconstruct(
 				% The condition under which this cell
Index: compiler/sr_dead.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_dead.m,v
retrieving revision 1.1.2.11
diff -u -r1.1.2.11 sr_dead.m
--- compiler/sr_dead.m	2001/02/07 14:30:37	1.1.2.11
+++ compiler/sr_dead.m	2001/03/12 17:11:18
@@ -329,7 +329,7 @@
 :- mode dead_cell_pool_leave_scope( in, in, out) is det.
 
 :- pred dead_cell_pool_try_to_reuse( cons_id, dead_cell_pool, 
-		set(pair(prog_var, reuse_condition))).
+		set(reuse_var)).
 :- mode dead_cell_pool_try_to_reuse( in, in, out) is det.
 
 dead_cell_pool_init( HVS, Pool ):- 
@@ -465,10 +465,9 @@
 	Extra = extra( DeadArity, _, _), 
 	Arity =< DeadArity.
 
-:- pred to_pair_var_condition( pair( prog_var, dead_extra_info), 
-		pair( prog_var, reuse_condition) ).
-:- mode to_pair_var_condition( in, out ) is det.
+:- pred to_pair_var_condition(pair(prog_var, dead_extra_info), reuse_var).
+:- mode to_pair_var_condition(in, out) is det.
 
-to_pair_var_condition( Var - Extra, Var - Condition ) :- 
-	Extra = extra( _, Condition, _).
+to_pair_var_condition(Var - Extra, reuse_var(Var, Condition, no)) :- 
+	Extra = extra(_, Condition, _).
 
Index: compiler/sr_split.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/sr_split.m,v
retrieving revision 1.1.2.10
diff -u -r1.1.2.10 sr_split.m
--- compiler/sr_split.m	2001/03/07 18:07:05	1.1.2.10
+++ compiler/sr_split.m	2001/03/12 17:11:18
@@ -312,7 +312,7 @@
 	{ Goal0 = unify(UVar, Rhs, Mode, Unification0, Ctxt) },
 	{
 		goal_info_get_reuse(GoalInfo0, Reuse),
-		Reuse = reuse(cell_reused(ReuseVar, ConditionalReuse))
+		Reuse = reuse(cell_reused(ReuseVar, ConditionalReuse, ConsIds))
 	->
 		( ConditionalReuse = yes, LocalReuseOnly = yes ->
 			Unification = Unification0,
@@ -328,7 +328,7 @@
 					% strategy that only cells with
 					% the same cons_id can be shared.
 				HTC = reuse_cell(cell_to_reuse(ReuseVar,
-						ConsId,
+						ConsIds,
 						list__duplicate(
 							list__length(Vars), no)
 						)),
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------



More information about the developers mailing list