update pet for more relaxed pet_expr_is_equal index comparison

[ppn.git] / pn2adg.cc

/*
 * Copyright 2011 Leiden University. All rights reserved.
 */

#include <sstream>

#include <isl/ctx.h>
#include <isl/id.h>
#include <isl/space.h>
#include <isl/local_space.h>
#include <isl/aff.h>
#include <isl/ilp.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_map.h>
#include <isa/pdg.h>
#include <isa/adg.h>

#include "adg_xml.h"
#include "pn2adg_options.h"

/* Convert the result of "pn" to and "adg".
 * The result may be written out as either a YAML or an XML file.
 *
 * We essentially create an adg node for each pn node and an adg edge
 * for each pn dependence.  The ports are obtained by projecting the
 * dependence relationss on their domains and ranges.
 * There are however various extra constraints on the resulting adg which
 * make the tranformation not quite as trivial as it sounds.
 */

/* ESPAM requirements:
 *
 * The static control variables that appear in the domain of a node
 * should also appear in the domains of the function, ports and invars
 * of that node.
 *
 * The name of a static control should uniquely define the expression
 * of the static control throughout the entire graph.  That is, two
 * static controls with the same name should have the same expression.
 *
 * The bounds on the domains should not involve any unions.
 *
 * An edge of type adg_edge_broadcast should only associate a write
 * with the first corresponding read.
 *
 * The name of a control edge should start with "CED".
 */

using pdg::PDG;

/* Create and return an adg_var that accesses the variable "id"
 * on the given space.
 */
static adg_var *var_from_id(__isl_take isl_id *id, __isl_take isl_space *space)
{
        adg_var *var = new adg_var;
        isl_ctx *ctx;
        isl_set *dom;
        isl_multi_aff *maff;
        isl_aff_list *list;

        ctx = isl_space_get_ctx(space);
        dom = isl_set_universe(isl_space_copy(space));
        space = isl_space_from_domain(space);
        space = isl_space_set_tuple_id(space, isl_dim_out, id);
        list = isl_aff_list_alloc(ctx, 0);
        maff = isl_multi_aff_from_aff_list(space, list);
        var->access = isl_pw_multi_aff_alloc(dom, maff);
        return var;
}

/* Create and return an isl_id of the form
 *
 *      in_<access->nr><suffix>
 * or
 *      out_<access->nr><suffix>
 *
 * depending on whether access represents a read or a write.
 */
static __isl_give isl_id *access_name(isl_ctx *ctx, pdg::access *access,
        const char *suffix)
{
        char buf[100];
        const char *type;

        if (access->type == pdg::access::write)
                type = "out";
        else
                type = "in";
        snprintf(buf, sizeof(buf), "%s_%d%s", type, access->nr, suffix);

        return isl_id_alloc(ctx, buf, NULL);
}

/* Extract the isl_id of the node from "space".
 *
 * The given space may be the result of one of more nestings of the form
 *
 *      D -> [D -> local[..]]
 *
 * and/or a nesting of the form
 *
 *      D -> [D -> [dynamic controls]]
 *
 * and so we may have to dig down to obtain the space that corresponds
 * to the node.
 */
static __isl_give isl_id *node_id(__isl_take isl_space *space)
{
        isl_id *id;

        if (!isl_space_is_wrapping(space)) {
                id = isl_space_get_tuple_id(space, isl_dim_set);
                isl_space_free(space);
                return id;
        }
        return node_id(isl_space_domain(isl_space_unwrap(space)));
}

/* Create and return an adg_var corresponding to "access" on "space".
 * If there is no array associated to the access, then we assume
 * it is an iterator and assign it type "int".
 */
static adg_var *new_var(pdg::access *access, __isl_take isl_space *space)
{
        adg_var *var;
        isl_ctx *ctx = isl_space_get_ctx(space);
        isl_id *id;
        const char *suffix;

        id = node_id(isl_space_copy(space));
        suffix = isl_id_get_name(id);
        isl_id_free(id);

        id = access_name(ctx, access, suffix);
        var = var_from_id(id, space);
        if (access->array)
                var->type = isl_id_alloc(ctx,
                                access->array->element_type->s.c_str(), NULL);
        else
                var->type = isl_id_alloc(ctx, "int", NULL);
        return var;
}

/* Return the schedule for "p_node", mapping the iteration domain
 * of "p_node" to the domain (with given "id") of the corresponding adg node.
 * In practice, we compose the pdg schedule with the mapping that
 * removes the dimensions with constant values.
 */
static __isl_give isl_map *node_schedule(pdg::node *p_node, adg *graph,
        __isl_take isl_id *id)
{
        isl_map *sched;

        sched = p_node->schedule->get_isl_map();
        sched = isl_map_apply_range(sched, isl_map_copy(graph->iterator_map));
        if (id)
                sched = isl_map_set_tuple_id(sched, isl_dim_out, id);

        return sched;
}

/* Return the schedule for "p_node", mapping the iteration domain
 * of "p_node" to the domain (with given "id") of the corresponding adg node.
 *
 * If "space" represents the space to which the schedule needs to be applied.
 * If it is a wrapped map, then we assume that the actual node schedule
 * applies to the domain of this wrapped map and we adjust the schedule
 * to preserve the range of this wrapped map.
 */
static __isl_give isl_map *extended_node_schedule(pdg::node *p_node, adg *graph,
        __isl_take isl_id *id, __isl_take isl_space *space)
{
        isl_map *sched;

        sched = node_schedule(p_node, graph, id);
        if (!isl_space_is_wrapping(space)) {
                isl_space_free(space);
        } else {
                isl_map *map;
                space = isl_space_unwrap(space);
                space = isl_space_map_from_set(isl_space_range(space));
                map = isl_map_identity(space);
                sched = isl_map_product(sched, map);
        }

        return sched;
}

/* Construct an isl_pw_aff from a map with a single output dimension.
 * The map needs to be single-valued in order to obtain a meaningful
 * result.
 */
static __isl_give isl_pw_aff *pw_aff_from_map(__isl_take isl_map *map)
{
        assert(isl_map_is_single_valued(map));
        return isl_map_dim_max(map, 0);
}

/* Create and return an adg_expr that corresponds to the given access
 * from the given node.  id represents the name of the corresponding adg_node.
 *
 * The access is assumed to be an access to the set of integers.
 * That is, the range is a nameless 1D space and the value is equal
 * to the index expression.
 */
static adg_expr *new_expression(adg *graph, pdg::node *node,
        pdg::access *access, __isl_take isl_id *id)
{
        isl_map *sched;
        isl_map *map;
        adg_expr *expr;

        sched = node_schedule(node, graph, isl_id_copy(id));
        map = access->map->get_isl_map();
        map = isl_map_apply_domain(map, sched);
        expr = new adg_expr;
        expr->name = access_name(isl_map_get_ctx(map), access,
                                isl_id_get_name(id));
        expr->expr = pw_aff_from_map(map);
        expr->expr = isl_pw_aff_coalesce(expr->expr);
        for (int i = 0; i < graph->iterators.size(); ++i)
                expr->expr = isl_pw_aff_set_dim_id(expr->expr,
                            isl_dim_in, i, isl_id_copy(graph->iterators[i]));

        isl_id_free(id);
        return expr;
}

/* Add an adg_expr to node->expressions for each access to the "set of
 * integers" from "call" (recursively) within the corresponding node p_node.
 */
static void add_expressions(adg *graph, adg_node *node, pdg::node *p_node,
        pdg::function_call *call)
{
        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) {
                        add_expressions(graph, node, p_node, coa->call);
                        continue;
                }

                assert(coa->type == pdg::call_or_access::t_access);
                if (coa->access->type == pdg::access::write)
                        continue;
                if (isl_map_has_tuple_id(coa->access->map->map, isl_dim_out))
                        continue;
                node->expressions.push_back(new_expression(graph, p_node,
                                        coa->access, isl_id_copy(node->name)));
        }
}

/* Append "var" with argument type "type" to "args",
 * provided such a combination doesn't appear in the list already.
 */
static void add_argument(std::vector<adg_arg *> &args, adg_var *var,
        enum adg_arg_type type)
{
        adg_arg *arg;

        for (int i = 0; i < args.size(); ++i) {
                if (type == args[i]->type &&
                    isl_pw_multi_aff_plain_is_equal(args[i]->var->access,
                                                        var->access)) {
                        delete var;
                        return;
                }
        }

        arg = new adg_arg;
        arg->var = var;
        arg->type = type;

        args.push_back(arg);
}

/* Recursively add an element to fn->out or fn->in for each argument of "call".
 * If we come across any "&", then we replace "type" by adg_arg_reference.
 */
