isl_schedule_constraints_compute_schedule: allow partial carrying schedule rows

[isl.git] / 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);
}