ISLTools.cpp 28.3 KB
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870
//===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Tools, utilities, helpers and extensions useful in conjunction with the
// Integer Set Library (isl).
//
//===----------------------------------------------------------------------===//

#include "polly/Support/ISLTools.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <vector>

using namespace polly;

namespace {
/// Create a map that shifts one dimension by an offset.
///
/// Example:
/// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
///   = { [i0, i1] -> [i0, i1 - 1] }
///
/// @param Space  The map space of the result. Must have equal number of in- and
///               out-dimensions.
/// @param Pos    Position to shift.
/// @param Amount Value added to the shifted dimension.
///
/// @return An isl_multi_aff for the map with this shifted dimension.
isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
  auto Identity = isl::multi_aff::identity(Space);
  if (Amount == 0)
    return Identity;
  auto ShiftAff = Identity.get_aff(Pos);
  ShiftAff = ShiftAff.set_constant_si(Amount);
  return Identity.set_aff(Pos, ShiftAff);
}

/// Construct a map that swaps two nested tuples.
///
/// @param FromSpace1 { Space1[] }
/// @param FromSpace2 { Space2[] }
///
/// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
                                     isl::space FromSpace2) {
  // Fast-path on out-of-quota.
  if (!FromSpace1 || !FromSpace2)
    return {};

  assert(FromSpace1.is_set());
  assert(FromSpace2.is_set());

  unsigned Dims1 = FromSpace1.dim(isl::dim::set);
  unsigned Dims2 = FromSpace2.dim(isl::dim::set);

  isl::space FromSpace =
      FromSpace1.map_from_domain_and_range(FromSpace2).wrap();
  isl::space ToSpace = FromSpace2.map_from_domain_and_range(FromSpace1).wrap();
  isl::space MapSpace = FromSpace.map_from_domain_and_range(ToSpace);

  isl::basic_map Result = isl::basic_map::universe(MapSpace);
  for (auto i = Dims1 - Dims1; i < Dims1; i += 1)
    Result = Result.equate(isl::dim::in, i, isl::dim::out, Dims2 + i);
  for (auto i = Dims2 - Dims2; i < Dims2; i += 1) {
    Result = Result.equate(isl::dim::in, Dims1 + i, isl::dim::out, i);
  }

  return Result;
}

/// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
/// an isl_map.
isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
  isl::basic_map BMapResult = makeTupleSwapBasicMap(FromSpace1, FromSpace2);
  return isl::map(BMapResult);
}
} // anonymous namespace

isl::map polly::beforeScatter(isl::map Map, bool Strict) {
  isl::space RangeSpace = Map.get_space().range();
  isl::map ScatterRel =
      Strict ? isl::map::lex_gt(RangeSpace) : isl::map::lex_ge(RangeSpace);
  return Map.apply_range(ScatterRel);
}

isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
  isl::union_map Result = isl::union_map::empty(UMap.get_space());

  for (isl::map Map : UMap.get_map_list()) {
    isl::map After = beforeScatter(Map, Strict);
    Result = Result.add_map(After);
  }

  return Result;
}

isl::map polly::afterScatter(isl::map Map, bool Strict) {
  isl::space RangeSpace = Map.get_space().range();
  isl::map ScatterRel =
      Strict ? isl::map::lex_lt(RangeSpace) : isl::map::lex_le(RangeSpace);
  return Map.apply_range(ScatterRel);
}

isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
  for (isl::map Map : UMap.get_map_list()) {
    isl::map After = afterScatter(Map, Strict);
    Result = Result.add_map(After);
  }
  return Result;
}

isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
                               bool InclTo) {
  isl::map AfterFrom = afterScatter(From, !InclFrom);
  isl::map BeforeTo = beforeScatter(To, !InclTo);

  return AfterFrom.intersect(BeforeTo);
}

isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
                                     bool InclFrom, bool InclTo) {
  isl::union_map AfterFrom = afterScatter(From, !InclFrom);
  isl::union_map BeforeTo = beforeScatter(To, !InclTo);

  return AfterFrom.intersect(BeforeTo);
}

isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
  if (!UMap)
    return nullptr;

  if (isl_union_map_n_map(UMap.get()) == 0)
    return isl::map::empty(ExpectedSpace);

  isl::map Result = isl::map::from_union_map(UMap);
  assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));

  return Result;
}

isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
  if (!USet)
    return nullptr;

  if (isl_union_set_n_set(USet.get()) == 0)
    return isl::set::empty(ExpectedSpace);

  isl::set Result(USet);
  assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));

  return Result;
}

unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
  unsigned Dims = 0;
  for (isl::map Map : Schedule.get_map_list())
    Dims = std::max(Dims, Map.dim(isl::dim::out));
  return Dims;
}

isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
  if (!Schedule)
    return nullptr;
  unsigned Dims = getNumScatterDims(Schedule);
  isl::space ScatterSpace = Schedule.get_space().set_from_params();
  return ScatterSpace.add_dims(isl::dim::set, Dims);
}

isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
                                      bool RestrictDomain) {
  isl::union_map Result = isl::union_map::empty(USet.get_space());
  for (isl::set Set : USet.get_set_list()) {
    isl::map IdentityMap = isl::map::identity(Set.get_space().map_from_set());
    if (RestrictDomain)
      IdentityMap = IdentityMap.intersect_domain(Set);
    Result = Result.add_map(IdentityMap);
  }
  return Result;
}

isl::map polly::reverseDomain(isl::map Map) {
  isl::space DomSpace = Map.get_space().domain().unwrap();
  isl::space Space1 = DomSpace.domain();
  isl::space Space2 = DomSpace.range();
  isl::map Swap = makeTupleSwapMap(Space1, Space2);
  return Map.apply_domain(Swap);
}

isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
  for (isl::map Map : UMap.get_map_list()) {
    auto Reversed = reverseDomain(std::move(Map));
    Result = Result.add_map(Reversed);
  }
  return Result;
}

isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
  int NumDims = Set.dim(isl::dim::set);
  if (Pos < 0)
    Pos = NumDims + Pos;
  assert(Pos < NumDims && "Dimension index must be in range");
  isl::space Space = Set.get_space();
  Space = Space.map_from_domain_and_range(Space);
  isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
  isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
  return Set.apply(TranslatorMap);
}

isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
  isl::union_set Result = isl::union_set::empty(USet.get_space());
  for (isl::set Set : USet.get_set_list()) {
    isl::set Shifted = shiftDim(Set, Pos, Amount);
    Result = Result.add_set(Shifted);
  }
  return Result;
}

isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
  int NumDims = Map.dim(Dim);
  if (Pos < 0)
    Pos = NumDims + Pos;
  assert(Pos < NumDims && "Dimension index must be in range");
  isl::space Space = Map.get_space();
  switch (Dim) {
  case isl::dim::in:
    Space = Space.domain();
    break;
  case isl::dim::out:
    Space = Space.range();
    break;
  default:
    llvm_unreachable("Unsupported value for 'dim'");
  }
  Space = Space.map_from_domain_and_range(Space);
  isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
  isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
  switch (Dim) {
  case isl::dim::in:
    return Map.apply_domain(TranslatorMap);
  case isl::dim::out:
    return Map.apply_range(TranslatorMap);
  default:
    llvm_unreachable("Unsupported value for 'dim'");
  }
}

isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
                               int Amount) {
  isl::union_map Result = isl::union_map::empty(UMap.get_space());

  for (isl::map Map : UMap.get_map_list()) {
    isl::map Shifted = shiftDim(Map, Dim, Pos, Amount);
    Result = Result.add_map(Shifted);
  }
  return Result;
}

void polly::simplify(isl::set &Set) {
  Set = isl::manage(isl_set_compute_divs(Set.copy()));
  Set = Set.detect_equalities();
  Set = Set.coalesce();
}

