isl_schedule_constraints.c

   1 /*
   2  * Copyright 2012      Ecole Normale Superieure
   3  * Copyright 2015-2016 Sven Verdoolaege
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege,
   8  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   9  */
  10
  11 #include <isl_schedule_constraints.h>
  12 #include <isl/schedule.h>
  13 #include <isl/set.h>
  14 #include <isl/map.h>
  15 #include <isl/union_set.h>
  16 #include <isl/union_map.h>
  17
  18 /* The constraints that need to be satisfied by a schedule on "domain".
  19  *
  20  * "context" specifies extra constraints on the parameters.
  21  *
  22  * "validity" constraints map domain elements i to domain elements
  23  * that should be scheduled after i.  (Hard constraint)
  24  * "proximity" constraints map domain elements i to domains elements
  25  * that should be scheduled as early as possible after i (or before i).
  26  * (Soft constraint)
  27  *
  28  * "condition" and "conditional_validity" constraints map possibly "tagged"
  29  * domain elements i -> s to "tagged" domain elements j -> t.
  30  * The elements of the "conditional_validity" constraints, but without the
  31  * tags (i.e., the elements i -> j) are treated as validity constraints,
  32  * except that during the construction of a tilable band,
  33  * the elements of the "conditional_validity" constraints may be violated
  34  * provided that all adjacent elements of the "condition" constraints
  35  * are local within the band.
  36  * A dependence is local within a band if domain and range are mapped
  37  * to the same schedule point by the band.
  38  */
  39 struct isl_schedule_constraints {
  40         isl_union_set *domain;
  41         isl_set *context;
  42
  43         isl_union_map *constraint[isl_edge_last + 1];
  44 };
  45
  46 __isl_give isl_schedule_constraints *isl_schedule_constraints_copy(
  47         __isl_keep isl_schedule_constraints *sc)
  48 {
  49         isl_ctx *ctx;
  50         isl_schedule_constraints *sc_copy;
  51         enum isl_edge_type i;
  52
  53         ctx = isl_union_set_get_ctx(sc->domain);
  54         sc_copy = isl_calloc_type(ctx, struct isl_schedule_constraints);
  55         if (!sc_copy)
  56                 return NULL;
  57
  58         sc_copy->domain = isl_union_set_copy(sc->domain);
  59         sc_copy->context = isl_set_copy(sc->context);
  60         if (!sc_copy->domain || !sc_copy->context)
  61                 return isl_schedule_constraints_free(sc_copy);
  62
  63         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
  64                 sc_copy->constraint[i] = isl_union_map_copy(sc->constraint[i]);
  65                 if (!sc_copy->constraint[i])
  66                         return isl_schedule_constraints_free(sc_copy);
  67         }
  68
  69         return sc_copy;
  70 }
  71
  72 /* Construct an isl_schedule_constraints object for computing a schedule
  73  * on "domain".  The initial object does not impose any constraints.
  74  */
  75 __isl_give isl_schedule_constraints *isl_schedule_constraints_on_domain(
  76         __isl_take isl_union_set *domain)
  77 {
  78         isl_ctx *ctx;
  79         isl_space *space;
  80         isl_schedule_constraints *sc;
  81         isl_union_map *empty;
  82         enum isl_edge_type i;
  83
  84         if (!domain)
  85                 return NULL;
  86
  87         ctx = isl_union_set_get_ctx(domain);
  88         sc = isl_calloc_type(ctx, struct isl_schedule_constraints);
  89         if (!sc)
  90                 goto error;
  91
  92         space = isl_union_set_get_space(domain);
  93         sc->domain = domain;
  94         sc->context = isl_set_universe(isl_space_copy(space));
  95         empty = isl_union_map_empty(space);
  96         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
  97                 sc->constraint[i] = isl_union_map_copy(empty);
  98                 if (!sc->constraint[i])
  99                         sc->domain = isl_union_set_free(sc->domain);
 100         }
 101         isl_union_map_free(empty);
 102
 103         if (!sc->domain || !sc->context)
 104                 return isl_schedule_constraints_free(sc);
 105
 106         return sc;
 107 error:
 108         isl_union_set_free(domain);
 109         return NULL;
 110 }
 111
 112 /* Replace the context of "sc" by "context".
 113  */
 114 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_context(
 115         __isl_take isl_schedule_constraints *sc, __isl_take isl_set *context)
 116 {
 117         if (!sc || !context)
 118                 goto error;
 119
 120         isl_set_free(sc->context);
 121         sc->context = context;
 122
 123         return sc;
 124 error:
 125         isl_schedule_constraints_free(sc);
 126         isl_set_free(context);
 127         return NULL;
 128 }
 129
 130 /* Replace the validity constraints of "sc" by "validity".
 131  */
 132 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_validity(
 133         __isl_take isl_schedule_constraints *sc,
 134         __isl_take isl_union_map *validity)
 135 {
 136         if (!sc || !validity)
 137                 goto error;
 138
 139         isl_union_map_free(sc->constraint[isl_edge_validity]);
 140         sc->constraint[isl_edge_validity] = validity;
 141
 142         return sc;
 143 error:
 144         isl_schedule_constraints_free(sc);
 145         isl_union_map_free(validity);
 146         return NULL;
 147 }
 148
 149 /* Replace the coincidence constraints of "sc" by "coincidence".
 150  */
 151 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_coincidence(
 152         __isl_take isl_schedule_constraints *sc,
 153         __isl_take isl_union_map *coincidence)
 154 {
 155         if (!sc || !coincidence)
 156                 goto error;
 157
 158         isl_union_map_free(sc->constraint[isl_edge_coincidence]);
 159         sc->constraint[isl_edge_coincidence] = coincidence;
 160
 161         return sc;
 162 error:
 163         isl_schedule_constraints_free(sc);
 164         isl_union_map_free(coincidence);
 165         return NULL;
 166 }
 167
 168 /* Replace the proximity constraints of "sc" by "proximity".
 169  */
 170 __isl_give isl_schedule_constraints *isl_schedule_constraints_set_proximity(
 171         __isl_take isl_schedule_constraints *sc,
 172         __isl_take isl_union_map *proximity)
 173 {
 174         if (!sc || !proximity)
 175                 goto error;
 176
 177         isl_union_map_free(sc->constraint[isl_edge_proximity]);
 178         sc->constraint[isl_edge_proximity] = proximity;
 179
 180         return sc;
 181 error:
 182         isl_schedule_constraints_free(sc);
 183         isl_union_map_free(proximity);
 184         return NULL;
 185 }
 186
 187 /* Replace the conditional validity constraints of "sc" by "condition"
 188  * and "validity".
 189  */
 190 __isl_give isl_schedule_constraints *
 191 isl_schedule_constraints_set_conditional_validity(
 192         __isl_take isl_schedule_constraints *sc,
 193         __isl_take isl_union_map *condition,
 194         __isl_take isl_union_map *validity)
 195 {
 196         if (!sc || !condition || !validity)
 197                 goto error;
 198
 199         isl_union_map_free(sc->constraint[isl_edge_condition]);
 200         sc->constraint[isl_edge_condition] = condition;
 201         isl_union_map_free(sc->constraint[isl_edge_conditional_validity]);
 202         sc->constraint[isl_edge_conditional_validity] = validity;
 203
 204         return sc;
 205 error:
 206         isl_schedule_constraints_free(sc);
 207         isl_union_map_free(condition);
 208         isl_union_map_free(validity);
 209         return NULL;
 210 }
 211
 212 __isl_null isl_schedule_constraints *isl_schedule_constraints_free(
 213         __isl_take isl_schedule_constraints *sc)
 214 {
 215         enum isl_edge_type i;
 216
 217         if (!sc)
 218                 return NULL;
 219
 220         isl_union_set_free(sc->domain);
 221         isl_set_free(sc->context);
 222         for (i = isl_edge_first; i <= isl_edge_last; ++i)
 223                 isl_union_map_free(sc->constraint[i]);
 224
 225         free(sc);
 226
 227         return NULL;
 228 }
 229
 230 isl_ctx *isl_schedule_constraints_get_ctx(
 231         __isl_keep isl_schedule_constraints *sc)
 232 {
 233         return sc ? isl_union_set_get_ctx(sc->domain) : NULL;
 234 }
 235
 236 /* Return the domain of "sc".
 237  */
 238 __isl_give isl_union_set *isl_schedule_constraints_get_domain(
 239         __isl_keep isl_schedule_constraints *sc)
 240 {
 241         if (!sc)
 242                 return NULL;
 243
 244         return isl_union_set_copy(sc->domain);
 245 }
 246
 247 /* Return the context of "sc".
 248  */
 249 __isl_give isl_set *isl_schedule_constraints_get_context(
 250         __isl_keep isl_schedule_constraints *sc)
 251 {
 252         if (!sc)
 253                 return NULL;
 254
 255         return isl_set_copy(sc->context);
 256 }
 257
 258 /* Return the constraints of type "type" in "sc".
 259  */
 260 __isl_give isl_union_map *isl_schedule_constraints_get(
 261         __isl_keep isl_schedule_constraints *sc, enum isl_edge_type type)
 262 {
 263         if (!sc)
 264                 return NULL;
 265
 266         return isl_union_map_copy(sc->constraint[type]);
 267 }
 268
 269 /* Return the validity constraints of "sc".
 270  */
 271 __isl_give isl_union_map *isl_schedule_constraints_get_validity(
 272         __isl_keep isl_schedule_constraints *sc)
 273 {
 274         return isl_schedule_constraints_get(sc, isl_edge_validity);
 275 }
 276
 277 /* Return the coincidence constraints of "sc".
 278  */
 279 __isl_give isl_union_map *isl_schedule_constraints_get_coincidence(
 280         __isl_keep isl_schedule_constraints *sc)
 281 {
 282         return isl_schedule_constraints_get(sc, isl_edge_coincidence);
 283 }
 284
 285 /* Return the proximity constraints of "sc".
 286  */
 287 __isl_give isl_union_map *isl_schedule_constraints_get_proximity(
 288         __isl_keep isl_schedule_constraints *sc)
 289 {
 290         return isl_schedule_constraints_get(sc, isl_edge_proximity);
 291 }
 292
 293 /* Return the conditional validity constraints of "sc".
 294  */
 295 __isl_give isl_union_map *isl_schedule_constraints_get_conditional_validity(
 296         __isl_keep isl_schedule_constraints *sc)
 297 {
 298         return isl_schedule_constraints_get(sc, isl_edge_conditional_validity);
 299 }
 300
 301 /* Return the conditions for the conditional validity constraints of "sc".
 302  */
 303 __isl_give isl_union_map *
 304 isl_schedule_constraints_get_conditional_validity_condition(
 305         __isl_keep isl_schedule_constraints *sc)
 306 {
 307         return isl_schedule_constraints_get(sc, isl_edge_condition);
 308 }
 309
 310 /* Add "c" to the constraints of type "type" in "sc".
 311  */
 312 __isl_give isl_schedule_constraints *isl_schedule_constraints_add(
 313         __isl_take isl_schedule_constraints *sc, enum isl_edge_type type,
 314         __isl_take isl_union_map *c)
 315 {
 316         if (!sc || !c)
 317                 goto error;
 318
 319         c = isl_union_map_union(sc->constraint[type], c);
 320         sc->constraint[type] = c;
 321         if (!c)
 322                 return isl_schedule_constraints_free(sc);
 323
 324         return sc;
 325 error:
 326         isl_schedule_constraints_free(sc);
 327         isl_union_map_free(c);
 328         return NULL;
 329 }
 330
 331 /* Can a schedule constraint of type "type" be tagged?
 332  */
 333 static int may_be_tagged(enum isl_edge_type type)
 334 {
 335         if (type == isl_edge_condition || type == isl_edge_conditional_validity)
 336                 return 1;
 337         return 0;
 338 }
 339
 340 /* Apply "umap" to the domains of the wrapped relations
 341  * inside the domain and range of "c".
 342  *
 343  * That is, for each map of the form
 344  *
 345  *      [D -> S] -> [E -> T]
 346  *
 347  * in "c", apply "umap" to D and E.
 348  *
 349  * D is exposed by currying the relation to
 350  *
 351  *      D -> [S -> [E -> T]]
 352  *
 353  * E is exposed by doing the same to the inverse of "c".
 354  */
 355 static __isl_give isl_union_map *apply_factor_domain(
 356         __isl_take isl_union_map *c, __isl_keep isl_union_map *umap)
 357 {
 358         c = isl_union_map_curry(c);
 359         c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
 360         c = isl_union_map_uncurry(c);
 361
 362         c = isl_union_map_reverse(c);
 363         c = isl_union_map_curry(c);
 364         c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
 365         c = isl_union_map_uncurry(c);
 366         c = isl_union_map_reverse(c);
 367
 368         return c;
 369 }
 370
 371 /* Apply "umap" to domain and range of "c".
 372  * If "tag" is set, then "c" may contain tags and then "umap"
 373  * needs to be applied to the domains of the wrapped relations
 374  * inside the domain and range of "c".
 375  */
 376 static __isl_give isl_union_map *apply(__isl_take isl_union_map *c,
 377         __isl_keep isl_union_map *umap, int tag)
 378 {
 379         isl_union_map *t;
 380
 381         if (tag)
 382                 t = isl_union_map_copy(c);
 383         c = isl_union_map_apply_domain(c, isl_union_map_copy(umap));
 384         c = isl_union_map_apply_range(c, isl_union_map_copy(umap));
 385         if (!tag)
 386                 return c;
 387         t = apply_factor_domain(t, umap);
 388         c = isl_union_map_union(c, t);
 389         return c;
 390 }
 391
 392 /* Apply "umap" to the domain of the schedule constraints "sc".
 393  *
 394  * The two sides of the various schedule constraints are adjusted
 395  * accordingly.
 396  */
 397 __isl_give isl_schedule_constraints *isl_schedule_constraints_apply(
 398         __isl_take isl_schedule_constraints *sc,
 399         __isl_take isl_union_map *umap)
 400 {
 401         enum isl_edge_type i;
 402
 403         if (!sc || !umap)
 404                 goto error;
 405
 406         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
 407                 int tag = may_be_tagged(i);
 408
 409                 sc->constraint[i] = apply(sc->constraint[i], umap, tag);
 410                 if (!sc->constraint[i])
 411                         goto error;
 412         }
 413         sc->domain = isl_union_set_apply(sc->domain, umap);
 414         if (!sc->domain)
 415                 return isl_schedule_constraints_free(sc);
 416
 417         return sc;
 418 error:
 419         isl_schedule_constraints_free(sc);
 420         isl_union_map_free(umap);
 421         return NULL;
 422 }
 423
 424 void isl_schedule_constraints_dump(__isl_keep isl_schedule_constraints *sc)
 425 {
 426         if (!sc)
 427                 return;
 428
 429         fprintf(stderr, "domain: ");
 430         isl_union_set_dump(sc->domain);
 431         fprintf(stderr, "context: ");
 432         isl_set_dump(sc->context);
 433         fprintf(stderr, "validity: ");
 434         isl_union_map_dump(sc->constraint[isl_edge_validity]);
 435         fprintf(stderr, "proximity: ");
 436         isl_union_map_dump(sc->constraint[isl_edge_proximity]);
 437         fprintf(stderr, "coincidence: ");
 438         isl_union_map_dump(sc->constraint[isl_edge_coincidence]);
 439         fprintf(stderr, "condition: ");
 440         isl_union_map_dump(sc->constraint[isl_edge_condition]);
 441         fprintf(stderr, "conditional_validity: ");
 442         isl_union_map_dump(sc->constraint[isl_edge_conditional_validity]);
 443 }
 444
 445 /* Align the parameters of the fields of "sc".
 446  */
 447 __isl_give isl_schedule_constraints *
 448 isl_schedule_constraints_align_params(__isl_take isl_schedule_constraints *sc)
 449 {
 450         isl_space *space;
 451         enum isl_edge_type i;
 452
 453         if (!sc)
 454                 return NULL;
 455
 456         space = isl_union_set_get_space(sc->domain);
 457         space = isl_space_align_params(space, isl_set_get_space(sc->context));
 458         for (i = isl_edge_first; i <= isl_edge_last; ++i)
 459                 space = isl_space_align_params(space,
 460                                     isl_union_map_get_space(sc->constraint[i]));
 461
 462         for (i = isl_edge_first; i <= isl_edge_last; ++i) {
 463                 sc->constraint[i] = isl_union_map_align_params(
 464                                     sc->constraint[i], isl_space_copy(space));
 465                 if (!sc->constraint[i])
 466                         space = isl_space_free(space);
 467         }
 468         sc->context = isl_set_align_params(sc->context, isl_space_copy(space));
 469         sc->domain = isl_union_set_align_params(sc->domain, space);
 470         if (!sc->context || !sc->domain)
 471                 return isl_schedule_constraints_free(sc);
 472
 473         return sc;
 474 }
 475
 476 /* Add the number of basic maps in "map" to *n.
 477  */
 478 static isl_stat add_n_basic_map(__isl_take isl_map *map, void *user)
 479 {
 480         int *n = user;
 481
 482         *n += isl_map_n_basic_map(map);
 483         isl_map_free(map);
 484
 485         return isl_stat_ok;
 486 }
 487
 488 /* Return the total number of isl_basic_maps in the constraints of "sc".
 489  * Return -1 on error.
 490  */
 491 int isl_schedule_constraints_n_basic_map(
 492         __isl_keep isl_schedule_constraints *sc)
 493 {
 494         enum isl_edge_type i;
 495         int n = 0;
 496
 497         if (!sc)
 498                 return -1;
 499         for (i = isl_edge_first; i <= isl_edge_last; ++i)
 500                 if (isl_union_map_foreach_map(sc->constraint[i],
 501                                                 &add_n_basic_map, &n) < 0)
 502                         return -1;
 503
 504         return n;
 505 }
 506
 507 /* Return the total number of isl_maps in the constraints of "sc".
 508  */
 509 int isl_schedule_constraints_n_map(__isl_keep isl_schedule_constraints *sc)
 510 {
 511         enum isl_edge_type i;
 512         int n = 0;
 513
 514         for (i = isl_edge_first; i <= isl_edge_last; ++i)
 515                 n += isl_union_map_n_map(sc->constraint[i]);
 516
 517         return n;
 518 }