update isl for change in coalescing

[ppn.git] / pn.cc

#include <iostream>
#include <set>
#include <map>
#include <vector>

#include <isl/ctx.h>
#include <isl/space.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_map.h>
#include <isl/polynomial.h>
#include <isl/flow.h>

#include <isa/yaml.h>
#include <isa/pdg.h>
#include "da.h"
#include "size.h"
extern "C" {
#include "isl_util.h"
}
#include "translation.h"
#include "pn_options.h"

#include "memrchr.h"

using pdg::PDG;
using namespace std;
using namespace da;
using namespace size;

/* Check whether node is a propagation node 
 *
 * A propagation node simply copies a value from one array to another array.
 * In principle, a copy node could also copy a value to the same array,
 * but then we would have to be careful that the node does not recursively
 * copy values.
 * Note that the check is incomplete.  If a node performs some additional
 * operations involving only iterators, then this information is not stored
 * so we may incorrectly conclude that the node is a copy node.
 */
static bool propagation_node(pdg::node *node)
{
    pdg::statement *s = node->statement;
    if (s->accesses.size() != 2)
        return false;
    if (s->accesses[0]->type != pdg::access::read)
        return false;
    if (s->accesses[1]->type != pdg::access::write)
        return false;
    if (s->accesses[0]->array == s->accesses[1]->array)
        return false;
    if (s->accesses[1]->array->dims.size() != 0)
        return false;
    if (s->top_function && s->top_function->name &&
        strcmp(s->top_function->name->s.c_str(), ""))
        return false;
    return true;
}

static pdg::IslMap *join_input(PDG *pdg, pdg::IslMap *left,
        pdg::IslMap *right)
{
        pdg::IslMap *res;
        isl_ctx *ctx = pdg->get_isl_ctx();
        isl_map *rel = left->get_isl_map(ctx);
        isl_map *acc = right->get_isl_map(ctx);

        acc = isl_map_apply_domain(acc, rel);

        res = new pdg::IslMap(acc);

        return res;
}

/* Given a dependence relation um_rel that maps iterations from
 * a propagation node to the current node and an access relation
 * from the current node, drop those iterations from the domain
 * of the access relation that have been propagated, i.e.,
 * that are in the range of the dependence relation.
 *
 * The original access relation is destroyed and a new one
 * is returned, provided the new access relation is not empty.
 * If it is empty, then a NULL pointer is returned.
 *
 * Note that the input access relation may not have been specialized
 * to the domain of the node, i.e., the access relation may have
 * a universe domain.  In that case, the new relation is unlikely
 * to be empty, but it may end up having a domain that is disjoint
 * from the domain of the node.
 */
static pdg::IslMap *remove_propagated_from_domain(PDG *pdg,
        pdg::IslMap *um_rel, pdg::IslMap *um_acc)
{
        pdg::IslMap *res = NULL;
        isl_ctx *ctx = pdg->get_isl_ctx();
        isl_map *rel = um_rel->get_isl_map(ctx);
        isl_map *acc = um_acc->get_isl_map(ctx);

        isl_set *rel_ran = isl_map_range(rel);
        isl_set *acc_dom = isl_map_domain(isl_map_copy(acc));

        acc_dom = isl_set_subtract(acc_dom, rel_ran);
        acc = isl_map_intersect_domain(acc, acc_dom);

        delete um_acc;

        if (isl_map_is_empty(acc))
                isl_map_free(acc);
        else
                res = new pdg::IslMap(acc);

        return res;
}

/* Recursively replace old_access inside call by new_access.
 */
static void replace_access(pdg::function_call *call, pdg::access *old_access,
                           pdg::call_or_access *new_coa)
{
        for (int i = 0; i < call->arguments.size(); ++i) {
                pdg::call_or_access *coa = call->arguments[i];
                if (coa->type == pdg::call_or_access::t_call)
                        replace_access(coa->call, old_access, new_coa);
                if (coa->type == pdg::call_or_access::t_access &&
                    coa->access == old_access) {
                        *coa = *new_coa;
                        break;
                }
        }
}

/* Replace old_access inside s by new_access.
 * If empty is not set, then new_access only replaces part of
 * old_access.  This means that old_access is kept in the list
 * of accesses and that in the parse tree of the statement,
 * old_access is replaced by a new virtual function call
 * with old_access and new_access as arguments.
 */
static void replace_access(pdg::statement *s, pdg::access *old_access,
                           pdg::access *new_access, bool empty)
{
    pdg::call_or_access coa;

    if (empty)
        s->accesses.erase(old_access);
    s->accesses.push_back(new_access);

    if (!s->top_function)
        return;

    if (empty) {
        coa.type = pdg::call_or_access::t_access;
        coa.access = new_access;
    } else {
        pdg::call_or_access *old_coa, *new_coa;
        coa.type = pdg::call_or_access::t_call;
        coa.call = new pdg::function_call;
        coa.call->name = new str(string("#PHI"));
        old_coa = new pdg::call_or_access;
        old_coa->type = pdg::call_or_access::t_access;
        old_coa->access = old_access;
        coa.call->arguments.push_back(old_coa);
        new_coa = new pdg::call_or_access;
        new_coa->type = pdg::call_or_access::t_access;
        new_coa->access = new_access;
        coa.call->arguments.push_back(new_coa);
    }
    replace_access(s->top_function, old_access, &coa);
}

static void clear_dependences(PDG *pdg)
{
        for (int j = 0; j < pdg->dependences.size(); ++j) {
                pdg::dependence *dep = pdg->dependences[j];
                delete dep->controlled_relation;
                delete dep->relation;
                delete dep;
        }
        pdg->dependences.resize(0);
}

/* Check if there is any node that simply copies the value from an array
 * to a scalar.  If so, perform dependence analysis on the scalar
 * and replaces read access to the scalar that depend on writes from
 * a propagation node to reads from the propagated array.
 * In particular, the propagated iterations are removed from the access
 * relation and replaced by an access to the propagated array.
 * Finally, the propagation node is removed.
 */
