[m-dev.] diff: more optimization of Aditi joins and subtracts
Simon Taylor
stayl at cs.mu.OZ.AU
Wed Mar 1 12:05:48 AEDT 2000
Estimated hours taken: 25
More optimization of Aditi joins and subtracts.
compiler/rl.m:
Add predicates to detect trivial subtracts -- subtracts
for which the condition doesn't use one of the input tuples.
compiler/rl_sort.m:
Introduce index and hash subtract operations.
Improve the handling of trivial joins and subtracts
which can just pass one of their input relations
to the output, so that following instructions can make
use of any indexing on the passed through input relation.
compiler/rl_relops.m:
compiler/rl_block_opt.m:
Detect trivial- and semi-joins and trivial subtracts when
the instructions are generated in rl_relops.m, rather
than in rl_block_opt.m -- these should be detected regardless
of whether the more complex optimizations are being performed.
compiler/rl_code.m:
The indexed instructions now take a parameter describing
whether the key ranges are open or closed -- all key ranges
currently generated by the compiler are closed.
Increment the RL bytecode version number.
compiler/rl_block.m:
Don't assume the output of map__keys is sorted --
use map__sorted_keys instead.
compiler/rl_dump.m:
Write out information about trivial subtracts.
compiler/rl_key.m:
Fix the handling of unbounded key ranges.
compiler/rl_out.pp:
Generate trivial, index and hash subtracts.
Don't optimize away unneeded projects here --
they should be removed (or not generated) earlier.
compiler/rl_stream.m:
Fix the handling of trivial joins and subtracts
which can create aliases of one of their input
relations.
Index: rl.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl.m,v
retrieving revision 1.9
diff -u -u -r1.9 rl.m
--- rl.m 2000/02/22 02:55:30 1.9
+++ rl.m 2000/02/29 04:47:00
@@ -136,7 +136,8 @@
relation_id, % input 1
relation_id, % input 2
subtract_type,
- rl_goal % subtraction condition
+ rl_goal, % subtraction condition
+ maybe(trivial_subtract_info)
)
;
% A difference is just a special case of subtract.
@@ -219,7 +220,7 @@
% Make a copy of the input relation, making sure the
% output has the given set of indexes.
% This could be a bit slow, because the system can't just
- % copy the files, but has to do a full
+ % copy the files, but has to do a full tuple-by-tuple copy.
copy(
output_rel, % output
relation_id % input
@@ -336,26 +337,52 @@
% Output = join(Input1, Input2, Cond), where Cond does
% not depend on Input2, can be generated as:
%
- % if (empty(Input2)) {
- % Output = project(Input1, Cond)
- % else {
- % init(Output)
- % }
+ % if (empty(Input2)) {
+ % Output = project(Input1, Cond)
+ % } else {
+ % init(Output)
+ % }
%
% If the join is a semi-join with a deterministic
% condition, the project is not necessary.
%
+ % Subtracts are similar.
+ %
+ % Output = semi_subtract(Input1, Input2, Cond).
+ %
+ % If Cond does not depend on Input1, this can be generated
+ % as:
+ %
+ % if (empty(select(Input2, Cond))) {
+ % Output = Input1
+ % } else {
+ % init(Output)
+ % }
+ %
+ % If Cond does not depend on Input2, this can be generated
+ % as:
+ %
+ % if (empty(Input2)) {
+ % Output = Input1
+ % } else {
+ % Output = select(Input1, not(Cond))
+ % }
+ %
+ %
% We don't just do this optimization in the intermediate RL
% because it introduces extra branching which can interfere
% with other optimizations (e.g. rl_block_opt.m, rl_stream.m).
-:- type trivial_join_info
- ---> trivial_join_info(
+:- type trivial_join_or_subtract_info
+ ---> trivial_join_or_subtract_info(
tuple_num, % which tuple does the join depend on
maybe(project_type)
- % the type of projection to use,
+ % the type of selection/projection to use,
% if one is needed
).
+:- type trivial_join_info == trivial_join_or_subtract_info.
+:- type trivial_subtract_info == trivial_join_or_subtract_info.
+
% All subtracts are done using the semi-subtract operator.
% There is no advantage in including any post projection
% in the operation because the projection cannot use any
@@ -490,9 +517,26 @@
:- pred rl__is_semi_join(join_type::in, rl_goal::in,
maybe(semi_join_info)::out) is det.
+
+ % See the comment on type trivial_join_or_subtract_info.
+:- pred rl__is_trivial_join(module_info::in, join_type::in,
+ rl_goal::in, maybe(semi_join_info)::in,
+ maybe(trivial_join_info)::out) is det.
+
+ % See the comment on type trivial_join_or_subtract_info.
+:- pred rl__is_trivial_subtract(module_info::in, subtract_type::in,
+ rl_goal::in, maybe(trivial_subtract_info)::out) is det.
+
+ % Find the project type which is equivalent to the join type,
+ % useful for a trivial join which can be converted into a projection.
+:- pred rl__join_type_to_project_type(join_type::in,
+ maybe(project_type)::out) is det.
-:- pred rl__is_trivial_join(module_info::in, join_type::in, rl_goal::in,
- maybe(semi_join_info)::in, maybe(trivial_join_info)::out) is det.
+ % Find the project type which is equivalent to the subtract type.
+ % useful for a trivial subtract which can be converted into a
+ % projection.
+:- pred rl__subtract_type_to_project_type(subtract_type::in,
+ maybe(project_type)::out) is det.
% Succeed if the goal contain any of the variables corresponding
% to the attributes of the given input tuple.
@@ -604,7 +648,7 @@
join(output_rel(Output, _), Input1, Input2, _, _, _, _) - _,
[Input1, Input2], [Output]).
rl__instr_relations(subtract(output_rel(Output, _),
- Input1, Input2, _, _) - _, [Input1, Input2], [Output]).
+ Input1, Input2, _, _, _) - _, [Input1, Input2], [Output]).
rl__instr_relations(difference(output_rel(Output, _),
Input1, Input2, _) - _, [Input1, Input2], [Output]).
rl__instr_relations(project(OutputRel,
@@ -717,27 +761,57 @@
rl__is_trivial_join(ModuleInfo, JoinType, Cond,
SemiJoinInfo, TrivialJoinInfo) :-
(
- join_type_to_project_type(JoinType, yes(ProjectType))
+ rl__join_type_to_project_type(JoinType, yes(ProjectType))
->
- ( rl__goal_is_independent_of_input(one, Cond) ->
- rl__make_trivial_join_info(ModuleInfo, ProjectType,
- Cond, two, SemiJoinInfo, TrivialJoinInfo)
- ; rl__goal_is_independent_of_input(two, Cond) ->
- rl__make_trivial_join_info(ModuleInfo, ProjectType,
- Cond, one, SemiJoinInfo, TrivialJoinInfo)
- ;
- TrivialJoinInfo = no
- )
+ rl__is_trivial_join_or_subtract(ModuleInfo, join,
+ ProjectType, Cond, SemiJoinInfo, TrivialJoinInfo)
;
TrivialJoinInfo = no
).
-:- pred rl__make_trivial_join_info(module_info::in, project_type::in,
- rl_goal::in, tuple_num::in, maybe(semi_join_info)::in,
- maybe(trivial_join_info)::out) is det.
+rl__is_trivial_subtract(ModuleInfo, SubtractType, Cond, TrivialSubtractInfo) :-
+ (
+ rl__subtract_type_to_project_type(SubtractType,
+ yes(ProjectType))
+ ->
+ % Subtracts always return the first input tuple.
+ SemiJoinInfo = yes(one),
+ rl__is_trivial_join_or_subtract(ModuleInfo, subtract,
+ ProjectType, Cond, SemiJoinInfo, TrivialSubtractInfo)
+ ;
+ TrivialSubtractInfo = no
+ ).
-rl__make_trivial_join_info(ModuleInfo, ProjectType,
- Cond, TupleNum, SemiJoin, TrivialJoinInfo) :-
+:- type join_or_subtract
+ ---> join
+ ; subtract
+ .
+
+:- pred rl__is_trivial_join_or_subtract(module_info::in, join_or_subtract::in,
+ project_type::in, rl_goal::in, maybe(semi_join_info)::in,
+ maybe(trivial_join_or_subtract_info)::out) is det.
+
+rl__is_trivial_join_or_subtract(ModuleInfo, JoinOrSubtract, ProjectType, Cond,
+ SemiJoinInfo, TrivialJoinInfo) :-
+ ( rl__goal_is_independent_of_input(one, Cond) ->
+ rl__make_trivial_join_or_subtract_info(ModuleInfo,
+ JoinOrSubtract, ProjectType, Cond, two, SemiJoinInfo,
+ TrivialJoinInfo)
+ ; rl__goal_is_independent_of_input(two, Cond) ->
+ rl__make_trivial_join_or_subtract_info(ModuleInfo,
+ JoinOrSubtract, ProjectType, Cond, one,
+ SemiJoinInfo, TrivialJoinInfo)
+ ;
+ TrivialJoinInfo = no
+ ).
+
+:- pred rl__make_trivial_join_or_subtract_info(module_info::in,
+ join_or_subtract::in, project_type::in, rl_goal::in,
+ tuple_num::in, maybe(semi_join_info)::in,
+ maybe(trivial_join_or_subtract_info)::out) is det.
+
+rl__make_trivial_join_or_subtract_info(ModuleInfo, JoinOrSubtract, ProjectType,
+ Cond, UsedTupleNum, SemiJoin, TrivialJoinInfo) :-
Goals = Cond ^ goal,
(
@@ -746,6 +820,18 @@
% deterministic conditions.
%
SemiJoin = yes(_),
+ \+ (
+ % For this type of trivial subtract,
+ % the selection will use the negation
+ % of the condition, which will pretty
+ % much always be semidet.
+ % The select can only be removed if the
+ % condition has determinism failure, in
+ % which case the negation should have been
+ % removed earlier.
+ JoinOrSubtract = subtract,
+ UsedTupleNum = one
+ ),
rl__goal_can_be_removed(ModuleInfo, Goals)
->
MaybeProjectType = no
@@ -753,7 +839,38 @@
MaybeProjectType = yes(ProjectType)
),
- TrivialJoinInfo = yes(trivial_join_info(TupleNum, MaybeProjectType)).
+ TrivialJoinInfo =
+ yes(trivial_join_or_subtract_info(UsedTupleNum,
+ MaybeProjectType)).
+
+ % Check whether a projection is needed.
+ % A projection is not needed if it is a selection
+ % (there is no output tuple) and the selection condition
+ % is deterministic.
+:- pred rl__is_removeable_project(module_info::in, project_type::in,
+ rl_goal::in, bool::out) is det.
+
+rl__is_removeable_project(ModuleInfo, ProjectType, RLGoal, IsRemoveable) :-
+ (
+ ProjectType = filter,
+ (
+ \+ rl__goal_produces_tuple(RLGoal),
+ Goals = RLGoal ^ goal,
+
+ rl__goal_can_be_removed(ModuleInfo, Goals)
+ ->
+ IsRemoveable = yes
+ ;
+ IsRemoveable = no
+ )
+ ;
+ %
+ % Indexed projections contain a selection
+ % which must always be performed.
+ %
+ ProjectType = index(_, _),
+ IsRemoveable = no
+ ).
rl__goal_can_be_removed(ModuleInfo, Goals) :-
goal_list_determinism(Goals, Detism),
@@ -763,6 +880,10 @@
module_info_globals(ModuleInfo, Globals),
globals__lookup_bool_option(Globals, fully_strict, FullyStrict),
+ % I'm not sure whether this test is actually worthwhile --
+ % the optimization passes which introduce index, sort-merge
+ % and hash joins and subtracts prune away large chunks of
+ % computation without caring about the semantics.
(
FullyStrict = no
;
@@ -773,12 +894,11 @@
)
).
-:- pred join_type_to_project_type(join_type::in,
- maybe(project_type)::out) is det.
-
-join_type_to_project_type(nested_loop, yes(filter)).
-join_type_to_project_type(index(IndexSpec, KeyRange),
- yes(index(IndexSpec, KeyRange))).
+rl__join_type_to_project_type(nested_loop, yes(filter)).
+rl__join_type_to_project_type(index(IndexSpec, KeyRange0),
+ yes(index(IndexSpec, KeyRange))) :-
+ join_key_range_to_project_key_range(KeyRange0, KeyRange).
+
%
% Introducing sort-merge and hash joins means that there is a
% connection between the arguments of the two input tuples, so
@@ -786,6 +906,28 @@
%
join_type_to_project_type(sort_merge(_, _), no).
join_type_to_project_type(hash(_, _), no).
+
+
+subtract_type_to_project_type(semi_nested_loop, yes(filter)).
+subtract_type_to_project_type(semi_index(IndexSpec, KeyRange0),
+ yes(index(IndexSpec, KeyRange))) :-
+ join_key_range_to_project_key_range(KeyRange0, KeyRange).
+
+ %
+ % Introducing sort-merge and hash subtracts means that there is a
+ % connection between the arguments of the two input tuples, so
+ % the subtract cannot be turned into a projection.
+ %
+subtract_type_to_project_type(semi_sort_merge(_, _), no).
+subtract_type_to_project_type(semi_hash(_, _), no).
+
+ % The expression to create a key range for a project/select does
+ % not take an input tuple.
+:- pred join_key_range_to_project_key_range(key_range::in,
+ key_range::out) is det.
+
+join_key_range_to_project_key_range(key_range(A, B, _, D),
+ key_range(A, B, no, D)).
rl__remove_goal_input(InputNo, RLGoal0, RLGoal) :-
require(rl__goal_is_independent_of_input(InputNo, RLGoal0),
Index: rl_block.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_block.m,v
retrieving revision 1.1
diff -u -u -r1.1 rl_block.m
--- rl_block.m 1998/12/06 23:44:44 1.1
+++ rl_block.m 2000/02/23 03:50:33
@@ -599,7 +599,7 @@
relation__init(FlowGraph0),
FirstBlockId = 0,
- map__keys(RelationInfoMap, RelationIds),
+ map__sorted_keys(RelationInfoMap, RelationIds),
( list__last(RelationIds, HighestRelationId) ->
NextRelationId is HighestRelationId + 1
;
Index: rl_block_opt.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_block_opt.m,v
retrieving revision 1.5
diff -u -u -r1.5 rl_block_opt.m
--- rl_block_opt.m 2000/02/22 02:55:30 1.5
+++ rl_block_opt.m 2000/02/25 01:01:09
@@ -40,7 +40,7 @@
:- implementation.
:- import_module goal_util, hlds_goal, hlds_module, hlds_pred, inlining.
-:- import_module prog_data, rl, rl_key.
+:- import_module prog_data, rl, rl_key, globals, options.
:- import_module assoc_list, bool, int, map, multi_map.
:- import_module relation, require, set, std_util, string.
@@ -87,18 +87,21 @@
% Add an instruction to the DAG for the block.
:- pred rl_block_opt__build_dag(rl_instruction::in, dag::in, dag::out) is det.
-rl_block_opt__build_dag(
- join(Output, Input1, Input2, Type, Exprn, _, _) - _) -->
+rl_block_opt__build_dag(join(Output, Input1, Input2, Type, Exprn,
+ SemiJoin, TrivialJoin) - _) -->
rl_block_opt__lookup_relation(Input1, Input1Node),
rl_block_opt__lookup_relation(Input2, Input2Node),
rl_block_opt__add_dag_node([Output], [Input1Node, Input2Node],
- join(Input1Node, Input2Node, Type, Exprn), _).
+ join(Input1Node, Input2Node, Type, Exprn,
+ SemiJoin, TrivialJoin), _).
-rl_block_opt__build_dag(subtract(Output, Input1, Input2, Type, Exprn) - _) -->
+rl_block_opt__build_dag(subtract(Output, Input1, Input2, Type,
+ Exprn, TrivialSubtract) - _) -->
rl_block_opt__lookup_relation(Input1, Input1Node),
rl_block_opt__lookup_relation(Input2, Input2Node),
rl_block_opt__add_dag_node([Output], [Input1Node, Input2Node],
- subtract(Input1Node, Input2Node, Type, Exprn), _).
+ subtract(Input1Node, Input2Node, Type, Exprn, TrivialSubtract),
+ _).
rl_block_opt__build_dag(difference(Output, Input1, Input2, Type) - _) -->
rl_block_opt__lookup_relation(Input1, Input1Node),
@@ -507,7 +510,14 @@
dag_get_node_info_map(NodeInfoMap0),
{ NodeInfo0 = node_info(Instr, OutputRels0) },
dag_get_flags(Flags),
+ dag_get_rl_opt_info(RLInfo),
+ { rl_opt_info_get_module_info(ModuleInfo, RLInfo, _) },
+ { module_info_globals(ModuleInfo, Globals) },
+ { globals__lookup_bool_option(Globals,
+ optimize_rl_index, OptimizeIndex) },
(
+ { OptimizeIndex = yes },
+
% Look for a union and a difference which can be
% changed into a union_diff.
{ Instr = union(UnionInputLocs, _) },
@@ -1341,29 +1351,25 @@
list(rl_instruction)::out, dag::in, dag::out) is det.
rl_block_opt__generate_instr(_, NodeOutputs, NodeRels,
- join(Input1Loc, Input2Loc, JoinType, Exprn), [JoinInstr]) -->
-
- { rl__is_semi_join(JoinType, Exprn, SemiJoinInfo) },
-
- dag_get_rl_opt_info(RLOptInfo),
- { rl_opt_info_get_module_info(ModuleInfo, RLOptInfo, _) },
-
- { rl__is_trivial_join(ModuleInfo, JoinType, Exprn, SemiJoinInfo,
- TrivialJoinInfo) },
+ join(Input1Loc, Input2Loc, JoinType, Exprn,
+ SemiJoin, TrivialJoin),
+ [JoinInstr]) -->
rl_block_opt__get_relation_id(NodeRels, Input1Loc, Input1),
rl_block_opt__get_relation_id(NodeRels, Input2Loc, Input2),
{ rl_block_opt__one_output(NodeOutputs, Output) },
{ JoinInstr = join(Output, Input1, Input2, JoinType, Exprn,
- SemiJoinInfo, TrivialJoinInfo) - "" }.
+ SemiJoin, TrivialJoin) - "" }.
-
rl_block_opt__generate_instr(_, NodeOutputs, NodeRels,
- subtract(Input1Loc, Input2Loc, Type, Exprn),
- [subtract(Output, Input1, Input2, Type, Exprn) - ""]) -->
+ subtract(Input1Loc, Input2Loc, Type, Exprn, TrivialSubtract),
+ [SubtractInstr]) -->
+
rl_block_opt__get_relation_id(NodeRels, Input1Loc, Input1),
rl_block_opt__get_relation_id(NodeRels, Input2Loc, Input2),
- { rl_block_opt__one_output(NodeOutputs, Output) }.
+ { rl_block_opt__one_output(NodeOutputs, Output) },
+ { SubtractInstr = subtract(Output, Input1, Input2, Type,
+ Exprn, TrivialSubtract) - "" }.
rl_block_opt__generate_instr(_, NodeOutputs, NodeRels,
difference(Input1Loc, Input2Loc, Type),
@@ -1504,8 +1510,10 @@
% Cut down versions of the relational operations without their outputs.
:- type instr
- ---> join(output_id, output_id, join_type, rl_goal)
- ; subtract(output_id, output_id, subtract_type, rl_goal)
+ ---> join(output_id, output_id, join_type, rl_goal,
+ maybe(semi_join_info), maybe(trivial_join_info))
+ ; subtract(output_id, output_id, subtract_type, rl_goal,
+ maybe(trivial_subtract_info))
; difference(output_id, output_id, difference_type)
% The first output of a project is distinguished -
% it can be a stream, the others must all be materialised.
Index: rl_code.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_code.m,v
retrieving revision 1.9
diff -u -u -r1.9 rl_code.m
--- rl_code.m 1999/09/07 05:48:54 1.9
+++ rl_code.m 2000/02/27 23:57:44
@@ -5,7 +5,7 @@
%-----------------------------------------------------------------------------%
% Do not edit - this file was automatically generated by
% $ADITI_ROOT/src/rosi/create_rl_code_m.
-% Created Tue Sep 7 15:35:16 1999
+% Created Mon Feb 28 10:57:44 2000
%-----------------------------------------------------------------------------%
:- module rl_code.
@@ -371,27 +371,27 @@
; rl_PROC_join_nl
; rl_PROC_join_sm
; rl_PROC_join_hj
- ; rl_PROC_join_index_simple
+ ; rl_PROC_join_index_simple(int32)
; rl_PROC_join_index_complex
; rl_PROC_join_cross
; rl_PROC_semijoin_nl
; rl_PROC_semijoin_sm
; rl_PROC_semijoin_hj
- ; rl_PROC_semijoin_index
+ ; rl_PROC_semijoin_index(int32,int32)
; rl_PROC_subtract
; rl_PROC_subtract_nl
; rl_PROC_subtract_sm
; rl_PROC_subtract_hj
- ; rl_PROC_subtract_index
+ ; rl_PROC_subtract_index(int32)
; rl_PROC_subtract_cross
; rl_PROC_semisubtract_nl
; rl_PROC_semisubtract_hj
- ; rl_PROC_semisubtract_index
+ ; rl_PROC_semisubtract_index(int32)
; rl_PROC_difference
; rl_PROC_select
; rl_PROC_select_filter
- ; rl_PROC_select_index
- ; rl_PROC_btree_scan
+ ; rl_PROC_select_index(int32)
+ ; rl_PROC_btree_scan(int32)
; rl_PROC_project_tee
; rl_PROC_sort(int32)
; rl_PROC_union
@@ -1550,9 +1550,10 @@
bytecode_to_intlist(rl_PROC_join_hj, Splits) :-
int16_to_bytecode(308, I308Codes),
list__condense([I308Codes], Splits).
-bytecode_to_intlist(rl_PROC_join_index_simple, Splits) :-
+bytecode_to_intlist(rl_PROC_join_index_simple(X0int32), Splits) :-
int16_to_bytecode(309, I309Codes),
- list__condense([I309Codes], Splits).
+ int32_to_bytecode(X0int32, X0int32Codes),
+ list__condense([I309Codes,X0int32Codes], Splits).
bytecode_to_intlist(rl_PROC_join_index_complex, Splits) :-
int16_to_bytecode(310, I310Codes),
list__condense([I310Codes], Splits).
@@ -1568,9 +1569,11 @@
bytecode_to_intlist(rl_PROC_semijoin_hj, Splits) :-
int16_to_bytecode(314, I314Codes),
list__condense([I314Codes], Splits).
-bytecode_to_intlist(rl_PROC_semijoin_index, Splits) :-
+bytecode_to_intlist(rl_PROC_semijoin_index(X0int32,X1int32), Splits) :-
int16_to_bytecode(315, I315Codes),
- list__condense([I315Codes], Splits).
+ int32_to_bytecode(X0int32, X0int32Codes),
+ int32_to_bytecode(X1int32, X1int32Codes),
+ list__condense([I315Codes,X0int32Codes,X1int32Codes], Splits).
bytecode_to_intlist(rl_PROC_subtract, Splits) :-
int16_to_bytecode(316, I316Codes),
list__condense([I316Codes], Splits).
@@ -1583,9 +1586,10 @@
bytecode_to_intlist(rl_PROC_subtract_hj, Splits) :-
int16_to_bytecode(319, I319Codes),
list__condense([I319Codes], Splits).
-bytecode_to_intlist(rl_PROC_subtract_index, Splits) :-
+bytecode_to_intlist(rl_PROC_subtract_index(X0int32), Splits) :-
int16_to_bytecode(320, I320Codes),
- list__condense([I320Codes], Splits).
+ int32_to_bytecode(X0int32, X0int32Codes),
+ list__condense([I320Codes,X0int32Codes], Splits).
bytecode_to_intlist(rl_PROC_subtract_cross, Splits) :-
int16_to_bytecode(321, I321Codes),
list__condense([I321Codes], Splits).
@@ -1595,9 +1599,10 @@
bytecode_to_intlist(rl_PROC_semisubtract_hj, Splits) :-
int16_to_bytecode(323, I323Codes),
list__condense([I323Codes], Splits).
-bytecode_to_intlist(rl_PROC_semisubtract_index, Splits) :-
+bytecode_to_intlist(rl_PROC_semisubtract_index(X0int32), Splits) :-
int16_to_bytecode(324, I324Codes),
- list__condense([I324Codes], Splits).
+ int32_to_bytecode(X0int32, X0int32Codes),
+ list__condense([I324Codes,X0int32Codes], Splits).
bytecode_to_intlist(rl_PROC_difference, Splits) :-
int16_to_bytecode(325, I325Codes),
list__condense([I325Codes], Splits).
@@ -1607,12 +1612,14 @@
bytecode_to_intlist(rl_PROC_select_filter, Splits) :-
int16_to_bytecode(327, I327Codes),
list__condense([I327Codes], Splits).
-bytecode_to_intlist(rl_PROC_select_index, Splits) :-
+bytecode_to_intlist(rl_PROC_select_index(X0int32), Splits) :-
int16_to_bytecode(328, I328Codes),
- list__condense([I328Codes], Splits).
-bytecode_to_intlist(rl_PROC_btree_scan, Splits) :-
+ int32_to_bytecode(X0int32, X0int32Codes),
+ list__condense([I328Codes,X0int32Codes], Splits).
+bytecode_to_intlist(rl_PROC_btree_scan(X0int32), Splits) :-
int16_to_bytecode(329, I329Codes),
- list__condense([I329Codes], Splits).
+ int32_to_bytecode(X0int32, X0int32Codes),
+ list__condense([I329Codes,X0int32Codes], Splits).
bytecode_to_intlist(rl_PROC_project_tee, Splits) :-
int16_to_bytecode(330, I330Codes),
list__condense([I330Codes], Splits).
@@ -1733,4 +1740,4 @@
int_to_byte_list(X, List).
-rl_code__version(1, 25).
+rl_code__version(1, 26).
Index: rl_dump.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_dump.m,v
retrieving revision 1.5
diff -u -u -r1.5 rl_dump.m
--- rl_dump.m 2000/02/22 02:55:31 1.5
+++ rl_dump.m 2000/02/23 00:40:22
@@ -121,22 +121,7 @@
;
{ SemiJoinInfo = no }
),
- (
- { TrivialJoinInfo = yes(trivial_join_info(Tuple,
- MaybeProject)) },
- io__write_string(" (trivial join input "),
- io__write(Tuple),
- (
- { MaybeProject = yes(_) },
- io__write_string(" projected")
- ;
- { MaybeProject = no },
- io__write_string(" not projected")
- ),
- io__write_string(")")
- ;
- { TrivialJoinInfo = no }
- ),
+ rl_dump__write_trivial_join_or_subtract(TrivialJoinInfo),
comma,
io__nl,
rl_dump__write_goal(ModuleInfo, Exprn),
@@ -145,7 +130,8 @@
io__nl.
rl_dump__write_instruction(ModuleInfo, RelationInfo,
- subtract(Output, Input1, Input2, SubType, Exprn) - Comment) -->
+ subtract(Output, Input1, Input2, SubType,
+ Exprn, TrivialSubtractInfo) - Comment) -->
rl_dump__write_output_rel(RelationInfo, Output),
io__write_string(" = subtract("),
rl_dump__write_relation_id(RelationInfo, Input1),
@@ -154,6 +140,7 @@
comma,
rl_dump__write_subtract_type(ModuleInfo, SubType),
comma,
+ rl_dump__write_trivial_join_or_subtract(TrivialSubtractInfo),
io__nl,
rl_dump__write_goal(ModuleInfo, Exprn),
io__write_string(").\t"),
@@ -476,6 +463,28 @@
io__write_string("index("),
mercury_output_index_spec(IndexSpec),
io__write_string(")").
+
+:- pred rl_dump__write_trivial_join_or_subtract(
+ maybe(trivial_join_or_subtract_info)::in,
+ io__state::di, io__state::uo) is det.
+
+rl_dump__write_trivial_join_or_subtract(TrivialJoinInfo) -->
+ (
+ { TrivialJoinInfo = yes(trivial_join_or_subtract_info(Tuple,
+ MaybeProject)) },
+ io__write_string(" (trivial input "),
+ io__write(Tuple),
+ (
+ { MaybeProject = yes(_) },
+ io__write_string(" projected")
+ ;
+ { MaybeProject = no },
+ io__write_string(" not projected")
+ ),
+ io__write_string(")")
+ ;
+ { TrivialJoinInfo = no }
+ ).
%-----------------------------------------------------------------------------%
Index: rl_key.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_key.m,v
retrieving revision 1.5
diff -u -u -r1.5 rl_key.m
--- rl_key.m 2000/02/22 02:55:31 1.5
+++ rl_key.m 2000/02/28 03:55:18
@@ -187,47 +187,57 @@
assoc_list(int, key_term)::in, bounding_tuple::out) is det.
rl_key__convert_bound(MaybeArgs, Tuple, Bound) :-
+ assoc_list__keys(Tuple, Indexes),
+ assoc_list__values(Tuple, Terms),
+ SeenInfinity0 = no,
+ list__map_foldl(rl_key__convert_key_attr(MaybeArgs),
+ Terms, Attrs, SeenInfinity0, SeenInfinity),
+
+ % If there is an attribute of the key tuple which is
+ % not constrained either by a test against the arguments
+ % of the other input tuple, or by a test against
+ % a constructor, treat the entire bound as infinity.
+ % XXX this is temporary, until Aditi supports infinities
+ % within bounds tuples.
(
- % XXX this is temporary, until Aditi supports infinities
- % within bounds tuples.
- (
- list__member(Attr, Tuple),
- (
- MaybeArgs = no,
- Attr = _ - (var - _)
- ;
- MaybeArgs = yes(Args),
- Attr = _ - (var - Vars),
- \+ (
- set__member(Var, Vars),
- list__member(Var, Args)
- )
- )
- )
+ SeenInfinity = yes
->
Bound = infinity
;
- list__member(Attr, Tuple),
- \+ (
- MaybeArgs = yes(Args),
- Attr = _ - (var - Vars),
- set__member(Var, Vars),
- list__member(Var, Args)
- )
+ % If all attributes are infinity, the entire bound is just
+ % infinity.
+ Attrs = [KeyAttr | _],
+ KeyAttr = infinity
->
- assoc_list__keys(Tuple, Indexes),
- assoc_list__values(Tuple, Terms),
- list__map(rl_key__convert_key_attr(MaybeArgs), Terms, Attrs),
+ Bound = infinity
+ ;
assoc_list__from_corresponding_lists(Indexes, Attrs, KeyTuple),
Bound = bound(KeyTuple)
- ;
- Bound = infinity
).
:- pred rl_key__convert_key_attr(maybe(list(prog_var))::in,
- key_term::in, key_attr::out) is det.
+ key_term::in, key_attr::out, bool::in, bool::out) is det.
+
+rl_key__convert_key_attr(MaybeArgs, KeyTerm, KeyAttr,
+ SeenInfinity0, SeenInfinity) :-
+ (
+ % As soon as we've seen one infinity in the key tuple,
+ % the remaining attributes can't affect the result of
+ % the comparison in a B-tree search.
+ SeenInfinity0 = yes,
+ KeyAttr = infinity,
+ SeenInfinity = yes
+ ;
+ SeenInfinity0 = no,
+ rl_key__convert_key_attr_2(MaybeArgs, KeyTerm,
+ KeyAttr, SeenInfinity)
+ ).
+
+:- pred rl_key__convert_key_attr_2(maybe(list(prog_var))::in,
+ key_term::in, key_attr::out, bool::out) is det.
-rl_key__convert_key_attr(MaybeArgs, var - Vars, Attr) :-
+rl_key__convert_key_attr_2(MaybeArgs, var - Vars, Attr,
+ SeenInfinity) :-
(
MaybeArgs = yes(Args),
set__list_to_set(Args, ArgSet),
@@ -235,13 +245,17 @@
set__to_sorted_list(Intersection, [Arg | _]),
list__nth_member_search(Args, Arg, Index)
->
- Attr = input_field(Index)
+ Attr = input_field(Index),
+ SeenInfinity = no
;
- Attr = infinity
+ Attr = infinity,
+ SeenInfinity = yes
).
-rl_key__convert_key_attr(MaybeArgs, functor(ConsId, Type, Terms) - _,
- functor(ConsId, Type, Attrs)) :-
- list__map(rl_key__convert_key_attr(MaybeArgs), Terms, Attrs).
+rl_key__convert_key_attr_2(MaybeArgs, functor(ConsId, Type, Terms) - _,
+ functor(ConsId, Type, Attrs), SeenInfinity) :-
+ SeenInfinity0 = no,
+ list__map_foldl(rl_key__convert_key_attr(MaybeArgs),
+ Terms, Attrs, SeenInfinity0, SeenInfinity).
:- pred rl_key__split_key_tuples(assoc_list(int, pair(key_term))::in,
assoc_list(int, key_term)::out, assoc_list(int, key_term)::out) is det.
Index: rl_out.pp
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_out.pp,v
retrieving revision 1.10
diff -u -u -r1.10 rl_out.pp
--- rl_out.pp 2000/02/22 02:55:32 1.10
+++ rl_out.pp 2000/02/28 05:24:45
@@ -59,7 +59,7 @@
:- import_module code_util, hlds_data, hlds_pred, prog_data, prog_out.
:- import_module llds, globals, options, rl_code, tree, type_util, passes_aux.
:- import_module rl_file, getopt, modules, prog_util, magic_util, hlds_goal.
-:- import_module code_aux.
+:- import_module code_aux, det_analysis, instmap.
#if INCLUDE_ADITI_OUTPUT % See ../Mmake.common.in.
:- import_module rl_exprn.
@@ -560,38 +560,13 @@
rl_out__generate_instr(join(Output, Input1, Input2, Type, Cond,
SemiJoin, TrivialJoin) - _, Code) -->
rl_out__generate_join(Output, Input1, Input2, Type,
- SemiJoin, TrivialJoin, Cond, Code).
-
-rl_out__generate_instr(subtract(Output, Input1, Input2, Type, Cond) - _,
+ Cond, SemiJoin, TrivialJoin, Code).
+rl_out__generate_instr(
+ subtract(Output, Input1, Input2,
+ Type, Cond, TrivialSubtract) - _,
Code) -->
- rl_out__generate_stream(Input1, Stream1Code),
- rl_out__generate_stream(Input2, Stream2Code),
- rl_out_info_get_output_relation_schema_offset(Output,
- OutputSchemaOffset),
- rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
- (
- { Type = semi_nested_loop },
- { SubtractCode = rl_PROC_semisubtract_nl }
- ;
- { Type = semi_sort_merge(_, _) },
- { error(
- "rl_out__generate_instr: subtract_sm not yet implemented") }
- ;
- { Type = semi_hash(_, _) },
- { error(
- "rl_out__generate_instr: subtract_hash not yet implemented") }
- ;
- { Type = semi_index(_IndexSpec, _) },
- { error(
- "rl_out__generate_instr: subtract_index not yet implemented") }
- ),
- { InstrCode =
- tree(node([SubtractCode]),
- tree(Stream1Code,
- tree(Stream2Code,
- node([rl_PROC_expr(CondExprn)])
- ))) },
- rl_out__generate_stream_instruction(Output, InstrCode, Code).
+ rl_out__generate_subtract(Output, Input1, Input2, Type,
+ Cond, TrivialSubtract, Code).
rl_out__generate_instr(difference(Output, Input1, Input2, Type) - _,
Code) -->
rl_out__generate_stream(Input1, Stream1Code),
@@ -810,12 +785,12 @@
%-----------------------------------------------------------------------------%
:- pred rl_out__generate_join(output_rel::in, relation_id::in,
- relation_id::in, join_type::in, maybe(semi_join_info)::in,
- maybe(trivial_join_info)::in, rl_goal::in, byte_tree::out,
+ relation_id::in, join_type::in, rl_goal::in, maybe(semi_join_info)::in,
+ maybe(trivial_join_info)::in, byte_tree::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out__generate_join(Output, Input1a, Input2a, JoinType0, MaybeSemiJoin,
- MaybeTrivialJoin, Cond0, Code) -->
+rl_out__generate_join(Output, Input1a, Input2a, JoinType0, Cond0,
+ MaybeSemiJoin, MaybeTrivialJoin, Code) -->
%
% Work out the bytecode to use for the join, and whether the
% join is actually a semi-join.
@@ -861,8 +836,8 @@
%
(
{ MaybeTrivialJoin = yes(TrivialJoinInfo) },
- { TrivialJoinInfo = trivial_join_info(ProjectTupleNum0,
- MaybeProjectType) },
+ { TrivialJoinInfo = trivial_join_or_subtract_info(
+ ProjectTupleNum0, MaybeProjectType) },
{
SwapInputs = yes,
rl__swap_tuple_num(ProjectTupleNum0, ProjectTupleNum)
@@ -901,7 +876,7 @@
rl_out__generate_ite(CondCode, ThenCode, ElseCode, Code)
;
{ MaybeTrivialJoin = no },
- rl_out__generate_join_2(Output, Input1, Input2,
+ rl_out__generate_join_or_subtract(Output, Input1, Input2,
JoinType, JoinBytecode, Cond, Code)
).
@@ -922,10 +897,25 @@
rl_out__compute_join_bytecode(hash(_, _), yes(Tuple),
rl_PROC_semijoin_hj, Swap) :-
rl_out__should_swap_inputs(Tuple, Swap).
+
+rl_out__compute_join_bytecode(index(_, _), no,
+ rl_PROC_join_index_simple(IndexRangeTypes), no) :-
-rl_out__compute_join_bytecode(index(_, _), no, rl_PROC_join_index_simple, no).
+ % both ends of the key range are closed.
+ % XXX we should detect and use open ranges
+ IndexRangeTypes = 0.
+
rl_out__compute_join_bytecode(index(_, _), yes(Tuple),
- rl_PROC_semijoin_index, no) :-
+ rl_PROC_semijoin_index(Output, IndexRangeTypes), no) :-
+
+ % The tuple from the non-indexed relation is returned --
+ % returning the tuple from the index relation is not
+ % yet implemented in Aditi.
+ Output = 0,
+
+ % both ends of the key range are closed.
+ % XXX we should detect and use open ranges
+ IndexRangeTypes = 0,
require(unify(Tuple, one),
"indexed semi_join doesn't return first tuple").
@@ -934,16 +924,142 @@
rl_out__should_swap_inputs(one, no).
rl_out__should_swap_inputs(two, yes).
+
+%-----------------------------------------------------------------------------%
+
+:- pred rl_out__generate_subtract(output_rel::in, relation_id::in,
+ relation_id::in, subtract_type::in, rl_goal::in,
+ maybe(trivial_subtract_info)::in, byte_tree::out,
+ rl_out_info::in, rl_out_info::out) is det.
+
+rl_out__generate_subtract(Output, Input1, Input2, Type,
+ Cond, TrivialSubtract, Code) -->
+ (
+ { TrivialSubtract = yes(
+ trivial_join_or_subtract_info(TupleNum, MaybeProject)) },
+ (
+ { TupleNum = one },
+ % Output = subtract(Input1, Input2, Cond),
+ % where Cond is independent of input two,
+ % is generated as:
+ %
+ % if (empty(Input2)) {
+ % Output = Input1
+ % else {
+ % Output = select(Input1, not(Cond))
+ % }
+ (
+ { MaybeProject = yes(ProjectType) },
+ { rl__remove_goal_input(two, Cond, ProjectCond0) },
+ { Goals0 = ProjectCond0 ^ goal },
+ { goal_list_nonlocals(Goals0, NonLocals) },
+ { goal_list_determinism(Goals0, Detism0) },
+ { det_negation_det(Detism0, MaybeDetism) },
+ { MaybeDetism = yes(NegDetism0) ->
+ NegDetism = NegDetism0
+ ;
+ % This should probably never happen,
+ % but semidet is a safe approximation.
+ NegDetism = semidet
+ },
+ { instmap_delta_init_reachable(IMDelta) },
+ { goal_info_init(NonLocals, IMDelta, Detism0,
+ GoalInfo) },
+ { conj_list_to_goal(Goals0, GoalInfo, Conj) },
+ { goal_info_init(NonLocals, IMDelta, NegDetism,
+ NegGoalInfo) },
+ { NegGoal = not(Conj) - NegGoalInfo },
+ { ProjectCond = ProjectCond0 ^ goal := [NegGoal] },
+ { ProjectInstr = project(Output, Input1,
+ ProjectCond, [], ProjectType) - "" },
+ rl_out__generate_instr(ProjectInstr, ElseCode)
+ ;
+ { MaybeProject = no },
+ % The selection is not removed by
+ % rl__is_trivial_subtract in this case.
+ { error(
+ "rl_out__generate_subtract: trivial subtract without select") }
+ ),
+
+ rl_out__generate_stream(Input2, InputStream2Code),
+ { CondCode = tree(node([rl_PROC_empty]), InputStream2Code) },
+ rl_out__generate_instr(init(Output) - "", ThenCode),
+ rl_out__generate_ite(CondCode, ThenCode, ElseCode, Code)
+ ;
+ { TupleNum = two },
+ % Output = subtract(Input1, Input2, Cond),
+ % where Cond is independent of input one,
+ % is generated as:
+ %
+ % if (empty(select(Input2, Cond))) {
+ % Output = Input1
+ % else {
+ % init(Output)
+ % }
+
+ (
+ { MaybeProject = yes(ProjectType) },
+ { rl__remove_goal_input(one, Cond, ProjectCond) },
-:- pred rl_out__generate_join_2(output_rel::in, relation_id::in,
+ rl_out_info_get_relation_schema(Input2, Input2Schema),
+ rl_out_info_add_temporary_relation(Input2Schema,
+ stream, TmpRel),
+ { ProjectInstr = project(output_rel(TmpRel, []),
+ Input2, ProjectCond, [], ProjectType) - "" },
+ rl_out__generate_instr(ProjectInstr, ProjectCode),
+ { ProjectRel = TmpRel }
+ ;
+ { MaybeProject = no },
+ { ProjectRel = Input2 },
+ { ProjectCode = empty }
+ ),
+ rl_out__generate_stream(ProjectRel, ProjectStreamCode),
+ { CondCode = tree(node([rl_PROC_empty]), ProjectStreamCode) },
+ rl_out__maybe_materialise(Output, Input1, ThenCode),
+ rl_out__generate_instr(init(Output) - "", ElseCode),
+
+ rl_out__generate_ite(CondCode, ThenCode, ElseCode, ITECode),
+ { Code = tree(ProjectCode, ITECode) }
+ )
+ ;
+ { TrivialSubtract = no },
+ { rl_out__compute_subtract_bytecode(Type, SubtractBytecode,
+ JoinType) },
+ rl_out__generate_join_or_subtract(Output, Input1, Input2,
+ JoinType, SubtractBytecode, Cond, Code)
+ ).
+
+ % Work out which bytecode to use, and which join type
+ % uses the same instruction format.
+:- pred rl_out__compute_subtract_bytecode(subtract_type::in, bytecode::out,
+ join_type::out) is det.
+
+rl_out__compute_subtract_bytecode(semi_nested_loop, rl_PROC_semisubtract_nl,
+ nested_loop).
+rl_out__compute_subtract_bytecode(semi_sort_merge(_, _), _, _) :-
+ error(
+ "rl_out__compute_subtract_bytecode: subtract_sm not yet implemented").
+rl_out__compute_subtract_bytecode(semi_hash(Attrs1, Attrs2),
+ rl_PROC_semisubtract_hj, hash(Attrs1, Attrs2)).
+rl_out__compute_subtract_bytecode(semi_index(IndexSpec, KeyRange),
+ rl_PROC_semisubtract_index(IndexRangeTypes),
+ index(IndexSpec, KeyRange)) :-
+
+ % both ends of the key range are closed.
+ % XXX we should detect and use open ranges
+ IndexRangeTypes = 0.
+
+%-----------------------------------------------------------------------------%
+
+:- pred rl_out__generate_join_or_subtract(output_rel::in, relation_id::in,
relation_id::in, join_type::in, bytecode::in,
rl_goal::in, byte_tree::out, rl_out_info::in, rl_out_info::out) is det.
-rl_out__generate_join_2(Output, Input1, Input2, JoinType,
+rl_out__generate_join_or_subtract(Output, Input1, Input2, JoinType,
JoinBytecode, Cond, Code) -->
(
{ JoinType = nested_loop },
- rl_out__generate_join_3(JoinBytecode, Output,
+ rl_out__generate_join_or_subtract_2(JoinBytecode, Output,
Input1, Input2, [], Cond, Code)
;
{ JoinType = hash(Attrs1, Attrs2) },
@@ -955,7 +1071,7 @@
%
rl_out__generate_hash_exprn(Input1, Attrs1, HashExprn1),
rl_out__generate_hash_exprn(Input2, Attrs2, HashExprn2),
- rl_out__generate_join_3(JoinBytecode, Output,
+ rl_out__generate_join_or_subtract_2(JoinBytecode, Output,
Input1, Input2, [HashExprn1, HashExprn2], Cond, Code)
;
{ JoinType = sort_merge(Spec1, Spec2) },
@@ -968,7 +1084,7 @@
% XXX We should strip out the parts of the join
% condition which are already tested by the CompareExprns.
%
- rl_out__generate_join_3(JoinBytecode, Output,
+ rl_out__generate_join_or_subtract_2(JoinBytecode, Output,
Input1, Input2, [CompareExprn],
Cond, Code)
;
@@ -998,12 +1114,12 @@
rl_out__generate_stream_instruction(Output, InstrCode, Code)
).
-:- pred rl_out__generate_join_3(bytecode::in, output_rel::in,
+:- pred rl_out__generate_join_or_subtract_2(bytecode::in, output_rel::in,
relation_id::in, relation_id::in,
list(int)::in, rl_goal::in, byte_tree::out,
rl_out_info::in, rl_out_info::out) is det.
-rl_out__generate_join_3(JoinCode, Output, Input1, Input2,
+rl_out__generate_join_or_subtract_2(JoinCode, Output, Input1, Input2,
ExtraExprns, Cond, Code) -->
rl_out_info_get_output_relation_schema_offset(Output,
OutputSchemaOffset),
@@ -1038,24 +1154,14 @@
% the projection is actually a selection.
%
{ rl__goal_returns_input_tuple(Cond0, one) ->
- rl__strip_goal_outputs(Cond0, Cond1)
+ rl__strip_goal_outputs(Cond0, Cond)
;
- Cond1 = Cond0
+ Cond = Cond0
},
- rl_out_info_get_module_info(ModuleInfo),
- { rl_out__is_trivial_project(ModuleInfo, ProjectType,
- Cond1, ProjectIsTrivial) },
(
- { ProjectIsTrivial = yes }
- ->
- %
- % Just copy the input to the output unmodified.
- %
- rl_out__maybe_materialise(Output, Input, Code)
- ;
{ OtherOutputs = [] },
- { rl__goal_is_independent_of_input(one, Cond0) }
+ { rl__goal_is_independent_of_input(one, Cond) }
->
%
% If the produced tuple is independent of the input tuple,
@@ -1073,8 +1179,9 @@
% other projections of the same input relation in the
% one instruction by rl_block_opt.m.
%
- { rl__remove_goal_input(one, Cond0, Cond) },
- rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
+ { rl__remove_goal_input(one, Cond, TupleGoal) },
+ rl_out__generate_exprn(TupleGoal,
+ OutputSchemaOffset, CondExprn),
rl_out__generate_stream(Input, StreamCode),
{ CondCode = tree(node([rl_PROC_empty]), StreamCode) },
rl_out__generate_instr(init(Output) - "", ThenCode),
@@ -1109,16 +1216,21 @@
rl_out_info_get_relation_addr(Input, InputAddr),
rl_out_info_assign_const(string(IndexStr), IndexConst),
rl_out__generate_key_range(Range, RangeExprn),
+
+ % both ends of the key range are closed.
+ % XXX we should detect and use open ranges
+ { IndexRangeTypes = 0 },
+
{ StreamCode = node([
rl_PROC_stream,
- rl_PROC_btree_scan,
+ rl_PROC_btree_scan(IndexRangeTypes),
rl_PROC_indexed_var(InputAddr, 0, IndexConst),
rl_PROC_expr(RangeExprn),
rl_PROC_stream_end
]) }
),
- rl_out__generate_exprn(Cond0, OutputSchemaOffset, CondExprn),
+ rl_out__generate_exprn(Cond, OutputSchemaOffset, CondExprn),
%
% Initialise the other output relations.
@@ -1153,37 +1265,6 @@
{ Code = tree(OtherOutputInitCode, Code0) }
).
- %
- % Check whether a projection is needed.
- % A projection is not needed if it is a selection
- % (there is no output tuple) and the selection condition
- % is deterministic.
- %
-:- pred rl_out__is_trivial_project(module_info::in, project_type::in,
- rl_goal::in, bool::out) is det.
-
-rl_out__is_trivial_project(ModuleInfo, ProjectType, RLGoal, IsTrivial) :-
- (
- ProjectType = filter,
- (
- \+ rl__goal_produces_tuple(RLGoal),
- Goals = RLGoal ^ goal,
-
- rl__goal_can_be_removed(ModuleInfo, Goals)
- ->
- IsTrivial = yes
- ;
- IsTrivial = no
- )
- ;
- %
- % Indexed projections contain a selection
- % which must always be performed.
- %
- ProjectType = index(_, _),
- IsTrivial = no
- ).
-
%-----------------------------------------------------------------------------%
% Copy any arguments which are needed again later to a temporary
@@ -1440,13 +1521,13 @@
;
rl_out_info_get_relation_schema_offset(Output, SchemaOffset),
rl_out_info_get_tmp_var(SchemaOffset, TmpVar),
- rl_out_info_return_tmp_var(SchemaOffset,
- TmpVar, TmpClearCode),
{ LockSpec = 0 }, % default lock spec
rl_out__add_indexes_to_rel(does_not_have_index,
Output, Indexes, IndexInstrs),
rl_out_info_get_next_materialise_id(Id),
+ rl_out_info_return_tmp_var(SchemaOffset,
+ TmpVar, TmpClearCode),
{ Code =
tree(node([
rl_PROC_createtemprel(TmpVar, SchemaOffset)
@@ -1482,10 +1563,10 @@
{ InputType = temporary(stream) },
{ OutputType = temporary(materialised) }
->
- rl_out_info_get_relation_addr(Input, InputAddr),
- { LockSpec = 0 }, % default,
- rl_out__generate_stream_instruction(OutputRel,
- node([rl_PROC_var(InputAddr, LockSpec)]), Code)
+ %
+ % Materialise the input into the output.
+ %
+ rl_out__generate_instr(copy(OutputRel, Input) - "", Code)
;
rl_out__generate_instr(ref(Output, Input) - "", RefCode),
( { Indexes = [] } ->
@@ -2133,6 +2214,29 @@
rl_out_info::in, rl_out_info::out) is det.
rl_out_info_get_relations(Relations) --> Relations =^ relations.
+
+:- pred rl_out_info_add_temporary_relation(list(type)::in, relation_state::in,
+ relation_id::out, rl_out_info::in, rl_out_info::out) is det.
+
+rl_out_info_add_temporary_relation(Schema, State, RelationId) -->
+ Relations0 =^ relations,
+
+ % This should be pretty rare (this predicate is currently only
+ % used in optimizing one type of trivial subtract), so efficiency
+ % isn't a concern.
+ { map__sorted_keys(Relations0, RelationIds0) },
+ { list__last(RelationIds0, HighestRelationId) ->
+ RelationId = HighestRelationId + 1
+ ;
+ RelationId = 0
+ },
+
+ { rl__relation_id_to_string(RelationId, RelName) },
+ { RelationInfo = relation_info(temporary(State),
+ Schema, [], RelName) },
+
+ { map__det_insert(Relations0, RelationId, RelationInfo, Relations) },
+ ^ relations := Relations.
%-----------------------------------------------------------------------------%
Index: rl_relops.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_relops.m,v
retrieving revision 1.4
diff -u -u -r1.4 rl_relops.m
--- rl_relops.m 2000/02/22 02:55:32 1.4
+++ rl_relops.m 2000/02/28 01:27:04
@@ -230,8 +230,12 @@
rl_info__comment(Comment),
rl_info_get_new_temporary(OutputSchema, OutputRel),
- { TrivialJoin = no },
- { SemiJoin = no },
+ { rl__is_semi_join(JoinType, JoinCond, SemiJoin) },
+
+ rl_info_get_module_info(ModuleInfo),
+ { rl__is_trivial_join(ModuleInfo, JoinType, JoinCond,
+ SemiJoin, TrivialJoin) },
+
{ Code = node([join(output_rel(OutputRel, []), ReorderedInput1,
ReorderedInput2, JoinType, JoinCond,
SemiJoin, TrivialJoin) - Comment]) }.
@@ -289,8 +293,14 @@
rl_relops__goal(InstMap, two_inputs(OutputArgs1, OutputArgs2), no,
SubtractGoals, SubtractCond),
rl_info_get_new_temporary(same_as_relation(Rel1), TempRel),
+ rl_info_get_module_info(ModuleInfo),
+
+ { rl__is_trivial_subtract(ModuleInfo, SubtractType, SubtractCond,
+ TrivialSubtract) },
+
{ Subtract = subtract(output_rel(TempRel, []),
- Rel1, Rel2, SubtractType, SubtractCond) - Comment },
+ Rel1, Rel2, SubtractType, SubtractCond,
+ TrivialSubtract) - Comment },
rl_info__comment(Comment),
% The output projection for subtracts must be done as a separate
Index: rl_sort.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_sort.m,v
retrieving revision 1.6
diff -u -u -r1.6 rl_sort.m
--- rl_sort.m 2000/02/22 02:55:33 1.6
+++ rl_sort.m 2000/02/29 00:41:02
@@ -139,7 +139,9 @@
% Go through the instructions removing unnecessary
% sorts and add_indexes.
%
- list__foldl(rl_sort__remove_useless_ops(NeededSortMap), Order),
+ list__foldl(
+ rl_sort__add_indexing_and_remove_useless_ops(NeededSortMap),
+ Order),
%
% Remove the arc we added for memoed relations.
@@ -640,7 +642,7 @@
Input2)
).
rl_sort__instr_needed(BlockId,
- subtract(_Output, Input1, Input2, Type, _Exprn) - _) -->
+ subtract(_Output, Input1, Input2, Type, _Exprn, _Semi) - _) -->
(
{ Type = semi_nested_loop }
;
@@ -778,11 +780,45 @@
sort_info::in, sort_info::out) is det.
rl_sort__instr_avail(BlockId,
- join(Output, _Input1, _Input2, _Type, _Exprn, _, _) - _) -->
- rl_sort__handle_output_indexing(BlockId, Output).
+ join(Output, Input1, Input2, _Type, _Exprn,
+ SemiJoin, Trivial) - _)
+ -->
+ (
+ { SemiJoin = yes(_) },
+ { Trivial = yes(trivial_join_or_subtract_info(TupleNum, no)) }
+ ->
+ %
+ % For trivial semi-joins, which test one of the inputs
+ % for emptiness and return the other, the sortedness
+ % and indexing for the returned relation is passed through
+ % to the output.
+ %
+ { TupleNum = one, PassedInput = Input1
+ ; TupleNum = two, PassedInput = Input2
+ },
+ { Output = output_rel(OutputRel, _) },
+ rl_sort__assign_sortedness_and_indexing(BlockId,
+ OutputRel, PassedInput)
+ ;
+ rl_sort__handle_output_indexing(BlockId, Output)
+ ).
rl_sort__instr_avail(BlockId,
- subtract(Output, _Input1, _Input2, _Type, _Exprn) - _) -->
- rl_sort__handle_output_indexing(BlockId, Output).
+ subtract(Output, Input1, _Input2, _Type,
+ _Exprn, TrivialSubtract) - _)
+ -->
+ (
+ { TrivialSubtract = yes(_) }
+ ->
+ %
+ % For trivial subtracts, the sortedness and indexing for
+ % the first input relation is passed through to the output.
+ %
+ { Output = output_rel(OutputRel, _) },
+ rl_sort__assign_sortedness_and_indexing(BlockId,
+ OutputRel, Input1)
+ ;
+ rl_sort__handle_output_indexing(BlockId, Output)
+ ).
rl_sort__instr_avail(BlockId,
difference(Output, _Input1, _Input2, _Type) - _) -->
% { Type = sort_merge(SortSpec) },
@@ -950,14 +986,21 @@
rl_sort__specialize_instr(BlockId, Instr0, Instrs0, Instrs) -->
(
- { Instr0 = join(Output, Input1, Input2, Type, Exprn, _, _)
- - Comment }
+ { Instr0 = join(Output, Input1, Input2, Type, Exprn,
+ SemiJoin, TrivialJoin) - Comment }
->
rl_sort__specialize_join(Instr0, Output, Input1, Input2,
- Exprn, Type, Comment, Instrs0, Instrs)
+ Type, Exprn, SemiJoin, TrivialJoin,
+ Comment, Instrs0, Instrs)
+ ;
+ { Instr0 = subtract(Output, Input1, Input2, Type, Exprn,
+ TrivialSubtract) - Comment }
+ ->
+ rl_sort__specialize_subtract(Instr0, Output, Input1, Input2,
+ Type, Exprn, TrivialSubtract, Comment, Instrs0, Instrs)
;
- { Instr0 = project(Output, Input, Exprn,
- OtherOutputs, Type) - Comment }
+ { Instr0 = project(Output, Input, Exprn, OtherOutputs, Type)
+ - Comment }
->
rl_sort__specialize_project(Instr0, Output, Input, Exprn,
OtherOutputs, Type, Comment, Instrs0, Instrs)
@@ -968,35 +1011,36 @@
%-----------------------------------------------------------------------------%
- % Attempt to use an indexed join algorithm.
+ % Attempt to use an index/sort/hash join algorithm.
:- pred rl_sort__specialize_join(rl_instruction::in, output_rel::in,
- relation_id::in, relation_id::in, rl_goal::in, join_type::in,
- string::in, list(rl_instruction)::in, list(rl_instruction)::out,
- sort_info::in, sort_info::out) is det.
+ relation_id::in, relation_id::in, join_type::in, rl_goal::in,
+ maybe(semi_join_info)::in, maybe(trivial_join_info)::in,
+ string::in, list(rl_instruction)::in,
+ list(rl_instruction)::out, sort_info::in, sort_info::out) is det.
-rl_sort__specialize_join(Instr0, Output, Input1, Input2, Exprn,
- JoinType, Comment, Instrs0, Instrs,
+rl_sort__specialize_join(Instr0, Output, Input1, Input2, JoinType,
+ Exprn, SemiJoin, TrivialJoin, Comment, Instrs0, Instrs,
SortInfo0, SortInfo) :-
SortInfo0 = sort_info(Sortedness0, SortVars, RLInfo0),
Sortedness0 = sortedness(RelSortMap, _),
rl_sort__introduce_indexed_join(RelSortMap, Output, Input1, Input2,
- JoinType, Exprn, Comment, MaybeIndexJoinInstrs,
- RLInfo0, RLInfo1),
+ JoinType, Exprn, SemiJoin, TrivialJoin, Comment,
+ MaybeIndexJoinInstrs, RLInfo0, RLInfo1),
( MaybeIndexJoinInstrs = yes(IndexJoinInstrs) ->
RLInfo = RLInfo1,
JoinInstrs = IndexJoinInstrs
;
rl_sort__introduce_sort_join(RelSortMap,
- Output, Input1, Input2, JoinType, Exprn, Comment,
- MaybeSortJoinInstrs, RLInfo1, RLInfo2),
+ Output, Input1, Input2, JoinType, Exprn, SemiJoin,
+ Comment, MaybeSortJoinInstrs, RLInfo1, RLInfo2),
( MaybeSortJoinInstrs = yes(SortJoinInstrs) ->
RLInfo = RLInfo2,
JoinInstrs = SortJoinInstrs
;
rl_sort__introduce_hash_join(Output,
- Input1, Input2, JoinType, Exprn, Comment,
- MaybeHashJoinInstrs, RLInfo2, RLInfo),
+ Input1, Input2, JoinType, Exprn, SemiJoin,
+ Comment, MaybeHashJoinInstrs, RLInfo2, RLInfo),
( MaybeHashJoinInstrs = yes(HashJoinInstrs) ->
JoinInstrs = HashJoinInstrs
;
@@ -1008,14 +1052,143 @@
list__append(RevJoinInstrs, Instrs0, Instrs),
SortInfo = sort_info(Sortedness0, SortVars, RLInfo).
+ % Attempt to use an index/hash subtract algorithm.
+:- pred rl_sort__specialize_subtract(rl_instruction::in, output_rel::in,
+ relation_id::in, relation_id::in, subtract_type::in, rl_goal::in,
+ maybe(trivial_subtract_info)::in, string::in,
+ list(rl_instruction)::in, list(rl_instruction)::out,
+ sort_info::in, sort_info::out) is det.
+
+rl_sort__specialize_subtract(Instr0, Output, Input1, Input2, SubtractType,
+ Exprn, TrivialSubtract, Comment, Instrs0, Instrs,
+ SortInfo0, SortInfo) :-
+ SortInfo0 = sort_info(Sortedness0, SortVars, RLInfo0),
+ Sortedness0 = sortedness(RelSortMap, _),
+
+ rl_sort__introduce_indexed_subtract(RelSortMap, Output, Input1, Input2,
+ SubtractType, Exprn, TrivialSubtract, Comment,
+ MaybeIndexSubtractInstrs, RLInfo0, RLInfo1),
+ ( MaybeIndexSubtractInstrs = yes(IndexSubtractInstrs) ->
+ RLInfo = RLInfo1,
+ SubtractInstrs = IndexSubtractInstrs
+ ;
+ RLInfo2 = RLInfo1,
+ /*
+ rl_sort__introduce_sort_subtract(RelSortMap,
+ Output, Input1, Input2, SubtractType, Exprn, Comment,
+ MaybeSortSubtractInstrs, RLInfo1, RLInfo2),
+ ( MaybeSortSubtractInstrs = yes(SortSubtractInstrs) ->
+ RLInfo = RLInfo2,
+ SubtractInstrs = SortSubtractInstrs
+ ;
+ */
+ rl_sort__introduce_hash_subtract(Output,
+ Input1, Input2, SubtractType, Exprn, Comment,
+ MaybeHashSubtractInstrs, RLInfo2, RLInfo),
+ ( MaybeHashSubtractInstrs = yes(HashSubtractInstrs) ->
+ SubtractInstrs = HashSubtractInstrs
+ ;
+ SubtractInstrs = [Instr0]
+ )
+ %)
+ ),
+ list__reverse(SubtractInstrs, RevSubtractInstrs),
+ list__append(RevSubtractInstrs, Instrs0, Instrs),
+ SortInfo = sort_info(Sortedness0, SortVars, RLInfo).
+
+%-----------------------------------------------------------------------------%
+
:- pred rl_sort__introduce_indexed_join(relation_sort_map::in, output_rel::in,
relation_id::in, relation_id::in, join_type::in,
- rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_goal::in, maybe(semi_join_info)::in, maybe(trivial_join_info)::in,
+ string::in, maybe(list(rl_instruction))::out,
rl_opt_info::in, rl_opt_info::out) is det.
rl_sort__introduce_indexed_join(RelSortMap, Output, Input1, Input2, _JoinType0,
- Exprn, Comment, MaybeIndexJoinInstrs, RLInfo0, RLInfo) :-
+ Exprn0, _SemiJoin0, _TrivialJoin0, Comment,
+ MaybeIndexJoinInstrs, RLInfo0, RLInfo) :-
+
+ CanSwapInputs = yes,
+ rl_sort__is_indexed_join_or_subtract(RelSortMap, Input1, Input2,
+ CanSwapInputs, Exprn0, MaybeIndexInfo, RLInfo0, RLInfo1),
+
+ (
+ MaybeIndexInfo = no,
+ MaybeIndexJoinInstrs = no,
+ RLInfo = RLInfo1
+ ;
+ MaybeIndexInfo = yes(
+ index_instr_info(Index, KeyRange, SwapInputs)),
+ JoinType = index(Index, KeyRange),
+ (
+ SwapInputs = yes,
+ rl__swap_goal_inputs(Exprn0, Exprn),
+ JoinInput1 = Input2,
+ JoinInput2 = Input1
+ ;
+ SwapInputs = no,
+ Exprn = Exprn0,
+ JoinInput1 = Input1,
+ JoinInput2 = Input2
+ ),
+
+ rl__is_semi_join(JoinType, Exprn, SemiJoin),
+
+ rl_opt_info_get_module_info(ModuleInfo, RLInfo1, RLInfo),
+ rl__is_trivial_join(ModuleInfo, JoinType, Exprn, SemiJoin,
+ TrivialJoin),
+
+ JoinInstr = join(Output, JoinInput1, JoinInput2,
+ JoinType, Exprn, SemiJoin, TrivialJoin) - Comment,
+ MaybeIndexJoinInstrs = yes([JoinInstr])
+ ).
+
+:- pred rl_sort__introduce_indexed_subtract(relation_sort_map::in,
+ output_rel::in, relation_id::in, relation_id::in, subtract_type::in,
+ rl_goal::in, maybe(trivial_subtract_info)::in, string::in,
+ maybe(list(rl_instruction))::out,
+ rl_opt_info::in, rl_opt_info::out) is det.
+rl_sort__introduce_indexed_subtract(RelSortMap, Output, Input1, Input2,
+ _SubtractType0, Exprn, _TrivialSubtract0, Comment,
+ MaybeIndexSubtractInstrs, RLInfo0, RLInfo) :-
+
+ CanSwapInputs = no,
+ rl_sort__is_indexed_join_or_subtract(RelSortMap, Input1, Input2,
+ CanSwapInputs, Exprn, MaybeIndexInfo, RLInfo0, RLInfo1),
+
+ (
+ MaybeIndexInfo = no,
+ MaybeIndexSubtractInstrs = no,
+ RLInfo = RLInfo1
+ ;
+ MaybeIndexInfo = yes(index_instr_info(Index, KeyRange, _)),
+ SubtractType = semi_index(Index, KeyRange),
+
+ rl_opt_info_get_module_info(ModuleInfo, RLInfo1, RLInfo),
+ rl__is_trivial_subtract(ModuleInfo, SubtractType, Exprn,
+ TrivialSubtract),
+
+ SubtractInstr = subtract(Output, Input1, Input2,
+ SubtractType, Exprn, TrivialSubtract) - Comment,
+ MaybeIndexSubtractInstrs = yes([SubtractInstr])
+ ).
+
+:- type index_instr_info
+ ---> index_instr_info(
+ index_spec,
+ key_range,
+ bool % Do the inputs need to be swapped
+ ).
+
+:- pred rl_sort__is_indexed_join_or_subtract(relation_sort_map::in,
+ relation_id::in, relation_id::in, bool::in,
+ rl_goal::in, maybe(index_instr_info)::out,
+ rl_opt_info::in, rl_opt_info::out) is det.
+
+rl_sort__is_indexed_join_or_subtract(RelSortMap, Input1, Input2,
+ CanSwapInputs, Exprn, MaybeIndexInfo, RLInfo0, RLInfo) :-
+
rl_opt_info_get_relation_info_map(RelMap, RLInfo0, RLInfo1),
rl_sort__get_relation_indexes(RelSortMap, RelMap,
Input1, Input1Indexes, IsBaseRelation1),
@@ -1023,7 +1196,7 @@
Input2, Input2Indexes, IsBaseRelation2),
( Input1Indexes = [], Input2Indexes = [] ->
- MaybeIndexJoinInstrs = no,
+ MaybeIndexInfo = no,
RLInfo = RLInfo1
;
rl_opt_info_get_module_info(ModuleInfo, RLInfo1, RLInfo),
@@ -1044,8 +1217,13 @@
IndexRanges2 = [],
rl_sort__choose_join_index(IndexRanges1a,
IndexRange1a, IndexRange),
- Optimize = yes(IndexRange),
- SwapInputs = yes
+ ( CanSwapInputs = yes ->
+ Optimize = yes(IndexRange),
+ SwapInputs = yes
+ ;
+ Optimize = no,
+ SwapInputs = no
+ )
;
IndexRanges1 = [],
IndexRanges2 = [IndexRange2a | IndexRanges2a],
@@ -1066,7 +1244,8 @@
% (XXX this isn't necessarily correct).
(
IsBaseRelation1 = yes,
- IsBaseRelation2 = no
+ IsBaseRelation2 = no,
+ CanSwapInputs = yes
->
SwapInputs = yes,
Optimize = yes(BestIndexRange1)
@@ -1085,24 +1264,10 @@
),
% XXX handle multiple key ranges.
( Optimize = yes(Index - [KeyRange]) ->
- JoinType = index(Index, KeyRange),
- ( SwapInputs = yes ->
- rl__swap_goal_inputs(Exprn, Exprn1),
- JoinInput1 = Input2,
- JoinInput2 = Input1
- ;
- Exprn1 = Exprn,
- JoinInput1 = Input1,
- JoinInput2 = Input2
- ),
- SemiJoin = no,
- TrivialJoin = no,
- JoinInstr = join(Output, JoinInput1, JoinInput2,
- JoinType, Exprn1, SemiJoin,
- TrivialJoin) - Comment,
- MaybeIndexJoinInstrs = yes([JoinInstr])
+ MaybeIndexInfo = yes(
+ index_instr_info(Index, KeyRange, SwapInputs))
;
- MaybeIndexJoinInstrs = no
+ MaybeIndexInfo = no
)
).
@@ -1147,11 +1312,13 @@
:- pred rl_sort__introduce_sort_join(relation_sort_map::in, output_rel::in,
relation_id::in, relation_id::in, join_type::in,
- rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_goal::in, maybe(semi_join_info)::in, string::in,
+ maybe(list(rl_instruction))::out,
rl_opt_info::in, rl_opt_info::out) is det.
rl_sort__introduce_sort_join(SortMap, Output, Input1, Input2, _JoinType0,
- Exprn, Comment, MaybeSortJoinInstrs, RLInfo, RLInfo) :-
+ Exprn, SemiJoin, Comment, MaybeSortJoinInstrs,
+ RLInfo, RLInfo) :-
Exprn = rl_goal(_, _, _, _, Inputs, _, _, VarBounds),
(
rl_key__is_equijoin(Inputs, VarBounds, Attrs1, Attrs2),
@@ -1163,7 +1330,8 @@
find_equijoin_sort_spec(Attrs2, SortSpecs2, SortSpec2)
->
JoinType = sort_merge(SortSpec1, SortSpec2),
- SemiJoin = no,
+ % The join condition of an equi-join always depends
+ % on both input tuples.
TrivialJoin = no,
JoinInstr = join(Output, Input1, Input2,
JoinType, Exprn, SemiJoin, TrivialJoin) - Comment,
@@ -1252,19 +1420,25 @@
)
), SortMap, [], SortSpecs).
+%-----------------------------------------------------------------------------%
+
:- pred rl_sort__introduce_hash_join(output_rel::in,
relation_id::in, relation_id::in, join_type::in,
- rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_goal::in, maybe(semi_join_info)::in,
+ string::in, maybe(list(rl_instruction))::out,
rl_opt_info::in, rl_opt_info::out) is det.
rl_sort__introduce_hash_join(Output, Input1, Input2, _JoinType0, Exprn,
- Comment, MaybeHashJoinInstrs, RLInfo, RLInfo) :-
- Exprn = rl_goal(_, _, _, _, Inputs, _, _, VarBounds),
+ SemiJoin, Comment, MaybeHashJoinInstrs,
+ RLInfo, RLInfo) :-
+ Inputs = Exprn ^ inputs,
+ VarBounds = Exprn ^ bounds,
(
rl_key__is_equijoin(Inputs, VarBounds, Attrs1, Attrs2)
->
JoinType = hash(Attrs1, Attrs2),
- SemiJoin = no,
+ % The join condition of an equi-join always depends
+ % on both input tuples.
TrivialJoin = no,
JoinInstr = join(Output, Input1, Input2,
JoinType, Exprn, SemiJoin, TrivialJoin) - Comment,
@@ -1273,6 +1447,29 @@
MaybeHashJoinInstrs = no
).
+:- pred rl_sort__introduce_hash_subtract(output_rel::in,
+ relation_id::in, relation_id::in, subtract_type::in,
+ rl_goal::in, string::in, maybe(list(rl_instruction))::out,
+ rl_opt_info::in, rl_opt_info::out) is det.
+
+rl_sort__introduce_hash_subtract(Output, Input1, Input2, _SubtractType0, Exprn,
+ Comment, MaybeHashSubtractInstrs, RLInfo, RLInfo) :-
+ Inputs = Exprn ^ inputs,
+ VarBounds = Exprn ^ bounds,
+ (
+ rl_key__is_equijoin(Inputs, VarBounds, Attrs1, Attrs2)
+ ->
+ SubtractType = semi_hash(Attrs1, Attrs2),
+ % The subtract condition of an equi-subtract always depends
+ % on both input tuples.
+ TrivialSubtract = no,
+ SubtractInstr = subtract(Output, Input1, Input2,
+ SubtractType, Exprn, TrivialSubtract) - Comment,
+ MaybeHashSubtractInstrs = yes([SubtractInstr])
+ ;
+ MaybeHashSubtractInstrs = no
+ ).
+
%-----------------------------------------------------------------------------%
% Work out which index could be used for a project.
@@ -1432,10 +1629,11 @@
%-----------------------------------------------------------------------------%
% Remove unnecessary indexing and sorting operations.
-:- pred rl_sort__remove_useless_ops(sort_data_map::in, block_id::in,
- rl_opt_info::in, rl_opt_info::out) is det.
+:- pred rl_sort__add_indexing_and_remove_useless_ops(sort_data_map::in,
+ block_id::in, rl_opt_info::in, rl_opt_info::out) is det.
-rl_sort__remove_useless_ops(NeededSortMap, BlockId, Info0, Info) :-
+rl_sort__add_indexing_and_remove_useless_ops(NeededSortMap,
+ BlockId, Info0, Info) :-
rl_opt_info_get_block(BlockId, Block0, Info0, Info1),
Block0 = block(Label, Instrs0, EndInstr, BlockInfo),
@@ -1444,18 +1642,22 @@
map__init(VarRequests),
SortInfo0 = sort_info(NeededSorts, VarRequests, Info1),
- list__foldl2(rl_sort__remove_useless_ops_instr(BlockId),
+ list__foldl2(
+ rl_sort__add_indexing_and_remove_useless_ops_instr(BlockId),
RevInstrs0, [], Instrs, SortInfo0, sort_info(_, _, Info2)),
Block = block(Label, Instrs, EndInstr, BlockInfo),
rl_opt_info_set_block(BlockId, Block, Info2, Info).
-:- pred rl_sort__remove_useless_ops_instr(block_id::in,
+:- pred rl_sort__add_indexing_and_remove_useless_ops_instr(block_id::in,
rl_instruction::in, list(rl_instruction)::in,
list(rl_instruction)::out, sort_info::in, sort_info::out) is det.
-rl_sort__remove_useless_ops_instr(BlockId, Instr, Instrs0, Instrs) -->
+rl_sort__add_indexing_and_remove_useless_ops_instr(BlockId,
+ Instr, Instrs0, Instrs) -->
=(sort_info(sortedness(RelSortMap, _), _, _)),
- ( { Instr = add_index(OutputRel0) - Comm } ->
+ (
+ { Instr = add_index(OutputRel0) - Comm }
+ ->
{ rl_sort__map_output_rel(RelSortMap, rl_sort__map_spec,
OutputRel0, OutputRel) },
{ OutputRel = output_rel(Relation, NeededIndexes) },
@@ -1465,7 +1667,9 @@
Instrs = [add_index(output_rel(Relation,
NeededIndexes)) - Comm | Instrs0]
}
- ; { Instr = sort(Output0, Input, SortSpec) - Comm } ->
+ ;
+ { Instr = sort(Output0, Input, SortSpec) - Comm }
+ ->
{ rl_sort__map_output_rel(RelSortMap, rl_sort__map_spec,
Output0, Output) },
{ Output = output_rel(OutputRel, _) },
@@ -1484,7 +1688,8 @@
(
{ SpecNeeded = no },
list__foldl2(
- rl_sort__remove_useless_ops_instr(BlockId),
+ rl_sort__add_indexing_and_remove_useless_ops_instr(
+ BlockId),
[add_index(Output) - Comm,
ref(OutputRel, Input) - Comm],
Instrs0, Instrs)
@@ -1495,6 +1700,26 @@
Instrs0] }
)
;
+ { Instr = join(Output0, Input1, Input2, Type,
+ Exprn, SemiJoin, TrivialJoin) - Comm },
+ { TrivialJoin = yes(trivial_join_or_subtract_info(_, no)) }
+ ->
+ { rl_sort__trivial_join_or_subtract_output_indexes(RelSortMap,
+ Output0, Output) },
+ { Instr1 = join(Output, Input1, Input2, Type,
+ Exprn, SemiJoin, TrivialJoin) - Comm },
+ { Instrs = [Instr1 | Instrs0] }
+ ;
+ { Instr = subtract(Output0, Input1, Input2, Type,
+ Exprn, TrivialSubtract) - Comm },
+ { TrivialSubtract = yes(_) }
+ ->
+ { rl_sort__trivial_join_or_subtract_output_indexes(RelSortMap,
+ Output0, Output) },
+ { Instr1 = subtract(Output, Input1, Input2, Type,
+ Exprn, TrivialSubtract) - Comm },
+ { Instrs = [Instr1 | Instrs0] }
+ ;
{ rl_sort__map_sort_and_index_specs(
rl_sort__map_output_rel(RelSortMap, rl_sort__map_spec),
rl_sort__map_spec, rl_sort__map_spec,
@@ -1502,8 +1727,31 @@
{ Instrs = [Instr1 | Instrs0] }
),
rl_sort__instr_needed(BlockId, Instr).
+
+ % In the cases where a trivial join or subtract creates its output
+ % relation instead of just passing out one of the inputs,
+ % make sure the created relation has the correct indexes.
+:- pred rl_sort__trivial_join_or_subtract_output_indexes(relation_sort_map::in,
+ output_rel::in, output_rel::out) is det.
+
+rl_sort__trivial_join_or_subtract_output_indexes(RelSortMap, Output0, Output) :-
+ rl_sort__map_output_rel(RelSortMap, rl_sort__map_spec,
+ Output0, Output1),
+ Output1 = output_rel(OutputRel, Indexes0),
+ ( map__search(RelSortMap, OutputRel, NeededSorts0) ->
+ map__to_assoc_list(NeededSorts0, NeededSortsAL0),
+ list__filter_map(
+ (pred(SortIndex::in, Index::out) is semidet :-
+ SortIndex = index(Index) - _
+ ), NeededSortsAL0, NeededIndexes),
+ list__delete_elems(NeededIndexes, Indexes0, Indexes1),
+ list__append(Indexes0, Indexes1, Indexes),
+ Output = output_rel(OutputRel, Indexes)
+ ;
+ Output = Output1
+ ).
- % Eventually this will need to instantiate sort variables.
+ % Eventually this will need to instantiate sort variables.
:- pred rl_sort__map_spec(T::in, T::out) is det.
rl_sort__map_spec(Spec, Spec).
@@ -1552,8 +1800,8 @@
Type = Type0
).
rl_sort__map_sort_and_index_specs(OutputPred, IndexPred, SortPred,
- subtract(Output0, B, C, Type0, E) - F,
- subtract(Output, B, C, Type, E) - F) :-
+ subtract(Output0, B, C, Type0, E, F) - G,
+ subtract(Output, B, C, Type, E, F) - G) :-
call(OutputPred, Output0, Output),
( Type0 = semi_sort_merge(Sort1a, Sort2a) ->
call(SortPred, Sort1a, Sort1),
Index: rl_stream.m
===================================================================
RCS file: /home/staff/zs/imp/mercury/compiler/rl_stream.m,v
retrieving revision 1.3
diff -u -u -r1.3 rl_stream.m
--- rl_stream.m 2000/02/22 02:55:34 1.3
+++ rl_stream.m 2000/02/24 00:17:37
@@ -258,9 +258,45 @@
stream_info::in, stream_info::out) is det.
rl_stream__detect_streams_instr(Instr) -->
- ( { Instr = ref(Output, Input) - _ } ->
+ (
+ { Instr = ref(Output, Input) - _ }
+ ->
rl_stream__add_alias(Output, Input)
;
+ { Instr = join(output_rel(Output, _), Input1, Input2,
+ _, _, _, Trivial) - "" },
+ { Trivial = yes(
+ trivial_join_or_subtract_info(ReturnedTuple, no)) }
+ ->
+ % For a trivial join with no projection,
+ % a reference may be taken to the relation
+ % on which the join condition depends.
+ (
+ { ReturnedTuple = one },
+ rl_stream__add_alias(Output, Input1),
+ rl_stream__update_counts([Input2])
+ ;
+ { ReturnedTuple = two },
+ rl_stream__add_alias(Output, Input2),
+ rl_stream__update_counts([Input1])
+ )
+ ;
+ % For a trivial semi-subtract, a reference may be
+ % taken to the relation being subtracted from.
+ { Instr = subtract(output_rel(Output, _), Input1, Input2,
+ _, _, Trivial) - "" },
+ { Trivial = yes(
+ trivial_join_or_subtract_info(UsedTuple, _)) }
+ ->
+ rl_stream__add_alias(Output, Input1),
+ (
+ { UsedTuple = one },
+ rl_stream__update_counts([Input1, Input2])
+ ;
+ { UsedTuple = two },
+ rl_stream__update_counts([Input2])
+ )
+ ;
{ rl__instr_relations(Instr, Inputs, _) },
rl_stream__update_counts(Inputs)
).
@@ -367,7 +403,7 @@
rl_stream__must_materialise_rels(join(Output, _, _, _, _, _, _) - _,
Materialise) :-
rl_stream__output_is_indexed(Output, Materialise).
-rl_stream__must_materialise_rels(subtract(Output, _, _, _, _) - _,
+rl_stream__must_materialise_rels(subtract(Output, _, _, _, _, _) - _,
Materialise) :-
rl_stream__output_is_indexed(Output, Materialise).
rl_stream__must_materialise_rels(difference(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
--------------------------------------------------------------------------
More information about the developers
mailing list