Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -49,6 +49,7 @@ struct isl_ast_build; struct isl_constraint; struct isl_pw_multi_aff; +struct isl_schedule; namespace polly { @@ -422,36 +423,6 @@ /// instance. isl_set *Domain; - /// The schedule map describes the execution order of the statement - /// instances. - /// - /// A statement and its iteration domain do not give any information about the - /// order in time in which the different statement instances are executed. - /// This information is provided by the schedule. - /// - /// The schedule maps every instance of each statement into a multi - /// dimensional schedule space. This space can be seen as a multi - /// dimensional clock. - /// - /// Example: - /// - /// may be mapped to (5,4) by this schedule: - /// - /// s0 = i (Year of execution) - /// s1 = j (Day of execution) - /// - /// or to (9, 20) by this schedule: - /// - /// s0 = i + j (Year of execution) - /// s1 = 20 (Day of execution) - /// - /// The order statement instances are executed is defined by the - /// schedule vectors they are mapped to. A statement instance - /// is executed before a statement instance , if - /// the schedule vector of A is lexicographic smaller than the schedule - /// vector of B. - isl_map *Schedule; - /// The memory accesses of this statement. /// /// The only side effects of a statement are its memory accesses. @@ -492,7 +463,6 @@ __isl_give isl_set *addLoopBoundsToDomain(__isl_take isl_set *Domain, TempScop &tempScop); __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion); - void buildSchedule(SmallVectorImpl &ScheduleVec); /// @brief Create the accesses for instructions in @p Block. /// @@ -548,13 +518,11 @@ /// Create the ScopStmt from a BasicBlock. ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, - BasicBlock &bb, SmallVectorImpl &NestLoops, - SmallVectorImpl &ScheduleVec); + BasicBlock &bb, SmallVectorImpl &NestLoops); /// Create an overapproximating ScopStmt for the region @p R. ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, Region &R, - SmallVectorImpl &NestLoops, - SmallVectorImpl &ScheduleVec); + SmallVectorImpl &NestLoops); friend class Scop; @@ -586,7 +554,6 @@ /// /// @return The schedule function of this ScopStmt. __isl_give isl_map *getSchedule() const; - void setSchedule(__isl_take isl_map *Schedule); /// @brief Get an isl string representing this schedule. std::string getScheduleStr() const; @@ -638,7 +605,6 @@ unsigned getNumParams() const; unsigned getNumIterators() const; - unsigned getNumSchedule() const; Scop *getParent() { return &Parent; } const Scop *getParent() const { return &Parent; } @@ -757,6 +723,42 @@ /// this scop and that need to be code generated as a run-time test. isl_set *AssumedContext; + /// @brief The schedule of the SCoP + /// + /// The schedule of the SCoP describes the execution order of the statements + /// in the scop by assigning each statement instance a possibly + /// multi-dimensional execution time. The schedule is stored as a tree of + /// schedule nodes. + /// + /// The most common nodes in a schedule tree are so-called band nodes. Band + /// nodes map statement instances into a multi dimensional schedule space. + /// This space can be seen as a multi-dimensional clock. + /// + /// Example: + /// + /// may be mapped to (5,4) by this schedule: + /// + /// s0 = i (Year of execution) + /// s1 = j (Day of execution) + /// + /// or to (9, 20) by this schedule: + /// + /// s0 = i + j (Year of execution) + /// s1 = 20 (Day of execution) + /// + /// The order statement instances are executed is defined by the + /// schedule vectors they are mapped to. A statement instance + /// is executed before a statement instance , if + /// the schedule vector of A is lexicographic smaller than the schedule + /// vector of B. + /// + /// Besides band nodes, schedule trees contain additional nodes that specify + /// a textual ordering between two subtrees or filter nodes that filter the + /// set of statement instances that will be scheduled in a subtree. There + /// are also several other nodes. A full description of the different nodes + /// in a schedule tree is given in the isl manual. + isl_schedule *Schedule; + /// @brief The set of minimal/maximal accesses for each alias group. /// /// When building runtime alias checks we look at all memory instructions and @@ -807,18 +809,23 @@ /// @param tempScop The temp SCoP we use as model. /// @param CurRegion The SCoP region. /// @param NestLoops A vector of all surrounding loops. - /// @param Schedule The position of the new statement as schedule. - void addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, - const Region &CurRegion, SmallVectorImpl &NestLoops, - SmallVectorImpl &Schedule); - - /// Build the Scop and Statement with precalculated scop information. - void buildScop(TempScop &TempScop, const Region &CurRegion, - // Loops in Scop containing CurRegion - SmallVectorImpl &NestLoops, - // The schedule numbers - SmallVectorImpl &Schedule, LoopInfo &LI, - ScopDetection &SD); + ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, + const Region &CurRegion, + SmallVectorImpl &NestLoops); + + /// @brief Build Scop and ScopStmts from a given TempScop. + /// + /// @param TempScop The temporary scop that is translated into an actual + /// scop. + /// @param CurRegion The subregion of the current scop that we are currently + /// translating. + /// @param NestLoop The set of loops that surround the current subregion. + /// @param LI The LoopInfo object. + /// @param SD The ScopDetection object. + __isl_give isl_schedule *buildScop(TempScop &TempScop, + const Region &CurRegion, + SmallVectorImpl &NestLoops, + LoopInfo &LI, ScopDetection &SD); /// @name Helper function for printing the Scop. /// @@ -881,18 +888,6 @@ /// @return The maximum depth of the loop. inline unsigned getMaxLoopDepth() const { return MaxLoopDepth; } - /// @brief Get the schedule dimension number of this Scop. - /// - /// @return The schedule dimension number of this Scop. - inline unsigned getScheduleDim() const { - unsigned maxScheduleDim = 0; - - for (const_iterator SI = begin(), SE = end(); SI != SE; ++SI) - maxScheduleDim = std::max(maxScheduleDim, (*SI)->getNumSchedule()); - - return maxScheduleDim; - } - /// @brief Mark the SCoP as optimized by the scheduler. void markAsOptimized() { IsOptimized = true; } @@ -933,13 +928,6 @@ /// @returns True if __no__ error occurred, false otherwise. bool buildAliasGroups(AliasAnalysis &AA); - //// @brief Drop all constant dimensions from statment schedules. - /// - /// Schedule dimensions that are constant accross the scop do not carry - /// any information, but would cost compile time due to the increased number - /// of schedule dimensions. To not pay this cost, we remove them. - void dropConstantScheduleDims(); - /// @brief Return all alias groups for this SCoP. const MinMaxVectorVectorTy &getAliasGroups() const { return MinMaxAliasGroups; @@ -1005,7 +993,7 @@ isl_ctx *getIslCtx() const; /// @brief Get a union set containing the iteration domains of all statements. - __isl_give isl_union_set *getDomains(); + __isl_give isl_union_set *getDomains() const; /// @brief Get a union map of all may-writes performed in the SCoP. __isl_give isl_union_map *getMayWrites(); @@ -1020,7 +1008,20 @@ __isl_give isl_union_map *getReads(); /// @brief Get the schedule of all the statements in the SCoP. - __isl_give isl_union_map *getSchedule(); + __isl_give isl_union_map *getSchedule() const; + + /// @brief Get a schedule tree describing the schedule of all statements. + __isl_give isl_schedule *getScheduleTree() const; + + /// @brief Update the current schedule + /// + /// @brief NewSchedule The new schedule (given as a flat union-map). + void setSchedule(__isl_take isl_union_map *NewSchedule); + + /// @brief Update the current schedule + /// + /// @brief NewSchedule The new schedule (given as schedule tree). + void setScheduleTree(__isl_take isl_schedule *NewSchedule); /// @brief Intersects the domains of all statements in the SCoP. /// Index: lib/Analysis/DependenceInfo.cpp =================================================================== --- lib/Analysis/DependenceInfo.cpp +++ lib/Analysis/DependenceInfo.cpp @@ -241,6 +241,7 @@ DEBUG(dbgs() << "Read: " << Read << "\n"; dbgs() << "Write: " << Write << "\n"; dbgs() << "MayWrite: " << MayWrite << "\n"; + dbgs() << "MayWrite: " << MayWrite << "\n"; dbgs() << "Schedule: " << ScheduleMap << "\n"); RAW = WAW = WAR = RED = nullptr; Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -42,6 +42,8 @@ #include "isl/printer.h" #include "isl/local_space.h" #include "isl/options.h" +#include "isl/schedule_node.h" +#include "isl/schedule.h" #include "isl/val.h" #include @@ -818,44 +820,34 @@ //===----------------------------------------------------------------------===// -isl_map *ScopStmt::getSchedule() const { return isl_map_copy(Schedule); } +isl_map *ScopStmt::getSchedule() const { + isl_set *Domain = getDomain(); + if (isl_set_is_empty(Domain)) { + isl_set_free(Domain); + return isl_map_from_aff( + isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace()))); + } + auto *Schedule = getParent()->getSchedule(); + Schedule = isl_union_map_intersect_domain( + Schedule, isl_union_set_from_set(isl_set_copy(Domain))); + if (isl_union_map_is_empty(Schedule)) { + isl_set_free(Domain); + isl_union_map_free(Schedule); + return isl_map_from_aff( + isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace()))); + } + auto *M = isl_map_from_union_map(Schedule); + M = isl_map_coalesce(M); + M = isl_map_gist_domain(M, Domain); + M = isl_map_coalesce(M); + return M; +} void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) { assert(isl_set_is_subset(NewDomain, Domain) && "New domain is not a subset of old domain!"); isl_set_free(Domain); Domain = NewDomain; - Schedule = isl_map_intersect_domain(Schedule, isl_set_copy(Domain)); -} - -void ScopStmt::setSchedule(__isl_take isl_map *NewSchedule) { - assert(NewSchedule && "New schedule is nullptr"); - isl_map_free(Schedule); - Schedule = NewSchedule; -} - -void ScopStmt::buildSchedule(SmallVectorImpl &ScheduleVec) { - unsigned NbIterators = getNumIterators(); - unsigned NbScheduleDims = Parent.getMaxLoopDepth() * 2 + 1; - - isl_space *Space = isl_space_set_alloc(getIslCtx(), 0, NbScheduleDims); - - Schedule = isl_map_from_domain_and_range(isl_set_universe(getDomainSpace()), - isl_set_universe(Space)); - - // Loop dimensions. - for (unsigned i = 0; i < NbIterators; ++i) - Schedule = isl_map_equate(Schedule, isl_dim_out, 2 * i + 1, isl_dim_in, i); - - // Constant dimensions - for (unsigned i = 0; i < NbIterators + 1; ++i) - Schedule = isl_map_fix_si(Schedule, isl_dim_out, 2 * i, ScheduleVec[i]); - - // Fill schedule dimensions. - for (unsigned i = 2 * NbIterators + 1; i < NbScheduleDims; ++i) - Schedule = isl_map_fix_si(Schedule, isl_dim_out, i, 0); - - Schedule = isl_map_align_params(Schedule, Parent.getParamSpace()); } void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block, @@ -895,7 +887,6 @@ MA->realignParams(); Domain = isl_set_align_params(Domain, Parent.getParamSpace()); - Schedule = isl_map_align_params(Schedule, Parent.getParamSpace()); } __isl_give isl_set *ScopStmt::buildConditionSet(const Comparison &Comp) { @@ -1054,8 +1045,7 @@ } ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, - Region &R, SmallVectorImpl &Nest, - SmallVectorImpl &ScheduleVec) + Region &R, SmallVectorImpl &Nest) : Parent(parent), BB(nullptr), R(&R), Build(nullptr), NestLoops(Nest.size()) { // Setup the induction variables. @@ -1065,7 +1055,6 @@ BaseName = getIslCompatibleName("Stmt_(", R.getNameStr(), ")"); Domain = buildDomain(tempScop, CurRegion); - buildSchedule(ScheduleVec); BasicBlock *EntryBB = R.getEntry(); for (BasicBlock *Block : R.blocks()) { @@ -1076,8 +1065,7 @@ } ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, - BasicBlock &bb, SmallVectorImpl &Nest, - SmallVectorImpl &ScheduleVec) + BasicBlock &bb, SmallVectorImpl &Nest) : Parent(parent), BB(&bb), R(nullptr), Build(nullptr), NestLoops(Nest.size()) { // Setup the induction variables. @@ -1087,7 +1075,6 @@ BaseName = getIslCompatibleName("Stmt_", &bb, ""); Domain = buildDomain(tempScop, CurRegion); - buildSchedule(ScheduleVec); buildAccesses(tempScop, BB); deriveAssumptions(BB); checkForReductions(); @@ -1225,17 +1212,16 @@ std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); } std::string ScopStmt::getScheduleStr() const { - return stringFromIslObj(Schedule); + auto *S = getSchedule(); + auto Str = stringFromIslObj(S); + isl_map_free(S); + return Str; } unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); } unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); } -unsigned ScopStmt::getNumSchedule() const { - return isl_map_dim(Schedule, isl_dim_out); -} - const char *ScopStmt::getBaseName() const { return BaseName.c_str(); } const Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const { @@ -1261,7 +1247,6 @@ } isl_set_free(Domain); - isl_map_free(Schedule); } void ScopStmt::print(raw_ostream &OS) const { @@ -1654,39 +1639,6 @@ return MaxLD - MinLD + 1; } -void Scop::dropConstantScheduleDims() { - isl_union_map *FullSchedule = getSchedule(); - - if (isl_union_map_n_map(FullSchedule) == 0) { - isl_union_map_free(FullSchedule); - return; - } - - isl_set *ScheduleSpace = - isl_set_from_union_set(isl_union_map_range(FullSchedule)); - isl_map *DropDimMap = isl_set_identity(isl_set_copy(ScheduleSpace)); - - int NumDimsDropped = 0; - for (unsigned i = 0; i < isl_set_dim(ScheduleSpace, isl_dim_set); i += 2) { - isl_val *FixedVal = - isl_set_plain_get_val_if_fixed(ScheduleSpace, isl_dim_set, i); - if (isl_val_is_int(FixedVal)) { - DropDimMap = - isl_map_project_out(DropDimMap, isl_dim_out, i - NumDimsDropped, 1); - NumDimsDropped++; - } - isl_val_free(FixedVal); - } - - for (auto *S : *this) { - isl_map *Schedule = S->getSchedule(); - Schedule = isl_map_apply_range(Schedule, isl_map_copy(DropDimMap)); - S->setSchedule(Schedule); - } - isl_set_free(ScheduleSpace); - isl_map_free(DropDimMap); -} - Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution, ScopDetection &SD, isl_ctx *Context) : SE(&ScalarEvolution), R(tempScop.getMaxRegion()), IsOptimized(false), @@ -1696,18 +1648,16 @@ buildContext(); SmallVector NestLoops; - SmallVector Schedule; - - Schedule.assign(MaxLoopDepth + 1, 0); // Build the iteration domain, access functions and schedule functions // traversing the region tree. - buildScop(tempScop, getRegion(), NestLoops, Schedule, LI, SD); + Schedule = buildScop(tempScop, getRegion(), NestLoops, LI, SD); + if (!Schedule) + Schedule = isl_schedule_empty(getParamSpace()); realignParams(); addParameterBounds(); simplifyAssumedContext(); - dropConstantScheduleDims(); assert(NestLoops.empty() && "NestLoops not empty at top level!"); } @@ -1715,6 +1665,7 @@ Scop::~Scop() { isl_set_free(Context); isl_set_free(AssumedContext); + isl_schedule_free(Schedule); // Free the statements; for (ScopStmt *Stmt : *this) @@ -1849,7 +1800,7 @@ isl_ctx *Scop::getIslCtx() const { return IslCtx; } -__isl_give isl_union_set *Scop::getDomains() { +__isl_give isl_union_set *Scop::getDomains() const { isl_union_set *Domain = isl_union_set_empty(getParamSpace()); for (ScopStmt *Stmt : *this) @@ -1927,13 +1878,29 @@ return isl_union_map_coalesce(Read); } -__isl_give isl_union_map *Scop::getSchedule() { - isl_union_map *Schedule = isl_union_map_empty(getParamSpace()); +__isl_give isl_union_map *Scop::getSchedule() const { + auto Tree = getScheduleTree(); + auto S = isl_schedule_get_map(Tree); + isl_schedule_free(Tree); + return S; +} - for (ScopStmt *Stmt : *this) - Schedule = isl_union_map_add_map(Schedule, Stmt->getSchedule()); +__isl_give isl_schedule *Scop::getScheduleTree() const { + return isl_schedule_intersect_domain(isl_schedule_copy(Schedule), + getDomains()); +} - return isl_union_map_coalesce(Schedule); +void Scop::setSchedule(__isl_take isl_union_map *NewSchedule) { + auto *S = isl_schedule_from_domain(getDomains()); + S = isl_schedule_insert_partial_schedule( + S, isl_multi_union_pw_aff_from_union_map(NewSchedule)); + isl_schedule_free(Schedule); + Schedule = S; +} + +void Scop::setScheduleTree(__isl_take isl_schedule *NewSchedule) { + isl_schedule_free(Schedule); + Schedule = NewSchedule; } bool Scop::restrictDomains(__isl_take isl_union_set *Domain) { @@ -1973,20 +1940,71 @@ return true; } -void Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, - const Region &CurRegion, - SmallVectorImpl &NestLoops, - SmallVectorImpl &ScheduleVec) { +struct MapToDimensionDataTy { + int N; + isl_union_pw_multi_aff *Res; +}; + +// @brief Create a function that maps the elements of 'Set' to its N-th +// dimension. +// +// The result is added to 'User->Res'. +// +// @param Set The input set. +// @param N The dimension to map to. +// +// @returns Zero if no error occurred, non-zero otherwise. +static int mapToDimension_AddSet(__isl_take isl_set *Set, void *User) { + struct MapToDimensionDataTy *Data = (struct MapToDimensionDataTy *)User; + int Dim; + isl_space *Space; + isl_pw_multi_aff *PMA; + + Dim = isl_set_dim(Set, isl_dim_set); + Space = isl_set_get_space(Set); + PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N, + Dim - Data->N); + if (Data->N > 1) + PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1); + Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA); + + isl_set_free(Set); + + return 0; +} + +// @brief Create a function that maps the elements of Domain to their Nth +// dimension. +// +// @param Domain The set of elements to map. +// @param N The dimension to map to. +static __isl_give isl_multi_union_pw_aff * +mapToDimension(__isl_take isl_union_set *Domain, int N) { + struct MapToDimensionDataTy Data; + isl_space *Space; + + Space = isl_union_set_get_space(Domain); + Data.N = N; + Data.Res = isl_union_pw_multi_aff_empty(Space); + if (isl_union_set_foreach_set(Domain, &mapToDimension_AddSet, &Data) < 0) + Data.Res = isl_union_pw_multi_aff_free(Data.Res); + + isl_union_set_free(Domain); + return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res); +} + +ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, + const Region &CurRegion, + SmallVectorImpl &NestLoops) { ScopStmt *Stmt; if (BB) { - Stmt = - new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, ScheduleVec); + Stmt = new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops); StmtMap[BB] = Stmt; } else { assert(R && "Either a basic block or a region is needed to " "create a new SCoP stmt."); - Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops, ScheduleVec); + Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops); for (BasicBlock *BB : R->blocks()) StmtMap[BB] = Stmt; } @@ -1994,18 +2012,19 @@ // Insert all statements into the statement map and the statement vector. Stmts.push_back(Stmt); - // Increasing the Schedule function is OK for the moment, because - // we are using a depth first iterator and the program is well structured. - ++ScheduleVec[NestLoops.size()]; + return Stmt; } -void Scop::buildScop(TempScop &tempScop, const Region &CurRegion, - SmallVectorImpl &NestLoops, - SmallVectorImpl &ScheduleVec, LoopInfo &LI, - ScopDetection &SD) { - if (SD.isNonAffineSubRegion(&CurRegion, &getRegion())) - return addScopStmt(nullptr, const_cast(&CurRegion), tempScop, - CurRegion, NestLoops, ScheduleVec); +__isl_give isl_schedule *Scop::buildScop(TempScop &tempScop, + const Region &CurRegion, + SmallVectorImpl &NestLoops, + LoopInfo &LI, ScopDetection &SD) { + if (SD.isNonAffineSubRegion(&CurRegion, &getRegion())) { + auto *Stmt = addScopStmt(nullptr, const_cast(&CurRegion), + tempScop, CurRegion, NestLoops); + auto *Domain = Stmt->getDomain(); + return isl_schedule_from_domain(isl_union_set_from_set(Domain)); + } Loop *L = castToLoop(CurRegion, LI); @@ -2013,30 +2032,45 @@ NestLoops.push_back(L); unsigned loopDepth = NestLoops.size(); - assert(ScheduleVec.size() > loopDepth && "Schedule not big enough!"); + isl_schedule *Schedule = nullptr; for (Region::const_element_iterator I = CurRegion.element_begin(), E = CurRegion.element_end(); - I != E; ++I) + I != E; ++I) { + isl_schedule *StmtSchedule = nullptr; if (I->isSubRegion()) { - buildScop(tempScop, *I->getNodeAs(), NestLoops, ScheduleVec, LI, - SD); + StmtSchedule = + buildScop(tempScop, *I->getNodeAs(), NestLoops, LI, SD); } else { BasicBlock *BB = I->getNodeAs(); - if (isTrivialBB(BB, tempScop)) + if (isTrivialBB(BB, tempScop)) { continue; - - addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops, ScheduleVec); + } else { + auto *Stmt = addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops); + auto *Domain = Stmt->getDomain(); + StmtSchedule = isl_schedule_from_domain(isl_union_set_from_set(Domain)); + } } + if (!Schedule) + Schedule = StmtSchedule; + else if (StmtSchedule) + Schedule = isl_schedule_sequence(Schedule, StmtSchedule); + } + if (!L) - return; + return Schedule; + + auto *Domain = isl_schedule_get_domain(Schedule); + if (!isl_union_set_is_empty(Domain)) { + auto *MUPA = mapToDimension(isl_union_set_copy(Domain), loopDepth); + Schedule = isl_schedule_insert_partial_schedule(Schedule, MUPA); + } + isl_union_set_free(Domain); - // Exiting a loop region. - ScheduleVec[loopDepth] = 0; NestLoops.pop_back(); - ++ScheduleVec[loopDepth - 1]; + return Schedule; } ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const { Index: lib/CodeGen/IslAst.cpp =================================================================== --- lib/CodeGen/IslAst.cpp +++ lib/CodeGen/IslAst.cpp @@ -384,9 +384,6 @@ Build = isl_ast_build_set_at_each_domain(Build, AtEachDomain, nullptr); - isl_union_map *Schedule = - isl_union_map_intersect_domain(S->getSchedule(), S->getDomains()); - if (PerformParallelTest) { BuildInfo.Deps = &D; BuildInfo.InParallelFor = 0; @@ -399,7 +396,7 @@ buildRunCondition(Build); - Root = isl_ast_build_ast_from_schedule(Build, Schedule); + Root = isl_ast_build_node_from_schedule(Build, S->getScheduleTree()); isl_ast_build_free(Build); } Index: lib/CodeGen/IslCodeGeneration.cpp =================================================================== --- lib/CodeGen/IslCodeGeneration.cpp +++ lib/CodeGen/IslCodeGeneration.cpp @@ -297,6 +297,9 @@ unsigned IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node *For) { isl_union_map *Schedule = IslAstInfo::getSchedule(For); isl_set *LoopDomain = isl_set_from_union_set(isl_union_map_range(Schedule)); + if (isl_set_is_wrapping(LoopDomain)) + LoopDomain = isl_map_range(isl_set_unwrap(LoopDomain)); + int NumberOfIterations = polly::getNumberOfIterations(LoopDomain); if (NumberOfIterations == -1) return -1; Index: lib/Exchange/JSONExporter.cpp =================================================================== --- lib/Exchange/JSONExporter.cpp +++ lib/Exchange/JSONExporter.cpp @@ -255,13 +255,18 @@ return false; } + auto ScheduleMap = isl_union_map_empty(S.getParamSpace()); for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) { ScopStmt *Stmt = *SI; if (NewSchedule.find(Stmt) != NewSchedule.end()) - Stmt->setSchedule(NewSchedule[Stmt]); + ScheduleMap = isl_union_map_add_map(ScheduleMap, NewSchedule[Stmt]); + else + ScheduleMap = isl_union_map_add_map(ScheduleMap, Stmt->getSchedule()); } + S.setSchedule(ScheduleMap); + int statementIdx = 0; for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) { ScopStmt *Stmt = *SI; Index: lib/Transform/ScheduleOptimizer.cpp =================================================================== --- lib/Transform/ScheduleOptimizer.cpp +++ lib/Transform/ScheduleOptimizer.cpp @@ -173,8 +173,20 @@ /// @param User A pointer to forward some use information (currently unused). static isl_schedule_node *optimizeBand(isl_schedule_node *Node, void *User); - static __isl_give isl_union_map * - getScheduleMap(__isl_keep isl_schedule *Schedule); + /// @brief Apply post-scheduling transformations. + /// + /// This function applies a set of additional local transformations on the + /// schedule tree as it computed by the isl scheduler. Local transformations + /// applied include: + /// + /// - Tiling + /// - Prevectorization + /// + /// @param Schedule The schedule object post-transformations will be applied + /// on. + /// @returns The transformed schedule. + static __isl_give isl_schedule * + addPostTransforms(__isl_take isl_schedule *Schedule); using llvm::Pass::doFinalization; @@ -317,15 +329,15 @@ return Res; } -__isl_give isl_union_map * -IslScheduleOptimizer::getScheduleMap(__isl_keep isl_schedule *Schedule) { +__isl_give isl_schedule * +IslScheduleOptimizer::addPostTransforms(__isl_take isl_schedule *Schedule) { isl_schedule_node *Root = isl_schedule_get_root(Schedule); + isl_schedule_free(Schedule); Root = isl_schedule_node_map_descendant( Root, IslScheduleOptimizer::optimizeBand, NULL); - auto ScheduleMap = isl_schedule_node_get_subtree_schedule_union_map(Root); - ScheduleMap = isl_union_map_detect_equalities(ScheduleMap); + auto S = isl_schedule_node_get_schedule(Root); isl_schedule_node_free(Root); - return ScheduleMap; + return S; } bool IslScheduleOptimizer::isProfitableSchedule( @@ -461,36 +473,20 @@ DEBUG(dbgs() << "Schedule := " << stringFromIslObj(Schedule) << ";\n"); - isl_union_map *NewSchedule = getScheduleMap(Schedule); + isl_schedule *NewSchedule = addPostTransforms(Schedule); + isl_union_map *NewScheduleMap = isl_schedule_get_map(NewSchedule); // Check if the optimizations performed were profitable, otherwise exit early. - if (!isProfitableSchedule(S, NewSchedule)) { - isl_schedule_free(Schedule); - isl_union_map_free(NewSchedule); + if (!isProfitableSchedule(S, NewScheduleMap)) { + isl_union_map_free(NewScheduleMap); + isl_schedule_free(NewSchedule); return false; } - + S.setScheduleTree(NewSchedule); S.markAsOptimized(); - for (ScopStmt *Stmt : S) { - isl_map *StmtSchedule; - isl_set *Domain = Stmt->getDomain(); - isl_union_map *StmtBand; - StmtBand = isl_union_map_intersect_domain(isl_union_map_copy(NewSchedule), - isl_union_set_from_set(Domain)); - if (isl_union_map_is_empty(StmtBand)) { - StmtSchedule = isl_map_from_domain(isl_set_empty(Stmt->getDomainSpace())); - isl_union_map_free(StmtBand); - } else { - assert(isl_union_map_n_map(StmtBand) == 1); - StmtSchedule = isl_map_from_union_map(StmtBand); - } - - Stmt->setSchedule(StmtSchedule); - } + isl_union_map_free(NewScheduleMap); - isl_schedule_free(Schedule); - isl_union_map_free(NewSchedule); return false; } Index: test/DeadCodeElimination/chained_iterations.ll =================================================================== --- test/DeadCodeElimination/chained_iterations.ll +++ test/DeadCodeElimination/chained_iterations.ll @@ -49,13 +49,13 @@ ret void } -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_1(c1); -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_2(c1); -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_3(c1); - -; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK-DCE: Stmt_for_body_3(c1); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_1(c0); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_2(c0); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_3(c0); + +; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK-DCE: Stmt_for_body_3(c0); Index: test/DeadCodeElimination/chained_iterations_2.ll =================================================================== --- test/DeadCodeElimination/chained_iterations_2.ll +++ test/DeadCodeElimination/chained_iterations_2.ll @@ -54,12 +54,12 @@ ret void } -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_1(c1); -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_2(c1); -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_3(c1); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_1(c0); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_2(c0); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_3(c0); -; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK-DCE: Stmt_for_body_3(c1); +; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK-DCE: Stmt_for_body_3(c0); Index: test/DeadCodeElimination/computeout.ll =================================================================== --- test/DeadCodeElimination/computeout.ll +++ test/DeadCodeElimination/computeout.ll @@ -51,13 +51,13 @@ } ; CHECK-NOT: Stmt_S -; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK: Stmt_S3(c1); - -; TIMEOUT: for (int c1 = 0; c1 <= 99; c1 += 1) -; TIMEOUT: Stmt_S1(c1); -; TIMEOUT: for (int c1 = 0; c1 <= 9; c1 += 1) -; TIMEOUT: Stmt_S2(c1); -; TIMEOUT: for (int c1 = 0; c1 <= 199; c1 += 1) -; TIMEOUT: Stmt_S3(c1); +; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK: Stmt_S3(c0); + +; TIMEOUT: for (int c0 = 0; c0 <= 99; c0 += 1) +; TIMEOUT: Stmt_S1(c0); +; TIMEOUT: for (int c0 = 0; c0 <= 9; c0 += 1) +; TIMEOUT: Stmt_S2(c0); +; TIMEOUT: for (int c0 = 0; c0 <= 199; c0 += 1) +; TIMEOUT: Stmt_S3(c0); Index: test/DeadCodeElimination/dead_iteration_elimination.ll =================================================================== --- test/DeadCodeElimination/dead_iteration_elimination.ll +++ test/DeadCodeElimination/dead_iteration_elimination.ll @@ -67,12 +67,12 @@ ret void } -; CHECK: for (int c1 = 50; c1 <= 99; c1 += 1) -; CHECK: Stmt_for_body_1(c1); -; CHECK: for (int c1 = 110; c1 <= 199; c1 += 1) -; CHECK: Stmt_for_body_1(c1); -; CHECK: for (int c1 = 0; c1 <= 49; c1 += 1) -; CHECK: Stmt_for_body_2(c1); -; CHECK: for (int c1 = 0; c1 <= 69; c1 += 1) -; CHECK: Stmt_for_body_3(c1); -; CHECK: for (int c1 = 0; c1 <= 9; c1 += 1) +; CHECK: for (int c0 = 50; c0 <= 99; c0 += 1) +; CHECK: Stmt_for_body_1(c0); +; CHECK: for (int c0 = 110; c0 <= 199; c0 += 1) +; CHECK: Stmt_for_body_1(c0); +; CHECK: for (int c0 = 0; c0 <= 49; c0 += 1) +; CHECK: Stmt_for_body_2(c0); +; CHECK: for (int c0 = 0; c0 <= 69; c0 += 1) +; CHECK: Stmt_for_body_3(c0); +; CHECK: for (int c0 = 0; c0 <= 9; c0 += 1) Index: test/DeadCodeElimination/non-affine-affine-mix.ll =================================================================== --- test/DeadCodeElimination/non-affine-affine-mix.ll +++ test/DeadCodeElimination/non-affine-affine-mix.ll @@ -11,10 +11,10 @@ ; the size of A and as a result S1 may write for example to A[1024], which ; is not overwritten by S2. -; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1) -; CHECK: Stmt_S1(c1); -; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1) -; CHECK: Stmt_S2(c1); +; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) +; CHECK: Stmt_S1(c0); +; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) +; CHECK: Stmt_S2(c0); target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" Index: test/DeadCodeElimination/null_schedule.ll =================================================================== --- test/DeadCodeElimination/null_schedule.ll +++ test/DeadCodeElimination/null_schedule.ll @@ -52,5 +52,5 @@ ret void } -; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1) -; CHECK-DCE: Stmt_for_body_2(c1); +; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1) +; CHECK-DCE: Stmt_for_body_2(c0); Index: test/Isl/Ast/reduction_modulo_schedule_multiple_dimensions_4.ll =================================================================== --- test/Isl/Ast/reduction_modulo_schedule_multiple_dimensions_4.ll +++ test/Isl/Ast/reduction_modulo_schedule_multiple_dimensions_4.ll @@ -6,7 +6,7 @@ ; CHECK: #pragma known-parallel ; CHECK: for (int c1 = 0; c1 < 2 * n; c1 += 1) ; CHECK: #pragma simd reduction -; CHECK: for (int c3 = -1022; c3 <= 1023; c3 += 1) { +; CHECK: for (int c3 = -1023; c3 <= 1023; c3 += 1) { ; CHECK: if (c3 <= 0 && c3 % 2 == 0) { ; CHECK: Stmt_for_body3(c1, -c3); ; CHECK: } else if (c3 >= 1 && (c3 - 1) % 2 == 0) Index: test/Isl/Ast/simple-run-time-condition.ll =================================================================== --- test/Isl/Ast/simple-run-time-condition.ll +++ test/Isl/Ast/simple-run-time-condition.ll @@ -24,13 +24,13 @@ ; CHECK: ) ; CHECK: if (o >= 1) { -; CHECK: for (int c1 = 0; c1 < n; c1 += 1) -; CHECK: for (int c2 = 0; c2 < m; c2 += 1) -; CHECK: Stmt_for_j(c1, c2); +; CHECK: for (int c0 = 0; c0 < n; c0 += 1) +; CHECK: for (int c1 = 0; c1 < m; c1 += 1) +; CHECK: Stmt_for_j(c0, c1); ; CHECK: } else -; CHECK: for (int c1 = 0; c1 < n; c1 += 1) -; CHECK: for (int c2 = 0; c2 < m; c2 += 1) -; CHECK: Stmt_for_j_1(c1, c2); +; CHECK: for (int c0 = 0; c0 < n; c0 += 1) +; CHECK: for (int c1 = 0; c1 < m; c1 += 1) +; CHECK: Stmt_for_j_1(c0, c1); ; CHECK: else ; CHECK: { /* original code */ } Index: test/Isl/CodeGen/loop_with_condition.ll =================================================================== --- test/Isl/CodeGen/loop_with_condition.ll +++ test/Isl/CodeGen/loop_with_condition.ll @@ -166,9 +166,9 @@ declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) { -; CHECK: if (c0 >= 513) { -; CHECK: Stmt_5(c0); -; CHECK: } else +; CHECK: if (c0 <= 512) { ; CHECK: Stmt_4(c0); +; CHECK: } else +; CHECK: Stmt_5(c0); ; CHECK: Stmt_6(c0); ; CHECK: } Index: test/Isl/CodeGen/loop_with_condition_2.ll =================================================================== --- test/Isl/CodeGen/loop_with_condition_2.ll +++ test/Isl/CodeGen/loop_with_condition_2.ll @@ -5,10 +5,10 @@ ; CHECK: #pragma simd ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) { -; CHECK: if (c0 >= m + 1025) { -; CHECK: Stmt_if_else(c0); -; CHECK: } else +; CHECK: if (m + 1024 >= c0) { ; CHECK: Stmt_if_then(c0); +; CHECK: } else +; CHECK: Stmt_if_else(c0); ; CHECK: Stmt_if_end(c0); ; CHECK: } Index: test/Isl/CodeGen/loop_with_condition_ineq.ll =================================================================== --- test/Isl/CodeGen/loop_with_condition_ineq.ll +++ test/Isl/CodeGen/loop_with_condition_ineq.ll @@ -166,9 +166,7 @@ declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) { -; CHECK: if (c0 >= 513) { -; CHECK: Stmt_4(c0); -; CHECK: } else if (c0 <= 511) { +; CHECK: if (c0 >= 513 || c0 <= 511) { ; CHECK: Stmt_4(c0); ; CHECK: } else ; CHECK: Stmt_5(512); Index: test/Isl/CodeGen/loop_with_condition_nested.ll =================================================================== --- test/Isl/CodeGen/loop_with_condition_nested.ll +++ test/Isl/CodeGen/loop_with_condition_nested.ll @@ -204,10 +204,10 @@ declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) { -; CHECK: if (c0 <= 20) { -; CHECK: Stmt_7(c0); -; CHECK: } else if (c0 <= 512) +; CHECK: if (c0 >= 21 && c0 <= 512) { ; CHECK: Stmt_6(c0); +; CHECK: } else if (c0 <= 20) +; CHECK: Stmt_7(c0); ; CHECK: Stmt_9(c0); ; CHECK: } Index: test/Isl/CodeGen/sequential_loops.ll =================================================================== --- test/Isl/CodeGen/sequential_loops.ll +++ test/Isl/CodeGen/sequential_loops.ll @@ -130,8 +130,8 @@ declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind ; CHECK: { -; CHECK: for (int c1 = 0; c1 <= 511; c1 += 1) -; CHECK: Stmt_bb2(c1); -; CHECK: for (int c1 = 0; c1 <= 511; c1 += 1) -; CHECK: Stmt_bb6(c1); +; CHECK: for (int c0 = 0; c0 <= 511; c0 += 1) +; CHECK: Stmt_bb2(c0); +; CHECK: for (int c0 = 0; c0 <= 511; c0 += 1) +; CHECK: Stmt_bb6(c0); ; CHECK: } Index: test/ScheduleOptimizer/computeout.ll =================================================================== --- test/ScheduleOptimizer/computeout.ll +++ test/ScheduleOptimizer/computeout.ll @@ -60,10 +60,10 @@ ; CHECK: Stmt_S3(c0); ; CHECK: } -; TIMEOUT: for (int c1 = 0; c1 <= 99; c1 += 1) -; TIMEOUT: Stmt_S1(c1); -; TIMEOUT: for (int c1 = 0; c1 <= 9; c1 += 1) -; TIMEOUT: Stmt_S2(c1); -; TIMEOUT: for (int c1 = 0; c1 <= 199; c1 += 1) -; TIMEOUT: Stmt_S3(c1); +; TIMEOUT: for (int c0 = 0; c0 <= 99; c0 += 1) +; TIMEOUT: Stmt_S1(c0); +; TIMEOUT: for (int c0 = 0; c0 <= 9; c0 += 1) +; TIMEOUT: Stmt_S2(c0); +; TIMEOUT: for (int c0 = 0; c0 <= 199; c0 += 1) +; TIMEOUT: Stmt_S3(c0); Index: test/ScheduleOptimizer/line-tiling.ll =================================================================== --- test/ScheduleOptimizer/line-tiling.ll +++ test/ScheduleOptimizer/line-tiling.ll @@ -1,4 +1,4 @@ -; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-no-tiling=0 -polly-ast -polly-tile-sizes=64,1 < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-ast -polly-tile-sizes=64,1 < %s | FileCheck %s ; CHECK: for (int c0 = 0; c0 <= 15; c0 += 1) ; CHECK: for (int c1 = 0; c1 <= 511; c1 += 1) Index: test/ScheduleOptimizer/one-dimensional-band.ll =================================================================== --- test/ScheduleOptimizer/one-dimensional-band.ll +++ test/ScheduleOptimizer/one-dimensional-band.ll @@ -1,4 +1,4 @@ -; RUN: opt %loadPolly -polly-opt-isl -polly-ast -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-opt-isl -polly-ast -analyze -polly-no-early-exit < %s | FileCheck %s ; ; void jacobi1d(long T, long N, float *A, float *B) { ; long t, i, j; @@ -13,10 +13,10 @@ ; Verify that we do not tile bands that have just a single dimension. ; CHECK: for (int c0 = 0; c0 < T; c0 += 1) { -; CHECK: for (int c2 = 0; c2 < N - 2; c2 += 1) -; CHECK: Stmt_for_body3(c0, c2); -; CHECK: for (int c2 = 0; c2 < N - 2; c2 += 1) -; CHECK: Stmt_for_body15(c0, c2); +; CHECK: for (int c1 = 0; c1 < N - 2; c1 += 1) +; CHECK: Stmt_for_body3(c0, c1); +; CHECK: for (int c1 = 0; c1 < N - 2; c1 += 1) +; CHECK: Stmt_for_body15(c0, c1); ; CHECK: } target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: test/ScheduleOptimizer/prevectorization.ll =================================================================== --- test/ScheduleOptimizer/prevectorization.ll +++ test/ScheduleOptimizer/prevectorization.ll @@ -55,23 +55,23 @@ attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } ; CHECK: #pragma known-parallel -; CHECK: for (int c1 = 0; c1 <= 47; c1 += 1) -; CHECK: for (int c2 = 0; c2 <= 47; c2 += 1) -; CHECK: for (int c3 = 0; c3 <= 31; c3 += 1) -; CHECK: for (int c4 = 0; c4 <= 31; c4 += 4) +; CHECK: for (int c0 = 0; c0 <= 47; c0 += 1) +; CHECK: for (int c1 = 0; c1 <= 47; c1 += 1) +; CHECK: for (int c2 = 0; c2 <= 31; c2 += 1) +; CHECK: for (int c3 = 0; c3 <= 31; c3 += 4) ; CHECK: #pragma simd -; CHECK: for (int c5 = c4; c5 <= c4 + 3; c5 += 1) -; CHECK: Stmt_for_body3(32 * c1 + c3, 32 * c2 + c5); +; CHECK: for (int c4 = c3; c4 <= c3 + 3; c4 += 1) +; CHECK: Stmt_for_body3(32 * c0 + c2, 32 * c1 + c4); ; CHECK: #pragma known-parallel -; CHECK: for (int c1 = 0; c1 <= 47; c1 += 1) -; CHECK: for (int c2 = 0; c2 <= 47; c2 += 1) -; CHECK: for (int c3 = 0; c3 <= 47; c3 += 1) -; CHECK: for (int c4 = 0; c4 <= 31; c4 += 1) -; CHECK: for (int c5 = 0; c5 <= 31; c5 += 4) -; CHECK: for (int c6 = 0; c6 <= 31; c6 += 1) +; CHECK: for (int c0 = 0; c0 <= 47; c0 += 1) +; CHECK: for (int c1 = 0; c1 <= 47; c1 += 1) +; CHECK: for (int c2 = 0; c2 <= 47; c2 += 1) +; CHECK: for (int c3 = 0; c3 <= 31; c3 += 1) +; CHECK: for (int c4 = 0; c4 <= 31; c4 += 4) +; CHECK: for (int c5 = 0; c5 <= 31; c5 += 1) ; CHECK: #pragma simd -; CHECK: for (int c7 = c5; c7 <= c5 + 3; c7 += 1) -; CHECK: Stmt_for_body8(32 * c1 + c4, 32 * c2 + c7, 32 * c3 + c6); +; CHECK: for (int c6 = c4; c6 <= c4 + 3; c6 += 1) +; CHECK: Stmt_for_body8(32 * c0 + c3, 32 * c1 + c6, 32 * c2 + c5); !llvm.ident = !{!0} Index: test/ScheduleOptimizer/rectangular-tiling.ll =================================================================== --- test/ScheduleOptimizer/rectangular-tiling.ll +++ test/ScheduleOptimizer/rectangular-tiling.ll @@ -1,5 +1,5 @@ ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-ast -polly-tile-sizes=256,16 < %s | FileCheck %s -; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-no-tiling -polly-ast -polly-tile-sizes=256,16 < %s | FileCheck %s --check-prefix=NOTILING +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-no-tiling -polly-ast -polly-tile-sizes=256,16 -polly-no-early-exit < %s | FileCheck %s --check-prefix=NOTILING ; CHECK: for (int c0 = 0; c0 <= 3; c0 += 1) ; CHECK: for (int c1 = 0; c1 <= 31; c1 += 1) Index: test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll =================================================================== --- test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll +++ test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll @@ -23,7 +23,7 @@ ; INNERMOST: Domain := ; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) or (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) }; ; INNERMOST: Schedule := -; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] }; +; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 }; ; INNERMOST: ReadAccess := [Reduction Type: NONE] [Scalar: 0] ; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 }; ; INNERMOST: ReadAccess := [Reduction Type: NONE] [Scalar: 0] Index: test/ScopInfo/NonAffine/non_affine_loop_used_later.ll =================================================================== --- test/ScopInfo/NonAffine/non_affine_loop_used_later.ll +++ test/ScopInfo/NonAffine/non_affine_loop_used_later.ll @@ -16,9 +16,9 @@ ; CHECK: Statements { ; CHECK: Stmt_bb2 ; CHECK: Domain := -; CHECK: [N] -> { Stmt_bb2[i0] : i0 >= 0 and N >= 1 and i0 <= N; Stmt_bb2[0] : N <= 0 }; +; CHECK: [N] -> { Stmt_bb2[i0] : i0 >= 0 and N >= 1 and i0 <= N; Stmt_bb2[0] : N <= 0 } ; CHECK: Schedule := -; CHECK: [N] -> { Stmt_bb2[i0] -> [i0, 0] }; +; CHECK: [N] -> { Stmt_bb2[i0] -> [i0, 0] : i0 <= N and N >= 1; Stmt_bb2[0] -> [0, 0] : N <= 0 } ; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK: [N] -> { Stmt_bb2[i0] -> MemRef_j_0[] }; ; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] Index: test/ScopInfo/pointer-type-expressions.ll =================================================================== --- test/ScopInfo/pointer-type-expressions.ll +++ test/ScopInfo/pointer-type-expressions.ll @@ -43,6 +43,6 @@ ; CHECK: (P >= 1 and i0 >= 0 and i0 <= -1 + N) ; CHECK: }; ; CHECK: Schedule := -; CHECK: [N, P] -> { Stmt_store[i0] -> [i0] }; +; CHECK: [N, P] -> { Stmt_store[i0] -> [i0] : P <= -1 or P >= 1 }; ; CHECK: MustWriteAccess := [Reduction Type: NONE] ; CHECK: [N, P] -> { Stmt_store[i0] -> MemRef_a[i0] };