static void copy_propagation(PDG* pdg)
{
    std::set<pdg::node *> to_remove_n;
    for (int i = 0; i < pdg->nodes.size(); ++i) {
        pdg::node *node = pdg->nodes[i];
        pdg::statement *s = node->statement;
        if (!propagation_node(node))
            continue;
        pdg::array *a = s->accesses[1]->array;
        find_deps(pdg, a, flow);
        std::set<pdg::access *> to_remove;
        for (int j = 0; j < pdg->dependences.size(); ++j) {
            pdg::dependence *dep = pdg->dependences[j];
            if (dep->controlled_relation)
                continue;
            assert(dep->type == pdg::dependence::flow);
            assert(dep->from != dep->to);
            if (!propagation_node(dep->from))
                continue;
            to_remove_n.insert(dep->from);
            pdg::IslMap *access_map = dep->from->statement->accesses[0]->map;
            pdg::IslMap *prop_access = join_input(pdg, dep->relation, access_map);
            access_map = dep->to_access->map;
            access_map = remove_propagated_from_domain(pdg, dep->relation,
                                                        access_map);
            dep->to_access->map = access_map;
            bool empty = !access_map;
            pdg::access *access = new pdg::access;
            access->nr = dep->to_access->nr;
            access->array = dep->from->statement->accesses[0]->array;
            access->type = pdg::access::read;
            access->map = prop_access;
            replace_access(dep->to->statement, dep->to_access, access, empty);
            if (empty)
                to_remove.insert(dep->to_access);
        }
        std::set<pdg::access *>::iterator it;
        for (it = to_remove.begin(); it != to_remove.end(); ++it) {
            (*it)->array = NULL;
            (*it)->free();
            delete (*it);
        }
        clear_dependences(pdg);
    }
    if (to_remove_n.size() == 0)
        return;
    std::set<pdg::node *>::iterator itn;
    for (itn = to_remove_n.begin(); itn != to_remove_n.end(); ++itn) {
        (*itn)->statement->accesses[0]->array = NULL;
        (*itn)->statement->accesses[1]->array = NULL;
        (*itn)->free();
        delete (*itn);
        pdg->nodes.erase(*itn);
    }
    for (int i = 0; i < pdg->nodes.size(); ++i)
        pdg->nodes[i]->nr = i;
}

/* Check whether dep writes and reads from consecutive iterations of
 * the same domain.
 * We check this property by testing whether any other read for the
 * same access occurs in between.
 */
bool is_consecutive_dep(PDG *pdg, pdg::dependence *dep, isl_map *map)
{
    isl_ctx *ctx = pdg->get_isl_ctx();
    assert(dep->to == dep->from);
    for (int i = 0; i < pdg->dependences.size(); ++i) {
        pdg::dependence *other_dep = pdg->dependences[i];
        if (other_dep == dep)
            continue;
        if (other_dep->to != dep->to)
            continue;
        if (other_dep->to_access != dep->to_access)
            continue;
        isl_map *other_map = other_dep->relation->get_isl_map(ctx);
        bool consec = isl_is_consecutive_dep(map, other_map);
        isl_map_free(other_map);
        if (!consec)
            return false;
    }
    return true;
}

/* An auxiliary class that keeps a reference to an isl_map
 * and frees it when it goes out of scope.
 */
struct temp_map {
    isl_map * const map;
    temp_map(isl_map *m) : map(m) {}
    operator isl_map *() const { return map; }
    ~temp_map() {
        isl_map_free(map);
    }
};

/* Set *user to qp of the first call, assuming *user was initialized to NULL.
 * If this function is called more than once, then return isl_stat_error.
 */
static isl_stat extract_single(__isl_take isl_set *set,
        __isl_take isl_qpolynomial *qp, void *user)
{
        isl_qpolynomial **res = (isl_qpolynomial **) user;

        isl_set_free(set);

        if (*res) {
                isl_qpolynomial_free(qp);
                return isl_stat_error;
        }

        *res = qp;
        return isl_stat_ok;
}

/* Check if we can use a shift register for the self-dependence dep
 * on the domain D.
 * If yes, return the required size of the shift register.
 * If no, return NULL.
 *
 * We assume that the register is shifted on every iteration of D.
 * If the number of shifts between any pair of writes and reads is
 * constant, then we can use a shift register.
 * Note that the size of the shift register may be larger than
 * that of the FIFO, since there may be iterations of the domain
 * between corresponding writes and reads where nothing is written
 * to or read from the shift register.
 *
 * If "ref" is a wrapped map, then the iteration domain
 * is in the domain of that map.
 */
static size::enumerator *shift_register_size(pdg::PDG *pdg,
        __isl_take isl_set *ref, __isl_take isl_map *dep)
{
        isl_space *dims;
        isl_set *dep_set;
        isl_map *read_after_ref;
        isl_map *write_before_ref;
        isl_map *ref_between;
        isl_pw_qpolynomial *pwqp;
        isl_set *universe;
        isl_qpolynomial *qp;
        unsigned dim;

        if (isl_set_is_wrapping(ref))
                ref = isl_map_domain(isl_set_unwrap(ref));

        dim = isl_set_dim(ref, isl_dim_set);
        dep = isl_map_move_dims(dep, isl_dim_in, dim, isl_dim_out, 0, dim);
        dep_set = isl_map_domain(dep);

        read_after_ref = isl_map_lex_ge(isl_set_get_space(ref));
        read_after_ref = isl_map_insert_dims(read_after_ref, isl_dim_in, 0, dim);
        write_before_ref = isl_map_lex_lt(isl_set_get_space(ref));
        write_before_ref = isl_map_add_dims(write_before_ref, isl_dim_in, dim);
        ref_between = isl_map_intersect(read_after_ref, write_before_ref);

        ref_between = isl_map_intersect_range(ref_between, ref);
        ref_between = isl_map_intersect_domain(ref_between,
                                                isl_set_copy(dep_set));

        pwqp = isl_map_card(ref_between);

        pwqp = isl_pw_qpolynomial_gist(pwqp, dep_set);

        pwqp = isl_pw_qpolynomial_coalesce(pwqp);

        qp = NULL;
        if (isl_pw_qpolynomial_foreach_piece(pwqp, &extract_single, &qp) < 0 ||
            !qp ||
            isl_qpolynomial_involves_dims(qp, isl_dim_in, 0, dim + dim)) {
                isl_qpolynomial_free(qp);
                isl_pw_qpolynomial_free(pwqp);
                return NULL;
        }
        isl_pw_qpolynomial_free(pwqp);

        qp = isl_qpolynomial_project_domain_on_params(qp);
        universe = isl_set_universe(isl_qpolynomial_get_domain_space(qp));
        pwqp = isl_pw_qpolynomial_alloc(universe, qp);

        return new size::enumerator(pwqp, pdg);
}

/* isl_access_level_before function used in a context where there
 * is a single iteration domain.  The order is given by the order
 * of the accesses passed through first and second.
 * If the first access precedes the second, we return 2 * d + 1,
 * where d is the dimension of the iteration domain, and otherwise 2 * d.
 */
static int precedes_access(void *first, void *second)
{
        pdg::access *access1 = (pdg::access *) first;
        pdg::access *access2 = (pdg::access *) second;
        int d = isl_map_dim(access1->map->map, isl_dim_in);

        return 2 * d + (access1->nr < access2->nr);
}

/* Return true if all input dimensions are constrained to be equal to the 
 * corresponding output dimensions.
 */
static bool is_identity_map(__isl_keep isl_map *map)
{
        int is_id;
        isl_space *space = isl_map_get_space(map);
        isl_map *id = isl_map_identity(space);

        is_id = isl_map_is_subset(map, id);

        isl_map_free(id);

        return is_id;
}