void polly::simplify(isl::union_set &USet) {
  USet = isl::manage(isl_union_set_compute_divs(USet.copy()));
  USet = USet.detect_equalities();
  USet = USet.coalesce();
}

void polly::simplify(isl::map &Map) {
  Map = isl::manage(isl_map_compute_divs(Map.copy()));
  Map = Map.detect_equalities();
  Map = Map.coalesce();
}

void polly::simplify(isl::union_map &UMap) {
  UMap = isl::manage(isl_union_map_compute_divs(UMap.copy()));
  UMap = UMap.detect_equalities();
  UMap = UMap.coalesce();
}

isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
                                           isl::union_map Writes, bool Reverse,
                                           bool InclPrevDef, bool InclNextDef) {

  // { Scatter[] }
  isl::space ScatterSpace = getScatterSpace(Schedule);

  // { ScatterRead[] -> ScatterWrite[] }
  isl::map Relation;
  if (Reverse)
    Relation = InclPrevDef ? isl::map::lex_lt(ScatterSpace)
                           : isl::map::lex_le(ScatterSpace);
  else
    Relation = InclNextDef ? isl::map::lex_gt(ScatterSpace)
                           : isl::map::lex_ge(ScatterSpace);

  // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
  isl::map RelationMap = Relation.range_map().reverse();

  // { Element[] -> ScatterWrite[] }
  isl::union_map WriteAction = Schedule.apply_domain(Writes);

  // { ScatterWrite[] -> Element[] }
  isl::union_map WriteActionRev = WriteAction.reverse();

  // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
  isl::union_map DefSchedRelation =
      isl::union_map(RelationMap).apply_domain(WriteActionRev);

  // For each element, at every point in time, map to the times of previous
  // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
  isl::union_map ReachableWrites = DefSchedRelation.uncurry();
  if (Reverse)
    ReachableWrites = ReachableWrites.lexmin();
  else
    ReachableWrites = ReachableWrites.lexmax();

  // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
  isl::union_map SelfUse = WriteAction.range_map();

  if (InclPrevDef && InclNextDef) {
    // Add the Def itself to the solution.
    ReachableWrites = ReachableWrites.unite(SelfUse).coalesce();
  } else if (!InclPrevDef && !InclNextDef) {
    // Remove Def itself from the solution.
    ReachableWrites = ReachableWrites.subtract(SelfUse);
  }

  // { [Element[] -> ScatterRead[]] -> Domain[] }
  return ReachableWrites.apply_range(Schedule.reverse());
}

isl::union_map
polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
                          isl::union_map Reads, bool ReadEltInSameInst,
                          bool IncludeLastRead, bool IncludeWrite) {
  // { Element[] -> Scatter[] }
  isl::union_map ReadActions = Schedule.apply_domain(Reads);
  isl::union_map WriteActions = Schedule.apply_domain(Writes);

  // { [Element[] -> DomainWrite[]] -> Scatter[] }
  isl::union_map EltDomWrites =
      Writes.reverse().range_map().apply_range(Schedule);

  // { [Element[] -> Scatter[]] -> DomainWrite[] }
  isl::union_map ReachingOverwrite = computeReachingWrite(
      Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);

  // { [Element[] -> Scatter[]] -> DomainWrite[] }
  isl::union_map ReadsOverwritten =
      ReachingOverwrite.intersect_domain(ReadActions.wrap());

  // { [Element[] -> DomainWrite[]] -> Scatter[] }
  isl::union_map ReadsOverwrittenRotated =
      reverseDomain(ReadsOverwritten).curry().reverse();
  isl::union_map LastOverwrittenRead = ReadsOverwrittenRotated.lexmax();

  // { [Element[] -> DomainWrite[]] -> Scatter[] }
  isl::union_map BetweenLastReadOverwrite = betweenScatter(
      LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);

  // { [Element[] -> Scatter[]] -> DomainWrite[] }
  isl::union_map ReachingOverwriteZone = computeReachingWrite(
      Schedule, Writes, true, IncludeLastRead, IncludeWrite);

  // { [Element[] -> DomainWrite[]] -> Scatter[] }
  isl::union_map ReachingOverwriteRotated =
      reverseDomain(ReachingOverwriteZone).curry().reverse();

  // { [Element[] -> DomainWrite[]] -> Scatter[] }
  isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
      ReadsOverwrittenRotated.domain());

  return BetweenLastReadOverwrite.unite(WritesWithoutReads)
      .domain_factor_domain();
}

isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
                                              bool InclStart, bool InclEnd) {
  if (!InclStart && InclEnd)
    return Zone;

  auto ShiftedZone = shiftDim(Zone, -1, -1);
  if (InclStart && !InclEnd)
    return ShiftedZone;
  else if (!InclStart && !InclEnd)
    return Zone.intersect(ShiftedZone);

  assert(InclStart && InclEnd);
  return Zone.unite(ShiftedZone);
}

isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
                                              bool InclStart, bool InclEnd) {
  if (!InclStart && InclEnd)
    return Zone;

  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
  if (InclStart && !InclEnd)
    return ShiftedZone;
  else if (!InclStart && !InclEnd)
    return Zone.intersect(ShiftedZone);

  assert(InclStart && InclEnd);
  return Zone.unite(ShiftedZone);
}

isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
                                        bool InclStart, bool InclEnd) {
  if (!InclStart && InclEnd)
    return Zone;

  auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
  if (InclStart && !InclEnd)
    return ShiftedZone;
  else if (!InclStart && !InclEnd)
    return Zone.intersect(ShiftedZone);

  assert(InclStart && InclEnd);
  return Zone.unite(ShiftedZone);
}

isl::map polly::distributeDomain(isl::map Map) {
  // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
  // Domain[] -> Range2[] } and combine again. We would loose any relation
  // between Range1[] and Range2[] that is not also a constraint to Domain[].

  isl::space Space = Map.get_space();
  isl::space DomainSpace = Space.domain();
  unsigned DomainDims = DomainSpace.dim(isl::dim::set);
  isl::space RangeSpace = Space.range().unwrap();
  isl::space Range1Space = RangeSpace.domain();
  unsigned Range1Dims = Range1Space.dim(isl::dim::set);
  isl::space Range2Space = RangeSpace.range();
  unsigned Range2Dims = Range2Space.dim(isl::dim::set);

  isl::space OutputSpace =
      DomainSpace.map_from_domain_and_range(Range1Space)
          .wrap()
          .map_from_domain_and_range(
              DomainSpace.map_from_domain_and_range(Range2Space).wrap());

  isl::basic_map Translator = isl::basic_map::universe(
      Space.wrap().map_from_domain_and_range(OutputSpace.wrap()));

  for (unsigned i = 0; i < DomainDims; i += 1) {
    Translator = Translator.equate(isl::dim::in, i, isl::dim::out, i);
    Translator = Translator.equate(isl::dim::in, i, isl::dim::out,
                                   DomainDims + Range1Dims + i);
  }
  for (unsigned i = 0; i < Range1Dims; i += 1)
    Translator = Translator.equate(isl::dim::in, DomainDims + i, isl::dim::out,
                                   DomainDims + i);
  for (unsigned i = 0; i < Range2Dims; i += 1)
    Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i,
                                   isl::dim::out,
                                   DomainDims + Range1Dims + DomainDims + i);

  return Map.wrap().apply(Translator).unwrap();
}

isl::union_map polly::distributeDomain(isl::union_map UMap) {
  isl::union_map Result = isl::union_map::empty(UMap.get_space());
  for (isl::map Map : UMap.get_map_list()) {
    auto Distributed = distributeDomain(Map);
    Result = Result.add_map(Distributed);
  }
  return Result;
}

isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {

  // { Factor[] -> Factor[] }
  isl::union_map Factors = makeIdentityMap(Factor, true);

  return Factors.product(UMap);
}

