lib/Support/ISLTools.cpp

   1 //===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Tools, utilities, helpers and extensions useful in conjunction with the
  10 // Integer Set Library (isl).
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "polly/Support/ISLTools.h"
  15 #include "llvm/Support/raw_ostream.h"
  16 #include <cassert>
  17 #include <vector>
  18
  19 using namespace polly;
  20
  21 namespace {
  22 /// Create a map that shifts one dimension by an offset.
  23 ///
  24 /// Example:
  25 /// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
  26 ///   = { [i0, i1] -> [i0, i1 - 1] }
  27 ///
  28 /// @param Space  The map space of the result. Must have equal number of in- and
  29 ///               out-dimensions.
  30 /// @param Pos    Position to shift.
  31 /// @param Amount Value added to the shifted dimension.
  32 ///
  33 /// @return An isl_multi_aff for the map with this shifted dimension.
  34 isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
  35   auto Identity = isl::multi_aff::identity(Space);
  36   if (Amount == 0)
  37     return Identity;
  38   auto ShiftAff = Identity.get_aff(Pos);
  39   ShiftAff = ShiftAff.set_constant_si(Amount);
  40   return Identity.set_aff(Pos, ShiftAff);
  41 }
  42
  43 /// Construct a map that swaps two nested tuples.
  44 ///
  45 /// @param FromSpace1 { Space1[] }
  46 /// @param FromSpace2 { Space2[] }
  47 ///
  48 /// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
  49 isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
  50                                      isl::space FromSpace2) {
  51   // Fast-path on out-of-quota.
  52   if (!FromSpace1 || !FromSpace2)
  53     return {};
  54
  55   assert(FromSpace1.is_set());
  56   assert(FromSpace2.is_set());
  57
  58   unsigned Dims1 = FromSpace1.dim(isl::dim::set);
  59   unsigned Dims2 = FromSpace2.dim(isl::dim::set);
  60
  61   isl::space FromSpace =
  62       FromSpace1.map_from_domain_and_range(FromSpace2).wrap();
  63   isl::space ToSpace = FromSpace2.map_from_domain_and_range(FromSpace1).wrap();
  64   isl::space MapSpace = FromSpace.map_from_domain_and_range(ToSpace);
  65
  66   isl::basic_map Result = isl::basic_map::universe(MapSpace);
  67   for (auto i = Dims1 - Dims1; i < Dims1; i += 1)
  68     Result = Result.equate(isl::dim::in, i, isl::dim::out, Dims2 + i);
  69   for (auto i = Dims2 - Dims2; i < Dims2; i += 1) {
  70     Result = Result.equate(isl::dim::in, Dims1 + i, isl::dim::out, i);
  71   }
  72
  73   return Result;
  74 }
  75
  76 /// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
  77 /// an isl_map.
  78 isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
  79   isl::basic_map BMapResult = makeTupleSwapBasicMap(FromSpace1, FromSpace2);
  80   return isl::map(BMapResult);
  81 }
  82 } // anonymous namespace
  83
  84 isl::map polly::beforeScatter(isl::map Map, bool Strict) {
  85   isl::space RangeSpace = Map.get_space().range();
  86   isl::map ScatterRel =
  87       Strict ? isl::map::lex_gt(RangeSpace) : isl::map::lex_ge(RangeSpace);
  88   return Map.apply_range(ScatterRel);
  89 }
  90
  91 isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
  92   isl::union_map Result = isl::union_map::empty(UMap.get_space());
  93
  94   for (isl::map Map : UMap.get_map_list()) {
  95     isl::map After = beforeScatter(Map, Strict);
  96     Result = Result.add_map(After);
  97   }
  98
  99   return Result;
 100 }
 101
 102 isl::map polly::afterScatter(isl::map Map, bool Strict) {
 103   isl::space RangeSpace = Map.get_space().range();
 104   isl::map ScatterRel =
 105       Strict ? isl::map::lex_lt(RangeSpace) : isl::map::lex_le(RangeSpace);
 106   return Map.apply_range(ScatterRel);
 107 }
 108
 109 isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
 110   isl::union_map Result = isl::union_map::empty(UMap.get_space());
 111   for (isl::map Map : UMap.get_map_list()) {
 112     isl::map After = afterScatter(Map, Strict);
 113     Result = Result.add_map(After);
 114   }
 115   return Result;
 116 }
 117
 118 isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
 119                                bool InclTo) {
 120   isl::map AfterFrom = afterScatter(From, !InclFrom);
 121   isl::map BeforeTo = beforeScatter(To, !InclTo);
 122
 123   return AfterFrom.intersect(BeforeTo);
 124 }
 125
 126 isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
 127                                      bool InclFrom, bool InclTo) {
 128   isl::union_map AfterFrom = afterScatter(From, !InclFrom);
 129   isl::union_map BeforeTo = beforeScatter(To, !InclTo);
 130
 131   return AfterFrom.intersect(BeforeTo);
 132 }
 133
 134 isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
 135   if (!UMap)
 136     return nullptr;
 137
 138   if (isl_union_map_n_map(UMap.get()) == 0)
 139     return isl::map::empty(ExpectedSpace);
 140
 141   isl::map Result = isl::map::from_union_map(UMap);
 142   assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
 143
 144   return Result;
 145 }
 146
 147 isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
 148   if (!USet)
 149     return nullptr;
 150
 151   if (isl_union_set_n_set(USet.get()) == 0)
 152     return isl::set::empty(ExpectedSpace);
 153
 154   isl::set Result(USet);
 155   assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
 156
 157   return Result;
 158 }
 159
 160 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
 161   unsigned Dims = 0;
 162   for (isl::map Map : Schedule.get_map_list())
 163     Dims = std::max(Dims, Map.dim(isl::dim::out));
 164   return Dims;
 165 }
 166
 167 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
 168   if (!Schedule)
 169     return nullptr;
 170   unsigned Dims = getNumScatterDims(Schedule);
 171   isl::space ScatterSpace = Schedule.get_space().set_from_params();
 172   return ScatterSpace.add_dims(isl::dim::set, Dims);
 173 }
 174
 175 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
 176                                       bool RestrictDomain) {
 177   isl::union_map Result = isl::union_map::empty(USet.get_space());
 178   for (isl::set Set : USet.get_set_list()) {
 179     isl::map IdentityMap = isl::map::identity(Set.get_space().map_from_set());
 180     if (RestrictDomain)
 181       IdentityMap = IdentityMap.intersect_domain(Set);
 182     Result = Result.add_map(IdentityMap);
 183   }
 184   return Result;
 185 }
 186
 187 isl::map polly::reverseDomain(isl::map Map) {
 188   isl::space DomSpace = Map.get_space().domain().unwrap();
 189   isl::space Space1 = DomSpace.domain();
 190   isl::space Space2 = DomSpace.range();
 191   isl::map Swap = makeTupleSwapMap(Space1, Space2);
 192   return Map.apply_domain(Swap);
 193 }
 194
 195 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
 196   isl::union_map Result = isl::union_map::empty(UMap.get_space());
 197   for (isl::map Map : UMap.get_map_list()) {
 198     auto Reversed = reverseDomain(std::move(Map));
 199     Result = Result.add_map(Reversed);
 200   }
 201   return Result;
 202 }
 203
 204 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
 205   int NumDims = Set.dim(isl::dim::set);
 206   if (Pos < 0)
 207     Pos = NumDims + Pos;
 208   assert(Pos < NumDims && "Dimension index must be in range");
 209   isl::space Space = Set.get_space();
 210   Space = Space.map_from_domain_and_range(Space);
 211   isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
 212   isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
 213   return Set.apply(TranslatorMap);
 214 }
 215
 216 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
 217   isl::union_set Result = isl::union_set::empty(USet.get_space());
 218   for (isl::set Set : USet.get_set_list()) {
 219     isl::set Shifted = shiftDim(Set, Pos, Amount);
 220     Result = Result.add_set(Shifted);
 221   }
 222   return Result;
 223 }
 224
 225 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
 226   int NumDims = Map.dim(Dim);
 227   if (Pos < 0)
 228     Pos = NumDims + Pos;
 229   assert(Pos < NumDims && "Dimension index must be in range");
 230   isl::space Space = Map.get_space();
 231   switch (Dim) {
 232   case isl::dim::in:
 233     Space = Space.domain();
 234     break;
 235   case isl::dim::out:
 236     Space = Space.range();
 237     break;
 238   default:
 239     llvm_unreachable("Unsupported value for 'dim'");
 240   }
 241   Space = Space.map_from_domain_and_range(Space);
 242   isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
 243   isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
 244   switch (Dim) {
 245   case isl::dim::in:
 246     return Map.apply_domain(TranslatorMap);
 247   case isl::dim::out:
 248     return Map.apply_range(TranslatorMap);
 249   default:
 250     llvm_unreachable("Unsupported value for 'dim'");
 251   }
 252 }
 253
 254 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
 255                                int Amount) {
 256   isl::union_map Result = isl::union_map::empty(UMap.get_space());
 257
 258   for (isl::map Map : UMap.get_map_list()) {
 259     isl::map Shifted = shiftDim(Map, Dim, Pos, Amount);
 260     Result = Result.add_map(Shifted);
 261   }
 262   return Result;
 263 }
 264
 265 void polly::simplify(isl::set &Set) {
 266   Set = isl::manage(isl_set_compute_divs(Set.copy()));
 267   Set = Set.detect_equalities();
 268   Set = Set.coalesce();
 269 }
 270
 271 void polly::simplify(isl::union_set &USet) {
 272   USet = isl::manage(isl_union_set_compute_divs(USet.copy()));
 273   USet = USet.detect_equalities();
 274   USet = USet.coalesce();
 275 }
 276
 277 void polly::simplify(isl::map &Map) {
 278   Map = isl::manage(isl_map_compute_divs(Map.copy()));
 279   Map = Map.detect_equalities();
 280   Map = Map.coalesce();
 281 }
 282
 283 void polly::simplify(isl::union_map &UMap) {
 284   UMap = isl::manage(isl_union_map_compute_divs(UMap.copy()));
 285   UMap = UMap.detect_equalities();
 286   UMap = UMap.coalesce();
 287 }
 288
 289 isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
 290                                            isl::union_map Writes, bool Reverse,
 291                                            bool InclPrevDef, bool InclNextDef) {
 292
 293   // { Scatter[] }
 294   isl::space ScatterSpace = getScatterSpace(Schedule);
 295
 296   // { ScatterRead[] -> ScatterWrite[] }
 297   isl::map Relation;
 298   if (Reverse)
 299     Relation = InclPrevDef ? isl::map::lex_lt(ScatterSpace)
 300                            : isl::map::lex_le(ScatterSpace);
 301   else
 302     Relation = InclNextDef ? isl::map::lex_gt(ScatterSpace)
 303                            : isl::map::lex_ge(ScatterSpace);
 304
 305   // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
 306   isl::map RelationMap = Relation.range_map().reverse();
 307
 308   // { Element[] -> ScatterWrite[] }
 309   isl::union_map WriteAction = Schedule.apply_domain(Writes);
 310
 311   // { ScatterWrite[] -> Element[] }
 312   isl::union_map WriteActionRev = WriteAction.reverse();
 313
 314   // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
 315   isl::union_map DefSchedRelation =
 316       isl::union_map(RelationMap).apply_domain(WriteActionRev);
 317
 318   // For each element, at every point in time, map to the times of previous
 319   // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
 320   isl::union_map ReachableWrites = DefSchedRelation.uncurry();
 321   if (Reverse)
 322     ReachableWrites = ReachableWrites.lexmin();
 323   else
 324     ReachableWrites = ReachableWrites.lexmax();
 325
 326   // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
 327   isl::union_map SelfUse = WriteAction.range_map();
 328
 329   if (InclPrevDef && InclNextDef) {
 330     // Add the Def itself to the solution.
 331     ReachableWrites = ReachableWrites.unite(SelfUse).coalesce();
 332   } else if (!InclPrevDef && !InclNextDef) {
 333     // Remove Def itself from the solution.
 334     ReachableWrites = ReachableWrites.subtract(SelfUse);
 335   }
 336
 337   // { [Element[] -> ScatterRead[]] -> Domain[] }
 338   return ReachableWrites.apply_range(Schedule.reverse());
 339 }
 340
 341 isl::union_map
 342 polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
 343                           isl::union_map Reads, bool ReadEltInSameInst,
 344                           bool IncludeLastRead, bool IncludeWrite) {
 345   // { Element[] -> Scatter[] }
 346   isl::union_map ReadActions = Schedule.apply_domain(Reads);
 347   isl::union_map WriteActions = Schedule.apply_domain(Writes);
 348
 349   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 350   isl::union_map EltDomWrites =
 351       Writes.reverse().range_map().apply_range(Schedule);
 352
 353   // { [Element[] -> Scatter[]] -> DomainWrite[] }
 354   isl::union_map ReachingOverwrite = computeReachingWrite(
 355       Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
 356
 357   // { [Element[] -> Scatter[]] -> DomainWrite[] }
 358   isl::union_map ReadsOverwritten =
 359       ReachingOverwrite.intersect_domain(ReadActions.wrap());
 360
 361   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 362   isl::union_map ReadsOverwrittenRotated =
 363       reverseDomain(ReadsOverwritten).curry().reverse();
 364   isl::union_map LastOverwrittenRead = ReadsOverwrittenRotated.lexmax();
 365
 366   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 367   isl::union_map BetweenLastReadOverwrite = betweenScatter(
 368       LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
 369
 370   // { [Element[] -> Scatter[]] -> DomainWrite[] }
 371   isl::union_map ReachingOverwriteZone = computeReachingWrite(
 372       Schedule, Writes, true, IncludeLastRead, IncludeWrite);
 373
 374   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 375   isl::union_map ReachingOverwriteRotated =
 376       reverseDomain(ReachingOverwriteZone).curry().reverse();
 377
 378   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 379   isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
 380       ReadsOverwrittenRotated.domain());
 381
 382   return BetweenLastReadOverwrite.unite(WritesWithoutReads)
 383       .domain_factor_domain();
 384 }
 385
 386 isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
 387                                               bool InclStart, bool InclEnd) {
 388   if (!InclStart && InclEnd)
 389     return Zone;
 390
 391   auto ShiftedZone = shiftDim(Zone, -1, -1);
 392   if (InclStart && !InclEnd)
 393     return ShiftedZone;
 394   else if (!InclStart && !InclEnd)
 395     return Zone.intersect(ShiftedZone);
 396
 397   assert(InclStart && InclEnd);
 398   return Zone.unite(ShiftedZone);
 399 }
 400
 401 isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
 402                                               bool InclStart, bool InclEnd) {
 403   if (!InclStart && InclEnd)
 404     return Zone;
 405
 406   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
 407   if (InclStart && !InclEnd)
 408     return ShiftedZone;
 409   else if (!InclStart && !InclEnd)
 410     return Zone.intersect(ShiftedZone);
 411
 412   assert(InclStart && InclEnd);
 413   return Zone.unite(ShiftedZone);
 414 }
 415
 416 isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
 417                                         bool InclStart, bool InclEnd) {
 418   if (!InclStart && InclEnd)
 419     return Zone;
 420
 421   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
 422   if (InclStart && !InclEnd)
 423     return ShiftedZone;
 424   else if (!InclStart && !InclEnd)
 425     return Zone.intersect(ShiftedZone);
 426
 427   assert(InclStart && InclEnd);
 428   return Zone.unite(ShiftedZone);
 429 }
 430
 431 isl::map polly::distributeDomain(isl::map Map) {
 432   // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
 433   // Domain[] -> Range2[] } and combine again. We would loose any relation
 434   // between Range1[] and Range2[] that is not also a constraint to Domain[].
 435
 436   isl::space Space = Map.get_space();
 437   isl::space DomainSpace = Space.domain();
 438   unsigned DomainDims = DomainSpace.dim(isl::dim::set);
 439   isl::space RangeSpace = Space.range().unwrap();
 440   isl::space Range1Space = RangeSpace.domain();
 441   unsigned Range1Dims = Range1Space.dim(isl::dim::set);
 442   isl::space Range2Space = RangeSpace.range();
 443   unsigned Range2Dims = Range2Space.dim(isl::dim::set);
 444
 445   isl::space OutputSpace =
 446       DomainSpace.map_from_domain_and_range(Range1Space)
 447           .wrap()
 448           .map_from_domain_and_range(
 449               DomainSpace.map_from_domain_and_range(Range2Space).wrap());
 450
 451   isl::basic_map Translator = isl::basic_map::universe(
 452       Space.wrap().map_from_domain_and_range(OutputSpace.wrap()));
 453
 454   for (unsigned i = 0; i < DomainDims; i += 1) {
 455     Translator = Translator.equate(isl::dim::in, i, isl::dim::out, i);
 456     Translator = Translator.equate(isl::dim::in, i, isl::dim::out,
 457                                    DomainDims + Range1Dims + i);
 458   }
 459   for (unsigned i = 0; i < Range1Dims; i += 1)
 460     Translator = Translator.equate(isl::dim::in, DomainDims + i, isl::dim::out,
 461                                    DomainDims + i);
 462   for (unsigned i = 0; i < Range2Dims; i += 1)
 463     Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i,
 464                                    isl::dim::out,
 465                                    DomainDims + Range1Dims + DomainDims + i);
 466
 467   return Map.wrap().apply(Translator).unwrap();
 468 }
 469
 470 isl::union_map polly::distributeDomain(isl::union_map UMap) {
 471   isl::union_map Result = isl::union_map::empty(UMap.get_space());
 472   for (isl::map Map : UMap.get_map_list()) {
 473     auto Distributed = distributeDomain(Map);
 474     Result = Result.add_map(Distributed);
 475   }
 476   return Result;
 477 }
 478
 479 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
 480
 481   // { Factor[] -> Factor[] }
 482   isl::union_map Factors = makeIdentityMap(Factor, true);
 483
 484   return Factors.product(UMap);
 485 }
 486
 487 isl::union_map polly::applyDomainRange(isl::union_map UMap,
 488                                        isl::union_map Func) {
 489   // This implementation creates unnecessary cross products of the
 490   // DomainDomain[] and Func. An alternative implementation could reverse
 491   // domain+uncurry,apply Func to what now is the domain, then undo the
 492   // preparing transformation. Another alternative implementation could create a
 493   // translator map for each piece.
 494
 495   // { DomainDomain[] }
 496   isl::union_set DomainDomain = UMap.domain().unwrap().domain();
 497
 498   // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
 499   // }
 500   isl::union_map LifetedFunc = liftDomains(std::move(Func), DomainDomain);
 501
 502   return UMap.apply_domain(LifetedFunc);
 503 }
 504
 505 isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
 506   isl::set RangeSet = Range.extract_set(Map.get_space().range());
 507   return Map.intersect_range(RangeSet);
 508 }
 509
 510 isl::map polly::subtractParams(isl::map Map, isl::set Params) {
 511   auto MapSpace = Map.get_space();
 512   auto ParamsMap = isl::map::universe(MapSpace).intersect_params(Params);
 513   return Map.subtract(ParamsMap);
 514 }
 515
 516 isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
 517   assert(!Max || !Min); // Cannot return min and max at the same time.
 518   isl::val Result;
 519   isl::stat Stat = PwAff.foreach_piece(
 520       [=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {
 521         if (Result && Result.is_nan())
 522           return isl::stat::ok();
 523
 524         // TODO: If Min/Max, we can also determine a minimum/maximum value if
 525         // Set is constant-bounded.
 526         if (!Aff.is_cst()) {
 527           Result = isl::val::nan(Aff.get_ctx());
 528           return isl::stat::error();
 529         }
 530
 531         isl::val ThisVal = Aff.get_constant_val();
 532         if (!Result) {
 533           Result = ThisVal;
 534           return isl::stat::ok();
 535         }
 536
 537         if (Result.eq(ThisVal))
 538           return isl::stat::ok();
 539
 540         if (Max && ThisVal.gt(Result)) {
 541           Result = ThisVal;
 542           return isl::stat::ok();
 543         }
 544
 545         if (Min && ThisVal.lt(Result)) {
 546           Result = ThisVal;
 547           return isl::stat::ok();
 548         }
 549
 550         // Not compatible
 551         Result = isl::val::nan(Aff.get_ctx());
 552         return isl::stat::error();
 553       });
 554
 555   if (Stat.is_error())
 556     return {};
 557
 558   return Result;
 559 }
 560
 561 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 562 static void foreachPoint(const isl::set &Set,
 563                          const std::function<void(isl::point P)> &F) {
 564   Set.foreach_point([&](isl::point P) -> isl::stat {
 565     F(P);
 566     return isl::stat::ok();
 567   });
 568 }
 569
 570 static void foreachPoint(isl::basic_set BSet,
 571                          const std::function<void(isl::point P)> &F) {
 572   foreachPoint(isl::set(BSet), F);
 573 }
 574
 575 /// Determine the sorting order of the sets @p A and @p B without considering
 576 /// the space structure.
 577 ///
 578 /// Ordering is based on the lower bounds of the set's dimensions. First
 579 /// dimensions are considered first.
 580 static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {
 581   unsigned ALen = A.dim(isl::dim::set);
 582   unsigned BLen = B.dim(isl::dim::set);
 583   unsigned Len = std::min(ALen, BLen);
 584
 585   for (unsigned i = 0; i < Len; i += 1) {
 586     isl::basic_set ADim =
 587         A.project_out(isl::dim::param, 0, A.dim(isl::dim::param))
 588             .project_out(isl::dim::set, i + 1, ALen - i - 1)
 589             .project_out(isl::dim::set, 0, i);
 590     isl::basic_set BDim =
 591         B.project_out(isl::dim::param, 0, B.dim(isl::dim::param))
 592             .project_out(isl::dim::set, i + 1, BLen - i - 1)
 593             .project_out(isl::dim::set, 0, i);
 594
 595     isl::basic_set AHull = isl::set(ADim).convex_hull();
 596     isl::basic_set BHull = isl::set(BDim).convex_hull();
 597
 598     bool ALowerBounded =
 599         bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0));
 600     bool BLowerBounded =
 601         bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0));
 602
 603     int BoundedCompare = BLowerBounded - ALowerBounded;
 604     if (BoundedCompare != 0)
 605       return BoundedCompare;
 606
 607     if (!ALowerBounded || !BLowerBounded)
 608       continue;
 609
 610     isl::pw_aff AMin = isl::set(ADim).dim_min(0);
 611     isl::pw_aff BMin = isl::set(BDim).dim_min(0);
 612
 613     isl::val AMinVal = polly::getConstant(AMin, false, true);
 614     isl::val BMinVal = polly::getConstant(BMin, false, true);
 615
 616     int MinCompare = AMinVal.sub(BMinVal).sgn();
 617     if (MinCompare != 0)
 618       return MinCompare;
 619   }
 620
 621   // If all the dimensions' lower bounds are equal or incomparable, sort based
 622   // on the number of dimensions.
 623   return ALen - BLen;
 624 }
 625
 626 /// Compare the sets @p A and @p B according to their nested space structure.
 627 /// Returns 0 if the structure is considered equal.
 628 /// If @p ConsiderTupleLen is false, the number of dimensions in a tuple are
 629 /// ignored, i.e. a tuple with the same name but different number of dimensions
 630 /// are considered equal.
 631 static int structureCompare(const isl::space &ASpace, const isl::space &BSpace,
 632                             bool ConsiderTupleLen) {
 633   int WrappingCompare = bool(ASpace.is_wrapping()) - bool(BSpace.is_wrapping());
 634   if (WrappingCompare != 0)
 635     return WrappingCompare;
 636
 637   if (ASpace.is_wrapping() && BSpace.is_wrapping()) {
 638     isl::space AMap = ASpace.unwrap();
 639     isl::space BMap = BSpace.unwrap();
 640
 641     int FirstResult =
 642         structureCompare(AMap.domain(), BMap.domain(), ConsiderTupleLen);
 643     if (FirstResult != 0)
 644       return FirstResult;
 645
 646     return structureCompare(AMap.range(), BMap.range(), ConsiderTupleLen);
 647   }
 648
 649   std::string AName;
 650   if (ASpace.has_tuple_name(isl::dim::set))
 651     AName = ASpace.get_tuple_name(isl::dim::set);
 652
 653   std::string BName;
 654   if (BSpace.has_tuple_name(isl::dim::set))
 655     BName = BSpace.get_tuple_name(isl::dim::set);
 656
 657   int NameCompare = AName.compare(BName);
 658   if (NameCompare != 0)
 659     return NameCompare;
 660
 661   if (ConsiderTupleLen) {
 662     int LenCompare = BSpace.dim(isl::dim::set) - ASpace.dim(isl::dim::set);
 663     if (LenCompare != 0)
 664       return LenCompare;
 665   }
 666
 667   return 0;
 668 }
 669
 670 /// Compare the sets @p A and @p B according to their nested space structure. If
 671 /// the structure is the same, sort using the dimension lower bounds.
 672 /// Returns an std::sort compatible bool.
 673 static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) {
 674   isl::space ASpace = A.get_space();
 675   isl::space BSpace = B.get_space();
 676
 677   // Ignoring number of dimensions first ensures that structures with same tuple
 678   // names, but different number of dimensions are still sorted close together.
 679   int TupleNestingCompare = structureCompare(ASpace, BSpace, false);
 680   if (TupleNestingCompare != 0)
 681     return TupleNestingCompare < 0;
 682
 683   int TupleCompare = structureCompare(ASpace, BSpace, true);
 684   if (TupleCompare != 0)
 685     return TupleCompare < 0;
 686
 687   return flatCompare(A, B) < 0;
 688 }
 689
 690 /// Print a string representation of @p USet to @p OS.
 691 ///
 692 /// The pieces of @p USet are printed in a sorted order. Spaces with equal or
 693 /// similar nesting structure are printed together. Compared to isl's own
 694 /// printing function the uses the structure itself as base of the sorting, not
 695 /// a hash of it. It ensures that e.g. maps spaces with same domain structure
 696 /// are printed together. Set pieces with same structure are printed in order of
 697 /// their lower bounds.
 698 ///
 699 /// @param USet     Polyhedra to print.
 700 /// @param OS       Target stream.
 701 /// @param Simplify Whether to simplify the polyhedron before printing.
 702 /// @param IsMap    Whether @p USet is a wrapped map. If true, sets are
 703 ///                 unwrapped before printing to again appear as a map.
 704 static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS,
 705                                  bool Simplify, bool IsMap) {
 706   if (!USet) {
 707     OS << "<null>\n";
 708     return;
 709   }
 710
 711   if (Simplify)
 712     simplify(USet);
 713
 714   // Get all the polyhedra.
 715   std::vector<isl::basic_set> BSets;
 716
 717   for (isl::set Set : USet.get_set_list()) {
 718     for (isl::basic_set BSet : Set.get_basic_set_list()) {
 719       BSets.push_back(BSet);
 720     }
 721   }
 722
 723   if (BSets.empty()) {
 724     OS << "{\n}\n";
 725     return;
 726   }
 727
 728   // Sort the polyhedra.
 729   llvm::sort(BSets, orderComparer);
 730
 731   // Print the polyhedra.
 732   bool First = true;
 733   for (const isl::basic_set &BSet : BSets) {
 734     std::string Str;
 735     if (IsMap)
 736       Str = isl::map(BSet.unwrap()).to_str();
 737     else
 738       Str = isl::set(BSet).to_str();
 739     size_t OpenPos = Str.find_first_of('{');
 740     assert(OpenPos != std::string::npos);
 741     size_t ClosePos = Str.find_last_of('}');
 742     assert(ClosePos != std::string::npos);
 743
 744     if (First)
 745       OS << llvm::StringRef(Str).substr(0, OpenPos + 1) << "\n ";
 746     else
 747       OS << ";\n ";
 748
 749     OS << llvm::StringRef(Str).substr(OpenPos + 1, ClosePos - OpenPos - 2);
 750     First = false;
 751   }
 752   assert(!First);
 753   OS << "\n}\n";
 754 }
 755
 756 static void recursiveExpand(isl::basic_set BSet, int Dim, isl::set &Expanded) {
 757   int Dims = BSet.dim(isl::dim::set);
 758   if (Dim >= Dims) {
 759     Expanded = Expanded.unite(BSet);
 760     return;
 761   }
 762
 763   isl::basic_set DimOnly =
 764       BSet.project_out(isl::dim::param, 0, BSet.dim(isl::dim::param))
 765           .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1)
 766           .project_out(isl::dim::set, 0, Dim);
 767   if (!DimOnly.is_bounded()) {
 768     recursiveExpand(BSet, Dim + 1, Expanded);
 769     return;
 770   }
 771
 772   foreachPoint(DimOnly, [&, Dim](isl::point P) {
 773     isl::val Val = P.get_coordinate_val(isl::dim::set, 0);
 774     isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val);
 775     recursiveExpand(FixBSet, Dim + 1, Expanded);
 776   });
 777 }
 778
 779 /// Make each point of a set explicit.
 780 ///
 781 /// "Expanding" makes each point a set contains explicit. That is, the result is
 782 /// a set of singleton polyhedra. Unbounded dimensions are not expanded.
 783 ///
 784 /// Example:
 785 ///   { [i] : 0 <= i < 2 }
 786 /// is expanded to:
 787 ///   { [0]; [1] }
 788 static isl::set expand(const isl::set &Set) {
 789   isl::set Expanded = isl::set::empty(Set.get_space());
 790   for (isl::basic_set BSet : Set.get_basic_set_list())
 791     recursiveExpand(BSet, 0, Expanded);
 792   return Expanded;
 793 }
 794
 795 /// Expand all points of a union set explicit.
 796 ///
 797 /// @see expand(const isl::set)
 798 static isl::union_set expand(const isl::union_set &USet) {
 799   isl::union_set Expanded = isl::union_set::empty(USet.get_space());
 800   for (isl::set Set : USet.get_set_list()) {
 801     isl::set SetExpanded = expand(Set);
 802     Expanded = Expanded.add_set(SetExpanded);
 803   }
 804   return Expanded;
 805 }
 806
 807 LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {
 808   printSortedPolyhedra(Set, llvm::errs(), true, false);
 809 }
 810
 811 LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {
 812   printSortedPolyhedra(Map.wrap(), llvm::errs(), true, true);
 813 }
 814
 815 LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) {
 816   printSortedPolyhedra(USet, llvm::errs(), true, false);
 817 }
 818
 819 LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) {
 820   printSortedPolyhedra(UMap.wrap(), llvm::errs(), true, true);
 821 }
 822
 823 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_set *Set) {
 824   dumpPw(isl::manage_copy(Set));
 825 }
 826
 827 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_map *Map) {
 828   dumpPw(isl::manage_copy(Map));
 829 }
 830
 831 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_set *USet) {
 832   dumpPw(isl::manage_copy(USet));
 833 }
 834
 835 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_map *UMap) {
 836   dumpPw(isl::manage_copy(UMap));
 837 }
 838
 839 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) {
 840   printSortedPolyhedra(expand(Set), llvm::errs(), false, false);
 841 }
 842
 843 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) {
 844   printSortedPolyhedra(expand(Map.wrap()), llvm::errs(), false, true);
 845 }
 846
 847 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) {
 848   printSortedPolyhedra(expand(USet), llvm::errs(), false, false);
 849 }
 850
 851 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) {
 852   printSortedPolyhedra(expand(UMap.wrap()), llvm::errs(), false, true);
 853 }
 854
 855 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_set *Set) {
 856   dumpExpanded(isl::manage_copy(Set));
 857 }
 858
 859 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_map *Map) {
 860   dumpExpanded(isl::manage_copy(Map));
 861 }
 862
 863 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_set *USet) {
 864   dumpExpanded(isl::manage_copy(USet));
 865 }
 866
 867 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_map *UMap) {
 868   dumpExpanded(isl::manage_copy(UMap));
 869 }
 870 #endif