Makefile.am: add gitversion.h to BUILT_SOURCES

[ppcg.git] / hybrid.c

/*
 * Copyright 2013      Ecole Normale Superieure
 * Copyright 2015      Sven Verdoolaege
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege,
 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
 */

#include <string.h>

#include <isl/space.h>
#include <isl/constraint.h>
#include <isl/val.h>
#include <isl/aff.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_set.h>
#include <isl/union_map.h>

#include "hybrid.h"
#include "schedule.h"

/* The hybrid tiling implemented in this file is based on
 * Grosser et al., "Hybrid Hexagonal/Classical Tiling for GPUs".
 */

/* Bounds on relative dependence distances in input to hybrid tiling.
 * upper is an upper bound on the relative dependence distances
 * in the first space dimension
 * -lower is a lower bound on the relative dependence distances
 * in all space dimensions.
 *
 * In particular,
 *
 *      d_i >= -lower_i d_0
 * and
 *      d_1 <= upper d_0
 *
 * for each dependence distance vector d, where d_1 is the component
 * corresponding to the first space dimension.
 *
 * upper and lower are always non-negative.
 * Some of the values may be NaN if no bound could be found.
 */
struct ppcg_ht_bounds {
        isl_val *upper;
        isl_multi_val *lower;
};

/* Free "bounds" along with all its fields.
 */
__isl_null ppcg_ht_bounds *ppcg_ht_bounds_free(
        __isl_take ppcg_ht_bounds *bounds)
{
        if (!bounds)
                return NULL;
        isl_val_free(bounds->upper);
        isl_multi_val_free(bounds->lower);
        free(bounds);

        return NULL;
}

/* Create a ppcg_ht_bounds object for a band living in "space".
 * The bounds are initialized to NaN.
 */
__isl_give ppcg_ht_bounds *ppcg_ht_bounds_alloc(__isl_take isl_space *space)
{
        int i, n;
        isl_ctx *ctx;
        ppcg_ht_bounds *bounds;

        if (!space)
                return NULL;

        ctx = isl_space_get_ctx(space);
        bounds = isl_alloc_type(ctx, struct ppcg_ht_bounds);
        if (!bounds)
                goto error;
        bounds->upper = isl_val_nan(ctx);
        bounds->lower = isl_multi_val_zero(space);
        n = isl_multi_val_dim(bounds->lower, isl_dim_set);
        for (i = 0; i < n; ++i) {
                isl_val *v = isl_val_copy(bounds->upper);
                bounds->lower = isl_multi_val_set_val(bounds->lower, i, v);
        }

        if (!bounds->lower || !bounds->upper)
                return ppcg_ht_bounds_free(bounds);

        return bounds;
error:
        isl_space_free(space);
        return NULL;
}

void ppcg_ht_bounds_dump(__isl_keep ppcg_ht_bounds *bounds)
{
        if (!bounds)
                return;

        fprintf(stderr, "lower: ");
        isl_multi_val_dump(bounds->lower);
        fprintf(stderr, "upper: ");
        isl_val_dump(bounds->upper);
}

/* Return the upper bound on the relative dependence distances
 * in the first space dimension.
 */
__isl_give isl_val *ppcg_ht_bounds_get_upper(__isl_keep ppcg_ht_bounds *bounds)
{
        if (!bounds)
                return NULL;
        return isl_val_copy(bounds->upper);
}

/* Replace the upper bound on the relative dependence distances
 * in the first space dimension by "upper".
 */
__isl_give ppcg_ht_bounds *ppcg_ht_bounds_set_upper(
        __isl_take ppcg_ht_bounds *bounds, __isl_take isl_val *upper)
{
        if (!bounds || !upper)
                goto error;
        isl_val_free(bounds->upper);
        bounds->upper = upper;
        return bounds;
error:
        ppcg_ht_bounds_free(bounds);
        isl_val_free(upper);
        return NULL;
}

/* Return the lower bound on the relative dependence distances
 * in space dimension "pos".
 */
__isl_give isl_val *ppcg_ht_bounds_get_lower(__isl_keep ppcg_ht_bounds *bounds,
        int pos)
{
        if (!bounds)
                return NULL;
        return isl_multi_val_get_val(bounds->lower, pos);
}

/* Replace the lower bound on the relative dependence distances
 * in space dimension "pos" by "lower".
 */
__isl_give ppcg_ht_bounds *ppcg_ht_bounds_set_lower(
        __isl_take ppcg_ht_bounds *bounds, int pos, __isl_take isl_val *lower)
{
        if (!bounds || !lower)
                goto error;
        bounds->lower = isl_multi_val_set_val(bounds->lower, pos, lower);
        if (!bounds->lower)
                return ppcg_ht_bounds_free(bounds);
        return bounds;
error:
        ppcg_ht_bounds_free(bounds);
        isl_val_free(lower);
        return NULL;
}

/* Can the bounds on relative dependence distances recorded in "bounds"
 * be used to perform hybrid tiling?
 * In particular, have appropriate lower and upper bounds been found?
 * Any NaN indicates that no corresponding bound was found.
 */
isl_bool ppcg_ht_bounds_is_valid(__isl_keep ppcg_ht_bounds *bounds)
{
        isl_bool is_nan;
        int i, n;

        if (!bounds)
                return isl_bool_error;
        is_nan = isl_val_is_nan(bounds->upper);
        if (is_nan < 0)
                return isl_bool_error;
        if (is_nan)
                return isl_bool_false;

        n = isl_multi_val_dim(bounds->lower, isl_dim_set);
        for (i = 0; i < n; ++i) {
                isl_val *v;

                v = isl_multi_val_get_val(bounds->lower, i);
                is_nan = isl_val_is_nan(v);
                if (is_nan < 0)
                        return isl_bool_error;
                if (is_nan)
                        return isl_bool_false;
                isl_val_free(v);
        }

        return isl_bool_true;
}

/* Structure that represents the basic hexagonal tiling,
 * along with information that is needed to perform the hybrid tiling.
 *
 * "bounds" are the bounds on the dependence distances that
 * define the hexagonal shape and the required skewing in the remaining
 * space dimensions.
 *
 * "input_node" points to the input pair of band nodes.
 * "input_schedule" is the partial schedule of this input pair of band nodes.
 * The space of this schedule is [P -> C], where P is the space
 * of the parent node and C is the space of the child node.
 *
 * "space_sizes" represent the total size of a tile for the space
 * dimensions, i.e., those corresponding to the child node.
 * The space of "space_sizes" is C.
 * If S_0 is the original tile size in the first space dimension,
 * then the first entry of "space_sizes" is equal to
 * W = 2*S_0 + floor(d_l h) + floor(d_u h).
 * The remaining entries are the same as in the original tile sizes.
 *
 * The basic hexagonal tiling "hex" is defined
 * in a "ts" (time-space) space and corresponds to the phase-1 tiles.
 * "time_tile" maps the "ts" space to outer time tile.
 * Is is equal to ts[t, s] -> floor(t/(2 * S_t)), with S_t the original tile
 * size corresponding to the parent node.
 * "local_time" maps the "ts" space to the time dimension inside each tile.
 * It is equal to ts[t, s] -> t mod (2 S_t), with S_t the original tile
 * size corresponding to the parent node.
 * "shift_space" shifts the tiles at time tile T = floor(t/(2 S_t))
 * in the space dimension such that they align to a multiple of W.
 * It is equal to ts[t, s] -> s + (-(2 * shift_s)*T) % W,
 * with shift_s = S_0 + floor(d_u h).
 * "shift_phase" is the shift taken to go from phase 0 to phase 1
 * It is equal to ts[t, s] -> ts[t + S_t, s + shift_s],
 * with shift_s = S_0 + floor(d_u h).
 *
 * "project_ts" projects the space of the input schedule to the ts-space.
 * It is equal to [P[t] -> C[s_0, ...]] -> ts[t, s_0].
 */
struct ppcg_ht_tiling {
        int ref;

        ppcg_ht_bounds *bounds;
        isl_schedule_node *input_node;
        isl_multi_union_pw_aff *input_schedule;

        isl_multi_val *space_sizes;

        isl_aff *time_tile;
        isl_aff *local_time;
        isl_aff *shift_space;
        isl_multi_aff *shift_phase;
        isl_set *hex;

        isl_multi_aff *project_ts;
};
typedef struct ppcg_ht_tiling ppcg_ht_tiling;

/* Return the space of the pair of band nodes that form the input
 * to the hybrid tiling.
 * In particular, return the space [P -> C], where P is the space
 * of the parent node and C is the space of the child node.
 */
__isl_give isl_space *ppcg_ht_tiling_get_input_space(
        __isl_keep ppcg_ht_tiling *tile)
{
        if (!tile)
                return NULL;

        return isl_multi_union_pw_aff_get_space(tile->input_schedule);
}

/* Remove a reference to "tile" and free "tile" along with all its fields
 * as soon as the reference count drops to zero.
 */
static __isl_null ppcg_ht_tiling *ppcg_ht_tiling_free(
        __isl_take ppcg_ht_tiling *tiling)
{
        if (!tiling)
                return NULL;
        if (--tiling->ref > 0)
                return NULL;

        ppcg_ht_bounds_free(tiling->bounds);
        isl_schedule_node_free(tiling->input_node);
        isl_multi_union_pw_aff_free(tiling->input_schedule);
        isl_multi_val_free(tiling->space_sizes);
        isl_aff_free(tiling->time_tile);
        isl_aff_free(tiling->local_time);
        isl_aff_free(tiling->shift_space);
        isl_multi_aff_free(tiling->shift_phase);
        isl_set_free(tiling->hex);
        isl_multi_aff_free(tiling->project_ts);
        free(tiling);

        return NULL;
}

/* Return a new reference to "tiling".
 */
__isl_give ppcg_ht_tiling *ppcg_ht_tiling_copy(
        __isl_keep ppcg_ht_tiling *tiling)
{
        if (!tiling)
                return NULL;

        tiling->ref++;
        return tiling;
}

