path: root/polly/lib/External/isl/isl_schedule.c

/*
 * 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_sort.h>
#include <isl_schedule_private.h>
#include <isl_band_private.h>

__isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched)
{
	int i;
	if (!sched)
		return NULL;

	if (--sched->ref > 0)
		return NULL;

	for (i = 0; i < sched->n; ++i) {
		isl_multi_aff_free(sched->node[i].sched);
		free(sched->node[i].band_end);
		free(sched->node[i].band_id);
		free(sched->node[i].coincident);
	}
	isl_space_free(sched->dim);
	isl_band_list_free(sched->band_forest);
	free(sched);
	return NULL;
}

isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
{
	return schedule ? isl_space_get_ctx(schedule->dim) : NULL;
}

/* Set max_out to the maximal number of output dimensions over
 * all maps.
 */
static int 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 0;
}

/* 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 int 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 -1;

	return 0;
}

/* 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 an isl_union_map of the schedule.  If we have already constructed
 * a band forest, then this band forest may have been modified so we need
 * to extract the isl_union_map from the forest rather than from
 * the originally computed schedule.  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)
{
	int i;
	isl_union_map *umap;

	if (!sched)
		return NULL;

	if (sched->band_forest) {
		umap = isl_band_list_get_suffix_schedule(sched->band_forest);
		return pad_schedule_map(umap);
	}

	umap = isl_union_map_empty(isl_space_copy(sched->dim));
	for (i = 0; i < sched->n; ++i) {
		isl_multi_aff *ma;

		ma = isl_multi_aff_copy(sched->node[i].sched);
		umap = isl_union_map_add_map(umap, isl_map_from_multi_aff(ma));
	}

	return umap;
}

static __isl_give isl_band_list *construct_band_list(
	__isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
	int band_nr, int *parent_active, int n_active);

/* Construct an isl_band structure for the band in the given schedule
 * with sequence number band_nr for the n_active nodes marked by active.
 * If the nodes don't have a band with the given sequence number,
 * then a band without members is created.
 *
 * Because of the way the schedule is constructed, we know that
 * the position of the band inside the schedule of a node is the same
 * for all active nodes.
 *
 * The partial schedule for the band is created before the children
 * are created to that construct_band_list can refer to the partial
 * schedule of the parent.
 */
static __isl_give isl_band *construct_band(__isl_keep isl_schedule *schedule,
	__isl_keep isl_band *parent,
	int band_nr, int *active, int n_active)
{
	int i, j;
	isl_ctx *ctx = isl_schedule_get_ctx(schedule);
	isl_band *band;
	unsigned start, end;

	band = isl_band_alloc(ctx);
	if (!band)
		return NULL;

	band->schedule = schedule;
	band->parent = parent;

	for (i = 0; i < schedule->n; ++i)
		if (active[i])
			break;

	if (i >= schedule->n)
		isl_die(ctx, isl_error_internal,
			"band without active statements", goto error);

	start = band_nr ? schedule->node[i].band_end[band_nr - 1] : 0;
	end = band_nr < schedule->node[i].n_band ?
		schedule->node[i].band_end[band_nr] : start;
	band->n = end - start;

	band->coincident = isl_alloc_array(ctx, int, band->n);
	if (band->n && !band->coincident)
		goto error;

	for (j = 0; j < band->n; ++j)
		band->coincident[j] = schedule->node[i].coincident[start + j];

	band->pma = isl_union_pw_multi_aff_empty(isl_space_copy(schedule->dim));
	for (i = 0; i < schedule->n; ++i) {
		isl_multi_aff *ma;
		isl_pw_multi_aff *pma;
		unsigned n_out;

		if (!active[i])
			continue;

		ma = isl_multi_aff_copy(schedule->node[i].sched);
		n_out = isl_multi_aff_dim(ma, isl_dim_out);
		ma = isl_multi_aff_drop_dims(ma, isl_dim_out, end, n_out - end);
		ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, start);
		pma = isl_pw_multi_aff_from_multi_aff(ma);
		band->pma = isl_union_pw_multi_aff_add_pw_multi_aff(band->pma,
								    pma);
	}
	if (!band->pma)
		goto error;

	for (i = 0; i < schedule->n; ++i)
		if (active[i] && schedule->node[i].n_band > band_nr + 1)
			break;

	if (i < schedule->n) {
		band->children = construct_band_list(schedule, band,
						band_nr + 1, active, n_active);
		if (!band->children)
			goto error;
	}

	return band;
