/*
* Copyright 2011 INRIA Saclay
* Copyright 2012-2014 Ecole Normale Superieure
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
* 91893 Orsay, France
* and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
*/
#include <isl/ctx.h>
#include <isl_aff_private.h>
#include <isl/map.h>
#include <isl/set.h>
#include <isl/schedule.h>
#include <isl/schedule_node.h>
#include <isl_sort.h>
#include <isl_schedule_private.h>
#include <isl_schedule_tree.h>
#include <isl_schedule_node_private.h>
#include <isl_band_private.h>
/* Return a schedule encapsulating the given schedule tree.
*
* We currently only allow schedule trees with a domain or extension as root.
*
* The leaf field is initialized as a leaf node so that it can be
* used to represent leaves in the constructed schedule.
* The reference count is set to -1 since the isl_schedule_tree
* should never be freed. It is up to the (internal) users of
* these leaves to ensure that they are only used while the schedule
* is still alive.
*/
__isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx,
__isl_take isl_schedule_tree *tree)
{
enum isl_schedule_node_type type;
isl_schedule *schedule;
if (!tree)
return NULL;
type = isl_schedule_tree_get_type(tree);
if (type != isl_schedule_node_domain &&
type != isl_schedule_node_extension)
isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
"root of schedule tree should be a domain or extension",
goto error);
schedule = isl_calloc_type(ctx, isl_schedule);
if (!schedule)
goto error;
schedule->leaf.ctx = ctx;
isl_ctx_ref(ctx);
schedule->ref = 1;
schedule->root = tree;
schedule->leaf.ref = -1;
schedule->leaf.type = isl_schedule_node_leaf;
return schedule;
error:
isl_schedule_tree_free(tree);
return NULL;
}
/* Return a pointer to a schedule with as single node
* a domain node with the given domain.
*/
__isl_give isl_schedule *isl_schedule_from_domain(
__isl_take isl_union_set *domain)
{
isl_ctx *ctx;
isl_schedule_tree *tree;
ctx = isl_union_set_get_ctx(domain);
tree = isl_schedule_tree_from_domain(domain);
return isl_schedule_from_schedule_tree(ctx, tree);
}
/* Return a pointer to a schedule with as single node
* a domain node with an empty domain.
*/
__isl_give isl_schedule *isl_schedule_empty(__isl_take isl_space *space)
{
return isl_schedule_from_domain(isl_union_set_empty(space));
}
/* Return a new reference to "sched".
*/
__isl_give isl_schedule *isl_schedule_copy(__isl_keep isl_schedule *sched)
{
if (!sched)
return NULL;
sched->ref++;
return sched;
}
/* Return an isl_schedule that is equal to "schedule" and that has only
* a single reference.
*
* We only need and support this function when the schedule is represented
* as a schedule tree.
*/
__isl_give isl_schedule *isl_schedule_cow(__isl_take isl_schedule *schedule)
{
isl_ctx *ctx;
isl_schedule_tree *tree;
if (!schedule)
return NULL;
if (schedule->ref == 1)
return schedule;
ctx = isl_schedule_get_ctx(schedule);
if (!schedule->root)
isl_die(ctx, isl_error_internal,
"only for schedule tree based schedules",
return isl_schedule_free(schedule));
schedule->ref--;
tree = isl_schedule_tree_copy(schedule->root);
return isl_schedule_from_schedule_tree(ctx, tree);
}
__isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched)
{
if (!sched)
return NULL;
if (--sched->ref > 0)
return NULL;
isl_band_list_free(sched->band_forest);
isl_schedule_tree_free(sched->root);
isl_ctx_deref(sched->leaf.ctx);
free(sched);
return NULL;
}
/* Replace the root of "schedule" by "tree".
*/
__isl_give isl_schedule *isl_schedule_set_root(
__isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree)
{
if (!schedule || !tree)
goto error;
if (schedule->root == tree) {
isl_schedule_tree_free(tree);
return schedule;
}
schedule = isl_schedule_cow(schedule);
if (!schedule)
goto error;
isl_schedule_tree_free(schedule->root);
schedule->root = tree;
return schedule;
error:
isl_schedule_free(schedule);
isl_schedule_tree_free(tree);
return NULL;
}
isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
{
return schedule ? schedule->leaf.ctx : NULL;
}
/* Return a pointer to the leaf of "schedule".
*
* Even though these leaves are not reference counted, we still
* indicate that this function does not return a copy.
*/
__isl_keep isl_schedule_tree *isl_schedule_peek_leaf(
__isl_keep isl_schedule *schedule)
{
return schedule ? &schedule->leaf : NULL;
}
/* Are "schedule1" and "schedule2" obviously equal to each other?
*/
isl_bool isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1,
__isl_keep isl_schedule *schedule2)
{
if (!schedule1 || !schedule2)
return isl_bool_error;
if (schedule1 == schedule2)
return isl_bool_true;
return isl_schedule_tree_plain_is_equal(schedule1->root,
schedule2->root);
}
/* Return the (parameter) space of the schedule, i.e., the space
* of the root domain.
*/
__isl_give isl_space *isl_schedule_get_space(
__isl_keep isl_schedule *schedule)
{
enum isl_schedule_node_type type;
isl_space *space;
isl_union_set *domain;
if (!schedule)
return NULL;
if (!schedule->root)
isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
"schedule tree representation not available",
return NULL);
type = isl_schedule_tree_get_type(schedule->root);
if (type != isl_schedule_node_domain)
isl_die(isl_schedule_get_ctx(schedule), isl_error_internal,
"root node not a domain node", return NULL);
domain = isl_schedule_tree_domain_get_domain(schedule->root);
space = isl_union_set_get_space(domain);
isl_union_set_free(domain);
return space;
}
/* Return a pointer to the root of "schedule".
*/
__isl_give isl_schedule_node *isl_schedule_get_root(
__isl_keep isl_schedule *schedule)
{
isl_ctx *ctx;
isl_schedule_tree *tree;
isl_schedule_tree_list *ancestors;
if (!schedule)
return NULL;
if (!schedule->root)
isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
"schedule tree representation not available",
return NULL);
ctx = isl_schedule_get_ctx(schedule);
tree = isl_schedule_tree_copy(schedule->root);
schedule = isl_schedule_copy(schedule);
ancestors = isl_schedule_tree_list_alloc(ctx, 0);
return isl_schedule_node_alloc(schedule, tree, ancestors, NULL);
}
/* Set max_out to the maximal number of output dimensions over
* all maps.
*/
static isl_stat update_max_out(__isl_take isl_map *map, void *user)
{
int *max_out = user;
int n_out = isl_map_dim(map, isl_dim_out);
if (n_out > *max_out)
*max_out = n_out;
isl_map_free(map);
return isl_stat_ok;
}
/* Internal data structure for map_pad_range.
*
* "max_out" is the maximal schedule dimension.
* "res" collects the results.
*/
struct isl_pad_schedule_map_data {
int max_out;
isl_union_map *res;
};
/* Pad the range of the given map with zeros to data->max_out and
* then add the result to data->res.
*/
static isl_stat map_pad_range(__isl_take isl_map *map, void *user)
{
struct isl_pad_schedule_map_data *data = user;
int i;
int n_out = isl_map_dim(map, isl_dim_out);
map = isl_map_add_dims(map, isl_dim_out, data->max_out - n_out);
for (i = n_out; i < data->max_out; ++i)
map = isl_map_fix_si(map, isl_dim_out, i, 0);
data->res = isl_union_map_add_map(data->res, map);
if (!data->res)
return isl_stat_error;
return isl_stat_ok;
}
/* Pad the ranges of the maps in the union map with zeros such they all have
* the same dimension.
*/
static __isl_give isl_union_map *pad_schedule_map(
__isl_take isl_union_map *umap)
{
struct isl_pad_schedule_map_data data;
if (!umap)
return NULL;
if (isl_union_map_n_map(umap) <= 1)
return umap;
data.max_out = 0;
if (isl_union_map_foreach_map(umap, &update_max_out, &data.max_out) < 0)
return isl_union_map_free(umap);
data.res = isl_union_map_empty(isl_union_map_get_space(umap));
if (isl_union_map_foreach_map(umap, &map_pad_range, &data) < 0)
data.res = isl_union_map_free(data.res);
isl_union_map_free(umap);
return data.res;
}
/* Return the domain of the root domain node of "schedule".
*/
__isl_give isl_union_set *isl_schedule_get_domain(
__isl_keep isl_schedule *schedule)
{
if (!schedule)
return NULL;
if (!schedule->root)
isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
"schedule tree representation not available",
return NULL);
return isl_schedule_tree_domain_get_domain(schedule->root);
}
/* Traverse all nodes of "sched" in depth first preorder.
*
* If "fn" returns -1 on any of the nodes, then the traversal is aborted.
* If "fn" returns 0 on any of the nodes, then the subtree rooted
* at that node is skipped.
*
* Return 0 on success and -1 on failure.
*/
isl_stat isl_schedule_foreach_schedule_node_top_down(
__isl_keep isl_schedule *sched,
isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user),
void *user)
{
isl_schedule_node *node;
isl_stat r;
if (!sched)
return isl_stat_error;
node = isl_schedule_get_root(sched);
r = isl_schedule_node_foreach_descendant_top_down(node, fn, user);
isl_schedule_node_free(node);
return r;
}
/* Traverse the node of "sched" in depth first postorder,
* allowing the user to modify the visited node.
* The traversal continues from the node returned by the callback function.
* It is the responsibility of the user to ensure that this does not
* lead to an infinite loop. It is safest to always return a pointer
* to the same position (same ancestors and child positions) as the input node.
*/
__isl_give isl_schedule *isl_schedule_map_schedule_node_bottom_up(
__isl_take isl_schedule *schedule,
__isl_give isl_schedule_node *(*fn)(
__isl_take isl_schedule_node *node, void *user), void *user)
{
isl_schedule_node *node;
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
node = isl_schedule_node_map_descendant_bottom_up(node, fn, user);
schedule = isl_schedule_node_get_schedule(node);
isl_schedule_node_free(node);
return schedule;
}
/* Wrapper around isl_schedule_node_reset_user for use as
* an isl_schedule_map_schedule_node_bottom_up callback.
*/
static __isl_give isl_schedule_node *reset_user(
__isl_take isl_schedule_node *node, void *user)
{
return isl_schedule_node_reset_user(node);
}
/* Reset the user pointer on all identifiers of parameters and tuples
* in the schedule "schedule".
*/
__isl_give isl_schedule *isl_schedule_reset_user(
__isl_take isl_schedule *schedule)
{
return isl_schedule_map_schedule_node_bottom_up(schedule, &reset_user,
NULL);
}
/* Wrapper around isl_schedule_node_align_params for use as
* an isl_schedule_map_schedule_node_bottom_up callback.
*/
static __isl_give isl_schedule_node *align_params(
__isl_take isl_schedule_node *node, void *user)
{
isl_space *space = user;
return isl_schedule_node_align_params(node, isl_space_copy(space));
}
/* Align the parameters of all nodes in schedule "schedule"
* to those of "space".
*/
__isl_give isl_schedule *isl_schedule_align_params(
__isl_take isl_schedule *schedule, __isl_take isl_space *space)
{
schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
&align_params, space);
isl_space_free(space);
return schedule;
}
/* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as
* an isl_schedule_map_schedule_node_bottom_up callback.
*/
static __isl_give isl_schedule_node *pullback_upma(
__isl_take isl_schedule_node *node, void *user)
{
isl_union_pw_multi_aff *upma = user;
return isl_schedule_node_pullback_union_pw_multi_aff(node,
isl_union_pw_multi_aff_copy(upma));
}
/* Compute the pullback of "schedule" by the function represented by "upma".
* In other words, plug in "upma" in the iteration domains of "schedule".
*
* The schedule tree is not allowed to contain any expansion nodes.
*/
__isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff(
__isl_take isl_schedule *schedule,
__isl_take isl_union_pw_multi_aff *upma)
{
schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
&pullback_upma, upma);
isl_union_pw_multi_aff_free(upma);
return schedule;
}
/* Intersect the domain of the schedule "schedule" with "domain".
* The root of "schedule" is required to be a domain node.
*/
__isl_give isl_schedule *isl_schedule_intersect_domain(
__isl_take isl_schedule *schedule, __isl_take isl_union_set *domain)
{
enum isl_schedule_node_type root_type;
isl_schedule_node *node;
if (!schedule || !domain)
goto error;
root_type = isl_schedule_tree_get_type(schedule->root);
if (root_type != isl_schedule_node_domain)
isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
"root node must be a domain node", goto error);
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
node = isl_schedule_node_domain_intersect_domain(node, domain);
schedule = isl_schedule_node_get_schedule(node);
isl_schedule_node_free(node);
return schedule;
error:
isl_schedule_free(schedule);
isl_union_set_free(domain);
return NULL;
}
/* Replace the domain of the schedule "schedule" with the gist
* of the original domain with respect to the parameter domain "context".
*/
__isl_give isl_schedule *isl_schedule_gist_domain_params(
__isl_take isl_schedule *schedule, __isl_take isl_set *context)
{
enum isl_schedule_node_type root_type;
isl_schedule_node *node;
if (!schedule || !context)
goto error;
root_type = isl_schedule_tree_get_type(schedule->root);
if (root_type != isl_schedule_node_domain)
isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
"root node must be a domain node", goto error);
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
node = isl_schedule_node_domain_gist_params(node, context);
schedule = isl_schedule_node_get_schedule(node);
isl_schedule_node_free(node);
return schedule;
error:
isl_schedule_free(schedule);
isl_set_free(context);
return NULL;
}
/* Return an isl_union_map representation of the schedule.
* If we still have access to the schedule tree, then we return
* an isl_union_map corresponding to the subtree schedule of the child
* of the root domain node. That is, we do not intersect the domain
* of the returned isl_union_map with the domain constraints.
* Otherwise, we must have removed it because we created a band forest.
* If so, we extract the isl_union_map from the forest.
* This reconstructed schedule map
* then needs to be padded with zeros to unify the schedule space
* since the result of isl_band_list_get_suffix_schedule may not have
* a unified schedule space.
*/
__isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
{
enum isl_schedule_node_type type;
isl_schedule_node *node;
isl_union_map *umap;
if (!sched)
return NULL;
if (sched->root) {
type = isl_schedule_tree_get_type(sched->root);
if (type != isl_schedule_node_domain)
isl_die(isl_schedule_get_ctx(sched), isl_error_internal,
"root node not a domain node", return NULL);
node = isl_schedule_get_root(sched);
node = isl_schedule_node_child(node, 0);
umap = isl_schedule_node_get_subtree_schedule_union_map(node);
isl_schedule_node_free(node);
return umap;
}
umap = isl_band_list_get_suffix_schedule(sched->band_forest);
return pad_schedule_map(umap);
}
static __isl_give isl_band_list *construct_band_list(
__isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
__isl_keep isl_band *parent);
/* Construct an isl_band structure from the given schedule tree node,
* which may be either a band node or a leaf node.
* In the latter case, construct a zero-dimensional band.
* "domain" is the universe set of the domain elements that reach "node".
* "parent" is the parent isl_band of the isl_band constructed
* by this function.
*
* In case of a band node, we copy the properties (except tilability,
* which is implicit in an isl_band) to the isl_band.
* We assume that the band node is not zero-dimensional.
* If the child of the band node is not a leaf node,
* then we extract the children of the isl_band from this child.
*/
static __isl_give isl_band *construct_band(__isl_take isl_schedule_node *node,
__isl_take isl_union_set *domain, __isl_keep isl_band *parent)
{
int i;
isl_ctx *ctx;
isl_band *band = NULL;
isl_multi_union_pw_aff *mupa;
if (!node || !domain)
goto error;
ctx = isl_schedule_node_get_ctx(node);
band = isl_band_alloc(ctx);
if (!band)
goto error;
band->schedule = node->schedule;
band->parent = parent;
if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
band->n = 0;
band->pma = isl_union_pw_multi_aff_from_domain(domain);
isl_schedule_node_free(node);
return band;
}
band->n = isl_schedule_node_band_n_member(node);
if (band->n == 0)
isl_die(ctx, isl_error_unsupported,
"zero-dimensional band nodes not supported",
goto error);
band->coincident = isl_alloc_array(ctx, int, band->n);
if (band->n && !band->coincident)
goto error;
for (i = 0; i < band->n; ++i)
band->coincident[i] =
isl_schedule_node_band_member_get_coincident(node, i);
mupa = isl_schedule_node_band_get_partial_schedule(node);
band->pma = isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa);
if (!band->pma)
goto error;
node = isl_schedule_node_child(node, 0);
if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
isl_schedule_node_free(node);
isl_union_set_free(domain);
return band;
}
band->children = construct_band_list(node, domain, band);
if (!band->children)
return isl_band_free(band);
return band;
error:
isl_union_set_free(domain);
isl_schedule_node_free(node);
isl_band_free(band);
return NULL;
}
/* Construct a list of isl_band structures from the children of "node".
* "node" itself is a sequence or set node, so that each of the child nodes
* is a filter node and the list returned by node_construct_band_list
* consists of a single element.
* "domain" is the universe set of the domain elements that reach "node".
* "parent" is the parent isl_band of the isl_band structures constructed
* by this function.
*/
static __isl_give isl_band_list *construct_band_list_from_children(
__isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
__isl_keep isl_band *parent)
{
int i, n;
isl_ctx *ctx;
isl_band_list *list;
n = isl_schedule_node_n_children(node);
ctx = isl_schedule_node_get_ctx(node);
list = isl_band_list_alloc(ctx, 0);
for (i = 0; i < n; ++i) {
isl_schedule_node *child;
isl_band_list *list_i;
child = isl_schedule_node_get_child(node, i);
list_i = construct_band_list(child, isl_union_set_copy(domain),
parent);
list = isl_band_list_concat(list, list_i);
}
isl_union_set_free(domain);
isl_schedule_node_free(node);
return list;
}
/* Construct an isl_band structure from the given sequence node
* (or set node that is treated as a sequence node).
* A single-dimensional band is created with as schedule for each of
* filters of the children, the corresponding child position.
* "domain" is the universe set of the domain elements that reach "node".
* "parent" is the parent isl_band of the isl_band constructed
* by this function.
*/
static __isl_give isl_band_list *construct_band_list_sequence(
__isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
__isl_keep isl_band *parent)
{
int i, n;
isl_ctx *ctx;
isl_band *band = NULL;
isl_space *space;
isl_union_pw_multi_aff *upma;
if (!node || !domain)
goto error;
ctx = isl_schedule_node_get_ctx(node);
band = isl_band_alloc(ctx);
if (!band)
goto error;
band->schedule = node->schedule;
band->parent = parent;
band->n = 1;
band->coincident = isl_calloc_array(ctx, int, band->n);
if (!band->coincident)
goto error;
n = isl_schedule_node_n_children(node);
space = isl_union_set_get_space(domain);
upma = isl_union_pw_multi_aff_empty(isl_space_copy(space));
space = isl_space_set_from_params(space);
space = isl_space_add_dims(space, isl_dim_set, 1);
for (i = 0; i < n; ++i) {
isl_schedule_node *child;
isl_union_set *filter;
isl_val *v;
isl_val_list *vl;
isl_multi_val *mv;
isl_union_pw_multi_aff *upma_i;
child = isl_schedule_node_get_child(node, i);
filter = isl_schedule_node_filter_get_filter(child);
isl_schedule_node_free(child);
filter = isl_union_set_intersect(filter,
isl_union_set_copy(domain));
v = isl_val_int_from_si(ctx, i);
vl = isl_val_list_from_val(v);
mv = isl_multi_val_from_val_list(isl_space_copy(space), vl);
upma_i = isl_union_pw_multi_aff_multi_val_on_domain(filter, mv);
upma = isl_union_pw_multi_aff_union_add(upma, upma_i);
}
isl_space_free(space);
band->pma = upma;
if (!band->pma)
goto error;
band->children = construct_band_list_from_children(node, domain, band);
if (!band->children)
band = isl_band_free(band);
return isl_band_list_from_band(band);
error:
isl_union_set_free(domain);
isl_schedule_node_free(node);
isl_band_free(band);
return NULL;
}
/* Construct a list of isl_band structures from "node" depending
* on the type of "node".
* "domain" is the universe set of the domain elements that reach "node".
* "parent" is the parent isl_band of the isl_band structures constructed
* by this function.
*
* If schedule_separate_components is set then set nodes are treated
* as sequence nodes. Otherwise, we directly extract an (implicitly
* parallel) list of isl_band structures.
*
* If "node" is a filter, then "domain" is updated by the filter.
*/
static __isl_give isl_band_list *construct_band_list(
__isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
__isl_keep isl_band *parent)
{
enum isl_schedule_node_type type;
isl_ctx *ctx;
isl_band *band;
isl_band_list *list;
isl_union_set *filter;
if (!node || !domain)
goto error;
type = isl_schedule_node_get_type(node);
switch (type) {
case isl_schedule_node_error:
goto error;
case isl_schedule_node_context:
isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
"context nodes not supported", goto error);
case isl_schedule_node_domain:
isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
"internal domain nodes not allowed", goto error);
case isl_schedule_node_expansion:
isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
"expansion nodes not supported", goto error);
case isl_schedule_node_extension:
isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
"extension nodes not supported", goto error);
case isl_schedule_node_filter:
filter = isl_schedule_node_filter_get_filter(node);
domain = isl_union_set_intersect(domain, filter);
node = isl_schedule_node_child(node, 0);
return construct_band_list(node, domain, parent);
case isl_schedule_node_guard:
isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
"guard nodes not supported", goto error);
case isl_schedule_node_mark:
isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
"mark nodes not supported", goto error);
case isl_schedule_node_set:
ctx = isl_schedule_node_get_ctx(node);
if (isl_options_get_schedule_separate_components(ctx))
return construct_band_list_sequence(node, domain,
parent);
else
return construct_band_list_from_children(node, domain,
parent);
case isl_schedule_node_sequence:
return construct_band_list_sequence(node, domain, parent);
case isl_schedule_node_leaf:
case isl_schedule_node_band:
band = construct_band(node, domain, parent);
list = isl_band_list_from_band(band);
break;
}
return list;
error:
isl_union_set_free(domain);
isl_schedule_node_free(node);
return NULL;
}
/* Return the roots of a band forest representation of the schedule.
* The band forest is constructed from the schedule tree,
* but once such a band forest is
* constructed, we forget about the original schedule tree since
* the user may modify the schedule through the band forest.
*/
__isl_give isl_band_list *isl_schedule_get_band_forest(
__isl_keep isl_schedule *schedule)
{
isl_schedule_node *node;
isl_union_set *domain;
if (!schedule)
return NULL;
if (schedule->root) {
node = isl_schedule_get_root(schedule);
domain = isl_schedule_node_domain_get_domain(node);
domain = isl_union_set_universe(domain);
node = isl_schedule_node_child(node, 0);
schedule->band_forest = construct_band_list(node, domain, NULL);
schedule->root = isl_schedule_tree_free(schedule->root);
}
return isl_band_list_dup(schedule->band_forest);
}
/* Call "fn" on each band in the schedule in depth-first post-order.
*/
int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
int (*fn)(__isl_keep isl_band *band, void *user), void *user)
{
int r;
isl_band_list *forest;
if (!sched)
return -1;
forest = isl_schedule_get_band_forest(sched);
r = isl_band_list_foreach_band(forest, fn, user);
isl_band_list_free(forest);
return r;
}
static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
__isl_keep isl_band_list *list);
static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
__isl_keep isl_band *band)
{
isl_band_list *children;
p = isl_printer_start_line(p);
p = isl_printer_print_union_pw_multi_aff(p, band->pma);
p = isl_printer_end_line(p);
if (!isl_band_has_children(band))
return p;
children = isl_band_get_children(band);
p = isl_printer_indent(p, 4);
p = print_band_list(p, children);
p = isl_printer_indent(p, -4);
isl_band_list_free(children);
return p;
}
static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
__isl_keep isl_band_list *list)
{
int i, n;
n = isl_band_list_n_band(list);
for (i = 0; i < n; ++i) {
isl_band *band;
band = isl_band_list_get_band(list, i);
p = print_band(p, band);
isl_band_free(band);
}
return p;
}
/* Insert a band node with partial schedule "partial" between the domain
* root node of "schedule" and its single child.
* Return a pointer to the updated schedule.
*
* If any of the nodes in the tree depend on the set of outer band nodes
* then we refuse to insert the band node.
*/
__isl_give isl_schedule *isl_schedule_insert_partial_schedule(
__isl_take isl_schedule *schedule,
__isl_take isl_multi_union_pw_aff *partial)
{
isl_schedule_node *node;
int anchored;
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
if (!node)
goto error;
if (isl_schedule_node_get_type(node) != isl_schedule_node_domain)
isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
"root node not a domain node", goto error);
node = isl_schedule_node_child(node, 0);
anchored = isl_schedule_node_is_subtree_anchored(node);
if (anchored < 0)
goto error;
if (anchored)
isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
"cannot insert band node in anchored subtree",
goto error);
node = isl_schedule_node_insert_partial_schedule(node, partial);
schedule = isl_schedule_node_get_schedule(node);
isl_schedule_node_free(node);
return schedule;
error:
isl_schedule_node_free(node);
isl_multi_union_pw_aff_free(partial);
return NULL;
}
/* Insert a context node with constraints "context" between the domain
* root node of "schedule" and its single child.
* Return a pointer to the updated schedule.
*/
__isl_give isl_schedule *isl_schedule_insert_context(
__isl_take isl_schedule *schedule, __isl_take isl_set *context)
{
isl_schedule_node *node;
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
node = isl_schedule_node_child(node, 0);
node = isl_schedule_node_insert_context(node, context);
schedule = isl_schedule_node_get_schedule(node);
isl_schedule_node_free(node);
return schedule;
}
/* Insert a guard node with constraints "guard" between the domain
* root node of "schedule" and its single child.
* Return a pointer to the updated schedule.
*/
__isl_give isl_schedule *isl_schedule_insert_guard(
__isl_take isl_schedule *schedule, __isl_take isl_set *guard)
{
isl_schedule_node *node;
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
node = isl_schedule_node_child(node, 0);
node = isl_schedule_node_insert_guard(node, guard);
schedule = isl_schedule_node_get_schedule(node);
isl_schedule_node_free(node);
return schedule;
}
/* Return a tree with as top-level node a filter corresponding to "filter" and
* as child, the (single) child of "tree".
* However, if this single child is of type "type", then the filter is inserted
* in the children of this single child instead.
*/
static __isl_give isl_schedule_tree *insert_filter_in_child_of_type(
__isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter,
enum isl_schedule_node_type type)
{
if (!isl_schedule_tree_has_children(tree)) {
isl_schedule_tree_free(tree);
return isl_schedule_tree_from_filter(filter);
} else {
tree = isl_schedule_tree_child(tree, 0);
}
if (isl_schedule_tree_get_type(tree) == type)
tree = isl_schedule_tree_children_insert_filter(tree, filter);
else
tree = isl_schedule_tree_insert_filter(tree, filter);
return tree;
}
/* Construct a schedule that combines the schedules "schedule1" and "schedule2"
* with a top-level node (underneath the domain node) of type "type",
* either isl_schedule_node_sequence or isl_schedule_node_set.
* The domains of the two schedules are assumed to be disjoint.
*
* The new schedule has as domain the union of the domains of the two
* schedules. The child of the domain node is a node of type "type"
* with two filters corresponding to the domains of the input schedules.
* If one (or both) of the top-level nodes of the two schedules is itself
* of type "type", then the filter is pushed into the children of that
* node and the sequence of set is flattened.
*/
__isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type,
__isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
{
int disjoint;
isl_ctx *ctx;
enum isl_schedule_node_type root_type;
isl_schedule_tree *tree1, *tree2;
isl_union_set *filter1, *filter2, *domain;
if (!schedule1 || !schedule2)
goto error;
root_type = isl_schedule_tree_get_type(schedule1->root);
if (root_type != isl_schedule_node_domain)
isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
"root node not a domain node", goto error);
root_type = isl_schedule_tree_get_type(schedule2->root);
if (root_type != isl_schedule_node_domain)
isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
"root node not a domain node", goto error);
ctx = isl_schedule_get_ctx(schedule1);
tree1 = isl_schedule_tree_copy(schedule1->root);
filter1 = isl_schedule_tree_domain_get_domain(tree1);
tree2 = isl_schedule_tree_copy(schedule2->root);
filter2 = isl_schedule_tree_domain_get_domain(tree2);
isl_schedule_free(schedule1);
isl_schedule_free(schedule2);
disjoint = isl_union_set_is_disjoint(filter1, filter2);
if (disjoint < 0)
filter1 = isl_union_set_free(filter1);
if (!disjoint)
isl_die(ctx, isl_error_invalid,
"schedule domains not disjoint",
filter1 = isl_union_set_free(filter1));
domain = isl_union_set_union(isl_union_set_copy(filter1),
isl_union_set_copy(filter2));
filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain));
filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain));
tree1 = insert_filter_in_child_of_type(tree1, filter1, type);
tree2 = insert_filter_in_child_of_type(tree2, filter2, type);
tree1 = isl_schedule_tree_from_pair(type, tree1, tree2);
tree1 = isl_schedule_tree_insert_domain(tree1, domain);
return isl_schedule_from_schedule_tree(ctx, tree1);
error:
isl_schedule_free(schedule1);
isl_schedule_free(schedule2);
return NULL;
}
/* Construct a schedule that combines the schedules "schedule1" and "schedule2"
* through a sequence node.
* The domains of the input schedules are assumed to be disjoint.
*/
__isl_give isl_schedule *isl_schedule_sequence(
__isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
{
return isl_schedule_pair(isl_schedule_node_sequence,
schedule1, schedule2);
}
/* Construct a schedule that combines the schedules "schedule1" and "schedule2"
* through a set node.
* The domains of the input schedules are assumed to be disjoint.
*/
__isl_give isl_schedule *isl_schedule_set(
__isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
{
return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2);
}
/* Print "schedule" to "p".
*
* If "schedule" was created from a schedule tree, then we print
* the schedule tree representation. Otherwise, we print
* the band forest representation.
*/
__isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
__isl_keep isl_schedule *schedule)
{
isl_band_list *forest;
if (!schedule)
return isl_printer_free(p);
if (schedule->root)
return isl_printer_print_schedule_tree(p, schedule->root);
forest = isl_schedule_get_band_forest(schedule);
p = print_band_list(p, forest);
isl_band_list_free(forest);
return p;
}
void isl_schedule_dump(__isl_keep isl_schedule *schedule)
{
isl_printer *printer;
if (!schedule)
return;
printer = isl_printer_to_file(isl_schedule_get_ctx(schedule), stderr);
printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
printer = isl_printer_print_schedule(printer, schedule);
isl_printer_free(printer);
}
/* Return a string representation of "schedule".
* Print the schedule in flow format.
*/
__isl_give char *isl_schedule_to_str(__isl_keep isl_schedule *schedule)
{
isl_printer *printer;
char *s;
if (!schedule)
return NULL;
printer = isl_printer_to_str(isl_schedule_get_ctx(schedule));
printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_FLOW);
printer = isl_printer_print_schedule(printer, schedule);
s = isl_printer_get_str(printer);
isl_printer_free(printer);
return s;
}