/* Return the isl_ctx to which "tiling" belongs.
 */
isl_ctx *ppcg_ht_tiling_get_ctx(__isl_keep ppcg_ht_tiling *tiling)
{
        if (!tiling)
                return NULL;

        return isl_multi_union_pw_aff_get_ctx(tiling->input_schedule);
}

/* Representation of one of the two phases of hybrid tiling.
 *
 * "tiling" points to the shared tiling data.
 *
 * "time_tile", "local_time" and "shift_space" are equal to the corresponding
 * fields of "tiling", pulled back to the input space.
 * In case of phase 0, these expressions have also been moved
 * from phase 1 to phase 0.
 *
 * "domain" contains the hexagonal tiling of this phase.
 *
 * "space_shift" is the shift that should be added to the space band
 * in order to be able to apply rectangular tiling to the space.
 * For phase 1, it is equal to
 *
 *      [P[t] -> C[s_0, s_i]] -> C[(-(2 * shift_s)*T) % W, dl_i * u]
 *
 * with shift_s = S_0 + floor(d_u h),
 * T equal to "time_tile" and u equal to "local_time".
 * For phase 0, it is equal to
 *
 *      [P[t] -> C[s_0, s_i]] -> C[shift_s + (-(2 * shift_s)*T) % W, dl_i * u]
 *
 * "space_tile" is the space tiling.  It is equal to
 *
 *      [P[t] -> C[s]] -> C[floor((s + space_shift)/space_size]
 */
struct ppcg_ht_phase {
        ppcg_ht_tiling *tiling;

        isl_aff *time_tile;
        isl_aff *local_time;
        isl_aff *shift_space;
        isl_set *domain;

        isl_multi_aff *space_shift;
        isl_multi_aff *space_tile;
};

/* Free "phase" along with all its fields.
 */
static __isl_null ppcg_ht_phase *ppcg_ht_phase_free(
        __isl_take ppcg_ht_phase *phase)
{
        if (!phase)
                return NULL;

        ppcg_ht_tiling_free(phase->tiling);
        isl_aff_free(phase->time_tile);
        isl_aff_free(phase->local_time);
        isl_aff_free(phase->shift_space);
        isl_set_free(phase->domain);
        isl_multi_aff_free(phase->space_shift);
        isl_multi_aff_free(phase->space_tile);
        free(phase);

        return NULL;
}

/* Wrapper around ppcg_ht_phase_free for use as an argument
 * to isl_id_set_free_user.
 */
static void ppcg_ht_phase_free_wrap(void *user)
{
        ppcg_ht_phase *phase = user;

        ppcg_ht_phase_free(phase);
}

/* Return the domain of hybrid tiling phase "phase".
 */
static __isl_give isl_set *ppcg_ht_phase_get_domain(ppcg_ht_phase *phase)
{
        if (!phase)
                return NULL;

        return isl_set_copy(phase->domain);
}

/* Return the space of the pair of band nodes that form the input
 * to the hybrid tiling of which "phase" is a phase.
 * In particular, return the space [P -> C], where P is the space
 * of the parent node and C is the space of the child node.
 */
static __isl_give isl_space *ppcg_ht_phase_get_input_space(
        __isl_keep ppcg_ht_phase *phase)
{
        if (!phase)
                return NULL;

        return ppcg_ht_tiling_get_input_space(phase->tiling);
}

/* Construct the lower left constraint of the hexagonal tile, i.e.,
 *
 *      du a - b <= (2h+1) du - duh
 *      -du a + b + (2h+1) du - duh >= 0
 *
 * where duh = floor(du * h).
 *
 * This constraint corresponds to (6) in
 * "Hybrid Hexagonal/Classical Tiling for GPUs".
 */
static __isl_give isl_constraint *hex_lower_left(__isl_take isl_local_space *ls,
        __isl_keep isl_val *h, __isl_keep isl_val *du, __isl_keep isl_val *duh)
{
        isl_val *v;
        isl_aff *aff;

        v = isl_val_add_ui(isl_val_mul_ui(isl_val_copy(h), 2), 1);
        v = isl_val_mul(v, isl_val_copy(du));
        v = isl_val_sub(v, isl_val_copy(duh));
        aff = isl_aff_val_on_domain(ls, v);
        v = isl_val_neg(isl_val_copy(du));
        aff = isl_aff_set_coefficient_val(aff, isl_dim_in, 0, v);
        aff = isl_aff_set_coefficient_si(aff, isl_dim_in, 1, 1);

        return isl_inequality_from_aff(aff);
}

/* Construct the lower constraint of the hexagonal tile, i.e.,
 *
 *      a <= 2h+1
 *      -a + 2h+1 >= 0
 *
 * This constraint corresponds to (7) in
 * "Hybrid Hexagonal/Classical Tiling for GPUs".
 */
static __isl_give isl_constraint *hex_lower(__isl_take isl_local_space *ls,
        __isl_keep isl_val *h)
{
        isl_val *v;
        isl_aff *aff;

        v = isl_val_add_ui(isl_val_mul_ui(isl_val_copy(h), 2), 1);
        aff = isl_aff_val_on_domain(ls, v);
        aff = isl_aff_set_coefficient_si(aff, isl_dim_in, 0, -1);

        return isl_inequality_from_aff(aff);
}

/* Construct the lower right constraint of the hexagonal tile, i.e.,
 *
 *      dl a + b <= (2h+1) dl + duh + (s0-1)
 *      -dl a - b + (2h+1) dl + duh + (s0-1) >= 0
 *
 * where duh = floor(du * h).
 *
 * This constraint corresponds to (8) in
 * "Hybrid Hexagonal/Classical Tiling for GPUs".
 */
static __isl_give isl_constraint *hex_lower_right(
        __isl_take isl_local_space *ls, __isl_keep isl_val *h,
        __isl_keep isl_val *s0, __isl_keep isl_val *dl, __isl_keep isl_val *duh)
{
        isl_val *v;
        isl_aff *aff;

        v = isl_val_add_ui(isl_val_mul_ui(isl_val_copy(h), 2), 1);
        v = isl_val_mul(v, isl_val_copy(dl));
        v = isl_val_add(v, isl_val_copy(duh));
        v = isl_val_add(v, isl_val_copy(s0));
        v = isl_val_sub_ui(v, 1);
        aff = isl_aff_val_on_domain(ls, v);
        v = isl_val_neg(isl_val_copy(dl));
        aff = isl_aff_set_coefficient_val(aff, isl_dim_in, 0, v);
        aff = isl_aff_set_coefficient_si(aff, isl_dim_in, 1, -1);

        return isl_inequality_from_aff(aff);
}

/* Construct the upper left constraint of the hexagonal tile, i.e.,
 *
 *      dl a + b >= h dl - (d - 1)/d                            with d = den(dl)
 *      dl a + b - h dl + (d - 1)/d >= 0
 *
 * This constraint corresponds to (10) in
 * "Hybrid Hexagonal/Classical Tiling for GPUs".
 */
static __isl_give isl_constraint *hex_upper_left(__isl_take isl_local_space *ls,
        __isl_keep isl_val *h, __isl_keep isl_val *dl)
{
        isl_val *v, *d;
        isl_aff *aff;

        d = isl_val_get_den_val(dl);
        v = isl_val_sub_ui(isl_val_copy(d), 1);
        v = isl_val_div(v, d);
        v = isl_val_sub(v, isl_val_mul(isl_val_copy(h), isl_val_copy(dl)));
        aff = isl_aff_val_on_domain(ls, v);
        aff = isl_aff_set_coefficient_val(aff, isl_dim_in, 0, isl_val_copy(dl));
        aff = isl_aff_set_coefficient_si(aff, isl_dim_in, 1, 1);

        return isl_inequality_from_aff(aff);
}

/* Construct the upper right constraint of the hexagonal tile, i.e.,
 *
 *      du a - b >= du h - duh - (s0-1) - dlh - (d - 1)/d       with d = den(du)
 *      du a - b - du h + duh + (s0-1) + dlh + (d - 1)/d >= 0
 *
 * where dlh = floor(dl * h) and duh = floor(du * h).
 *
 * This constraint corresponds to (12) in
 * "Hybrid Hexagonal/Classical Tiling for GPUs".
 */
static __isl_give isl_constraint *hex_upper_right(
        __isl_take isl_local_space *ls, __isl_keep isl_val *h,
        __isl_keep isl_val *s0, __isl_keep isl_val *du,
        __isl_keep isl_val *dlh, __isl_keep isl_val *duh)
{
        isl_val *v, *d;
        isl_aff *aff;

        d = isl_val_get_den_val(du);
        v = isl_val_sub_ui(isl_val_copy(d), 1);
        v = isl_val_div(v, d);
        v = isl_val_sub(v, isl_val_mul(isl_val_copy(h), isl_val_copy(du)));
        v = isl_val_add(v, isl_val_copy(duh));
        v = isl_val_add(v, isl_val_copy(dlh));
        v = isl_val_add(v, isl_val_copy(s0));
        v = isl_val_sub_ui(v, 1);
        aff = isl_aff_val_on_domain(ls, v);
        aff = isl_aff_set_coefficient_val(aff, isl_dim_in, 0, isl_val_copy(du));
        aff = isl_aff_set_coefficient_si(aff, isl_dim_in, 1, -1);

        return isl_inequality_from_aff(aff);
}

/* Construct the uppper constraint of the hexagonal tile, i.e.,
 *
 *      a >= 0
 *
 * This constraint corresponds to (13) in
 * "Hybrid Hexagonal/Classical Tiling for GPUs".
 */
static __isl_give isl_constraint *hex_upper(__isl_take isl_local_space *ls)
{
        isl_aff *aff;

        aff = isl_aff_var_on_domain(ls, isl_dim_set, 0);

        return isl_inequality_from_aff(aff);
}

