Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -589,12 +589,10 @@ const ScopStmt &operator=(const ScopStmt &) = delete; /// Create the ScopStmt from a BasicBlock. - ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb, - SmallVectorImpl &NestLoops); + ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb); /// Create an overapproximating ScopStmt for the region @p R. - ScopStmt(Scop &parent, TempScop &tempScop, Region &R, - SmallVectorImpl &NestLoops); + ScopStmt(Scop &parent, TempScop &tempScop, Region &R); private: /// Polyhedral description @@ -653,7 +651,7 @@ /// @brief The isl AST build for the new generated AST. isl_ast_build *Build; - std::vector NestLoops; + SmallVector NestLoops; std::string BaseName; @@ -661,6 +659,9 @@ //@{ void buildDomain(); + /// @brief Fill NestLoops with loops surrounding this statement. + void collectSurroundingLoops(); + /// @brief Create the accesses for instructions in @p Block. /// /// @param tempScop The template SCoP. @@ -1084,35 +1085,17 @@ /// @param BB The basic block we build the statement for (or null) /// @param R The region we build the statement for (or null). /// @param tempScop The temp SCoP we use as model. - /// @param NestLoops A vector of all surrounding loops. - ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, - SmallVectorImpl &NestLoops); + ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop); - /// @brief Create the ScopStmt for a BasicBlock and return its schedule. - /// - /// Returns null if the BB is trivial and no stmt has been created. + /// @brief Build Schedule and ScopStmts from a given TempScop. /// - /// @param BB The basic block we build the statement for. - /// @param tempScop The temp SCoP we use as model. - /// @param NestLoops A vector of all surrounding loops. - /// - /// @return The ScopStmt's schedule. - __isl_give isl_schedule *buildBBScopStmt(BasicBlock *BB, TempScop &tempScop, - 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); + /// @param R The current region traversed. + /// @param TS The temporary scop that is translated into an actual scop. + /// @param LI The LoopInfo object. + /// @param SD The ScopDetection object. + void buildSchedule( + Region *R, TempScop &TS, LoopInfo &LI, ScopDetection &SD, + DenseMap> &LoopSchedules); /// @name Helper function for printing the Scop. /// Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -363,16 +363,6 @@ } } - // Allow loop exit conditions. - Loop *L = LI->getLoopFor(&BB); - if (L && L->getExitingBlock() == &BB) - return true; - - // Allow perfectly nested conditions. - Region *R = RI->getRegionFor(&BB); - if (R->getEntry() != &BB) - return invalid(Context, /*Assert=*/true, &BB); - return true; } @@ -709,66 +699,37 @@ bool ScopDetection::canUseISLTripCount(Loop *L, DetectionContext &Context) const { - - Region &CurRegion = Context.CurRegion; - // Ensure the loop has a single back edge. if (L->getNumBackEdges() != 1) return false; - // Ensure the loop has a single exiting block. - BasicBlock *ExitingBB = L->getExitingBlock(); - if (!ExitingBB) - return false; - - // Ensure the exiting block is terminated by a conditional branch. - BranchInst *Term = dyn_cast(ExitingBB->getTerminator()); - if (!Term || !Term->isConditional()) - return false; - - Value *Cond = Term->getCondition(); - - // If the terminating condition is an integer comparison, ensure that it is a - // comparison between a recurrence and an invariant value. - if (ICmpInst *I = dyn_cast(Cond)) { - const Value *Op0 = I->getOperand(0); - const Value *Op1 = I->getOperand(1); - const SCEV *LHS = SE->getSCEVAtScope(const_cast(Op0), L); - const SCEV *RHS = SE->getSCEVAtScope(const_cast(Op1), L); - if ((isa(LHS) && !isInvariant(*Op1, CurRegion)) || - (isa(RHS) && !isInvariant(*Op0, CurRegion))) + // Ensure the loop has a valid exiting blocks, otherwise we need to + // overapproximate it as a boxed loop. + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + for (BasicBlock *ExitingBB : ExitingBlocks) { + if (!isValidCFG(*ExitingBB, Context)) return false; } - // If the terminating condition is not an integer comparison, ensure that it - // is a constant. - else if (!isa(Cond)) - return false; - // We can use ISL to compute the trip count of L. return true; } bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { - // Is the loop count affine? - bool IsLoopCountAffine = false; - const SCEV *LoopCount = SE->getBackedgeTakenCount(L); - if (!isa(LoopCount)) - IsLoopCountAffine = isAffineExpr(&Context.CurRegion, LoopCount, *SE); - else - IsLoopCountAffine = canUseISLTripCount(L, Context); - if (IsLoopCountAffine) { + if (canUseISLTripCount(L, Context)) { Context.hasAffineLoops = true; return true; } - if (AllowNonAffineSubRegions) { + if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) { Region *R = RI->getRegionFor(L->getHeader()); if (R->contains(L)) if (addOverApproximatedRegion(R, Context)) return true; } + const SCEV *LoopCount = SE->getBackedgeTakenCount(L); return invalid(Context, /*Assert=*/true, L, LoopCount); } Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -30,6 +30,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/RegionIterator.h" @@ -891,6 +892,12 @@ LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), Domain); RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), Domain); ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), LHS, RHS); + + for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) { + isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u); + ConsequenceCondSet = + isl_set_set_dim_id(ConsequenceCondSet, isl_dim_set, u, DimId); + } } assert(ConsequenceCondSet); @@ -968,17 +975,21 @@ deriveAssumptionsFromGEP(GEP); } -ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, Region &R, - SmallVectorImpl &Nest) - : Parent(parent), BB(nullptr), R(&R), Build(nullptr), - NestLoops(Nest.size()) { - // Setup the induction variables. - for (unsigned i = 0, e = Nest.size(); i < e; ++i) - NestLoops[i] = Nest[i]; +void ScopStmt::collectSurroundingLoops() { + for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) { + isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u); + NestLoops.push_back(static_cast(isl_id_get_user(DimId))); + isl_id_free(DimId); + } +} + +ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, Region &R) + : Parent(parent), BB(nullptr), R(&R), Build(nullptr) { BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), ""); buildDomain(); + collectSurroundingLoops(); BasicBlock *EntryBB = R.getEntry(); for (BasicBlock *Block : R.blocks()) { @@ -989,17 +1000,13 @@ checkForReductions(); } -ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb, - SmallVectorImpl &Nest) - : Parent(parent), BB(&bb), R(nullptr), Build(nullptr), - NestLoops(Nest.size()) { - // Setup the induction variables. - for (unsigned i = 0, e = Nest.size(); i < e; ++i) - NestLoops[i] = Nest[i]; +ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb) + : Parent(parent), BB(&bb), R(nullptr), Build(nullptr) { BaseName = getIslCompatibleName("Stmt_", &bb, ""); buildDomain(); + collectSurroundingLoops(); buildAccesses(tempScop, BB); deriveAssumptions(BB); if (DetectReductions) @@ -1469,8 +1476,28 @@ return L; } +static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) { + if (!RN->isSubRegion()) + return 1; + + unsigned NumBlocks = 0; + Region *R = RN->getNodeAs(); + for (auto BB : R->blocks()) { + (void)BB; + NumBlocks++; + } + return NumBlocks; +} + ///} +static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain, + unsigned Dim, Loop *L) { + isl_id *DimId = + isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast(L)); + return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId); +} + isl_set *Scop::getDomainConditions(ScopStmt *Stmt) { BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock() : Stmt->getRegion()->getEntry(); @@ -1483,6 +1510,13 @@ auto *EntryBB = R->getEntry(); int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB)); auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1)); + + Loop *L = LI.getLoopFor(EntryBB); + while (LD-- >= 0) { + S = addDomainDimId(S, LD + 1, L); + L = L->getParentLoop(); + } + DomainMap[EntryBB] = S; buildDomainsWithBranchConstraints(R, LI, SD, DT); @@ -1572,9 +1606,11 @@ CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1); } else if (SuccBBLoopDepth > BBLoopDepth) { CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1); + CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop); } else if (BBLoopDepth >= 0) { CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1); CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1); + CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop); } } @@ -1612,6 +1648,64 @@ return getDomainForBlock(R->getEntry(), DomainMap, RI); } +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 isl_stat 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 isl_stat_ok; +} + +// @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) { + if (N <= 0 || isl_union_set_is_empty(Domain)) { + isl_union_set_free(Domain); + return nullptr; + } + + 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); +} + void Scop::propagateDomainConstraints(Region *R, LoopInfo &LI, ScopDetection &SD, DominatorTree &DT) { // Iterate over the region R and propagate the domain constrains from the @@ -1992,6 +2086,11 @@ return true; } +static Loop *getLoopSurroundingRegion(Region &R, LoopInfo &LI) { + Loop *L = LI.getLoopFor(R.getEntry()); + return L ? (R.contains(L) ? L->getParentLoop() : L) : nullptr; +} + static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI, ScopDetection &SD) { @@ -2032,21 +2131,18 @@ buildDomains(&R, LI, SD, DT); - SmallVector NestLoops; + DenseMap> LoopSchedules; - // Build the iteration domain, access functions and schedule functions - // traversing the region tree. - Schedule = buildScop(TempScop, getRegion(), NestLoops, LI, SD); - if (!Schedule) - Schedule = isl_schedule_empty(getParamSpace()); + Loop *L = getLoopSurroundingRegion(R, LI); + LoopSchedules[L]; + buildSchedule(&R, TempScop, LI, SD, LoopSchedules); + Schedule = LoopSchedules[L].first; realignParams(); addParameterBounds(); addUserContext(); simplifyAssumedContext(); buildAliasChecks(AA); - - assert(NestLoops.empty() && "NestLoops not empty at top level!"); } Scop *Scop::createFromTempScop(TempScop &TempScop, LoopInfo &LI, @@ -2395,69 +2491,15 @@ return true; } -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 isl_stat 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 isl_stat_ok; -} - -// @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, - SmallVectorImpl &NestLoops) { +ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop) { ScopStmt *Stmt; if (BB) { - Stmts.emplace_back(*this, tempScop, *BB, NestLoops); + Stmts.emplace_back(*this, tempScop, *BB); Stmt = &Stmts.back(); StmtMap[BB] = Stmt; } else { assert(R && "Either basic block or a region expected."); - Stmts.emplace_back(*this, tempScop, *R, NestLoops); + Stmts.emplace_back(*this, tempScop, *R); Stmt = &Stmts.back(); for (BasicBlock *BB : R->blocks()) StmtMap[BB] = Stmt; @@ -2465,62 +2507,59 @@ return Stmt; } -__isl_give isl_schedule * -Scop::buildBBScopStmt(BasicBlock *BB, TempScop &tempScop, - SmallVectorImpl &NestLoops) { - if (isTrivialBB(BB, tempScop)) - return nullptr; +void Scop::buildSchedule( + Region *R, TempScop &TS, LoopInfo &LI, ScopDetection &SD, + DenseMap> &LoopSchedules) { - auto *Stmt = addScopStmt(BB, nullptr, tempScop, NestLoops); - auto *Domain = Stmt->getDomain(); - return isl_schedule_from_domain(isl_union_set_from_set(Domain)); -} + ReversePostOrderTraversal RTraversal(R); + for (auto *RN : RTraversal) { -__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, NestLoops); - auto *Domain = Stmt->getDomain(); - return isl_schedule_from_domain(isl_union_set_from_set(Domain)); - } + if (RN->isSubRegion()) { + Region *SubRegion = RN->getNodeAs(); + if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { + buildSchedule(SubRegion, TS, LI, SD, LoopSchedules); + continue; + } + } - Loop *L = castToLoop(CurRegion, LI); + Loop *L = getRegionNodeLoop(RN, LI); + int LD = getRelativeLoopDepth(L); + auto &LSchedulePair = LoopSchedules[L]; + LSchedulePair.second += getNumBlocksInRegionNode(RN); - if (L) - NestLoops.push_back(L); + BasicBlock *BB = getRegionNodeBasicBlock(RN); + if (RN->isSubRegion() || !isTrivialBB(BB, TS)) { - unsigned loopDepth = NestLoops.size(); - isl_schedule *Schedule = nullptr; + ScopStmt *Stmt; + if (RN->isSubRegion()) + Stmt = addScopStmt(nullptr, RN->getNodeAs(), TS); + else + Stmt = addScopStmt(BB, nullptr, TS); - for (Region::const_element_iterator I = CurRegion.element_begin(), - E = CurRegion.element_end(); - I != E; ++I) { - isl_schedule *StmtSchedule = nullptr; - if (I->isSubRegion()) { - StmtSchedule = - buildScop(tempScop, *I->getNodeAs(), NestLoops, LI, SD); - } else { - StmtSchedule = - buildBBScopStmt(I->getNodeAs(), tempScop, NestLoops); + auto *UDomain = isl_union_set_from_set(Stmt->getDomain()); + auto *StmtSchedule = isl_schedule_from_domain(UDomain); + LSchedulePair.first = + combineInSequence(LSchedulePair.first, StmtSchedule); } - Schedule = combineInSequence(Schedule, StmtSchedule); - } - if (!L) - 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); + unsigned NumVisited = LSchedulePair.second; + while (L && NumVisited == L->getNumBlocks()) { + auto *LDomain = isl_schedule_get_domain(LSchedulePair.first); + if (auto *MUPA = mapToDimension(LDomain, LD + 1)) + LSchedulePair.first = + isl_schedule_insert_partial_schedule(LSchedulePair.first, MUPA); + + auto *PL = L->getParentLoop(); + assert(LoopSchedules.count(PL)); + auto &PSchedulePair = LoopSchedules[PL]; + PSchedulePair.first = + combineInSequence(PSchedulePair.first, LSchedulePair.first); + PSchedulePair.second += NumVisited; + + L = PL; + NumVisited = PSchedulePair.second; + } } - isl_union_set_free(Domain); - - NestLoops.pop_back(); - return Schedule; } ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const { Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -28,36 +28,6 @@ #define DEBUG_TYPE "polly-scop-helper" -// Helper function for Scop -// TODO: Add assertion to not allow parameter to be null -//===----------------------------------------------------------------------===// -// Temporary Hack for extended region tree. -// Cast the region to loop if there is a loop have the same header and exit. -Loop *polly::castToLoop(const Region &R, LoopInfo &LI) { - BasicBlock *entry = R.getEntry(); - - if (!LI.isLoopHeader(entry)) - return 0; - - Loop *L = LI.getLoopFor(entry); - - BasicBlock *exit = L->getExitBlock(); - - // Is the loop with multiple exits? - if (!exit) - return 0; - - if (exit != R.getExit()) { - // SubRegion/ParentRegion with the same entry. - assert((R.getNode(R.getEntry())->isSubRegion() || - R.getParent()->getEntry() == entry) && - "Expect the loop is the smaller or bigger region"); - return 0; - } - - return L; -} - Value *polly::getPointerOperand(Instruction &Inst) { if (LoadInst *load = dyn_cast(&Inst)) return load->getPointerOperand(); Index: test/ScopInfo/phi_condition_modeling_2.ll =================================================================== --- test/ScopInfo/phi_condition_modeling_2.ll +++ test/ScopInfo/phi_condition_modeling_2.ll @@ -12,15 +12,15 @@ ; } ; ; CHECK: Statements { -; CHECK-LABEL: Stmt_bb6 +; CHECK-LABEL: Stmt_bb7 ; CHECK-NOT: Access ; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK: [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] }; +; CHECK: [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] }; ; CHECK-NOT: Access -; CHECK-LABEL: Stmt_bb7 +; CHECK-LABEL: Stmt_bb6 ; CHECK-NOT: Access ; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK: [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] }; +; CHECK: [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] }; ; CHECK-NOT: Access ; CHECK-LABEL: Stmt_bb8 ; CHECK-NOT: Access