update isl for change in lexicographic optimization

[isa.git] / translation.cc

#include <iostream>
#include <set>
#include <limits.h>

#include <isa/yaml.h>
#include <isa/pdg.h>
#include "da.h"
#include <isl/val.h>
#include <isl/space.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl/aff.h>
#include <isl/mat.h>
#include <isl/ilp.h>
#include "translation.h"

using namespace std;

namespace pdg {

static void set_prefix(pdg::node *node, const vector<int>& prefix, int l)
{
    node->prefix.resize(0);
    for (int j = 0; j < l-1; ++j) {
        node->prefix.push_back(prefix[j]);
        node->prefix.push_back(-1);
    }
    node->prefix.push_back(prefix[l-1]);
}

/* A comparison function for sorting pdg::nodes based on their prefix.
 */
struct earlier_prefix {
        bool operator()(pdg::node *x, pdg::node *y) {
                for (int i = 0; i < x->prefix.size(); ++i) {
                        if (x->prefix[i] == -1 && y->prefix[i] == -1)
                                continue;
                        assert(x->prefix[i] != -1 && y->prefix[i] != -1);
                        if (x->prefix[i] < y->prefix[i])
                                return true;
                        if (x->prefix[i] > y->prefix[i])
                                return false;
                }
                return false;
        }
};

/* Normalize prefix to be an alternation between statement
 * level dimensions and loop level dimensions.
 * Return the number of statement level dimension.
 *
 * Since the algorithm assumes the input prefixes are ordered
 * lexicographically, we perform it on a sorted list of nodes.
 */
int normalize_prefix(PDG *pdg)
{
    int i, l, maxl;
    vector<int> prefix;
    vector<pdg::node *> nodes;

    if (pdg->nodes.size() == 0)
        return 0;

    for (int i = 0; i < pdg->nodes.size(); ++i)
        nodes.push_back(pdg->nodes[i]);
    std::sort(nodes.begin(), nodes.end(), earlier_prefix());

    l = 1;
    for (int j = 0; j < nodes[0]->prefix.size(); ++j)
        if (nodes[0]->prefix[j] == -1)
            ++l;
    prefix.resize(l);
    maxl = l;
    for (i = 1; i < nodes.size(); ++i) {
        int old_l = l;
        pdg::node *old_node = nodes[i-1];
        pdg::node *node = nodes[i];
        int change_l;
        l = 1;
        change_l = -1;
        for (int j = 0; j < node->prefix.size(); ++j) {
            if (change_l == -1) {
                assert(old_node->prefix[j] <= node->prefix[j]);
                if (old_node->prefix[j] != node->prefix[j])
                    change_l = l;
            }
            if (node->prefix[j] == -1)
                ++l;
        }
        if (l > maxl) {
            maxl = l;
            prefix.resize(l);
        }
        set_prefix(old_node, prefix, old_l);
        if (change_l == -1)
            continue;
        prefix[change_l-1]++;
        for (int j = change_l+1; j < prefix.size(); ++j)
            prefix[j] = 0;
    }
    pdg::node *node = nodes[nodes.size()-1];
    set_prefix(node, prefix, l);
    return maxl;
}

void set_schedule_from_prefix(PDG *pdg)
{
    int statement_dims = normalize_prefix(pdg);
    int dim = 2 * statement_dims - 1;
    int nparam = pdg->params.size();
    isl_ctx *ctx = pdg->get_isl_ctx();

    assert(pdg->dimension == 0);
    assert(pdg->dimension == pdg->statement_dimensions.size());
    pdg->dimension = dim;
    for (int i = 0; i < dim; ++i)
        pdg->statement_dimensions.push_back(1-(i%2));

    for (int i = 0; i < pdg->nodes.size(); ++i) {
        pdg::node *node = pdg->nodes[i];
        isl_set *set = node->source->get_isl_set(ctx);
        isl_space *space = isl_set_get_space(set);
        isl_map *map;
        isl_set_free(set);
        if (isl_space_is_wrapping(space))
            space = isl_space_domain(isl_space_unwrap(space));
        map = isl_map_identity(isl_space_map_from_set(space));
        for (int j = 0; 2 * j < node->prefix.size(); ++j) {
            map = isl_map_insert_dims(map, isl_dim_out, 2 * j, 1);
            map = isl_map_fix_si(map, isl_dim_out, 2 * j, node->prefix[2*j]);
        }
        map = isl_map_add_dims(map, isl_dim_out,
                                2 * statement_dims - 1 - node->prefix.size());
        for (int j = node->prefix.size(); j < 2 * statement_dims - 1; ++j)
            map = isl_map_fix_si(map, isl_dim_out, j, 0);
        node->schedule = new pdg::IslMap(map);
    }
}

/* Create a schedule for the domains "source" based on "pos" and "scale".
 * The "extra" dimensions of source do not appear in the schedule
 * since they have a unique value determined by the values of the "actual"
 * dimensions.
 * If "source" has filters (in the range of the wrapped map), then
 * we project out the filters so that the created schedule only applies
 * to the actual iteration domain.
 */
static pdg::IslMap *create_schedule(PDG *pdg, pdg::IslSet *source,
                                        vector<int>& pos, vector<int>& scale)
{
        pdg::IslMap *s;
        isl_ctx *ctx = pdg->get_isl_ctx();
        isl_set *set = source->get_isl_set(ctx);
        isl_space *space = isl_set_get_space(set);
        isl_multi_aff *ma;
        isl_map *map;

        if (isl_space_is_wrapping(space))
                space = isl_space_domain(isl_space_unwrap(space));
        space = isl_space_from_domain(space);
        isl_set_free(set);
        space = isl_space_add_dims(space, isl_dim_out, pdg->dimension);
        ma = isl_multi_aff_zero(space);
        for (int i = 0; i < pdg->dimension; ++i) {
                isl_aff *aff;

                if (pos[i] < 0)
                        continue;
                aff = isl_multi_aff_get_aff(ma, i);
                aff = isl_aff_set_coefficient_si(aff, isl_dim_in,
                                                            pos[i], scale[i]);
                ma = isl_multi_aff_set_aff(ma, i, aff);
        }

        map = isl_map_from_multi_aff(ma);
        s = new pdg::IslMap(map);

        return s;
}

static pdg::IslMap *pull_back_schedule(PDG *pdg, pdg::IslSet *source,
        pdg::IslMap *schedule, __isl_keep isl_map *map)
{
        isl_ctx *ctx = pdg->get_isl_ctx();
        isl_map *scat = schedule->get_isl_map(ctx);
        isl_basic_map *aff;
        isl_mat *mat;
        int dim = pdg->dimension;
        int this_dim = isl_map_dim(map, isl_dim_in);
        vector<int> pos(dim);
        vector<int> scale(dim);
        // k: position in pos
        int k = 0, j = 0;
        isl_val *v;

        map = isl_map_copy(map);
        map = isl_map_apply_range(map, scat);
        aff = isl_map_affine_hull(map);
        aff = isl_basic_map_remove_divs(aff);
        mat = isl_basic_map_equalities_matrix(aff, isl_dim_in, isl_dim_out,
                                    isl_dim_div, isl_dim_param, isl_dim_cst);
        isl_basic_map_free(aff);

        for (j = 0; j < this_dim; ++j) {
                int s;
                int m;
                int min_m = k;
                int max_m = j + dim - this_dim;

                for (m = min_m; m <= max_m; ++m) {
                        int row;
                        for (row = 0; row < isl_mat_rows(mat); ++row) {
                                int s_v, i_v;
                                v = isl_mat_get_element_val(mat,
                                                            row, this_dim + m);
                                s_v = isl_val_get_num_si(v);
                                isl_val_free(v);
                                if (s_v == 0)
                                        continue;
                                v = isl_mat_get_element_val(mat, row, j);
                                i_v = isl_val_get_num_si(v);
                                isl_val_free(v);
                                if (i_v == 0)
                                        continue;
                                if (s_v < 0)
                                        s_v = -s_v;
                                if (i_v < 0)
                                        i_v = -i_v;
                                if (s_v == 1)
                                        s = i_v;
                                else if (i_v % s_v == 0)
                                        s = i_v / s_v;
                                else
                                        s = 1;
                                break;
                        }
                        if (row < isl_mat_rows(mat))
                                break;
                }
                if (m > max_m)
                        break;
                for ( ; k < m; ++k)
                        pos[k] = -1;
                scale[k] = s;
                pos[k++] = j;
        }

        isl_mat_free(mat);

        for ( ; j < this_dim; ++j) {
                scale[k] = 1;
                pos[k++] = j;
        }
        for ( ; k < dim; ++k)
                pos[k] = -1;

        return create_schedule(pdg, source, pos, scale);
}

/* Return the dimension of the iteration domain of "node".
 * If node->source is a wrapped map, then the iteration domain
 * is in the domain of that map.
 */
static int source_dim(pdg::node *node)
{
        isl_space *space = node->source->get_dim();
        int d;

        if (isl_space_is_wrapping(space)) {
                space = isl_space_unwrap(space);
                d = isl_space_dim(space, isl_dim_in);
        } else
                d = isl_space_dim(space, isl_dim_set);
        isl_space_free(space);
        return d;
}

void common_dimension(PDG *pdg)
{
    isl_ctx *ctx = pdg->get_isl_ctx();
    int dim = pdg->dimension;
    for (int i = 0; i < pdg->nodes.size(); ++i) {
        pdg::node *node = pdg->nodes[i];
        int dim_i = source_dim(node);
        if (dim_i > dim)
            dim = dim_i;
    }
    assert(pdg->dimension == pdg->statement_dimensions.size());
    for (int i = pdg->dimension; i < dim; ++i)
        pdg->statement_dimensions.push_back(0);
    pdg->dimension = dim;
    vector<int> pos(dim);
    vector<int> scale(dim);
    for (int i = 0; i < dim; ++i) {
        scale[i] = 1;
        pos[i] = i;
    }

    int todo = pdg->nodes.size();
    for (int i = 0; i < pdg->nodes.size(); ++i) {
        pdg::node *node = pdg->nodes[i];
        if (source_dim(node) != dim)
            continue;
        node->schedule = create_schedule(pdg, node->source, pos, scale);
        --todo;
        break;
    }

    while (todo) {
        pdg::dependence *maxdep = NULL;
        vector<int> maxw(4);
        vector<int> w(4);
        maxw[0] = -1;
        maxw[1] = -1;
        maxw[2] = -1;
        maxw[3] = -1;
        w[0] = -1;
        w[1] = -1;
        w[2] = -1;
        w[3] = -1;
        for (int i = 0; i < pdg->dependences.size(); ++i) {
            pdg::dependence *dep = pdg->dependences[i];
            if (dep->type == pdg::dependence::uninitialized)
                continue;
            pdg::IslMap *rel = dep->relation;
            if (dep->to->schedule && !dep->from->schedule) {
                w[0] = rel->output();
                w[1] = rel->input();
                w[2] = 1;
            } else if (dep->from->schedule && !dep->to->schedule) {
                w[0] = rel->input();
                w[1] = rel->output();
                w[2] = 1;
            } else
                continue;
            w[3] = dep->array ? dep->array->dims.size() : 0;
            if (maxw < w) {
                maxw = w;
                maxdep = dep;
            }
        }
        pdg::dependence *dep = maxdep;
        if (!dep) {
            int maxi = -1;
            int maxdim = -1;
            for (int i = 0; i < pdg->nodes.size(); ++i) {
                pdg::node *node = pdg->nodes[i];
                int dim_i;
                if (node->schedule)
                    continue;
                dim_i = source_dim(node);
                if (dim_i > maxdim) {
                    maxdim = dim_i;
                    maxi = i;
                }
            }
            assert(maxi != -1);
            pdg::node *node = pdg->nodes[maxi];
            for (int i = node->source->dim(); i < pos.size(); ++i)
                pos[i] = -1;
            node->schedule = create_schedule(pdg, node->source, pos, scale);
            for (int i = node->source->dim(); i < pos.size(); ++i)
                pos[i] = i;
            fprintf(stderr, "WARNING: disconnected dependence graph\n");
        } else {
            isl_map *dep_map = dep->relation->get_isl_map(ctx);
            if (dep->to->schedule) {
                dep->from->schedule = pull_back_schedule(pdg,
                                        dep->from->source,
                                        dep->to->schedule, dep_map);
            } else {
                dep_map = isl_map_reverse(dep_map);
                dep->to->schedule = pull_back_schedule(pdg,
                                        dep->to->source,
                                        dep->from->schedule, dep_map);
            }
            isl_map_free(dep_map);
        }
        --todo;
    }
}


struct dvector {
        isl_set *d;