/* Set buf (of size buf_len) to the prefix of control variables
 * that correspond to the from and to access of the given "dep"
 * and return the length of the prefix.
 */
static size_t set_local_control_name(char *buf, size_t buf_len,
        pdg::dependence *dep)
{
        snprintf(buf, buf_len, "__last_%s_%d_%s_%d",
                dep->from->name->s.c_str(), dep->from_access->nr,
                dep->to->name->s.c_str(), dep->to_access->nr);
        return strlen(buf);
}

/* Given the name of a binding variable, reset the part that refers
 * to the sink access by "nr".
 *
 * The original name is of the form
 *
 *      __last_ND_<source node>_<source access>_ND_<sink node>_<sink access>_*
 *
 * We simply replace the <sink access> by <nr>.
 */
static str *replace_to_access(isl_ctx *ctx, str *id, int nr)
{
        const char *name;
        const char *suffix;
        const char *infix;
        char *replaced;
        size_t len;
        str *s;

        name = id->s.c_str();
        assert(name);
        suffix = strrchr(name, '_');
        assert(suffix);
        infix = (const char *) memrchr(name, '_', suffix - name);
        assert(infix);
        len = infix + 1 - name + strlen(suffix) + 20;
        replaced = isl_alloc_array(ctx, char, len);
        assert(replaced);
        len = infix + 1 - name;
        memcpy(replaced, name, len);
        snprintf(replaced + len, 20, "%d", nr);
        len += strlen(replaced + len);
        strcpy(replaced + len, suffix);

        s = new str(replaced);
        free(replaced);

        return s;
}

/* For each element of controls, replace the part of the name that
 * refers to the sink access by "nr" and collect the results in
 * renamed_controls.
 */
static void replace_to_access(isl_ctx *ctx, seq<str> &renamed_controls,
        seq<str> &controls, int nr)
{
        for (int i = 0; i < controls.size(); ++i)
                renamed_controls.push_back(replace_to_access(ctx,
                                                            controls[i], nr));
}

/* Is the i-th parameter of "map" of the form __last_*
 * but not of the form local_control*?
 */
static bool is_foreign_control(__isl_keep isl_map *map, int i,
        const char *local_control, size_t len)
{
        const char *name;
        const char *prefix = "__last_";
        size_t prefix_len = strlen(prefix);

        if (!isl_map_has_dim_id(map, isl_dim_param, i))
                return false;
        name = isl_map_get_dim_name(map, isl_dim_param, i);
        if (strncmp(name, prefix, prefix_len))
                return false;
        return strncmp(name, local_control, len) != 0;
}

/* Remove from "dep" all those parameters that are of the form __last_*
 * but not of the form local_control* and return the result.
 */
static __isl_give isl_map *remove_foreign_controls(__isl_take isl_map *dep,
        const char *local_control, size_t len)
{
        int n_param;

        n_param = isl_map_dim(dep, isl_dim_param);
        for (int i = n_param - 1; i >= 0; --i) {
                if (!is_foreign_control(dep, i, local_control, len))
                        continue;
                dep = isl_map_project_out(dep, isl_dim_param, i, 1);
        }
        dep = isl_map_coalesce(dep);

        return dep;
}

/* Is the i-th parameter of "map" a control, i.e., a parameter
 * introduced by convert_writer()?
 * In particular, is the parameter of the form __last_*?
 */
static bool is_control(__isl_keep isl_map *map, int i)
{
        const char *name;
        const char *prefix = "__last_";
        size_t prefix_len = strlen(prefix);

        if (!isl_map_has_dim_id(map, isl_dim_param, i))
                return false;
        name = isl_map_get_dim_name(map, isl_dim_param, i);
        return strncmp(name, prefix, prefix_len) == 0;
}

/* Remove all parameters that were introduced by convert_writer().
 */
static __isl_give isl_map *remove_all_controls(__isl_take isl_map *dep)
{
        int n_param;

        n_param = isl_map_dim(dep, isl_dim_param);
        for (int i = n_param - 1; i >= 0; --i) {
                if (!is_control(dep, i))
                        continue;
                dep = isl_map_project_out(dep, isl_dim_param, i, 1);
        }
        dep = isl_map_coalesce(dep);

        return dep;
}

struct add_reuse_data {
        PDG *pdg;
        pdg::dependence *dep;
};

extern "C" {
        static isl_stat add_reuse(__isl_take isl_map *dep_rel, int must,
                void *dep_user, void *user);
};

/* Add a reuse dependence with dependence relation "dep_rel" to
 * data->pdg->dependences.
 * data->dep corresponds to the original dependence that is reusing
 * some value that was previously used by "propagate_access", from
 * the same node.
 * Since "dep_rel" was obtained from a relation with local
 * control variables, we need to remove them to obtain the
 * dependence relation on the reuse dependence.
 *
 * If we are reusing control variables, then we need to rename
 * the from_control to refer to the access where we are reusing
 * the control variables from.
 *
 * If the dependence relations maps iterations to themselves, then
 * we mark the new reuse dependence as a wire.
 */
static isl_stat add_reuse(__isl_take isl_map *dep_rel, int must, void *dep_user,
        void *user)
{
        pdg::access *propagate_access = (pdg::access *) dep_user;
        add_reuse_data *data = (add_reuse_data *) user;
        pdg::dependence *reuse_dep;
        isl_ctx *ctx = isl_map_get_ctx(dep_rel);

        reuse_dep = new pdg::dependence;
        reuse_dep->array = data->dep->array;
        replace_to_access(ctx, reuse_dep->from_controls,
                                data->dep->from_controls, propagate_access->nr);
        reuse_dep->to_controls = data->dep->to_controls;
        reuse_dep->from = data->dep->to;
        reuse_dep->to = data->dep->to;
        reuse_dep->from_access = propagate_access;
        reuse_dep->to_access = data->dep->to_access;
        if (reuse_dep->from == reuse_dep->to && is_identity_map(dep_rel))
                reuse_dep->type = pdg::dependence::pn_wire;
        else
                reuse_dep->type = data->dep->type;
        if (data->dep->controlled_relation) {
                pdg::IslMap *cr = data->dep->controlled_relation;
                isl_set *dom = isl_map_range(cr->get_isl_map());
                isl_map *control_rel = isl_map_copy(dep_rel);
                control_rel = isl_map_intersect_range(control_rel, dom);
                reuse_dep->controlled_relation = new pdg::IslMap(control_rel);
        }
        dep_rel = remove_all_controls(dep_rel);
        reuse_dep->relation = new pdg::IslMap(dep_rel);
        data->pdg->dependences.push_back(reuse_dep);

        return isl_stat_ok;
}

/* Detect reuse among the dependences in "deps", adding split off
 * dependences to pdg->dependences.
 * Each of the dependences in "deps" originates from the same
 * write access and ends in the same node.
 *
 * We look for values, i.e., iterations of the write access,
 * that are used several times.  To do so, we perform dependence
 * analysis on the inverted dependence relations.  That is,
 * we use these inverted dependence relations as "access relations",
 * accessing iterations of the write access.
 * We consider each dependence in turn as a "read", each time taking
 * all dependences as writes.
 * In the result of such a dependence analysis, the "uninitialized reads"
 * correspond to the first use of a result from the original write access,
 * while all the "dependences" corespond to a propagation of a value
 * from one original read access to another original read access.
 *
 * If the dependence has a controlled_relation, then we use this
 * controlled_relation as the "access relation" after removing all
 * the foreign controls.  This ensures that we only reuse data if
 * the last iteration hasn't changed.
 * After restricting the range of the controlled_relation based on
 * the "uninitialized reads", we recompute the uncontrolled relation
 * from this result.
 *
 * If there is only one dependence in "deps" and if that dependence
 * is single-valued, then obviously there can be no reuse, so we skip
 * the analysis.
 *
 * We currently assume that none of the accesses has an extended_relation.
 */
static void detect_reuse(PDG *pdg, std::vector<pdg::dependence *> &deps)
{
        add_reuse_data data = { pdg };
        char buf[120];
        size_t len;

        if (deps.size() == 1 &&
            isl_map_is_single_valued(deps[0]->relation->map))
                return;

        for (int i = 0; i < deps.size(); ++i) {
                isl_access_info *ai;
                isl_flow *flow;
                isl_set *first;
                isl_map *local;
                pdg::IslMap *rel;

                assert(!deps[i]->extended_relation);

                if (deps[i]->controlled_relation) {
                        local = deps[i]->controlled_relation->get_isl_map();
                        len = set_local_control_name(buf, sizeof(buf), deps[i]);
                        local = remove_foreign_controls(local, buf, len);
                } else
                        local = deps[i]->relation->get_isl_map();
                local = isl_map_reverse(local);

                data.dep = deps[i];
                ai = isl_access_info_alloc(isl_map_copy(local),
                            deps[i]->to_access, &precedes_access, deps.size());
                for (int j = 0; j < deps.size(); ++j) {
                        isl_map *map;
                        if (i == j) {
                                map = isl_map_copy(local);
                        } else {
                                map = deps[j]->relation->get_isl_map();
                                map = isl_map_reverse(map);
                        }
                        ai = isl_access_info_add_source(ai, map,
                            1, deps[j]->to_access);
                }
                flow = isl_access_info_compute_flow(ai);
                isl_flow_foreach(flow, &add_reuse, &data);
                first = isl_map_domain(isl_flow_get_no_source(flow, 1));
                isl_flow_free(flow);

                rel = deps[i]->relation;
                if (deps[i]->controlled_relation) {
                        pdg::IslMap *cr = deps[i]->controlled_relation;
                        cr->map = isl_map_intersect_range(cr->map, first);
                        isl_map_free(rel->map);
                        rel->map = remove_all_controls(isl_map_copy(cr->map));
                } else
                        rel->map = isl_map_intersect_range(rel->map, first);

                isl_map_free(local);
        }
}

/* Has this dependence been created during the detection
 * of multiple assignments?  In particular, does this dependence
 * propagate the values in the source.
 */
static bool is_multi_assignment_propagation(pdg::dependence *dep)
{
        return dep->to_access == dep->from_access &&
                dep->to_access->type == pdg::access::write;
}

typedef std::pair<pdg::access *, pdg::node *> an_pair;
typedef std::pair<int, an_pair> nan_triple;

struct nan_triple_cmp {
        bool operator()(nan_triple t1, nan_triple t2) const {
                if (t1.first != t2.first)
                        return t1.first < t2.first;
                if (t1.second.first->nr != t2.second.first->nr)
                        return t1.second.first->nr < t2.second.first->nr;
                return t1.second.second->nr < t2.second.second->nr;
        }
};

typedef std::map<nan_triple, std::vector<pdg::dependence *>, nan_triple_cmp>
        nan2deps;

/* Detect reuse of the same value (originating from the same
 * write access) within a node and split the corresponding dependence
 * into part of the original dependences that use the value for
 * the first time and internal dependences that propagate the value.
 *
 * If a scheduling is applied that changes the order of the iterations
 * within a given node, then this scheduling should be performed
 * before the reuse detection.
 *
 * We first collect the dependences that originate in a given access
 * and end up in a given node and then process each such collection
 * in turn, in an order that does not depend on pointer values.
 * While collecting dependences, we skip those that correspond
 * to the propagation of multiple assignments to the next potential
 * assignment.
 *
 * Dependences that propagate data (those that have a dep->array)
 * are treated separately from those that propagate control.
 *
 * If the user has turned off reuse detection, then we do nothing.
 */
static void detect_reuse(PDG *pdg, struct pn_options *options)
{
        nan2deps access_deps;
        nan2deps control_deps;
        nan2deps::iterator it;

        if (!options->reuse)
                return;

        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];
                if (dep->type == pdg::dependence::uninitialized)
                        continue;
                if (is_multi_assignment_propagation(dep))
                        continue;
                an_pair p(dep->from_access, dep->to);
                nan_triple t(dep->from->nr, p);
                if (dep->array)
                        access_deps[t].push_back(dep);
                else
                        control_deps[t].push_back(dep);
        }

        for (it = access_deps.begin(); it != access_deps.end(); ++it)
                detect_reuse(pdg, it->second);
        for (it = control_deps.begin(); it != control_deps.end(); ++it)
                detect_reuse(pdg, it->second);
}

/* isl_access_level_before function used in a context where the
 * iteration domains live in a common space.  We therefore just
 * need to retun 2 * the dimension of this space, which is stored
 * in *first (and *second).
 */
static int common_space(void *first, void *second)
{
        int depth = *(int *) first;
        return 2 * depth;
}

/* Assign dep to *user.  This function is expected to be called
 * exactly once.
 */
static isl_stat extract_dep(__isl_take isl_map *dep, int must,
        void *dep_user, void *user)
{
        isl_map **map_p = (isl_map **) user;

        *map_p = dep;

        return isl_stat_ok;
}

/* Is the i-th parameter of "set" of the form __last_*
 * but not of the form local_control*?
 */
static bool is_foreign_control(__isl_keep isl_set *set, int i,
        const char *local_control, size_t len)
{
        const char *name;
        const char *prefix = "__last_";
        size_t prefix_len = strlen(prefix);

        if (!isl_set_has_dim_id(set, isl_dim_param, i))
                return false;
        name = isl_set_get_dim_name(set, isl_dim_param, i);
        if (strncmp(name, prefix, prefix_len))
                return false;
        return strncmp(name, local_control, len) != 0;
}

/* Does "set" have any parameters of the form __last_*
 * that are not of the form local_control*?
 */