static void add_arguments(adg_function *fn,
        pdg::function_call *call, __isl_keep isl_space *space,
        enum adg_arg_type type)
{
        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) {
                        enum adg_arg_type type_i = type;
                        if (!strcmp(coa->call->name->s.c_str(), "&"))
                                type_i = adg_arg_reference;
                        add_arguments(fn, coa->call, space, type_i);
                        continue;
                }

                assert(coa->type == pdg::call_or_access::t_access);
                if (coa->access->type == pdg::access::write)
                        add_argument(fn->out,
                            new_var(coa->access, isl_space_copy(space)), type);
                else
                        add_argument(fn->in,
                            new_var(coa->access, isl_space_copy(space)), type);
        }
}

/* Add the filters of "node" to "filters", having them refer to "space"
 * as their iteration domain.
 */
static void add_domain_filters(std::vector<adg_var *> &filters, pdg::node *node,
        __isl_keep isl_space *space)
{
        for (int i = 0; i < node->filters.size(); ++i) {
                pdg::call_or_access *coa = node->filters[i];
                assert(coa->type == pdg::call_or_access::t_access);
                filters.push_back(new_var(coa->access, isl_space_copy(space)));
        }
}

/* Set node->function based on "p_node" and the node domain "domain".
 * In particular, create an adg_function with the given domain
 * and add input and output arguments.
 * If any of the input arguments is an affine expression (as opposed to
 * an array access), then it is added to node->expressions.
 *
 * If p_node has any filters, then they are converted to filters on node.
 */
static void set_function(adg *adg, adg_node *node, pdg::node *p_node,
        __isl_take isl_set *domain)
{
        isl_ctx *ctx = isl_set_get_ctx(domain);
        const char *name;
        pdg::statement *stat = p_node->statement;
        adg_function *fn = new adg_function;
        isl_space *space;
        node->function = fn;

        space = isl_set_get_space(domain);
        fn->domain = new adg_domain(domain);

        add_domain_filters(fn->domain->filters, p_node, space);

        for (int i = 0; i < stat->top_outputs.size(); ++i)
                add_argument(fn->out,
                    new_var(stat->top_outputs[i], isl_space_copy(space)),
                    adg_arg_return);

        if (!stat->top_function)
                return;

        name = stat->top_function->name->s.c_str();
        fn->name = isl_id_alloc(ctx, name, NULL);

        add_expressions(adg, node, p_node, stat->top_function);
        add_arguments(fn, stat->top_function, space, adg_arg_value);

        isl_space_free(space);
}

/* Return the domain of "p_node" after scheduling.
 * "id" represents the name of the corresponding adg_node.
 *
 * If "p_node" has any filters, then its source iteration domain
 * is a wrapped map with the filters in the range.  The computed
 * node schedule therefore needs to take this filters into account
 * and so we pass along the domain space to extended_node_schedule().
 * In particular, we want the filter values to be preserved.
 */
static __isl_give isl_set *scheduled_domain(pdg::node *p_node, adg *adg,
        __isl_take isl_id *id)
{
        isl_set *domain;
        isl_map *sched;

        domain = p_node->source->get_isl_set();
        sched = extended_node_schedule(p_node, adg, id,
                                        isl_set_get_space(domain));
        domain = isl_set_apply(domain, sched);

        return domain;
}

/* Construct a schedule for the adg_node (called "id") corresponding to
 * "p_node".  Note that the domain of the adg_node is the result of
 * applying the p_node schedule to its domain, with some of the
 * dimensions with constant values removed (through composition with
 * adg->iterator_map).  The schedule for the adg_node then simply
 * needs to insert those dimensions with constant values back.
 *
 * If "p_node" has any filters, then its source iteration domain
 * is a wrapped map with the filters in the range.  These filters
 * need to be removed first.
 */
static __isl_give isl_map *adg_node_schedule(pdg::node *p_node, adg *adg,
        __isl_take isl_id *id)
{
        isl_set *domain;
        isl_map *sched;

        domain = p_node->source->get_isl_set();
        if (isl_set_is_wrapping(domain))
                domain = isl_map_domain(isl_set_unwrap(domain));
        sched = p_node->schedule->get_isl_map();
        domain = isl_set_apply(domain, sched);
        sched = isl_map_reverse(isl_map_copy(adg->iterator_map));
        sched = isl_map_intersect_range(sched, domain);
        sched = isl_map_set_tuple_id(sched, isl_dim_in, id);

        return sched;
}

/* Construct the name of the adg_node corresponding to "p_node".
 */
static __isl_give isl_id *node_id(isl_ctx *ctx, pdg::node *p_node)
{
        char buf[10];

        snprintf(buf, sizeof(buf), "ND_%d", p_node->nr);

        return isl_id_alloc(ctx, buf, NULL);
}

extern "C" {
        static isl_stat intersect_local_space(__isl_take isl_basic_set *bset,
                void *user);
}

/* Intersect the local space *user with the local space of "bset".
 */
static isl_stat intersect_local_space(__isl_take isl_basic_set *bset,
        void *user)
{
        isl_local_space *ls;
        isl_local_space **res = (isl_local_space **)user;

        ls = isl_basic_set_get_local_space(bset);
        isl_basic_set_free(bset);

        *res = isl_local_space_intersect(*res, ls);

        return isl_stat_ok;
}

/* Find the position of the first filter in "space".
 *
 * The given space may be the result of one of more nestings of the form
 *
 *      D -> [D -> local[..]]
 *
 * and/or a nesting of the form
 *
 *      D -> [D -> [dynamic controls]]
 *
 * and so we may have to dig down until we find a wrapped space
 * with an unnamed range.  If we find it, the position of the filters
 * in the original space is equal to the number of input dimensions
 * of that wrapped space.  Otherwise, there are no filters and we
 * return 0.
 */
static int filter_pos(__isl_take isl_space *space)
{
        int pos;

        if (!isl_space_is_wrapping(space)) {
                isl_space_free(space);
                return 0;
        }
        space = isl_space_unwrap(space);
        if (isl_space_has_tuple_id(space, isl_dim_out))
                return filter_pos(isl_space_domain(space));
        pos = isl_space_dim(space, isl_dim_in);
        isl_space_free(space);
        return pos;
}

/* Set the names of the input dimensions of "aff" according
 * to "filters", "iterators" and "controls".
 *
 * The first dimensions correspond to the iterators.
 * The are followed by the iterators, with the filters intermixed.
 */
static __isl_give isl_aff *set_names(__isl_take isl_aff *aff,
        std::vector<adg_var *> &filters, std::vector<isl_id *> &iterators,
        std::vector<adg_expr *> &controls)
{
        int pos = 0;
        int n_in = isl_aff_dim(aff, isl_dim_in);
        int fp;
        int nf;
        int ci;

        fp = filter_pos(isl_aff_get_domain_space(aff));
        nf = filters.size();

        for (int i = 0; i < iterators.size(); ++i, ++pos) {
                isl_id *id = isl_id_copy(iterators[i]);
                aff = isl_aff_set_dim_id(aff, isl_dim_in, pos, id);
        }

        for (ci = 0; ci < controls.size() && pos < fp; ++ci, ++pos) {
                isl_id *id = isl_id_copy(controls[ci]->name);
                aff = isl_aff_set_dim_id(aff, isl_dim_in, pos, id);
        }

        for (int i = 0; i < nf; ++i, ++pos) {
                isl_id *id;
                id = isl_pw_multi_aff_get_tuple_id(filters[i]->access,
                                                        isl_dim_out);
                aff = isl_aff_set_dim_id(aff, isl_dim_in, pos, id);
        }

        for (; ci < controls.size() && pos < n_in; ++ci, ++pos) {
                isl_id *id = isl_id_copy(controls[ci]->name);
                aff = isl_aff_set_dim_id(aff, isl_dim_in, pos, id);
        }

        return aff;
}

/* Set the names of the input dimensions of "pa" according
 * to "filters", "iterators" and "controls".
 *
 * The first dimensions correspond to the iterators.
 * The are followed by the iterators, with the filters intermixed.
 */
static __isl_give isl_pw_aff *set_names(__isl_take isl_pw_aff *pa,
        std::vector<adg_var *> &filters, std::vector<isl_id *> &iterators,
        std::vector<adg_expr *> &controls)
{
        int pos = 0;
        int n_in = isl_pw_aff_dim(pa, isl_dim_in);
        int fp;
        int nf;
        int ci;

        fp = filter_pos(isl_pw_aff_get_domain_space(pa));
        nf = filters.size();

        for (int i = 0; i < iterators.size(); ++i, ++pos) {
                isl_id *id = isl_id_copy(iterators[i]);
                pa = isl_pw_aff_set_dim_id(pa, isl_dim_in, pos, id);
        }

        for (ci = 0; ci < controls.size() && pos < fp; ++ci, ++pos) {
                isl_id *id = isl_id_copy(controls[ci]->name);
                pa = isl_pw_aff_set_dim_id(pa, isl_dim_in, pos, id);
        }

        for (int i = 0; i < nf; ++i, ++pos) {
                isl_id *id;
                id = isl_pw_multi_aff_get_tuple_id(filters[i]->access,
                                                        isl_dim_out);
                pa = isl_pw_aff_set_dim_id(pa, isl_dim_in, pos, id);
        }

        for (; ci < controls.size() && pos < n_in; ++ci, ++pos) {
                isl_id *id = isl_id_copy(controls[ci]->name);
                pa = isl_pw_aff_set_dim_id(pa, isl_dim_in, pos, id);
        }

        return pa;
}

