blob: 08bb0529424cf60140b0cbf5a9b0aba558b269a8 [file] [log] [blame]
 //===------ ISLTools.cpp ----------------------------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Tools, utilities, helpers and extensions useful in conjunction with the // Integer Set Library (isl). // //===----------------------------------------------------------------------===// #include "polly/Support/ISLTools.h" #include "llvm/Support/raw_ostream.h" #include #include using namespace polly; namespace { /// Create a map that shifts one dimension by an offset. /// /// Example: /// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2) /// = { [i0, i1] -> [i0, i1 - 1] } /// /// @param Space The map space of the result. Must have equal number of in- and /// out-dimensions. /// @param Pos Position to shift. /// @param Amount Value added to the shifted dimension. /// /// @return An isl_multi_aff for the map with this shifted dimension. isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) { auto Identity = isl::multi_aff::identity(Space); if (Amount == 0) return Identity; auto ShiftAff = Identity.get_aff(Pos); ShiftAff = ShiftAff.set_constant_si(Amount); return Identity.set_aff(Pos, ShiftAff); } /// Construct a map that swaps two nested tuples. /// /// @param FromSpace1 { Space1[] } /// @param FromSpace2 { Space2[] } /// /// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] } isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1, isl::space FromSpace2) { // Fast-path on out-of-quota. if (!FromSpace1 || !FromSpace2) return {}; assert(FromSpace1.is_set()); assert(FromSpace2.is_set()); unsigned Dims1 = FromSpace1.dim(isl::dim::set); unsigned Dims2 = FromSpace2.dim(isl::dim::set); isl::space FromSpace = FromSpace1.map_from_domain_and_range(FromSpace2).wrap(); isl::space ToSpace = FromSpace2.map_from_domain_and_range(FromSpace1).wrap(); isl::space MapSpace = FromSpace.map_from_domain_and_range(ToSpace); isl::basic_map Result = isl::basic_map::universe(MapSpace); for (auto i = Dims1 - Dims1; i < Dims1; i += 1) Result = Result.equate(isl::dim::in, i, isl::dim::out, Dims2 + i); for (auto i = Dims2 - Dims2; i < Dims2; i += 1) { Result = Result.equate(isl::dim::in, Dims1 + i, isl::dim::out, i); } return Result; } /// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns /// an isl_map. isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) { isl::basic_map BMapResult = makeTupleSwapBasicMap(FromSpace1, FromSpace2); return isl::map(BMapResult); } } // anonymous namespace isl::map polly::beforeScatter(isl::map Map, bool Strict) { isl::space RangeSpace = Map.get_space().range(); isl::map ScatterRel = Strict ? isl::map::lex_gt(RangeSpace) : isl::map::lex_ge(RangeSpace); return Map.apply_range(ScatterRel); } isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) { isl::union_map Result = isl::union_map::empty(UMap.get_space()); for (isl::map Map : UMap.get_map_list()) { isl::map After = beforeScatter(Map, Strict); Result = Result.add_map(After); } return Result; } isl::map polly::afterScatter(isl::map Map, bool Strict) { isl::space RangeSpace = Map.get_space().range(); isl::map ScatterRel = Strict ? isl::map::lex_lt(RangeSpace) : isl::map::lex_le(RangeSpace); return Map.apply_range(ScatterRel); } isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) { isl::union_map Result = isl::union_map::empty(UMap.get_space()); for (isl::map Map : UMap.get_map_list()) { isl::map After = afterScatter(Map, Strict); Result = Result.add_map(After); } return Result; } isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom, bool InclTo) { isl::map AfterFrom = afterScatter(From, !InclFrom); isl::map BeforeTo = beforeScatter(To, !InclTo); return AfterFrom.intersect(BeforeTo); } isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To, bool InclFrom, bool InclTo) { isl::union_map AfterFrom = afterScatter(From, !InclFrom); isl::union_map BeforeTo = beforeScatter(To, !InclTo); return AfterFrom.intersect(BeforeTo); } isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) { if (!UMap) return nullptr; if (isl_union_map_n_map(UMap.get()) == 0) return isl::map::empty(ExpectedSpace); isl::map Result = isl::map::from_union_map(UMap); assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace)); return Result; } isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) { if (!USet) return nullptr; if (isl_union_set_n_set(USet.get()) == 0) return isl::set::empty(ExpectedSpace); isl::set Result(USet); assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace)); return Result; } unsigned polly::getNumScatterDims(const isl::union_map &Schedule) { unsigned Dims = 0; for (isl::map Map : Schedule.get_map_list()) Dims = std::max(Dims, Map.dim(isl::dim::out)); return Dims; } isl::space polly::getScatterSpace(const isl::union_map &Schedule) { if (!Schedule) return nullptr; unsigned Dims = getNumScatterDims(Schedule); isl::space ScatterSpace = Schedule.get_space().set_from_params(); return ScatterSpace.add_dims(isl::dim::set, Dims); } isl::union_map polly::makeIdentityMap(const isl::union_set &USet, bool RestrictDomain) { isl::union_map Result = isl::union_map::empty(USet.get_space()); for (isl::set Set : USet.get_set_list()) { isl::map IdentityMap = isl::map::identity(Set.get_space().map_from_set()); if (RestrictDomain) IdentityMap = IdentityMap.intersect_domain(Set); Result = Result.add_map(IdentityMap); } return Result; } isl::map polly::reverseDomain(isl::map Map) { isl::space DomSpace = Map.get_space().domain().unwrap(); isl::space Space1 = DomSpace.domain(); isl::space Space2 = DomSpace.range(); isl::map Swap = makeTupleSwapMap(Space1, Space2); return Map.apply_domain(Swap); } isl::union_map polly::reverseDomain(const isl::union_map &UMap) { isl::union_map Result = isl::union_map::empty(UMap.get_space()); for (isl::map Map : UMap.get_map_list()) { auto Reversed = reverseDomain(std::move(Map)); Result = Result.add_map(Reversed); } return Result; } isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) { int NumDims = Set.dim(isl::dim::set); if (Pos < 0) Pos = NumDims + Pos; assert(Pos < NumDims && "Dimension index must be in range"); isl::space Space = Set.get_space(); Space = Space.map_from_domain_and_range(Space); isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount); isl::map TranslatorMap = isl::map::from_multi_aff(Translator); return Set.apply(TranslatorMap); } isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) { isl::union_set Result = isl::union_set::empty(USet.get_space()); for (isl::set Set : USet.get_set_list()) { isl::set Shifted = shiftDim(Set, Pos, Amount); Result = Result.add_set(Shifted); } return Result; } isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) { int NumDims = Map.dim(Dim); if (Pos < 0) Pos = NumDims + Pos; assert(Pos < NumDims && "Dimension index must be in range"); isl::space Space = Map.get_space(); switch (Dim) { case isl::dim::in: Space = Space.domain(); break; case isl::dim::out: Space = Space.range(); break; default: llvm_unreachable("Unsupported value for 'dim'"); } Space = Space.map_from_domain_and_range(Space); isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount); isl::map TranslatorMap = isl::map::from_multi_aff(Translator); switch (Dim) { case isl::dim::in: return Map.apply_domain(TranslatorMap); case isl::dim::out: return Map.apply_range(TranslatorMap); default: llvm_unreachable("Unsupported value for 'dim'"); } } isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos, int Amount) { isl::union_map Result = isl::union_map::empty(UMap.get_space()); for (isl::map Map : UMap.get_map_list()) { isl::map Shifted = shiftDim(Map, Dim, Pos, Amount); Result = Result.add_map(Shifted); } return Result; } void polly::simplify(isl::set &Set) { Set = isl::manage(isl_set_compute_divs(Set.copy())); Set = Set.detect_equalities(); Set = Set.coalesce(); } void polly::simplify(isl::union_set &USet) { USet = isl::manage(isl_union_set_compute_divs(USet.copy())); USet = USet.detect_equalities(); USet = USet.coalesce(); } void polly::simplify(isl::map &Map) { Map = isl::manage(isl_map_compute_divs(Map.copy())); Map = Map.detect_equalities(); Map = Map.coalesce(); } void polly::simplify(isl::union_map &UMap) { UMap = isl::manage(isl_union_map_compute_divs(UMap.copy())); UMap = UMap.detect_equalities(); UMap = UMap.coalesce(); } isl::union_map polly::computeReachingWrite(isl::union_map Schedule, isl::union_map Writes, bool Reverse, bool InclPrevDef, bool InclNextDef) { // { Scatter[] } isl::space ScatterSpace = getScatterSpace(Schedule); // { ScatterRead[] -> ScatterWrite[] } isl::map Relation; if (Reverse) Relation = InclPrevDef ? isl::map::lex_lt(ScatterSpace) : isl::map::lex_le(ScatterSpace); else Relation = InclNextDef ? isl::map::lex_gt(ScatterSpace) : isl::map::lex_ge(ScatterSpace); // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] } isl::map RelationMap = Relation.range_map().reverse(); // { Element[] -> ScatterWrite[] } isl::union_map WriteAction = Schedule.apply_domain(Writes); // { ScatterWrite[] -> Element[] } isl::union_map WriteActionRev = WriteAction.reverse(); // { Element[] -> [ScatterUse[] -> ScatterWrite[]] } isl::union_map DefSchedRelation = isl::union_map(RelationMap).apply_domain(WriteActionRev); // For each element, at every point in time, map to the times of previous // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] } isl::union_map ReachableWrites = DefSchedRelation.uncurry(); if (Reverse) ReachableWrites = ReachableWrites.lexmin(); else ReachableWrites = ReachableWrites.lexmax(); // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] } isl::union_map SelfUse = WriteAction.range_map(); if (InclPrevDef && InclNextDef) { // Add the Def itself to the solution. ReachableWrites = ReachableWrites.unite(SelfUse).coalesce(); } else if (!InclPrevDef && !InclNextDef) { // Remove Def itself from the solution. ReachableWrites = ReachableWrites.subtract(SelfUse); } // { [Element[] -> ScatterRead[]] -> Domain[] } return ReachableWrites.apply_range(Schedule.reverse()); } isl::union_map polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes, isl::union_map Reads, bool ReadEltInSameInst, bool IncludeLastRead, bool IncludeWrite) { // { Element[] -> Scatter[] } isl::union_map ReadActions = Schedule.apply_domain(Reads); isl::union_map WriteActions = Schedule.apply_domain(Writes); // { [Element[] -> DomainWrite[]] -> Scatter[] } isl::union_map EltDomWrites = Writes.reverse().range_map().apply_range(Schedule); // { [Element[] -> Scatter[]] -> DomainWrite[] } isl::union_map ReachingOverwrite = computeReachingWrite( Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst); // { [Element[] -> Scatter[]] -> DomainWrite[] } isl::union_map ReadsOverwritten = ReachingOverwrite.intersect_domain(ReadActions.wrap()); // { [Element[] -> DomainWrite[]] -> Scatter[] } isl::union_map ReadsOverwrittenRotated = reverseDomain(ReadsOverwritten).curry().reverse(); isl::union_map LastOverwrittenRead = ReadsOverwrittenRotated.lexmax(); // { [Element[] -> DomainWrite[]] -> Scatter[] } isl::union_map BetweenLastReadOverwrite = betweenScatter( LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite); // { [Element[] -> Scatter[]] -> DomainWrite[] } isl::union_map ReachingOverwriteZone = computeReachingWrite( Schedule, Writes, true, IncludeLastRead, IncludeWrite); // { [Element[] -> DomainWrite[]] -> Scatter[] } isl::union_map ReachingOverwriteRotated = reverseDomain(ReachingOverwriteZone).curry().reverse(); // { [Element[] -> DomainWrite[]] -> Scatter[] } isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain( ReadsOverwrittenRotated.domain()); return BetweenLastReadOverwrite.unite(WritesWithoutReads) .domain_factor_domain(); } isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone, bool InclStart, bool InclEnd) { if (!InclStart && InclEnd) return Zone; auto ShiftedZone = shiftDim(Zone, -1, -1); if (InclStart && !InclEnd) return ShiftedZone; else if (!InclStart && !InclEnd) return Zone.intersect(ShiftedZone); assert(InclStart && InclEnd); return Zone.unite(ShiftedZone); } isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim, bool InclStart, bool InclEnd) { if (!InclStart && InclEnd) return Zone; auto ShiftedZone = shiftDim(Zone, Dim, -1, -1); if (InclStart && !InclEnd) return ShiftedZone; else if (!InclStart && !InclEnd) return Zone.intersect(ShiftedZone); assert(InclStart && InclEnd); return Zone.unite(ShiftedZone); } isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim, bool InclStart, bool InclEnd) { if (!InclStart && InclEnd) return Zone; auto ShiftedZone = shiftDim(Zone, Dim, -1, -1); if (InclStart && !InclEnd) return ShiftedZone; else if (!InclStart && !InclEnd) return Zone.intersect(ShiftedZone); assert(InclStart && InclEnd); return Zone.unite(ShiftedZone); } isl::map polly::distributeDomain(isl::map Map) { // Note that we cannot take Map apart into { Domain[] -> Range1[] } and { // Domain[] -> Range2[] } and combine again. We would loose any relation // between Range1[] and Range2[] that is not also a constraint to Domain[]. isl::space Space = Map.get_space(); isl::space DomainSpace = Space.domain(); unsigned DomainDims = DomainSpace.dim(isl::dim::set); isl::space RangeSpace = Space.range().unwrap(); isl::space Range1Space = RangeSpace.domain(); unsigned Range1Dims = Range1Space.dim(isl::dim::set); isl::space Range2Space = RangeSpace.range(); unsigned Range2Dims = Range2Space.dim(isl::dim::set); isl::space OutputSpace = DomainSpace.map_from_domain_and_range(Range1Space) .wrap() .map_from_domain_and_range( DomainSpace.map_from_domain_and_range(Range2Space).wrap()); isl::basic_map Translator = isl::basic_map::universe( Space.wrap().map_from_domain_and_range(OutputSpace.wrap())); for (unsigned i = 0; i < DomainDims; i += 1) { Translator = Translator.equate(isl::dim::in, i, isl::dim::out, i); Translator = Translator.equate(isl::dim::in, i, isl::dim::out, DomainDims + Range1Dims + i); } for (unsigned i = 0; i < Range1Dims; i += 1) Translator = Translator.equate(isl::dim::in, DomainDims + i, isl::dim::out, DomainDims + i); for (unsigned i = 0; i < Range2Dims; i += 1) Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i, isl::dim::out, DomainDims + Range1Dims + DomainDims + i); return Map.wrap().apply(Translator).unwrap(); } isl::union_map polly::distributeDomain(isl::union_map UMap) { isl::union_map Result = isl::union_map::empty(UMap.get_space()); for (isl::map Map : UMap.get_map_list()) { auto Distributed = distributeDomain(Map); Result = Result.add_map(Distributed); } return Result; } isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) { // { Factor[] -> Factor[] } isl::union_map Factors = makeIdentityMap(Factor, true); return Factors.product(UMap); } isl::union_map polly::applyDomainRange(isl::union_map UMap, isl::union_map Func) { // This implementation creates unnecessary cross products of the // DomainDomain[] and Func. An alternative implementation could reverse // domain+uncurry,apply Func to what now is the domain, then undo the // preparing transformation. Another alternative implementation could create a // translator map for each piece. // { DomainDomain[] } isl::union_set DomainDomain = UMap.domain().unwrap().domain(); // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]] // } isl::union_map LifetedFunc = liftDomains(std::move(Func), DomainDomain); return UMap.apply_domain(LifetedFunc); } isl::map polly::intersectRange(isl::map Map, isl::union_set Range) { isl::set RangeSet = Range.extract_set(Map.get_space().range()); return Map.intersect_range(RangeSet); } isl::map polly::subtractParams(isl::map Map, isl::set Params) { auto MapSpace = Map.get_space(); auto ParamsMap = isl::map::universe(MapSpace).intersect_params(Params); return Map.subtract(ParamsMap); } isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) { assert(!Max || !Min); // Cannot return min and max at the same time. isl::val Result; isl::stat Stat = PwAff.foreach_piece( [=, &Result](isl::set Set, isl::aff Aff) -> isl::stat { if (Result && Result.is_nan()) return isl::stat::ok(); // TODO: If Min/Max, we can also determine a minimum/maximum value if // Set is constant-bounded. if (!Aff.is_cst()) { Result = isl::val::nan(Aff.get_ctx()); return isl::stat::error(); } isl::val ThisVal = Aff.get_constant_val(); if (!Result) { Result = ThisVal; return isl::stat::ok(); } if (Result.eq(ThisVal)) return isl::stat::ok(); if (Max && ThisVal.gt(Result)) { Result = ThisVal; return isl::stat::ok(); } if (Min && ThisVal.lt(Result)) { Result = ThisVal; return isl::stat::ok(); } // Not compatible Result = isl::val::nan(Aff.get_ctx()); return isl::stat::error(); }); if (Stat.is_error()) return {}; return Result; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) static void foreachPoint(const isl::set &Set, const std::function &F) { Set.foreach_point([&](isl::point P) -> isl::stat { F(P); return isl::stat::ok(); }); } static void foreachPoint(isl::basic_set BSet, const std::function &F) { foreachPoint(isl::set(BSet), F); } /// Determine the sorting order of the sets @p A and @p B without considering /// the space structure. /// /// Ordering is based on the lower bounds of the set's dimensions. First /// dimensions are considered first. static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) { unsigned ALen = A.dim(isl::dim::set); unsigned BLen = B.dim(isl::dim::set); unsigned Len = std::min(ALen, BLen); for (unsigned i = 0; i < Len; i += 1) { isl::basic_set ADim = A.project_out(isl::dim::param, 0, A.dim(isl::dim::param)) .project_out(isl::dim::set, i + 1, ALen - i - 1) .project_out(isl::dim::set, 0, i); isl::basic_set BDim = B.project_out(isl::dim::param, 0, B.dim(isl::dim::param)) .project_out(isl::dim::set, i + 1, BLen - i - 1) .project_out(isl::dim::set, 0, i); isl::basic_set AHull = isl::set(ADim).convex_hull(); isl::basic_set BHull = isl::set(BDim).convex_hull(); bool ALowerBounded = bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0)); bool BLowerBounded = bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0)); int BoundedCompare = BLowerBounded - ALowerBounded; if (BoundedCompare != 0) return BoundedCompare; if (!ALowerBounded || !BLowerBounded) continue; isl::pw_aff AMin = isl::set(ADim).dim_min(0); isl::pw_aff BMin = isl::set(BDim).dim_min(0); isl::val AMinVal = polly::getConstant(AMin, false, true); isl::val BMinVal = polly::getConstant(BMin, false, true); int MinCompare = AMinVal.sub(BMinVal).sgn(); if (MinCompare != 0) return MinCompare; } // If all the dimensions' lower bounds are equal or incomparable, sort based // on the number of dimensions. return ALen - BLen; } /// Compare the sets @p A and @p B according to their nested space structure. /// Returns 0 if the structure is considered equal. /// If @p ConsiderTupleLen is false, the number of dimensions in a tuple are /// ignored, i.e. a tuple with the same name but different number of dimensions /// are considered equal. static int structureCompare(const isl::space &ASpace, const isl::space &BSpace, bool ConsiderTupleLen) { int WrappingCompare = bool(ASpace.is_wrapping()) - bool(BSpace.is_wrapping()); if (WrappingCompare != 0) return WrappingCompare; if (ASpace.is_wrapping() && BSpace.is_wrapping()) { isl::space AMap = ASpace.unwrap(); isl::space BMap = BSpace.unwrap(); int FirstResult = structureCompare(AMap.domain(), BMap.domain(), ConsiderTupleLen); if (FirstResult != 0) return FirstResult; return structureCompare(AMap.range(), BMap.range(), ConsiderTupleLen); } std::string AName; if (ASpace.has_tuple_name(isl::dim::set)) AName = ASpace.get_tuple_name(isl::dim::set); std::string BName; if (BSpace.has_tuple_name(isl::dim::set)) BName = BSpace.get_tuple_name(isl::dim::set); int NameCompare = AName.compare(BName); if (NameCompare != 0) return NameCompare; if (ConsiderTupleLen) { int LenCompare = BSpace.dim(isl::dim::set) - ASpace.dim(isl::dim::set); if (LenCompare != 0) return LenCompare; } return 0; } /// Compare the sets @p A and @p B according to their nested space structure. If /// the structure is the same, sort using the dimension lower bounds. /// Returns an std::sort compatible bool. static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) { isl::space ASpace = A.get_space(); isl::space BSpace = B.get_space(); // Ignoring number of dimensions first ensures that structures with same tuple // names, but different number of dimensions are still sorted close together. int TupleNestingCompare = structureCompare(ASpace, BSpace, false); if (TupleNestingCompare != 0) return TupleNestingCompare < 0; int TupleCompare = structureCompare(ASpace, BSpace, true); if (TupleCompare != 0) return TupleCompare < 0; return flatCompare(A, B) < 0; } /// Print a string representation of @p USet to @p OS. /// /// The pieces of @p USet are printed in a sorted order. Spaces with equal or /// similar nesting structure are printed together. Compared to isl's own /// printing function the uses the structure itself as base of the sorting, not /// a hash of it. It ensures that e.g. maps spaces with same domain structure /// are printed together. Set pieces with same structure are printed in order of /// their lower bounds. /// /// @param USet Polyhedra to print. /// @param OS Target stream. /// @param Simplify Whether to simplify the polyhedron before printing. /// @param IsMap Whether @p USet is a wrapped map. If true, sets are /// unwrapped before printing to again appear as a map. static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS, bool Simplify, bool IsMap) { if (!USet) { OS << "\n"; return; } if (Simplify) simplify(USet); // Get all the polyhedra. std::vector BSets; for (isl::set Set : USet.get_set_list()) { for (isl::basic_set BSet : Set.get_basic_set_list()) { BSets.push_back(BSet); } } if (BSets.empty()) { OS << "{\n}\n"; return; } // Sort the polyhedra. llvm::sort(BSets, orderComparer); // Print the polyhedra. bool First = true; for (const isl::basic_set &BSet : BSets) { std::string Str; if (IsMap) Str = isl::map(BSet.unwrap()).to_str(); else Str = isl::set(BSet).to_str(); size_t OpenPos = Str.find_first_of('{'); assert(OpenPos != std::string::npos); size_t ClosePos = Str.find_last_of('}'); assert(ClosePos != std::string::npos); if (First) OS << llvm::StringRef(Str).substr(0, OpenPos + 1) << "\n "; else OS << ";\n "; OS << llvm::StringRef(Str).substr(OpenPos + 1, ClosePos - OpenPos - 2); First = false; } assert(!First); OS << "\n}\n"; } static void recursiveExpand(isl::basic_set BSet, int Dim, isl::set &Expanded) { int Dims = BSet.dim(isl::dim::set); if (Dim >= Dims) { Expanded = Expanded.unite(BSet); return; } isl::basic_set DimOnly = BSet.project_out(isl::dim::param, 0, BSet.dim(isl::dim::param)) .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1) .project_out(isl::dim::set, 0, Dim); if (!DimOnly.is_bounded()) { recursiveExpand(BSet, Dim + 1, Expanded); return; } foreachPoint(DimOnly, [&, Dim](isl::point P) { isl::val Val = P.get_coordinate_val(isl::dim::set, 0); isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val); recursiveExpand(FixBSet, Dim + 1, Expanded); }); } /// Make each point of a set explicit. /// /// "Expanding" makes each point a set contains explicit. That is, the result is /// a set of singleton polyhedra. Unbounded dimensions are not expanded. /// /// Example: /// { [i] : 0 <= i < 2 } /// is expanded to: /// { [0]; [1] } static isl::set expand(const isl::set &Set) { isl::set Expanded = isl::set::empty(Set.get_space()); for (isl::basic_set BSet : Set.get_basic_set_list()) recursiveExpand(BSet, 0, Expanded); return Expanded; } /// Expand all points of a union set explicit. /// /// @see expand(const isl::set) static isl::union_set expand(const isl::union_set &USet) { isl::union_set Expanded = isl::union_set::empty(USet.get_space()); for (isl::set Set : USet.get_set_list()) { isl::set SetExpanded = expand(Set); Expanded = Expanded.add_set(SetExpanded); } return Expanded; } LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) { printSortedPolyhedra(Set, llvm::errs(), true, false); } LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) { printSortedPolyhedra(Map.wrap(), llvm::errs(), true, true); } LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) { printSortedPolyhedra(USet, llvm::errs(), true, false); } LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) { printSortedPolyhedra(UMap.wrap(), llvm::errs(), true, true); } LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_set *Set) { dumpPw(isl::manage_copy(Set)); } LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_map *Map) { dumpPw(isl::manage_copy(Map)); } LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_set *USet) { dumpPw(isl::manage_copy(USet)); } LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_map *UMap) { dumpPw(isl::manage_copy(UMap)); } LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) { printSortedPolyhedra(expand(Set), llvm::errs(), false, false); } LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) { printSortedPolyhedra(expand(Map.wrap()), llvm::errs(), false, true); } LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) { printSortedPolyhedra(expand(USet), llvm::errs(), false, false); } LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) { printSortedPolyhedra(expand(UMap.wrap()), llvm::errs(), false, true); } LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_set *Set) { dumpExpanded(isl::manage_copy(Set)); } LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_map *Map) { dumpExpanded(isl::manage_copy(Map)); } LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_set *USet) { dumpExpanded(isl::manage_copy(USet)); } LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_map *UMap) { dumpExpanded(isl::manage_copy(UMap)); } #endif