        dvector() : d(NULL) {}
        dvector(__isl_take isl_set *d) : d(d) {}
        dvector(const dvector &copy) {
                d = isl_set_copy(copy.d);
        }
        dvector &operator= (const dvector &other) {
                isl_set_free(d);
                d = isl_set_copy(other.d);
                return *this;
        }
        virtual ~dvector() {
                isl_set_free(d);
        }

        bool combine(const dvector &dv, const dvector &offset);
};

void operator-= (dvector &d1, const dvector &d2)
{
        isl_set *neg = isl_set_neg(isl_set_copy(d2.d));
        d1.d = isl_set_sum(d1.d, neg);
}

dvector operator- (const dvector &d)
{
        return dvector(isl_set_neg(isl_set_copy(d.d)));
}

void operator+= (dvector &d1, const dvector &d2)
{
        d1.d = isl_set_sum(d1.d, isl_set_copy(d2.d));
}

dvector operator+ (const dvector &d1, const dvector &d2)
{
        return dvector(isl_set_sum(isl_set_copy(d1.d), isl_set_copy(d2.d)));
}

/* replace by dv + offset if dv + offset is smaller
 * return true if dv + offset was smaller
 */
bool dvector::combine(const dvector &dv, const dvector &offset)
{
        int equal;
        dvector new_v = dv + offset;
        new_v.d = isl_set_union(new_v.d, isl_set_copy(d));
        new_v.d = isl_set_lexmin(new_v.d);
        equal = isl_set_is_equal(new_v.d, d);
        assert(equal >= 0);
        if (equal)
                return false;
        new_v.d = isl_set_remove_divs(new_v.d);
        new_v.d = isl_set_lexmin(new_v.d);
        *this = new_v;
        return true;
}

struct wdvector : dvector {
        int     w;