/* For each of the local variables in "ls", create a corresponding
 * adg_expr and add it to "controls".
 *
 * "filters" contains the filters on the corresponding domain.
 * These filters appear as the first dimensions in "ls" and "filters" is
 * used to set the names of those dimensions.
 */
static void add_controls(adg *graph, std::vector<adg_var *> &filters,
        std::vector<adg_expr *> &controls,
        __isl_keep isl_local_space *ls)
{
        isl_ctx *ctx;
        int n_div;
        int n;

        ctx = isl_local_space_get_ctx(ls);
        n_div = isl_local_space_dim(ls, isl_dim_div);
        n = controls.size();
        for (int i = 0; i < n_div; ++i) {
                isl_aff *aff;
                adg_expr *expr;

                aff = isl_aff_floor(isl_local_space_get_div(ls, i));
                aff = set_names(aff, filters, graph->iterators, controls);
                expr = graph->to_control(aff);
                controls.push_back(expr);
        }
}

/* Apply the lifting "lifting" to domain->bounds and eliminate
 * redundant existentially quantified variables.
 */
static void apply_lifting(adg_domain *domain,
        __isl_take isl_basic_map *lifting)
{
        domain->bounds = isl_set_apply(domain->bounds,
                                        isl_map_from_basic_map(lifting));
        domain->bounds = isl_set_detect_equalities(domain->bounds);
}

/* Add static controls to "domain" based on the existentially quantified
 * variables in domain->bounds and set *lifting_p to the lifting that
 * corresponds to the added static controls.  That is, the control variables
 * correspond to the output variable in the nested map in the range
 * of the lifting.
 *
 * We first collect all existentially quantified variables in a single
 * local space.  If needed, we then add the corresponding static controls,
 * construct the corresponding lifting and finally apply it to domain->bounds.
 */
static void add_static_controls(adg *graph, adg_domain *domain,
        __isl_give isl_basic_map **lifting_p)
{
        isl_space *space;
        isl_local_space *ls;
        int n_div;
        isl_basic_map *lifting;

        space = isl_set_get_space(domain->bounds);
        ls = isl_local_space_from_space(space);
        isl_set_foreach_basic_set(domain->bounds, &intersect_local_space, &ls);

        n_div = isl_local_space_dim(ls, isl_dim_div);
        if (n_div == 0) {
                isl_local_space_free(ls);
                return;
        }

        add_controls(graph, domain->filters, domain->controls, ls);

        lifting = isl_local_space_lifting(ls);
        if (lifting_p)
                *lifting_p = isl_basic_map_copy(lifting);

        apply_lifting(domain, lifting);
}

/* Add copies of the elements in "src" to the back of "dst".
 */
static void copy_controls(std::vector<adg_expr *> &dst,
        std::vector<adg_expr *> &src)
{
        for (int i = 0; i < src.size(); ++i)
                dst.push_back(new adg_expr(*src[i]));
}

/* Add static controls to the adg_node "node".
 * In particular, add static controls to node->domain and if any
 * were added, copy them to node->function->domain and apply the corresponding
 * lifting.
 */
static void add_static_controls(adg *graph, adg_node *node)
{
        add_static_controls(graph, node->domain, &node->lifting);

        if (!node->lifting)
                return;

        copy_controls(node->function->domain->controls, node->domain->controls);
        apply_lifting(node->function->domain,
                        isl_basic_map_copy(node->lifting));
}

/* Add an adg_node corresponding to "p_node" to the graph.
 * We only construct the domain, the schedule, the expressions
 * and the function.
 * The ports and gates are created during the construction of the edges.
 *
 * The domain of the function may be subjected to filtering,
 * but the domain of the node itself may not as it should include
 * the domains of the ports reading the values of the filters.
 * The filters are therefore projected out from the node domain.
 */
static void add_node(isl_ctx *ctx, adg *graph, pdg::node *p_node)
{
        adg_node *node = new adg_node;
        isl_set *domain;

        node->name = node_id(ctx, p_node);

        domain = scheduled_domain(p_node, graph, isl_id_copy(node->name));
        node->schedule = adg_node_schedule(p_node, graph,
                                                isl_id_copy(node->name));
        set_function(graph, node, p_node, isl_set_copy(domain));
        if (isl_set_is_wrapping(domain))
                domain = isl_map_domain(isl_set_unwrap(domain));
        domain = isl_set_from_basic_set(isl_set_simple_hull(domain));
        node->domain = new adg_domain(domain);

        add_static_controls(graph, node);

        graph->nodes.push_back(node);
}

/* Is "name" of the form __last_*?
 */
static bool is_control(const char *name)
{
        const char *prefix = "__last_";
        size_t prefix_len = strlen(prefix);

        return !strncmp(name, prefix, prefix_len);
}

/* Is "name" of the form __last_<node_name>*?
 */
static bool is_local_control(const char *name, const char *node_name)
{
        const char *prefix = "__last_";
        size_t prefix_len = strlen(prefix);

        if (strncmp(name, prefix, prefix_len) != 0)
                return 0;
        return !strncmp(name + prefix_len, node_name, strlen(node_name));
}

/* Is the name of "id" of the form __last_*?
 */
static bool is_control(__isl_keep isl_id *id)
{
        return is_control(isl_id_get_name(id));
}

/* Is the name of the i-th parameter of map of the form __last_*?
 */
static bool is_control(__isl_keep isl_map *map, int i)
{
        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 is_control(name);
}

/* Move all parameters of the form __last_* into the range of a wrapped
 * map with "domain" as domain.
 *
 * We first create dimensions in the range of the wrapped map, equating
 * them to the corresponding parameters.
 * At the end, we project out the parameters.
 */
static void move_filters(adg_domain *domain)
{
        isl_space *space;
        isl_set *set;
        isl_map *map;
        int nparam;

        set = domain->bounds;
        space = isl_set_get_space(set);
        map = isl_map_from_domain(set);

        nparam = isl_map_dim(map, isl_dim_param);
        for (int i = 0; i < nparam; ++i) {
                int pos;
                isl_id *id;
                if (!is_control(map, i))
                        continue;
                pos = isl_map_dim(map, isl_dim_out);
                map = isl_map_add_dims(map, isl_dim_out, 1);
                map = isl_map_equate(map, isl_dim_param, i, isl_dim_out, pos);
                id = isl_map_get_dim_id(map, isl_dim_param, i);
                domain->filters.push_back(var_from_id(id,
                                                        isl_space_copy(space)));
        }

        for (int i = nparam - 1; i >= 0; --i) {
                if (!is_control(map, i))
                        continue;
                map = isl_map_project_out(map, isl_dim_param, i, 1);
        }

        domain->bounds = isl_map_wrap(map);
        isl_space_free(space);
}

/* Auxiliary data used during the construction of edges.
 *
 * dep is the dependence that is being converted into one or more edges.
 * container is the dependence that contains information about the buffer
 *      size.  It may be dep itself or it may be the pn_union dependence
 *      containing dep.
 * id is the name of the edge.
 * from_node is the source node.
 * to_node is the target node.
 * rel is the original dependence relation.
 * rel_maff is that part of rel that corresponds to maff.
 * range_filters_map is a map that adds back the range filters.
 * maff is the mapping that will be assigned to edge->map.
 * in_domain is the domain of the input port.
 *
 * in_filters are filters that should be added to input ports.
 * out_filters are filters that should be added to output ports.
 *
 * edge_nr is the sequence number of the original (non-control) edge.
 * port_nr is a pointer to the sequence number of the port
 *
 * lifting is the lifting used on the input port domain
 * in_controls are the controls for the input port domain.  They include
 *      the controls of the node domain and the extra controls induced by
 *      lifting.
 */
struct add_edge_data {
        adg *graph;
        pdg::dependence *dep;
        pdg::dependence *container;
        isl_id *id;
        adg_node *from_node;
        adg_node *to_node;
        isl_map *rel;
        isl_map *range_filters_map;
        isl_map *rel_maff;
        isl_multi_aff *maff;
        isl_basic_set *in_domain;
        enum adg_edge_type type;

        std::vector<adg_var *> in_filters;
        std::vector<adg_var *> out_filters;

        int edge_nr;
        int *port_nr;

        isl_basic_map *lifting;
        std::vector<adg_expr *> in_controls;
};