error:
	isl_band_free(band);
	return NULL;
}

/* Internal data structure used inside cmp_band and pw_multi_aff_extract_int.
 *
 * r is set to a negative value if anything goes wrong.
 *
 * c1 stores the result of extract_int.
 * c2 is a temporary value used inside cmp_band_in_ancestor.
 * t is a temporary value used inside extract_int.
 *
 * first and equal are used inside extract_int.
 * first is set if we are looking at the first isl_multi_aff inside
 * the isl_union_pw_multi_aff.
 * equal is set if all the isl_multi_affs have been equal so far.
 */
struct isl_cmp_band_data {
	int r;

	int first;
	int equal;

	isl_int t;
	isl_int c1;
	isl_int c2;
};

/* Check if "ma" assigns a constant value.
 * Note that this function is only called on isl_multi_affs
 * with a single output dimension.
 *
 * If "ma" assigns a constant value then we compare it to data->c1
 * or assign it to data->c1 if this is the first isl_multi_aff we consider.
 * If "ma" does not assign a constant value or if it assigns a value
 * that is different from data->c1, then we set data->equal to zero
 * and terminate the check.
 */
static int multi_aff_extract_int(__isl_take isl_set *set,
	__isl_take isl_multi_aff *ma, void *user)
{
	isl_aff *aff;
	struct isl_cmp_band_data *data = user;

	aff = isl_multi_aff_get_aff(ma, 0);
	data->r = isl_aff_is_cst(aff);
	if (data->r >= 0 && data->r) {
		isl_aff_get_constant(aff, &data->t);
		if (data->first) {
			isl_int_set(data->c1, data->t);
			data->first = 0;
		} else if (!isl_int_eq(data->c1, data->t))
			data->equal = 0;
	} else if (data->r >= 0 && !data->r)
		data->equal = 0;

	isl_aff_free(aff);
	isl_set_free(set);
	isl_multi_aff_free(ma);

	if (data->r < 0)
		return -1;
	if (!data->equal)
		return -1;
	return 0;
}

/* This function is called for each isl_pw_multi_aff in
 * the isl_union_pw_multi_aff checked by extract_int.
 * Check all the isl_multi_affs inside "pma".
 */
static int pw_multi_aff_extract_int(__isl_take isl_pw_multi_aff *pma,
	void *user)
{
	int r;

	r = isl_pw_multi_aff_foreach_piece(pma, &multi_aff_extract_int, user);
	isl_pw_multi_aff_free(pma);

	return r;
}

/* Check if "upma" assigns a single constant value to its domain.
 * If so, return 1 and store the result in data->c1.
 * If not, return 0.
 *
 * A negative return value from isl_union_pw_multi_aff_foreach_pw_multi_aff
 * means that either an error occurred or that we have broken off the check
 * because we already know the result is going to be negative.
 * In the latter case, data->equal is set to zero.
 */
static int extract_int(__isl_keep isl_union_pw_multi_aff *upma,
	struct isl_cmp_band_data *data)
{
	data->first = 1;
	data->equal = 1;

	if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
					&pw_multi_aff_extract_int, data) < 0) {
		if (!data->equal)
			return 0;
		return -1;
	}

	return !data->first && data->equal;
}