        wdvector() : w(0), dvector(NULL) {}
        wdvector(int w, __isl_take isl_set *d) : w(w), dvector(d) {}
};

wdvector operator+ (const wdvector &d1, const dvector &d2)
{
        return wdvector(d1.w,
                        isl_set_sum(isl_set_copy(d1.d), isl_set_copy(d2.d)));
}

/* Fairly arbitrary, but deterministic sorting of the nodes.
 * In particular, the order does not depend on pointer values.
 */
struct smaller_node_nr
{
        bool operator()(const pdg::node* n1, const pdg::node* n2) const {
                return n1->nr < n2->nr;
        }
};

typedef map<pdg::node *,
            map<pdg::node *, wdvector, smaller_node_nr>,
            smaller_node_nr>::iterator d_graph_iterator;

struct d_graph {
        map<pdg::node *,
            map<pdg::node *, wdvector, smaller_node_nr>, smaller_node_nr> data;

        void update(pdg::node *from, pdg::node *to, __isl_take isl_set *ddv,
                    int weight);

        void minimize();
        void collect_related_nodes(set<pdg::node *> &nodes, pdg::node *node);
};

void d_graph::update(pdg::node *from, pdg::node *to,
        __isl_take isl_set *ddv, int weight)
{
        assert(ddv);
        if (data[from].find(to) == data[from].end())
                data[from][to] = wdvector(weight, ddv);
        else {
                data[from][to].w += weight;
                data[from][to].d = isl_set_union(data[from][to].d, ddv);
        }
}

void d_graph::minimize()
{
        d_graph_iterator i;
        for (i = data.begin(); i != data.end(); ++i) {
                pdg::node *from = (*i).first;
                map<pdg::node *, wdvector>::iterator j;
                for (j = data[from].begin(); j != data[from].end(); ++j) {
                        (*j).second.d = isl_set_lexmin((*j).second.d);
                        (*j).second.d = isl_set_remove_divs((*j).second.d);
                        (*j).second.d = isl_set_lexmin((*j).second.d);
                        (*j).second.d = isl_set_coalesce((*j).second.d);
                }
        }
}

void d_graph::collect_related_nodes(set<pdg::node *> &nodes,
        pdg::node *node)
{
        vector<pdg::node *> todo;

        todo.push_back(node);

        while (!todo.empty()) {
                pdg::node *node = todo.back();
                todo.pop_back();
                if (nodes.find(node) != nodes.end())
                        continue;

                nodes.insert(node);

                d_graph_iterator i;
                map<pdg::node *, wdvector>::iterator j;
                for (j = data[node].begin(); j != data[node].end(); ++j) {
                        pdg::node *node2 = (*j).first;
                        if (nodes.find(node2) != nodes.end())
                                continue;
                        todo.push_back(node2);
                }
                for (i = data.begin(); i != data.end(); ++i) {
                        pdg::node *node2 = (*i).first;
                        if (nodes.find(node2) != nodes.end())
                                continue;
                        if ((*i).second.find(node) == (*i).second.end())
                                continue;
                        todo.push_back(node2);
                }
        }
}

struct combiner {
        PDG *pdg;
        d_graph &graph;
        /* dependence distance offsets used during moving */
        map<pdg::node *, dvector> move_offsets;
        /* the relative offsets */
        map<pdg::node *, map<pdg::node *, dvector> > delays;
        /* the original distance vectors */
        map<pdg::node *, map<pdg::node *, dvector> > distances;
        /* the final offsets */
        map<pdg::node *, dvector> offsets;
        int         n_nodes;
        bool        move;
        /* space of schedule domain */
        isl_space  *space;

