schedule.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <assert.h>
  12 #include <ctype.h>
  13 #include <string.h>
  14
  15 #include <isl/set.h>
  16 #include <isl/map.h>
  17 #include <isl/constraint.h>
  18
  19 #include "schedule.h"
  20
  21 /* Construct a map from a len-dimensional domain to
  22  * a (len-n)-dimensional domain that projects out the n coordinates
  23  * starting at first.
  24  * "dim" prescribes the parameters.
  25  */
  26 __isl_give isl_map *project_out(__isl_take isl_space *dim,
  27     int len, int first, int n)
  28 {
  29     int i, j;
  30     isl_constraint *c;
  31     isl_basic_map *bmap;
  32     isl_int v;
  33     isl_local_space *ls;
  34
  35     isl_int_init(v);
  36
  37     dim = isl_space_add_dims(dim, isl_dim_in, len);
  38     dim = isl_space_add_dims(dim, isl_dim_out, len - n);
  39     bmap = isl_basic_map_universe(isl_space_copy(dim));
  40     ls = isl_local_space_from_space(dim);
  41
  42     for (i = 0, j = 0; i < len; ++i) {
  43         if (i >= first && i < first + n)
  44             continue;
  45         c = isl_equality_alloc(isl_local_space_copy(ls));
  46         isl_int_set_si(v, -1);
  47         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  48         isl_int_set_si(v, 1);
  49         isl_constraint_set_coefficient(c, isl_dim_out, j, v);
  50         bmap = isl_basic_map_add_constraint(bmap, c);
  51         ++j;
  52     }
  53     isl_local_space_free(ls);
  54
  55     isl_int_clear(v);
  56
  57     return isl_map_from_basic_map(bmap);
  58 }
  59
  60 /* Construct a projection that maps a src_len dimensional domain
  61  * to its first dst_len coordinates.
  62  * "dim" prescribes the parameters.
  63  */
  64 __isl_give isl_map *projection(__isl_take isl_space *dim,
  65     int src_len, int dst_len)
  66 {
  67     return project_out(dim, src_len, dst_len, src_len - dst_len);
  68 }
  69
  70 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
  71  */
  72 __isl_give isl_set *extend(__isl_take isl_set *set, int dst_len)
  73 {
  74     int n_set;
  75     isl_space *dim;
  76     isl_map *map;
  77
  78     dim = isl_set_get_space(set);
  79     n_set = isl_space_dim(dim, isl_dim_set);
  80     dim = isl_space_drop_dims(dim, isl_dim_set, 0, n_set);
  81     map = projection(dim, dst_len, n_set);
  82     map = isl_map_reverse(map);
  83
  84     return isl_set_apply(set, map);
  85 }
  86
  87 /* Set max_out to the maximal number of output dimensions over
  88  * all maps.
  89  */
  90 static int update_max_out(__isl_take isl_map *map, void *user)
  91 {
  92         int *max_out = user;
  93         int n_out = isl_map_dim(map, isl_dim_out);
  94
  95         if (n_out > *max_out)
  96                 *max_out = n_out;
  97
  98         isl_map_free(map);
  99         return 0;
 100 }
 101
 102 struct align_range_data {
 103         int max_out;
 104         isl_union_map *res;
 105 };
 106
 107 /* Extend the dimension of the range of the given map to data->max_out and
 108  * then add the result to data->res.
 109  */
 110 static int map_align_range(__isl_take isl_map *map, void *user)
 111 {
 112         struct align_range_data *data = user;
 113         int i;
 114         isl_space *dim;
 115         isl_map *proj;
 116         int n_out = isl_map_dim(map, isl_dim_out);
 117
 118         dim = isl_union_map_get_space(data->res);
 119         proj = isl_map_reverse(projection(dim, data->max_out, n_out));
 120         for (i = n_out; i < data->max_out; ++i)
 121                 proj = isl_map_fix_si(proj, isl_dim_out, i, 0);
 122
 123         map = isl_map_apply_range(map, proj);
 124
 125         data->res = isl_union_map_add_map(data->res, map);
 126
 127         return 0;
 128 }
 129
 130 /* Extend the ranges of the maps in the union map such they all have
 131  * the same dimension.
 132  */
 133 __isl_give isl_union_map *align_range(__isl_take isl_union_map *umap)
 134 {
 135         struct align_range_data data;
 136
 137         data.max_out = 0;
 138         isl_union_map_foreach_map(umap, &update_max_out, &data.max_out);
 139
 140         data.res = isl_union_map_empty(isl_union_map_get_space(umap));
 141         isl_union_map_foreach_map(umap, &map_align_range, &data);
 142
 143         isl_union_map_free(umap);
 144         return data.res;
 145 }