/* Construct the basic hexagonal tile shape.
 * "space" is the 2D space in which the hexagon should be constructed.
 * h is st-1, with st the tile size in the time dimension
 * s0 is the tile size in the space dimension
 * dl is a bound on the negative relative dependence distances, i.e.,
 *
 *      d_s >= -dl d_t
 *
 * du is a bound on the positive relative dependence distances, i.e.,
 *
 *      d_s <= du d_t
 *
 * with (d_t,d_s) any dependence distance vector.
 * dlh = floor(dl * h)
 * duh = floor(du * h)
 *
 * The shape of the hexagon is as follows:
 *
 *              0 dlh   dlh+s0-1
 *                 ______                __
 * 0              /      \_             /
 *               /         \_          /
 * h            /            \ ______ /
 * h+1          \_           //      \\_
 *                \_        //         \\_
 * 2h+1             \______//            \\
 *              0   duh   duh+s0-1
 *                           duh+s0-1+dlh
 *                                duh+s0-1+dlh+1+s0+1
 *
 * The next hexagon is shifted by duh + dlh + 2 * s0.
 *
 * The slope of the "/" constraints is dl.
 * The slope of the "\_" constraints is du.
 */
static __isl_give isl_set *compute_hexagon(__isl_take isl_space *space,
        __isl_keep isl_val *h, __isl_keep isl_val *s0,
        __isl_keep isl_val *dl, __isl_keep isl_val *du,
        __isl_keep isl_val *dlh, __isl_keep isl_val *duh)
{
        isl_local_space *ls;
        isl_constraint *c;
        isl_basic_set *bset;

        ls = isl_local_space_from_space(space);

        c = hex_lower_left(isl_local_space_copy(ls), h, du, duh);
        bset = isl_basic_set_from_constraint(c);

        c = hex_lower(isl_local_space_copy(ls), h);
        bset = isl_basic_set_add_constraint(bset, c);

        c = hex_lower_right(isl_local_space_copy(ls), h, s0, dl, duh);
        bset = isl_basic_set_add_constraint(bset, c);

        c = hex_upper_left(isl_local_space_copy(ls), h, dl);
        bset = isl_basic_set_add_constraint(bset, c);

        c = hex_upper_right(isl_local_space_copy(ls), h, s0, du, dlh, duh);
        bset = isl_basic_set_add_constraint(bset, c);

        c = hex_upper(ls);
        bset = isl_basic_set_add_constraint(bset, c);

        return isl_set_from_basic_set(bset);
}

/* Name of the ts-space.
 */
static const char *ts_space_name = "ts";

/* Construct and return the space ts[t, s].
 */
static __isl_give isl_space *construct_ts_space(isl_ctx *ctx)
{
        isl_space *s;

        s = isl_space_set_alloc(ctx, 0, 2);
        s = isl_space_set_tuple_name(s, isl_dim_set, ts_space_name);

        return s;
}

/* Name of the local ts-space.
 */
static const char *local_ts_space_name = "local_ts";

/* Construct and return the space local_ts[t, s].
 */
static __isl_give isl_space *construct_local_ts_space(isl_ctx *ctx)
{
        isl_space *s;

        s = isl_space_set_alloc(ctx, 0, 2);
        s = isl_space_set_tuple_name(s, isl_dim_set, local_ts_space_name);

        return s;
}

/* Compute the total size of a tile for the space dimensions,
 * i.e., those corresponding to the child node
 * of the input pattern.
 * If S_0 is the original tile size in the first space dimension,
 * then the first entry of "space_sizes" is equal to
 * W = 2*S_0 + floor(d_l h) + floor(d_u h).
 * The remaining entries are the same as in the original tile sizes.
 * "tile_sizes" contains the original tile sizes, including
 * the tile size corresponding to the parent node.
 * "dlh" is equal to floor(d_l h).
 * "duh" is equal to floor(d_u h).
 */
static __isl_give isl_multi_val *compute_space_sizes(
        __isl_keep isl_multi_val *tile_sizes,
        __isl_keep isl_val *dlh, __isl_keep isl_val *duh)
{
        isl_val *size;
        isl_multi_val *space_sizes;

        space_sizes = isl_multi_val_copy(tile_sizes);
        space_sizes = isl_multi_val_factor_range(space_sizes);
        size = isl_multi_val_get_val(space_sizes, 0);
        size = isl_val_mul_ui(size, 2);
        size = isl_val_add(size, isl_val_copy(duh));
        size = isl_val_add(size, isl_val_copy(dlh));
        space_sizes = isl_multi_val_set_val(space_sizes, 0, size);

        return space_sizes;
}

/* Compute the offset of phase 1 with respect to phase 0
 * in the ts-space ("space").
 * In particular, return
 *
 *      ts[st, s0 + duh]
 */
static __isl_give isl_multi_val *compute_phase_shift(
        __isl_keep isl_space *space, __isl_keep isl_val *st,
        __isl_keep isl_val *s0, __isl_keep isl_val *duh)
{
        isl_val *v;
        isl_multi_val *phase_shift;

        phase_shift = isl_multi_val_zero(isl_space_copy(space));
        phase_shift = isl_multi_val_set_val(phase_shift, 0, isl_val_copy(st));
        v = isl_val_add(isl_val_copy(duh), isl_val_copy(s0));
        phase_shift = isl_multi_val_set_val(phase_shift, 1, v);

        return phase_shift;
}

/* Return the function
 *
 *      ts[t, s] -> floor(t/(2 * st))
 *
 * representing the time tile.
 * "space" is the space ts[t, s].
 */
static __isl_give isl_aff *compute_time_tile(__isl_keep isl_space *space,
        __isl_keep isl_val *st)
{
        isl_val *v;
        isl_aff *t;
        isl_local_space *ls;

        ls = isl_local_space_from_space(isl_space_copy(space));
        t = isl_aff_var_on_domain(ls, isl_dim_set, 0);
        v = isl_val_mul_ui(isl_val_copy(st), 2);
        t = isl_aff_floor(isl_aff_scale_down_val(t, v));

        return t;
}

/* Compute a shift in the space dimension for tiles
 * at time tile T = floor(t/(2 * S_t))
 * such that they align to a multiple of the total space tile dimension W.
 * In particular, compute
 *
 *      ts[t, s] -> s + (-(2 * shift_s)*T) % W
 *
 * where shift_s is the shift of phase 1 with respect to phase 0
 * in the space dimension (the first element of "phase_shift").
 * W is stored in the first element of "space_sizes".
 * "time_tile" is the function
 *
 *      ts[t, s] -> floor(t/(2 * S_T))
 *
 * Since phase 1 is shifted by shift_s with respect to phase 0,
 * the next line of phase 0 (at T+1) is shifted by 2*shift_s
 * with respect to the previous line (at T).
 * A shift of -(2 * shift_s)*T therefore allows the basic pattern
 * (which starts at 0) to be applied.
 * However, this shift will be used to obtain the tile coordinate
 * in the first space dimension and if the original values
 * in the space dimension are non-negative, then the shift should
 * not make them negative.  Moreover, the shift should be as minimal
 * as possible.
 * Since the pattern repeats itself with a period of W in the space
 * dimension, the shift can be replaced by (-(2 * shift_s)*T) % W.
 */
static __isl_give isl_aff *compute_shift_space(__isl_keep isl_aff *time_tile,
        __isl_keep isl_multi_val *space_sizes,
        __isl_keep isl_multi_val *phase_shift)
{
        isl_val *v;
        isl_aff *s, *t;
        isl_local_space *ls;

        ls = isl_local_space_from_space(isl_aff_get_domain_space(time_tile));
        t = isl_aff_copy(time_tile);
        v = isl_val_mul_ui(isl_multi_val_get_val(phase_shift, 1), 2);
        v = isl_val_neg(v);
        t = isl_aff_scale_val(t, v);
        v = isl_multi_val_get_val(space_sizes, 0);
        t = isl_aff_mod_val(t, v);
        s = isl_aff_var_on_domain(ls, isl_dim_set, 1);
        s = isl_aff_add(s, t);

        return s;
}

/* Give the phase_shift ts[S_t, S_0 + floor(d_u h)],
 * compute a function that applies the shift, i.e.,
 *
 *      ts[t, s] -> ts[t + S_t, s + S_0 + floor(d_u h)],
 */
static __isl_give isl_multi_aff *compute_shift_phase(
        __isl_keep isl_multi_val *phase_shift)
{
        isl_space *space;
        isl_multi_aff *shift;

        space = isl_multi_val_get_space(phase_shift);
        shift = isl_multi_aff_multi_val_on_space(space,
                                        isl_multi_val_copy(phase_shift));
        space = isl_multi_aff_get_space(shift);
        shift = isl_multi_aff_add(shift, isl_multi_aff_identity(space));

        return shift;
}

/* Compute a mapping from the ts-space to the local coordinates
 * within each tile.  In particular, compute
 *
 *      ts[t, s] -> local_ts[t % (2 S_t), (s + (-(2 * shift_s)*T) % W) % W]
 *
 * "ts" is the space ts[t, s]
 * "local_ts" is the space local_ts[t, s]
 * "shift_space" is equal to ts[t, s] -> s + (-(2 * shift_s)*T) % W
 * "st" is the tile size in the time dimension S_t.
 * The first element of "space_sizes" is equal to W.
 */
static __isl_give isl_multi_aff *compute_localize(
        __isl_keep isl_space *local_ts, __isl_keep isl_aff *shift_space,
        __isl_keep isl_val *st, __isl_keep isl_multi_val *space_sizes)
{
        isl_val *v;
        isl_space *space;
        isl_aff *s, *t;
        isl_multi_aff *localize;

        space = isl_aff_get_domain_space(shift_space);
        local_ts = isl_space_copy(local_ts);
        space = isl_space_map_from_domain_and_range(space, local_ts);
        localize = isl_multi_aff_identity(space);
        t = isl_multi_aff_get_aff(localize, 0);
        v = isl_val_mul_ui(isl_val_copy(st), 2);
        t = isl_aff_mod_val(t, v);
        localize = isl_multi_aff_set_aff(localize, 0, t);
        s = isl_aff_copy(shift_space);
        v = isl_multi_val_get_val(space_sizes, 0);
        s = isl_aff_mod_val(s, v);
        localize = isl_multi_aff_set_aff(localize, 1, s);

        return localize;
}