/* Compare "b1" and "b2" based on the parent schedule of their ancestor
 * "ancestor".
 *
 * If the parent of "ancestor" also has a single member, then we
 * first try to compare the two band based on the partial schedule
 * of this parent.
 *
 * Otherwise, or if the result is inconclusive, we look at the partial schedule
 * of "ancestor" itself.
 * In particular, we specialize the parent schedule based
 * on the domains of the child schedules, check if both assign
 * a single constant value and, if so, compare the two constant values.
 * If the specialized parent schedules do not assign a constant value,
 * then they cannot be used to order the two bands and so in this case
 * we return 0.
 */
static int cmp_band_in_ancestor(__isl_keep isl_band *b1,
	__isl_keep isl_band *b2, struct isl_cmp_band_data *data,
	__isl_keep isl_band *ancestor)
{
	isl_union_pw_multi_aff *upma;
	isl_union_set *domain;
	int r;

	if (data->r < 0)
		return 0;

	if (ancestor->parent && ancestor->parent->n == 1) {
		r = cmp_band_in_ancestor(b1, b2, data, ancestor->parent);
		if (data->r < 0)
			return 0;
		if (r)
			return r;
	}

	upma = isl_union_pw_multi_aff_copy(b1->pma);
	domain = isl_union_pw_multi_aff_domain(upma);
	upma = isl_union_pw_multi_aff_copy(ancestor->pma);
	upma = isl_union_pw_multi_aff_intersect_domain(upma, domain);
	r = extract_int(upma, data);
	isl_union_pw_multi_aff_free(upma);

	if (r < 0)
		data->r = -1;
	if (r < 0 || !r)
		return 0;

	isl_int_set(data->c2, data->c1);

	upma = isl_union_pw_multi_aff_copy(b2->pma);
	domain = isl_union_pw_multi_aff_domain(upma);
	upma = isl_union_pw_multi_aff_copy(ancestor->pma);
	upma = isl_union_pw_multi_aff_intersect_domain(upma, domain);
	r = extract_int(upma, data);
	isl_union_pw_multi_aff_free(upma);

	if (r < 0)
		data->r = -1;
	if (r < 0 || !r)
		return 0;

	return isl_int_cmp(data->c2, data->c1);
}

/* Compare "a" and "b" based on the parent schedule of their parent.
 */
static int cmp_band(const void *a, const void *b, void *user)
{
	isl_band *b1 = *(isl_band * const *) a;
	isl_band *b2 = *(isl_band * const *) b;
	struct isl_cmp_band_data *data = user;

	return cmp_band_in_ancestor(b1, b2, data, b1->parent);
}

/* Sort the elements in "list" based on the partial schedules of its parent
 * (and ancestors).  In particular if the parent assigns constant values
 * to the domains of the bands in "list", then the elements are sorted
 * according to that order.
 * This order should be a more "natural" order for the user, but otherwise
 * shouldn't have any effect.
 * If we would be constructing an isl_band forest directly in
 * isl_schedule_constraints_compute_schedule then there wouldn't be any need
 * for a reordering, since the children would be added to the list
 * in their natural order automatically.
 *
 * If there is only one element in the list, then there is no need to sort
 * anything.
 * If the partial schedule of the parent has more than one member
 * (or if there is no parent), then it's
 * defnitely not assigning constant values to the different children in
 * the list and so we wouldn't be able to use it to sort the list.
 */
static __isl_give isl_band_list *sort_band_list(__isl_take isl_band_list *list,
	__isl_keep isl_band *parent)
{
	struct isl_cmp_band_data data;

	if (!list)
		return NULL;
	if (list->n <= 1)
		return list;
	if (!parent || parent->n != 1)
		return list;

	data.r = 0;
	isl_int_init(data.c1);
	isl_int_init(data.c2);
	isl_int_init(data.t);
	isl_sort(list->p, list->n, sizeof(list->p[0]), &cmp_band, &data);
	if (data.r < 0)
		list = isl_band_list_free(list);
	isl_int_clear(data.c1);
	isl_int_clear(data.c2);
	isl_int_clear(data.t);

	return list;
}

