Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -1670,9 +1670,6 @@ /// A map from basic blocks to SCoP statements. DenseMap StmtMap; - /// A map from basic blocks to their domains. - DenseMap DomainMap; - /// Constraints on parameters. isl_set *Context; @@ -1852,11 +1849,13 @@ /// @param BBLoop The innermost affine loop surrounding @p BB. /// @param FinishedExitBlocks Set of region exits the domain was set for. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current /// region. void propagateDomainConstraintsToRegionExit( BasicBlock *BB, Loop *BBLoop, SmallPtrSetImpl &FinishedExitBlocks, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap); /// Compute the union of predecessor domains for @p BB. @@ -1869,22 +1868,25 @@ /// @param Domain The domain under which BB is executed. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// /// @returns The domain under which @p BB is executed. __isl_give isl_set * getPredecessorDomainConstraints(BasicBlock *BB, __isl_keep isl_set *Domain, - DominatorTree &DT, LoopInfo &LI); + DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap); /// Add loop carried constraints to the header block of the loop @p L. /// /// @param L The loop to process. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current /// region. /// /// @returns True if there was no problem and false otherwise. bool addLoopBoundsToHeaderDomain( - Loop *L, LoopInfo &LI, + Loop *L, LoopInfo &LI, DenseMap &DomainMap, DenseMap &InvalidDomainMap); /// Compute the branching constraints for each basic block in @p R. @@ -1893,12 +1895,14 @@ /// for. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current /// region. /// /// @returns True if there was no problem and false otherwise. bool buildDomainsWithBranchConstraints( Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap); /// Propagate the domain constraints through the region @p R. @@ -1907,12 +1911,14 @@ /// for. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current /// region. /// /// @returns True if there was no problem and false otherwise. bool propagateDomainConstraints( Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap); /// Propagate invalid domains of statements through @p R. @@ -1925,12 +1931,14 @@ /// @param R The currently traversed region. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current /// region. // /// @returns True if there was no problem and false otherwise. bool propagateInvalidStmtDomains( Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap); /// Compute the domain for each basic block in @p R. @@ -1938,11 +1946,13 @@ /// @param R The region we currently traverse. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. + /// @param DomainMap BB to Domain map for the BB of current region. /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current /// region. /// /// @returns True if there was no problem and false otherwise. bool buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap); /// Add parameter constraints to @p C that imply a non-empty domain. @@ -2484,7 +2494,9 @@ BasicBlock *BB = nullptr); /// Add all recorded assumptions to the assumed context. - void addRecordedAssumptions(); + /// + /// @param DomainMap BB to Domain map for the BB of current region. + void addRecordedAssumptions(DenseMap &DomainMap); /// Mark the scop as invalid. /// @@ -2755,8 +2767,11 @@ /// Return the domain of @p BB. /// - /// @param BB The block for which the conditions should be returned. - __isl_give isl_set *getDomainConditions(BasicBlock *BB) const; + /// @param DomainMap BB to Domain map for the BB of current region. + /// @param BB The block for which the conditions should be returned. + __isl_give isl_set * + getDomainConditions(DenseMap &DomainMap, + BasicBlock *BB) const; /// Get a union set containing the iteration domains of all statements. __isl_give isl_union_set *getDomains() const; @@ -2819,10 +2834,12 @@ /// Simplify the SCoP representation. /// + /// @param DomainMap BB to Domain map for the BB of current region. /// @param AfterHoisting Whether it is called after invariant load hoisting. /// When true, also removes statements without /// side-effects. - void simplifySCoP(bool AfterHoisting); + void simplifySCoP(DenseMap &DomainMap, + bool AfterHoisting); /// Get the next free array index. /// Index: lib/Analysis/ScopBuilder.cpp =================================================================== --- lib/Analysis/ScopBuilder.cpp +++ lib/Analysis/ScopBuilder.cpp @@ -963,10 +963,13 @@ scop->buildInvariantEquivalenceClasses(); + /// A map from basic blocks to their domains. + DenseMap DomainMap; + /// A map from basic blocks to their invalid domains. DenseMap InvalidDomainMap; - if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) + if (!scop->buildDomains(&R, DT, LI, DomainMap, InvalidDomainMap)) return; scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap); @@ -982,7 +985,7 @@ // Remove empty statements. // Exit early in case there are no executable statements left in this scop. - scop->simplifySCoP(false); + scop->simplifySCoP(DomainMap, false); if (scop->isEmpty()) return; @@ -1011,7 +1014,7 @@ // After the context was fully constructed, thus all our knowledge about // the parameters is in there, we add all recorded assumptions to the // assumed/invalid context. - scop->addRecordedAssumptions(); + scop->addRecordedAssumptions(DomainMap); scop->simplifyContexts(); if (!scop->buildAliasChecks(AA)) @@ -1020,7 +1023,7 @@ scop->hoistInvariantLoads(); scop->canonicalizeDynamicBasePtrs(); scop->verifyInvariantLoads(); - scop->simplifySCoP(true); + scop->simplifySCoP(DomainMap, true); // Check late for a feasible runtime context because profitability did not // change. Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -2646,7 +2646,10 @@ return getDomainConditions(Stmt->getEntryBlock()); } -__isl_give isl_set *Scop::getDomainConditions(BasicBlock *BB) const { +__isl_give isl_set * +Scop::getDomainConditions(DenseMap &DomainMap, + BasicBlock *BB) const { + auto DIt = DomainMap.find(BB); if (DIt != DomainMap.end()) return DIt->getSecond().copy(); @@ -2655,10 +2658,11 @@ auto *BBR = RI.getRegionFor(BB); while (BBR->getEntry() == BB) BBR = BBR->getParent(); - return getDomainConditions(BBR->getEntry()); + return getDomainConditions(DomainMap, BBR->getEntry()); } bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap) { bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R); @@ -2678,10 +2682,11 @@ if (IsOnlyNonAffineRegion) return !containsErrorBlock(R->getNode(), *R, LI, DT); - if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap)) + if (!buildDomainsWithBranchConstraints(R, DT, LI, DomainMap, + InvalidDomainMap)) return false; - if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap)) + if (!propagateDomainConstraints(R, DT, LI, DomainMap, InvalidDomainMap)) return false; // Error blocks and blocks dominated by them have been assumed to never be @@ -2696,7 +2701,7 @@ // with an empty set. Additionally, we will record for each block under which // parameter combination it would be reached via an error block in its // InvalidDomain. This information is needed during load hoisting. - if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap)) + if (!propagateInvalidStmtDomains(R, DT, LI, DomainMap, InvalidDomainMap)) return false; return true; @@ -2754,6 +2759,7 @@ bool Scop::propagateInvalidStmtDomains( Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap) { ReversePostOrderTraversal RTraversal(R); @@ -2764,7 +2770,8 @@ if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs(); if (!isNonAffineSubRegion(SubRegion)) { - propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap); + propagateInvalidStmtDomains(SubRegion, DT, LI, DomainMap, + InvalidDomainMap); continue; } } @@ -2839,6 +2846,7 @@ void Scop::propagateDomainConstraintsToRegionExit( BasicBlock *BB, Loop *BBLoop, SmallPtrSetImpl &FinishedExitBlocks, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap) { // Check if the block @p BB is the entry of a region. If so we propagate it's @@ -2884,6 +2892,7 @@ bool Scop::buildDomainsWithBranchConstraints( Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap) { // To create the domain for each block in R we iterate over all blocks and @@ -2906,7 +2915,7 @@ if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs(); if (!isNonAffineSubRegion(SubRegion)) { - if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI, + if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI, DomainMap, InvalidDomainMap)) return false; continue; @@ -2931,7 +2940,7 @@ // Propagate the domain from BB directly to blocks that have a superset // domain, at the moment only region exit nodes of regions that start in BB. propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI, - InvalidDomainMap); + DomainMap, InvalidDomainMap); // If all successors of BB have been set a domain through the propagation // above we do not need to build condition sets but can just skip this @@ -3012,10 +3021,10 @@ return true; } -__isl_give isl_set * -Scop::getPredecessorDomainConstraints(BasicBlock *BB, - __isl_keep isl_set *Domain, - DominatorTree &DT, LoopInfo &LI) { +__isl_give isl_set *Scop::getPredecessorDomainConstraints( + BasicBlock *BB, __isl_keep isl_set *Domain, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap) { + // If @p BB is the ScopEntry we are done if (R.getEntry() == BB) return isl_set_universe(isl_set_get_space(Domain)); @@ -3058,7 +3067,7 @@ PropagatedRegions.insert(PredR); } - auto *PredBBDom = getDomainConditions(PredBB); + auto *PredBBDom = getDomainConditions(DomainMap, PredBB); Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops()); PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop); @@ -3071,7 +3080,9 @@ bool Scop::propagateDomainConstraints( Region *R, DominatorTree &DT, LoopInfo &LI, + DenseMap &DomainMap, DenseMap &InvalidDomainMap) { + // Iterate over the region R and propagate the domain constrains from the // predecessors to the current node. In contrast to the // buildDomainsWithBranchConstraints function, this one will pull the domain @@ -3089,7 +3100,8 @@ if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs(); if (!isNonAffineSubRegion(SubRegion)) { - if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap)) + if (!propagateDomainConstraints(SubRegion, DT, LI, DomainMap, + InvalidDomainMap)) return false; continue; } @@ -3100,14 +3112,14 @@ assert(Domain); // Under the union of all predecessor conditions we can reach this block. - isl::set PredDom = - isl::manage(getPredecessorDomainConstraints(BB, Domain.get(), DT, LI)); + isl::set PredDom = isl::manage( + getPredecessorDomainConstraints(BB, Domain.get(), DT, LI, DomainMap)); Domain = Domain.intersect(PredDom).coalesce(); Domain = Domain.align_params(isl::manage(getParamSpace())); Loop *BBLoop = getRegionNodeLoop(RN, LI); if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop)) - if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap)) + if (!addLoopBoundsToHeaderDomain(BBLoop, LI, DomainMap, InvalidDomainMap)) return false; } @@ -3138,7 +3150,9 @@ } bool Scop::addLoopBoundsToHeaderDomain( - Loop *L, LoopInfo &LI, DenseMap &InvalidDomainMap) { + Loop *L, LoopInfo &LI, DenseMap &DomainMap, + DenseMap &InvalidDomainMap) { + int LoopDepth = getRelativeLoopDepth(L); assert(LoopDepth >= 0 && "Loop in region should have at least depth one"); @@ -3728,7 +3742,9 @@ Access->assumeNoOutOfBound(); } -void Scop::simplifySCoP(bool AfterHoisting) { +void Scop::simplifySCoP(DenseMap &DomainMap, + bool AfterHoisting) { + for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) { ScopStmt &Stmt = *StmtIt; @@ -4389,7 +4405,8 @@ RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB}); } -void Scop::addRecordedAssumptions() { +void Scop::addRecordedAssumptions(DenseMap &DomainMap) { + while (!RecordedAssumptions.empty()) { const Assumption &AS = RecordedAssumptions.pop_back_val(); @@ -4399,7 +4416,7 @@ } // If the domain was deleted the assumptions are void. - isl_set *Dom = getDomainConditions(AS.BB); + isl_set *Dom = getDomainConditions(DomainMap, AS.BB); if (!Dom) { isl_set_free(AS.Set); continue; Index: lib/Support/SCEVAffinator.cpp =================================================================== --- lib/Support/SCEVAffinator.cpp +++ lib/Support/SCEVAffinator.cpp @@ -135,6 +135,7 @@ if (BB) { auto *DC = S->getDomainConditions(BB); + NumIterators = isl_set_n_dim(DC); isl_set_free(DC); } else Index: lib/Transform/Simplify.cpp =================================================================== --- lib/Transform/Simplify.cpp +++ lib/Transform/Simplify.cpp @@ -307,6 +307,7 @@ void removeUnnecessaryStmts() { auto NumStmtsBefore = S->getSize(); S->simplifySCoP(true); + assert(NumStmtsBefore >= S->getSize()); StmtsRemoved = NumStmtsBefore - S->getSize(); DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore