lib/Support/ISLTools.cpp

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