isl::union_map polly::applyDomainRange(isl::union_map UMap,
                                       isl::union_map Func) {
  // This implementation creates unnecessary cross products of the
  // DomainDomain[] and Func. An alternative implementation could reverse
  // domain+uncurry,apply Func to what now is the domain, then undo the
  // preparing transformation. Another alternative implementation could create a
  // translator map for each piece.

  // { DomainDomain[] }
  isl::union_set DomainDomain = UMap.domain().unwrap().domain();

  // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
  // }
  isl::union_map LifetedFunc = liftDomains(std::move(Func), DomainDomain);

  return UMap.apply_domain(LifetedFunc);
}

isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
  isl::set RangeSet = Range.extract_set(Map.get_space().range());
  return Map.intersect_range(RangeSet);
}

isl::map polly::subtractParams(isl::map Map, isl::set Params) {
  auto MapSpace = Map.get_space();
  auto ParamsMap = isl::map::universe(MapSpace).intersect_params(Params);
  return Map.subtract(ParamsMap);
}

isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
  assert(!Max || !Min); // Cannot return min and max at the same time.
  isl::val Result;
  isl::stat Stat = PwAff.foreach_piece(
      [=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {
        if (Result && Result.is_nan())
          return isl::stat::ok();

        // TODO: If Min/Max, we can also determine a minimum/maximum value if
        // Set is constant-bounded.
        if (!Aff.is_cst()) {
          Result = isl::val::nan(Aff.get_ctx());
          return isl::stat::error();
        }

        isl::val ThisVal = Aff.get_constant_val();
        if (!Result) {
          Result = ThisVal;
          return isl::stat::ok();
        }

        if (Result.eq(ThisVal))
          return isl::stat::ok();

        if (Max && ThisVal.gt(Result)) {
          Result = ThisVal;
          return isl::stat::ok();
        }

        if (Min && ThisVal.lt(Result)) {
          Result = ThisVal;
          return isl::stat::ok();
        }

        // Not compatible
        Result = isl::val::nan(Aff.get_ctx());
        return isl::stat::error();
      });

  if (Stat.is_error())
    return {};

  return Result;
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
static void foreachPoint(const isl::set &Set,
                         const std::function<void(isl::point P)> &F) {
  Set.foreach_point([&](isl::point P) -> isl::stat {
    F(P);
    return isl::stat::ok();
  });
}

static void foreachPoint(isl::basic_set BSet,
                         const std::function<void(isl::point P)> &F) {
  foreachPoint(isl::set(BSet), F);
}

/// Determine the sorting order of the sets @p A and @p B without considering
/// the space structure.
///
/// Ordering is based on the lower bounds of the set's dimensions. First
/// dimensions are considered first.
static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {
  unsigned ALen = A.dim(isl::dim::set);
  unsigned BLen = B.dim(isl::dim::set);
  unsigned Len = std::min(ALen, BLen);

  for (unsigned i = 0; i < Len; i += 1) {
    isl::basic_set ADim =
        A.project_out(isl::dim::param, 0, A.dim(isl::dim::param))
            .project_out(isl::dim::set, i + 1, ALen - i - 1)
            .project_out(isl::dim::set, 0, i);
    isl::basic_set BDim =
        B.project_out(isl::dim::param, 0, B.dim(isl::dim::param))
            .project_out(isl::dim::set, i + 1, BLen - i - 1)
            .project_out(isl::dim::set, 0, i);

    isl::basic_set AHull = isl::set(ADim).convex_hull();
    isl::basic_set BHull = isl::set(BDim).convex_hull();

    bool ALowerBounded =
        bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0));
    bool BLowerBounded =
        bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0));

    int BoundedCompare = BLowerBounded - ALowerBounded;
    if (BoundedCompare != 0)
      return BoundedCompare;

    if (!ALowerBounded || !BLowerBounded)
      continue;

    isl::pw_aff AMin = isl::set(ADim).dim_min(0);
    isl::pw_aff BMin = isl::set(BDim).dim_min(0);

    isl::val AMinVal = polly::getConstant(AMin, false, true);
    isl::val BMinVal = polly::getConstant(BMin, false, true);

    int MinCompare = AMinVal.sub(BMinVal).sgn();
    if (MinCompare != 0)
      return MinCompare;
  }

  // If all the dimensions' lower bounds are equal or incomparable, sort based
  // on the number of dimensions.
  return ALen - BLen;
}