/* Set the project_ts field of "tiling".
 *
 * This field projects the space of the input schedule to the ts-space.
 * It is equal to [P[t] -> C[s_0, ...]] -> ts[t, s_0].
 */
static __isl_give ppcg_ht_tiling *ppcg_ht_tiling_set_project_ts(
        __isl_take ppcg_ht_tiling *tiling)
{
        int n;
        isl_space *space;
        isl_multi_aff *project;

        if (!tiling)
                return NULL;

        space = ppcg_ht_tiling_get_input_space(tiling);
        n = isl_space_dim(space, isl_dim_set);
        project = isl_multi_aff_project_out_map(space, isl_dim_set, 2, n - 2);
        project = isl_multi_aff_set_tuple_name(project,
                                                isl_dim_out, ts_space_name);
        if (!project)
                return ppcg_ht_tiling_free(tiling);

        tiling->project_ts = project;

        return tiling;
}

/* Construct a hybrid tiling description from bounds on the dependence
 * distances "bounds".
 * "input_node" points to the original parent node.
 * "input_schedule" is the combined schedule of the parent and child
 * node in the input.
 * "tile_sizes" are the original, user specified tile sizes.
 */
static __isl_give ppcg_ht_tiling *ppcg_ht_bounds_construct_tiling(
        __isl_take ppcg_ht_bounds *bounds,
        __isl_keep isl_schedule_node *input_node,
        __isl_keep isl_multi_union_pw_aff *input_schedule,
        __isl_keep isl_multi_val *tile_sizes)
{
        isl_ctx *ctx;
        ppcg_ht_tiling *tiling;
        isl_multi_val *space_sizes, *phase_shift;
        isl_aff *time_tile, *shift_space;
        isl_multi_aff *localize;
        isl_val *h, *duh, *dlh;
        isl_val *st, *s0, *du, *dl;
        isl_space *ts, *local_ts;

        if (!bounds || !input_node || !input_schedule || !tile_sizes)
                goto error;

        ctx = isl_multi_union_pw_aff_get_ctx(input_schedule);
        tiling = isl_calloc_type(ctx, struct ppcg_ht_tiling);
        if (!tiling)
                goto error;
        tiling->ref = 1;

        st = isl_multi_val_get_val(tile_sizes, 0);
        h = isl_val_sub_ui(isl_val_copy(st), 1);
        s0 = isl_multi_val_get_val(tile_sizes, 1);
        du = ppcg_ht_bounds_get_upper(bounds);
        dl = ppcg_ht_bounds_get_lower(bounds, 0);

        duh = isl_val_floor(isl_val_mul(isl_val_copy(du), isl_val_copy(h)));
        dlh = isl_val_floor(isl_val_mul(isl_val_copy(dl), isl_val_copy(h)));

        ts = construct_ts_space(ctx);
        local_ts = construct_local_ts_space(ctx);

        space_sizes = compute_space_sizes(tile_sizes, dlh, duh);
        phase_shift = compute_phase_shift(ts, st, s0, duh);
        time_tile = compute_time_tile(ts, st);
        shift_space = compute_shift_space(time_tile, space_sizes, phase_shift);
        localize = compute_localize(local_ts, shift_space, st, space_sizes);
        isl_space_free(ts);

        tiling->input_node = isl_schedule_node_copy(input_node);
        tiling->input_schedule = isl_multi_union_pw_aff_copy(input_schedule);
        tiling->space_sizes = space_sizes;
        tiling->bounds = bounds;
        tiling->local_time = isl_multi_aff_get_aff(localize, 0);
        tiling->hex = compute_hexagon(local_ts, h, s0, dl, du, dlh, duh);
        tiling->hex = isl_set_preimage_multi_aff(tiling->hex, localize);
        tiling->time_tile = time_tile;
        tiling->shift_space = shift_space;
        tiling->shift_phase = compute_shift_phase(phase_shift);
        isl_multi_val_free(phase_shift);

        isl_val_free(duh);
        isl_val_free(dlh);
        isl_val_free(du);
        isl_val_free(dl);
        isl_val_free(s0);
        isl_val_free(st);
        isl_val_free(h);

        if (!tiling->input_schedule || !tiling->local_time || !tiling->hex ||
            !tiling->shift_space || !tiling->shift_phase)
                return ppcg_ht_tiling_free(tiling);

        tiling = ppcg_ht_tiling_set_project_ts(tiling);

        return tiling;
error:
        ppcg_ht_bounds_free(bounds);
        return NULL;
}

/* Are all members of the band node "node" coincident?
 */
static isl_bool all_coincident(__isl_keep isl_schedule_node *node)
{
        int i, n;

        n = isl_schedule_node_band_n_member(node);
        for (i = 0; i < n; ++i) {
                isl_bool c;

                c = isl_schedule_node_band_member_get_coincident(node, i);
                if (c < 0 || !c)
                        return c;
        }

        return isl_bool_true;
}

/* Does "node" satisfy the properties of the inner node in the input
 * pattern for hybrid tiling?
 * That is, is it a band node with only coincident members, of which
 * there is at least one?
 */
static isl_bool has_child_properties(__isl_keep isl_schedule_node *node)
{
        if (!node)
                return isl_bool_error;
        if (isl_schedule_node_get_type(node) != isl_schedule_node_band)
                return isl_bool_false;
        if (isl_schedule_node_band_n_member(node) < 1)
                return isl_bool_false;
        return all_coincident(node);
}

/* Does "node" satisfy the properties of the outer node in the input
 * pattern for hybrid tiling?
 * That is, is it a band node with a single member?
 */
static isl_bool has_parent_properties(__isl_keep isl_schedule_node *node)
{
        if (!node)
                return isl_bool_error;
        if (isl_schedule_node_get_type(node) != isl_schedule_node_band)
                return isl_bool_false;
        if (isl_schedule_node_band_n_member(node) != 1)
                return isl_bool_false;
        return isl_bool_true;
}

/* Does the parent of "node" satisfy the input patttern for hybrid tiling?
 * That is, does "node" satisfy the properties of the inner node and
 * does the parent of "node" satisfy the properties of the outer node?
 */
isl_bool ppcg_ht_parent_has_input_pattern(__isl_keep isl_schedule_node *node)
{
        isl_bool has_pattern;

        has_pattern = has_child_properties(node);
        if (has_pattern < 0 || !has_pattern)
                return has_pattern;

        node = isl_schedule_node_copy(node);
        node = isl_schedule_node_parent(node);
        has_pattern = has_parent_properties(node);
        isl_schedule_node_free(node);

        return has_pattern;
}

/* Does "node" satisfy the input patttern for hybrid tiling?
 * That is, does "node" satisfy the properties of the outer node and
 * does the child of "node" satisfy the properties of the inner node?
 */
isl_bool ppcg_ht_has_input_pattern(__isl_keep isl_schedule_node *node)
{
        isl_bool has_pattern;

        has_pattern = has_parent_properties(node);
        if (has_pattern < 0 || !has_pattern)
                return has_pattern;

        node = isl_schedule_node_get_child(node, 0);
        has_pattern = has_child_properties(node);
        isl_schedule_node_free(node);

        return has_pattern;
}

/* Check that "node" satisfies the input pattern for hybrid tiling.
 * Error out if it does not.
 */
static isl_stat check_input_pattern(__isl_keep isl_schedule_node *node)
{
        isl_bool has_pattern;

        has_pattern = ppcg_ht_has_input_pattern(node);
        if (has_pattern < 0)
                return isl_stat_error;
        if (!has_pattern)
                isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
                        "invalid input pattern for hybrid tiling",
                        return isl_stat_error);

        return isl_stat_ok;
}

/* Extract the input schedule from "node", i.e., the product
 * of the partial schedules of the parent and child nodes
 * in the input pattern.
 */
static __isl_give isl_multi_union_pw_aff *extract_input_schedule(
        __isl_keep isl_schedule_node *node)
{
        isl_multi_union_pw_aff *partial, *partial2;

        partial = isl_schedule_node_band_get_partial_schedule(node);
        node = isl_schedule_node_get_child(node, 0);
        partial2 = isl_schedule_node_band_get_partial_schedule(node);
        isl_schedule_node_free(node);

        return isl_multi_union_pw_aff_range_product(partial, partial2);
}

/* Collect all dependences from "scop" that are relevant for performing
 * hybrid tiling on "node" and its child and map them to the schedule
 * space of this pair of nodes.
 *
 * In case live range reordering is not used,
 * the flow and the false dependences are collected.
 * In case live range reordering is used,
 * the flow and the forced dependences are collected, as well
 * as the order dependences that are adjacent to non-local
 * flow dependences.
 *
 * In all cases, only dependences that map to the same instance
 * of the outer part of the schedule are considered.
 */
