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
  17 using namespace polly;
  18
  19 namespace {
  20 /// Create a map that shifts one dimension by an offset.
  21 ///
  22 /// Example:
  23 /// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
  24 ///   = { [i0, i1] -> [i0, i1 - 1] }
  25 ///
  26 /// @param Space  The map space of the result. Must have equal number of in- and
  27 ///               out-dimensions.
  28 /// @param Pos    Position to shift.
  29 /// @param Amount Value added to the shifted dimension.
  30 ///
  31 /// @return An isl_multi_aff for the map with this shifted dimension.
  32 isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
  33   auto Identity = give(isl_multi_aff_identity(Space.take()));
  34   if (Amount == 0)
  35     return Identity;
  36   auto ShiftAff = give(isl_multi_aff_get_aff(Identity.keep(), Pos));
  37   ShiftAff = give(isl_aff_set_constant_si(ShiftAff.take(), Amount));
  38   return give(isl_multi_aff_set_aff(Identity.take(), Pos, ShiftAff.take()));
  39 }
  40
  41 /// Construct a map that swaps two nested tuples.
  42 ///
  43 /// @param FromSpace1 { Space1[] }
  44 /// @param FromSpace2 { Space2[] }
  45 ///
  46 /// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
  47 isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
  48                                      isl::space FromSpace2) {
  49   assert(isl_space_is_set(FromSpace1.keep()) != isl_bool_false);
  50   assert(isl_space_is_set(FromSpace2.keep()) != isl_bool_false);
  51
  52   auto Dims1 = isl_space_dim(FromSpace1.keep(), isl_dim_set);
  53   auto Dims2 = isl_space_dim(FromSpace2.keep(), isl_dim_set);
  54   auto FromSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
  55       FromSpace1.copy(), FromSpace2.copy())));
  56   auto ToSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
  57       FromSpace2.take(), FromSpace1.take())));
  58   auto MapSpace = give(
  59       isl_space_map_from_domain_and_range(FromSpace.take(), ToSpace.take()));
  60
  61   auto Result = give(isl_basic_map_universe(MapSpace.take()));
  62   for (auto i = Dims1 - Dims1; i < Dims1; i += 1) {
  63     Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, i,
  64                                        isl_dim_out, Dims2 + i));
  65   }
  66   for (auto i = Dims2 - Dims2; i < Dims2; i += 1) {
  67     Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, Dims1 + i,
  68                                        isl_dim_out, i));
  69   }
  70
  71   return Result;
  72 }
  73
  74 /// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
  75 /// an isl_map.
  76 isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
  77   auto BMapResult =
  78       makeTupleSwapBasicMap(std::move(FromSpace1), std::move(FromSpace2));
  79   return give(isl_map_from_basic_map(BMapResult.take()));
  80 }
  81 } // anonymous namespace
  82
  83 isl::map polly::beforeScatter(isl::map Map, bool Strict) {
  84   auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
  85   auto ScatterRel = give(Strict ? isl_map_lex_gt(RangeSpace.take())
  86                                 : isl_map_lex_ge(RangeSpace.take()));
  87   return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
  88 }
  89
  90 isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
  91   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
  92   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
  93     auto After = beforeScatter(Map, Strict);
  94     Result = give(isl_union_map_add_map(Result.take(), After.take()));
  95     return isl::stat::ok;
  96   });
  97   return Result;
  98 }
  99
 100 isl::map polly::afterScatter(isl::map Map, bool Strict) {
 101   auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
 102   auto ScatterRel = give(Strict ? isl_map_lex_lt(RangeSpace.take())
 103                                 : isl_map_lex_le(RangeSpace.take()));
 104   return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
 105 }
 106
 107 isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
 108   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
 109   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
 110     auto After = afterScatter(Map, Strict);
 111     Result = give(isl_union_map_add_map(Result.take(), After.take()));
 112     return isl::stat::ok;
 113   });
 114   return Result;
 115 }
 116
 117 isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
 118                                bool InclTo) {
 119   auto AfterFrom = afterScatter(From, !InclFrom);
 120   auto BeforeTo = beforeScatter(To, !InclTo);
 121
 122   return give(isl_map_intersect(AfterFrom.take(), BeforeTo.take()));
 123 }
 124
 125 isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
 126                                      bool InclFrom, bool InclTo) {
 127   auto AfterFrom = afterScatter(From, !InclFrom);
 128   auto BeforeTo = beforeScatter(To, !InclTo);
 129
 130   return give(isl_union_map_intersect(AfterFrom.take(), BeforeTo.take()));
 131 }
 132
 133 isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
 134   if (!UMap)
 135     return nullptr;
 136
 137   if (isl_union_map_n_map(UMap.keep()) == 0)
 138     return give(isl_map_empty(ExpectedSpace.take()));
 139
 140   auto Result = give(isl_map_from_union_map(UMap.take()));
 141   assert(!Result || isl_space_has_equal_tuples(
 142                         give(isl_map_get_space(Result.keep())).keep(),
 143                         ExpectedSpace.keep()) == isl_bool_true);
 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 give(isl_set_empty(ExpectedSpace.copy()));
 153
 154   auto Result = give(isl_set_from_union_set(USet.take()));
 155   assert(!Result || isl_space_has_equal_tuples(
 156                         give(isl_set_get_space(Result.keep())).keep(),
 157                         ExpectedSpace.keep()) == isl_bool_true);
 158   return Result;
 159 }
 160
 161 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
 162   unsigned Dims = 0;
 163   Schedule.foreach_map([&Dims](isl::map Map) -> isl::stat {
 164     Dims = std::max(Dims, isl_map_dim(Map.keep(), isl_dim_out));
 165     return isl::stat::ok;
 166   });
 167   return Dims;
 168 }
 169
 170 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
 171   if (!Schedule)
 172     return nullptr;
 173   auto Dims = getNumScatterDims(Schedule);
 174   auto ScatterSpace =
 175       give(isl_space_set_from_params(isl_union_map_get_space(Schedule.keep())));
 176   return give(isl_space_add_dims(ScatterSpace.take(), isl_dim_set, Dims));
 177 }
 178
 179 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
 180                                       bool RestrictDomain) {
 181   auto Result = give(isl_union_map_empty(isl_union_set_get_space(USet.keep())));
 182   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
 183     auto IdentityMap = give(isl_map_identity(
 184         isl_space_map_from_set(isl_set_get_space(Set.keep()))));
 185     if (RestrictDomain)
 186       IdentityMap =
 187           give(isl_map_intersect_domain(IdentityMap.take(), Set.take()));
 188     Result = give(isl_union_map_add_map(Result.take(), IdentityMap.take()));
 189     return isl::stat::ok;
 190   });
 191   return Result;
 192 }
 193
 194 isl::map polly::reverseDomain(isl::map Map) {
 195   auto DomSpace =
 196       give(isl_space_unwrap(isl_space_domain(isl_map_get_space(Map.keep()))));
 197   auto Space1 = give(isl_space_domain(DomSpace.copy()));
 198   auto Space2 = give(isl_space_range(DomSpace.take()));
 199   auto Swap = makeTupleSwapMap(std::move(Space1), std::move(Space2));
 200   return give(isl_map_apply_domain(Map.take(), Swap.take()));
 201 }
 202
 203 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
 204   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
 205   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
 206     auto Reversed = reverseDomain(std::move(Map));
 207     Result = give(isl_union_map_add_map(Result.take(), Reversed.take()));
 208     return isl::stat::ok;
 209   });
 210   return Result;
 211 }
 212
 213 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
 214   int NumDims = isl_set_dim(Set.keep(), isl_dim_set);
 215   if (Pos < 0)
 216     Pos = NumDims + Pos;
 217   assert(Pos < NumDims && "Dimension index must be in range");
 218   auto Space = give(isl_set_get_space(Set.keep()));
 219   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
 220   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
 221   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
 222   return give(isl_set_apply(Set.take(), TranslatorMap.take()));
 223 }
 224
 225 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
 226   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
 227   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
 228     auto Shifted = shiftDim(Set, Pos, Amount);
 229     Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
 230     return isl::stat::ok;
 231   });
 232   return Result;
 233 }
 234
 235 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
 236   int NumDims = Map.dim(Dim);
 237   if (Pos < 0)
 238     Pos = NumDims + Pos;
 239   assert(Pos < NumDims && "Dimension index must be in range");
 240   auto Space = give(isl_map_get_space(Map.keep()));
 241   switch (Dim) {
 242   case isl::dim::in:
 243     Space = std::move(Space).domain();
 244     break;
 245   case isl::dim::out:
 246     Space = give(isl_space_range(Space.take()));
 247     break;
 248   default:
 249     llvm_unreachable("Unsupported value for 'dim'");
 250   }
 251   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
 252   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
 253   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
 254   switch (Dim) {
 255   case isl::dim::in:
 256     return Map.apply_domain(TranslatorMap);
 257   case isl::dim::out:
 258     return Map.apply_range(TranslatorMap);
 259   default:
 260     llvm_unreachable("Unsupported value for 'dim'");
 261   }
 262 }
 263
 264 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
 265                                int Amount) {
 266   auto Result = isl::union_map::empty(UMap.get_space());
 267
 268   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
 269     auto Shifted = shiftDim(Map, Dim, Pos, Amount);
 270     Result = std::move(Result).add_map(Shifted);
 271     return isl::stat::ok;
 272   });
 273   return Result;
 274 }
 275
 276 void polly::simplify(isl::set &Set) {
 277   Set = give(isl_set_compute_divs(Set.take()));
 278   Set = give(isl_set_detect_equalities(Set.take()));
 279   Set = give(isl_set_coalesce(Set.take()));
 280 }
 281
 282 void polly::simplify(isl::union_set &USet) {
 283   USet = give(isl_union_set_compute_divs(USet.take()));
 284   USet = give(isl_union_set_detect_equalities(USet.take()));
 285   USet = give(isl_union_set_coalesce(USet.take()));
 286 }
 287
 288 void polly::simplify(isl::map &Map) {
 289   Map = give(isl_map_compute_divs(Map.take()));
 290   Map = give(isl_map_detect_equalities(Map.take()));
 291   Map = give(isl_map_coalesce(Map.take()));
 292 }
 293
 294 void polly::simplify(isl::union_map &UMap) {
 295   UMap = give(isl_union_map_compute_divs(UMap.take()));
 296   UMap = give(isl_union_map_detect_equalities(UMap.take()));
 297   UMap = give(isl_union_map_coalesce(UMap.take()));
 298 }
 299
 300 isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
 301                                            isl::union_map Writes, bool Reverse,
 302                                            bool InclPrevDef, bool InclNextDef) {
 303
 304   // { Scatter[] }
 305   auto ScatterSpace = getScatterSpace(Schedule);
 306
 307   // { ScatterRead[] -> ScatterWrite[] }
 308   isl::map Relation;
 309   if (Reverse)
 310     Relation = give(InclPrevDef ? isl_map_lex_lt(ScatterSpace.take())
 311                                 : isl_map_lex_le(ScatterSpace.take()));
 312   else
 313     Relation = give(InclNextDef ? isl_map_lex_gt(ScatterSpace.take())
 314                                 : isl_map_lex_ge(ScatterSpace.take()));
 315
 316   // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
 317   auto RelationMap = give(isl_map_reverse(isl_map_range_map(Relation.take())));
 318
 319   // { Element[] -> ScatterWrite[] }
 320   auto WriteAction =
 321       give(isl_union_map_apply_domain(Schedule.copy(), Writes.take()));
 322
 323   // { ScatterWrite[] -> Element[] }
 324   auto WriteActionRev = give(isl_union_map_reverse(WriteAction.copy()));
 325
 326   // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
 327   auto DefSchedRelation = give(isl_union_map_apply_domain(
 328       isl_union_map_from_map(RelationMap.take()), WriteActionRev.take()));
 329
 330   // For each element, at every point in time, map to the times of previous
 331   // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
 332   auto ReachableWrites = give(isl_union_map_uncurry(DefSchedRelation.take()));
 333   if (Reverse)
 334     ReachableWrites = give(isl_union_map_lexmin(ReachableWrites.copy()));
 335   else
 336     ReachableWrites = give(isl_union_map_lexmax(ReachableWrites.copy()));
 337
 338   // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
 339   auto SelfUse = give(isl_union_map_range_map(WriteAction.take()));
 340
 341   if (InclPrevDef && InclNextDef) {
 342     // Add the Def itself to the solution.
 343     ReachableWrites =
 344         give(isl_union_map_union(ReachableWrites.take(), SelfUse.take()));
 345     ReachableWrites = give(isl_union_map_coalesce(ReachableWrites.take()));
 346   } else if (!InclPrevDef && !InclNextDef) {
 347     // Remove Def itself from the solution.
 348     ReachableWrites =
 349         give(isl_union_map_subtract(ReachableWrites.take(), SelfUse.take()));
 350   }
 351
 352   // { [Element[] -> ScatterRead[]] -> Domain[] }
 353   auto ReachableWriteDomain = give(isl_union_map_apply_range(
 354       ReachableWrites.take(), isl_union_map_reverse(Schedule.take())));
 355
 356   return ReachableWriteDomain;
 357 }
 358
 359 isl::union_map
 360 polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
 361                           isl::union_map Reads, bool ReadEltInSameInst,
 362                           bool IncludeLastRead, bool IncludeWrite) {
 363   // { Element[] -> Scatter[] }
 364   auto ReadActions =
 365       give(isl_union_map_apply_domain(Schedule.copy(), Reads.take()));
 366   auto WriteActions =
 367       give(isl_union_map_apply_domain(Schedule.copy(), Writes.copy()));
 368
 369   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 370   auto EltDomWrites = give(isl_union_map_apply_range(
 371       isl_union_map_range_map(isl_union_map_reverse(Writes.copy())),
 372       Schedule.copy()));
 373
 374   // { [Element[] -> Scatter[]] -> DomainWrite[] }
 375   auto ReachingOverwrite = computeReachingWrite(
 376       Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
 377
 378   // { [Element[] -> Scatter[]] -> DomainWrite[] }
 379   auto ReadsOverwritten = give(isl_union_map_intersect_domain(
 380       ReachingOverwrite.take(), isl_union_map_wrap(ReadActions.take())));
 381
 382   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 383   auto ReadsOverwrittenRotated = give(isl_union_map_reverse(
 384       isl_union_map_curry(reverseDomain(ReadsOverwritten).take())));
 385   auto LastOverwrittenRead =
 386       give(isl_union_map_lexmax(ReadsOverwrittenRotated.copy()));
 387
 388   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 389   auto BetweenLastReadOverwrite = betweenScatter(
 390       LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
 391
 392   // { [Element[] -> Scatter[]] -> DomainWrite[] }
 393   isl::union_map ReachingOverwriteZone = computeReachingWrite(
 394       Schedule, Writes, true, IncludeLastRead, IncludeWrite);
 395
 396   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 397   isl::union_map ReachingOverwriteRotated =
 398       reverseDomain(ReachingOverwriteZone).curry().reverse();
 399
 400   // { [Element[] -> DomainWrite[]] -> Scatter[] }
 401   isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
 402       ReadsOverwrittenRotated.domain());
 403
 404   return BetweenLastReadOverwrite.unite(WritesWithoutReads)
 405       .domain_factor_domain();
 406 }
 407
 408 isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
 409                                               bool InclStart, bool InclEnd) {
 410   if (!InclStart && InclEnd)
 411     return Zone;
 412
 413   auto ShiftedZone = shiftDim(Zone, -1, -1);
 414   if (InclStart && !InclEnd)
 415     return ShiftedZone;
 416   else if (!InclStart && !InclEnd)
 417     return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take()));
 418
 419   assert(InclStart && InclEnd);
 420   return give(isl_union_set_union(Zone.take(), ShiftedZone.take()));
 421 }
 422
 423 isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
 424                                               bool InclStart, bool InclEnd) {
 425   if (!InclStart && InclEnd)
 426     return Zone;
 427
 428   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
 429   if (InclStart && !InclEnd)
 430     return ShiftedZone;
 431   else if (!InclStart && !InclEnd)
 432     return give(isl_union_map_intersect(Zone.take(), ShiftedZone.take()));
 433
 434   assert(InclStart && InclEnd);
 435   return give(isl_union_map_union(Zone.take(), ShiftedZone.take()));
 436 }
 437
 438 isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
 439                                         bool InclStart, bool InclEnd) {
 440   if (!InclStart && InclEnd)
 441     return Zone;
 442
 443   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
 444   if (InclStart && !InclEnd)
 445     return ShiftedZone;
 446   else if (!InclStart && !InclEnd)
 447     return give(isl_map_intersect(Zone.take(), ShiftedZone.take()));
 448
 449   assert(InclStart && InclEnd);
 450   return give(isl_map_union(Zone.take(), ShiftedZone.take()));
 451 }
 452
 453 isl::map polly::distributeDomain(isl::map Map) {
 454   // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
 455   // Domain[] -> Range2[] } and combine again. We would loose any relation
 456   // between Range1[] and Range2[] that is not also a constraint to Domain[].
 457
 458   auto Space = give(isl_map_get_space(Map.keep()));
 459   auto DomainSpace = give(isl_space_domain(Space.copy()));
 460   auto DomainDims = isl_space_dim(DomainSpace.keep(), isl_dim_set);
 461   auto RangeSpace = give(isl_space_unwrap(isl_space_range(Space.copy())));
 462   auto Range1Space = give(isl_space_domain(RangeSpace.copy()));
 463   auto Range1Dims = isl_space_dim(Range1Space.keep(), isl_dim_set);
 464   auto Range2Space = give(isl_space_range(RangeSpace.copy()));
 465   auto Range2Dims = isl_space_dim(Range2Space.keep(), isl_dim_set);
 466
 467   auto OutputSpace = give(isl_space_map_from_domain_and_range(
 468       isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
 469                                                          Range1Space.copy())),
 470       isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
 471                                                          Range2Space.copy()))));
 472
 473   auto Translator =
 474       give(isl_basic_map_universe(isl_space_map_from_domain_and_range(
 475           isl_space_wrap(Space.copy()), isl_space_wrap(OutputSpace.copy()))));
 476
 477   for (unsigned i = 0; i < DomainDims; i += 1) {
 478     Translator = give(
 479         isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out, i));
 480     Translator =
 481         give(isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out,
 482                                   DomainDims + Range1Dims + i));
 483   }
 484   for (unsigned i = 0; i < Range1Dims; i += 1) {
 485     Translator =
 486         give(isl_basic_map_equate(Translator.take(), isl_dim_in, DomainDims + i,
 487                                   isl_dim_out, DomainDims + i));
 488   }
 489   for (unsigned i = 0; i < Range2Dims; i += 1) {
 490     Translator = give(isl_basic_map_equate(
 491         Translator.take(), isl_dim_in, DomainDims + Range1Dims + i, isl_dim_out,
 492         DomainDims + Range1Dims + DomainDims + i));
 493   }
 494
 495   return give(isl_set_unwrap(isl_set_apply(
 496       isl_map_wrap(Map.copy()), isl_map_from_basic_map(Translator.copy()))));
 497 }
 498
 499 isl::union_map polly::distributeDomain(isl::union_map UMap) {
 500   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
 501   isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) {
 502     auto Distributed = distributeDomain(Map);
 503     Result = give(isl_union_map_add_map(Result.take(), Distributed.copy()));
 504     return isl::stat::ok;
 505   });
 506   if (Success != isl::stat::ok)
 507     return {};
 508   return Result;
 509 }
 510
 511 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
 512
 513   // { Factor[] -> Factor[] }
 514   auto Factors = makeIdentityMap(std::move(Factor), true);
 515
 516   return std::move(Factors).product(std::move(UMap));
 517 }
 518
 519 isl::union_map polly::applyDomainRange(isl::union_map UMap,
 520                                        isl::union_map Func) {
 521   // This implementation creates unnecessary cross products of the
 522   // DomainDomain[] and Func. An alternative implementation could reverse
 523   // domain+uncurry,apply Func to what now is the domain, then undo the
 524   // preparing transformation. Another alternative implementation could create a
 525   // translator map for each piece.
 526
 527   // { DomainDomain[] }
 528   auto DomainDomain = UMap.domain().unwrap().domain();
 529
 530   // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
 531   // }
 532   auto LifetedFunc = liftDomains(std::move(Func), DomainDomain);
 533
 534   return std::move(UMap).apply_domain(std::move(LifetedFunc));
 535 }