schedule.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT 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_basic_map *bmap;
  31
  32     dim = isl_space_add_dims(dim, isl_dim_in, len);
  33     dim = isl_space_add_dims(dim, isl_dim_out, len - n);
  34     bmap = isl_basic_map_universe(dim);
  35
  36     for (i = 0, j = 0; i < len; ++i) {
  37         if (i >= first && i < first + n)
  38             continue;
  39         bmap = isl_basic_map_equate(bmap, isl_dim_in, i, isl_dim_out, j);
  40         ++j;
  41     }
  42
  43     return isl_map_from_basic_map(bmap);
  44 }
  45
  46 /* Construct a projection that maps a src_len dimensional domain
  47  * to its first dst_len coordinates.
  48  * "dim" prescribes the parameters.
  49  */
  50 __isl_give isl_map *projection(__isl_take isl_space *dim,
  51     int src_len, int dst_len)
  52 {
  53     return project_out(dim, src_len, dst_len, src_len - dst_len);
  54 }
  55
  56 /* Add parameters with identifiers "ids" to "set".
  57  */
  58 static __isl_give isl_set *add_params(__isl_take isl_set *set,
  59         __isl_keep isl_id_list *ids)
  60 {
  61         int i, n;
  62         unsigned nparam;
  63
  64         n = isl_id_list_n_id(ids);
  65
  66         nparam = isl_set_dim(set, isl_dim_param);
  67         set = isl_set_add_dims(set, isl_dim_param, n);
  68
  69         for (i = 0; i < n; ++i) {
  70                 isl_id *id;
  71
  72                 id = isl_id_list_get_id(ids, i);
  73                 set = isl_set_set_dim_id(set, isl_dim_param, nparam + i, id);
  74         }
  75
  76         return set;
  77 }
  78
  79 /* Equate the dimensions of "set" starting at "first" to
  80  * freshly created parameters with identifiers "ids".
  81  * The number of equated dimensions is equal to the number of elements in "ids".
  82  */
  83 static __isl_give isl_set *parametrize(__isl_take isl_set *set,
  84         int first, __isl_keep isl_id_list *ids)
  85 {
  86         int i, n;
  87         unsigned nparam;
  88
  89         nparam = isl_set_dim(set, isl_dim_param);
  90
  91         set = add_params(set, ids);
  92
  93         n = isl_id_list_n_id(ids);
  94         for (i = 0; i < n; ++i)
  95                 set = isl_set_equate(set, isl_dim_param, nparam + i,
  96                                         isl_dim_set, first + i);
  97
  98         return set;
  99 }
 100
 101 /* Given a parameter space "space", create a set of dimension "len"
 102  * of which the dimensions starting at "first" are equated to
 103  * freshly created parameters with identifiers "ids".
 104  */
 105 __isl_give isl_set *parametrization(__isl_take isl_space *space,
 106         int len, int first, __isl_keep isl_id_list *ids)
 107 {
 108         isl_set *set;
 109
 110         space = isl_space_set_from_params(space);
 111         space = isl_space_add_dims(space, isl_dim_set, len);
 112         set = isl_set_universe(space);
 113
 114         return parametrize(set, first, ids);
 115 }
 116
 117 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
 118  */
 119 __isl_give isl_set *extend(__isl_take isl_set *set, int dst_len)
 120 {
 121     int n_set;
 122     isl_space *dim;
 123     isl_map *map;
 124
 125     dim = isl_set_get_space(set);
 126     n_set = isl_space_dim(dim, isl_dim_set);
 127     dim = isl_space_drop_dims(dim, isl_dim_set, 0, n_set);
 128     map = projection(dim, dst_len, n_set);
 129     map = isl_map_reverse(map);
 130
 131     return isl_set_apply(set, map);
 132 }
 133
 134 /* Set max_out to the maximal number of output dimensions over
 135  * all maps.
 136  */
 137 static int update_max_out(__isl_take isl_map *map, void *user)
 138 {
 139         int *max_out = user;
 140         int n_out = isl_map_dim(map, isl_dim_out);
 141
 142         if (n_out > *max_out)
 143                 *max_out = n_out;
 144
 145         isl_map_free(map);
 146         return 0;
 147 }
 148
 149 struct align_range_data {
 150         int max_out;
 151         isl_union_map *res;
 152 };
 153
 154 /* Extend the dimension of the range of the given map to data->max_out and
 155  * then add the result to data->res.
 156  */
 157 static int map_align_range(__isl_take isl_map *map, void *user)
 158 {
 159         struct align_range_data *data = user;
 160         int i;
 161         isl_space *dim;
 162         isl_map *proj;
 163         int n_out = isl_map_dim(map, isl_dim_out);
 164
 165         dim = isl_union_map_get_space(data->res);
 166         proj = isl_map_reverse(projection(dim, data->max_out, n_out));
 167         for (i = n_out; i < data->max_out; ++i)
 168                 proj = isl_map_fix_si(proj, isl_dim_out, i, 0);
 169
 170         map = isl_map_apply_range(map, proj);
 171
 172         data->res = isl_union_map_add_map(data->res, map);
 173
 174         return 0;
 175 }
 176
 177 /* Extend the ranges of the maps in the union map such they all have
 178  * the same dimension.
 179  */
 180 __isl_give isl_union_map *align_range(__isl_take isl_union_map *umap)
 181 {
 182         struct align_range_data data;
 183
 184         data.max_out = 0;
 185         isl_union_map_foreach_map(umap, &update_max_out, &data.max_out);
 186
 187         data.res = isl_union_map_empty(isl_union_map_get_space(umap));
 188         isl_union_map_foreach_map(umap, &map_align_range, &data);
 189
 190         isl_union_map_free(umap);
 191         return data.res;
 192 }