static __isl_give isl_map *collect_deps(struct ppcg_scop *scop,
        __isl_keep isl_schedule_node *node)
{
        isl_space *space;
        isl_multi_union_pw_aff *prefix, *partial;
        isl_union_map *flow, *other, *dep, *umap;
        isl_map *map;

        prefix = isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node);
        partial = extract_input_schedule(node);
        space = isl_multi_union_pw_aff_get_space(partial);

        flow = isl_union_map_copy(scop->dep_flow);
        flow = isl_union_map_eq_at_multi_union_pw_aff(flow,
                                        isl_multi_union_pw_aff_copy(prefix));
        if (!scop->options->live_range_reordering) {
                other = isl_union_map_copy(scop->dep_false);
                other = isl_union_map_eq_at_multi_union_pw_aff(other, prefix);
        } else {
                isl_union_map *local, *non_local, *order, *adj;
                isl_union_set *domain, *range;

                other = isl_union_map_copy(scop->dep_forced);
                other = isl_union_map_eq_at_multi_union_pw_aff(other,
                                        isl_multi_union_pw_aff_copy(prefix));
                local = isl_union_map_copy(flow);
                local = isl_union_map_eq_at_multi_union_pw_aff(local,
                                        isl_multi_union_pw_aff_copy(partial));
                non_local = isl_union_map_copy(flow);
                non_local = isl_union_map_subtract(non_local, local);

                order = isl_union_map_copy(scop->dep_order);
                order = isl_union_map_eq_at_multi_union_pw_aff(order, prefix);
                adj = isl_union_map_copy(order);
                domain = isl_union_map_domain(isl_union_map_copy(non_local));
                domain = isl_union_set_coalesce(domain);
                adj = isl_union_map_intersect_range(adj, domain);
                other = isl_union_map_union(other, adj);

                adj = order;
                range = isl_union_map_range(non_local);
                range = isl_union_set_coalesce(range);
                adj = isl_union_map_intersect_domain(adj, range);
                other = isl_union_map_union(other, adj);
        }
        dep = isl_union_map_union(flow, other);

        umap = isl_union_map_from_multi_union_pw_aff(partial);
        dep = isl_union_map_apply_domain(dep, isl_union_map_copy(umap));
        dep = isl_union_map_apply_range(dep, umap);

        space = isl_space_map_from_set(space);
        map = isl_union_map_extract_map(dep, space);
        isl_union_map_free(dep);

        map = isl_map_coalesce(map);

        return map;
}

/* Given a constraint of the form
 *
 *      a i_0 + b i_1 >= 0
 * or
 *      a i_0 + b i_1 = 0
 *
 * use it to update one or both of the non-negative bounds
 * in "list" = (min, max) such that
 *
 *      i_1 >= -min i_0
 * and
 *      i_1 <= max i_0
 *
 * If b = 0, then the constraint cannot be used.
 * Otherwise, the constraint is equivalent to
 *
 *      sgn(b) i_1 >= - a/abs(b) i_0
 * i.e.,
 *      i_1 >= - a/abs(b) i_0
 * or
 *      i_1 <= a/abs(b) i_0
 *
 * Set the first or second element of "list" to max(0, a/abs(b)),
 * according to the sign of "b".  Or set both in case the constraint
 * is an equality, taking into account the sign change.
 */
static __isl_give isl_val_list *list_set_min_max(__isl_take isl_val_list *list,
        __isl_keep isl_constraint *c)
{
        isl_val *a, *b;
        int sign;
        int pos;
        isl_bool eq, is_zero, is_neg;

        eq = isl_constraint_is_equality(c);
        if (eq < 0)
                return isl_val_list_free(list);

        b = isl_constraint_get_coefficient_val(c, isl_dim_set, 1);
        is_zero = isl_val_is_zero(b);
        if (is_zero == isl_bool_true) {
                isl_val_free(b);
                return list;
        }
        a = isl_constraint_get_coefficient_val(c, isl_dim_set, 0);
        sign = isl_val_sgn(b);
        b = isl_val_abs(b);
        a = isl_val_div(a, b);

        if (eq)
                b = isl_val_copy(a);

        pos = sign > 0 ? 0 : 1;
        is_neg = isl_val_is_neg(a);
        if (is_neg == isl_bool_true)
                a = isl_val_set_si(a, 0);
        list = isl_val_list_set_val(list, pos, a);

        if (!eq)
                return is_neg < 0 ? isl_val_list_free(list) : list;

        pos = 1 - pos;
        a = isl_val_neg(b);
        is_neg = isl_val_is_neg(a);
        if (is_neg == isl_bool_true)
                a = isl_val_set_si(a, 0);
        list = isl_val_list_set_val(list, pos, a);

        return is_neg < 0 ? isl_val_list_free(list) : list;
}

/* If constraint "c" passes through the origin, then try and use it
 * to update the non-negative bounds in "list" = (min, max) such that
 *
 *      i_1 >= -min i_0
 * and
 *      i_1 <= max i_0
 */
static isl_stat set_min_max(__isl_take isl_constraint *c, void *user)
{
        isl_val *v;
        isl_val_list **list = user;
        isl_bool is_zero;

        v = isl_constraint_get_constant_val(c);
        is_zero = isl_val_is_zero(v);
        isl_val_free(v);

        if (is_zero == isl_bool_true)
                *list = list_set_min_max(*list, c);

        isl_constraint_free(c);
        return is_zero < 0 ? isl_stat_error : isl_stat_ok;
}

/* Given a set of dependence distance vectors "dist", compute
 * pair of non-negative bounds min and max such that
 *
 *      d_pos >= -min d_0
 * and
 *      d_pos <= max d_0
 *
 * and return the pair (min, max).
 * If no bound can be found in either direction, then the bound
 * is replaced by NaN.
 *
 * The dependence distances are first projected onto the (d_0, d_pos).
 * Then the zero dependence distance is added and the convex hull is computed.
 * Finally, the bounds are extracted from the constraints of the convex hull
 * that pass through the origin.
 */
static __isl_give isl_val_list *min_max_dist(__isl_keep isl_set *dist, int pos)
{
        isl_space *space;
        isl_basic_set *hull;
        int dim;
        isl_ctx *ctx;
        isl_val *nan;
        isl_val_list *list;

        ctx = isl_set_get_ctx(dist);
        nan = isl_val_nan(ctx);
        list = isl_val_list_alloc(ctx, 2);
        list = isl_val_list_add(list, isl_val_copy(nan));
        list = isl_val_list_add(list, nan);

        dist = isl_set_copy(dist);
        dim = isl_set_dim(dist, isl_dim_set);
        if (dist && pos >= dim)
                isl_die(ctx, isl_error_internal, "position out of bounds",
                        dist = isl_set_free(dist));
        dist = isl_set_project_out(dist, isl_dim_set, pos + 1, dim - (pos + 1));
        dist = isl_set_project_out(dist, isl_dim_set, 1, pos - 1);

        space = isl_set_get_space(dist);
        dist = isl_set_union(dist, isl_set_from_point(isl_point_zero(space)));
        dist = isl_set_remove_divs(dist);
        hull = isl_set_convex_hull(dist);

        if (isl_basic_set_foreach_constraint(hull, &set_min_max, &list) < 0)
                list = isl_val_list_free(list);
        isl_basic_set_free(hull);

        return list;
}

/* Given a schedule node "node" that, together with its child,
 * satisfies the input pattern for hybrid tiling, compute bounds
 * on the relative dependence distances of the child node with
 * respect to the parent node.  These bounds are needed to
 * construct a hybrid tiling.
 *
 * First all relevant dependences are collected and mapped
 * to the schedule space of the pair of nodes.  Then, the
 * dependence distances are computed in this space.
 *
 * These dependence distances are then projected onto a two-dimensional
 * space consisting of the single schedule dimension of the outer node
 * and one of the schedule dimensions of the inner node.
 * The maximal and minimal relative dependence distances are extracted
 * from these projections.
 * This process is repeated for each of the schedule dimensions
 * of the inner node.  For the first dimension, both minimal and
 * maximal relative dependence distances are stored in the result.
 * For the other dimensions, only the minimal relative dependence
 * distance is stored.
 */
__isl_give ppcg_ht_bounds *ppcg_ht_compute_bounds(struct ppcg_scop *scop,
        __isl_keep isl_schedule_node *node)
{
        ppcg_ht_bounds *bnd;
        isl_space *space;
        isl_map *map;
        isl_set *dist;
        isl_val_list *pair;
        isl_schedule_node *child;
        int n;
        int i, dim;

        if (!scop || !node || check_input_pattern(node) < 0)
                return NULL;

        child = isl_schedule_node_get_child(node, 0);
        space = isl_schedule_node_band_get_space(child);
        dim = isl_schedule_node_band_n_member(child);
        isl_schedule_node_free(child);
        bnd = ppcg_ht_bounds_alloc(space);
        if (!bnd)
                return NULL;

        map = collect_deps(scop, node);

        dist = isl_map_deltas(map);
        n = isl_set_dim(dist, isl_dim_param);
        dist = isl_set_project_out(dist, isl_dim_param, 0, n);

        pair = min_max_dist(dist, 1);
        bnd = ppcg_ht_bounds_set_lower(bnd, 0, isl_val_list_get_val(pair, 0));
        bnd = ppcg_ht_bounds_set_upper(bnd, isl_val_list_get_val(pair, 1));
        isl_val_list_free(pair);

        for (i = 1; i < dim; ++i) {
                pair = min_max_dist(dist, 1 + i);
                bnd = ppcg_ht_bounds_set_lower(bnd, i,
                                                isl_val_list_get_val(pair, 0));
                isl_val_list_free(pair);
        }

        isl_set_free(dist);

        return bnd;
}

/* Check if all the fields of "phase" are valid, freeing "phase"
 * if they are not.
 */
static __isl_give ppcg_ht_phase *check_phase(__isl_take ppcg_ht_phase *phase)
{
        if (!phase)
                return NULL;

        if (!phase->tiling || !phase->local_time ||
            !phase->shift_space || !phase->domain)
                return ppcg_ht_phase_free(phase);

        return phase;
}

/* Construct a ppcg_ht_phase object, that simply copies
 * information from "tiling".
 * That is, the result is defined over the "ts" space and
 * corresponds to phase 1.
 */
static __isl_give ppcg_ht_phase *construct_phase(
        __isl_keep ppcg_ht_tiling *tiling)
{
        isl_ctx *ctx;
        ppcg_ht_phase *phase;

        if (!tiling)
                return NULL;

        ctx = ppcg_ht_tiling_get_ctx(tiling);
        phase = isl_calloc_type(ctx, struct ppcg_ht_phase);
        if (!phase)
                return NULL;
        phase->tiling = ppcg_ht_tiling_copy(tiling);
        phase->time_tile = isl_aff_copy(tiling->time_tile);
        phase->local_time = isl_aff_copy(tiling->local_time);
        phase->shift_space = isl_aff_copy(tiling->shift_space);
        phase->domain = isl_set_copy(tiling->hex);

        return check_phase(phase);
}