static __isl_give isl_set *remove_foreign_controls(__isl_take isl_set *set,
        const char *local_control, size_t len)
{
        int n_param;

        n_param = isl_set_dim(set, isl_dim_param);
        for (int i = n_param - 1; i >= 0; --i) {
                if (!is_foreign_control(set, i, local_control, len))
                        continue;
                set = isl_set_project_out(set, isl_dim_param, i, 1);
        }
        set = isl_set_coalesce(set);

        return set;
}

/* Given a dependence such that the dependence relation
 * is not injective, split the dependence into two parts,
 * one that propagates the value from a potential source iteration
 * to the next potential source iteration and one that sends
 * the data from the final potential source iteration to the sink
 * iteration.
 *
 * The dependence may either be a control dependence, propagating
 * control variables, or a data dependence, in which case it has
 * a controlled_relation and it is the uncontrolled relation that
 * is not injective.
 *
 * To obtain the last potential source iteration, we simply
 * compute the lexicographic maximum of all potential source iterations.
 *
 * To obtain the dependence from one potential source iteration
 * to the next potential source iteration, we apply
 * dependence analysis on the dependence relation.
 * In particular, we need a mapping from source iterations to
 * the next source iteration associated to the same sink iteration,
 * so we simply treat the original dependence relation as an access relation.
 *
 * The mapping to the next potential source should not have any controls.
 * If the input dependence is a control dependence, then it is propagating
 * control variables itself.  If it is a data dependence, then we want
 * to propagate values to the next potential source independently of
 * any control.
 *
 * The constraints on the controls for the dependence from the final
 * potential source iteration should be the same as those on the
 * original relation, when seen from the destination node.
 *
 * We currently assume that there is no extended relation associated
 * to the dependence.
 */
static void split_multi_assignment(PDG *pdg, pdg::dependence *dep)
{
        isl_set *dom;
        isl_map *last;
        isl_map *next = NULL;
        isl_access_info *ai;
        isl_flow *flow;
        int depth;
        pdg::dependence *next_dep;
        char buf[120];
        size_t len;

        assert(!dep->extended_relation);

        len = set_local_control_name(buf, sizeof(buf), dep);

        depth = isl_map_dim(dep->relation->map, isl_dim_in);
        ai = isl_access_info_alloc(isl_map_copy(dep->relation->map),
                                    &depth, &common_space, 1);
        ai = isl_access_info_add_source(ai, isl_map_copy(dep->relation->map),
                                        1, &depth);
        flow = isl_access_info_compute_flow(ai);
        isl_flow_foreach(flow, &extract_dep, &next);
        isl_flow_free(flow);

        last = isl_map_copy(dep->relation->map);
        last = isl_map_reverse(isl_map_lexmax(isl_map_reverse(last)));

        next_dep = new pdg::dependence;
        next_dep->array = dep->array;
        next_dep->from_controls = dep->from_controls;
        next_dep->to_controls = dep->to_controls;
        next_dep->type = dep->type;
        next_dep->from = dep->from;
        next_dep->to = dep->from;
        next_dep->from_access = dep->from_access;
        next_dep->to_access = dep->from_access;
        next_dep->relation = new pdg::IslMap(next);
        pdg->dependences.push_back(next_dep);

        dep->relation->map = isl_map_intersect(dep->relation->map, last);
        if (dep->controlled_relation)
                dep->controlled_relation->map =
                    isl_map_intersect_range(isl_map_copy(dep->relation->map),
                                isl_map_range(dep->controlled_relation->map));
}

/* If any sink iteration has more than one potential source
 * iteration, we split off the propagation of the data on the from
 * node from the transfer of the data to the to node.
 *
 * We only perform this operation here on (data) dependences
 * with a "controlled_relation".  The corresponding control dependence
 * has already been handled from within extract_control_dependence.
 * Other data dependences have an exact dependence relation and
 * can therefore not exhibit multiple assignments.
 */
static void split_multi_assignment(PDG *pdg)
{
        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];
                if (!dep->controlled_relation)
                        continue;
                if (isl_map_is_injective(dep->relation->map))
                        continue;
                split_multi_assignment(pdg, dep);
        }
}

/* Does "dep" have any parameters of the form __last_*?
 */
static bool has_controls(__isl_keep isl_map *dep)
{
        int n_param;
        const char *prefix = "__last_";
        size_t prefix_len = strlen(prefix);

        n_param = isl_map_dim(dep, isl_dim_param);
        for (int i = 0; i < n_param; ++i) {
                const char *name;

                if (!isl_map_has_dim_id(dep, isl_dim_param, i))
                        continue;
                name = isl_map_get_dim_name(dep, isl_dim_param, i);
                if (!strncmp(name, prefix, prefix_len))
                        return true;
        }

        return false;
}

/* Is the i-th parameter of "map" of the form local_control*?
 * "len" is the length of "local_control".
 */
static bool is_local_control(__isl_keep isl_map *map, int i,
        const char *local_control, size_t len)
{
        const char *name;

        if (!isl_map_has_dim_id(map, isl_dim_param, i))
                return false;
        name = isl_map_get_dim_name(map, isl_dim_param, i);
        return strncmp(name, local_control, len) == 0;
}

/* Does "dep" have any parameters of the form __last_*
 * that are not of the form local_control*?
 */
static bool has_foreign_controls(__isl_keep isl_map *dep,
        const char *local_control, size_t len)
{
        int n_param;

        n_param = isl_map_dim(dep, isl_dim_param);
        for (int i = 0; i < n_param; ++i)
                if (is_foreign_control(dep, i, local_control, len))
                        return true;

        return false;
}

/* Does "dep" have any parameters of the form local_control*?
 * "len" is the length of "local_control".
 */
static bool has_local_controls(__isl_keep isl_map *dep,
        const char *local_control, size_t len)
{
        int n_param;

        n_param = isl_map_dim(dep, isl_dim_param);
        for (int i = 0; i < n_param; ++i)
                if (is_local_control(dep, i, local_control, len))
                        return true;

        return false;
}

/* Extract a control dependence from a dependence with a controlled_relation.
 * The control dependence transfers the values of the control variables
 * that correspond to the given dependence, i.e., those that correspond
 * to the from and to access of the dependence.
 * We therefore don't need to do anything if the controlled_relation
 * only involves foreign controls.
 *
 * from_controls and to_controls are set from the local control variables
 * in dep->controlled_relation.
 *
 * The uncontrolled dependence relation may not be injective,
 * in which case the initial dependence relation on the control
 * dependence is also non-injective.  In such cases, the control
 * dependence is split using split_multi_assignment in two parts,
 * one that propagate the current value of the controls to the next
 * iteration of the source and one that sends the final values to the sink.
 * The data dependence is split later on.
 */