enum adg_port_type {
        adg_port_input,
        adg_port_output
};

/* Set the name of "port" to
 *
 *      <node>IP_<edge>_<nr>_V_<arg_pos>
 * or
 *      <node>OP_<edge>_<nr>_V_<arg_pos>
 *
 * depending on whether type is adg_port_input or adg_port_output.
 * The name includes the access->nr so that two edges between the same
 * pair of nodes that have been combined into a single pn_union edge
 * would not get identical port names.
 */
static void set_port_name(adg_port *port, enum adg_port_type type,
        __isl_keep isl_id *node_id, __isl_keep isl_id *edge_id, int nr)
{
        char buf[100];
        isl_ctx *ctx;
        const char *s_type;

        ctx = isl_id_get_ctx(edge_id);

        if (type == adg_port_input)
                s_type = "IP";
        else
                s_type = "OP";
        snprintf(buf, sizeof(buf), "%s%s_%s_%d_V_%d",
                isl_id_get_name(node_id), s_type,
                isl_id_get_name(edge_id), nr, port->arg_pos);
        port->name = isl_id_alloc(ctx, buf, NULL);
}

/* Set the binding variable on "port" by calling new_var().
 */
static void set_port_var(adg_port *port, pdg::access *access,
        __isl_keep isl_basic_set *bset)
{
        adg_var *var;
        isl_space *space;

        space = isl_basic_set_get_space(bset);
        var = new_var(access, space);
        port->vars.push_back(var);
}

/* Set the binding variables on "port", one for each element
 * in "dep_controls".  These binding variables are control variables
 * and they are assumed to of tyoe "int".
 */
static void set_port_vars(adg_port *port, seq<str> &dep_controls,
        __isl_keep isl_basic_set *bset)
{
        isl_ctx *ctx;
        isl_space *space;

        ctx = isl_basic_set_get_ctx(bset);
        space = isl_basic_set_get_space(bset);
        for (int i = 0; i < dep_controls.size(); ++i) {
                isl_id *id;
                adg_var *var;

                id = isl_id_alloc(ctx, dep_controls[i]->s.c_str(), NULL);
                var = var_from_id(id, isl_space_copy(space));
                var->type = isl_id_alloc(ctx, "int", NULL);
                port->vars.push_back(var);
        }
        isl_space_free(space);
}

/* Create and return a port of type "type" belonging to the node called
 * "node_id" and attached to the edge called "edge_id".
 * "access" is the corresponding access.
 * "nr" is the sequence number.
 * "dep_controls" contains the names of the control variables.
 * If the list contains any elements, then the port is connected
 * to a control edge.  Otherwise, it is connected to a data edge.
 * "bset" represents the iteration domain and "controls" are the controls
 * that need to be added based on previous liftings.
 * If "bset" has any existentially quantified variables left, then we
 * need to apply an additional lifting and append the corresponding
 * control variables.
 * "filters" contains the dynamic controls.
 */
static adg_port *create_port(adg *graph, enum adg_port_type type,
        seq<str> &dep_controls, pdg::access *access,
        __isl_keep isl_id *node_id, __isl_keep isl_id *edge_id, int edge_nr,
        int nr, __isl_take isl_basic_set *bset,
        std::vector<adg_var *> &filters, std::vector<adg_expr *> &controls)
{
        isl_local_space *ls = NULL;
        adg_port *port = new adg_port;

        port->edge_nr = edge_nr;

        if (isl_basic_set_dim(bset, isl_dim_div) != 0) {
                isl_basic_map *lifting;
                ls = isl_basic_set_get_local_space(bset);
                lifting = isl_local_space_lifting(isl_local_space_copy(ls));
                bset = isl_basic_set_apply(bset, lifting);
                bset = isl_basic_set_detect_equalities(bset);
        }

        port->arg_pos = access->nr;
        set_port_name(port, type, node_id, edge_id, nr);

        port->node_name = isl_id_copy(node_id);
        port->edge_name = isl_id_copy(edge_id);
        if (dep_controls.size() > 0)
                set_port_vars(port, dep_controls, bset);
        else
                set_port_var(port, access, bset);
        port->domain = new adg_domain(isl_set_from_basic_set(bset));

        for (int i = 0; i < filters.size(); ++i)
                port->domain->filters.push_back(new adg_var(*filters[i]));
        for (int i = 0; i < controls.size(); ++i)
                port->domain->controls.push_back(new adg_expr(*controls[i]));

        if (ls) {
                add_controls(graph, filters, port->domain->controls, ls);
                isl_local_space_free(ls);
        }

        return port;
}

/* Add an edge with a convex input port domain (data->in_domain)
 * and a convex output port domain (bset).
 *
 * We create the two ports, add them to the appropriate nodes
 * and add an edge that referes to the nodes and ports.
 */
static isl_stat add_edge_basic_in(__isl_take isl_basic_set *bset, void *user)
{
        add_edge_data *data = (add_edge_data *) user;
        adg_edge *edge = new adg_edge;
        adg_port *port;

        edge->name = isl_id_copy(data->id);
        edge->type = data->type;
        edge->map = isl_multi_aff_copy(data->maff);
        edge->from_node_name = isl_id_copy(data->from_node->name);
        edge->to_node_name = isl_id_copy(data->to_node->name);
        if (data->container->value_size) {
                isl_ctx *ctx = isl_basic_set_get_ctx(bset);
                edge->value_size = isl_val_int_from_si(ctx,
                                            data->container->value_size->v);
        }

        port = create_port(data->graph, adg_port_input,
                data->dep->to_controls, data->dep->to_access,
                data->to_node->name, data->id, data->edge_nr,
                *data->port_nr, isl_basic_set_copy(data->in_domain),
                data->in_filters, data->in_controls);
        data->to_node->input_ports.push_back(port);
        edge->to_port_name = isl_id_copy(port->name);

        port = create_port(data->graph, adg_port_output,
                data->dep->from_controls, data->dep->from_access,
                data->from_node->name, data->id, data->edge_nr,
                *data->port_nr, isl_basic_set_copy(bset),
                data->out_filters, data->from_node->domain->controls);
        data->from_node->output_ports.push_back(port);
        edge->from_port_name = isl_id_copy(port->name);

        (*data->port_nr)++;

        data->graph->edges.push_back(edge);

        isl_basic_set_free(bset);
        return isl_stat_ok;
}

/* Does the list of (dynamic) control variables node->function->ctrl
 * include "id"?
 */
static bool has_control(adg_node *node, __isl_keep isl_id *id)
{
        for (int i = 0; i < node->function->ctrl.size(); ++i)
                if (node->function->ctrl[i]->name == id)
                        return true;
        return false;
}

/* Add elements to node->function->ctrl for each element of dep->from_controls,
 * provided the element is not in there already.
 *
 * We only add elements that correspond to last iterations of "node".
 * The given dependence may be the result of reuse detection and may
 * therefore propagate controls from one access to the next in some other
 * node.
 *
 * To find out which value should be assigned to the variable,
 * we look at the final part of the name of the control variable.
 * If this final part is "valid", then the function needs
 * to assign the value "1".  Otherwise, the final part is
 * an integer and then we should assign the value of the
 * original corresponding iterator.  This value is obtained
 * from the schedule of "node".
 */
static void add_control_variables(isl_ctx *ctx, adg *graph, adg_node *node,
        pdg::dependence *dep)
{
        isl_map *sched;
        isl_pw_multi_aff *pma;
        isl_space *space;
        isl_local_space *ls;
        char *node_name;

        if (dep->from_controls.size() == 0)
                return;

        sched = node_schedule(dep->from, graph, isl_id_copy(node->name));
        node_name = strdup(isl_map_get_tuple_name(sched, isl_dim_in));
        pma = isl_pw_multi_aff_from_map(isl_map_reverse(sched));
        space = isl_set_get_space(node->domain->bounds);
        ls = isl_local_space_from_space(space);

        for (int i = 0; i < dep->from_controls.size(); ++i) {
                adg_expr *expr;
                isl_aff *aff;
                isl_pw_aff *pa;
                int pos;
                isl_id *id;
                const char *name = dep->from_controls[i]->s.c_str();

                id = isl_id_alloc(ctx, name, NULL);

                if (!is_local_control(name, node_name) ||
                    has_control(node, id)) {
                        isl_id_free(id);
                        continue;
                }

                name = strrchr(name, '_');
                assert(name);

                expr = new adg_expr;
                if (!strcmp(name + 1, "valid")) {
                        aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
                        aff = isl_aff_add_constant_si(aff, 1);
                        pa = isl_pw_aff_from_aff(aff);
                } else {
                        pos = atoi(name + 1);
                        pa = isl_pw_multi_aff_get_pw_aff(pma, pos);
                }

                pa = set_names(pa, node->domain->filters, graph->iterators,
                                node->domain->controls);

                expr->name = id;
                expr->expr = pa;
                node->function->ctrl.push_back(expr);
        }

        free(node_name);
        isl_local_space_free(ls);
        isl_pw_multi_aff_free(pma);
}