/* Align the parameters of the elements of "phase" to those of "space".
 */
static __isl_give ppcg_ht_phase *phase_align_params(
        __isl_take ppcg_ht_phase *phase, __isl_take isl_space *space)
{
        if (!phase)
                goto error;

        phase->time_tile = isl_aff_align_params(phase->time_tile,
                                                        isl_space_copy(space));
        phase->local_time = isl_aff_align_params(phase->local_time,
                                                        isl_space_copy(space));
        phase->shift_space = isl_aff_align_params(phase->shift_space,
                                                        isl_space_copy(space));
        phase->domain = isl_set_align_params(phase->domain, space);

        return check_phase(phase);
error:
        isl_space_free(space);
        return NULL;
}

/* Pull back "phase" over "ma".
 * That is, take a phase defined over the range of "ma" and
 * turn it into a phase defined over the domain of "ma".
 */
static __isl_give ppcg_ht_phase *pullback_phase(__isl_take ppcg_ht_phase *phase,
        __isl_take isl_multi_aff *ma)
{
        phase = phase_align_params(phase, isl_multi_aff_get_space(ma));
        if (!phase)
                goto error;

        phase->time_tile = isl_aff_pullback_multi_aff(phase->time_tile,
                                                        isl_multi_aff_copy(ma));
        phase->local_time = isl_aff_pullback_multi_aff(phase->local_time,
                                                        isl_multi_aff_copy(ma));
        phase->shift_space = isl_aff_pullback_multi_aff(phase->shift_space,
                                                        isl_multi_aff_copy(ma));
        phase->domain = isl_set_preimage_multi_aff(phase->domain, ma);

        return check_phase(phase);
error:
        isl_multi_aff_free(ma);
        return NULL;
}

/* Pullback "phase" over phase->tiling->shift_phase, which shifts
 * phase 0 to phase 1.  The pullback therefore takes a phase 1
 * description and turns it into a phase 0 description.
 */
static __isl_give ppcg_ht_phase *shift_phase(__isl_take ppcg_ht_phase *phase)
{
        ppcg_ht_tiling *tiling;

        if (!phase)
                return NULL;

        tiling = phase->tiling;
        return pullback_phase(phase, isl_multi_aff_copy(tiling->shift_phase));
}

/* Take a "phase" defined over the ts-space and plug in the projection
 * from the input schedule space to the ts-space.
 * The result is then defined over this input schedule space.
 */
static __isl_give ppcg_ht_phase *lift_phase(__isl_take ppcg_ht_phase *phase)
{
        ppcg_ht_tiling *tiling;

        if (!phase)
                return NULL;

        tiling = phase->tiling;
        return pullback_phase(phase, isl_multi_aff_copy(tiling->project_ts));
}

/* Compute the shift that should be added to the space band
 * in order to be able to apply rectangular tiling to the space.
 * Store the shift in phase->space_shift.
 *
 * In the first dimension, it is equal to shift_space - s.
 * For phase 1, this results in
 *
 *      (-(2 * shift_s)*T) % W
 *
 * In phase 0, the "s" in shift_space has been replaced by "s + shift_s",
 * so the result is
 *
 *      shift_s + (-(2 * shift_s)*T) % W
 *
 * In the other dimensions, the shift is equal to
 *
 *      dl_i * local_time.
 */
static __isl_give ppcg_ht_phase *compute_space_shift(
        __isl_take ppcg_ht_phase *phase)
{
        int i, n;
        isl_space *space;
        isl_local_space *ls;
        isl_aff *aff, *s;
        isl_multi_aff *space_shift;

        if (!phase)
                return NULL;

        space = ppcg_ht_phase_get_input_space(phase);
        space = isl_space_unwrap(space);
        space = isl_space_range_map(space);

        space_shift = isl_multi_aff_zero(space);
        aff = isl_aff_copy(phase->shift_space);
        ls = isl_local_space_from_space(isl_aff_get_domain_space(aff));
        s = isl_aff_var_on_domain(ls, isl_dim_set, 1);
        aff = isl_aff_sub(aff, s);
        space_shift = isl_multi_aff_set_aff(space_shift, 0, aff);

        n = isl_multi_aff_dim(space_shift, isl_dim_out);
        for (i = 1; i < n; ++i) {
                isl_val *v;
                isl_aff *time;

                v = ppcg_ht_bounds_get_lower(phase->tiling->bounds, i);
                time = isl_aff_copy(phase->local_time);
                time = isl_aff_scale_val(time, v);
                space_shift = isl_multi_aff_set_aff(space_shift, i, time);
        }

        if (!space_shift)
                return ppcg_ht_phase_free(phase);
        phase->space_shift = space_shift;
        return phase;
}

/* Compute the space tiling and store the result in phase->space_tile.
 * The space tiling is of the form
 *
 *      [P[t] -> C[s]] -> C[floor((s + space_shift)/space_size]
 */
static __isl_give ppcg_ht_phase *compute_space_tile(
        __isl_take ppcg_ht_phase *phase)
{
        isl_space *space;
        isl_multi_val *space_sizes;
        isl_multi_aff *space_shift;
        isl_multi_aff *tile;

        if (!phase)
                return NULL;

        space = ppcg_ht_phase_get_input_space(phase);
        space = isl_space_unwrap(space);
        tile = isl_multi_aff_range_map(space);
        space_shift = isl_multi_aff_copy(phase->space_shift);
        tile = isl_multi_aff_add(space_shift, tile);
        space_sizes = isl_multi_val_copy(phase->tiling->space_sizes);
        tile = isl_multi_aff_scale_down_multi_val(tile, space_sizes);
        tile = isl_multi_aff_floor(tile);

        if (!tile)
                return ppcg_ht_phase_free(phase);
        phase->space_tile = tile;
        return phase;
}

/* Construct a representation for one of the two phase for hybrid tiling
 * "tiling".  If "shift" is not set, then the phase is constructed
 * directly from the hexagonal tile shape in "tiling", which represents
 * the phase-1 tiles.  If "shift" is set, then this tile shape is shifted
 * back over tiling->shift_phase to obtain the phase-0 tiles.
 *
 * First copy data from "tiling", then optionally shift the phase and
 * finally move the tiling from the "ts" space of "tiling" to
 * the space of the input pattern.
 *
 * After the basic phase has been computed, also compute
 * the corresponding space shift.
 */
static __isl_give ppcg_ht_phase *ppcg_ht_tiling_compute_phase(
        __isl_keep ppcg_ht_tiling *tiling, int shift)
{
        ppcg_ht_phase *phase;

        phase = construct_phase(tiling);
        if (shift)
                phase = shift_phase(phase);
        phase = lift_phase(phase);

        phase = compute_space_shift(phase);
        phase = compute_space_tile(phase);

        return phase;
}

/* Consruct a function that is equal to the time tile of "phase0"
 * on the domain of "phase0" and equal to the time tile of "phase1"
 * on the domain of "phase1".
 * The two domains are assumed to form a partition of the input
 * schedule space.
 */
static __isl_give isl_pw_multi_aff *combine_time_tile(
        __isl_keep ppcg_ht_phase *phase0, __isl_keep ppcg_ht_phase *phase1)
{
        isl_aff *T;
        isl_pw_aff *time, *time1;

        if (!phase0 || !phase1)
                return NULL;

        T = isl_aff_copy(phase0->time_tile);
        time = isl_pw_aff_alloc(ppcg_ht_phase_get_domain(phase0), T);

        T = isl_aff_copy(phase1->time_tile);
        time1 = isl_pw_aff_alloc(ppcg_ht_phase_get_domain(phase1), T);

        time = isl_pw_aff_union_add(time, time1);

        return isl_pw_multi_aff_from_pw_aff(time);
}

/* Name used in mark nodes that contain a pointer to a ppcg_ht_phase.
 */
static char *ppcg_phase_name = "phase";

/* Does "id" contain a pointer to a ppcg_ht_phase?
 * That is, is it called "phase"?
 */
static isl_bool is_phase_id(__isl_keep isl_id *id)
{
        const char *name;

        name = isl_id_get_name(id);
        if (!name)
                return isl_bool_error;

        return !strcmp(name, ppcg_phase_name);
}

/* Given a mark node with an identifier that points to a ppcg_ht_phase,
 * extract this ppcg_ht_phase pointer.
 */
__isl_keep ppcg_ht_phase *ppcg_ht_phase_extract_from_mark(
        __isl_keep isl_schedule_node *node)
{
        isl_bool is_phase;
        isl_id *id;
        void *p;

        if (!node)
                return NULL;
        if (isl_schedule_node_get_type(node) != isl_schedule_node_mark)
                isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
                        "not a phase mark", return NULL);

        id = isl_schedule_node_mark_get_id(node);
        is_phase = is_phase_id(id);
        p = isl_id_get_user(id);
        isl_id_free(id);

        if (is_phase < 0)
                return NULL;
        if (!is_phase)
                isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
                        "not a phase mark", return NULL);

        return p;
}

/* Insert a mark node at "node" holding a pointer to "phase".
 */
static __isl_give isl_schedule_node *insert_phase(
        __isl_take isl_schedule_node *node, __isl_take ppcg_ht_phase *phase)
{
        isl_ctx *ctx;
        isl_id *id;

        if (!node)
                goto error;
        ctx = isl_schedule_node_get_ctx(node);
        id = isl_id_alloc(ctx, ppcg_phase_name, phase);
        if (!id)
                goto error;
        id = isl_id_set_free_user(id, &ppcg_ht_phase_free_wrap);
        node = isl_schedule_node_insert_mark(node, id);

        return node;
error:
        ppcg_ht_phase_free(phase);
        isl_schedule_node_free(node);
        return NULL;
}

