[m-rev.] for review: Avoid duplicate labels in target code generated for tag switches.
Peter Wang
novalazy at gmail.com
Tue Feb 12 17:35:21 AEDT 2013
Branches: main, release
---
commit f81fa62c71b0afa1402591c383757643dc5a0725
Author: Peter Wang <novalazy at gmail.com>
Date: Tue Feb 12 17:33:46 2013 +1100
Avoid duplicate labels in target code generated for tag switches.
In a MLDS tag switch, the code of each case was generated once then duplicated
for multiple primary tags. This produces invalid target code if the duplicated
code contains a label, e.g. to break of out of binary search loop.
The solution in this patch is to not duplicate the code if it contains a label,
but to regenerate it everywhere it occurs to ensure new labels.
compiler/ml_tag_switch.m
As above.
tests/hard_coded/Mmakefile:
tests/hard_coded/tag_switch_dup_label.exp:
tests/hard_coded/tag_switch_dup_label.m:
Add test case.
diff --git a/compiler/ml_tag_switch.m b/compiler/ml_tag_switch.m
index 0342753..ce0305b 100644
--- a/compiler/ml_tag_switch.m
+++ b/compiler/ml_tag_switch.m
@@ -47,6 +47,7 @@
:- import_module ml_backend.ml_simplify_switch.
:- import_module ml_backend.ml_switch_gen.
:- import_module ml_backend.ml_unify_gen.
+:- import_module ml_backend.ml_util.
:- import_module assoc_list.
:- import_module int.
@@ -56,6 +57,12 @@
:- import_module set.
:- import_module unit.
+:- type code_map == map(int, maybe_code).
+
+:- type maybe_code
+ ---> immediate(statement)
+ ; generate(hlds_goal).
+
%-----------------------------------------------------------------------------%
ml_generate_tag_switch(TaggedCases, Var, CodeModel, CanFail, Context,
@@ -108,14 +115,46 @@ ml_generate_tag_switch(TaggedCases, Var, CodeModel, CanFail, Context,
Statements = [SwitchStatement].
:- pred gen_tagged_case_code(code_model::in, tagged_case::in, int::out,
- map(int, statement)::in, map(int, statement)::out, unit::in, unit::out,
+ code_map::in, code_map::out, unit::in, unit::out,
ml_gen_info::in, ml_gen_info::out) is det.
-gen_tagged_case_code(CodeModel, TaggedCase, CaseNum, !CodeMap, !Unit, !Info) :-
- TaggedCase = tagged_case(_MainTaggedConsId, _OtherTaggedConsIds,
+gen_tagged_case_code(CodeModel, TaggedCase, CaseNum, !CodeMap, !Unit,
+ Info0, Info) :-
+ TaggedCase = tagged_case(_MainTaggedConsId, OtherTaggedConsIds,
CaseNum, Goal),
- ml_gen_goal_as_branch_block(CodeModel, Goal, Statement, !Info),
- map.det_insert(CaseNum, Statement, !CodeMap).
+ ml_gen_goal_as_branch_block(CodeModel, Goal, Statement, Info0, Info1),
+ % Do not allow the generated code to be literally duplicated if it contains
+ % labels. Rather, we will regenerate the code at every point it is required
+ % so that the labels are unique.
+ (
+ OtherTaggedConsIds = [_ | _],
+ statement_contains_label(Statement)
+ ->
+ MaybeCode = generate(Goal),
+ Info = Info0
+ ;
+ MaybeCode = immediate(Statement),
+ Info = Info1
+ ),
+ map.det_insert(CaseNum, MaybeCode, !CodeMap).
+
+:- pred statement_contains_label(statement::in) is semidet.
+
+statement_contains_label(Statement) :-
+ statement_contains_statement(Statement, Label),
+ Label = statement(ml_stmt_label(_), _).
+
+:- pred lookup_code_map(code_map::in, int::in, code_model::in, statement::out,
+ ml_gen_info::in, ml_gen_info::out) is det.
+
+lookup_code_map(CodeMap, CaseNum, CodeModel, Statement, !Info) :-
+ map.lookup(CodeMap, CaseNum, MaybeCode),
+ (
+ MaybeCode = immediate(Statement)
+ ;
+ MaybeCode = generate(Goal),
+ ml_gen_goal_as_branch_block(CodeModel, Goal, Statement, !Info)
+ ).
:- type is_a_case_split_between_ptags
---> no_case_is_split_between_ptags
@@ -141,7 +180,7 @@ find_any_split_cases_2(_CaseNum, Ptags, !IsAnyCaseSplit) :-
%-----------------------------------------------------------------------------%
-:- pred gen_ptag_cases(ptag_case_group_list(int)::in, map(int, statement)::in,
+:- pred gen_ptag_cases(ptag_case_group_list(int)::in, code_map::in,
prog_var::in, can_fail::in, code_model::in, ptag_count_map::in,
prog_context::in, list(mlds_switch_case)::out,
ml_gen_info::in, ml_gen_info::out) is det.
@@ -154,7 +193,7 @@ gen_ptag_cases([Ptag | Ptags], CodeMap, Var, CanFail, CodeModel,
gen_ptag_cases(Ptags, CodeMap, Var, CanFail, CodeModel,
PtagCountMap, Context, MLDS_Cases, !Info).
-:- pred gen_ptag_case(ptag_case_group_entry(int)::in, map(int, statement)::in,
+:- pred gen_ptag_case(ptag_case_group_entry(int)::in, code_map::in,
prog_var::in, can_fail::in, code_model::in, ptag_count_map::in,
prog_context::in, mlds_switch_case::out,
ml_gen_info::in, ml_gen_info::out) is det.
@@ -178,7 +217,7 @@ gen_ptag_case(PtagCase, CodeMap, Var, CanFail, CodeModel, PtagCountMap,
unexpected($module, $pred, "no goal for non-shared tag")
;
GoalList = [_Stag - CaseNum],
- map.lookup(CodeMap, CaseNum, Statement)
+ lookup_code_map(CodeMap, CaseNum, CodeModel, Statement, !Info)
;
GoalList = [_, _ | _],
unexpected($module, $pred, "more than one goal for non-shared tag")
@@ -213,7 +252,7 @@ gen_ptag_case(PtagCase, CodeMap, Var, CanFail, CodeModel, PtagCountMap,
% to switch on it. This can happen if the other functor symbols
% that share this primary tag are ruled out by the initial inst
% of the switched-on variable.
- map.lookup(CodeMap, CaseNum, Statement)
+ lookup_code_map(CodeMap, CaseNum, CodeModel, Statement, !Info)
;
gen_stag_switch(GroupedGoalList, CodeMap, MainPtag, SecTagLocn,
Var, CodeModel, CaseCanFail, Context, Statement, !Info)
@@ -266,7 +305,7 @@ build_stag_rev_map([Entry | Entries], !RevMap) :-
%-----------------------------------------------------------------------------%
:- pred gen_stag_switch(assoc_list(int, stags)::in,
- map(int, statement)::in, int::in, sectag_locn::in, prog_var::in,
+ code_map::in, int::in, sectag_locn::in, prog_var::in,
code_model::in, can_fail::in, prog_context::in, statement::out,
ml_gen_info::in, ml_gen_info::out) is det.
@@ -292,7 +331,7 @@ gen_stag_switch(Cases, CodeMap, PrimaryTag, StagLocn, Var, CodeModel,
),
% Generate the switch on the secondary tag.
- gen_stag_cases(Cases, CodeMap, StagCases0, !Info),
+ gen_stag_cases(Cases, CodeMap, CodeModel, StagCases0, !Info),
list.sort(StagCases0, StagCases),
ml_switch_generate_default(CanFail, CodeModel, Context, Default, !Info),
@@ -305,24 +344,25 @@ gen_stag_switch(Cases, CodeMap, PrimaryTag, StagLocn, Var, CodeModel,
%-----------------------------------------------------------------------------%
-:- pred gen_stag_cases(assoc_list(int, stags)::in, map(int, statement)::in,
+:- pred gen_stag_cases(assoc_list(int, stags)::in,
+ code_map::in, code_model::in,
list(mlds_switch_case)::out, ml_gen_info::in, ml_gen_info::out) is det.
-gen_stag_cases([], _, [], !Info).
-gen_stag_cases([Group | Groups], CodeMap, [Case | Cases], !Info) :-
- gen_stag_case(Group, CodeMap, Case, !Info),
- gen_stag_cases(Groups, CodeMap, Cases, !Info).
+gen_stag_cases([], _, _, [], !Info).
+gen_stag_cases([Group | Groups], CodeMap, CodeModel, [Case | Cases], !Info) :-
+ gen_stag_case(Group, CodeMap, CodeModel, Case, !Info),
+ gen_stag_cases(Groups, CodeMap, CodeModel, Cases, !Info).
-:- pred gen_stag_case(pair(int, stags)::in, map(int, statement)::in,
+:- pred gen_stag_case(pair(int, stags)::in, code_map::in, code_model::in,
mlds_switch_case::out, ml_gen_info::in, ml_gen_info::out) is det.
-gen_stag_case(Group, CodeMap, MLDS_Case, !Info) :-
+gen_stag_case(Group, CodeMap, CodeModel, MLDS_Case, !Info) :-
Group = CaseNum - Stags,
Stags = stags(FirstStag, RevLaterStags),
list.reverse(RevLaterStags, LaterStags),
FirstMatch = make_match_value(FirstStag),
LaterMatches = list.map(make_match_value, LaterStags),
- map.lookup(CodeMap, CaseNum, Statement),
+ lookup_code_map(CodeMap, CaseNum, CodeModel, Statement, !Info),
MLDS_Case = mlds_switch_case(FirstMatch, LaterMatches, Statement).
:- func make_match_value(int) = mlds_case_match_cond.
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index fa65c46..0fd3e0a 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -293,6 +293,7 @@ ORDINARY_PROGS= \
sv_record_update \
switch_detect \
system_sort \
+ tag_switch_dup_label \
target_mlobjs \
term_io_test \
term_to_univ_test \
diff --git a/tests/hard_coded/tag_switch_dup_label.exp b/tests/hard_coded/tag_switch_dup_label.exp
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/tests/hard_coded/tag_switch_dup_label.exp
@@ -0,0 +1 @@
+1
diff --git a/tests/hard_coded/tag_switch_dup_label.m b/tests/hard_coded/tag_switch_dup_label.m
new file mode 100644
index 0000000..899a3d0
--- /dev/null
+++ b/tests/hard_coded/tag_switch_dup_label.m
@@ -0,0 +1,52 @@
+% The compiler could previously generate high-level C code with duplicate
+% labels.
+
+:- module tag_switch_dup_label.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- type fruit
+ ---> apple
+ ; banana(int)
+ ; cherry(string).
+
+main(!IO) :-
+ ( p(apple, "a", N) ->
+ io.write_int(N, !IO),
+ io.nl(!IO)
+ ;
+ true
+ ).
+
+:- pred p(fruit::in, string::in, int::out) is semidet.
+:- pragma no_inline(p/3).
+
+p(F, S, N) :-
+ (
+ % A tag switch with multiple primary tags leading to the same case.
+ ( F = apple
+ ; F = banana(_)
+ ),
+ % A string switch which is compiled to a binary search.
+ % A label is used to jump out of the search.
+ ( S = "a", N = 1
+ ; S = "b", N = 2
+ ; S = "c", N = 3
+ ; S = "d", N = 4
+ ; S = "e", N = 5
+ )
+ ;
+ F = cherry(_),
+ N = 6
+ ).
+
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sts=4 sw=4 et
More information about the reviews
mailing list