From 7c01357cef0c0809d079e96d52609b5ed8ae6192 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Tue, 12 Apr 2016 09:57:34 +0000 Subject: [PATCH] Introduce an invalid context for each statement Collect the error domain contexts (formerly in the ErrorDomainCtxMap) for each statement in the new InvalidContext member variable. While this commit is basically a [NFC] it is a first step to make hoisting sound by allowing a more fine grained record of invalid contexts, e.g., here on statement level. llvm-svn: 266053 --- polly/include/polly/ScopInfo.h | 42 ++++++------ polly/lib/Analysis/ScopInfo.cpp | 74 +++++++++++++--------- .../invariant_loads_complicated_dependences.ll | 2 +- 3 files changed, 68 insertions(+), 50 deletions(-) diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 9a29e6c..f0f078f 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -932,6 +932,14 @@ private: /// The Scop containing this ScopStmt Scop &Parent; + /// @brief The context under which this statement is not modeled precisely. + /// + /// The invalid context for a statement describes all parameter combinations + /// under which the statement looks to be executed but is in fact not because + /// some assumption/restriction makes the statement/scop invalid. Currently + /// it is build only using error block domain contexts. + isl_set *InvalidContext; + /// The iteration domain describes the set of iterations for which this /// statement is executed. /// @@ -1086,6 +1094,14 @@ public: /// @brief Get an isl string representing this schedule. std::string getScheduleStr() const; + /// @brief Get the invalid context for this statement. + __isl_give isl_set *getInvalidContext() const { + return isl_set_copy(InvalidContext); + } + + /// @brief Set the invalid context for this statement to @p IC. + void setInvalidContext(__isl_take isl_set *IC); + /// @brief Get the BasicBlock represented by this ScopStmt (if any). /// /// @return The BasicBlock represented by this ScopStmt, or null if the @@ -1332,14 +1348,6 @@ private: /// @brief A map from basic blocks to their domains. DenseMap DomainMap; - /// @brief A map from basic blocks to the error context reaching them. - /// - /// The error context describes all parameter configurations under which - /// the block would be executed but the control would pass an error block. - /// This information is not contained in the domain and only implicit in the - /// AssumedContext/InvalidContext. - DenseMap ErrorDomainCtxMap; - /// Constraints on parameters. isl_set *Context; @@ -1517,20 +1525,19 @@ private: void propagateDomainConstraints(Region *R, ScopDetection &SD, DominatorTree &DT, LoopInfo &LI); - /// @brief Propagate of error block domain contexts through @p R. + /// @brief Propagate invalid contexts of statements through @p R. /// - /// This method will propagate error block domain contexts through @p R - /// and thereby fill the ErrorDomainCtxMap map. Additionally, the domains - /// of error statements and those only reachable via error statements will - /// be replaced by an empty set. Later those will be removed completely from - /// the SCoP. + /// This method will propagate invalid statement contexts through @p R and at + /// the same time add error block domain context to them. Additionally, the + /// domains of error statements and those only reachable via error statements + /// will be replaced by an empty set. Later those will be removed completely. /// /// @param R The currently traversed region. /// @param SD The ScopDetection analysis for the current function. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. - void propagateErrorConstraints(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI); + void propagateInvalidStmtContexts(Region *R, ScopDetection &SD, + DominatorTree &DT, LoopInfo &LI); /// @brief Compute the domain for each basic block in @p R. /// @@ -1566,9 +1573,6 @@ private: /// @see isIgnored() void simplifySCoP(bool RemoveIgnoredStmts, DominatorTree &DT, LoopInfo &LI); - /// @brief Return the error context under which @p Stmt is reached. - __isl_give isl_set *getErrorCtxReachingStmt(ScopStmt &Stmt); - /// @brief Create equivalence classes for required invariant accesses. /// /// These classes will consolidate multiple required invariant loads from the diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index ed9479d..4c97cce 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -1091,6 +1091,7 @@ void ScopStmt::realignParams() { for (MemoryAccess *MA : *this) MA->realignParams(); + InvalidContext = isl_set_align_params(InvalidContext, Parent.getParamSpace()); Domain = isl_set_align_params(Domain, Parent.getParamSpace()); } @@ -1437,13 +1438,15 @@ void ScopStmt::collectSurroundingLoops() { } ScopStmt::ScopStmt(Scop &parent, Region &R) - : Parent(parent), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) { + : Parent(parent), InvalidContext(isl_set_empty(Parent.getParamSpace())), + Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) { BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), ""); } ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb) - : Parent(parent), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) { + : Parent(parent), InvalidContext(isl_set_empty(Parent.getParamSpace())), + Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) { BaseName = getIslCompatibleName("Stmt_", &bb, ""); } @@ -1605,6 +1608,11 @@ std::string ScopStmt::getScheduleStr() const { return Str; } +void ScopStmt::setInvalidContext(__isl_take isl_set *IC) { + isl_set_free(InvalidContext); + InvalidContext = IC; +} + BasicBlock *ScopStmt::getEntryBlock() const { if (isBlockStmt()) return getBasicBlock(); @@ -1639,7 +1647,10 @@ __isl_give isl_id *ScopStmt::getDomainId() const { return isl_set_get_tuple_id(Domain); } -ScopStmt::~ScopStmt() { isl_set_free(Domain); } +ScopStmt::~ScopStmt() { + isl_set_free(Domain); + isl_set_free(InvalidContext); +} void ScopStmt::print(raw_ostream &OS) const { OS << "\t" << getBaseName() << "\n"; @@ -2222,9 +2233,9 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT, // can themselves not be constructed properly. To this end we will replace // the domains of error blocks and those only reachable via error blocks // with an empty set. Additionally, we will record for each block under which - // parameter combination it would be reached via an error block in the - // ErrorDomainCtxMap map. This information is needed during load hoisting. - propagateErrorConstraints(R, SD, DT, LI); + // parameter combination it would be reached via an error block in its + // InvalidContext. This information is needed during load hoisting. + propagateInvalidStmtContexts(R, SD, DT, LI); return true; } @@ -2288,8 +2299,8 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S, return Dom; } -void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI) { +void Scop::propagateInvalidStmtContexts(Region *R, ScopDetection &SD, + DominatorTree &DT, LoopInfo &LI) { ReversePostOrderTraversal RTraversal(R); for (auto *RN : RTraversal) { @@ -2299,23 +2310,24 @@ void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD, if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs(); if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { - propagateErrorConstraints(SubRegion, SD, DT, LI); + propagateInvalidStmtContexts(SubRegion, SD, DT, LI); continue; } } bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT); BasicBlock *BB = getRegionNodeBasicBlock(RN); + ScopStmt *Stmt = getStmtFor(BB); isl_set *&Domain = DomainMap[BB]; assert(Domain && "Cannot propagate a nullptr"); - auto *&ErrorCtx = ErrorDomainCtxMap[BB]; + auto *InvalidCtx = Stmt->getInvalidContext(); auto *DomainCtx = isl_set_params(isl_set_copy(Domain)); - bool IsErrorBlock = ContainsErrorBlock || - (ErrorCtx && isl_set_is_subset(DomainCtx, ErrorCtx)); + bool IsInvalidBlock = + ContainsErrorBlock || isl_set_is_subset(DomainCtx, InvalidCtx); - if (IsErrorBlock) { - ErrorCtx = ErrorCtx ? isl_set_union(ErrorCtx, DomainCtx) : DomainCtx; + if (IsInvalidBlock) { + InvalidCtx = isl_set_coalesce(isl_set_union(InvalidCtx, DomainCtx)); auto *EmptyDom = isl_set_empty(isl_set_get_space(Domain)); isl_set_free(Domain); Domain = EmptyDom; @@ -2323,22 +2335,32 @@ void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD, isl_set_free(DomainCtx); } - if (!ErrorCtx) + if (isl_set_is_empty(InvalidCtx)) { + isl_set_free(InvalidCtx); continue; + } + + Stmt->setInvalidContext(InvalidCtx); auto *TI = BB->getTerminator(); unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors(); for (unsigned u = 0; u < NumSuccs; u++) { auto *SuccBB = getRegionNodeSuccessor(RN, TI, u); - auto *&SuccErrorCtx = ErrorDomainCtxMap[SuccBB]; - auto *CurErrorCtx = isl_set_copy(ErrorCtx); - SuccErrorCtx = - SuccErrorCtx ? isl_set_union(SuccErrorCtx, CurErrorCtx) : CurErrorCtx; - SuccErrorCtx = isl_set_coalesce(SuccErrorCtx); + auto *SuccStmt = getStmtFor(SuccBB); + + // Skip successors outside the SCoP. + if (!SuccStmt) + continue; + + auto *SuccInvalidCtx = SuccStmt->getInvalidContext(); + SuccInvalidCtx = isl_set_union(SuccInvalidCtx, Stmt->getInvalidContext()); + SuccInvalidCtx = isl_set_coalesce(SuccInvalidCtx); + unsigned NumConjucts = isl_set_n_basic_set(SuccInvalidCtx); + SuccStmt->setInvalidContext(SuccInvalidCtx); // Check if the maximal number of domain conjuncts was reached. // In case this happens we will bail. - if (isl_set_n_basic_set(SuccErrorCtx) < MaxConjunctsInDomain) + if (NumConjucts < MaxConjunctsInDomain) continue; invalidate(COMPLEXITY, TI->getDebugLoc()); @@ -3016,8 +3038,6 @@ Scop::~Scop() { for (auto It : DomainMap) isl_set_free(It.second); - for (auto It : ErrorDomainCtxMap) - isl_set_free(It.second); // Free the alias groups for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) { @@ -3130,18 +3150,12 @@ const InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) const { return nullptr; } -__isl_give isl_set *Scop::getErrorCtxReachingStmt(ScopStmt &Stmt) { - auto *BB = Stmt.getEntryBlock(); - return isl_set_copy(ErrorDomainCtxMap.lookup(BB)); -} - void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) { // Get the context under which the statement is executed but remove the error // context under which this statement is reached. isl_set *DomainCtx = isl_set_params(Stmt.getDomain()); - if (auto *ErrorCtx = getErrorCtxReachingStmt(Stmt)) - DomainCtx = isl_set_subtract(DomainCtx, ErrorCtx); + DomainCtx = isl_set_subtract(DomainCtx, Stmt.getInvalidContext()); DomainCtx = isl_set_remove_redundancies(DomainCtx); DomainCtx = isl_set_detect_equalities(DomainCtx); DomainCtx = isl_set_coalesce(DomainCtx); diff --git a/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll b/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll index fe88b63..99cb35c 100644 --- a/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll +++ b/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll @@ -9,7 +9,7 @@ ; CHECK-NEXT: Execution Context: [LB, UB] -> { : } ; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] ; CHECK-NEXT: [LB, UB] -> { Stmt_if_then[i0, i1] -> MemRef_V[0] }; -; CHECK-NEXT: Execution Context: [LB, UB] -> { : (UB > LB and UB >= 6) or LB >= 6 } +; CHECK-NEXT: Execution Context: [LB, UB] -> { : LB >= 6 or (UB > LB and UB >= 6) } ; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] ; CHECK-NEXT: [LB, UB] -> { Stmt_if_else[i0, i1] -> MemRef_U[0] }; ; CHECK-NEXT: Execution Context: [LB, UB] -> { : LB <= 5 } -- 2.7.4