static void extract_control_dependence(PDG *pdg, pdg::dependence *dep)
{
        pdg::dependence *control;
        char buf[120];
        size_t len;
        int n_param;
        isl_map *rel;

        len = set_local_control_name(buf, sizeof(buf), dep);
        rel = dep->controlled_relation->map;
        if (!has_local_controls(rel, buf, len))
                return;
        n_param = isl_map_dim(rel, isl_dim_param);

        control = new pdg::dependence;
        control->type = dep->type;
        control->from = dep->from;
        control->to = dep->to;
        control->from_access = dep->from_access;
        control->to_access = dep->to_access;
        control->relation = new pdg::IslMap(dep->relation->get_isl_map());
        for (int i = 0; i < n_param; ++i) {
                const char *name;
                if (!isl_map_has_dim_id(rel, isl_dim_param, i))
                        continue;
                name = isl_map_get_dim_name(rel, isl_dim_param, i);
                if (strncmp(name, buf, len) != 0)
                        continue;
                control->from_controls.push_back(new str(name));
                control->to_controls.push_back(new str(name));
        }
        pdg->dependences.push_back(control);

        if (isl_map_is_injective(control->relation->map))
                return;
        split_multi_assignment(pdg, control);
}

/* Extract a control dependence from each dependence with a controlled_relation.
 */
static void extract_control_dependences(PDG *pdg)
{
        int n_dep = pdg->dependences.size();

        for (int i = 0; i < n_dep; ++i) {
                pdg::dependence *dep = pdg->dependences[i];
                if (!dep->controlled_relation)
                        continue;
                extract_control_dependence(pdg, dep);
        }
}

/* Split off the communication of data, along with the corresponding
 * controls, from selecting the data based on other controls.
 * "dep" is modified to only refer to the controls that correspond
 * to the given from and to access and an extra wire is introduced
 * to select the data.
 * If "dep" corresponds to a propagation from one potential source
 * to the next potential source, then it already only refers to
 * "local" controls.  We handle this case separately so that we
 * don't have to add a special case to set_local_control_name
 * for setting up the right name for local controls on such dependences.
 *
 * A new virtual access is created to act as the target of the modified
 * communication dependence and the source of the selection dependence.
 * If the input "dep" did not refer to the corresponding controls,
 * then the output "dep" does not refer to any control and
 * controlled_relation is cleared.
 */
static void split_wire(PDG *pdg, pdg::dependence *dep)
{
        isl_space *space;
        isl_set *dom;
        isl_map *rel;
        isl_map *id;
        pdg::dependence *wire;
        pdg::access *access;
        char buf[120];
        size_t len;

        if (is_multi_assignment_propagation(dep))
                return;

        assert(!dep->extended_relation);

        rel = dep->controlled_relation->map;
        len = set_local_control_name(buf, sizeof(buf), dep);

        if (!has_foreign_controls(rel, buf, len))
                return;

        space = isl_map_get_space(dep->controlled_relation->map);
        space = isl_space_range(space);
        space = isl_space_map_from_set(space);
        id = isl_map_identity(space);
        dom = isl_map_range(isl_map_copy(dep->controlled_relation->map));
        id = isl_map_intersect_domain(id, dom);

        access = new pdg::access;
        access->array = dep->to_access->array;
        access->nr = dep->to->statement->accesses.size();
        dep->to->statement->accesses.push_back(access);

        wire = new pdg::dependence;
        wire->array = dep->array;
        wire->type = pdg::dependence::pn_wire;
        wire->from = dep->to;
        wire->to = dep->to;
        wire->from_access = access;
        wire->to_access = dep->to_access;
        wire->relation = new pdg::IslMap(id);
        pdg->dependences.push_back(wire);

        dep->to_access = access;
        dep->controlled_relation->map = remove_foreign_controls(rel, buf, len);
        if (!has_controls(dep->controlled_relation->map)) {
                delete dep->controlled_relation;
                dep->controlled_relation = NULL;
        }
}

/* If the dependence involves "foreign" controls, i.e., controls
 * that correspond to other dependences, then we split off
 * the communication of the data (along with the "local" controls)
 * from the selection of the data based on the foreign controls.
 */
static void split_wires(PDG *pdg)
{
        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];
                if (!dep->controlled_relation)
                        continue;
                split_wire(pdg, dep);
        }
}

static void schedule(PDG *pdg, struct pn_options *options)
{
        translate(pdg, options->move);
}

/* Compute the size of the dependence "dep" with scheduled dependence
 * relation "dep_map".
 *
 * If "dep" is of type pn_union, then it may contains parts that read
 * from the channel in the same iteration.  We therefore need to recombine
 * the dependence relations of those parts, but separate them apart.
 * In particular, we add an extra inner dimension with a fixed value
 * corresponding to the index of the dependence.
 */
static size::enumerator *compute_size(pdg::PDG *pdg, pdg::dependence *dep,
        __isl_take isl_map *dep_map, pn_options *options)
{
        dep_map = isl_map_copy(dep_map);
        if (dep->type == pdg::dependence::pn_union) {
                isl_space *space = isl_map_get_space(dep_map);
                int n_in, n_out;

                n_in = isl_space_dim(space, isl_dim_in);
                n_out = isl_space_dim(space, isl_dim_out);
                space = isl_space_add_dims(space, isl_dim_in, 1);
                space = isl_space_add_dims(space, isl_dim_out, 1);
                isl_map_free(dep_map);
                dep_map = isl_map_empty(space);
                for (int i = 0; i < pdg->dependences.size(); ++i) {
                        pdg::dependence *part = pdg->dependences[i];
                        isl_map *map_i;

                        if (part->type != pdg::dependence::pn_part)
                                continue;
                        if (part->container != dep)
                                continue;
                        map_i = part->relation->get_isl_map();
                        map_i = isl_map_intersect_params(map_i,
                                                pdg->get_context_isl_set());
                        map_i = schedule_dependence(pdg, dep, map_i);
                        map_i = isl_map_add_dims(map_i, isl_dim_in, 1);
                        map_i = isl_map_add_dims(map_i, isl_dim_out, 1);
                        map_i = isl_map_fix_si(map_i, isl_dim_in, n_in, i);
                        map_i = isl_map_fix_si(map_i, isl_dim_out, n_out, i);
                        dep_map = isl_map_union(dep_map, map_i);
                }
        }
        return selfloop_size(pdg, dep_map, options->size);
}

