From 5f4d2e1b1e1f15aa71f1aede0d917a27823fbbbd Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 21 Jan 2015 21:22:27 +0100 Subject: [PATCH] iscc: support schedule trees in dependence analysis operations Signed-off-by: Sven Verdoolaege --- doc/isl.tex | 43 +++++++++++++++++++++++++++++-------------- iscc.c | 17 ++++++++++------- 2 files changed, 39 insertions(+), 21 deletions(-) diff --git a/doc/isl.tex b/doc/isl.tex index 7146079..9e6b931 100644 --- a/doc/isl.tex +++ b/doc/isl.tex @@ -618,6 +618,7 @@ $s$: set, $m$: map, $q$: piecewise quasipolynomial, $f$: piecewise quasipolynomial fold, +$t$: schedule (tree), $l$: list, $i$: integer, $b$: boolean, @@ -851,30 +852,44 @@ the cross product of domain and range of $m_1$, i.e., $\{\, (\vec w \to \vec y) \to (\vec x \to \vec z) \mid (\vec w \to \vec x) \to (\vec y \to \vec z) \in m_1 \,\}$ \\ -$m_4$ := \ai[\tt]{any} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $m_3$ & +$m_3$ := \ai[\tt]{any} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $t$ & 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)$. +and such that $x$ is scheduled before $y$ by $t$. \\ -$l$ := \ai[\tt]{last} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $m_3$ & +$m_4$ := \ai[\tt]{any} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $m_3$ & +same as the previous operation, with the schedule represented by a map. +\\ +$l$ := \ai[\tt]{last} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $t$ & 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)$. +a mapping from the last element $x$ in the domain of $m_1$ +(according to the schedule $t$) to $y$ +such that $m_1(x)$ and $m_2(y)$ overlap +and such that $x$ is scheduled before $y$ by $t$. 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$ & +$l$ := \ai[\tt]{last} $m_1$ \ai[\tt]{before} $m_2$ \ai[\tt]{under} $m_3$ & +same as the previous operation, with the schedule represented by a map. +\\ +$m_4$ := \ai[\tt]{any} $m_1$ \ai[\tt]{last} $m_2$ \ai[\tt]{before} $m_3$ +\ai[\tt]{under} $t$ & 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)$ +a mapping from the last element $x$ in the domain of $m_2$ +(according to the schedule $t$) to $y$ +such that $m_2(x)$ and $m_3(y)$ overlap +and such that $x$ is scheduled before $y$ by $t$ 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)$. +$m_1(z)$ and $m_3(y)$ overlap, +$z$ is scheduled before $y$ by $t$ +and such that there is no $x$ in the domain of $m_2$ with +$m_2(x) \cap m_3(y) \ne \emptyset$ and +$x$ scheduled between $z$ and $y$ by $t$. +\\ +$m_5$ := \ai[\tt]{any} $m_1$ \ai[\tt]{last} $m_2$ \ai[\tt]{before} $m_3$ +\ai[\tt]{under} $m_4$ & +same as the previous operation, with the schedule represented by a map. \\ $m_3$ := \ai[\tt]{schedule} $s$ \ai[\tt]{respecting} $m_1$ \ai[\tt]{minimizing} $m_2$ & compute a schedule for the domains in $s$ that respects all dependences diff --git a/iscc.c b/iscc.c index 8606f69..b1e4b52 100644 --- a/iscc.c +++ b/iscc.c @@ -1613,20 +1613,23 @@ error: return NULL; } -/* Read a schedule in the form of a union map from "s" and - * store the schedule in "access". +/* Read a schedule in the form of either a schedule (tree) or a union map + * from "s" and store the schedule in "access". */ static __isl_give isl_union_access_info *access_info_set_schedule( __isl_take isl_union_access_info *access, struct isl_stream *s, struct isl_hash_table *table) { - isl_union_map *schedule; + struct isl_obj obj; + isl_ctx *ctx; - schedule = read_map(s, table); - if (!schedule) - return isl_union_access_info_free(access); + obj = read_obj(s, table); + if (obj.type == isl_obj_schedule) + return isl_union_access_info_set_schedule(access, obj.v); + ctx = isl_stream_get_ctx(s); + obj = convert(ctx, obj, isl_obj_union_map); - return isl_union_access_info_set_schedule_map(access, schedule); + return isl_union_access_info_set_schedule_map(access, obj.v); } static struct isl_obj last_any(struct isl_stream *s, -- 2.11.4.GIT