/* Add an edge with a convex input port domain (bset).
 * We compute the corresponding output port domain by applying
 * the dependence relation and apply the required liftings in the from
 * domain.  The result may in principle be a union again and so we
 * split that up as well.
 * The lifting required by the input port (computed in add_edge_set)
 * is applied to the input port domain.  Note that we cannot
 * apply this lifting earlier because we need the original input port
 * domain (without lifting) to compute the output port domain.
 */
static isl_stat add_edge_basic(__isl_take isl_basic_set *bset, void *user)
{
        isl_stat r;
        add_edge_data *data = (add_edge_data *) user;
        isl_set *set;

        data->in_domain = isl_basic_set_copy(bset);
        data->in_domain = isl_basic_set_apply(data->in_domain,
                                isl_basic_map_copy(data->lifting));
        data->in_domain = isl_basic_set_detect_equalities(data->in_domain);
        set = isl_set_from_basic_set(bset);
        set = isl_set_apply(set, isl_map_copy(data->rel_maff));
        if (data->from_node->lifting)
                set = isl_set_apply(set, isl_map_from_basic_map(
                                isl_basic_map_copy(data->from_node->lifting)));
        set = isl_set_detect_equalities(set);
        set = isl_set_compute_divs(set);

        r = isl_set_foreach_basic_set(set, &add_edge_basic_in, data);

        isl_set_free(set);
        isl_basic_set_free(data->in_domain);
        return r;
}

/* Save a copy of "map" in data->rel, remove the range filters (if any)
 * and return the result.  The inverse of the mapping used to remove
 * the filters is save in data->range_filters_map so that the filters
 * can be reintroduced in insert_range_filters.
 */
static __isl_give isl_map *remove_range_filters(__isl_take isl_map *map,
        add_edge_data *data)
{
        isl_space *space;

        data->rel = isl_map_copy(map);

        space = isl_space_range(isl_map_get_space(map));
        if (isl_space_is_wrapping(space)) {
                isl_map *fm = isl_map_universe(isl_space_unwrap(space));
                fm = isl_map_domain_map(fm);
                map = isl_map_apply_range(map, isl_map_copy(fm));
                data->range_filters_map = isl_map_reverse(fm);
        } else {
                space = isl_space_map_from_set(space);
                data->range_filters_map = isl_map_identity(space);
        }

        return map;
}

/* Reintroduce the filters removed in remove_range_filters.
 */
static __isl_give isl_map *insert_range_filters(__isl_take isl_map *map,
        add_edge_data *data)
{
        map = isl_map_apply_range(map, isl_map_copy(data->range_filters_map));
        map = isl_map_intersect(map, isl_map_copy(data->rel));

        return map;
}

/* Add edges for the given input port domain (set) and the given
 * mapping (maff) to the corresponding output port domain.
 *
 * The lifting corresponding to the domain of the destination node
 * has already been applied, but "maff" may require additional liftings
 * to be applied to the input port domain.
 *
 * The given isl_multi_aff is also converted into an isl_basic_map
 * for use in the construction of the output port domains
 * in add_edge_basic().  After the conversion, we add back the filters
 * that were removed right before the call to isl_pw_multi_aff_from_map.
 */
static isl_stat add_edge_set(__isl_take isl_set *set,
        __isl_take isl_multi_aff *maff, void *user)
{
        add_edge_data *data = (add_edge_data *) user;
        isl_stat r;
        isl_local_space *ls;

        data->rel_maff = isl_map_from_basic_map(isl_basic_map_from_multi_aff(
                                                    isl_multi_aff_copy(maff)));
        data->rel_maff = insert_range_filters(data->rel_maff, data);

        maff = isl_multi_aff_lift(maff, &ls);
        copy_controls(data->in_controls, data->to_node->domain->controls);
        add_controls(data->graph, data->in_filters, data->in_controls, ls);
        data->lifting = isl_local_space_lifting(ls);

        data->maff = maff;

        r = isl_set_foreach_basic_set(set, &add_edge_basic, data);

        for (int i = 0; i < data->in_controls.size(); ++i)
                delete data->in_controls[i];
        data->in_controls.clear();
        isl_basic_map_free(data->lifting);
        isl_set_free(set);
        isl_map_free(data->rel_maff);
        isl_multi_aff_free(maff);

        return r;
}

/* Does "rel" have any parameter of the form __last_*?
 */
static bool has_filters(__isl_keep isl_map *rel)
{
        int nparam;

        nparam = isl_map_dim(rel, isl_dim_param);
        for (int i = 0; i < nparam; ++i)
                if (is_control(rel, i))
                        return true;

        return false;
}

/* Remove all parameters of the form __last_* from "rel".
 */
static __isl_give isl_map *remove_all_filters(__isl_take isl_map *rel)
{
        int nparam;

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

        return rel;
}

/* For each parameter of the form __last_*, add it to both
 * data->in_filters and data->out_filters, in each case defined
 * over the appropriate domain.
 */
static void extract_filters(__isl_take isl_map *rel, add_edge_data *data)
{
        isl_space *domain;
        isl_space *range;
        isl_space *space;
        int nparam;

        nparam = isl_map_dim(rel, isl_dim_param);
        space = isl_map_get_space(rel);
        domain = isl_space_domain(isl_space_copy(space));
        range = isl_space_range(space);

        for (int i = 0; i < nparam; ++i) {
                isl_id *id;

                if (!is_control(rel, i))
                        continue;

                id = isl_map_get_dim_id(rel, isl_dim_param, i);
                data->in_filters.push_back(var_from_id(isl_id_copy(id),
                                                isl_space_copy(domain)));
                data->out_filters.push_back(var_from_id(id,
                                                isl_space_copy(range)));
        }

        isl_space_free(domain);
        isl_space_free(range);
}

/* Replace both domain and range of "rel" by a wrapped map with the original
 * set as domain and dimensions corresponding to the parameters
 * referenced by the elements in "filters" as range and then
 * remove those parameters.
 * The overall effect is that those parameters are moved into
 * the ranges of the wrapped maps.
 */
static __isl_give isl_map *move_filters(__isl_take isl_map *rel,
        std::vector<adg_var *> &filters)
{
        isl_space *space;
        isl_map *map;

        space = isl_space_domain(isl_map_get_space(rel));
        space = isl_space_from_domain(space);
        map = isl_map_universe(space);
        for (int i = 0; i < filters.size(); ++i) {
                int param;
                int pos;
                isl_id *id;

                id = isl_pw_multi_aff_get_tuple_id(filters[i]->access,
                                                    isl_dim_out);
                param = isl_map_find_dim_by_id(map, isl_dim_param, id);
                isl_id_free(id);

                pos = isl_map_dim(map, isl_dim_out);
                map = isl_map_add_dims(map, isl_dim_out, 1);
                map = isl_map_equate(map, isl_dim_param, param,
                                                isl_dim_out, pos);
        }
        map = isl_map_domain_map(map);

        rel = isl_map_apply_range(map, rel);

        for (int i = 0; i < filters.size(); ++i) {
                int param;
                isl_id *id;

                id = isl_pw_multi_aff_get_tuple_id(filters[i]->access,
                                                    isl_dim_out);
                param = isl_map_find_dim_by_id(rel, isl_dim_param, id);
                isl_id_free(id);

                rel = isl_map_project_out(rel, isl_dim_param, param, 1);
        }

        space = isl_space_unwrap(isl_space_domain(isl_map_get_space(rel)));
        map = isl_map_range_map(isl_map_universe(space));
        rel = isl_map_range_product(rel, map);

        return rel;
}

/* Determine the appropriate adg_edge_type for "dep".
 */
static enum adg_edge_type dep_type(pdg::dependence *dep)
{
        if (dep->reordering)
                return adg_edge_generic;
        else if (dep->multiplicity)
                return adg_edge_broadcast;
        else if (dep->type == pdg::dependence::pn_shift)
                return adg_edge_shift_register;
        else
                return adg_edge_fifo;
}

/* Lift the domain of the relation "rel" according to domain->lifting,
 * if any.
 */
static __isl_give isl_map *lift(__isl_take isl_map *rel, adg_node *domain)
{
        if (domain->lifting) {
                isl_basic_map *lifting;
                lifting = isl_basic_map_copy(domain->lifting);
                rel = isl_map_apply_domain(rel,
                                            isl_map_from_basic_map(lifting));
                rel = isl_map_detect_equalities(rel);
        }

        return rel;
}

/* If "dom" is a wrapped map, then add the filters of "node" to "filters".
 */
static void extract_domain_filters(__isl_take isl_space *space,
        std::vector<adg_var *> &filters, pdg::node *node)
{
        if (isl_space_is_wrapping(space))
                add_domain_filters(filters, node, space);

        isl_space_free(space);
}

