isl_flow.c

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