/* Construct a mapping from the elements of the original pair of bands
 * to which tiling was applied that belong to a tile of "phase"
 * to that tile, preserving the values for the outer bands.
 *
 * The mapping is of the form
 *
 *      [[outer] -> [P -> C]] -> [[outer] -> [tile]]
 *
 * where tile is defined by a concatenation of the time_tile and
 * the space_tile.
 */
static __isl_give isl_map *construct_tile_map(__isl_keep ppcg_ht_phase *phase)
{
        int depth;
        isl_space *space;
        isl_multi_aff *ma;
        isl_multi_aff *tiling;
        isl_map *el2tile;

        depth = isl_schedule_node_get_schedule_depth(
                                                phase->tiling->input_node);
        space = isl_aff_get_space(phase->time_tile);
        space = isl_space_params(space);
        space = isl_space_set_from_params(space);
        space = isl_space_add_dims(space, isl_dim_set, depth);
        space = isl_space_map_from_set(space);
        ma = isl_multi_aff_identity(space);

        tiling = isl_multi_aff_flat_range_product(
                isl_multi_aff_from_aff(isl_aff_copy(phase->time_tile)),
                isl_multi_aff_copy(phase->space_tile));
        el2tile = isl_map_from_multi_aff(tiling);
        el2tile = isl_map_intersect_domain(el2tile,
                                                isl_set_copy(phase->domain));
        el2tile = isl_map_product(isl_map_from_multi_aff(ma), el2tile);

        return el2tile;
}

/* Return a description of the full tiles of "phase" at the point
 * in the original schedule tree where the tiling was applied.
 *
 * First construct a mapping from the input schedule dimensions
 * up to an including the original pair of bands to which hybrid tiling
 * was applied to schedule dimensions in which this original pair
 * has been replaced by the tiles.
 * This mapping is of the form
 *
 *      [[outer] -> [P -> C]] -> [[outer] -> [tile]]
 *
 * Apply this mapping to the set of all values for the input
 * schedule dimensions and then apply its inverse.
 * The result is the set of values for the input schedule dimensions
 * that would map to any of the tiles.  Subtracting from this set
 * the set of values that are actually executed produces the set
 * of values that belong to a tile but that are not executed.
 * Mapping these back to the tiles produces a description of
 * the partial tiles.  Subtracting these from the set of all tiles
 * produces a description of the full tiles in the form
 *
 *      [[outer] -> [tile]]
 */
static __isl_give isl_set *compute_full_tile(__isl_keep ppcg_ht_phase *phase)
{
        isl_schedule_node *node;
        isl_union_set *domain;
        isl_union_map *prefix, *schedule;
        isl_set *all, *partial, *all_el;
        isl_map *tile2el, *el2tile;
        isl_multi_union_pw_aff *mupa;

        el2tile = construct_tile_map(phase);
        tile2el = isl_map_reverse(isl_map_copy(el2tile));

        node = phase->tiling->input_node;
        prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
        domain = isl_schedule_node_get_domain(node);
        mupa = isl_multi_union_pw_aff_copy(phase->tiling->input_schedule);
        schedule = isl_union_map_from_multi_union_pw_aff(mupa);
        schedule = isl_union_map_range_product(prefix, schedule);
        all_el = isl_set_from_union_set(isl_union_set_apply(domain, schedule));
        all_el = isl_set_coalesce(all_el);

        all = isl_set_apply(isl_set_copy(all_el), isl_map_copy(el2tile));

        partial = isl_set_copy(all);
        partial = isl_set_apply(partial, tile2el);
        partial = isl_set_subtract(partial, all_el);
        partial = isl_set_apply(partial, el2tile);

        return isl_set_subtract(all, partial);
}

/* Copy the AST loop types of the non-isolated part to those
 * of the isolated part.
 */
static __isl_give isl_schedule_node *set_isolate_loop_type(
        __isl_take isl_schedule_node *node)
{
        int i, n;

        n = isl_schedule_node_band_n_member(node);
        for (i = 0; i < n; ++i) {
                enum isl_ast_loop_type type;

                type = isl_schedule_node_band_member_get_ast_loop_type(node, i);
                node = isl_schedule_node_band_member_set_isolate_ast_loop_type(
                                                                node, i, type);
        }

        return node;
}

/* If options->isolate_full_tiles is set, then mark the full tiles
 * in "node" for isolation.  The full tiles are derived from "phase".
 * "node" may point to a part of the tiling, e.g., the space tiling.
 *
 * The full tiles are originally computed in the form
 *
 *      [[outer] -> [tile]]
 *
 * However, the band that "node" points to may only contain
 * subset of the tile dimensions.
 * The description above is therefore treated as
 *
 *      [[outer] -> [before; this; after]]
 *
 * before is of size "pos"; this is of size "dim"; and
 * after is of size "out - pos - dim".
 * The after part is first project out.  Then the range is split
 * into a before and this part and finally the before part is moved
 * to the domain, resulting in
 *
 *      [[outer; before] -> [this]]
 *
 * This description is then used as the isolate option.
 *
 * The AST loop type for the isolated part is set to be the same
 * as that of the non-isolated part.
 */
static __isl_give isl_schedule_node *ppcg_ht_phase_isolate_full_tile_node(
        __isl_keep ppcg_ht_phase *phase, __isl_take isl_schedule_node *node,
        struct ppcg_options *options)
{
        int in, out, pos, depth, dim;
        isl_space *space;
        isl_multi_aff *ma1, *ma2;
        isl_set *tile;
        isl_map *map;
        isl_set *set;
        isl_union_set *opt;

        if (!options->isolate_full_tiles)
                return node;

        depth = isl_schedule_node_get_schedule_depth(node);
        dim = isl_schedule_node_band_n_member(node);

        tile = compute_full_tile(phase);
        map = isl_set_unwrap(tile);
        in = isl_map_dim(map, isl_dim_in);
        out = isl_map_dim(map, isl_dim_out);
        pos = depth - in;
        map = isl_map_project_out(map, isl_dim_out, pos + dim,
                                out - (pos + dim));
        space = isl_space_range(isl_map_get_space(map));
        ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
                                           isl_dim_set, pos, dim);
        ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
        ma1 = isl_multi_aff_range_product(ma1, ma2);
        map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1));
        map = isl_map_uncurry(map);
        map = isl_map_flatten_domain(map);
        set = isl_map_wrap(map);
        set = isl_set_set_tuple_name(set, "isolate");

        opt = isl_schedule_node_band_get_ast_build_options(node);
        opt = isl_union_set_add_set(opt, set);
        node = isl_schedule_node_band_set_ast_build_options(node, opt);
        node = set_isolate_loop_type(node);

        return node;
}

/* Insert a band node for performing the space tiling for "phase" at "node".
 * In particular, insert a band node with partial schedule
 *
 *      [P[t] -> C[s]] -> C[floor((s + space_shift)/space_size)]
 *
 * pulled back over the input schedule.
 * "options" determines whether full tiles should be separated
 * from partial tiles.
 *
 * The first tile dimension iterates over the hexagons in the same
 * phase, which are independent by construction.  The first dimension
 * is therefore marked coincident.
 * All dimensions are also marked for being generated as atomic loops
 * because separation is usually not desirable on tile loops.
 */
static __isl_give isl_schedule_node *insert_space_tiling(
        __isl_keep ppcg_ht_phase *phase, __isl_take isl_schedule_node *node,
        struct ppcg_options *options)
{
        isl_multi_aff *space_tile;
        isl_multi_union_pw_aff *mupa;

        if (!phase)
                return isl_schedule_node_free(node);

        space_tile = isl_multi_aff_copy(phase->space_tile);
        mupa = isl_multi_union_pw_aff_copy(phase->tiling->input_schedule);
        mupa = isl_multi_union_pw_aff_apply_multi_aff(mupa, space_tile);
        node = isl_schedule_node_insert_partial_schedule(node, mupa);
        node = ppcg_set_schedule_node_type(node, isl_ast_loop_atomic);
        node = ppcg_ht_phase_isolate_full_tile_node(phase, node, options);
        node = isl_schedule_node_band_member_set_coincident(node, 0, 1);

        return node;
}

/* Given a pointer "node" to (a copy of) the original child node
 * in the input pattern, adjust its partial schedule such that
 * it starts at zero within each tile.
 *
 * That is, replace "s" by (s + space_shift) % space_sizes.
 */
__isl_give isl_schedule_node *ppcg_ht_phase_shift_space_point(
        __isl_keep ppcg_ht_phase *phase, __isl_take isl_schedule_node *node)
{
        isl_multi_val *space_sizes;
        isl_multi_aff *space_shift;
        isl_multi_union_pw_aff *mupa;

        space_shift = isl_multi_aff_copy(phase->space_shift);
        mupa = isl_multi_union_pw_aff_copy(phase->tiling->input_schedule);
        mupa = isl_multi_union_pw_aff_apply_multi_aff(mupa, space_shift);
        node = isl_schedule_node_band_shift(node, mupa);
        space_sizes = isl_multi_val_copy(phase->tiling->space_sizes);
        node = isl_schedule_node_band_mod(node, space_sizes);

        return node;
}

/* Does
 *
 *      s0 > delta + 2 * {delta * h} - 1
 *
 * hold?
 */
static isl_bool wide_enough(__isl_keep isl_val *s0, __isl_keep isl_val *delta,
        __isl_keep isl_val *h)
{
        isl_val *v, *v2;
        isl_bool ok;

        v = isl_val_mul(isl_val_copy(delta), isl_val_copy(h));
        v2 = isl_val_floor(isl_val_copy(v));
        v = isl_val_sub(v, v2);
        v = isl_val_mul_ui(v, 2);
        v = isl_val_add(v, isl_val_copy(delta));
        v = isl_val_sub_ui(v, 1);
        ok = isl_val_gt(s0, v);
        isl_val_free(v);

        return ok;
}

