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 that maps a domain of dimensionality "len"
  22  * to another domain of the same dimensionality such that
  23  * coordinate "first" of the range is equal to the sum of the "wave_len"
  24  * coordinates starting at "first" in the domain.
  25  * The remaining coordinates in the range are equal to the corresponding ones
  26  * in the domain.
  27  * "dim" prescribes the parameters.
  28  */
  29 __isl_give isl_map *wavefront(__isl_take isl_space *dim, int len,
  30         int first, int wave_len)
  31 {
  32     int i;
  33     isl_int v;
  34     isl_basic_map *bmap;
  35     isl_constraint *c;
  36     isl_local_space *ls;
  37
  38     isl_int_init(v);
  39
  40     dim = isl_space_add_dims(dim, isl_dim_in, len);
  41     dim = isl_space_add_dims(dim, isl_dim_out, len);
  42     bmap = isl_basic_map_universe(isl_space_copy(dim));
  43     ls = isl_local_space_from_space(dim);
  44
  45     for (i = 0; i < len; ++i) {
  46         if (i == first)
  47             continue;
  48
  49         c = isl_equality_alloc(isl_local_space_copy(ls));
  50         isl_int_set_si(v, -1);
  51         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  52         isl_int_set_si(v, 1);
  53         isl_constraint_set_coefficient(c, isl_dim_out, i, v);
  54         bmap = isl_basic_map_add_constraint(bmap, c);
  55     }
  56
  57     c = isl_equality_alloc(isl_local_space_copy(ls));
  58     isl_int_set_si(v, -1);
  59     for (i = 0; i < wave_len; ++i)
  60         isl_constraint_set_coefficient(c, isl_dim_in, first + i, v);
  61     isl_int_set_si(v, 1);
  62     isl_constraint_set_coefficient(c, isl_dim_out, first, v);
  63     bmap = isl_basic_map_add_constraint(bmap, c);
  64
  65     isl_local_space_free(ls);
  66     isl_int_clear(v);
  67
  68     return isl_map_from_basic_map(bmap);
  69 }
  70
  71 /* Construct a map from a len-dimensional domain to
  72  * a (len-n)-dimensional domain that projects out the n coordinates
  73  * starting at first.
  74  * "dim" prescribes the parameters.
  75  */
  76 __isl_give isl_map *project_out(__isl_take isl_space *dim,
  77     int len, int first, int n)
  78 {
  79     int i, j;
  80     isl_constraint *c;
  81     isl_basic_map *bmap;
  82     isl_int v;
  83     isl_local_space *ls;
  84
  85     isl_int_init(v);
  86
  87     dim = isl_space_add_dims(dim, isl_dim_in, len);
  88     dim = isl_space_add_dims(dim, isl_dim_out, len - n);
  89     bmap = isl_basic_map_universe(isl_space_copy(dim));
  90     ls = isl_local_space_from_space(dim);
  91
  92     for (i = 0, j = 0; i < len; ++i) {
  93         if (i >= first && i < first + n)
  94             continue;
  95         c = isl_equality_alloc(isl_local_space_copy(ls));
  96         isl_int_set_si(v, -1);
  97         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  98         isl_int_set_si(v, 1);
  99         isl_constraint_set_coefficient(c, isl_dim_out, j, v);
 100         bmap = isl_basic_map_add_constraint(bmap, c);
 101         ++j;
 102     }
 103     isl_local_space_free(ls);
 104
 105     isl_int_clear(v);
 106
 107     return isl_map_from_basic_map(bmap);
 108 }
 109
 110 /* Construct a projection that maps a src_len dimensional domain
 111  * to its first dst_len coordinates.
 112  * "dim" prescribes the parameters.
 113  */
 114 __isl_give isl_map *projection(__isl_take isl_space *dim,
 115     int src_len, int dst_len)
 116 {
 117     return project_out(dim, src_len, dst_len, src_len - dst_len);
 118 }
 119
 120 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
 121  */
 122 __isl_give isl_set *extend(__isl_take isl_set *set, int dst_len)
 123 {
 124     int n_set;
 125     isl_space *dim;
 126     isl_map *map;
 127
 128     dim = isl_set_get_space(set);
 129     n_set = isl_space_dim(dim, isl_dim_set);
 130     dim = isl_space_drop_dims(dim, isl_dim_set, 0, n_set);
 131     map = projection(dim, dst_len, n_set);
 132     map = isl_map_reverse(map);
 133
 134     return isl_set_apply(set, map);
 135 }
 136
 137 /* Set max_out to the maximal number of output dimensions over
 138  * all maps.
 139  */
 140 static int update_max_out(__isl_take isl_map *map, void *user)
 141 {
 142         int *max_out = user;
 143         int n_out = isl_map_dim(map, isl_dim_out);
 144
 145         if (n_out > *max_out)
 146                 *max_out = n_out;
 147
 148         isl_map_free(map);
 149         return 0;
 150 }
 151
 152 struct align_range_data {
 153         int max_out;
 154         isl_union_map *res;
 155 };
 156
 157 /* Extend the dimension of the range of the given map to data->max_out and
 158  * then add the result to data->res.
 159  */
 160 static int map_align_range(__isl_take isl_map *map, void *user)
 161 {
 162         struct align_range_data *data = user;
 163         int i;
 164         isl_space *dim;
 165         isl_map *proj;
 166         int n_out = isl_map_dim(map, isl_dim_out);
 167
 168         dim = isl_union_map_get_space(data->res);
 169         proj = isl_map_reverse(projection(dim, data->max_out, n_out));
 170         for (i = n_out; i < data->max_out; ++i)
 171                 proj = isl_map_fix_si(proj, isl_dim_out, i, 0);
 172
 173         map = isl_map_apply_range(map, proj);
 174
 175         data->res = isl_union_map_add_map(data->res, map);
 176
 177         return 0;
 178 }
 179
 180 /* Extend the ranges of the maps in the union map such they all have
 181  * the same dimension.
 182  */
 183 __isl_give isl_union_map *align_range(__isl_take isl_union_map *umap)
 184 {
 185         struct align_range_data data;
 186
 187         data.max_out = 0;
 188         isl_union_map_foreach_map(umap, &update_max_out, &data.max_out);
 189
 190         data.res = isl_union_map_empty(isl_union_map_get_space(umap));
 191         isl_union_map_foreach_map(umap, &map_align_range, &data);
 192
 193         isl_union_map_free(umap);
 194         return data.res;
 195 }