35 isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {  in makeShiftDimAff()
36   auto Identity = isl::multi_aff::identity(Space);  in makeShiftDimAff()
50 isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,  in makeTupleSwapBasicMap()
51                                      isl::space FromSpace2) {  in makeTupleSwapBasicMap()
59   unsigned Dims1 = unsignedFromIslSize(FromSpace1.dim(isl::dim::set));  in makeTupleSwapBasicMap()
60   unsigned Dims2 = unsignedFromIslSize(FromSpace2.dim(isl::dim::set));  in makeTupleSwapBasicMap()
62   isl::space FromSpace =  in makeTupleSwapBasicMap()
64   isl::space ToSpace = FromSpace2.map_from_domain_and_range(FromSpace1).wrap();  in makeTupleSwapBasicMap()
65   isl::space MapSpace = FromSpace.map_from_domain_and_range(ToSpace);  in makeTupleSwapBasicMap()
67   isl::basic_map Result = isl::basic_map::universe(MapSpace);  in makeTupleSwapBasicMap()
69     Result = Result.equate(isl::dim::in, i, isl::dim::out, Dims2 + i);  in makeTupleSwapBasicMap()
71     Result = Result.equate(isl::dim::in, Dims1 + i, isl::dim::out, i);  in makeTupleSwapBasicMap()
79 isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {  in makeTupleSwapMap()
80   isl::basic_map BMapResult = makeTupleSwapBasicMap(FromSpace1, FromSpace2);  in makeTupleSwapMap()
81   return isl::map(BMapResult);  in makeTupleSwapMap()
85 isl::map polly::beforeScatter(isl::map Map, bool Strict) {  in beforeScatter()
86   isl::space RangeSpace = Map.get_space().range();  in beforeScatter()
87   isl::map ScatterRel =  in beforeScatter()
88       Strict ? isl::map::lex_gt(RangeSpace) : isl::map::lex_ge(RangeSpace);  in beforeScatter()
92 isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {  in beforeScatter()
93   isl::union_map Result = isl::union_map::empty(UMap.ctx());  in beforeScatter()
95   for (isl::map Map : UMap.get_map_list()) {  in beforeScatter()
96     isl::map After = beforeScatter(Map, Strict);  in beforeScatter()
103 isl::map polly::afterScatter(isl::map Map, bool Strict) {  in afterScatter()
104   isl::space RangeSpace = Map.get_space().range();  in afterScatter()
105   isl::map ScatterRel =  in afterScatter()
106       Strict ? isl::map::lex_lt(RangeSpace) : isl::map::lex_le(RangeSpace);  in afterScatter()
110 isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {  in afterScatter()
111   isl::union_map Result = isl::union_map::empty(UMap.ctx());  in afterScatter()
112   for (isl::map Map : UMap.get_map_list()) {  in afterScatter()
113     isl::map After = afterScatter(Map, Strict);  in afterScatter()
119 isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,  in betweenScatter()
121   isl::map AfterFrom = afterScatter(From, !InclFrom);  in betweenScatter()
122   isl::map BeforeTo = beforeScatter(To, !InclTo);  in betweenScatter()
127 isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,  in betweenScatter()
129   isl::union_map AfterFrom = afterScatter(From, !InclFrom);  in betweenScatter()
130   isl::union_map BeforeTo = beforeScatter(To, !InclTo);  in betweenScatter()
135 isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {  in singleton()
140     return isl::map::empty(ExpectedSpace);  in singleton()
142   isl::map Result = isl::map::from_union_map(UMap);  in singleton()
149 isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {  in singleton()
154     return isl::set::empty(ExpectedSpace);  in singleton()
156   isl::set Result(USet);  in singleton()
163 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {  in getNumScatterDims()
165   for (isl::map Map : Schedule.get_map_list()) {  in getNumScatterDims()
174 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {  in getScatterSpace()
178   isl::space ScatterSpace = Schedule.get_space().set_from_params();  in getScatterSpace()
179   return ScatterSpace.add_dims(isl::dim::set, Dims);  in getScatterSpace()
182 isl::map polly::makeIdentityMap(const isl::set &Set, bool RestrictDomain) {  in makeIdentityMap()
183   isl::map Result = isl::map::identity(Set.get_space().map_from_set());  in makeIdentityMap()
189 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,  in makeIdentityMap()
191   isl::union_map Result = isl::union_map::empty(USet.ctx());  in makeIdentityMap()
192   for (isl::set Set : USet.get_set_list()) {  in makeIdentityMap()
193     isl::map IdentityMap = makeIdentityMap(Set, RestrictDomain);  in makeIdentityMap()
199 isl::map polly::reverseDomain(isl::map Map) {  in reverseDomain()
200   isl::space DomSpace = Map.get_space().domain().unwrap();  in reverseDomain()
201   isl::space Space1 = DomSpace.domain();  in reverseDomain()
202   isl::space Space2 = DomSpace.range();  in reverseDomain()
203   isl::map Swap = makeTupleSwapMap(Space1, Space2);  in reverseDomain()
207 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {  in reverseDomain()
208   isl::union_map Result = isl::union_map::empty(UMap.ctx());  in reverseDomain()
209   for (isl::map Map : UMap.get_map_list()) {  in reverseDomain()
216 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {  in shiftDim()
221   isl::space Space = Set.get_space();  in shiftDim()
223   isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);  in shiftDim()
224   isl::map TranslatorMap = isl::map::from_multi_aff(Translator);  in shiftDim()
228 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {  in shiftDim()
229   isl::union_set Result = isl::union_set::empty(USet.ctx());  in shiftDim()
230   for (isl::set Set : USet.get_set_list()) {  in shiftDim()
231     isl::set Shifted = shiftDim(Set, Pos, Amount);  in shiftDim()
237 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {  in shiftDim()
242   isl::space Space = Map.get_space();  in shiftDim()
244   case isl::dim::in:  in shiftDim()
247   case isl::dim::out:  in shiftDim()
254   isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);  in shiftDim()
255   isl::map TranslatorMap = isl::map::from_multi_aff(Translator);  in shiftDim()
257   case isl::dim::in:  in shiftDim()
259   case isl::dim::out:  in shiftDim()
266 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,  in shiftDim()
268   isl::union_map Result = isl::union_map::empty(UMap.ctx());  in shiftDim()
270   for (isl::map Map : UMap.get_map_list()) {  in shiftDim()
271     isl::map Shifted = shiftDim(Map, Dim, Pos, Amount);  in shiftDim()
277 void polly::simplify(isl::set &Set) {  in simplify()
278   Set = isl::manage(isl_set_compute_divs(Set.copy()));  in simplify()
283 void polly::simplify(isl::union_set &USet) {  in simplify()
284   USet = isl::manage(isl_union_set_compute_divs(USet.copy()));  in simplify()
289 void polly::simplify(isl::map &Map) {  in simplify()
290   Map = isl::manage(isl_map_compute_divs(Map.copy()));  in simplify()
295 void polly::simplify(isl::union_map &UMap) {  in simplify()
296   UMap = isl::manage(isl_union_map_compute_divs(UMap.copy()));  in simplify()
301 isl::union_map polly::computeReachingWrite(isl::union_map Schedule,  in computeReachingWrite()
302                                            isl::union_map Writes, bool Reverse,  in computeReachingWrite()
306   isl::space ScatterSpace = getScatterSpace(Schedule);  in computeReachingWrite()
309   isl::map Relation;  in computeReachingWrite()
311     Relation = InclPrevDef ? isl::map::lex_lt(ScatterSpace)  in computeReachingWrite()
312                            : isl::map::lex_le(ScatterSpace);  in computeReachingWrite()
314     Relation = InclNextDef ? isl::map::lex_gt(ScatterSpace)  in computeReachingWrite()
315                            : isl::map::lex_ge(ScatterSpace);  in computeReachingWrite()
318   isl::map RelationMap = Relation.range_map().reverse();  in computeReachingWrite()
321   isl::union_map WriteAction = Schedule.apply_domain(Writes);  in computeReachingWrite()
324   isl::union_map WriteActionRev = WriteAction.reverse();  in computeReachingWrite()
327   isl::union_map DefSchedRelation =  in computeReachingWrite()
328       isl::union_map(RelationMap).apply_domain(WriteActionRev);  in computeReachingWrite()
332   isl::union_map ReachableWrites = DefSchedRelation.uncurry();  in computeReachingWrite()
339   isl::union_map SelfUse = WriteAction.range_map();  in computeReachingWrite()
353 isl::union_map
354 polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,  in computeArrayUnused()
355                           isl::union_map Reads, bool ReadEltInSameInst,  in computeArrayUnused()
358   isl::union_map ReadActions = Schedule.apply_domain(Reads);  in computeArrayUnused()
359   isl::union_map WriteActions = Schedule.apply_domain(Writes);  in computeArrayUnused()
362   isl::union_map EltDomWrites =  in computeArrayUnused()
366   isl::union_map ReachingOverwrite = computeReachingWrite(  in computeArrayUnused()
370   isl::union_map ReadsOverwritten =  in computeArrayUnused()
374   isl::union_map ReadsOverwrittenRotated =  in computeArrayUnused()
376   isl::union_map LastOverwrittenRead = ReadsOverwrittenRotated.lexmax();  in computeArrayUnused()
379   isl::union_map BetweenLastReadOverwrite = betweenScatter(  in computeArrayUnused()
383   isl::union_map ReachingOverwriteZone = computeReachingWrite(  in computeArrayUnused()
387   isl::union_map ReachingOverwriteRotated =  in computeArrayUnused()
391   isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(  in computeArrayUnused()
398 isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,  in convertZoneToTimepoints()
413 isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,  in convertZoneToTimepoints()
428 isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,  in convertZoneToTimepoints()
443 isl::map polly::distributeDomain(isl::map Map) {  in distributeDomain()
448   isl::space Space = Map.get_space();  in distributeDomain()
449   isl::space DomainSpace = Space.domain();  in distributeDomain()
452   unsigned DomainDims = unsignedFromIslSize(DomainSpace.dim(isl::dim::set));  in distributeDomain()
453   isl::space RangeSpace = Space.range().unwrap();  in distributeDomain()
454   isl::space Range1Space = RangeSpace.domain();  in distributeDomain()
457   unsigned Range1Dims = unsignedFromIslSize(Range1Space.dim(isl::dim::set));  in distributeDomain()
458   isl::space Range2Space = RangeSpace.range();  in distributeDomain()
461   unsigned Range2Dims = unsignedFromIslSize(Range2Space.dim(isl::dim::set));  in distributeDomain()
463   isl::space OutputSpace =  in distributeDomain()
469   isl::basic_map Translator = isl::basic_map::universe(  in distributeDomain()
473     Translator = Translator.equate(isl::dim::in, i, isl::dim::out, i);  in distributeDomain()
474     Translator = Translator.equate(isl::dim::in, i, isl::dim::out,  in distributeDomain()
478     Translator = Translator.equate(isl::dim::in, DomainDims + i, isl::dim::out,  in distributeDomain()
481     Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i,  in distributeDomain()
482                                    isl::dim::out,  in distributeDomain()
488 isl::union_map polly::distributeDomain(isl::union_map UMap) {  in distributeDomain()
489   isl::union_map Result = isl::union_map::empty(UMap.ctx());  in distributeDomain()
490   for (isl::map Map : UMap.get_map_list()) {  in distributeDomain()
497 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {  in liftDomains()
500   isl::union_map Factors = makeIdentityMap(Factor, true);  in liftDomains()
505 isl::union_map polly::applyDomainRange(isl::union_map UMap,  in applyDomainRange()
506                                        isl::union_map Func) {  in applyDomainRange()
514   isl::union_set DomainDomain = UMap.domain().unwrap().domain();  in applyDomainRange()
518   isl::union_map LifetedFunc = liftDomains(std::move(Func), DomainDomain);  in applyDomainRange()
523 isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {  in intersectRange()
524   isl::set RangeSet = Range.extract_set(Map.get_space().range());  in intersectRange()
528 isl::map polly::subtractParams(isl::map Map, isl::set Params) {  in subtractParams()
530   auto ParamsMap = isl::map::universe(MapSpace).intersect_params(Params);  in subtractParams()
534 isl::set polly::subtractParams(isl::set Set, isl::set Params) {  in subtractParams()
535   isl::space SetSpace = Set.get_space();  in subtractParams()
536   isl::set ParamsSet = isl::set::universe(SetSpace).intersect_params(Params);  in subtractParams()
540 isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {  in getConstant()
542   isl::val Result;  in getConstant()
543   isl::stat Stat = PwAff.foreach_piece(  in getConstant()
544       [=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {  in getConstant()
546           return isl::stat::ok();  in getConstant()
551           Result = isl::val::nan(Aff.ctx());  in getConstant()
552           return isl::stat::error();  in getConstant()
555         isl::val ThisVal = Aff.get_constant_val();  in getConstant()
558           return isl::stat::ok();  in getConstant()
562           return isl::stat::ok();  in getConstant()
566           return isl::stat::ok();  in getConstant()
571           return isl::stat::ok();  in getConstant()
575         Result = isl::val::nan(Aff.ctx());  in getConstant()
576         return isl::stat::error();  in getConstant()
585 llvm::iota_range<unsigned> polly::rangeIslSize(unsigned Begin, isl::size End) {  in rangeIslSize()
591 static void foreachPoint(const isl::set &Set,  in foreachPoint()
592                          const std::function<void(isl::point P)> &F) {  in foreachPoint()
593   Set.foreach_point([&](isl::point P) -> isl::stat {  in foreachPoint()
595     return isl::stat::ok();  in foreachPoint()
599 static void foreachPoint(isl::basic_set BSet,  in foreachPoint()
600                          const std::function<void(isl::point P)> &F) {  in foreachPoint()
601   foreachPoint(isl::set(BSet), F);  in foreachPoint()
609 static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {  in flatCompare()
614   unsigned ALen = unsignedFromIslSize(A.dim(isl::dim::set));  in flatCompare()
615   unsigned BLen = unsignedFromIslSize(B.dim(isl::dim::set));  in flatCompare()
619     isl::basic_set ADim =  in flatCompare()
620         A.project_out(isl::dim::param, 0,  in flatCompare()
621                       unsignedFromIslSize(A.dim(isl::dim::param)))  in flatCompare()
622             .project_out(isl::dim::set, i + 1, ALen - i - 1)  in flatCompare()
623             .project_out(isl::dim::set, 0, i);  in flatCompare()
624     isl::basic_set BDim =  in flatCompare()
625         B.project_out(isl::dim::param, 0,  in flatCompare()
626                       unsignedFromIslSize(B.dim(isl::dim::param)))  in flatCompare()
627             .project_out(isl::dim::set, i + 1, BLen - i - 1)  in flatCompare()
628             .project_out(isl::dim::set, 0, i);  in flatCompare()
630     isl::basic_set AHull = isl::set(ADim).convex_hull();  in flatCompare()
631     isl::basic_set BHull = isl::set(BDim).convex_hull();  in flatCompare()
634         bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0));  in flatCompare()
636         bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0));  in flatCompare()
645     isl::pw_aff AMin = isl::set(ADim).dim_min(0);  in flatCompare()
646     isl::pw_aff BMin = isl::set(BDim).dim_min(0);  in flatCompare()
648     isl::val AMinVal = polly::getConstant(AMin, false, true);  in flatCompare()
649     isl::val BMinVal = polly::getConstant(BMin, false, true);  in flatCompare()
666 static int structureCompare(const isl::space &ASpace, const isl::space &BSpace,  in structureCompare()
673     isl::space AMap = ASpace.unwrap();  in structureCompare()
674     isl::space BMap = BSpace.unwrap();  in structureCompare()
685   if (!ASpace.is_params() && ASpace.has_tuple_name(isl::dim::set))  in structureCompare()
686     AName = ASpace.get_tuple_name(isl::dim::set);  in structureCompare()
689   if (!BSpace.is_params() && BSpace.has_tuple_name(isl::dim::set))  in structureCompare()
690     BName = BSpace.get_tuple_name(isl::dim::set);  in structureCompare()
697     int LenCompare = (int)unsignedFromIslSize(BSpace.dim(isl::dim::set)) -  in structureCompare()
698                      (int)unsignedFromIslSize(ASpace.dim(isl::dim::set));  in structureCompare()
709 static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) {  in orderComparer()
710   isl::space ASpace = A.get_space();  in orderComparer()
711   isl::space BSpace = B.get_space();  in orderComparer()
740 static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS,  in printSortedPolyhedra()
751   std::vector<isl::basic_set> BSets;  in printSortedPolyhedra()
753   for (isl::set Set : USet.get_set_list()) {  in printSortedPolyhedra()
754     for (isl::basic_set BSet : Set.get_basic_set_list()) {  in printSortedPolyhedra()
769   for (const isl::basic_set &BSet : BSets) {  in printSortedPolyhedra()
772       Str = stringFromIslObj(isl::map(BSet.unwrap()));  in printSortedPolyhedra()
774       Str = stringFromIslObj(isl::set(BSet));  in printSortedPolyhedra()
792 static void recursiveExpand(isl::basic_set BSet, unsigned Dim,  in recursiveExpand()
793                             isl::set &Expanded) {  in recursiveExpand()
794   unsigned Dims = unsignedFromIslSize(BSet.dim(isl::dim::set));  in recursiveExpand()
800   isl::basic_set DimOnly =  in recursiveExpand()
801       BSet.project_out(isl::dim::param, 0,  in recursiveExpand()
802                        unsignedFromIslSize(BSet.dim(isl::dim::param)))  in recursiveExpand()
803           .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1)  in recursiveExpand()
804           .project_out(isl::dim::set, 0, Dim);  in recursiveExpand()
810   foreachPoint(DimOnly, [&, Dim](isl::point P) {  in recursiveExpand()
811     isl::val Val = P.get_coordinate_val(isl::dim::set, 0);  in recursiveExpand()
812     isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val);  in recursiveExpand()
826 static isl::set expand(const isl::set &Set) {  in expand()
827   isl::set Expanded = isl::set::empty(Set.get_space());  in expand()
828   for (isl::basic_set BSet : Set.get_basic_set_list())  in expand()
836 static isl::union_set expand(const isl::union_set &USet) {  in expand()
837   isl::union_set Expanded = isl::union_set::empty(USet.ctx());  in expand()
838   for (isl::set Set : USet.get_set_list()) {  in expand()
839     isl::set SetExpanded = expand(Set);  in expand()
845 LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {  in dumpPw()
849 LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {  in dumpPw()
853 LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) {  in dumpPw()
857 LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) {  in dumpPw()
862   dumpPw(isl::manage_copy(Set));  in dumpPw()
866   dumpPw(isl::manage_copy(Map));  in dumpPw()
870   dumpPw(isl::manage_copy(USet));  in dumpPw()
874   dumpPw(isl::manage_copy(UMap));  in dumpPw()
877 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) {  in dumpExpanded()
881 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) {  in dumpExpanded()
885 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) {  in dumpExpanded()
889 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) {  in dumpExpanded()
894   dumpExpanded(isl::manage_copy(Set));  in dumpExpanded()
898   dumpExpanded(isl::manage_copy(Map));  in dumpExpanded()
902   dumpExpanded(isl::manage_copy(USet));  in dumpExpanded()
906   dumpExpanded(isl::manage_copy(UMap));  in dumpExpanded()