/* Is the tile size specified by "sizes" wide enough in the first space
 * dimension, i.e., the base of the hexagon?  This ensures that,
 * after hybrid tiling using "bounds" and these sizes,
 * neighboring hexagons in the same phase are far enough apart
 * that they do not depend on each other.
 * The test is only meaningful if the bounds are valid.
 *
 * Let st be (half) the size in the time dimension and s0 the base
 * size in the first space dimension.  Let delta be the dependence
 * distance in either positive or negative direction.  In principle,
 * it should be enough to have s0 + 1 > delta, i.e., s0 >= delta.
 * However, in case of fractional delta, the tile is not extended
 * with delta * (st - 1), but instead with floor(delta * (st - 1)).
 * The condition therefore needs to be adjusted to
 *
 *      s0 + 1 > delta + 2 {delta * (st - 1)}
 *
 * (with {} the fractional part) to account for the two slanted sides.
 * The condition in the paper "Hybrid Hexagonal/Classical Tiling for GPUs"
 * translates to
 *
 *      s0 >= delta + {delta * (st - 1)}
 *
 * Since 1 > frac(delta * (st - 1)), this condition implies
 * the condition above.
 *
 * The condition is checked for both directions.
 */
isl_bool ppcg_ht_bounds_supports_sizes(__isl_keep ppcg_ht_bounds *bounds,
        __isl_keep isl_multi_val *sizes)
{
        isl_val *s0, *h;
        isl_val *delta;
        isl_bool ok;

        ok = ppcg_ht_bounds_is_valid(bounds);
        if (ok < 0 || !ok)
                return ok;

        h = isl_val_sub_ui(isl_multi_val_get_val(sizes, 0), 1);
        s0 = isl_multi_val_get_val(sizes, 1);

        delta = ppcg_ht_bounds_get_lower(bounds, 0);
        ok = wide_enough(s0, delta, h);
        isl_val_free(delta);

        delta = ppcg_ht_bounds_get_upper(bounds);
        if (ok == isl_bool_true)
                ok = wide_enough(s0, delta, h);
        isl_val_free(delta);

        isl_val_free(s0);
        isl_val_free(h);

        return ok;
}

/* Check that the tile will be wide enough in the first space
 * dimension, i.e., the base of the hexagon.  This ensures that
 * neighboring hexagons in the same phase are far enough apart
 * that they do not depend on each other.
 *
 * Error out if the condition fails to hold.
 */
static isl_stat check_width(__isl_keep ppcg_ht_bounds *bounds,
        __isl_keep isl_multi_val *sizes)
{
        isl_bool ok;

        ok = ppcg_ht_bounds_supports_sizes(bounds, sizes);

        if (ok < 0)
                return isl_stat_error;
        if (!ok)
                isl_die(isl_multi_val_get_ctx(sizes), isl_error_invalid,
                        "base of hybrid tiling hexagon not sufficiently wide",
                        return isl_stat_error);

        return isl_stat_ok;
}

/* Given valid bounds on the relative dependence distances for
 * the pair of nested nodes that "node" point to, as well as sufficiently
 * wide tile sizes "sizes", insert the corresponding time and space tiling
 * at "node", along with a pair of phase nodes that can be used
 * to make further changes.
 * The space of "sizes" should be the product of the spaces
 * of the schedules of the pair of parent and child nodes.
 * "options" determines whether full tiles should be separated
 * from partial tiles.
 *
 * In particular, given an input of the form
 *
 *      P - C - ...
 *
 * the output has the form
 *
 *              /- F0 - M0 - CT0 - P - C - ...
 *      PT - seq
 *              \- F1 - M1 - CT1 - P - C - ...
 *
 * PT is the global time tiling.  Within each of these tiles,
 * two phases are executed in order.  Within each phase, the schedule
 * space is further subdivided into tiles through CT0 and CT1.
 * The first dimension of each of these iterates over the hexagons
 * within a phase and these are independent by construction.
 * The F0 and F1 filters filter the statement instances that belong
 * to the corresponding phase.  The M0 and M1 marks contain a pointer
 * to a ppcg_ht_phase object that can be used to perform further changes.
 *
 * After checking that input satisfies the requirements,
 * a data structure is constructed that represents the tiling and
 * two additional data structures are constructed for the two phases
 * of the tiling.  These are then used to define the filters F0 and F1 and
 * combined to construct the time tiling PT.
 * Then the time tiling node PT is inserted, followed by
 * the sequence with the two filters, the CT space tiling nodes and
 * the phase markers M.
 */
__isl_give isl_schedule_node *ppcg_ht_bounds_insert_tiling(
        __isl_take ppcg_ht_bounds *bounds, __isl_take isl_multi_val *sizes,
        __isl_take isl_schedule_node *node, struct ppcg_options *options)
{
        isl_ctx *ctx;
        isl_union_set *phase0;
        isl_union_set *phase1;
        isl_multi_union_pw_aff *input, *dom_time;
        isl_union_pw_multi_aff *upma;
        isl_pw_multi_aff *time;
        isl_union_set_list *phases;
        ppcg_ht_tiling *tiling;
        ppcg_ht_phase *phase_0;
        ppcg_ht_phase *phase_1;

        if (!node || !sizes || !bounds)
                goto error;
        if (check_input_pattern(node) < 0 || check_width(bounds, sizes) < 0)
                goto error;

        ctx = isl_schedule_node_get_ctx(node);

        input = extract_input_schedule(node);

        tiling = ppcg_ht_bounds_construct_tiling(bounds, node, input, sizes);
        phase_0 = ppcg_ht_tiling_compute_phase(tiling, 1);
        phase_1 = ppcg_ht_tiling_compute_phase(tiling, 0);
        time = combine_time_tile(phase_0, phase_1);
        ppcg_ht_tiling_free(tiling);

        upma = isl_union_pw_multi_aff_from_multi_union_pw_aff(
                                        isl_multi_union_pw_aff_copy(input));
        phase0 = isl_union_set_from_set(ppcg_ht_phase_get_domain(phase_0));
        phase0 = isl_union_set_preimage_union_pw_multi_aff(phase0,
                                        isl_union_pw_multi_aff_copy(upma));
        phase1 = isl_union_set_from_set(ppcg_ht_phase_get_domain(phase_1));
        phase1 = isl_union_set_preimage_union_pw_multi_aff(phase1, upma);

        phases = isl_union_set_list_alloc(ctx, 2);
        phases = isl_union_set_list_add(phases, phase0);
        phases = isl_union_set_list_add(phases, phase1);

        dom_time = isl_multi_union_pw_aff_apply_pw_multi_aff(input, time);
        node = isl_schedule_node_insert_partial_schedule(node, dom_time);

        node = isl_schedule_node_child(node, 0);

        node = isl_schedule_node_insert_sequence(node, phases);
        node = isl_schedule_node_child(node, 0);
        node = isl_schedule_node_child(node, 0);
        node = insert_space_tiling(phase_0, node, options);
        node = insert_phase(node, phase_0);
        node = isl_schedule_node_parent(node);
        node = isl_schedule_node_next_sibling(node);
        node = isl_schedule_node_child(node, 0);
        node = insert_space_tiling(phase_1, node, options);
        node = insert_phase(node, phase_1);
        node = isl_schedule_node_parent(node);
        node = isl_schedule_node_parent(node);

        node = isl_schedule_node_parent(node);

        isl_multi_val_free(sizes);
        return node;
error:
        isl_multi_val_free(sizes);
        isl_schedule_node_free(node);
        ppcg_ht_bounds_free(bounds);
        return NULL;
}

/* Given a branch "node" that contains a sequence node with two phases
 * of hybrid tiling as input, call "fn" on each of the two phase marker
 * nodes.
 *
 * That is, the input is as follows
 *
 *               /- F0 - M0 - ...
 *      ... - seq
 *               \- F1 - M1 - ...
 *
 * and "fn" is called on M0 and on M1.
 */
__isl_give isl_schedule_node *hybrid_tile_foreach_phase(
        __isl_take isl_schedule_node *node,
        __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,
                void *user), void *user)
{
        int depth0, depth;

        depth0 = isl_schedule_node_get_tree_depth(node);

        while (node &&
            isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
                node = isl_schedule_node_child(node, 0);

        node = isl_schedule_node_child(node, 0);
        node = isl_schedule_node_child(node, 0);
        if (!node)
                return NULL;
        node = fn(node, user);
        node = isl_schedule_node_parent(node);
        node = isl_schedule_node_next_sibling(node);
        node = isl_schedule_node_child(node, 0);
        if (!node)
                return NULL;
        node = fn(node, user);
        node = isl_schedule_node_parent(node);
        node = isl_schedule_node_parent(node);

        depth = isl_schedule_node_get_tree_depth(node);
        node = isl_schedule_node_ancestor(node, depth - depth0);

        return node;
}

/* This function is called on each of the two phase marks
 * in a hybrid tiling tree.
 * Drop the phase mark at "node".
 */
static __isl_give isl_schedule_node *drop_phase_mark(
        __isl_take isl_schedule_node *node, void *user)
{
        isl_id *id;
        isl_bool is_phase;

        if (isl_schedule_node_get_type(node) != isl_schedule_node_mark)
                return node;

        id = isl_schedule_node_mark_get_id(node);
        is_phase = is_phase_id(id);
        isl_id_free(id);

        if (is_phase < 0)
                return isl_schedule_node_free(node);
        if (is_phase)
                node = isl_schedule_node_delete(node);

        return node;
}

/* Given a branch "node" that contains a sequence node with two phases
 * of hybrid tiling as input, remove the two phase marker nodes.
 *
 * That is, the input is as follows
 *
 *               /- F0 - M0 - ...
 *      ... - seq
 *               \- F1 - M1 - ...
 *
 * and the output is
 *
 *               /- F0 - ...
 *      ... - seq
 *               \- F1 - ...
 */
__isl_give isl_schedule_node *hybrid_tile_drop_phase_marks(
        __isl_take isl_schedule_node *node)
{
        return hybrid_tile_foreach_phase(node, &drop_phase_mark, NULL);
}