/* Construct a list of bands that start at the same position (with
 * sequence number band_nr) in the schedules of the nodes that
 * were active in the parent band.
 *
 * A separate isl_band structure is created for each band_id
 * and for each node that does not have a band with sequence
 * number band_nr.  In the latter case, a band without members
 * is created.
 * This ensures that if a band has any children, then each node
 * that was active in the band is active in exactly one of the children.
 */
static __isl_give isl_band_list *construct_band_list(
	__isl_keep isl_schedule *schedule, __isl_keep isl_band *parent,
	int band_nr, int *parent_active, int n_active)
{
	int i, j;
	isl_ctx *ctx = isl_schedule_get_ctx(schedule);
	int *active;
	int n_band;
	isl_band_list *list;

	n_band = 0;
	for (i = 0; i < n_active; ++i) {
		for (j = 0; j < schedule->n; ++j) {
			if (!parent_active[j])
				continue;
			if (schedule->node[j].n_band <= band_nr)
				continue;
			if (schedule->node[j].band_id[band_nr] == i) {
				n_band++;
				break;
			}
		}
	}
	for (j = 0; j < schedule->n; ++j)
		if (schedule->node[j].n_band <= band_nr)
			n_band++;

	if (n_band == 1) {
		isl_band *band;
		list = isl_band_list_alloc(ctx, n_band);
		band = construct_band(schedule, parent, band_nr,
					parent_active, n_active);
		return isl_band_list_add(list, band);
	}

	active = isl_alloc_array(ctx, int, schedule->n);
	if (schedule->n && !active)
		return NULL;

	list = isl_band_list_alloc(ctx, n_band);

	for (i = 0; i < n_active; ++i) {
		int n = 0;
		isl_band *band;

		for (j = 0; j < schedule->n; ++j) {
			active[j] = parent_active[j] &&
					schedule->node[j].n_band > band_nr &&
					schedule->node[j].band_id[band_nr] == i;
			if (active[j])
				n++;
		}
		if (n == 0)
			continue;

		band = construct_band(schedule, parent, band_nr, active, n);

		list = isl_band_list_add(list, band);
	}
	for (i = 0; i < schedule->n; ++i) {
		isl_band *band;
		if (!parent_active[i])
			continue;
		if (schedule->node[i].n_band > band_nr)
			continue;
		for (j = 0; j < schedule->n; ++j)
			active[j] = j == i;
		band = construct_band(schedule, parent, band_nr, active, 1);
		list = isl_band_list_add(list, band);
	}

	free(active);

	list = sort_band_list(list, parent);

	return list;
}

/* Construct a band forest representation of the schedule and
 * return the list of roots.
 */
static __isl_give isl_band_list *construct_forest(
	__isl_keep isl_schedule *schedule)
{
	int i;
	isl_ctx *ctx = isl_schedule_get_ctx(schedule);
	isl_band_list *forest;
	int *active;

	active = isl_alloc_array(ctx, int, schedule->n);
	if (schedule->n && !active)
		return NULL;

	for (i = 0; i < schedule->n; ++i)
		active[i] = 1;

	forest = construct_band_list(schedule, NULL, 0, active, schedule->n);

	free(active);

	return forest;
}

/* Return the roots of a band forest representation of the schedule.
 */
__isl_give isl_band_list *isl_schedule_get_band_forest(
	__isl_keep isl_schedule *schedule)
{
	if (!schedule)
		return NULL;
	if (!schedule->band_forest)
		schedule->band_forest = construct_forest(schedule);
	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;
}

__isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
	__isl_keep isl_schedule *schedule)
{
	isl_band_list *forest;

	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_print_schedule(printer, schedule);

	isl_printer_free(printer);
}