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