From 9963b91e565ed8f2a7fa48bd9100457640f6b741 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 10 May 2017 18:34:52 +0200 Subject: [PATCH] isl_union_access_info_compute_flow: handle coscheduled must-sources isl_union_access_info_compute_flow is defined to look for dependences from the last must-source preceding a sink source as well as all intermediate may-sources or simply any preceding may-source if there is no preceding must-source. This definition does not explain what happens when there are multiple must-sources that are scheduled together or when there are may-sources that are scheduled together with a must-source. What would happen in practice is that one of the must-sources would result in a dependence, while all other coscheduled sources would simply be ignored. It can sometimes be useful to allow coscheduled sources, especially in the high-level interface isl_union_access_info_compute_flow. Given that the input does not specify whether the must-source is executed before or after the other sources, the only sensible result is for any dependence resulting from this must-source to be considered a may-dependence, while the other sources should also result in may-dependences. This commit implements this result by looking for coscheduled sources after an initial computation of the dependences derived from a must-source at a given level. The behavior with respect to sources that are not coscheduled is not changed by this commit. The change in behavior is also reflected in the documentation. While this commit changes the behavior of isl_union_access_info_compute_flow, it only does so in cases where it was undefined before. Moreover, the original behavior was unreliable. The low-level interface is not modified by this commit. Users of the low-level interface should continue to ensure that there are no coscheduled sources. Signed-off-by: Sven Verdoolaege --- doc/user.pod | 12 +- isl_flow.c | 199 ++++++++++++++++++++++++++++++- test_inputs/flow/multi.ai | 10 ++ test_inputs/flow/multi.flow | 4 + test_inputs/flow/multi_source-tree.ai | 8 ++ test_inputs/flow/multi_source-tree.flow | 4 + test_inputs/flow/multi_source.ai | 3 + test_inputs/flow/multi_source.flow | 4 + test_inputs/flow/multi_source2-tree.ai | 9 ++ test_inputs/flow/multi_source2-tree.flow | 4 + test_inputs/flow/multi_source2.ai | 4 + test_inputs/flow/multi_source2.flow | 4 + test_inputs/flow/multi_source3-tree.ai | 13 ++ test_inputs/flow/multi_source3-tree.flow | 4 + test_inputs/flow/multi_source3.ai | 4 + test_inputs/flow/multi_source3.flow | 4 + test_inputs/flow/multi_source4-tree.ai | 13 ++ test_inputs/flow/multi_source4-tree.flow | 4 + test_inputs/flow/multi_source4.ai | 4 + test_inputs/flow/multi_source4.flow | 4 + 20 files changed, 311 insertions(+), 4 deletions(-) create mode 100644 test_inputs/flow/multi.ai create mode 100644 test_inputs/flow/multi.flow create mode 100644 test_inputs/flow/multi_source-tree.ai create mode 100644 test_inputs/flow/multi_source-tree.flow create mode 100644 test_inputs/flow/multi_source.ai create mode 100644 test_inputs/flow/multi_source.flow create mode 100644 test_inputs/flow/multi_source2-tree.ai create mode 100644 test_inputs/flow/multi_source2-tree.flow create mode 100644 test_inputs/flow/multi_source2.ai create mode 100644 test_inputs/flow/multi_source2.flow create mode 100644 test_inputs/flow/multi_source3-tree.ai create mode 100644 test_inputs/flow/multi_source3-tree.flow create mode 100644 test_inputs/flow/multi_source3.ai create mode 100644 test_inputs/flow/multi_source3.flow create mode 100644 test_inputs/flow/multi_source4-tree.ai create mode 100644 test_inputs/flow/multi_source4-tree.flow create mode 100644 test_inputs/flow/multi_source4.ai create mode 100644 test_inputs/flow/multi_source4.flow diff --git a/doc/user.pod b/doc/user.pod index c6704e38..82216813 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -8769,8 +8769,8 @@ C contains specialized functionality for performing array dataflow analysis. That is, given a I access relation and a collection of possible I access relations, C can compute relations that describe -for each iteration of the sink access, which iteration -of which of the source access relations was the last +for each iteration of the sink access, which iterations +of which of the source access relations may have been the last to access the same data element before the given iteration of the sink access. The resulting dependence relations map source iterations @@ -8781,8 +8781,10 @@ a read, while the sources should be writes. If any of the source accesses are marked as being I accesses, then there will be a (may) dependence from the last I access B from any I access that follows +or coincides with this last I access, but still precedes the sink access. -Only dependences originating in a must access and without +Only dependences originating in a must access not coscheduled +with any other access to the same element and without any may accesses between the must access and the sink access are considered to be must dependences. In particular, if I sources are I accesses, @@ -8977,6 +8979,10 @@ In particular, let I be the number of loops shared by the two accesses. If C precedes C textually, then the function should return I<2 * n + 1>; otherwise, it should return I<2 * n>. +The low-level interface assumes that no sources are coscheduled. +If the information returned by the callback does not allow +the relative order to be determined, then one of the sources +is arbitrarily taken to be executed after the other(s). The sources can be added to the C object by performing (at most) C calls to C. diff --git a/isl_flow.c b/isl_flow.c index 2056a3f6..b66c5148 100644 --- a/isl_flow.c +++ b/isl_flow.c @@ -160,10 +160,15 @@ struct isl_labeled_map { int must; }; +typedef int (*isl_access_coscheduled)(void *first, void *second); + /* A structure containing the input for dependence analysis: * - a sink * - n_must + n_may (<= max_source) sources * - a function for determining the relative order of sources and sink + * - an optional function "coscheduled" for determining whether sources + * may be coscheduled. If "coscheduled" is NULL, then the sources + * are assumed not to be coscheduled. * The must sources are placed before the may sources. * * domain_map is an auxiliary map that maps the sink access relation @@ -178,6 +183,7 @@ struct isl_access_info { isl_map *domain_map; struct isl_labeled_map sink; isl_access_level_before level_before; + isl_access_coscheduled coscheduled; isl_access_restrict restrict_fn; void *restrict_user; @@ -841,6 +847,140 @@ static __isl_give isl_map *all_intermediate_sources( return map; } +/* Given a dependence relation "old_map" between a must-source and the sink, + * return a subset of the dependences, augmented with instances + * of the source at position "pos" in "acc" that are coscheduled + * with the must-source and that access the same element. + * That is, if the input lives in a space T -> K, then the output + * lives in the space [T -> S] -> K, with S the space of source "pos", and + * the domain factor of the domain product is a subset of the input. + * The sources are considered to be coscheduled if they have the same values + * for the initial "depth" coordinates. + * + * First construct a dependence relation S -> K and a mapping + * between coscheduled sources T -> S. + * The second is combined with the original dependence relation T -> K + * to form a relation in T -> [S -> K], which is subsequently + * uncurried to [T -> S] -> K. + * This result is then intersected with the dependence relation S -> K + * to form the output. + */ +static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc, + __isl_keep isl_map *old_map, int pos, int depth) +{ + isl_space *space; + isl_set *set_C; + isl_map *read_map; + isl_map *write_map; + isl_map *dep_map; + isl_map *equal; + isl_map *map; + + set_C = isl_map_range(isl_map_copy(old_map)); + read_map = isl_map_copy(acc->sink.map); + read_map = isl_map_intersect_domain(read_map, set_C); + write_map = isl_map_copy(acc->source[pos].map); + dep_map = isl_map_domain_product(write_map, read_map); + dep_map = isl_set_unwrap(isl_map_domain(dep_map)); + space = isl_space_join(isl_map_get_space(old_map), + isl_space_reverse(isl_map_get_space(dep_map))); + equal = isl_map_from_basic_map(isl_basic_map_equal(space, depth)); + map = isl_map_range_product(equal, isl_map_copy(old_map)); + map = isl_map_uncurry(map); + map = isl_map_intersect_domain_factor_range(map, dep_map); + + return map; +} + +/* After the dependences derived from a must-source have been computed + * at a certain level, check if any of the sources of the must-dependences + * may be coscheduled with other sources. + * If they are any such sources, then there is no way of determining + * which of the sources actually comes last and the must-dependences + * need to be turned into may-dependences, while dependences from + * the other sources need to be added to the may-dependences as well. + * "acc" describes the sources and a callback for checking whether + * two sources may be coscheduled. If acc->coscheduled is NULL then + * the sources are assumed not to be coscheduled. + * "must_rel" and "may_rel" describe the must and may-dependence relations + * computed at the current level for the must-sources. Some of the dependences + * may be moved from "must_rel" to "may_rel". + * "flow" contains all dependences computed so far (apart from those + * in "must_rel" and "may_rel") and may be updated with additional + * dependences derived from may-sources. + * + * In particular, consider all the must-sources with a non-empty + * dependence relation in "must_rel". They are considered in reverse + * order because that is the order in which they are considered in the caller. + * If any of the must-sources are coscheduled, then the last one + * is the one that will have a corresponding dependence relation. + * For each must-source i, consider both all the previous must-sources + * and all the may-sources. If any of those may be coscheduled with + * must-source i, then compute the coscheduled instances that access + * the same memory elements. The result is a relation [T -> S] -> K. + * The projection onto T -> K is a subset of the must-dependence relation + * that needs to be turned into may-dependences. + * The projection onto S -> K needs to be added to the may-dependences + * of source S. + * Since a given must-source instance may be coscheduled with several + * other source instances, the dependences that need to be turned + * into may-dependences are first collected and only actually removed + * from the must-dependences after all other sources have been considered. + */ +static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc, + __isl_keep isl_map **must_rel, __isl_keep isl_map **may_rel, + __isl_take isl_flow *flow) +{ + int i, j; + + if (!acc->coscheduled) + return flow; + for (i = acc->n_must - 1; i >= 0; --i) { + isl_map *move; + + if (isl_map_plain_is_empty(must_rel[i])) + continue; + move = isl_map_empty(isl_map_get_space(must_rel[i])); + for (j = i - 1; j >= 0; --j) { + int depth; + isl_map *map, *factor; + + if (!acc->coscheduled(acc->source[i].data, + acc->source[j].data)) + continue; + depth = acc->level_before(acc->source[i].data, + acc->source[j].data) / 2; + map = coscheduled_source(acc, must_rel[i], j, depth); + factor = isl_map_domain_factor_range(isl_map_copy(map)); + may_rel[j] = isl_map_union(may_rel[j], factor); + map = isl_map_domain_factor_domain(map); + move = isl_map_union(move, map); + } + for (j = 0; j < acc->n_may; ++j) { + int depth, pos; + isl_map *map, *factor; + + pos = acc->n_must + j; + if (!acc->coscheduled(acc->source[i].data, + acc->source[pos].data)) + continue; + depth = acc->level_before(acc->source[i].data, + acc->source[pos].data) / 2; + map = coscheduled_source(acc, must_rel[i], pos, depth); + factor = isl_map_domain_factor_range(isl_map_copy(map)); + pos = 2 * acc->n_must + j; + flow->dep[pos].map = isl_map_union(flow->dep[pos].map, + factor); + map = isl_map_domain_factor_domain(map); + move = isl_map_union(move, map); + } + must_rel[i] = isl_map_subtract(must_rel[i], isl_map_copy(move)); + may_rel[i] = isl_map_union(may_rel[i], move); + } + + return flow; +} + /* Compute dependences for the case where all accesses are "may" * accesses, which boils down to computing memory based dependences. * The generic algorithm would also work in this case, but it would @@ -918,7 +1058,12 @@ static __isl_give isl_flow *compute_mem_based_dependences( * need to be considered. These iterations are split into those that * haven't been matched to any source access (mustdo) and those that have only * been matched to may accesses (maydo). - * At the end of each level, we also consider the may accesses. + * At the end of each level, must-sources and may-sources that are coscheduled + * with the sources of the must-dependences at that level are considered. + * If any coscheduled instances are found, then corresponding may-dependences + * are added and the original must-dependences are turned into may-dependences. + * Afterwards, the may accesses that occur after must-dependence sources + * are considered. * In particular, we consider may accesses that precede the remaining * sink iterations, moving elements from mustdo to maydo when appropriate, * and may accesses that occur between a must source and a sink of any @@ -1005,6 +1150,8 @@ static __isl_give isl_flow *compute_val_based_dependences( intermediate_sources(acc, may_rel, j, level); } + handle_coscheduled(acc, must_rel, may_rel, res); + for (j = 0; j < acc->n_may; ++j) { int plevel; isl_map *T; @@ -2148,6 +2295,40 @@ static int before(void *first, void *second) return 2 * n1; } +/* Check if the given two accesses may be coscheduled. + * If so, return 1. Otherwise return 0. + * + * Two accesses may only be coscheduled if the fixed schedule + * coordinates have the same values. + */ +static int coscheduled(void *first, void *second) +{ + struct isl_sched_info *info1 = first; + struct isl_sched_info *info2 = second; + int n1, n2; + int i; + + n1 = isl_vec_size(info1->cst); + n2 = isl_vec_size(info2->cst); + + if (n2 < n1) + n1 = n2; + + for (i = 0; i < n1; ++i) { + int cmp; + + if (!info1->is_cst[i]) + continue; + if (!info2->is_cst[i]) + continue; + cmp = isl_vec_cmp_element(info1->cst, info2->cst, i); + if (cmp != 0) + return 0; + } + + return 1; +} + /* Given a sink access, look for all the source accesses that access * the same array and perform dataflow analysis on them using * isl_access_info_compute_flow_core. @@ -2187,6 +2368,7 @@ static isl_stat compute_flow(__isl_take isl_map *map, void *user) if (!data->sink_info || (data->count && !data->source_info) || !data->accesses) goto error; + data->accesses->coscheduled = &coscheduled; data->count = 0; data->must = 1; if (isl_union_map_foreach_map(data->must_source, @@ -2590,6 +2772,19 @@ static int before_node(void *first, void *second) return 2 * depth + before; } +/* Check if the given two accesses may be coscheduled. + * If so, return 1. Otherwise return 0. + * + * Two accesses may only be coscheduled if they appear in the same leaf. + */ +static int coscheduled_node(void *first, void *second) +{ + isl_schedule_node *node1 = first; + isl_schedule_node *node2 = second; + + return node1 == node2; +} + /* Add the scheduled sources from "data" that access * the same data space as "sink" to "access". */ @@ -2660,6 +2855,8 @@ static __isl_give isl_union_flow *compute_single_flow( access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node, &before_node, data->n_source); + if (access) + access->coscheduled = &coscheduled_node; access = add_matching_sources(access, sink, data); flow = access_info_compute_flow_core(access); diff --git a/test_inputs/flow/multi.ai b/test_inputs/flow/multi.ai new file mode 100644 index 00000000..c76ed66c --- /dev/null +++ b/test_inputs/flow/multi.ai @@ -0,0 +1,10 @@ +sink: "{ [S_2[] -> __pet_ref_4[]] -> a[] }" +must_source: "{ [S_0[] -> __pet_ref_0[]] -> a[]; [S_2[] -> __pet_ref_3[]] -> b[]; [S_1[] -> __pet_ref_1[]] -> a[]; [S_1[] -> __pet_ref_2[]] -> a[] }" +may_source: "{ [S_1[] -> __pet_ref_2[]] -> a[]; [S_1[] -> __pet_ref_1[]] -> a[]; [S_2[] -> __pet_ref_3[]] -> b[]; [S_0[] -> __pet_ref_0[]] -> a[] }" +schedule: + domain: "{ [S_1[] -> __pet_ref_1[]]; [S_1[] -> __pet_ref_2[]]; [S_2[] -> __pet_ref_3[]]; [S_0[] -> __pet_ref_0[]]; [S_2[] -> __pet_ref_4[]] }" + child: + sequence: + - filter: "{ [S_0[] -> __pet_ref_0[]] }" + - filter: "{ [S_1[] -> __pet_ref_1[]]; [S_1[] -> __pet_ref_2[]] }" + - filter: "{ [S_2[] -> __pet_ref_3[]]; [S_2[] -> __pet_ref_4[]] }" diff --git a/test_inputs/flow/multi.flow b/test_inputs/flow/multi.flow new file mode 100644 index 00000000..da6b0a1c --- /dev/null +++ b/test_inputs/flow/multi.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ [S_1[] -> __pet_ref_2[]] -> [[S_2[] -> __pet_ref_4[]] -> a[]]; [S_1[] -> __pet_ref_1[]] -> [[S_2[] -> __pet_ref_4[]] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source-tree.ai b/test_inputs/flow/multi_source-tree.ai new file mode 100644 index 00000000..cf5826e3 --- /dev/null +++ b/test_inputs/flow/multi_source-tree.ai @@ -0,0 +1,8 @@ +sink: "{ S[] -> a[] }" +must_source: "{ T[] -> a[]; U[] -> a[] }" +schedule: + domain: "{ U[]; S[]; T[] }" + child: + sequence: + - filter: "{ T[]; U[] }" + - filter: "{ S[] }" diff --git a/test_inputs/flow/multi_source-tree.flow b/test_inputs/flow/multi_source-tree.flow new file mode 100644 index 00000000..e8f953aa --- /dev/null +++ b/test_inputs/flow/multi_source-tree.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; U[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source.ai b/test_inputs/flow/multi_source.ai new file mode 100644 index 00000000..1ce36897 --- /dev/null +++ b/test_inputs/flow/multi_source.ai @@ -0,0 +1,3 @@ +sink: { S[] -> a[] } +must_source: { T[] -> a[]; U[] -> a[] } +schedule_map: { T[] -> [0]; U[] -> [0]; S[] -> [1] } diff --git a/test_inputs/flow/multi_source.flow b/test_inputs/flow/multi_source.flow new file mode 100644 index 00000000..e8f953aa --- /dev/null +++ b/test_inputs/flow/multi_source.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; U[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source2-tree.ai b/test_inputs/flow/multi_source2-tree.ai new file mode 100644 index 00000000..d88d96b1 --- /dev/null +++ b/test_inputs/flow/multi_source2-tree.ai @@ -0,0 +1,9 @@ +sink: "{ S[] -> a[] }" +must_source: "{ T[] -> a[] }" +may_source: "{ U[] -> a[] }" +schedule: + domain: "{ U[]; S[]; T[] }" + child: + sequence: + - filter: "{ T[]; U[] }" + - filter: "{ S[] }" diff --git a/test_inputs/flow/multi_source2-tree.flow b/test_inputs/flow/multi_source2-tree.flow new file mode 100644 index 00000000..e8f953aa --- /dev/null +++ b/test_inputs/flow/multi_source2-tree.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; U[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source2.ai b/test_inputs/flow/multi_source2.ai new file mode 100644 index 00000000..ba9f46e4 --- /dev/null +++ b/test_inputs/flow/multi_source2.ai @@ -0,0 +1,4 @@ +sink: { S[] -> a[] } +must_source: { T[] -> a[] } +may_source: { U[] -> a[] } +schedule_map: { T[] -> [0]; U[] -> [0]; S[] -> [1] } diff --git a/test_inputs/flow/multi_source2.flow b/test_inputs/flow/multi_source2.flow new file mode 100644 index 00000000..e8f953aa --- /dev/null +++ b/test_inputs/flow/multi_source2.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; U[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source3-tree.ai b/test_inputs/flow/multi_source3-tree.ai new file mode 100644 index 00000000..7cd24657 --- /dev/null +++ b/test_inputs/flow/multi_source3-tree.ai @@ -0,0 +1,13 @@ +sink: "{ S[] -> a[] }" +must_source: "{ T[] -> a[]; U[] -> a[] }" +may_source: "{ V[] -> a[] }" +schedule: + domain: "{ S[]; U[]; T[]; V[] }" + child: + sequence: + - filter: "{ U[]; T[]; V[] }" + child: + sequence: + - filter: "{ T[]; U[] }" + - filter: "{ V[] }" + - filter: "{ S[] }" diff --git a/test_inputs/flow/multi_source3-tree.flow b/test_inputs/flow/multi_source3-tree.flow new file mode 100644 index 00000000..b037575e --- /dev/null +++ b/test_inputs/flow/multi_source3-tree.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; U[] -> [S[] -> a[]]; V[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source3.ai b/test_inputs/flow/multi_source3.ai new file mode 100644 index 00000000..e2e3d476 --- /dev/null +++ b/test_inputs/flow/multi_source3.ai @@ -0,0 +1,4 @@ +sink: { S[] -> a[] } +must_source: { T[] -> a[]; U[] -> a[] } +may_source: { V[] -> a[] } +schedule_map: { T[] -> [0,0]; U[] -> [0,0]; V[] -> [0,1]; S[] -> [1,0] } diff --git a/test_inputs/flow/multi_source3.flow b/test_inputs/flow/multi_source3.flow new file mode 100644 index 00000000..b037575e --- /dev/null +++ b/test_inputs/flow/multi_source3.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; U[] -> [S[] -> a[]]; V[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source4-tree.ai b/test_inputs/flow/multi_source4-tree.ai new file mode 100644 index 00000000..431ac76d --- /dev/null +++ b/test_inputs/flow/multi_source4-tree.ai @@ -0,0 +1,13 @@ +sink: "{ S[] -> a[] }" +must_source: "{ T[] -> a[]; U[] -> a[] }" +may_source: "{ V[] -> a[] }" +schedule: + domain: "{ S[]; U[]; T[]; V[] }" + child: + sequence: + - filter: "{ U[]; T[]; V[] }" + child: + sequence: + - filter: "{ U[] }" + - filter: "{ V[]; T[] }" + - filter: "{ S[] }" diff --git a/test_inputs/flow/multi_source4-tree.flow b/test_inputs/flow/multi_source4-tree.flow new file mode 100644 index 00000000..8bf4111f --- /dev/null +++ b/test_inputs/flow/multi_source4-tree.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; V[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" diff --git a/test_inputs/flow/multi_source4.ai b/test_inputs/flow/multi_source4.ai new file mode 100644 index 00000000..8ce0ebe1 --- /dev/null +++ b/test_inputs/flow/multi_source4.ai @@ -0,0 +1,4 @@ +sink: { S[] -> a[] } +must_source: { T[] -> a[]; U[] -> a[] } +may_source: { V[] -> a[] } +schedule_map: { T[] -> [0,1]; U[] -> [0,0]; V[] -> [0,1]; S[] -> [1,0] } diff --git a/test_inputs/flow/multi_source4.flow b/test_inputs/flow/multi_source4.flow new file mode 100644 index 00000000..8bf4111f --- /dev/null +++ b/test_inputs/flow/multi_source4.flow @@ -0,0 +1,4 @@ +must_dependence: "{ }" +may_dependence: "{ T[] -> [S[] -> a[]]; V[] -> [S[] -> a[]] }" +must_no_source: "{ }" +may_no_source: "{ }" -- 2.11.4.GIT