/* Extract the filters on the output and input ports from the "from"
 * and "to" nodes of "rel".
 */
static void extract_domain_filters(__isl_keep isl_map *rel, add_edge_data *data)
{
        isl_space *space;

        space = isl_space_domain(isl_map_get_space(rel));
        extract_domain_filters(space, data->out_filters, data->dep->from);

        space = isl_space_range(isl_map_get_space(rel));
        extract_domain_filters(space, data->in_filters, data->dep->to);
}

/* Add edges corresponding to "dep" for the relation "rel", which
 * may be a subset of dep->relation or dep->controlled_relation.
 * "container" contains information about the required buffer sizes.
 * "id" is the name that should be given to all created edges.
 * "type" is the type of the created edges.
 *
 * If "dep" is a control dependence (i.e., if it has elements
 * in its from_controls), then add corresponding control variable
 * to the from node.
 *
 * We schedule the domain and range of "rel" and extract the
 * domain filters for later use.  We currently only allow such filters
 * on dependences without control parameters.
 *
 * Since "rel" is a subset of dep->relation, it has the source as domain
 * and the sink as range.  Since the mapping on the edges map iterations
 * of the input port to iterations of the corresponding output port,
 * we need to invert it.  Then we apply the lifting on the
 * sink node as the initial static control variables on the input port domain
 * need to be the same as those of the node domain.  The control variables
 * themselves are copied to data->in_controls in add_edge_set().
 *
 * If "type" is adg_edge_broadcast, then a given write may be
 * associated to several (consecutive) reads in the original
 * dependence relation.  In the ADG, we only associate the write
 * with the first of those reads.
 *
 * If there are any dynamic control variables, we extract them
 * and move them from the parameters into the domain of the relation.
 * For loops however, we simply remove them.
 *
 * Finally, we construct an explicit function representation of the
 * mapping and consider each convex piece of the domain in turn.
 * This is needed because the bounds on the domains have to be convex.
 * Before we compute this explicit representation, we first remove
 * the range filters as they may not be uniquely defined in terms
 * of the source filters.
 */
static void add_edge(PDG *pdg, adg *adg,
        pdg::dependence *dep, pdg::dependence *container,
        __isl_take isl_id *id, int edge_nr, __isl_take isl_map *rel,
        enum adg_edge_type type, int *port_nr)
{
        isl_ctx *ctx;
        isl_pw_multi_aff *pma;
        int res;
        add_edge_data data = { adg, dep, container };

        ctx = pdg->get_isl_ctx();

        data.type = type;
        data.id = id;
        data.from_node = adg->node_by_id(node_id(ctx, dep->from));
        data.to_node = adg->node_by_id(node_id(ctx, dep->to));
        data.port_nr = port_nr;
        data.edge_nr = edge_nr;

        add_control_variables(ctx, adg, data.from_node, dep);

        rel = isl_map_apply_domain(rel,
                extended_node_schedule(dep->from, adg,
                        isl_id_copy(data.from_node->name),
                        isl_space_domain(isl_map_get_space(rel))));
        rel = isl_map_apply_range(rel,
                extended_node_schedule(dep->to, adg,
                        isl_id_copy(data.to_node->name),
                        isl_space_range(isl_map_get_space(rel))));
        extract_domain_filters(rel, &data);
        if (data.out_filters.size() || data.in_filters.size())
                assert(!dep->controlled_relation);
        if (type == adg_edge_broadcast)
                rel = isl_map_lexmin(rel);
        rel = isl_map_reverse(rel);
        rel = lift(rel, data.to_node);
        if (has_filters(rel)) {
                if (dep->from != dep->to) {
                        extract_filters(rel, &data);
                        rel = move_filters(rel, data.in_filters);
                } else
                        rel = remove_all_filters(rel);
        }
        rel = remove_range_filters(rel, &data);
        pma = isl_pw_multi_aff_from_map(rel);

        res = isl_pw_multi_aff_foreach_piece(pma, &add_edge_set, &data);

        isl_pw_multi_aff_free(pma);
        isl_map_free(data.range_filters_map);
        isl_map_free(data.rel);
        isl_id_free(data.id);

        for (int i = 0; i < data.in_filters.size(); ++i)
                delete data.in_filters[i];
        for (int i = 0; i < data.out_filters.size(); ++i)
                delete data.out_filters[i];
}

/* Create and return an isl_id of the form
 *
 *      ED_<i>
 * or
 *      CED_<i>
 *
 * depending on whether "dep" is a control edge.
 */
static __isl_give isl_id *edge_name(isl_ctx *ctx, pdg::dependence *dep, int i)
{
        char buf[19];
        bool control = dep->from_controls.size() > 0;

        snprintf(buf, sizeof(buf), "%sED_%d", control ? "C" : "", i);
        return isl_id_alloc(ctx, buf, NULL);
}

/* Add edges corresponding to "dep".
 * "container" contains information about the required buffer sizes.
 * "id" is the name that should be given to all created edges.
 *
 * The dependence relation is taken from dep->controlled_relation
 * if it is not NULL.  Otherwise, it is taken from dep->relation.
 *
 * We look for pn_hold dependences with overlapping domains.
 * A pn_hold dependence signifies that a value available at the source
 * iteration should be kept until the next iteration (= target of dependence).
 * If there is a pn_hold dependence whose domain overlaps with the target
 * of the given dependence, then we turn the entire given dependence into a
 * "sticky" fifo.
 * If no such pn_hold dependences were found, then a regular fifo edge
 * is created.
 *
 * Obviously, we should only convert fifos into sticky fifos.
 * So, if "dep" is not a fifo, we should just construct fifos for
 * the associated pn_hold dependences.
 */
static void add_edge(PDG *pdg, adg *adg,
        pdg::dependence *dep, pdg::dependence *container,
        __isl_take isl_id *id, int edge_nr, int *port_nr)
{
        isl_ctx *ctx;
        isl_map *rel;
        enum adg_edge_type type;

        ctx = pdg->get_isl_ctx();

        assert(dep->type == pdg::dependence::pn ||
               dep->type == pdg::dependence::pn_shift ||
               dep->type == pdg::dependence::pn_part ||
               dep->type == pdg::dependence::flow);

        if (dep->controlled_relation)
                rel = dep->controlled_relation->get_isl_map();
        else
                rel = dep->relation->get_isl_map();

        type = dep_type(dep);

        for (int j = 0; j < pdg->dependences.size(); ++j) {
                pdg::dependence *hold_dep = pdg->dependences[j];
                isl_map *hold_rel;
                bool empty;

                if (hold_dep->type != pdg::dependence::pn_hold)
                        continue;
                if (dep->to != hold_dep->from)
                        continue;
                if (dep->array != hold_dep->array)
                        continue;
                if (dep->to_access != hold_dep->from_access)
                        continue;

                if (hold_dep->controlled_relation)
                        hold_rel = hold_dep->controlled_relation->get_isl_map();
                else
                        hold_rel = hold_dep->relation->get_isl_map();

                if (type != adg_edge_fifo) {
                        isl_id *id = edge_name(ctx, pdg->dependences[j], j);
                        add_edge(pdg, adg, hold_dep, hold_dep, id, edge_nr,
                                hold_rel, adg_edge_fifo, port_nr);
                        continue;
                }

                hold_rel = isl_map_intersect_range(isl_map_copy(rel),
                                                    isl_map_domain(hold_rel));
                empty = isl_map_is_empty(hold_rel);
                isl_map_free(hold_rel);

                if (!empty) {
                        type = adg_edge_sticky_fifo;
                        break;
                }
        }

        add_edge(pdg, adg, dep, container, id, edge_nr, rel, type, port_nr);
}

/* Add edges corresponding to "dep".
 * If it is a pn_union, then all the corresponding pn_part dependences
 * should get the same name.
 */
static void add_union_edge(PDG *pdg, adg *adg, pdg::dependence *dep, int i)
{
        isl_ctx *ctx;
        isl_id *id;
        int port_nr = 0;

        ctx = pdg->get_isl_ctx();

        id = edge_name(ctx, dep, i);

        if (dep->type != pdg::dependence::pn_union) {
                add_edge(pdg, adg, dep, dep, id, i, &port_nr);
                return;
        }

        for (int j = 0; j < pdg->dependences.size(); ++j) {
                pdg::dependence *part_dep = pdg->dependences[j];

                if (part_dep->type != pdg::dependence::pn_part)
                    continue;
                if (part_dep->container != dep)
                    continue;

                add_edge(pdg, adg, part_dep, dep, isl_id_copy(id), i, &port_nr);
        }

        isl_id_free(id);
}

/* Auxiliary data used during the construction of gates.
 *
 * nr points to the sequence number.
 * from is the source access.
 * to is the target access.
 */
