update isl for change in lexicographic optimization

[ppn.git] / c2pdg.cc

#include <assert.h>
#include <stdio.h>
#include <string.h>

#include <isl/ctx.h>
#include <isl/id.h>
#include <isl/val.h>
#include <isl/space.h>
#include <isl/local_space.h>
#include <isl/aff.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl/ilp.h>
#include <isl/constraint.h>
#include <isl/schedule.h>
#include <isl/schedule_node.h>
#include <isl/union_set.h>
#include <isl/union_map.h>
#include <pet.h>

#include <isa/pdg.h>
#include "c2pdg_options.h"

const char dot_yaml[] = ".yaml";

static __isl_give isl_map *isl_map_equal_dims(__isl_take isl_space *dim,
        enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{
        isl_map *map = isl_map_universe(dim);
        return isl_map_equate(map, type1, pos1, type2, pos2);
}

static __isl_give isl_map *isl_map_opposite_dims(__isl_take isl_space *dim,
        enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{
        isl_map *map = isl_map_universe(dim);
        return isl_map_oppose(map, type1, pos1, type2, pos2);
}

static pdg::call_or_access *convert_expr(pdg::PDG *pdg,
        pdg::statement *stat, struct pet_expr *expr,
        std::map<isl_id *, pdg::array *> &id2array, __isl_keep isl_map *trans);

/* Convert the access pet_expr to a pdg::access and return it.
 * We assume that the pet_expr accesses data in a single space
 * (in particular, we do not support accesses to different fields
 * of a struct) and that it is either a write or a read (and not both).
 * The pdg::access is also added to the list of accesses in "stat".
 * The pointer to the pdg::array is taken from "id2array" based
 * on the tuple id on the access relation.
 *
 * The domain of the access relation is transformed using "trans".
 * If the access has any arguments then the domain of the access relation
 * is a wrapped mapping from the iteration space to the space of
 * argument values.  We only need to change the domain of this wrapped
 * mapping, so we extend the input transformation with an identity mapping
 * on the space of argument values.
 */
static pdg::access *extract_access(pdg::PDG *pdg, pdg::statement *stat,
        struct pet_expr *expr, std::map<isl_id *, pdg::array *> &id2array,
        __isl_keep isl_map *trans)
{
        pdg::access *access = new pdg::access;
        isl_id *id = NULL;
        isl_space *dim;
        isl_map *map;
        isl_union_map *umap;
        unsigned n_index;
        int n;

        n = pet_expr_get_n_arg(expr);
        for (int i = 0; i < n; ++i) {
                pdg::call_or_access *coa;
                pet_expr *arg;
                arg = pet_expr_get_arg(expr, i);
                coa = convert_expr(pdg, stat, arg, id2array, trans);
                pet_expr_free(arg);
                access->nested.push_back(coa);
        }

        if (pet_expr_access_is_write(expr)) {
                access->type = pdg::access::write;
                umap = pet_expr_access_get_dependent_may_write(expr);
        } else {
                access->type = pdg::access::read;
                umap = pet_expr_access_get_dependent_may_read(expr);
        }

        assert(isl_union_map_n_map(umap) == 1);

        map = isl_map_from_union_map(umap);
        trans = isl_map_copy(trans);

        dim = isl_space_domain(isl_map_get_space(map));
        if (!isl_space_is_wrapping(dim))
                isl_space_free(dim);
        else {
                isl_map *id;
                dim = isl_space_unwrap(dim);
                dim = isl_space_range(dim);
                dim = isl_space_map_from_set(dim);
                id = isl_map_identity(dim);
                trans = isl_map_product(trans, id);
        }

        map = isl_map_apply_domain(map, trans);
        if (isl_map_has_tuple_id(map, isl_dim_out))
                id = isl_map_get_tuple_id(map, isl_dim_out);
        n_index = isl_map_dim(map, isl_dim_out);
        for (int i = n_index - 1; i >= 0; --i)
                if (!isl_map_involves_dims(map, isl_dim_out, i, 1))
                        map = isl_map_project_out(map, isl_dim_out, i, 1);
                else
                        break;
        if (id)
                map = isl_map_set_tuple_id(map, isl_dim_out, id);
        access->map = new pdg::IslMap(map);

        if (!pet_expr_is_affine(expr)) {
                id = pet_expr_access_get_id(expr);
                access->array = id2array[id];
                isl_id_free(id);
        }

        stat->accesses.push_back(access);

        return access;
}

/* Convert the integer pet_expr to a pdg::access and return this pdg::access.
 * The pdg::access is also added to the list of accesses in "stat".
 *
 * The domain of the access relation derived from the integer value
 * is equal to the range space of "trans".
 */
static pdg::access *extract_access_from_int(pdg::PDG *pdg, pdg::statement *stat,
        struct pet_expr *expr, __isl_keep isl_map *trans)
{
        pdg::access *access = new pdg::access;
        isl_val *v;
        isl_aff *aff;
        isl_pw_aff *pa;
        isl_space *space;

        access->type = pdg::access::read;

        v = pet_expr_int_get_val(expr);
        space = isl_space_range(isl_map_get_space(trans));
        aff = isl_aff_val_on_domain(isl_local_space_from_space(space), v);
        pa = isl_pw_aff_from_aff(aff);

        access->map = new pdg::IslMap(isl_map_from_pw_aff(pa));

        stat->accesses.push_back(access);

        return access;
}

static pdg::call_or_access *convert_expr(pdg::PDG *pdg,
        pdg::statement *stat, struct pet_expr *expr,
        std::map<isl_id *, pdg::array *> &id2array, __isl_keep isl_map *trans)
{
        pdg::call_or_access *coa = new pdg::call_or_access;
        enum pet_expr_type type;

        type = pet_expr_get_type(expr);
        if (type == pet_expr_access) {
                coa->type = pdg::call_or_access::t_access;
                coa->access = extract_access(pdg, stat, expr, id2array, trans);
        } else if (type == pet_expr_int) {
                coa->type = pdg::call_or_access::t_access;
                coa->access = extract_access_from_int(pdg, stat, expr, trans);
        } else {
                int n;

                coa->type = pdg::call_or_access::t_call;
                coa->call = new pdg::function_call;

                if (type == pet_expr_call)
                        coa->call->name = new str(pet_expr_call_get_name(expr));
                else if (type == pet_expr_double) {
                        char *s = pet_expr_double_get_str(expr);
                        coa->call->name = new str(s);
                        free(s);
                } else if (type == pet_expr_op &&
                            pet_expr_op_get_type(expr) == pet_op_cond)
                        coa->call->name = new str("#test");
                else
                        coa->call->name =
                            new str(pet_op_str(pet_expr_op_get_type(expr)));

                n = pet_expr_get_n_arg(expr);
                for (int i = 0; i < n; ++i) {
                        pdg::call_or_access *child;
                        pet_expr *arg;
                        arg = pet_expr_get_arg(expr, i);
                        child = convert_expr(pdg, stat, arg, id2array, trans);
                        pet_expr_free(arg);
                        coa->call->arguments.push_back(child);
                }
        }

        return coa;
}

static pdg::function_call *extract_top_function(pdg::PDG *pdg,
        pdg::statement *stat, struct pet_expr *expr,
        std::map<isl_id *, pdg::array *> &id2array, __isl_keep isl_map *trans)
{
        pdg::function_call *call;
        pdg::call_or_access *coa = convert_expr(pdg, stat, expr, id2array, trans);

        if (coa->type == pdg::call_or_access::t_access) {
                call = new pdg::function_call;
                call->arguments.push_back(coa);
                call->name = new str(string(""));
        } else {
                call = coa->call;
                delete coa;
        }

        return call;
}

/* Extract a function call for the top-level function called from "tree".
 * We currently assume the tree is an expression statement and
 * extract the function call from the expression.
 */
static pdg::function_call *extract_top_function(pdg::PDG *pdg,
        pdg::statement *stat, __isl_keep pet_tree *tree,
        std::map<isl_id *, pdg::array *> &id2array, __isl_keep isl_map *trans)
{
        pdg::function_call *call;
        pet_expr *expr;

        assert(pet_tree_get_type(tree) == pet_tree_expr);
        expr = pet_tree_expr_get_expr(tree);
        call = extract_top_function(pdg, stat, expr, id2array, trans);
        pet_expr_free(expr);

        return call;
}

/* For each of the filters ("arguments") of "stmt", check if the user
 * has specified any bounds on the values of the corresponding array
 * elements.  If so, apply those bounds to the filter in the iteration
 * domain "dom".
 * Return the (possibly) restricted iteration domain.
 */
static __isl_give isl_set *apply_filter_bounds(__isl_take isl_set *dom,
        struct pet_stmt *stmt, std::map<isl_id *, pdg::array *> &id2array)
{
        isl_map *map;

        if (!isl_set_is_wrapping(dom))
                return dom;

        map = isl_set_unwrap(dom);

        for (int i = 0; i < stmt->n_arg; ++i) {
                isl_id *id;
                pdg::array *array;
                pet_expr *expr = stmt->args[i];
                isl_set *bound;

                if (pet_expr_get_type(expr) != pet_expr_access)
                        continue;

                id = pet_expr_access_get_id(expr);
                array = id2array[id];
                isl_id_free(id);

                if (!array->value_bounds)
                        continue;
                bound = array->value_bounds->get_isl_set();
                bound = isl_set_insert_dims(bound, isl_dim_set, 0, i);
                bound = isl_set_add_dims(bound, isl_dim_set,
                                                stmt->n_arg - (i + 1));
                map = isl_map_intersect_range(map, bound);
        }

        return isl_map_wrap(map);
}

/* Given a filter access function encoded in "coa" corresponding to
 * filter "pos" in "domain", extend the function to a filter access
 * relation by exploiting the implications in "scop".
 * In particular, if a statement depends on all previous iterations
 * of some (other) statement (not) having executed, then it is marked
 * by pet as only depending on the latest iteration of that statement.
 * The implicit dependence on all previous iterations is encoded
 * in the implications in "scop".
 *
 * If the given filter has a fixed filter value that matches the satisfied
 * field of one of the implications and if that implication also references
 * the same virtual array, then the corresponding extension is applied
 * to the original filter access function to extend it to the complete
 * filter access relation.
 * Otherwise, we leave the filter access function untouched.
 */
static void apply_implications(pdg::call_or_access *coa, struct pet_scop *scop,
        __isl_keep isl_set *domain, int pos)
{
        isl_map *map;
        isl_map *ext_domain;
        isl_val *v;
        isl_id *map_id;
        int is_int, satisfied;

        if (scop->n_implication == 0)
                return;

        ext_domain = isl_set_unwrap(isl_set_copy(domain));
        v = isl_map_plain_get_val_if_fixed(ext_domain, isl_dim_out, pos);
        is_int = isl_val_is_int(v);
        if (is_int)
                satisfied = isl_val_get_num_si(v);
        isl_val_free(v);
        isl_map_free(ext_domain);
        if (!is_int)
                return;

        assert(coa->type == pdg::call_or_access::t_access);
        map = coa->access->map->map;
        map_id = isl_map_get_tuple_id(map, isl_dim_out);

        for (int i = 0; i < scop->n_implication; ++i) {
                struct pet_implication *pi;
                isl_id *pi_id;

                pi = scop->implications[i];

                if (pi->satisfied != satisfied)
                        continue;
                pi_id = isl_map_get_tuple_id(pi->extension, isl_dim_in);
                isl_id_free(pi_id);
                if (pi_id != map_id)
                        continue;

                map = isl_map_apply_range(map, isl_map_copy(pi->extension));
                break;
        }

        coa->access->map->map = map;

        isl_id_free(map_id);
}

/* Does "expr" perform a (possibly compound) assignment?
 */
static int is_assignment(__isl_keep pet_expr *expr)
{
        pet_expr *arg;
        int is_access;

        if (pet_expr_get_type(expr) != pet_expr_op)
                return 0;
        if (pet_expr_op_get_type(expr) > pet_op_assign)
                return 0;
        arg = pet_expr_get_arg(expr, 0);
        is_access = pet_expr_get_type(arg) == pet_expr_access;
        pet_expr_free(arg);

        return is_access;
}

/* Does "expr" perform an increment or decrement operation?
 */
static int is_inc_dec(__isl_keep pet_expr *expr)
{
        pet_expr *arg;
        int is_access;

        if (pet_expr_get_type(expr) != pet_expr_op)
                return 0;
        if (!pet_op_is_inc_dec(pet_expr_op_get_type(expr)))
                return 0;
        arg = pet_expr_get_arg(expr, 0);
        is_access = pet_expr_get_type(arg) == pet_expr_access;
        pet_expr_free(arg);

        return is_access;
}

/* Is "tree" an expression statement that satisfies "fn"?
 */
static int is_expr_tree(__isl_keep pet_tree *tree,
        int (*fn)(__isl_keep pet_expr *expr))
{
        pet_expr *expr;
        int res;

        if (pet_tree_get_type(tree) != pet_tree_expr)
                return 0;
        expr = pet_tree_expr_get_expr(tree);
        res = fn(expr);
        pet_expr_free(expr);

        return res;
}

/* Does "tree" perform a (possibly compound) assignment?
 */
static int is_assignment(__isl_keep pet_tree *tree)
{
        return is_expr_tree(tree, &is_assignment);
}

/* Does "tree" perform an increment or decrement operation?
 */
static int is_inc_dec(__isl_keep pet_tree *tree)
{
        return is_expr_tree(tree, &is_inc_dec);
}

/* Find the position of the filter node among the children of "node"
 * that contains elements in "space".
 * It is assumed that there is exactly one such node.
 */
static int get_filter_pos(__isl_keep isl_schedule_node *node,
        __isl_keep isl_space *space)
{
        int i, n;

        n = isl_schedule_node_n_children(node);
        for (i = 0; i < n; ++i) {
                isl_schedule_node *child;
                isl_union_set *filter;
                isl_set *set;
                int empty;

                child = isl_schedule_node_get_child(node, i);
                filter = isl_schedule_node_filter_get_filter(child);
                set = isl_union_set_extract_set(filter, isl_space_copy(space));
                empty = isl_set_is_empty(set);
                isl_set_free(set);
                isl_union_set_free(filter);
                isl_schedule_node_free(child);

                assert(empty >= 0);
                if (!empty)
                        return i;
        }
        assert(0);
}

/* Create and return a pdg::node correspondingto stmt.
 * Since isa uses the "prefix" field in a pdg::node to represent the
 * original schedule, we try to extract such a prefix from the schedule.
 * If one of the original for loops had a decrement, then the corresponding
 * part of the schedule will be of the form [i] -> [-i].  Since such
 * an inverse cannot be represented by "prefix", we invert the corresponding
 * dimension of the iteration domain instead, taking care to also
 * change the domains of all access relations accordingly.
 *
 * If 'stmt" has any arguments, then stmt->domain is a wrapped map
 * and the transformation on the iteration domain only applies
 * to the domain of that map.  We therefore need to combine that
 * transformation with an identity mapping on the range before
 * applying it to the domain.
 * Any arguments found are also converted into filters on the node
 * domain.  The original filter access functions are extended to
 * filter access relations using the implications in "scop".
 */
static pdg::node *extract_node(pdg::PDG *pdg, struct pet_scop *scop,
        struct pet_stmt *stmt, std::map<isl_id *, pdg::array *> &id2array)
{
        pdg::node *node = new pdg::node;
        pdg::statement *stat;
        int nr;
        isl_space *space, *space_dom;
        isl_set *dom;
        isl_map *trans, *trans_dom;
        isl_schedule_node *snode;
        isl_union_set *universe;
        enum isl_schedule_node_type type;
        int i;

        space = isl_set_get_space(stmt->domain);
        if (isl_space_is_wrapping(space))
                space = isl_space_domain(isl_space_unwrap(space));
        space_dom = isl_space_copy(space);
        trans = isl_map_universe(isl_space_map_from_set(space));

        snode = isl_schedule_get_root(scop->schedule);
        space = isl_space_copy(space_dom);
        universe = isl_union_set_from_set(isl_set_universe(space));
        i = 0;
        while (snode) {
                type = isl_schedule_node_get_type(snode);
                assert(type != isl_schedule_node_error);
                if (type == isl_schedule_node_leaf)
                        break;
                if (type == isl_schedule_node_band) {
                        isl_union_map *umap;
                        isl_map *map, *test;
                        assert(isl_schedule_node_band_n_member(snode) == 1);
                        umap =
                        isl_schedule_node_band_get_partial_schedule_union_map(
                                snode);
                        umap = isl_union_map_intersect_domain(umap,
                                        isl_union_set_copy(universe));
                        map = isl_map_from_union_map(umap);
                        space = isl_map_get_space(map);
                        test = isl_map_equal_dims(space, isl_dim_in, i,
                                                        isl_dim_out, 0);
                        if (isl_map_is_subset(map, test)) {
                                trans = isl_map_equate(trans, isl_dim_in, i,
                                                        isl_dim_out, i);
                        } else {
                                isl_map_free(test);
                                space = isl_map_get_space(map);
                                test = isl_map_opposite_dims(space,
                                                isl_dim_in, i, isl_dim_out, 0);
                                assert(isl_map_is_subset(map, test));
                                trans = isl_map_oppose(trans, isl_dim_in, i,
                                                        isl_dim_out, i);
                        }
                        isl_map_free(test);
                        i++;
                        node->prefix.push_back(-1);
                        isl_map_free(map);
                }
                if (type == isl_schedule_node_sequence ||
                    type == isl_schedule_node_set) {
                        int pos;

                        pos = get_filter_pos(snode, space_dom);
                        node->prefix.push_back(pos);
                        snode = isl_schedule_node_child(snode, pos);
                } else
                        snode = isl_schedule_node_child(snode, 0);
        };
        assert(snode);
        isl_schedule_node_free(snode);
        isl_union_set_free(universe);

        dom = isl_set_copy(stmt->domain);
        trans_dom = isl_map_copy(trans);
        if (isl_set_is_wrapping(dom)) {
                isl_space *space = isl_set_get_space(dom);
                isl_map *id;
                space = isl_space_range(isl_space_unwrap(space));
                id = isl_map_identity(isl_space_map_from_set(space));
                trans_dom = isl_map_product(trans_dom, id);
        }
        dom = isl_set_apply(dom, trans_dom);
        dom = apply_filter_bounds(dom, stmt, id2array);
        node->source = new pdg::IslSet(dom);
        node->name = new str(isl_space_get_tuple_name(space_dom, isl_dim_set));
        isl_space_free(space_dom);

        stat = new pdg::statement;
        node->statement = stat;

        stat->line = pet_loc_get_line(stmt->loc);

        for (int i = 0; i < stmt->n_arg; ++i) {
                pdg::call_or_access *coa;
                coa = convert_expr(pdg, stat, stmt->args[i], id2array, trans);
                apply_implications(coa, scop, node->source->set, i);
                node->filters.push_back(coa);
        }

        if (is_assignment(stmt->body)) {
                pdg::access *access;
                pet_expr *expr, *arg;
                expr = pet_tree_expr_get_expr(stmt->body);
                if (pet_expr_op_get_type(expr) != pet_op_assign) {
                        arg = pet_expr_get_arg(expr, 0);
                        access = extract_access(pdg, stat,
                                                arg, id2array, trans);
                        pet_expr_free(arg);
                        access->type = pdg::access::read;
                }
                arg = pet_expr_get_arg(expr, 1);
                stat->top_function = extract_top_function(pdg, stat,
                                                arg, id2array, trans);
                pet_expr_free(arg);
                arg = pet_expr_get_arg(expr, 0);
                access = extract_access(pdg, stat, arg, id2array, trans);
                pet_expr_free(arg);
                stat->top_outputs.push_back(access);
                pet_expr_free(expr);
        } else if (is_inc_dec(stmt->body)) {
                pdg::access *access;
                pet_expr *expr, *arg;
                expr = pet_tree_expr_get_expr(stmt->body);
                arg = pet_expr_get_arg(expr, 0);
                access = extract_access(pdg, stat, arg, id2array, trans);
                access->type = pdg::access::read;
                stat->top_function = new pdg::function_call;
                stat->top_function->name =
                        new str(pet_op_str(pet_expr_op_get_type(expr)));
                access = extract_access(pdg, stat, arg, id2array, trans);
                stat->top_outputs.push_back(access);
                pet_expr_free(arg);
                pet_expr_free(expr);
        } else
                stat->top_function = extract_top_function(pdg, stat,
                                        stmt->body, id2array, trans);

        nr = 0;
        for (int i = 0; i < stat->accesses.size(); ++i)
                if (stat->accesses[i]->type == pdg::access::read)
                        stat->accesses[i]->nr = nr++;
        for (int i = 0; i < stat->accesses.size(); ++i)
                if (stat->accesses[i]->type != pdg::access::read)
                        stat->accesses[i]->nr = nr++;

        isl_map_free(trans);

        return node;
}

/* Create and return a pdg::array corresponding to pa and add it
 * to id2array.
 */
static pdg::array *extract_array(pdg::PDG *pdg, struct pet_array *pa,
        std::map<isl_id *, pdg::array *> &id2array)
{
        isl_id *id = isl_set_get_tuple_id(pa->extent);
        pdg::array *array = new pdg::array;
        int dim = isl_set_dim(pa->extent, isl_dim_set);

        array->name = new str(isl_id_get_name(id));
        array->element_type = new str(pa->element_type);
        for (int j = 0; j < dim; ++j) {
                isl_space *dim;
                isl_aff *obj;
                isl_val *v;

                dim = isl_set_get_space(pa->extent);
                obj = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
                obj = isl_aff_add_coefficient_si(obj, isl_dim_in, j, 1);
                v = isl_set_max_val(pa->extent, obj);
                isl_aff_free(obj);
                if (isl_val_is_int(v))
                        array->dims.push_back(isl_val_get_num_si(v) + 1);
                else
                        array->dims.push_back(-1);
                isl_val_free(v);
        }
        if (pa->value_bounds)
                array->value_bounds =
                        new pdg::IslSet(isl_set_copy(pa->value_bounds));
        array->uniquely_defined = pa->uniquely_defined;

        id2array[id] = array;

        isl_id_free(id);

        return array;
}

/* Assign a default value to parameter "p", which corresponds
 * to the parameter at position "i" in scop->context.
 *
 * If the parameter appears in scop->context_value and if
 * it has a fixed value, then use that value.
 * Otherwise find the minimual value of "p" in scop->context.
 * It there is no minimal value, then we currently leave p->value unset.
 */
static void set_default_parameter_value(pdg::parameter *p,
        __isl_keep isl_id *id, struct pet_scop *scop, int i)
{
        isl_space *space;
        isl_aff *obj;
        isl_val *v;
        int pos;

        pos = isl_set_find_dim_by_id(scop->context_value, isl_dim_param, id);
        if (pos >= 0) {
                v = isl_set_plain_get_val_if_fixed(scop->context_value,
                                                    isl_dim_param, pos);
                if (isl_val_is_int(v)) {
                        p->value = new integer(isl_val_get_num_si(v));
                        isl_val_free(v);
                        return;
                }
                isl_val_free(v);
        }

        space = isl_set_get_space(scop->context);
        obj = isl_aff_zero_on_domain(isl_local_space_from_space(space));
        obj = isl_aff_add_coefficient_si(obj, isl_dim_param, i, 1);
        v = isl_set_min_val(scop->context, obj);
        isl_aff_free(obj);
        if (isl_val_is_int(v))
                p->value = new integer(isl_val_get_num_si(v));

        isl_val_free(v);
}

extern "C" {
        static isl_bool kill_array(__isl_keep isl_schedule_node *node,
                void *user);
}

/* Internal data structure for kill_array.
 * "id2kill_stmt" maps the tuple id of the instance set of a kill statement
 * to the corresponding pet_stmt.
 * "id2array" maps the array identifier to the corresponding constructed
 * pdg::array.
 */
struct kill_array_data {
        std::map<isl_id *, struct pet_stmt *> &id2kill_stmt;
        std::map<isl_id *, pdg::array *> &id2array;
};

/* Mark the array "accessed" by "expr" as killed.
 * The expression is assumed to represent a kill of an entire array.
 */
static int kill_array(__isl_keep pet_expr *expr, void *user)
{
        kill_array_data *data = (kill_array_data *) user;
        isl_id *id;
        pdg::array *array;

        id = pet_expr_access_get_id(expr);
        array = data->id2array[id];
        isl_id_free(id);

        if (!array)
                return -1;
        array->killed = 1;

        return 0;
}

/* Mark all arrays "accessed" by the statement with instance set "set"
 * as killed.
 */
static isl_stat kill_stmt_arrays(__isl_take isl_set *set, void *user)
{
        kill_array_data *data = (kill_array_data *) user;
        isl_id *id;
        struct pet_stmt *stmt;

        id = isl_set_get_tuple_id(set);
        stmt = data->id2kill_stmt[id];
        isl_id_free(id);
        isl_set_free(set);

        if (!stmt)
                return isl_stat_error;

        if (pet_tree_foreach_access_expr(stmt->body, &kill_array, data) < 0)
                return isl_stat_error;

        return isl_stat_ok;
}

/* Given a filter node "node", mark all arrays accessed by the statements
 * corresponding to the instance set in the filter as killed.
 * "id2kill_stmt" maps the tuple id of the instance set of a kill statement
 * to the corresponding pet_stmt.
 * "id2array" maps the array identifier to the corresponding constructed
 * pdg::array.
 */
static isl_stat kill_arrays(__isl_keep isl_schedule_node *node,
        std::map<isl_id *, struct pet_stmt *> &id2kill_stmt,
        std::map<isl_id *, pdg::array *> &id2array)
{
        kill_array_data data = { id2kill_stmt, id2array };
        isl_union_set *filter;
        isl_stat ok;

        filter = isl_schedule_node_filter_get_filter(node);
        ok = isl_union_set_foreach_set(filter, &kill_stmt_arrays, &data);
        isl_union_set_free(filter);

        return ok;
}

/* Look for pieces of the schedule "schedule" that are executed after
 * all other pieces and that consist of only instances in "kills".
 * If any such pieces can be found, then mark all arrays accessed
 * by the corresponding statements as killed.
 * "id2kill_stmt" maps the tuple id of the instance set of a kill statement
 * to the corresponding pet_stmt.
 * "id2array" maps the array identifier to the corresponding constructed
 * pdg::array.
 */
static void kill_final(__isl_keep isl_schedule *schedule,
        __isl_keep isl_union_set *kills,
        std::map<isl_id *, struct pet_stmt *> &id2kill_stmt,
        std::map<isl_id *, pdg::array *> &id2array)
{
        int n;
        isl_schedule_node *node;

        node = isl_schedule_get_root(schedule);
        node = isl_schedule_node_child(node, 0);
        if (isl_schedule_node_get_type(node) == isl_schedule_node_context)
                node = isl_schedule_node_child(node, 0);
        if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence) {
                isl_schedule_node_free(node);
                return;
        }

        n = isl_schedule_node_n_children(node);
        node = isl_schedule_node_child(node, n - 1);
        while (node) {
                isl_union_set *filter;
                int is_all_kill;

                filter = isl_schedule_node_filter_get_filter(node);
                is_all_kill = isl_union_set_is_subset(filter, kills);
                isl_union_set_free(filter);
                if (!is_all_kill)
                        break;
                kill_arrays(node, id2kill_stmt, id2array);
                if (!isl_schedule_node_has_previous_sibling(node))
                        break;
                node = isl_schedule_node_previous_sibling(node);
        }

        isl_schedule_node_free(node);
}

int main(int argc, char **argv)
{
        isl_ctx *ctx;
        isl_union_set *kills;
        struct options *options = options_new_with_defaults();
        struct pet_scop *scop;
        pdg::PDG *pdg;
        int len;
        char *output_name;
        FILE *output;
        int nparam;
        char *slash;
        std::map<isl_id *, pdg::array *> id2array;
        std::map<isl_id *, struct pet_stmt *> id2kill_stmt;

        ctx = isl_ctx_alloc_with_options(&options_args, options);
        if (!ctx) {
                fprintf(stderr, "Unable to allocate ctx\n");
                return -1;
        }

        pdg = new pdg::PDG(ctx);
        pdg->add_history_line("c2pdg", argc, argv);
        pdg->placement = new str(string("original"));

        pet_options_set_autodetect(ctx, 1);
        argc = options_parse(options, argc, argv, ISL_ARG_ALL);

        len = strlen(options->input);
        if (len > 2 && !strcmp(options->input + len - 2, ".c"))
                len -= 2;
        output_name = isl_alloc_array(ctx, char, len + sizeof(dot_yaml));
        assert(output_name);
        memcpy(output_name, options->input, len);
        memcpy(output_name + len, dot_yaml, sizeof(dot_yaml));
        output = fopen(output_name, "w");
        assert(output);

        scop = pet_scop_extract_from_C_source(ctx, options->input,
                                                options->function);
        scop = pet_scop_align_params(scop);
        assert(scop);

        output_name[len] = '\0';
        slash = strrchr(output_name, '/');
        if (!slash)
                slash = output_name;
        pdg->name = new str(output_name);

        nparam = isl_set_dim(scop->context, isl_dim_param);
        for (int i = 0; i < nparam; ++i) {
                isl_id *id = isl_set_get_dim_id(scop->context, isl_dim_param, i);
                pdg::parameter *p = new pdg::parameter;

                p->name = new str(isl_id_get_name(id));
                set_default_parameter_value(p, id, scop, i);

                pdg->params.push_back(p);
                isl_id_free(id);
        }

        pdg->context = new pdg::IslSet(isl_set_copy(scop->context));

        for (int i = 0; i < scop->n_array; ++i) {
                pdg::array *array;
                array = extract_array(pdg, scop->arrays[i], id2array);
                pdg->arrays.push_back(array);
        }

        kills = isl_union_set_empty(isl_set_get_space(scop->context));
        for (int i = 0, nodenr = 0; i < scop->n_stmt; ++i) {
                pdg::node *node;
                if (isl_set_is_empty(scop->stmts[i]->domain))
                        continue;
                if (pet_stmt_is_kill(scop->stmts[i])) {
                        isl_set *domain = isl_set_copy(scop->stmts[i]->domain);
                        isl_id *id = isl_set_get_tuple_id(domain);
                        id2kill_stmt[id] = scop->stmts[i];
                        isl_id_free(id);
                        kills = isl_union_set_add_set(kills, domain);
                        continue;
                }
                node = extract_node(pdg, scop, scop->stmts[i], id2array);
                node->nr = nodenr++;
                pdg->nodes.push_back(node);
        }
        kill_final(scop->schedule, kills, id2kill_stmt, id2array);
        isl_union_set_free(kills);

        pdg->Dump(output);
        pdg->free();
        delete pdg;

        pet_scop_free(scop);

        fclose(output);
        free(output_name);

        isl_ctx_free(ctx);
        return 0;
}