        combiner(PDG *pdg, d_graph& distances, int n_nodes, bool move,
            __isl_keep isl_space *space) :
            pdg(pdg), graph(distances), n_nodes(n_nodes), move(move),
            space(space) {}

        void combine();

        void compute_move_offsets();
        dvector compute_relative_offset(pdg::node* from, pdg::node *to,
                                             bool do_move);
        void set_relative_offset(pdg::node* from, pdg::node *to);
        void update_graph(pdg::node* from, pdg::node *to);
        void compute_absolute_offsets();
        void handle_zero_dependences();
        void handle_negative_offsets();
};

static __isl_give isl_set *zero_set(__isl_take isl_space *dim)
{
        isl_set *set;
        int n = isl_space_dim(dim, isl_dim_set);
        set = isl_set_universe(dim);
        for (int i = 0; i < n; ++i)
                set = isl_set_fix_si(set, isl_dim_set, i, 0);
        return set;
}

dvector combiner::compute_relative_offset(pdg::node* from,
        pdg::node *to, bool do_move)
{
        dvector delay;
        map<pdg::node *, dvector> d;
        bool progress = true;
        map<pdg::node *, dvector>::iterator i;

        d[from] = dvector(zero_set(isl_set_get_space(graph.data[from][to].d)));

        for (int k = 0; k < n_nodes && progress; ++k) {
                map<pdg::node *, wdvector>::iterator j;
                progress = false;
                for (i = d.begin(); i != d.end(); ++i) {
                        pdg::node *a = (*i).first;
                        for (j = graph.data[a].begin();
                             j != graph.data[a].end(); ++j) {
                                pdg::node *b = (*j).first;
                                if (do_move &&
                                    move_offsets.find(a) != move_offsets.end())
                                        (*j).second -= move_offsets[a];
                                if (d.find(b) == d.end()) {
                                        progress = true;
                                        d[b] = (*j).second + d[a];
                                } else {
                                        bool p;
                                        p = d[b].combine((*j).second, d[a]);
                                        progress = progress || p;
                                }
                                if (do_move &&
                                    move_offsets.find(a) != move_offsets.end())
                                        (*j).second += move_offsets[a];
                        }
                }
        }

        /* d[from] + d[from] < d[from] iff d[from] < 0 */
        bool lexneg = d[from].combine(d[from], d[from]);
        if (!do_move)
                assert(!lexneg);

        if (!lexneg)
                delay = -d[to];

        return delay;
}

void combiner::set_relative_offset(pdg::node* from, pdg::node *to)
{
        dvector delay;
        if (move)
                delay = compute_relative_offset(from, to, true);
        if (!delay.d)
                delay = compute_relative_offset(from, to, false);
        assert(delay.d);
        delays[from][to] = delay;
}

void combiner::update_graph(pdg::node* from, pdg::node *to)
{
        dvector offset = delays[from][to];
        dvector neg_offset = -offset;

        map<pdg::node *, wdvector>::iterator j;
        for (j = graph.data[to].begin(); j != graph.data[to].end(); ++j) {
                if ((*j).first == from)
                        continue;
                if (graph.data[from].find((*j).first) == graph.data[from].end())
                        graph.data[from][(*j).first] = (*j).second + neg_offset;
                else
                        graph.data[from][(*j).first].combine((*j).second,
                                                             neg_offset);
        }

        graph.data.erase(to);

        d_graph_iterator i;
        for (i = graph.data.begin(); i != graph.data.end(); ++i) {
                if ((*i).second.find(to) == (*i).second.end())
                    continue;
                if ((*i).first != from) {
                    if ((*i).second.find(from) == (*i).second.end())
                            (*i).second[from] = (*i).second[to] + offset;
                    else
                            (*i).second[from].combine((*i).second[to], offset);
                }
                (*i).second.erase(to);
        }

        --n_nodes;
}

void combiner::compute_absolute_offsets()
{
        pdg::node *init = (*graph.data.begin()).first;
        vector<pdg::node *> todo;
        todo.push_back(init);
        offsets[init] = dvector(zero_set(isl_space_copy(space)));

        while (!todo.empty()) {
                pdg::node *n = todo.back();
                todo.pop_back();
                if (delays.find(n) == delays.end())
                        continue;

                map<pdg::node *, dvector>::iterator i;
                for (i = delays[n].begin(); i != delays[n].end(); ++i) {
                        offsets[(*i).first] = offsets[n] + (*i).second;
                        todo.push_back((*i).first);
                }
        }
}

void combiner::handle_zero_dependences()
{
        map<pdg::node *, set<pdg::node *> > succ;
        map<pdg::node *, int > prec;
        map<pdg::node *, map<pdg::node *, dvector> >::iterator i;
        map<pdg::node *, dvector>::iterator j;
        for (j = offsets.begin(); j != offsets.end(); ++j)
                prec[(*j).first] = 0;

        for (i = distances.begin(); i != distances.end(); ++i)
                for (j = (*i).second.begin(); j != (*i).second.end(); ++j) {
                        distances[(*i).first][(*j).first] +=
                                offsets[(*j).first];
                        distances[(*i).first][(*j).first] -=
                                offsets[(*i).first];
                        isl_set *test = distances[(*i).first][(*j).first].d;
                        isl_set *zero = zero_set(isl_set_get_space(test));
                        zero = isl_set_intersect(zero, isl_set_copy(test));
                        int has_zero = !isl_set_is_empty(zero);
                        isl_set_free(zero);
                        if (has_zero) {
                                succ[(*i).first].insert((*j).first);
                                prec[(*j).first]++;
                        }
                }

        map<pdg::node *, int> final;
        for (j = offsets.begin(); j != offsets.end(); ++j) {
                final[(*j).first] = 0;
        }

        while (!prec.empty()) {
                map<pdg::node *, int >::iterator i;
                for (i = prec.begin(); (*i).second > 0; ++i) 
                        ;
                set<pdg::node *>::iterator j;
                for (j = succ[(*i).first].begin();
                     j != succ[(*i).first].end(); ++j) {
                        prec[(*j)]--;
                        if (final[(*j)] <= final[(*i).first])
                                final[(*j)] = final[(*i).first] + 1;
                }
                prec.erase(i);
        }

        int dim = isl_set_dim((*offsets.begin()).second.d, isl_dim_set);
        for (j = offsets.begin(); j != offsets.end(); ++j) {
                (*j).second.d = isl_set_add_dims((*j).second.d, isl_dim_set, 1);
                (*j).second.d = isl_set_fix_si((*j).second.d, isl_dim_set, dim,
                                                final[(*j).first]);
        }
}

/* Remove negative offsets by shifting all offsets over the opposite
 * of the most negative offsets in each direction.
 */
void combiner::handle_negative_offsets()
{
        int dim = isl_set_dim((*offsets.begin()).second.d, isl_dim_set);
        isl_space *space;
        isl_set *shift;
        isl_set *set;
        map<pdg::node *, dvector>::iterator j;

        space = isl_set_get_space((*offsets.begin()).second.d);
        set = isl_set_universe(isl_space_copy(space));
        space = isl_space_params(space);
        space = isl_space_add_unnamed_tuple_ui(space, 0);
        shift = isl_set_universe(space);

        for (int i = 0; i < dim; ++i)
                set = isl_set_fix_si(set, isl_dim_set, i, 0);

        for (j = offsets.begin(); j != offsets.end(); ++j)
                set = isl_set_union(set, isl_set_copy((*j).second.d));

        for (int i = 0; i < dim; ++i) {
                isl_pw_aff *pa = isl_set_dim_min(isl_set_copy(set), i);
                pa = isl_pw_aff_coalesce(pa);
                isl_set *shift_i = isl_set_from_pw_aff(pa);
                shift = isl_set_flat_product(shift, shift_i);
        }

        shift = isl_set_neg(shift);
        shift = isl_set_gist_params(shift, pdg->get_context_isl_set());
        for (j = offsets.begin(); j != offsets.end(); ++j)
                (*j).second.d = isl_set_sum((*j).second.d, isl_set_copy(shift));

        isl_set_free(set);
        isl_set_free(shift);
}

/* Builds a relation that connects iterations of D to the next iteration */
static __isl_give isl_map *next_iteration_map(__isl_take isl_set *dom)
{
        isl_space *dims = isl_set_get_space(dom);
        isl_map *lt = isl_map_lex_lt(dims);
        lt = isl_map_intersect_domain(lt, isl_set_copy(dom));
        lt = isl_map_intersect_range(lt, isl_set_copy(dom));
        lt = isl_map_partial_lexmax(lt, dom, NULL);
        return lt;
}

void combiner::compute_move_offsets()
{
        d_graph_iterator i;
        isl_ctx *ctx = pdg->get_isl_ctx();

        for (i = graph.data.begin(); i != graph.data.end(); ++i) {
                pdg::node *node = (*i).first;
                isl_set *dom = node->source->get_isl_set(ctx);
                isl_set *context = pdg->get_context_isl_set();
                dom = isl_set_intersect_params(dom, context);
                isl_map *scat = (*i).first->schedule->get_isl_map(ctx);
                dom = isl_set_apply(dom, scat);
                isl_map *next = next_iteration_map(dom);
                isl_set *step = isl_map_deltas(next);
                step = isl_set_lexmin(step);
                if (isl_set_is_empty(step))
                        isl_set_free(step);
                else
                        move_offsets[node] = dvector(step);
        }
}

void combiner::combine()
{
        d_graph_iterator i;
        map<pdg::node *, wdvector>::iterator j;

        if (move)
                compute_move_offsets();

        for (i = graph.data.begin(); i != graph.data.end(); ++i)
                for (j = (*i).second.begin(); j != (*i).second.end(); ++j)
                        distances[(*i).first][(*j).first] = (*j).second;

        while (n_nodes > 1) {
                int max = -1;
                pdg::node* max_from = NULL;
                pdg::node* max_to = NULL;
                d_graph_iterator i;
                map<pdg::node *, wdvector>::iterator j;
                for (i = graph.data.begin(); i != graph.data.end(); ++i)
                        for (j = (*i).second.begin();
                             j != (*i).second.end(); ++j) {
                                if ((*j).second.w <= max)
                                        continue;
                                max = (*j).second.w;
                                max_from = (*i).first;
                                max_to = (*j).first;
                        }
                assert(max_from);
                assert(max_to);
                set_relative_offset(max_from, max_to);
                update_graph(max_from, max_to);
        }

        compute_absolute_offsets();
        handle_zero_dependences();
        handle_negative_offsets();
}

bool translate(PDG *pdg, bool move)
{
        isl_ctx *ctx = pdg->get_isl_ctx();
        isl_space *space;
        d_graph distances;

        if (pdg->nodes.size() == 0)
                return true;

        space = isl_map_get_space(pdg->nodes[0]->schedule->map);
        space = isl_space_range(space);

        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];
                if (dep->type == pdg::dependence::uninitialized)
                        continue;
                if (dep->from == dep->to)
                        continue;
                int weight = dep->type == pdg::dependence::anti ? 0 : 1;
                pdg::node* from = dep->from;
                pdg::node* to = dep->to;
                isl_set *ddv;
                isl_map *scat;
                isl_map *dep_map = dep->relation->get_isl_map(ctx);
                scat = from->schedule->get_isl_map(ctx);
                dep_map = isl_map_apply_domain(dep_map, scat);
                scat = to->schedule->get_isl_map(ctx);
                dep_map = isl_map_apply_range(dep_map, scat);
                ddv = isl_map_deltas(dep_map);
                distances.update(from, to, ddv, weight);
        }

        distances.minimize();

        set<pdg::node *> nodes_done;
        /* split the dependence graph into connected subgraphs
         * and compute offsets in each subgraph
         */
        while (nodes_done.size() < pdg->nodes.size()) {
                set<pdg::node *> current_nodes;
                d_graph current_distances;
                pdg::node *node;

                for (int i = 0; i < pdg->nodes.size(); ++i) {
                        node = pdg->nodes[i];
                        if (nodes_done.find(node) != nodes_done.end())
                                continue;
                        break;
                }

                distances.collect_related_nodes(current_nodes, node);

                set<pdg::node *>::iterator i;
                for (i = current_nodes.begin(); i != current_nodes.end(); ++i) {
                        current_distances.data[(*i)] = distances.data[(*i)];
                }

                combiner c(pdg, current_distances, current_nodes.size(),
                                move, space);
                c.combine();

                for (i = current_nodes.begin(); i != current_nodes.end(); ++i) {
                        pdg::node *node = *i;
                        nodes_done.insert(node);

                        isl_map *s = node->schedule->get_isl_map(ctx);

                        isl_space *dim = isl_set_get_space(c.offsets[node].d);
                        int d = isl_space_dim(dim, isl_dim_set) - 1;
                        isl_map *id = isl_map_identity(
                                isl_space_map_from_set(isl_space_copy(dim)));
                        isl_set *u = isl_set_universe(dim);
                        isl_map *off = isl_map_from_domain_and_range(u,
                                            isl_set_copy(c.offsets[node].d));
                        id = isl_map_project_out(id, isl_dim_in, d, 1);
                        id = isl_map_fix_si(id, isl_dim_out, d, 0);
                        off = isl_map_project_out(off, isl_dim_in, d, 1);
                        off = isl_map_sum(id, off);
                        s = isl_map_apply_range(s, off);

                        delete node->schedule;
                        node->schedule = new IslMap(s);
                }
        }

        pdg->statement_dimensions.push_back(1);
        pdg->dimension++;

        isl_space_free(space);

        return true;
}

}