static bool determine_dependence_properties(PDG *pdg, pdg::dependence *dep,
        bool evaluate, bool scheduled, struct pn_options *options)
{
        if (dep->type == pdg::dependence::uninitialized) {
                fprintf(stderr,
                    "access to uninitialized data from %s on line %d\n",
                     dep->array->name->s.c_str(), dep->to->statement->line);
                dep->relation->Dump(stderr);
                return scheduled;
        }
        pdg::IslMap *rel = dep->relation;
        if (dep->type == pdg::dependence::pn_part ||
            dep->type == pdg::dependence::pn_wire) {
                dep->reordering = 0;
                dep->multiplicity = 0;
                dep->size = new pdg::enumerator(0);
                dep->value_size = new integer(0);
                return scheduled;
        }

        isl_map *dep_map = rel->get_isl_map();
        dep_map = isl_map_intersect_params(dep_map, pdg->get_context_isl_set());
        dep->reordering = isl_map_is_reordering(dep_map);
        dep->multiplicity = 0;
        if (!options->reuse)
                dep->multiplicity = isl_map_has_multiplicity(dep_map);
        if (dep->reordering || dep->multiplicity) {
                isl_map_free(dep_map);
                return scheduled;
        }

        if (dep->to != dep->from && !scheduled) {
                schedule(pdg, options);
                scheduled = true;
        }

        if (dep->to != dep->from)
                dep_map = schedule_dependence(pdg, dep, dep_map);

        if (!dep->controlled_relation && isl_is_consecutive_loop(dep_map)) {
                dep->size = new pdg::enumerator(1);
                dep->value_size = new integer(1);
                if (dep->from_access == dep->to_access &&
                    dep->to_access->type != pdg::access::write &&
                    is_consecutive_dep(pdg, dep, dep_map))
                        dep->type = pdg::dependence::pn_hold;
        } else {
                size::enumerator *size = NULL;
                if (options->shift_register && dep->to == dep->from &&
                    !dep->controlled_relation) {
                        isl_set *ref = dep->to->source->get_isl_set();
                        size = shift_register_size(pdg, ref,
                                                    isl_map_copy(dep_map));
                }
                if (size)
                        dep->type = pdg::dependence::pn_shift;
                else
                        size = compute_size(pdg, dep, dep_map, options);
                if (size) {
                        dep->size = *size;
                        if (evaluate)
                                dep->value_size = size->evaluate();
                        delete size;
                }
        }

        isl_map_free(dep_map);

        return scheduled;
}

static void determine_dependence_properties(PDG *pdg, bool evaluate,
        bool scheduled, struct pn_options *options)
{
        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];
                scheduled = determine_dependence_properties(pdg, dep, evaluate,
                                            scheduled, options);
        }
}

/* Can we merge "dep1" and "dep2"?
 *
 * That is,
 *      - do they connect the same from_access to the same to node?
 *      - is there no reordering in the combined dependence relation?
 */
static bool can_merge(PDG *pdg, pdg::dependence *dep1, pdg::dependence *dep2)
{
        pdg::IslMap *rel1 = dep1->relation;
        pdg::IslMap *rel2 = dep2->relation;
        isl_map *dep_rel;
        bool reordering;

        if (dep1->to != dep2->to)
                return false;
        if (dep1->from_access != dep2->from_access)
                return false;
        dep_rel = isl_map_union(rel1->get_isl_map(), rel2->get_isl_map());
        dep_rel = isl_map_intersect_params(dep_rel, pdg->get_context_isl_set());

        reordering = isl_map_is_reordering(dep_rel);

        isl_map_free(dep_rel);

        return !reordering;
}

/* Combine the dependences "dep1" and "dep2" into a single pn_union
 * dependences with the union dependence relation.
 *
 * If "dep2" is already a pn_union, we simply extend it.
 * Otherwise, we create a new pn_union modeled after "dep2",
 * add it to the list of dependences and turn "dep2" into a pn_part.
 * "dep1" is turned into a pn_part in any case.
 */
static void merge_dependences(PDG *pdg, pdg::dependence *dep1,
        pdg::dependence *dep2)
{
        pdg::dependence *dep_union;

        if (dep2->type == pdg::dependence::pn_union)
                dep_union = dep2;
        else {
                pdg::IslMap *rel;
                dep_union = new pdg::dependence;
                dep_union->from = dep2->from;
                dep_union->to = dep2->to;
                dep_union->from_access = dep2->from_access;
                dep_union->to_access = NULL;
                dep_union->array = dep2->array;
                dep_union->type = pdg::dependence::pn_union;
                rel = dep2->relation;
                dep_union->relation = new pdg::IslMap(rel->get_isl_map());
                pdg->dependences.push_back(dep_union);

                dep2->type = pdg::dependence::pn_part;
                dep2->container = dep_union;
        }

        dep1->type = pdg::dependence::pn_part;
        dep1->container = dep_union;

        dep_union->relation->map = isl_map_union(dep_union->relation->map,
                                                dep1->relation->get_isl_map());
}

/* Try and merge dependences between a given pair of (distinct) nodes.
 * A merge is performed only if it the resulting merged dependence
 * does not exhibit any reordering.
 * The merging needs to be applied before the buffer size computation
 * as the buffer sizes are computed on the merged (pn_union) dependences.
 *
 * We run through all original dependences and check whether it can
 * be combined with any later dependences.  If so, we turn the two
 * dependences into "pn_part"s and add an extra pn_union dependence
 * that combines the two.  The inner loop starts from the latest
 * dependence so that we compare with any previously added pn_union
 * dependences first.  If such a previously add pn_union can be combined
 * with the current dependence, it is simply extended to include the
 * current dependence.
 *
 * We currently don't allow any merging of dependences involving control.
 *
 * If the user has turned off merging, the we do nothing.
 * We do the same if the user has turned off reuse detection, as there
 * may in this case be dependences with multiplicity.  It is not clear
 * if we would want to merge such edges.
 */
static void merge_dependences(PDG *pdg, struct pn_options *options)
{
        int n_dep;

        if (!options->reuse)
                return;
        if (!options->merge)
                return;

        n_dep = pdg->dependences.size();
        for (int i = 0; i < n_dep; ++i) {
                pdg::dependence *dep_i = pdg->dependences[i];
                if (dep_i->type != pdg::dependence::flow)
                        continue;
                if (dep_i->to == dep_i->from)
                        continue;
                if (dep_i->controlled_relation)
                        continue;

                for (int j = pdg->dependences.size() - 1; j > i; --j) {
                        pdg::dependence *dep_j = pdg->dependences[j];

                        if (dep_j->type != pdg::dependence::flow &&
                            dep_j->type != pdg::dependence::pn_union)
                                continue;
                        if (dep_j->controlled_relation)
                                continue;
                        if (!can_merge(pdg, dep_i, dep_j))
                                continue;

                        merge_dependences(pdg, dep_i, dep_j);
                }
        }
}

/* Is "access" one of the filter accesses of "node"?
 */
static bool is_filter_access(pdg::node *node, pdg::access *access)
{
        for (int i = 0; i < node->filters.size(); ++i) {
                pdg::call_or_access *coa;

                coa = node->filters[i];
                assert(coa->type == pdg::call_or_access::t_access);
                if (access == coa->access)
                        return true;
        }
        return false;
}