/// Compare the sets @p A and @p B according to their nested space structure.
/// Returns 0 if the structure is considered equal.
/// If @p ConsiderTupleLen is false, the number of dimensions in a tuple are
/// ignored, i.e. a tuple with the same name but different number of dimensions
/// are considered equal.
static int structureCompare(const isl::space &ASpace, const isl::space &BSpace,
                            bool ConsiderTupleLen) {
  int WrappingCompare = bool(ASpace.is_wrapping()) - bool(BSpace.is_wrapping());
  if (WrappingCompare != 0)
    return WrappingCompare;

  if (ASpace.is_wrapping() && BSpace.is_wrapping()) {
    isl::space AMap = ASpace.unwrap();
    isl::space BMap = BSpace.unwrap();

    int FirstResult =
        structureCompare(AMap.domain(), BMap.domain(), ConsiderTupleLen);
    if (FirstResult != 0)
      return FirstResult;

    return structureCompare(AMap.range(), BMap.range(), ConsiderTupleLen);
  }

  std::string AName;
  if (ASpace.has_tuple_name(isl::dim::set))
    AName = ASpace.get_tuple_name(isl::dim::set);

  std::string BName;
  if (BSpace.has_tuple_name(isl::dim::set))
    BName = BSpace.get_tuple_name(isl::dim::set);

  int NameCompare = AName.compare(BName);
  if (NameCompare != 0)
    return NameCompare;

  if (ConsiderTupleLen) {
    int LenCompare = BSpace.dim(isl::dim::set) - ASpace.dim(isl::dim::set);
    if (LenCompare != 0)
      return LenCompare;
  }

  return 0;
}

/// Compare the sets @p A and @p B according to their nested space structure. If
/// the structure is the same, sort using the dimension lower bounds.
/// Returns an std::sort compatible bool.
static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) {
  isl::space ASpace = A.get_space();
  isl::space BSpace = B.get_space();

  // Ignoring number of dimensions first ensures that structures with same tuple
  // names, but different number of dimensions are still sorted close together.
  int TupleNestingCompare = structureCompare(ASpace, BSpace, false);
  if (TupleNestingCompare != 0)
    return TupleNestingCompare < 0;

  int TupleCompare = structureCompare(ASpace, BSpace, true);
  if (TupleCompare != 0)
    return TupleCompare < 0;

  return flatCompare(A, B) < 0;
}

/// Print a string representation of @p USet to @p OS.
///
/// The pieces of @p USet are printed in a sorted order. Spaces with equal or
/// similar nesting structure are printed together. Compared to isl's own
/// printing function the uses the structure itself as base of the sorting, not
/// a hash of it. It ensures that e.g. maps spaces with same domain structure
/// are printed together. Set pieces with same structure are printed in order of
/// their lower bounds.
///
/// @param USet     Polyhedra to print.
/// @param OS       Target stream.
/// @param Simplify Whether to simplify the polyhedron before printing.
/// @param IsMap    Whether @p USet is a wrapped map. If true, sets are
///                 unwrapped before printing to again appear as a map.
static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS,
                                 bool Simplify, bool IsMap) {
  if (!USet) {
    OS << "<null>\n";
    return;
  }

  if (Simplify)
    simplify(USet);

  // Get all the polyhedra.
  std::vector<isl::basic_set> BSets;

  for (isl::set Set : USet.get_set_list()) {
    for (isl::basic_set BSet : Set.get_basic_set_list()) {
      BSets.push_back(BSet);
    }
  }

  if (BSets.empty()) {
    OS << "{\n}\n";
    return;
  }

  // Sort the polyhedra.
  llvm::sort(BSets, orderComparer);

  // Print the polyhedra.
  bool First = true;
  for (const isl::basic_set &BSet : BSets) {
    std::string Str;
    if (IsMap)
      Str = isl::map(BSet.unwrap()).to_str();
    else
      Str = isl::set(BSet).to_str();
    size_t OpenPos = Str.find_first_of('{');
    assert(OpenPos != std::string::npos);
    size_t ClosePos = Str.find_last_of('}');
    assert(ClosePos != std::string::npos);

    if (First)
      OS << llvm::StringRef(Str).substr(0, OpenPos + 1) << "\n ";
    else
      OS << ";\n ";

    OS << llvm::StringRef(Str).substr(OpenPos + 1, ClosePos - OpenPos - 2);
    First = false;
  }
  assert(!First);
  OS << "\n}\n";
}

