[m-dev.] diff: performance improvements for Aditi

[Simon Taylor]

Estimated hours taken: 5

compiler/rl_out.pp:
	Use the `one_reference' bytecode to avoid unnecessary copying.
	Use the `has_index' bytecode to avoid adding indexes multiple times.

compiler/rl_sort.m:
	Fix bugs in the rules describing how required and available
	sorting and indexing are affected by the `make_unique' instruction.

compiler/rl.m:
	Remove an obsolete comment.

Index: rl.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl.m,v
retrieving revision 1.3
diff -u -u -r1.3 rl.m
--- rl.m	1999/06/16 00:34:46	1.3
+++ rl.m	1999/06/23 04:42:20
@@ -239,9 +239,6 @@
 		% to the input. To introduce this, the compiler must know that
 		% there are no later references in the code to the input
 		% relation.
-		% I'm not 100% sure that the reference counts maintained
-		% by Aditi can be used in this way - currently we always
-		% do the copy. 
 		% Make sure the output has the given set of indexes, even
 		% if it isn't copied.
 		make_unique(
Index: rl_out.pp
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_out.pp,v
retrieving revision 1.4
diff -u -u -r1.4 rl_out.pp
--- rl_out.pp	1999/06/16 00:36:32	1.4
+++ rl_out.pp	1999/06/23 05:07:59
@@ -829,20 +829,22 @@
 	)) },
 	rl_out__generate_stream_instruction(Output, InstrCode, Code).
 rl_out__generate_instr(add_index(output_rel(Rel, Indexes)) - _, Code) -->
-	rl_out__add_indexes_to_rel(Rel, Indexes, IndexCodes),
-	{ Code = node(IndexCodes) }.
+	rl_out__add_indexes_to_rel(may_have_index, Rel, Indexes, Code).
 rl_out__generate_instr(clear(Rel) - _, Code) -->
 	rl_out_info_get_relation_addr(Rel, Addr),
 	{ Code = node([rl_PROC_clear(Addr)]) }.
 rl_out__generate_instr(init(output_rel(Rel, Indexes)) - _, Code) -->
 	rl_out_info_get_relation_addr(Rel, Addr),
 	rl_out_info_get_relation_schema_offset(Rel, SchemaOffset),
-	rl_out__add_indexes_to_rel(Rel, Indexes, IndexCodes),
-	{ Code = node([
-		rl_PROC_unsetrel(Addr),
-		rl_PROC_createtemprel(Addr, SchemaOffset) |
+	rl_out__add_indexes_to_rel(does_not_have_index,
+		Rel, Indexes, IndexCodes),
+	{ Code = 
+		tree(node([
+			rl_PROC_unsetrel(Addr),
+			rl_PROC_createtemprel(Addr, SchemaOffset)
+		]),
 		IndexCodes
-	]) }.
+	) }.
 rl_out__generate_instr(insert_tuple(Output, Input, Exprn) - _, Code) -->
 	rl_out__generate_stream(Input, InputStream),
 	rl_out_info_get_output_relation_schema_offset(Output,
@@ -904,17 +906,25 @@
 			rl_PROC_var_list_nil
 		])
 	) }.
-rl_out__generate_instr(make_unique(OutputRel, InputRel) - Comment,
-		Code) -->
-	% This should eventually do something like:
-	% 	if (num_references(InputRel) == 1) {
+rl_out__generate_instr(make_unique(OutputRel, Input) - Comment, Code) -->
+	% 	if (one_reference(InputRel)) {
 	% 		OutputRel = ref(InputRel)
 	% 	} else {
 	% 		OutputRel = copy(InputRel)
 	%	}
-	% At the moment reference counting doesn't work, so we always copy.
-	rl_out__generate_instr(copy(OutputRel, InputRel) - Comment,
-		Code).
+	rl_out_info_get_relation_addr(Input, InputAddr),
+	{ CondCode = node([rl_PROC_one_reference(InputAddr)]) },
+
+	{ OutputRel = output_rel(Output, _) },
+	rl_out__generate_instr(ref(Output, Input) - Comment, ThenCode0),
+	% We may not need to generate this instruction - rl_sort.m
+	% has enough information to work out whether this is actually needed.
+	rl_out__generate_instr(add_index(OutputRel) - Comment, ThenCode1),
+	{ ThenCode = tree(ThenCode0, ThenCode1) },
+
+	rl_out__generate_instr(copy(OutputRel, Input) - Comment, ElseCode),
+
+	rl_out__generate_ite(CondCode, ThenCode, ElseCode, Code).
 rl_out__generate_instr(call(ProcName, Inputs, OutputRels, SaveRels) - _,
 		Code) -->
 
@@ -932,7 +942,8 @@
 	rl_out_info_assign_const(string(ProcNameStr), ProcNameConst),
 	rl_out_info_return_tmp_vars(SaveTmpVars, SaveClearCode),
 	rl_out_info_return_tmp_vars(OverlapTmpVars, OverlapClearCode),
-	rl_out__add_indexes_to_rels(OutputRels, IndexCode),
+	rl_out__add_indexes_to_rels(does_not_have_index,
+		OutputRels, IndexCode),
 	{ Code =
 		tree(SaveCode,
 		tree(node([rl_PROC_call(ProcNameConst)]), 
@@ -1152,28 +1163,55 @@
 	string__append("#:", AttrStr, Str).
 
 %-----------------------------------------------------------------------------%
+
+:- type check_index
+	--->	may_have_index
+	;	does_not_have_index
+	.
 
-:- pred rl_out__add_indexes_to_rels(list(output_rel)::in, byte_tree::out,
+:- pred rl_out__add_indexes_to_rels(check_index::in,
+		list(output_rel)::in, byte_tree::out,
 		rl_out_info::in, rl_out_info::out) is det.
 	
-rl_out__add_indexes_to_rels([], empty) --> [].
-rl_out__add_indexes_to_rels([output_rel(Output, Indexes) | Outputs],
-		IndexCode) -->
-	rl_out__add_indexes_to_rel(Output, Indexes, Instrs),
-	rl_out__add_indexes_to_rels(Outputs, IndexCode1),
-	{ IndexCode = tree(node(Instrs), IndexCode1) }.
-
-:- pred rl_out__add_indexes_to_rel(relation_id::in, list(index_spec)::in,
-		list(bytecode)::out, rl_out_info::in, rl_out_info::out) is det.
-
-rl_out__add_indexes_to_rel(_, [], []) --> [].
-rl_out__add_indexes_to_rel(Output, [Index | Indexes],
-		[IndexInstr | IndexInstrs]) -->
+rl_out__add_indexes_to_rels(_, [], empty) --> [].
+rl_out__add_indexes_to_rels(CheckIndex,
+		[output_rel(Output, Indexes) | Outputs], IndexCode) -->
+	rl_out__add_indexes_to_rel(CheckIndex, Output, Indexes, IndexCode0),
+	rl_out__add_indexes_to_rels(CheckIndex, Outputs, IndexCode1),
+	{ IndexCode = tree(IndexCode0, IndexCode1) }.
+
+:- pred rl_out__add_indexes_to_rel(check_index::in, relation_id::in,
+		list(index_spec)::in, byte_tree::out,
+		rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__add_indexes_to_rel(_, _, [], empty) --> [].
+rl_out__add_indexes_to_rel(CheckIndex, Output,
+		[Index | Indexes], IndexCode) -->
 	rl_out_info_get_relation_addr(Output, OutputAddr),
 	{ rl_out__index_spec_to_string(Index, IndexStr) },
 	rl_out_info_assign_const(string(IndexStr), IndexConst),
-	{ IndexInstr = rl_PROC_addindextorel(OutputAddr, IndexConst) },
-	rl_out__add_indexes_to_rel(OutputAddr, Indexes, IndexInstrs).
+
+	(
+		{ CheckIndex = may_have_index },
+		% Generate code to test whether the index already exists
+		% before adding it.
+		{ CondCode = node([
+			rl_PROC_has_index(OutputAddr, IndexConst)
+		]) },
+		{ ThenCode = empty },
+		{ ElseCode = node([
+			rl_PROC_addindextorel(OutputAddr, IndexConst)
+		]) },
+		rl_out__generate_ite(CondCode, ThenCode, ElseCode, IndexCode0)
+	;
+		{ CheckIndex = does_not_have_index },
+		{ IndexCode0 = node([
+			rl_PROC_addindextorel(OutputAddr, IndexConst)
+		]) }
+	),
+	rl_out__add_indexes_to_rel(CheckIndex,
+		OutputAddr, Indexes, IndexCode1),
+	{ IndexCode = tree(IndexCode0, IndexCode1) }.
 
 %-----------------------------------------------------------------------------%
 
@@ -1208,13 +1246,14 @@
 			TmpVar, TmpClearCode),
 
 		{ LockSpec = 0 },	% default lock spec
-		rl_out__add_indexes_to_rel(Output, Indexes, IndexInstrs),
+		rl_out__add_indexes_to_rel(does_not_have_index,
+			Output, Indexes, IndexInstrs),
 		rl_out_info_get_next_materialise_id(Id),
 		{ Code = 
 			tree(node([
-				rl_PROC_createtemprel(TmpVar, SchemaOffset) |
-				IndexInstrs
+				rl_PROC_createtemprel(TmpVar, SchemaOffset)
 			]),
+			tree(IndexInstrs,
 			tree(node([
 				rl_PROC_materialise(Id)
 			]),
@@ -1230,7 +1269,7 @@
 				rl_PROC_setrel(OutputAddr, TmpVar)
 			]),
 			TmpClearCode
-		)))) }
+		))))) }
 	).
 
 %-----------------------------------------------------------------------------%
Index: rl_sort.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_sort.m,v
retrieving revision 1.2
diff -u -u -r1.2 rl_sort.m
--- rl_sort.m	1999/05/27 01:06:02	1.2
+++ rl_sort.m	1999/06/23 04:45:20
@@ -205,6 +205,16 @@
 
 %-----------------------------------------------------------------------------%
 
+	% Filter out unneeded specs.
+:- type spec_filter ==  pred(pair(sort_index, sort_req)).
+:- inst spec_filter == (pred(in) is semidet).
+
+:- func true_filter = (spec_filter::out(spec_filter)) is det.
+
+true_filter = (pred(_::in) is semidet :- true).
+
+%-----------------------------------------------------------------------------%
+
 :- pred rl_sort__init_block(block_id::in, sort_data_map::in,
 		sort_data_map::out, rl_opt_info::in, rl_opt_info::out) is det.
 
@@ -498,10 +508,21 @@
 
 	% Add the required sortedness of the first relation
 	% to that of the second.
-:- pred rl_sort__assign_relation_sortedness(block_id::in, relation_id::in,
-		relation_id::in, sort_info::in, sort_info::out) is det.
+:- pred rl_sort__assign_sortedness_and_indexing(block_id::in,
+		relation_id::in, relation_id::in,
+		sort_info::in, sort_info::out) is det.
+
+rl_sort__assign_sortedness_and_indexing(BlockId,
+		Relation1, Relation2) -->
+	rl_sort__assign_sortedness_and_indexing(true_filter, BlockId,
+		Relation1, Relation2).
+
+:- pred rl_sort__assign_sortedness_and_indexing(spec_filter::in(spec_filter),
+		block_id::in, relation_id::in, relation_id::in,
+		sort_info::in, sort_info::out) is det.
 
-rl_sort__assign_relation_sortedness(BlockId, Relation1, Relation2) -->
+rl_sort__assign_sortedness_and_indexing(SpecFilter, BlockId,
+		Relation1, Relation2) -->
 	=(sort_info(sortedness(RelMap0, _), _, RLInfo)),
 	{ rl_opt_info_get_relation_info(Relation2, RelInfo, RLInfo, _) },
 	( { RelInfo = relation_info(permanent(_), _, Indexes, _) } ->
@@ -512,9 +533,15 @@
 			(
 				map__set(SpecMap0, index(Index),
 					sort_req(definite, BlockIds), SpecMap)
-			)), Indexes, Specs0, Specs) },
+			)), Indexes, Specs0, Specs1) },
+		{ map__to_assoc_list(Specs1, SpecAL1) },
+		{ list__filter(SpecFilter, SpecAL1, SpecAL) },
+		{ map__from_assoc_list(SpecAL, Specs) },
 		rl_sort__add_relation_sortedness_map(Specs, Relation1)
-	; { map__search(RelMap0, Relation2, Specs) } ->
+	; { map__search(RelMap0, Relation2, Specs0) } ->
+		{ map__to_assoc_list(Specs0, SpecAL0) },
+		{ list__filter(SpecFilter, SpecAL0, SpecAL) },
+		{ map__from_assoc_list(SpecAL, Specs) },
 		rl_sort__add_relation_sortedness_map(Specs, Relation1)
 	;
 		[]
@@ -533,22 +560,21 @@
 	{ map__from_assoc_list(Specs0, Specs) },
 	rl_sort__add_relation_sortedness_map(Specs, Output).
 
-:- pred rl_sort__assign_indexing(relation_id::in, relation_id::in,
-		sort_info::in, sort_info::out) is det.
+:- pred rl_sort__assign_indexing(block_id::in, relation_id::in,
+		relation_id::in, sort_info::in, sort_info::out) is det.
 
-rl_sort__assign_indexing(Output, Input) -->
-	=(sort_info(sortedness(RelMap0, _VarMap0), _, _)),
-	( { map__search(RelMap0, Input, Specs0) } ->
-		{ map__to_assoc_list(Specs0, Specs1) },
-		{ list__filter(
-			lambda([SpecAndReq::in] is semidet, (
-				SpecAndReq = index(_) - _
-			)), Specs1, Specs2) },
-		{ map__from_assoc_list(Specs2, Specs) },
-		rl_sort__add_relation_sortedness_map(Specs, Output)
-	;
-		[]
-	).
+rl_sort__assign_indexing(BlockId, Output, Input) -->
+	{ FilterSpecs = (pred((index(_) - _)::in) is semidet) },
+	rl_sort__assign_sortedness_and_indexing(FilterSpecs,
+		BlockId, Output, Input).
+
+:- pred rl_sort__assign_sortedness(block_id::in, relation_id::in,
+		relation_id::in, sort_info::in, sort_info::out) is det.
+
+rl_sort__assign_sortedness(BlockId, Output, Input) -->
+	{ FilterSpecs = (pred((sort(_) - _)::in) is semidet) },
+	rl_sort__assign_sortedness_and_indexing(FilterSpecs,
+		BlockId, Output, Input).
 
 :- pred rl_sort__unset_relation(relation_id::in, 
 		sort_info::in, sort_info::out) is det.
@@ -643,7 +669,7 @@
 rl_sort__instr_needed(BlockId, insert(UoOutput, DiInput, _, InsertType, _) - _)
 		-->
 	( { InsertType = index(Index) } ->
-		rl_sort__assign_indexing(DiInput, UoOutput),
+		rl_sort__assign_indexing(BlockId, DiInput, UoOutput),
 		rl_sort__add_relation_sortedness(BlockId,
 			index(Index), DiInput)
 	;
@@ -651,17 +677,17 @@
 	).
 rl_sort__instr_needed(BlockId,
 		union_diff(UoOutput, DiInput, _, _, Index, _) - _) -->
-	rl_sort__assign_indexing(DiInput, UoOutput),
+	rl_sort__assign_indexing(BlockId, DiInput, UoOutput),
 	rl_sort__add_relation_sortedness(BlockId, index(Index), DiInput).
 rl_sort__instr_needed(_BlockId, sort(_Output, _Input, _Attrs) - _) --> [].
 rl_sort__instr_needed(BlockId, ref(Output, Input) - _) -->
-	rl_sort__assign_relation_sortedness(BlockId, Input, Output).
+	rl_sort__assign_sortedness_and_indexing(BlockId, Input, Output).
 rl_sort__instr_needed(BlockId, copy(Output, Input) - _) -->
 	{ Output = output_rel(OutputRel, _) },
-	rl_sort__assign_relation_sortedness(BlockId, Input, OutputRel).
+	rl_sort__assign_sortedness(BlockId, Input, OutputRel).
 rl_sort__instr_needed(BlockId, make_unique(Output, Input) - _) -->
 	{ Output = output_rel(OutputRel, _) },
-	rl_sort__assign_relation_sortedness(BlockId, Input, OutputRel).
+	rl_sort__assign_sortedness(BlockId, Input, OutputRel).
 rl_sort__instr_needed(_BlockId, init(_Output) - _) --> [].
 rl_sort__instr_needed(_BlockId, insert_tuple(_, _, _) - _) --> [].
 rl_sort__instr_needed(_BlockId, call(_, _Inputs, _Outputs, _) - _) --> [].
@@ -772,12 +798,12 @@
 	{ Output = output_rel(OutputRel, _) },
 	rl_sort__add_relation_sortedness(BlockId, sort(SortSpec), OutputRel),
 	rl_sort__handle_output_indexing(BlockId, Output).
-rl_sort__instr_avail(_, insert(UoOutput, DiInput, _Input, _Type, _) - _)
+rl_sort__instr_avail(BlockId, insert(UoOutput, DiInput, _Input, _Type, _) - _)
 		-->
-	rl_sort__assign_indexing(UoOutput, DiInput).
+	rl_sort__assign_indexing(BlockId, UoOutput, DiInput).
 rl_sort__instr_avail(BlockId,
 		union_diff(UoOutput, DiInput, _Input1, Diff, _, _) - _) -->
-	rl_sort__assign_indexing(UoOutput, DiInput),
+	rl_sort__assign_indexing(BlockId, UoOutput, DiInput),
 	rl_sort__handle_output_indexing(BlockId, Diff).
 rl_sort__instr_avail(BlockId, sort(Output, _Input, Attrs) - _) -->
 	{ Output = output_rel(OutputRel, _) },
@@ -785,14 +811,14 @@
 		sort(attributes(Attrs)), OutputRel),
 	rl_sort__handle_output_indexing(BlockId, Output).
 rl_sort__instr_avail(BlockId, ref(Output, Input) - _) -->
-	rl_sort__assign_relation_sortedness(BlockId, Output, Input).
+	rl_sort__assign_sortedness_and_indexing(BlockId, Output, Input).
 rl_sort__instr_avail(BlockId, copy(Output, Input) - _) -->
 	{ Output = output_rel(OutputRel, _) },
-	rl_sort__assign_relation_sortedness(BlockId, OutputRel, Input),
+	rl_sort__assign_sortedness(BlockId, OutputRel, Input),
 	rl_sort__handle_output_indexing(BlockId, Output).
 rl_sort__instr_avail(BlockId, make_unique(Output, Input) - _) -->
 	{ Output = output_rel(OutputRel, _) },
-	rl_sort__assign_relation_sortedness(BlockId, OutputRel, Input),
+	rl_sort__assign_sortedness(BlockId, OutputRel, Input),
 	rl_sort__handle_output_indexing(BlockId, Output).
 rl_sort__instr_avail(BlockId, init(Output) - _) -->
 	rl_sort__handle_output_indexing(BlockId, Output).

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