/* Given the (overapproximation of the) dependence relation "dep_rel",
 * check whether "to" and "from" represent the same filter, i.e.,
 * whether they refer to the same array element written at the same
 * iteration.
 *
 * We apply the mappings from source/sink iterations
 * to filter access relations to both sides of "dep_rel".
 * If the result is a subset of the identity relation, then
 * we know that the filter element accessed by the source is
 * exactly the same as the filter element accessed by
 * the courresponding sink(s).
 *
 * If we were unable to find the source for one or both of the two filters,
 * then the filter access relations live in different spaces and
 * the computed relation cannot be a subset of the identity relation.
 */
static bool is_same_filter(pdg::access *to, pdg::access *from,
        __isl_keep isl_map *dep_rel)
{
        isl_union_map *from_access;
        isl_union_map *to_access;
        isl_union_map *test;
        isl_union_map *univ;
        isl_union_map *id;
        bool same;

        if (to->array != from->array)
                return false;

        from_access = from->extract_access_map();
        to_access = to->extract_access_map();
        test = isl_union_map_from_map(isl_map_copy(dep_rel));
        test = isl_union_map_apply_domain(test, from_access);
        test = isl_union_map_apply_range(test, to_access);
        univ = isl_union_map_universe(isl_union_map_copy(test));
        id = isl_union_set_identity(isl_union_map_domain(univ));
        same = isl_union_map_is_subset(test, id);
        isl_union_map_free(test);
        isl_union_map_free(id);

        return same;
}

/* Insert equalities between source filters and sink filters
 * of dependences, whenever we are able to detect that they are the same.
 *
 * We first introduce the constraints on the sink filters in the dependence
 * relation and we add unconstrained variables for the source filters.
 * Then, for each of the sink filters, we check if we can find
 * any source filter that has the same value on the other side
 * of the dependence.  If so, we can keep the constraints on this
 * filter value and we add an equality between the source filter
 * and the sink filter so that these constraints will also be
 * applied to the source filter.
 * Otherwise, we eliminate the sink filter value from the constraints.
 */
static void insert_filter_constraints(pdg::dependence *dep)
{
        isl_space *space;
        isl_map *map;
        isl_map *dep_rel;
        int n_in;
        int n_out;
        bool any = false;

        dep_rel = isl_map_copy(dep->relation->map);
        n_in = isl_map_dim(dep_rel, isl_dim_in);
        n_out = isl_map_dim(dep_rel, isl_dim_out);

        space = isl_set_get_space(dep->from->source->set);
        map = isl_set_unwrap(isl_set_universe(space));
        map = isl_map_reverse(isl_map_domain_map(map));
        dep_rel = isl_map_apply_domain(dep_rel, map);
        map = isl_set_unwrap(dep->to->source->get_isl_set());
        map = isl_map_reverse(isl_map_domain_map(map));
        dep_rel = isl_map_apply_range(dep_rel, map);

        for (int i = 0; i < dep->to->filters.size(); ++i) {
                pdg::call_or_access *coa_i;
                pdg::access *access_i;
                bool found = false;

                coa_i = dep->to->filters[i];
                assert(coa_i->type == pdg::call_or_access::t_access);
                access_i = coa_i->access;

                for (int j = 0; j < dep->from->filters.size(); ++j) {
                        pdg::call_or_access *coa_j;
                        pdg::access *access_j;

                        coa_j = dep->from->filters[j];
                        assert(coa_j->type == pdg::call_or_access::t_access);
                        access_j = coa_j->access;

                        if (!is_same_filter(access_i, access_j,
                                            dep->relation->map))
                                continue;
                        dep_rel = isl_map_equate(dep_rel, isl_dim_in, n_in + j,
                                                        isl_dim_out, n_out + i);
                        found = true;
                        any = true;
                }

                if (!found)
                        dep_rel = isl_map_eliminate(dep_rel, isl_dim_out,
                                                        n_out + i, 1);
        }

        if (any) {
                isl_map_free(dep->relation->map);
                dep->relation->map = dep_rel;
        } else
                isl_map_free(dep_rel);
}

/* Insert equalities between source filters and sink filters
 * of dependences, whenever we are able to detect that they are the same.
 *
 * We currently don't introduce any such equalities in dependences
 * that involve control variables.  Both these control variables and
 * the filters will be treated as "dynamic controls" in pn2adg
 * and it probably needs to be tweaked to be able to handle two sets
 * of dynamic controls.
 */
static void insert_filter_constraints(PDG *pdg)
{
        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];

                if (dep->type == pdg::dependence::uninitialized)
                        continue;
                if (dep->to == dep->from)
                        continue;
                if (dep->controlled_relation)
                        continue;
                if (dep->to->filters.size() == 0)
                        continue;
                if (dep->from->filters.size() == 0)
                        continue;
                if (is_filter_access(dep->to, dep->to_access))
                        continue;
                insert_filter_constraints(dep);
        }
}

int main(int argc, char * argv[])
{
    isl_ctx *ctx;
    FILE *in = stdin, *out = stdout;
    int c, ind = 0;
    PDG *pdg;
    struct pn_options *options = pn_options_new_with_defaults();
    bool evaluate = true;

    argc = pn_options_parse(options, argc, argv, ISL_ARG_ALL);

    if (!options->reuse)
        options->propagate = 0;

    if (options->input && strcmp(options->input, "-")) {
        in = fopen(options->input, "r");
        assert(in);
        if (!options->output) {
            int len = strlen(options->input);
            if (len > 5 && !strcmp(options->input+len-5, ".yaml"))
                len -= 5;
            options->output = (char *)malloc(len+9+1);
            strncpy(options->output, options->input, len);
            strcpy(options->output+len, options->reuse ? "_pn.yaml" : "_cpn.yaml");
        }
    }

    ctx = isl_ctx_alloc_with_options(&pn_options_args, options);
    pdg = PDG::Load(in, ctx);
    assert(pdg);
    int nparam = pdg->params.size();

    if (options->propagate)
        copy_propagation(pdg);

    compute_filter_sources(pdg);
    for (int i = 0; i < pdg->arrays.size(); ++i)
        find_deps(pdg, pdg->arrays[i], flow);
    extract_control_dependences(pdg);

    for (int i = 0; i < nparam; ++i)
        if (!pdg->params[i]->value) {
            evaluate = false;
            break;
        }

    bool translated;
    if (options->reschedule) {
        common_dimension(pdg);
        translated = false;
    } else {
        set_schedule_from_prefix(pdg);
        translated = true;
    }

    detect_reuse(pdg, options);
    split_multi_assignment(pdg);
    split_wires(pdg);
    merge_dependences(pdg, options);
    determine_dependence_properties(pdg, evaluate, translated, options);
    insert_filter_constraints(pdg);

    pdg->add_history_line("pn", argc, argv);

    if (options->output && strcmp(options->output, "-")) {
        out = fopen(options->output, "w");
        assert(out);
    }

    pdg->Dump(out);
    pdg->free();
    delete pdg;
    isl_ctx_free(ctx);

    return 0;
}