static void recursiveExpand(isl::basic_set BSet, int Dim, isl::set &Expanded) {
  int Dims = BSet.dim(isl::dim::set);
  if (Dim >= Dims) {
    Expanded = Expanded.unite(BSet);
    return;
  }

  isl::basic_set DimOnly =
      BSet.project_out(isl::dim::param, 0, BSet.dim(isl::dim::param))
          .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1)
          .project_out(isl::dim::set, 0, Dim);
  if (!DimOnly.is_bounded()) {
    recursiveExpand(BSet, Dim + 1, Expanded);
    return;
  }

  foreachPoint(DimOnly, [&, Dim](isl::point P) {
    isl::val Val = P.get_coordinate_val(isl::dim::set, 0);
    isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val);
    recursiveExpand(FixBSet, Dim + 1, Expanded);
  });
}

/// Make each point of a set explicit.
///
/// "Expanding" makes each point a set contains explicit. That is, the result is
/// a set of singleton polyhedra. Unbounded dimensions are not expanded.
///
/// Example:
///   { [i] : 0 <= i < 2 }
/// is expanded to:
///   { [0]; [1] }
static isl::set expand(const isl::set &Set) {
  isl::set Expanded = isl::set::empty(Set.get_space());
  for (isl::basic_set BSet : Set.get_basic_set_list())
    recursiveExpand(BSet, 0, Expanded);
  return Expanded;
}

/// Expand all points of a union set explicit.
///
/// @see expand(const isl::set)
static isl::union_set expand(const isl::union_set &USet) {
  isl::union_set Expanded = isl::union_set::empty(USet.get_space());
  for (isl::set Set : USet.get_set_list()) {
    isl::set SetExpanded = expand(Set);
    Expanded = Expanded.add_set(SetExpanded);
  }
  return Expanded;
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {
  printSortedPolyhedra(Set, llvm::errs(), true, false);
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {
  printSortedPolyhedra(Map.wrap(), llvm::errs(), true, true);
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) {
  printSortedPolyhedra(USet, llvm::errs(), true, false);
}

LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) {
  printSortedPolyhedra(UMap.wrap(), llvm::errs(), true, true);
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_set *Set) {
  dumpPw(isl::manage_copy(Set));
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_map *Map) {
  dumpPw(isl::manage_copy(Map));
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_set *USet) {
  dumpPw(isl::manage_copy(USet));
}

LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_map *UMap) {
  dumpPw(isl::manage_copy(UMap));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) {
  printSortedPolyhedra(expand(Set), llvm::errs(), false, false);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) {
  printSortedPolyhedra(expand(Map.wrap()), llvm::errs(), false, true);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) {
  printSortedPolyhedra(expand(USet), llvm::errs(), false, false);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) {
  printSortedPolyhedra(expand(UMap.wrap()), llvm::errs(), false, true);
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_set *Set) {
  dumpExpanded(isl::manage_copy(Set));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_map *Map) {
  dumpExpanded(isl::manage_copy(Map));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_set *USet) {
  dumpExpanded(isl::manage_copy(USet));
}

LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_map *UMap) {
  dumpExpanded(isl::manage_copy(UMap));
}
#endif