struct add_wire_data {
        int *nr;
        pdg::access *from;
        pdg::access *to;
        adg_node *node;
};

extern "C" {
        static isl_stat add_wire_basic(__isl_take isl_basic_set *bset,
                void *user);
}

/* Add a wire with the convex domain "bset".
 * To ensure that the initial control variables of the gate are the same as
 * that of the node, we apply the node lifting, if any, and copy the
 * static control variables.
 *
 * If there are any dynamic control variables among the parameters,
 * we move them into the domain of a wrapped map.
 */
static isl_stat add_wire_basic(__isl_take isl_basic_set *bset, void *user)
{
        add_wire_data *data = (add_wire_data *) user;
        isl_ctx *ctx;
        isl_space *space;
        adg_gate *gate = new adg_gate;
        char buf[100];

        ctx = isl_basic_set_get_ctx(bset);
        space = isl_basic_set_get_space(bset);
        snprintf(buf, sizeof(buf), "%sID_%d",
                isl_id_get_name(data->node->name), (*data->nr)++);
        gate->name = isl_id_alloc(ctx, buf, NULL);
        gate->in = new_var(data->from, isl_space_copy(space));
        gate->out = new_var(data->to, space);

        gate->node_name = isl_id_copy(data->node->name);
        gate->domain = new adg_domain(isl_set_from_basic_set(bset));
        if (data->node->lifting)
                apply_lifting(gate->domain,
                                isl_basic_map_copy(data->node->lifting));
        copy_controls(gate->domain->controls, data->node->domain->controls);
        move_filters(gate->domain);

        data->node->gates.push_back(gate);

        return isl_stat_ok;
}

/* Add gates corresponding to the wire "dep".
 * "g_nr" is a pointer to the sequence number of gates.
 * The gate copies the variable corresponding to the from_access
 * to the variable corresponding to the to_access.
 * The dependence relation of a wire is always an identity relation,
 * so we can just take the domain of this relation.
 * We schedule both this domain and the dynamic control variables, if any.
 */
static void add_wire_gate(PDG *pdg, adg *adg, pdg::dependence *dep, int *g_nr)
{
        isl_map *rel;
        isl_set *dom;
        isl_ctx *ctx;
        isl_id *id;
        struct add_wire_data data = { g_nr, dep->from_access, dep->to_access };

        ctx = pdg->get_isl_ctx();
        rel = dep->relation->get_isl_map();
        dom = isl_map_domain(rel);
        id = node_id(ctx, dep->to);
        data.node = adg->node_by_id(isl_id_copy(id));
        dom = isl_set_apply(dom, node_schedule(dep->from, adg, id));
        isl_set_foreach_basic_set(dom, &add_wire_basic, &data);
        isl_set_free(dom);
}

/* Construct a map that removes some dimensions with known constant
 * values from the schedule domain.
 * The map is stored in graph->iterator_map.
 * Names for the iterators in the domain of this map are stored
 * in graph->all_iterators, while the names for the iterators
 * that are kept in the range are stored in graph->iterators.
 */
static void compute_iterator_map(adg *graph, PDG *pdg)
{
        int n_it;
        int n_all;
        isl_ctx *ctx;
        isl_space *space;
        isl_map *map;
        char buf[20];

        n_all = pdg->statement_dimensions.size();
        n_it = 0;
        for (int i = 0; i < n_all; ++i)
                if (!pdg->statement_dimensions[i])
                        n_it++;

        ctx = pdg->get_isl_ctx();
        space = isl_space_alloc(ctx, 0, n_all, n_it);
        map = isl_map_universe(space);

        n_it = 0;
        for (int i = 0; i < n_all; ++i) {
                isl_id *id;

                snprintf(buf, sizeof(buf), "c%d", i);
                id = isl_id_alloc(ctx, buf, NULL);
                graph->all_iterators.push_back(id);
                map = isl_map_set_dim_id(map, isl_dim_in, i, isl_id_copy(id));

                if (pdg->statement_dimensions[i])
                        continue;
                graph->iterators.push_back(isl_id_copy(id));
                map = isl_map_equate(map, isl_dim_in, i, isl_dim_out, n_it);
                n_it++;
        }

        graph->iterator_map = map;
}

/* Create an adg_param for each element in pdg->params.
 * param->val is obtained from pdg->params[i]->value, if any.
 * param->lb and param->ub are obtained from the context.
 */
static void extract_params(adg *adg, PDG *pdg)
{
        isl_ctx *ctx;
        isl_local_space *ls;

        ctx = pdg->get_isl_ctx();

        ls = isl_local_space_from_space(isl_set_get_space(adg->context));
        for (int i = 0; i < pdg->params.size(); ++i) {
                adg_param *param = new adg_param;
                isl_aff *aff;
                isl_val *v;

                param->name = isl_id_alloc(ctx, pdg->params[i]->name->s.c_str(),
                                                NULL);
                if (pdg->params[i]->value) {
                        isl_space *space = isl_space_params_alloc(ctx, 0);
                        isl_local_space *ls = isl_local_space_from_space(space);
                        param->val = isl_aff_zero_on_domain(ls);
                        param->val = isl_aff_add_constant_si(param->val,
                                                    pdg->params[i]->value->v);
                }

                aff = isl_aff_zero_on_domain(isl_local_space_copy(ls));
                aff = isl_aff_add_coefficient_si(aff, isl_dim_param, i, 1);
                v = isl_set_min_val(adg->context, aff);
                if (isl_val_is_int(v)) {
                        isl_space *space = isl_space_params_alloc(ctx, 0);
                        isl_local_space *ls = isl_local_space_from_space(space);
                        param->lb = isl_aff_zero_on_domain(ls);
                        param->lb = isl_aff_add_constant_val(param->lb, v);
                } else
                        isl_val_free(v);
                v = isl_set_max_val(adg->context, aff);
                if (isl_val_is_int(v)) {
                        isl_space *space = isl_space_params_alloc(ctx, 0);
                        isl_local_space *ls = isl_local_space_from_space(space);
                        param->ub = isl_aff_zero_on_domain(ls);
                        param->ub = isl_aff_add_constant_val(param->ub, v);
                } else
                        isl_val_free(v);
                isl_aff_free(aff);

                adg->params.push_back(param);
        }
        isl_local_space_free(ls);
}

/* Comparison function for sorting input ports such that
 * first, for input ports that are connected to the same edge,
 * an input port corresponding to an earlier argument position comes
 * before an input port corresponding to a later argument position, and,
 * second, ports that have dynamic control variables in their domains
 * come after the ports that set those control variables.
 *
 * The first is needed for pn_union channels as their detection allows for
 * the case where two (or more) tokens are consumed in the same iteration,
 * provided they don't cause reordering when consumed in the order of
 * the arguments.
 *
 * The second is needed to ensure that the values of the dynamic
 * control variables are available when they are needed.
 * We enforce the second property by sorting the edges based
 * on their depth with respect to dependences between input ports.
 * It would probably make more sense to perform a topological sort,
 * but it seemed easier to implement it this way.
 *
 * If two edges are equivalent with respect to the above two criteria,
 * then we arbitrarily sort them according to the edge sequence number.
 */
struct less_input_port :
                public std::binary_function<adg_port *, adg_port *, bool> {
        std::vector<adg_port *> ports;

        less_input_port(std::vector<adg_port *> &ports) : ports(ports) {}

        bool writes(adg_port *p, __isl_keep isl_id *id);
        int depth(adg_port *p);

        bool operator()(adg_port *x, adg_port *y) {
                int depth_x, depth_y;

                if (x->edge_nr == y->edge_nr)
                        return x->arg_pos < y->arg_pos;

                depth_x = depth(x);
                depth_y = depth(y);
                if (depth_x != depth_y)
                        return depth_x < depth_y;
                return x->edge_nr < y->edge_nr;
        }
};

/* Does "p" write to the variable "id"?
 */
bool less_input_port::writes(adg_port *p, __isl_keep isl_id *id)
{
        for (int i = 0; i < p->vars.size(); ++i) {
                adg_var *var = p->vars[i];
                isl_id *var_id;
                var_id = isl_pw_multi_aff_get_tuple_id(var->access,
                                                        isl_dim_out);
                isl_id_free(var_id);
                if (var_id == id)
                        return true;
        }

        return false;
}

/* Return 0 if this port does not involve any filters.
 * Otherwise, return 1 plus the maximal depth of any port
 * writing a filter used in the domain of the current port.
 * We obviously assume here that there are no cyclic dependences.
 */
int less_input_port::depth(adg_port *p)
{
        int max_depth = 0;

        for (int i = 0; i < p->domain->filters.size(); ++i) {
                adg_var *filter = p->domain->filters[i];
                isl_id *id;
                id = isl_pw_multi_aff_get_tuple_id(filter->access, isl_dim_out);
                for (int j = 0; j < ports.size(); ++j) {
                        int d;
                        if (writes(ports[j], id)) {
                                d = depth(ports[j]) + 1;
                                if (d > max_depth)
                                        max_depth = d;
                        }
                }
                isl_id_free(id);
        }

        return max_depth;
}

