isl_flow.c

   1 /*
   2  * Copyright 2005-2007 Universiteit Leiden
   3  * Copyright 2008-2009 Katholieke Universiteit Leuven
   4  * Copyright 2010      INRIA Saclay
   5  *
   6  * Use of this software is governed by the GNU LGPLv2.1 license
   7  *
   8  * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
   9  * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
  10  * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
  11  * B-3001 Leuven, Belgium
  12  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  13  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  14  */
  15
  16 #include <isl/set.h>
  17 #include <isl/map.h>
  18 #include <isl/flow.h>
  19 #include <isl_qsort.h>
  20
  21 /* A private structure to keep track of a mapping together with
  22  * a user-specified identifier and a boolean indicating whether
  23  * the map represents a must or may access/dependence.
  24  */
  25 struct isl_labeled_map {
  26         struct isl_map  *map;
  27         void            *data;
  28         int             must;
  29 };
  30
  31 /* A structure containing the input for dependence analysis:
  32  * - a sink
  33  * - n_must + n_may (<= max_source) sources
  34  * - a function for determining the relative order of sources and sink
  35  * The must sources are placed before the may sources.
  36  *
  37  * domain_map is an auxiliary map that maps the sink access relation
  38  * to the domain of this access relation.
  39  *
  40  * restrict_sources is a callback that (if not NULL) will be called
  41  * right before any lexicographical maximization.
  42  */
  43 struct isl_access_info {
  44         isl_map                         *domain_map;
  45         struct isl_labeled_map          sink;
  46         isl_access_level_before         level_before;
  47         isl_access_restrict_sources     restrict_sources;
  48         int                             max_source;
  49         int                             n_must;
  50         int                             n_may;
  51         struct isl_labeled_map          source[1];
  52 };
  53
  54 /* A structure containing the output of dependence analysis:
  55  * - n_source dependences
  56  * - a wrapped subset of the sink for which definitely no source could be found
  57  * - a wrapped subset of the sink for which possibly no source could be found
  58  */
  59 struct isl_flow {
  60         isl_set                 *must_no_source;
  61         isl_set                 *may_no_source;
  62         int                     n_source;
  63         struct isl_labeled_map  *dep;
  64 };
  65
  66 /* Construct an isl_access_info structure and fill it up with
  67  * the given data.  The number of sources is set to 0.
  68  */
  69 __isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink,
  70         void *sink_user, isl_access_level_before fn, int max_source)
  71 {
  72         isl_ctx *ctx;
  73         struct isl_access_info *acc;
  74
  75         if (!sink)
  76                 return NULL;
  77
  78         ctx = isl_map_get_ctx(sink);
  79         isl_assert(ctx, max_source >= 0, goto error);
  80
  81         acc = isl_calloc(ctx, struct isl_access_info,
  82                         sizeof(struct isl_access_info) +
  83                         (max_source - 1) * sizeof(struct isl_labeled_map));
  84         if (!acc)
  85                 goto error;
  86
  87         acc->sink.map = sink;
  88         acc->sink.data = sink_user;
  89         acc->level_before = fn;
  90         acc->max_source = max_source;
  91         acc->n_must = 0;
  92         acc->n_may = 0;
  93
  94         return acc;
  95 error:
  96         isl_map_free(sink);
  97         return NULL;
  98 }
  99
 100 /* Free the given isl_access_info structure.
 101  */
 102 void isl_access_info_free(__isl_take isl_access_info *acc)
 103 {
 104         int i;
 105
 106         if (!acc)
 107                 return;
 108         isl_map_free(acc->domain_map);
 109         isl_map_free(acc->sink.map);
 110         for (i = 0; i < acc->n_must + acc->n_may; ++i)
 111                 isl_map_free(acc->source[i].map);
 112         free(acc);
 113 }
 114
 115 isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc)
 116 {
 117         return acc ? isl_map_get_ctx(acc->sink.map) : NULL;
 118 }
 119
 120 __isl_give isl_access_info *isl_access_info_set_restrict_sources(
 121         __isl_take isl_access_info *acc, isl_access_restrict_sources fn)
 122 {
 123         if (!acc)
 124                 return NULL;
 125         acc->restrict_sources = fn;
 126         return acc;
 127 }
 128
 129 /* Add another source to an isl_access_info structure, making
 130  * sure the "must" sources are placed before the "may" sources.
 131  * This function may be called at most max_source times on a
 132  * given isl_access_info structure, with max_source as specified
 133  * in the call to isl_access_info_alloc that constructed the structure.
 134  */
 135 __isl_give isl_access_info *isl_access_info_add_source(
 136         __isl_take isl_access_info *acc, __isl_take isl_map *source,
 137         int must, void *source_user)
 138 {
 139         isl_ctx *ctx;
 140
 141         if (!acc)
 142                 return NULL;
 143         ctx = isl_map_get_ctx(acc->sink.map);
 144         isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);
 145
 146         if (must) {
 147                 if (acc->n_may)
 148                         acc->source[acc->n_must + acc->n_may] =
 149                                 acc->source[acc->n_must];
 150                 acc->source[acc->n_must].map = source;
 151                 acc->source[acc->n_must].data = source_user;
 152                 acc->source[acc->n_must].must = 1;
 153                 acc->n_must++;
 154         } else {
 155                 acc->source[acc->n_must + acc->n_may].map = source;
 156                 acc->source[acc->n_must + acc->n_may].data = source_user;
 157                 acc->source[acc->n_must + acc->n_may].must = 0;
 158                 acc->n_may++;
 159         }
 160
 161         return acc;
 162 error:
 163         isl_map_free(source);
 164         isl_access_info_free(acc);
 165         return NULL;
 166 }
 167
 168 /* Return -n, 0 or n (with n a positive value), depending on whether
 169  * the source access identified by p1 should be sorted before, together
 170  * or after that identified by p2.
 171  *
 172  * If p1 and p2 share a different number of levels with the sink,
 173  * then the one with the lowest number of shared levels should be
 174  * sorted first.
 175  * If they both share no levels, then the order is irrelevant.
 176  * Otherwise, if p1 appears before p2, then it should be sorted first.
 177  * For more generic initial schedules, it is possible that neither
 178  * p1 nor p2 appears before the other, or at least not in any obvious way.
 179  * We therefore also check if p2 appears before p1, in which case p2
 180  * should be sorted first.
 181  * If not, we try to order the two statements based on the description
 182  * of the iteration domains.  This results in an arbitrary, but fairly
 183  * stable ordering.
 184  */
 185 static int access_sort_cmp(const void *p1, const void *p2, void *user)
 186 {
 187         isl_access_info *acc = user;
 188         const struct isl_labeled_map *i1, *i2;
 189         int level1, level2;
 190         uint32_t h1, h2;
 191         i1 = (const struct isl_labeled_map *) p1;
 192         i2 = (const struct isl_labeled_map *) p2;
 193
 194         level1 = acc->level_before(i1->data, acc->sink.data);
 195         level2 = acc->level_before(i2->data, acc->sink.data);
 196
 197         if (level1 != level2 || !level1)
 198                 return level1 - level2;
 199
 200         level1 = acc->level_before(i1->data, i2->data);
 201         if (level1 % 2)
 202                 return -1;
 203
 204         level2 = acc->level_before(i2->data, i1->data);
 205         if (level2 % 2)
 206                 return 1;
 207
 208         h1 = isl_map_get_hash(i1->map);
 209         h2 = isl_map_get_hash(i2->map);
 210         return h1 > h2 ? 1 : h1 < h2 ? -1 : 0;
 211 }
 212
 213 /* Sort the must source accesses in order of increasing number of shared
 214  * levels with the sink access.
 215  * Source accesses with the same number of shared levels are sorted
 216  * in their textual order.
 217  */
 218 static __isl_give isl_access_info *isl_access_info_sort_sources(
 219         __isl_take isl_access_info *acc)
 220 {
 221         if (!acc)
 222                 return NULL;
 223         if (acc->n_must <= 1)
 224                 return acc;
 225
 226         isl_quicksort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),
 227                 access_sort_cmp, acc);
 228
 229         return acc;
 230 }
 231
 232 /* Align the parameters of the two spaces if needed and then call
 233  * isl_space_join.
 234  */
 235 static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left,
 236         __isl_take isl_space *right)
 237 {
 238         if (isl_space_match(left, isl_dim_param, right, isl_dim_param))
 239                 return isl_space_join(left, right);
 240
 241         left = isl_space_align_params(left, isl_space_copy(right));
 242         right = isl_space_align_params(right, isl_space_copy(left));
 243         return isl_space_join(left, right);
 244 }
 245
 246 /* Initialize an empty isl_flow structure corresponding to a given
 247  * isl_access_info structure.
 248  * For each must access, two dependences are created (initialized
 249  * to the empty relation), one for the resulting must dependences
 250  * and one for the resulting may dependences.  May accesses can
 251  * only lead to may dependences, so only one dependence is created
 252  * for each of them.
 253  * This function is private as isl_flow structures are only supposed
 254  * to be created by isl_access_info_compute_flow.
 255  */
 256 static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc)
 257 {
 258         int i;
 259         struct isl_ctx *ctx;
 260         struct isl_flow *dep;
 261
 262         if (!acc)
 263                 return NULL;
 264
 265         ctx = isl_map_get_ctx(acc->sink.map);
 266         dep = isl_calloc_type(ctx, struct isl_flow);
 267         if (!dep)
 268                 return NULL;
 269
 270         dep->dep = isl_calloc_array(ctx, struct isl_labeled_map,
 271                                         2 * acc->n_must + acc->n_may);
 272         if (!dep->dep)
 273                 goto error;
 274
 275         dep->n_source = 2 * acc->n_must + acc->n_may;
 276         for (i = 0; i < acc->n_must; ++i) {
 277                 isl_space *dim;
 278                 dim = space_align_and_join(
 279                         isl_map_get_space(acc->source[i].map),
 280                         isl_space_reverse(isl_map_get_space(acc->sink.map)));
 281                 dep->dep[2 * i].map = isl_map_empty(dim);
 282                 dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map);
 283                 dep->dep[2 * i].data = acc->source[i].data;
 284                 dep->dep[2 * i + 1].data = acc->source[i].data;
 285                 dep->dep[2 * i].must = 1;
 286                 dep->dep[2 * i + 1].must = 0;
 287                 if (!dep->dep[2 * i].map || !dep->dep[2 * i + 1].map)
 288                         goto error;
 289         }
 290         for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) {
 291                 isl_space *dim;
 292                 dim = space_align_and_join(
 293                         isl_map_get_space(acc->source[i].map),
 294                         isl_space_reverse(isl_map_get_space(acc->sink.map)));
 295                 dep->dep[acc->n_must + i].map = isl_map_empty(dim);
 296                 dep->dep[acc->n_must + i].data = acc->source[i].data;
 297                 dep->dep[acc->n_must + i].must = 0;
 298                 if (!dep->dep[acc->n_must + i].map)
 299                         goto error;
 300         }
 301
 302         return dep;
 303 error:
 304         isl_flow_free(dep);
 305         return NULL;
 306 }
 307
 308 /* Iterate over all sources and for each resulting flow dependence
 309  * that is not empty, call the user specfied function.
 310  * The second argument in this function call identifies the source,
 311  * while the third argument correspond to the final argument of
 312  * the isl_flow_foreach call.
 313  */
 314 int isl_flow_foreach(__isl_keep isl_flow *deps,
 315         int (*fn)(__isl_take isl_map *dep, int must, void *dep_user, void *user),
 316         void *user)
 317 {
 318         int i;
 319
 320         if (!deps)
 321                 return -1;
 322
 323         for (i = 0; i < deps->n_source; ++i) {
 324                 if (isl_map_plain_is_empty(deps->dep[i].map))
 325                         continue;
 326                 if (fn(isl_map_copy(deps->dep[i].map), deps->dep[i].must,
 327                                 deps->dep[i].data, user) < 0)
 328                         return -1;
 329         }
 330
 331         return 0;
 332 }
 333
 334 /* Return a copy of the subset of the sink for which no source could be found.
 335  */
 336 __isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
 337 {
 338         if (!deps)
 339                 return NULL;
 340
 341         if (must)
 342                 return isl_set_unwrap(isl_set_copy(deps->must_no_source));
 343         else
 344                 return isl_set_unwrap(isl_set_copy(deps->may_no_source));
 345 }
 346
 347 void isl_flow_free(__isl_take isl_flow *deps)
 348 {
 349         int i;
 350
 351         if (!deps)
 352                 return;
 353         isl_set_free(deps->must_no_source);
 354         isl_set_free(deps->may_no_source);
 355         if (deps->dep) {
 356                 for (i = 0; i < deps->n_source; ++i)
 357                         isl_map_free(deps->dep[i].map);
 358                 free(deps->dep);
 359         }
 360         free(deps);
 361 }
 362
 363 isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps)
 364 {
 365         return deps ? isl_set_get_ctx(deps->must_no_source) : NULL;
 366 }
 367
 368 /* Return a map that enforces that the domain iteration occurs after
 369  * the range iteration at the given level.
 370  * If level is odd, then the domain iteration should occur after
 371  * the target iteration in their shared level/2 outermost loops.
 372  * In this case we simply need to enforce that these outermost
 373  * loop iterations are the same.
 374  * If level is even, then the loop iterator of the domain should
 375  * be greater than the loop iterator of the range at the last
 376  * of the level/2 shared loops, i.e., loop level/2 - 1.
 377  */
 378 static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level)
 379 {
 380         struct isl_basic_map *bmap;
 381
 382         if (level % 2)
 383                 bmap = isl_basic_map_equal(dim, level/2);
 384         else
 385                 bmap = isl_basic_map_more_at(dim, level/2 - 1);
 386
 387         return isl_map_from_basic_map(bmap);
 388 }
 389
 390 /* Check if the user has set acc->restrict_sources and if so
 391  * intersect the range of "dep" with the result of a call to this function.
 392  *
 393  * Since the user expects a mapping from sink iterations to source iterations,
 394  * whereas the domain of "dep" is a wrapped map, mapping sink iterations
 395  * to accessed array elements, we first need to project out the accessed
 396  * sink array elements by applying acc->domain_map.
 397  */
 398 static __isl_give isl_map *restrict_sources(__isl_take isl_map *dep,
 399         struct isl_access_info *acc, int source)
 400 {
 401         isl_map *source_map;
 402         isl_set *param;
 403
 404         if (!acc->restrict_sources)
 405                 return dep;
 406
 407         source_map = isl_map_copy(dep);
 408         source_map = isl_map_apply_domain(source_map,
 409                                             isl_map_copy(acc->domain_map));
 410         param = acc->restrict_sources(source_map, acc->sink.data,
 411                                     acc->source[source].data);
 412         dep = isl_map_intersect_range(dep, param);
 413         return dep;
 414 }
 415
 416 /* Compute the last iteration of must source j that precedes the sink
 417  * at the given level for sink iterations in set_C.
 418  * The subset of set_C for which no such iteration can be found is returned
 419  * in *empty.
 420  */
 421 static struct isl_map *last_source(struct isl_access_info *acc,
 422                                     struct isl_set *set_C,
 423                                     int j, int level, struct isl_set **empty)
 424 {
 425         struct isl_map *read_map;
 426         struct isl_map *write_map;
 427         struct isl_map *dep_map;
 428         struct isl_map *after;
 429         struct isl_map *result;
 430
 431         read_map = isl_map_copy(acc->sink.map);
 432         write_map = isl_map_copy(acc->source[j].map);
 433         write_map = isl_map_reverse(write_map);
 434         dep_map = isl_map_apply_range(read_map, write_map);
 435         after = after_at_level(isl_map_get_space(dep_map), level);
 436         dep_map = isl_map_intersect(dep_map, after);
 437         dep_map = restrict_sources(dep_map, acc, j);
 438         result = isl_map_partial_lexmax(dep_map, set_C, empty);
 439         result = isl_map_reverse(result);
 440
 441         return result;
 442 }
 443
 444 /* For a given mapping between iterations of must source j and iterations
 445  * of the sink, compute the last iteration of must source k preceding
 446  * the sink at level before_level for any of the sink iterations,
 447  * but following the corresponding iteration of must source j at level
 448  * after_level.
 449  */
 450 static struct isl_map *last_later_source(struct isl_access_info *acc,
 451                                          struct isl_map *old_map,
 452                                          int j, int before_level,
 453                                          int k, int after_level,
 454                                          struct isl_set **empty)
 455 {
 456         isl_space *dim;
 457         struct isl_set *set_C;
 458         struct isl_map *read_map;
 459         struct isl_map *write_map;
 460         struct isl_map *dep_map;
 461         struct isl_map *after_write;
 462         struct isl_map *before_read;
 463         struct isl_map *result;
 464
 465         set_C = isl_map_range(isl_map_copy(old_map));
 466         read_map = isl_map_copy(acc->sink.map);
 467         write_map = isl_map_copy(acc->source[k].map);
 468
 469         write_map = isl_map_reverse(write_map);
 470         dep_map = isl_map_apply_range(read_map, write_map);
 471         dim = space_align_and_join(isl_map_get_space(acc->source[k].map),
 472                     isl_space_reverse(isl_map_get_space(acc->source[j].map)));
 473         after_write = after_at_level(dim, after_level);
 474         after_write = isl_map_apply_range(after_write, old_map);
 475         after_write = isl_map_reverse(after_write);
 476         dep_map = isl_map_intersect(dep_map, after_write);
 477         before_read = after_at_level(isl_map_get_space(dep_map), before_level);
 478         dep_map = isl_map_intersect(dep_map, before_read);
 479         dep_map = restrict_sources(dep_map, acc, k);
 480         result = isl_map_partial_lexmax(dep_map, set_C, empty);
 481         result = isl_map_reverse(result);
 482
 483         return result;
 484 }
 485
 486 /* Given a shared_level between two accesses, return 1 if the
 487  * the first can precede the second at the requested target_level.
 488  * If the target level is odd, i.e., refers to a statement level
 489  * dimension, then first needs to precede second at the requested
 490  * level, i.e., shared_level must be equal to target_level.
 491  * If the target level is odd, then the two loops should share
 492  * at least the requested number of outer loops.
 493  */
 494 static int can_precede_at_level(int shared_level, int target_level)
 495 {
 496         if (shared_level < target_level)
 497                 return 0;
 498         if ((target_level % 2) && shared_level > target_level)
 499                 return 0;
 500         return 1;
 501 }
 502
 503 /* Given a possible flow dependence temp_rel[j] between source j and the sink
 504  * at level sink_level, remove those elements for which
 505  * there is an iteration of another source k < j that is closer to the sink.
 506  * The flow dependences temp_rel[k] are updated with the improved sources.
 507  * Any improved source needs to precede the sink at the same level
 508  * and needs to follow source j at the same or a deeper level.
 509  * The lower this level, the later the execution date of source k.
 510  * We therefore consider lower levels first.
 511  *
 512  * If temp_rel[j] is empty, then there can be no improvement and
 513  * we return immediately.
 514  */
 515 static int intermediate_sources(__isl_keep isl_access_info *acc,
 516         struct isl_map **temp_rel, int j, int sink_level)
 517 {
 518         int k, level;
 519         int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1;
 520
 521         if (isl_map_plain_is_empty(temp_rel[j]))
 522                 return 0;
 523
 524         for (k = j - 1; k >= 0; --k) {
 525                 int plevel, plevel2;
 526                 plevel = acc->level_before(acc->source[k].data, acc->sink.data);
 527                 if (!can_precede_at_level(plevel, sink_level))
 528                         continue;
 529
 530                 plevel2 = acc->level_before(acc->source[j].data,
 531                                                 acc->source[k].data);
 532
 533                 for (level = sink_level; level <= depth; ++level) {
 534                         struct isl_map *T;
 535                         struct isl_set *trest;
 536                         struct isl_map *copy;
 537
 538                         if (!can_precede_at_level(plevel2, level))
 539                                 continue;
 540
 541                         copy = isl_map_copy(temp_rel[j]);
 542                         T = last_later_source(acc, copy, j, sink_level, k,
 543                                               level, &trest);
 544                         if (isl_map_plain_is_empty(T)) {
 545                                 isl_set_free(trest);
 546                                 isl_map_free(T);
 547                                 continue;
 548                         }
 549                         temp_rel[j] = isl_map_intersect_range(temp_rel[j], trest);
 550                         temp_rel[k] = isl_map_union_disjoint(temp_rel[k], T);
 551                 }
 552         }
 553
 554         return 0;
 555 }
 556
 557 /* Compute all iterations of may source j that precedes the sink at the given
 558  * level for sink iterations in set_C.
 559  */
 560 static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc,
 561                                     __isl_take isl_set *set_C, int j, int level)
 562 {
 563         isl_map *read_map;
 564         isl_map *write_map;
 565         isl_map *dep_map;
 566         isl_map *after;
 567
 568         read_map = isl_map_copy(acc->sink.map);
 569         read_map = isl_map_intersect_domain(read_map, set_C);
 570         write_map = isl_map_copy(acc->source[acc->n_must + j].map);
 571         write_map = isl_map_reverse(write_map);
 572         dep_map = isl_map_apply_range(read_map, write_map);
 573         after = after_at_level(isl_map_get_space(dep_map), level);
 574         dep_map = isl_map_intersect(dep_map, after);
 575
 576         return isl_map_reverse(dep_map);
 577 }
 578
 579 /* For a given mapping between iterations of must source k and iterations
 580  * of the sink, compute the all iteration of may source j preceding
 581  * the sink at level before_level for any of the sink iterations,
 582  * but following the corresponding iteration of must source k at level
 583  * after_level.
 584  */
 585 static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc,
 586         __isl_keep isl_map *old_map,
 587         int j, int before_level, int k, int after_level)
 588 {
 589         isl_space *dim;
 590         isl_set *set_C;
 591         isl_map *read_map;
 592         isl_map *write_map;
 593         isl_map *dep_map;
 594         isl_map *after_write;
 595         isl_map *before_read;
 596
 597         set_C = isl_map_range(isl_map_copy(old_map));
 598         read_map = isl_map_copy(acc->sink.map);
 599         read_map = isl_map_intersect_domain(read_map, set_C);
 600         write_map = isl_map_copy(acc->source[acc->n_must + j].map);
 601
 602         write_map = isl_map_reverse(write_map);
 603         dep_map = isl_map_apply_range(read_map, write_map);
 604         dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map),
 605                     isl_space_reverse(isl_map_get_space(acc->source[k].map)));
 606         after_write = after_at_level(dim, after_level);
 607         after_write = isl_map_apply_range(after_write, old_map);
 608         after_write = isl_map_reverse(after_write);
 609         dep_map = isl_map_intersect(dep_map, after_write);
 610         before_read = after_at_level(isl_map_get_space(dep_map), before_level);
 611         dep_map = isl_map_intersect(dep_map, before_read);
 612         return isl_map_reverse(dep_map);
 613 }
 614
 615 /* Given the must and may dependence relations for the must accesses
 616  * for level sink_level, check if there are any accesses of may access j
 617  * that occur in between and return their union.
 618  * If some of these accesses are intermediate with respect to
 619  * (previously thought to be) must dependences, then these
 620  * must dependences are turned into may dependences.
 621  */
 622 static __isl_give isl_map *all_intermediate_sources(
 623         __isl_keep isl_access_info *acc, __isl_take isl_map *map,
 624         struct isl_map **must_rel, struct isl_map **may_rel,
 625         int j, int sink_level)
 626 {
 627         int k, level;
 628         int depth = 2 * isl_map_dim(acc->source[acc->n_must + j].map,
 629                                         isl_dim_in) + 1;
 630
 631         for (k = 0; k < acc->n_must; ++k) {
 632                 int plevel;
 633
 634                 if (isl_map_plain_is_empty(may_rel[k]) &&
 635                     isl_map_plain_is_empty(must_rel[k]))
 636                         continue;
 637
 638                 plevel = acc->level_before(acc->source[k].data,
 639                                         acc->source[acc->n_must + j].data);
 640
 641                 for (level = sink_level; level <= depth; ++level) {
 642                         isl_map *T;
 643                         isl_map *copy;
 644                         isl_set *ran;
 645
 646                         if (!can_precede_at_level(plevel, level))
 647                                 continue;
 648
 649                         copy = isl_map_copy(may_rel[k]);
 650                         T = all_later_sources(acc, copy, j, sink_level, k, level);
 651                         map = isl_map_union(map, T);
 652
 653                         copy = isl_map_copy(must_rel[k]);
 654                         T = all_later_sources(acc, copy, j, sink_level, k, level);
 655                         ran = isl_map_range(isl_map_copy(T));
 656                         map = isl_map_union(map, T);
 657                         may_rel[k] = isl_map_union_disjoint(may_rel[k],
 658                             isl_map_intersect_range(isl_map_copy(must_rel[k]),
 659                                                     isl_set_copy(ran)));
 660                         T = isl_map_from_domain_and_range(
 661                             isl_set_universe(
 662                                 isl_space_domain(isl_map_get_space(must_rel[k]))),
 663                             ran);
 664                         must_rel[k] = isl_map_subtract(must_rel[k], T);
 665                 }
 666         }
 667
 668         return map;
 669 }
 670
 671 /* Compute dependences for the case where all accesses are "may"
 672  * accesses, which boils down to computing memory based dependences.
 673  * The generic algorithm would also work in this case, but it would
 674  * be overkill to use it.
 675  */
 676 static __isl_give isl_flow *compute_mem_based_dependences(
 677         __isl_keep isl_access_info *acc)
 678 {
 679         int i;
 680         isl_set *mustdo;
 681         isl_set *maydo;
 682         isl_flow *res;
 683
 684         res = isl_flow_alloc(acc);
 685         if (!res)
 686                 return NULL;
 687
 688         mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
 689         maydo = isl_set_copy(mustdo);
 690
 691         for (i = 0; i < acc->n_may; ++i) {
 692                 int plevel;
 693                 int is_before;
 694                 isl_space *dim;
 695                 isl_map *before;
 696                 isl_map *dep;
 697
 698                 plevel = acc->level_before(acc->source[i].data, acc->sink.data);
 699                 is_before = plevel & 1;
 700                 plevel >>= 1;
 701
 702                 dim = isl_map_get_space(res->dep[i].map);
 703                 if (is_before)
 704                         before = isl_map_lex_le_first(dim, plevel);
 705                 else
 706                         before = isl_map_lex_lt_first(dim, plevel);
 707                 dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),
 708                         isl_map_reverse(isl_map_copy(acc->sink.map)));
 709                 dep = isl_map_intersect(dep, before);
 710                 mustdo = isl_set_subtract(mustdo,
 711                                             isl_map_range(isl_map_copy(dep)));
 712                 res->dep[i].map = isl_map_union(res->dep[i].map, dep);
 713         }
 714
 715         res->may_no_source = isl_set_subtract(maydo, isl_set_copy(mustdo));
 716         res->must_no_source = mustdo;
 717
 718         return res;
 719 }
 720
 721 /* Compute dependences for the case where there is at least one
 722  * "must" access.
 723  *
 724  * The core algorithm considers all levels in which a source may precede
 725  * the sink, where a level may either be a statement level or a loop level.
 726  * The outermost statement level is 1, the first loop level is 2, etc...
 727  * The algorithm basically does the following:
 728  * for all levels l of the read access from innermost to outermost
 729  *      for all sources w that may precede the sink access at that level
 730  *          compute the last iteration of the source that precedes the sink access
 731  *                                          at that level
 732  *          add result to possible last accesses at level l of source w
 733  *          for all sources w2 that we haven't considered yet at this level that may
 734  *                                          also precede the sink access
 735  *              for all levels l2 of w from l to innermost
 736  *                  for all possible last accesses dep of w at l
 737  *                      compute last iteration of w2 between the source and sink
 738  *                                                              of dep
 739  *                      add result to possible last accesses at level l of write w2
 740  *                      and replace possible last accesses dep by the remainder
 741  *
 742  *
 743  * The above algorithm is applied to the must access.  During the course
 744  * of the algorithm, we keep track of sink iterations that still
 745  * need to be considered.  These iterations are split into those that
 746  * haven't been matched to any source access (mustdo) and those that have only
 747  * been matched to may accesses (maydo).
 748  * At the end of each level, we also consider the may accesses.
 749  * In particular, we consider may accesses that precede the remaining
 750  * sink iterations, moving elements from mustdo to maydo when appropriate,
 751  * and may accesses that occur between a must source and a sink of any
 752  * dependences found at the current level, turning must dependences into
 753  * may dependences when appropriate.
 754  *
 755  */
 756 static __isl_give isl_flow *compute_val_based_dependences(
 757         __isl_keep isl_access_info *acc)
 758 {
 759         isl_ctx *ctx;
 760         isl_flow *res;
 761         isl_set *mustdo = NULL;
 762         isl_set *maydo = NULL;
 763         int level, j;
 764         int depth;
 765         isl_map **must_rel = NULL;
 766         isl_map **may_rel = NULL;
 767
 768         if (!acc)
 769                 return NULL;
 770
 771         res = isl_flow_alloc(acc);
 772         if (!res)
 773                 goto error;
 774         ctx = isl_map_get_ctx(acc->sink.map);
 775
 776         depth = 2 * isl_map_dim(acc->sink.map, isl_dim_in) + 1;
 777         mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
 778         maydo = isl_set_empty_like(mustdo);
 779         if (!mustdo || !maydo)
 780                 goto error;
 781         if (isl_set_plain_is_empty(mustdo))
 782                 goto done;
 783
 784         must_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
 785         may_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
 786         if (!must_rel || !may_rel)
 787                 goto error;
 788
 789         for (level = depth; level >= 1; --level) {
 790                 for (j = acc->n_must-1; j >=0; --j) {
 791                         must_rel[j] = isl_map_empty_like(res->dep[j].map);
 792                         may_rel[j] = isl_map_copy(must_rel[j]);
 793                 }
 794
 795                 for (j = acc->n_must - 1; j >= 0; --j) {
 796                         struct isl_map *T;
 797                         struct isl_set *rest;
 798                         int plevel;
 799
 800                         plevel = acc->level_before(acc->source[j].data,
 801                                                      acc->sink.data);
 802                         if (!can_precede_at_level(plevel, level))
 803                                 continue;
 804
 805                         T = last_source(acc, mustdo, j, level, &rest);
 806                         must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
 807                         mustdo = rest;
 808
 809                         intermediate_sources(acc, must_rel, j, level);
 810
 811                         T = last_source(acc, maydo, j, level, &rest);
 812                         may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
 813                         maydo = rest;
 814
 815                         intermediate_sources(acc, may_rel, j, level);
 816
 817                         if (isl_set_plain_is_empty(mustdo) &&
 818                             isl_set_plain_is_empty(maydo))
 819                                 break;
 820                 }
 821                 for (j = j - 1; j >= 0; --j) {
 822                         int plevel;
 823
 824                         plevel = acc->level_before(acc->source[j].data,
 825                                                      acc->sink.data);
 826                         if (!can_precede_at_level(plevel, level))
 827                                 continue;
 828
 829                         intermediate_sources(acc, must_rel, j, level);
 830                         intermediate_sources(acc, may_rel, j, level);
 831                 }
 832
 833                 for (j = 0; j < acc->n_may; ++j) {
 834                         int plevel;
 835                         isl_map *T;
 836                         isl_set *ran;
 837
 838                         plevel = acc->level_before(acc->source[acc->n_must + j].data,
 839                                                      acc->sink.data);
 840                         if (!can_precede_at_level(plevel, level))
 841                                 continue;
 842
 843                         T = all_sources(acc, isl_set_copy(maydo), j, level);
 844                         res->dep[2 * acc->n_must + j].map =
 845                             isl_map_union(res->dep[2 * acc->n_must + j].map, T);
 846                         T = all_sources(acc, isl_set_copy(mustdo), j, level);
 847                         ran = isl_map_range(isl_map_copy(T));
 848                         res->dep[2 * acc->n_must + j].map =
 849                             isl_map_union(res->dep[2 * acc->n_must + j].map, T);
 850                         mustdo = isl_set_subtract(mustdo, isl_set_copy(ran));
 851                         maydo = isl_set_union_disjoint(maydo, ran);
 852
 853                         T = res->dep[2 * acc->n_must + j].map;
 854                         T = all_intermediate_sources(acc, T, must_rel, may_rel,
 855                                                         j, level);
 856                         res->dep[2 * acc->n_must + j].map = T;
 857                 }
 858
 859                 for (j = acc->n_must - 1; j >= 0; --j) {
 860                         res->dep[2 * j].map =
 861                                 isl_map_union_disjoint(res->dep[2 * j].map,
 862                                                              must_rel[j]);
 863                         res->dep[2 * j + 1].map =
 864                                 isl_map_union_disjoint(res->dep[2 * j + 1].map,
 865                                                              may_rel[j]);
 866                 }
 867
 868                 if (isl_set_plain_is_empty(mustdo) &&
 869                     isl_set_plain_is_empty(maydo))
 870                         break;
 871         }
 872
 873         free(must_rel);
 874         free(may_rel);
 875 done:
 876         res->must_no_source = mustdo;
 877         res->may_no_source = maydo;
 878         return res;
 879 error:
 880         isl_flow_free(res);
 881         isl_set_free(mustdo);
 882         isl_set_free(maydo);
 883         free(must_rel);
 884         free(may_rel);
 885         return NULL;
 886 }
 887
 888 /* Given a "sink" access, a list of n "source" accesses,
 889  * compute for each iteration of the sink access
 890  * and for each element accessed by that iteration,
 891  * the source access in the list that last accessed the
 892  * element accessed by the sink access before this sink access.
 893  * Each access is given as a map from the loop iterators
 894  * to the array indices.
 895  * The result is a list of n relations between source and sink
 896  * iterations and a subset of the domain of the sink access,
 897  * corresponding to those iterations that access an element
 898  * not previously accessed.
 899  *
 900  * To deal with multi-valued sink access relations, the sink iteration
 901  * domain is first extended with dimensions that correspond to the data
 902  * space.  After the computation is finished, these extra dimensions are
 903  * projected out again.
 904  */
 905 __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc)
 906 {
 907         int j;
 908         struct isl_flow *res = NULL;
 909
 910         if (!acc)
 911                 return NULL;
 912
 913         acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map));
 914         acc->sink.map = isl_map_range_map(acc->sink.map);
 915         if (!acc->sink.map)
 916                 goto error;
 917
 918         if (acc->n_must == 0)
 919                 res = compute_mem_based_dependences(acc);
 920         else {
 921                 acc = isl_access_info_sort_sources(acc);
 922                 res = compute_val_based_dependences(acc);
 923         }
 924         if (!res)
 925                 goto error;
 926
 927         for (j = 0; j < res->n_source; ++j) {
 928                 res->dep[j].map = isl_map_apply_range(res->dep[j].map,
 929                                         isl_map_copy(acc->domain_map));
 930                 if (!res->dep[j].map)
 931                         goto error;
 932         }
 933         if (!res->must_no_source || !res->may_no_source)
 934                 goto error;
 935
 936         isl_access_info_free(acc);
 937         return res;
 938 error:
 939         isl_access_info_free(acc);
 940         isl_flow_free(res);
 941         return NULL;
 942 }
 943
 944
 945 /* Keep track of some information about a schedule for a given
 946  * access.  In particular, keep track of which dimensions
 947  * have a constant value and of the actual constant values.
 948  */
 949 struct isl_sched_info {
 950         int *is_cst;
 951         isl_vec *cst;
 952 };
 953
 954 static void sched_info_free(__isl_take struct isl_sched_info *info)
 955 {
 956         if (!info)
 957                 return;
 958         isl_vec_free(info->cst);
 959         free(info->is_cst);
 960         free(info);
 961 }
 962
 963 /* Extract information on the constant dimensions of the schedule
 964  * for a given access.  The "map" is of the form
 965  *
 966  *      [S -> D] -> A
 967  *
 968  * with S the schedule domain, D the iteration domain and A the data domain.
 969  */
 970 static __isl_give struct isl_sched_info *sched_info_alloc(
 971         __isl_keep isl_map *map)
 972 {
 973         isl_ctx *ctx;
 974         isl_space *dim;
 975         struct isl_sched_info *info;
 976         int i, n;
 977
 978         if (!map)
 979                 return NULL;
 980
 981         dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
 982         if (!dim)
 983                 return NULL;
 984         n = isl_space_dim(dim, isl_dim_in);
 985         isl_space_free(dim);
 986
 987         ctx = isl_map_get_ctx(map);
 988         info = isl_alloc_type(ctx, struct isl_sched_info);
 989         if (!info)
 990                 return NULL;
 991         info->is_cst = isl_alloc_array(ctx, int, n);
 992         info->cst = isl_vec_alloc(ctx, n);
 993         if (!info->is_cst || !info->cst)
 994                 goto error;
 995
 996         for (i = 0; i < n; ++i)
 997                 info->is_cst[i] = isl_map_plain_is_fixed(map, isl_dim_in, i,
 998                                                         &info->cst->el[i]);
 999
1000         return info;
1001 error:
1002         sched_info_free(info);
1003         return NULL;
1004 }
1005
1006 struct isl_compute_flow_data {
1007         isl_union_map *must_source;
1008         isl_union_map *may_source;
1009         isl_union_map *must_dep;
1010         isl_union_map *may_dep;
1011         isl_union_map *must_no_source;
1012         isl_union_map *may_no_source;
1013
1014         int count;
1015         int must;
1016         isl_space *dim;
1017         struct isl_sched_info *sink_info;
1018         struct isl_sched_info **source_info;
1019         isl_access_info *accesses;
1020 };
1021
1022 static int count_matching_array(__isl_take isl_map *map, void *user)
1023 {
1024         int eq;
1025         isl_space *dim;
1026         struct isl_compute_flow_data *data;
1027
1028         data = (struct isl_compute_flow_data *)user;
1029
1030         dim = isl_space_range(isl_map_get_space(map));
1031
1032         eq = isl_space_is_equal(dim, data->dim);
1033
1034         isl_space_free(dim);
1035         isl_map_free(map);
1036
1037         if (eq < 0)
1038                 return -1;
1039         if (eq)
1040                 data->count++;
1041
1042         return 0;
1043 }
1044
1045 static int collect_matching_array(__isl_take isl_map *map, void *user)
1046 {
1047         int eq;
1048         isl_space *dim;
1049         struct isl_sched_info *info;
1050         struct isl_compute_flow_data *data;
1051
1052         data = (struct isl_compute_flow_data *)user;
1053
1054         dim = isl_space_range(isl_map_get_space(map));
1055
1056         eq = isl_space_is_equal(dim, data->dim);
1057
1058         isl_space_free(dim);
1059
1060         if (eq < 0)
1061                 goto error;
1062         if (!eq) {
1063                 isl_map_free(map);
1064                 return 0;
1065         }
1066
1067         info = sched_info_alloc(map);
1068         data->source_info[data->count] = info;
1069
1070         data->accesses = isl_access_info_add_source(data->accesses,
1071                                                     map, data->must, info);
1072
1073         data->count++;
1074
1075         return 0;
1076 error:
1077         isl_map_free(map);
1078         return -1;
1079 }
1080
1081 /* Determine the shared nesting level and the "textual order" of
1082  * the given accesses.
1083  *
1084  * We first determine the minimal schedule dimension for both accesses.
1085  *
1086  * If among those dimensions, we can find one where both have a fixed
1087  * value and if moreover those values are different, then the previous
1088  * dimension is the last shared nesting level and the textual order
1089  * is determined based on the order of the fixed values.
1090  * If no such fixed values can be found, then we set the shared
1091  * nesting level to the minimal schedule dimension, with no textual ordering.
1092  */
1093 static int before(void *first, void *second)
1094 {
1095         struct isl_sched_info *info1 = first;
1096         struct isl_sched_info *info2 = second;
1097         int n1, n2;
1098         int i;
1099
1100         n1 = info1->cst->size;
1101         n2 = info2->cst->size;
1102
1103         if (n2 < n1)
1104                 n1 = n2;
1105
1106         for (i = 0; i < n1; ++i) {
1107                 if (!info1->is_cst[i])
1108                         continue;
1109                 if (!info2->is_cst[i])
1110                         continue;
1111                 if (isl_int_eq(info1->cst->el[i], info2->cst->el[i]))
1112                         continue;
1113                 return 2 * i + isl_int_lt(info1->cst->el[i], info2->cst->el[i]);
1114         }
1115
1116         return 2 * n1;
1117 }
1118
1119 /* Given a sink access, look for all the source accesses that access
1120  * the same array and perform dataflow analysis on them using
1121  * isl_access_info_compute_flow.
1122  */
1123 static int compute_flow(__isl_take isl_map *map, void *user)
1124 {
1125         int i;
1126         isl_ctx *ctx;
1127         struct isl_compute_flow_data *data;
1128         isl_flow *flow;
1129
1130         data = (struct isl_compute_flow_data *)user;
1131
1132         ctx = isl_map_get_ctx(map);
1133
1134         data->accesses = NULL;
1135         data->sink_info = NULL;
1136         data->source_info = NULL;
1137         data->count = 0;
1138         data->dim = isl_space_range(isl_map_get_space(map));
1139
1140         if (isl_union_map_foreach_map(data->must_source,
1141                                         &count_matching_array, data) < 0)
1142                 goto error;
1143         if (isl_union_map_foreach_map(data->may_source,
1144                                         &count_matching_array, data) < 0)
1145                 goto error;
1146
1147         data->sink_info = sched_info_alloc(map);
1148         data->source_info = isl_calloc_array(ctx, struct isl_sched_info *,
1149                                              data->count);
1150
1151         data->accesses = isl_access_info_alloc(isl_map_copy(map),
1152                                 data->sink_info, &before, data->count);
1153         if (!data->sink_info || !data->source_info || !data->accesses)
1154                 goto error;
1155         data->count = 0;
1156         data->must = 1;
1157         if (isl_union_map_foreach_map(data->must_source,
1158                                         &collect_matching_array, data) < 0)
1159                 goto error;
1160         data->must = 0;
1161         if (isl_union_map_foreach_map(data->may_source,
1162                                         &collect_matching_array, data) < 0)
1163                 goto error;
1164
1165         flow = isl_access_info_compute_flow(data->accesses);
1166         data->accesses = NULL;
1167
1168         if (!flow)
1169                 goto error;
1170
1171         data->must_no_source = isl_union_map_union(data->must_no_source,
1172                     isl_union_map_from_map(isl_flow_get_no_source(flow, 1)));
1173         data->may_no_source = isl_union_map_union(data->may_no_source,
1174                     isl_union_map_from_map(isl_flow_get_no_source(flow, 0)));
1175
1176         for (i = 0; i < flow->n_source; ++i) {
1177                 isl_union_map *dep;
1178                 dep = isl_union_map_from_map(isl_map_copy(flow->dep[i].map));
1179                 if (flow->dep[i].must)
1180                         data->must_dep = isl_union_map_union(data->must_dep, dep);
1181                 else
1182                         data->may_dep = isl_union_map_union(data->may_dep, dep);
1183         }
1184
1185         isl_flow_free(flow);
1186
1187         sched_info_free(data->sink_info);
1188         if (data->source_info) {
1189                 for (i = 0; i < data->count; ++i)
1190                         sched_info_free(data->source_info[i]);
1191                 free(data->source_info);
1192         }
1193         isl_space_free(data->dim);
1194         isl_map_free(map);
1195
1196         return 0;
1197 error:
1198         isl_access_info_free(data->accesses);
1199         sched_info_free(data->sink_info);
1200         if (data->source_info) {
1201                 for (i = 0; i < data->count; ++i)
1202                         sched_info_free(data->source_info[i]);
1203                 free(data->source_info);
1204         }
1205         isl_space_free(data->dim);
1206         isl_map_free(map);
1207
1208         return -1;
1209 }
1210
1211 /* Given a collection of "sink" and "source" accesses,
1212  * compute for each iteration of a sink access
1213  * and for each element accessed by that iteration,
1214  * the source access in the list that last accessed the
1215  * element accessed by the sink access before this sink access.
1216  * Each access is given as a map from the loop iterators
1217  * to the array indices.
1218  * The result is a relations between source and sink
1219  * iterations and a subset of the domain of the sink accesses,
1220  * corresponding to those iterations that access an element
1221  * not previously accessed.
1222  *
1223  * We first prepend the schedule dimensions to the domain
1224  * of the accesses so that we can easily compare their relative order.
1225  * Then we consider each sink access individually in compute_flow.
1226  */
1227 int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
1228         __isl_take isl_union_map *must_source,
1229         __isl_take isl_union_map *may_source,
1230         __isl_take isl_union_map *schedule,
1231         __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep,
1232         __isl_give isl_union_map **must_no_source,
1233         __isl_give isl_union_map **may_no_source)
1234 {
1235         isl_space *dim;
1236         isl_union_map *range_map = NULL;
1237         struct isl_compute_flow_data data;
1238
1239         sink = isl_union_map_align_params(sink,
1240                                             isl_union_map_get_space(must_source));
1241         sink = isl_union_map_align_params(sink,
1242                                             isl_union_map_get_space(may_source));
1243         sink = isl_union_map_align_params(sink,
1244                                             isl_union_map_get_space(schedule));
1245         dim = isl_union_map_get_space(sink);
1246         must_source = isl_union_map_align_params(must_source, isl_space_copy(dim));
1247         may_source = isl_union_map_align_params(may_source, isl_space_copy(dim));
1248         schedule = isl_union_map_align_params(schedule, isl_space_copy(dim));
1249
1250         schedule = isl_union_map_reverse(schedule);
1251         range_map = isl_union_map_range_map(schedule);
1252         schedule = isl_union_map_reverse(isl_union_map_copy(range_map));
1253         sink = isl_union_map_apply_domain(sink, isl_union_map_copy(schedule));
1254         must_source = isl_union_map_apply_domain(must_source,
1255                                                 isl_union_map_copy(schedule));
1256         may_source = isl_union_map_apply_domain(may_source, schedule);
1257
1258         data.must_source = must_source;
1259         data.may_source = may_source;
1260         data.must_dep = must_dep ?
1261                 isl_union_map_empty(isl_space_copy(dim)) : NULL;
1262         data.may_dep = may_dep ? isl_union_map_empty(isl_space_copy(dim)) : NULL;
1263         data.must_no_source = must_no_source ?
1264                 isl_union_map_empty(isl_space_copy(dim)) : NULL;
1265         data.may_no_source = may_no_source ?
1266                 isl_union_map_empty(isl_space_copy(dim)) : NULL;
1267
1268         isl_space_free(dim);
1269
1270         if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0)
1271                 goto error;
1272
1273         isl_union_map_free(sink);
1274         isl_union_map_free(must_source);
1275         isl_union_map_free(may_source);
1276
1277         if (must_dep) {
1278                 data.must_dep = isl_union_map_apply_domain(data.must_dep,
1279                                         isl_union_map_copy(range_map));
1280                 data.must_dep = isl_union_map_apply_range(data.must_dep,
1281                                         isl_union_map_copy(range_map));
1282                 *must_dep = data.must_dep;
1283         }
1284         if (may_dep) {
1285                 data.may_dep = isl_union_map_apply_domain(data.may_dep,
1286                                         isl_union_map_copy(range_map));
1287                 data.may_dep = isl_union_map_apply_range(data.may_dep,
1288                                         isl_union_map_copy(range_map));
1289                 *may_dep = data.may_dep;
1290         }
1291         if (must_no_source) {
1292                 data.must_no_source = isl_union_map_apply_domain(
1293                         data.must_no_source, isl_union_map_copy(range_map));
1294                 *must_no_source = data.must_no_source;
1295         }
1296         if (may_no_source) {
1297                 data.may_no_source = isl_union_map_apply_domain(
1298                         data.may_no_source, isl_union_map_copy(range_map));
1299                 *may_no_source = data.may_no_source;
1300         }
1301
1302         isl_union_map_free(range_map);
1303
1304         return 0;
1305 error:
1306         isl_union_map_free(range_map);
1307         isl_union_map_free(sink);
1308         isl_union_map_free(must_source);
1309         isl_union_map_free(may_source);
1310         isl_union_map_free(data.must_dep);
1311         isl_union_map_free(data.may_dep);
1312         isl_union_map_free(data.must_no_source);
1313         isl_union_map_free(data.may_no_source);
1314
1315         if (must_dep)
1316                 *must_dep = NULL;
1317         if (may_dep)
1318                 *may_dep = NULL;
1319         if (must_no_source)
1320                 *must_no_source = NULL;
1321         if (may_no_source)
1322                 *may_no_source = NULL;
1323         return -1;
1324 }