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_dim *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
  37     isl_int_init(v);
  38
  39     dim = isl_dim_add(dim, isl_dim_in, len);
  40     dim = isl_dim_add(dim, isl_dim_out, len);
  41     bmap = isl_basic_map_universe(isl_dim_copy(dim));
  42
  43     for (i = 0; i < len; ++i) {
  44         if (i == first)
  45             continue;
  46
  47         c = isl_equality_alloc(isl_dim_copy(dim));
  48         isl_int_set_si(v, -1);
  49         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  50         isl_int_set_si(v, 1);
  51         isl_constraint_set_coefficient(c, isl_dim_out, i, v);
  52         bmap = isl_basic_map_add_constraint(bmap, c);
  53     }
  54
  55     c = isl_equality_alloc(isl_dim_copy(dim));
  56     isl_int_set_si(v, -1);
  57     for (i = 0; i < wave_len; ++i)
  58         isl_constraint_set_coefficient(c, isl_dim_in, first + i, v);
  59     isl_int_set_si(v, 1);
  60     isl_constraint_set_coefficient(c, isl_dim_out, first, v);
  61     bmap = isl_basic_map_add_constraint(bmap, c);
  62
  63     isl_dim_free(dim);
  64     isl_int_clear(v);
  65
  66     return isl_map_from_basic_map(bmap);
  67 }
  68
  69 /* Construct a map from a len-dimensional domain to
  70  * a (len-n)-dimensional domain that projects out the n coordinates
  71  * starting at first.
  72  * "dim" prescribes the parameters.
  73  */
  74 __isl_give isl_map *project_out(__isl_take isl_dim *dim,
  75     int len, int first, int n)
  76 {
  77     int i, j;
  78     isl_constraint *c;
  79     isl_basic_map *bmap;
  80     isl_int v;
  81
  82     isl_int_init(v);
  83
  84     dim = isl_dim_add(dim, isl_dim_in, len);
  85     dim = isl_dim_add(dim, isl_dim_out, len - n);
  86     bmap = isl_basic_map_universe(isl_dim_copy(dim));
  87
  88     for (i = 0, j = 0; i < len; ++i) {
  89         if (i >= first && i < first + n)
  90             continue;
  91         c = isl_equality_alloc(isl_dim_copy(dim));
  92         isl_int_set_si(v, -1);
  93         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  94         isl_int_set_si(v, 1);
  95         isl_constraint_set_coefficient(c, isl_dim_out, j, v);
  96         bmap = isl_basic_map_add_constraint(bmap, c);
  97         ++j;
  98     }
  99     isl_dim_free(dim);
 100
 101     isl_int_clear(v);
 102
 103     return isl_map_from_basic_map(bmap);
 104 }
 105
 106 /* Construct a projection that maps a src_len dimensional domain
 107  * to its first dst_len coordinates.
 108  * "dim" prescribes the parameters.
 109  */
 110 __isl_give isl_map *projection(__isl_take isl_dim *dim,
 111     int src_len, int dst_len)
 112 {
 113     return project_out(dim, src_len, dst_len, src_len - dst_len);
 114 }
 115
 116 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
 117  */
 118 __isl_give isl_set *extend(__isl_take isl_set *set, int dst_len)
 119 {
 120     int n_set;
 121     isl_dim *dim;
 122     isl_map *map;
 123
 124     dim = isl_set_get_dim(set);
 125     n_set = isl_dim_size(dim, isl_dim_set);
 126     dim = isl_dim_drop(dim, isl_dim_set, 0, n_set);
 127     map = projection(dim, dst_len, n_set);
 128     map = isl_map_reverse(map);
 129
 130     return isl_set_apply(set, map);
 131 }
 132
 133 /* Extract the access in stmt->text starting at position identifier
 134  * and of length identifier_len, and return a corresponding cuda_stmt_access.
 135  *
 136  * The access in C notation is first copied to "buffer" (which
 137  * has been allocated by the caller and should be of sufficient size)
 138  * and slightly modified to a map in isl notation.
 139  * This string is then parsed by isl.
 140  */
 141 static struct cuda_stmt_access *stmt_extract_access(struct cuda_stmt *stmt,
 142         char *buffer,
 143         int identifier, int identifier_len, int index, int index_len)
 144 {
 145         int i;
 146         int pos = 0;
 147         unsigned nparam = isl_set_dim(stmt->domain, isl_dim_param);
 148         unsigned nvar = isl_set_dim(stmt->domain, isl_dim_set);
 149         isl_ctx *ctx = isl_set_get_ctx(stmt->domain);
 150         struct cuda_stmt_access *access;
 151
 152         access = isl_alloc_type(ctx, struct cuda_stmt_access);
 153         assert(access);
 154         access->text_offset = identifier;
 155         access->text_len = (index - identifier) + index_len;
 156         access->next = NULL;
 157         access->read = 1;
 158         access->write = 0;
 159
 160         pos += sprintf(buffer, "[");
 161         for (i = 0; i < nparam; ++i) {
 162                 if (i)
 163                         pos += sprintf(buffer + pos, ",");
 164                 pos += sprintf(buffer + pos, "%s",
 165                         isl_set_get_dim_name(stmt->domain, isl_dim_param, i));
 166         }
 167         pos += sprintf(buffer + pos, "] -> { %s[",
 168                         isl_set_get_tuple_name(stmt->domain));
 169         for (i = 0; i < nvar; ++i) {
 170                 if (i)
 171                         pos += sprintf(buffer + pos, ",");
 172                 pos += sprintf(buffer + pos, "%s",
 173                             isl_set_get_dim_name(stmt->domain, isl_dim_set, i));
 174         }
 175         pos += sprintf(buffer + pos, "] -> ");
 176         memcpy(buffer + pos, stmt->text + identifier, identifier_len);
 177         pos += identifier_len;
 178         pos += sprintf(buffer + pos, "[");
 179         for (i = 1; i < index_len - 1; ++i) {
 180                 if (stmt->text[index + i] == ']') {
 181                         buffer[pos++] = ',';
 182                         ++i;
 183                 } else
 184                         buffer[pos++] = stmt->text[index + i];
 185         }
 186         pos += sprintf(buffer + pos, "] }");
 187         access->access = isl_map_read_from_str(ctx, buffer, -1);
 188
 189         return access;
 190 }
 191
 192 /* Construct an access to the given iterator.
 193  */
 194 static struct cuda_stmt_access *iterator_access(struct cuda_stmt *stmt,
 195         int identifier, int len, int pos)
 196 {
 197         isl_ctx *ctx = isl_set_get_ctx(stmt->domain);
 198         struct cuda_stmt_access *access;
 199         isl_constraint *c;
 200         isl_map *map;
 201
 202         map = isl_map_from_domain(isl_set_copy(stmt->domain));
 203         map = isl_map_add_dims(map, isl_dim_out, 1);
 204         c = isl_equality_alloc(isl_map_get_dim(map));
 205         isl_constraint_set_coefficient_si(c, isl_dim_in, pos, 1);
 206         isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
 207         map = isl_map_add_constraint(map, c);
 208
 209         access = isl_alloc_type(ctx, struct cuda_stmt_access);
 210         assert(access);
 211         access->text_offset = identifier;
 212         access->text_len = len;
 213         access->next = NULL;
 214         access->read = 1;
 215         access->write = 0;
 216
 217         access->access = map;
 218
 219         return access;
 220 }
 221
 222 /* Check if the identifier matches one of the iterators and
 223  * if so return an access to that iterator.
 224  */
 225 static struct cuda_stmt_access *stmt_extract_iterator(struct cuda_stmt *stmt,
 226         int identifier, int len)
 227 {
 228         int i;
 229         unsigned n = isl_set_dim(stmt->domain, isl_dim_set);
 230
 231         for (i = 0; i < n; ++i) {
 232                 const char *name;
 233                 name = isl_set_get_dim_name(stmt->domain, isl_dim_set, i);
 234                 if (!strncmp(name, stmt->text + identifier, len) &&
 235                     name[len] == '\0')
 236                         return iterator_access(stmt, identifier, len, i);
 237         }
 238
 239         return NULL;
 240 }
 241
 242 static int is_identifier(int c)
 243 {
 244         return isalnum(c) || c == '_';
 245 }
 246
 247 static int is_assignment(const char *text, int pos, int *compound)
 248 {
 249         if (text[pos] != '=')
 250                 return 0;
 251         if (pos > 0 && text[pos - 1] == '=')
 252                 return 0;
 253         if (text[pos + 1] == '=')
 254                 return 0;
 255         if (pos >= 1 && text[pos - 1] == '>' &&
 256             !(pos >= 2 && text[pos - 2] == '>'))
 257                 return 0;
 258         if (pos >= 1 && text[pos - 1] == '<' &&
 259             !(pos >= 2 && text[pos - 2] == '<'))
 260                 return 0;
 261
 262         *compound = pos >= 1 && strchr("+-*/%&|^<>", text[pos - 1]);
 263
 264         return 1;
 265 }
 266
 267 /* Extract accesses from stmt->text and store them in stmt->accesses.
 268  * dim describes the parameters.
 269  */
 270 void stmt_extract_accesses(struct cuda_stmt *stmt)
 271 {
 272         int i, j;
 273         size_t text_len = strlen(stmt->text);
 274         size_t len = 50;
 275         char *buffer;
 276         int identifier = -1;
 277         int end = -1;
 278         unsigned nparam = isl_set_dim(stmt->domain, isl_dim_param);
 279         unsigned nvar = isl_set_dim(stmt->domain, isl_dim_set);
 280         struct cuda_stmt_access **next_access = &stmt->accesses;
 281
 282         for (i = 0; i < nparam; ++i)
 283                 len += strlen(isl_set_get_dim_name(stmt->domain,
 284                                                         isl_dim_param, i));
 285         for (i = 0; i < nvar; ++i)
 286                 len += strlen(isl_set_get_dim_name(stmt->domain, isl_dim_set, i));
 287         buffer = isl_alloc_array(isl_set_get_ctx(stmt->domain), char, len);
 288         assert(buffer);
 289
 290         stmt->accesses = NULL;
 291         for (i = 0; i < text_len; ++i) {
 292                 if (identifier < 0 && isalpha(stmt->text[i])) {
 293                         identifier = i;
 294                         end = -1;
 295                 } else if (identifier >= 0 && end < 0 &&
 296                            is_identifier(stmt->text[i]))
 297                         continue;
 298                 else if (identifier >= 0 && end < 0 && isblank(stmt->text[i]))
 299                         end = i;
 300                 else if (identifier >= 0 && end >= 0 && isblank(stmt->text[i]))
 301                         continue;
 302                 else if (identifier >= 0 && stmt->text[i] == '[') {
 303                         if (end < 0)
 304                                 end = i;
 305                         for (j = i + 1; j < text_len; ++j)
 306                                 if (stmt->text[j] == ']' &&
 307                                     stmt->text[j + 1] != '[')
 308                                         break;
 309                         *next_access = stmt_extract_access(stmt, buffer,
 310                                 identifier, end - identifier, i, j - i + 1);
 311                         next_access = &(*next_access)->next;
 312                         end = identifier = -1;
 313                         i = j;
 314                 } else if (identifier >= 0) {
 315                         if (end < 0)
 316                                 end = i;
 317                         *next_access = stmt_extract_iterator(stmt, identifier,
 318                                                             end - identifier);
 319                         if (*next_access)
 320                                 next_access = &(*next_access)->next;
 321                         end = identifier = -1;
 322                 } else {
 323                         int compound;
 324
 325                         end = identifier = -1;
 326                         /* If we find an assignment and we have seen a single
 327                          * access, that access must be a write.
 328                          */
 329                         if (is_assignment(stmt->text, i, &compound) &&
 330                             stmt->accesses && !stmt->accesses->next) {
 331                                 stmt->accesses->write = 1;
 332                                 if (!compound)
 333                                         stmt->accesses->read = 0;
 334                         }
 335                 }
 336         }
 337
 338         free(buffer);
 339 }