/* Sort the input ports of the given node.
 */
static void sort_input_ports(adg_node *node)
{
        std::sort(node->input_ports.begin(), node->input_ports.end(),
                less_input_port(node->input_ports));
}

/* Sort the input ports in all nodes of the graph.
 */
static void sort_input_ports(adg *graph)
{
        for (int i = 0; i < graph->nodes.size(); ++i)
                sort_input_ports(graph->nodes[i]);
}

/* Rename the dynamic control "id" from __last_*_valid to
 *
 *      dc<nr>_<node>_b
 *
 * and from __last_*_<i> to
 *
 *      dc<nr>_<node>_c<i>
 *
 * "prefix_map" maps previously translated prefixes __last_*
 * (within the same node) to their dc<nr>_<node> translations.
 * If we can't find the current prefix in this cache, we create
 * a new name and add it to the cache.
 */
static __isl_give isl_id *rename_dynamic_control(__isl_take isl_id *id,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        const char *name, *underscore;
        string old;
        std::ostringstream strm;
        isl_ctx *ctx;

        if (!is_control(id))
                return id;

        name = isl_id_get_name(id);
        underscore = strrchr(name, '_');
        assert(underscore);

        old = string(name, underscore - name);
        if (prefix_map.find(old) == prefix_map.end()) {
                strm << "dc" << prefix_map.size() << "_" << node_name;
                prefix_map[old] = strm.str();
        }

        strm.str("");
        strm << prefix_map[old] << "_";
        if (!strcmp(underscore + 1, "valid"))
                strm << "b";
        else
                strm << "c" << underscore + 1;

        ctx = isl_id_get_ctx(id);
        isl_id_free(id);

        return isl_id_alloc(ctx, strm.str().c_str(), NULL);
}

static void rename_dynamic_controls(adg_expr *expr,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        isl_id *id;
        int n_in;

        n_in = isl_pw_aff_dim(expr->expr, isl_dim_in);
        for (int i = 0; i < n_in; ++i) {
                const char *name;
                name = isl_pw_aff_get_dim_name(expr->expr, isl_dim_in, i);
                if (!is_control(name))
                        continue;
                id = isl_pw_aff_get_dim_id(expr->expr, isl_dim_in, i);
                id = rename_dynamic_control(id, node_name, prefix_map);
                expr->expr = isl_pw_aff_set_dim_id(expr->expr,
                                                        isl_dim_in, i, id);
        }

        if (!is_control(expr->name))
                return;
        expr->name = rename_dynamic_control(expr->name, node_name, prefix_map);
}

static void rename_dynamic_controls(adg_var *var,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        isl_id *id;
        int nparam;

        nparam = isl_pw_multi_aff_dim(var->access, isl_dim_param);
        for (int i = 0; i < nparam; ++i) {
                const char *name;
                name = isl_pw_multi_aff_get_dim_name(var->access,
                                                        isl_dim_param, i);
                if (!is_control(name))
                        continue;
                id = isl_pw_multi_aff_get_dim_id(var->access,
                                                        isl_dim_param, i);
                id = rename_dynamic_control(id, node_name, prefix_map);
                var->access = isl_pw_multi_aff_set_dim_id(var->access,
                                                        isl_dim_param, i, id);
        }

        if (!isl_pw_multi_aff_has_tuple_id(var->access, isl_dim_out))
                return;
        id = isl_pw_multi_aff_get_tuple_id(var->access, isl_dim_out);
        id = rename_dynamic_control(id, node_name, prefix_map);
        var->access = isl_pw_multi_aff_set_tuple_id(var->access,
                                                        isl_dim_out, id);
}

static void rename_dynamic_controls(adg_domain *domain,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        for (int i = 0; i < domain->controls.size(); ++i)
                rename_dynamic_controls(domain->controls[i], node_name,
                                        prefix_map);
        for (int i = 0; i < domain->filters.size(); ++i)
                rename_dynamic_controls(domain->filters[i], node_name,
                                        prefix_map);
}

static void rename_dynamic_controls(adg_function *fn,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        for (int i = 0; i < fn->ctrl.size(); ++i)
                rename_dynamic_controls(fn->ctrl[i], node_name, prefix_map);
}

static void rename_dynamic_controls(adg_port *port,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        for (int i = 0; i < port->vars.size(); ++i)
                rename_dynamic_controls(port->vars[i], node_name, prefix_map);
        rename_dynamic_controls(port->domain, node_name, prefix_map);
}

static void rename_dynamic_controls(adg_gate *gate,
        const char *node_name,
        std::map<std::string, std::string> &prefix_map)
{
        rename_dynamic_controls(gate->in, node_name, prefix_map);
        rename_dynamic_controls(gate->out, node_name, prefix_map);
        rename_dynamic_controls(gate->domain, node_name, prefix_map);
}

/* Rename all sets of dynamic controls in "node" from __last_*_valid to
 *
 *      dc<nr>_<node>_b
 *
 * and from __last_*_<i> to
 *
 *      dc<nr>_<node>_c<i>
 *
 * This ensures that each set of dynamic controls has a unique name.
 * In particular, if such a set of dynamic controls is transferred from
 * one node to another, then they will have different names in the two
 * nodes.
 */
static void rename_dynamic_controls(adg_node *node)
{
        std::map<std::string, std::string> prefix_map;
        const char *node_name = isl_id_get_name(node->name);

        rename_dynamic_controls(node->function, node_name, prefix_map);

        for (int i = 0; i < node->input_ports.size(); ++i)
                rename_dynamic_controls(node->input_ports[i], node_name,
                                        prefix_map);
        for (int i = 0; i < node->output_ports.size(); ++i)
                rename_dynamic_controls(node->output_ports[i], node_name,
                                        prefix_map);
        for (int i = 0; i < node->gates.size(); ++i)
                rename_dynamic_controls(node->gates[i], node_name, prefix_map);
}

static void rename_dynamic_controls(adg *graph)
{
        for (int i = 0; i < graph->nodes.size(); ++i)
                rename_dynamic_controls(graph->nodes[i]);
}

/* Convert the pn model "pdg" to an adg model.
 */
static adg *pdg2adg(PDG *pdg)
{
        isl_ctx *ctx;
        adg *graph;
        int g_nr = 0;

        ctx = pdg->get_isl_ctx();

        graph = new adg;

        graph->name = isl_id_alloc(ctx, pdg->name->s.c_str(), NULL);
        graph->context = pdg->context->get_isl_set();
        compute_iterator_map(graph, pdg);

        extract_params(graph, pdg);

        for (int i = 0; i < pdg->nodes.size(); ++i)
                add_node(ctx, graph, pdg->nodes[i]);
        for (int i = 0; i < pdg->dependences.size(); ++i) {
                pdg::dependence *dep = pdg->dependences[i];

                if (dep->type == pdg::dependence::uninitialized)
                        continue;
                if (dep->type == pdg::dependence::pn_part)
                        continue;
                if (dep->type == pdg::dependence::pn_hold)
                        continue;
                if (dep->type == pdg::dependence::pn_wire)
                        add_wire_gate(pdg, graph, dep, &g_nr);
                else
                        add_union_edge(pdg, graph, dep, i);
        }

        sort_input_ports(graph);
        rename_dynamic_controls(graph);

        return graph;
}

static void set_output_name(isl_ctx *ctx, struct options *options)
{
        int len;
        const char *suffix = options->xml ? "_adg.xml" : "_adg.yaml";

        if (!options->input || !strcmp(options->input, "-"))
                return;
        if (options->output)
                return;

        len = strlen(options->input);
        if (len > 5 && !strcmp(options->input + len - 5, ".yaml"))
                len -= 5;
        options->output = isl_alloc_array(ctx, char, len + strlen(suffix) + 1);
        assert(options->output);
        strncpy(options->output, options->input, len);
        strcpy(options->output + len, suffix);
}

/* Convert the input pn model to an adg model and print out the adg
 * model in either YAML format or XML format.
 */
int main(int argc, char *argv[])
{
        isl_ctx *ctx;
        struct options *options = options_new_with_defaults();
        PDG *pdg;
        adg *adg;
        FILE *in = stdin, *out = stdout;

        argc = options_parse(options, argc, argv, ISL_ARG_ALL);
        ctx = isl_ctx_alloc_with_options(&options_args, options);

        set_output_name(ctx, options);

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

        pdg = PDG::Load(in, ctx);

        adg = pdg2adg(pdg);
        if (options->xml)
                adg_print_xml(adg, out);
        else
                adg->print(out);
        delete adg;

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

        return 0;
}