From debfa8a7007aa45abbef93a8027ace94ab066954 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 4 Oct 2010 22:08:42 +0200 Subject: [PATCH] iscc: add dependence analysis operations --- doc/isl.tex | 31 +++++++++- iscc.c | 190 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 218 insertions(+), 3 deletions(-) diff --git a/doc/isl.tex b/doc/isl.tex index d32c5a2..6798492 100644 --- a/doc/isl.tex +++ b/doc/isl.tex @@ -1,5 +1,9 @@ \section{\protect\isl/ interface} +\let\llt\prec +\let\lle\preccurlyeq +\let\lgt\succ + \subsection{Library} The \barvinok/ library currently supports only a few @@ -118,7 +122,7 @@ Syntax & Meaning \\ } \tablelasttail{} -\begin{supertabular}{lp{0.7\textwidth}} +\begin{supertabular}{p{0.35\textwidth}p{0.6\textwidth}} $s_2$ := \ai[\tt]{aff} $s_1$ & affine hull of $s_1$ \\ $m_2$ := \ai[\tt]{aff} $m_1$ & affine hull of $m_1$ @@ -230,6 +234,31 @@ wrap the map in a set $m$ := \ai[\tt]{unwrap} $s$ & unwrap the map from the set \\ +$m_4$ := \ai[\tt]{any} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $m_3$ & +compute a map from any element $x$ in the domain of $m_1$ +to any element $y$ in the domain of $m_2$ +such that their images $m_1(x)$ and $m_2(y)$ overlap +and such that $m_3(x) \llt m_3(y)$. +\\ +$l$ := \ai[\tt]{last} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $m_3$ & +compute a map that contains for any element $y$ in the domain of $m_2$ +a mapping from the lexicographically last element $x$ in the domain of $m_1$ +(according to the schedule $m_3$) to $y$ +such that $m_1(x)$ and $m_2(y)$ overlap and such that $m_3(x) \llt m_3(y)$. +Return a list containing this map and the set of elements in the domain of +$m_2$ for which there is no corresponding element in the domain of $m_1$. +\\ +$m_5$ := \ai[\tt]{any} $m_1$ \ai[\tt]{last} $m_2$ \ai[\tt]{before} $m_3$ +\ai[\tt]{under} $m_4$ & +compute a map that contains for any element $y$ in the domain of $m_3$ +a mapping from the lexicographically last element $x$ in the domain of $m_2$ +(according to the schedule $m_4$) to $y$ +such that $m_2(x)$ and $m_3(y)$ overlap and such that $m_4(x) \llt m_4(y)$ +as well as from any element $z$ in the domain of $m_1$ such that +$m_1(z)$ and $m_3(y)$ overlap, $m_4(z) \llt m_4(y)$ and such that there +is no $x$ in the domain of $m_2$ with +$m_2(x) \cap m_3(y) \ne \emptyset$ and $m_4(z) \llt m_4(x) \llt m_4(y)$. +\\ $s_3$ := $s_1$ \ai{$+$} $s_2$ & union \\ $m_3$ := $m_1$ \ai{$+$} $m_2$ & union diff --git a/iscc.c b/iscc.c index 452a2af..4c2f8df 100644 --- a/iscc.c +++ b/iscc.c @@ -18,8 +18,10 @@ static int isl_bool_false = 0; static int isl_bool_true = 1; static int isl_bool_error = -1; -enum iscc_op { ISCC_READ, ISCC_SOURCE, ISCC_VERTICES, ISCC_N_OP }; -static const char *op_name[ISCC_N_OP] = { "read", "source", "vertices" }; +enum iscc_op { ISCC_READ, ISCC_SOURCE, ISCC_VERTICES, + ISCC_LAST, ISCC_ANY, ISCC_BEFORE, ISCC_UNDER, ISCC_N_OP }; +static const char *op_name[ISCC_N_OP] = { + "read", "source", "vertices", "last", "any", "before", "under" }; static enum isl_token_type iscc_op[ISCC_N_OP]; struct isl_arg_choice iscc_format[] = { @@ -1119,6 +1121,186 @@ error: return obj; } +static __isl_give isl_union_map *read_map(struct isl_stream *s, + struct isl_hash_table *table) +{ + struct isl_obj obj; + + obj = read_expr(s, table); + obj = convert(s->ctx, obj, isl_obj_union_map); + isl_assert(s->ctx, obj.type == isl_obj_union_map, goto error); + return obj.v; +error: + free_obj(obj); + return NULL; +} + +static struct isl_obj last_any(struct isl_stream *s, + struct isl_hash_table *table, __isl_take isl_union_map *must_source, + __isl_take isl_union_map *may_source) +{ + struct isl_obj obj = { isl_obj_none, NULL }; + isl_union_map *sink = NULL; + isl_union_map *schedule = NULL; + isl_union_map *may_dep; + isl_union_map *must_dep; + + if (isl_stream_eat(s, iscc_op[ISCC_BEFORE])) + goto error; + + sink = read_map(s, table); + if (!sink) + goto error; + + if (isl_stream_eat(s, iscc_op[ISCC_UNDER])) + goto error; + + schedule = read_map(s, table); + if (!schedule) + goto error; + + if (isl_union_map_compute_flow(sink, must_source, may_source, + schedule, &must_dep, &may_dep, + NULL, NULL) < 0) + return obj; + + obj.type = isl_obj_union_map; + obj.v = isl_union_map_union(must_dep, may_dep); + + return obj; +error: + isl_union_map_free(may_source); + isl_union_map_free(must_source); + isl_union_map_free(sink); + isl_union_map_free(schedule); + free_obj(obj); + obj.type = isl_obj_none; + obj.v = NULL; + return obj; +} + +static struct isl_obj any(struct isl_stream *s, struct isl_hash_table *table) +{ + struct isl_obj obj = { isl_obj_none, NULL }; + isl_union_map *must_source = NULL; + isl_union_map *may_source = NULL; + isl_union_map *sink = NULL; + isl_union_map *schedule = NULL; + isl_union_map *may_dep; + + may_source = read_map(s, table); + if (!may_source) + goto error; + + if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) { + must_source = read_map(s, table); + if (!must_source) + goto error; + return last_any(s, table, must_source, may_source); + } + + if (isl_stream_eat(s, iscc_op[ISCC_BEFORE])) + goto error; + + sink = read_map(s, table); + if (!sink) + goto error; + + if (isl_stream_eat(s, iscc_op[ISCC_UNDER])) + goto error; + + schedule = read_map(s, table); + if (!schedule) + goto error; + + must_source = isl_union_map_empty(isl_union_map_get_dim(sink)); + if (isl_union_map_compute_flow(sink, must_source, may_source, + schedule, NULL, &may_dep, + NULL, NULL) < 0) + return obj; + + obj.type = isl_obj_union_map; + obj.v = may_dep; + + return obj; +error: + isl_union_map_free(may_source); + isl_union_map_free(must_source); + isl_union_map_free(sink); + isl_union_map_free(schedule); + free_obj(obj); + obj.type = isl_obj_none; + obj.v = NULL; + return obj; +} + +static struct isl_obj last(struct isl_stream *s, struct isl_hash_table *table) +{ + struct isl_obj obj = { isl_obj_none, NULL }; + struct isl_list *list = NULL; + isl_union_map *must_source = NULL; + isl_union_map *may_source = NULL; + isl_union_map *sink = NULL; + isl_union_map *schedule = NULL; + isl_union_map *must_dep; + isl_union_set *must_no_source; + + must_source = read_map(s, table); + if (!must_source) + goto error; + + if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) { + may_source = read_map(s, table); + if (!may_source) + goto error; + return last_any(s, table, must_source, may_source); + } + + list = isl_list_alloc(s->ctx, 2); + if (!list) + goto error; + + if (isl_stream_eat(s, iscc_op[ISCC_BEFORE])) + goto error; + + sink = read_map(s, table); + if (!sink) + goto error; + + if (isl_stream_eat(s, iscc_op[ISCC_UNDER])) + goto error; + + schedule = read_map(s, table); + if (!schedule) + goto error; + + may_source = isl_union_map_empty(isl_union_map_get_dim(sink)); + if (isl_union_map_compute_flow(sink, must_source, may_source, + schedule, &must_dep, NULL, + &must_no_source, NULL) < 0) + return obj; + + list->obj[0].type = isl_obj_union_map; + list->obj[0].v = must_dep; + list->obj[1].type = isl_obj_union_set; + list->obj[1].v = must_no_source; + + obj.v = list; + obj.type = isl_obj_list; + + return obj; +error: + isl_list_free(list); + isl_union_map_free(may_source); + isl_union_map_free(must_source); + isl_union_map_free(sink); + isl_union_map_free(schedule); + free_obj(obj); + obj.type = isl_obj_none; + obj.v = NULL; + return obj; +} + static struct isl_obj power(struct isl_stream *s, struct isl_obj obj) { struct isl_token *tok; @@ -1234,6 +1416,10 @@ static struct isl_obj read_obj(struct isl_stream *s, return read_from_file(s); if (isl_stream_eat_if_available(s, iscc_op[ISCC_VERTICES])) return vertices(s, table); + if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) + return any(s, table); + if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) + return last(s, table); name = isl_stream_read_ident_if_available(s); if (name) -- 2.11.4.GIT