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