Index: polly/include/polly/ScopBuilder.h =================================================================== --- polly/include/polly/ScopBuilder.h +++ polly/include/polly/ScopBuilder.h @@ -123,6 +123,172 @@ // Build the SCoP for Region @p R. void buildScop(Region &R, AssumptionCache &AC); + /// Adjust the dimensions of @p Dom that was constructed for @p OldL + /// to be compatible to domains constructed for loop @p NewL. + /// + /// This function assumes @p NewL and @p OldL are equal or there is a CFG + /// edge from @p OldL to @p NewL. + isl::set adjustDomainDimensions(isl::set Dom, Loop *OldL, Loop *NewL); + + /// Compute the domain for each basic block in @p R. + /// + /// @param R The region we currently traverse. + /// @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, + DenseMap &InvalidDomainMap); + + /// Compute the branching constraints for each basic block in @p R. + /// + /// @param R The region we currently build branching conditions + /// for. + /// @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, DenseMap &InvalidDomainMap); + + /// Build the conditions sets for the terminator @p TI in the @p Domain. + /// + /// This will fill @p ConditionSets with the conditions under which control + /// will be moved from @p TI to its successors. Hence, @p ConditionSets will + /// have as many elements as @p TI has successors. + bool buildConditionSets(BasicBlock *BB, Instruction *TI, Loop *L, + __isl_keep isl_set *Domain, + DenseMap &InvalidDomainMap, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets); + + /// Build the conditions sets for the branch condition @p Condition in + /// the @p Domain. + /// + /// This will fill @p ConditionSets with the conditions under which control + /// will be moved from @p TI to its successors. Hence, @p ConditionSets will + /// have as many elements as @p TI has successors. If @p TI is nullptr the + /// context under which @p Condition is true/false will be returned as the + /// new elements of @p ConditionSets. + bool buildConditionSets(BasicBlock *BB, Value *Condition, Instruction *TI, + Loop *L, __isl_keep isl_set *Domain, + DenseMap &InvalidDomainMap, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets); + + /// Build the conditions sets for the switch @p SI in the @p Domain. + /// + /// This will fill @p ConditionSets with the conditions under which control + /// will be moved from @p SI to its successors. Hence, @p ConditionSets will + /// have as many elements as @p SI has successors. + bool buildConditionSets(BasicBlock *BB, SwitchInst *SI, Loop *L, + __isl_keep isl_set *Domain, + DenseMap &InvalidDomainMap, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets); + + /// Build condition sets for unsigned ICmpInst(s). + /// Special handling is required for unsigned operands to ensure that if + /// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst + /// it should wrap around. + /// + /// @param IsStrictUpperBound holds information on the predicate relation + /// between TestVal and UpperBound, i.e, + /// TestVal < UpperBound OR TestVal <= UpperBound + __isl_give isl_set *buildUnsignedConditionSets( + BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, + const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound, + DenseMap &InvalidDomainMap, + bool IsStrictUpperBound); + + /// Propagate the domain constraints through the region @p R. + /// + /// @param R The region we currently build branching + /// conditions for. + /// @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, DenseMap &InvalidDomainMap); + + /// Propagate domains that are known due to graph properties. + /// + /// As a CFG is mostly structured we use the graph properties to propagate + /// domains without the need to compute all path conditions. In particular, + /// if a block A dominates a block B and B post-dominates A we know that the + /// domain of B is a superset of the domain of A. As we do not have + /// post-dominator information available here we use the less precise region + /// information. Given a region R, we know that the exit is always executed + /// if the entry was executed, thus the domain of the exit is a superset of + /// the domain of the entry. In case the exit can only be reached from + /// within the region the domains are in fact equal. This function will use + /// this property to avoid the generation of condition constraints that + /// determine when a branch is taken. If @p BB is a region entry block we + /// will propagate its domain to the region exit block. Additionally, we put + /// the region exit block in the @p FinishedExitBlocks set so we can later + /// skip edges from within the region to that block. + /// + /// @param BB The block for which the domain is currently + /// propagated. + /// @param BBLoop The innermost affine loop surrounding @p BB. + /// @param FinishedExitBlocks Set of region exits the domain was set for. + /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current + /// region. + void propagateDomainConstraintsToRegionExit( + BasicBlock *BB, Loop *BBLoop, + SmallPtrSetImpl &FinishedExitBlocks, + DenseMap &InvalidDomainMap); + + /// Propagate invalid domains of statements through @p R. + /// + /// This method will propagate invalid statement domains through @p R and at + /// the same time add error block domains 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 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, DenseMap &InvalidDomainMap); + + /// Compute the union of predecessor domains for @p BB. + /// + /// To compute the union of all domains of predecessors of @p BB this + /// function applies similar reasoning on the CFG structure as described for + /// @see propagateDomainConstraintsToRegionExit + /// + /// @param BB The block for which the predecessor domains are collected. + /// @param Domain The domain under which BB is executed. + /// + /// @returns The domain under which @p BB is executed. + isl::set getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain); + + /// Add loop carried constraints to the header block of the loop @p L. + /// + /// @param L The loop to process. + /// @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, DenseMap &InvalidDomainMap); + + /// Compute the isl representation for the SCEV @p E in this BB. + /// + /// @param BB The BB for which isl representation is to be + /// computed. + /// @param InvalidDomainMap A map of BB to their invalid domains. + /// @param E The SCEV that should be translated. + /// @param NonNegative Flag to indicate the @p E has to be + /// non-negative. + /// + /// Note that this function will also adjust the invalid context + /// accordingly. + __isl_give isl_pw_aff * + getPwAff(BasicBlock *BB, DenseMap &InvalidDomainMap, + const SCEV *E, bool NonNegative = false); + /// Create equivalence classes for required invariant accesses. /// /// These classes will consolidate multiple required invariant loads from the Index: polly/include/polly/ScopInfo.h =================================================================== --- polly/include/polly/ScopInfo.h +++ polly/include/polly/ScopInfo.h @@ -1641,43 +1641,6 @@ /// An optional block whose domain can simplify the assumption. BasicBlock *BB; }; -/// Build the conditions sets for the branch condition @p Condition in -/// the @p Domain. -/// -/// This will fill @p ConditionSets with the conditions under which control -/// will be moved from @p TI to its successors. Hence, @p ConditionSets will -/// have as many elements as @p TI has successors. If @p TI is nullptr the -/// context under which @p Condition is true/false will be returned as the -/// new elements of @p ConditionSets. -bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition, - Instruction *TI, Loop *L, __isl_keep isl_set *Domain, - DenseMap &InvalidDomainMap, - SmallVectorImpl<__isl_give isl_set *> &ConditionSets); - -/// Build condition sets for unsigned ICmpInst(s). -/// Special handling is required for unsigned operands to ensure that if -/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst -/// it should wrap around. -/// -/// @param IsStrictUpperBound holds information on the predicate relation -/// between TestVal and UpperBound, i.e, -/// TestVal < UpperBound OR TestVal <= UpperBound -__isl_give isl_set * -buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition, - __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal, - const SCEV *SCEV_UpperBound, - DenseMap &InvalidDomainMap, - bool IsStrictUpperBound); - -/// Build the conditions sets for the terminator @p TI in the @p Domain. -/// -/// This will fill @p ConditionSets with the conditions under which control -/// will be moved from @p TI to its successors. Hence, @p ConditionSets will -/// have as many elements as @p TI has successors. -bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L, - __isl_keep isl_set *Domain, - DenseMap &InvalidDomainMap, - SmallVectorImpl<__isl_give isl_set *> &ConditionSets); /// Static Control Part /// @@ -1951,120 +1914,6 @@ void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI); - /// Propagate domains that are known due to graph properties. - /// - /// As a CFG is mostly structured we use the graph properties to propagate - /// domains without the need to compute all path conditions. In particular, if - /// a block A dominates a block B and B post-dominates A we know that the - /// domain of B is a superset of the domain of A. As we do not have - /// post-dominator information available here we use the less precise region - /// information. Given a region R, we know that the exit is always executed if - /// the entry was executed, thus the domain of the exit is a superset of the - /// domain of the entry. In case the exit can only be reached from within the - /// region the domains are in fact equal. This function will use this property - /// to avoid the generation of condition constraints that determine when a - /// branch is taken. If @p BB is a region entry block we will propagate its - /// domain to the region exit block. Additionally, we put the region exit - /// block in the @p FinishedExitBlocks set so we can later skip edges from - /// within the region to that block. - /// - /// @param BB The block for which the domain is currently - /// propagated. - /// @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 InvalidDomainMap BB to InvalidDomain map for the BB of current - /// region. - void propagateDomainConstraintsToRegionExit( - BasicBlock *BB, Loop *BBLoop, - SmallPtrSetImpl &FinishedExitBlocks, LoopInfo &LI, - DenseMap &InvalidDomainMap); - - /// Compute the union of predecessor domains for @p BB. - /// - /// To compute the union of all domains of predecessors of @p BB this - /// function applies similar reasoning on the CFG structure as described for - /// @see propagateDomainConstraintsToRegionExit - /// - /// @param BB The block for which the predecessor domains are collected. - /// @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. - /// - /// @returns The domain under which @p BB is executed. - isl::set getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain, - DominatorTree &DT, LoopInfo &LI); - - /// 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 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, - DenseMap &InvalidDomainMap); - - /// Compute the branching constraints for each basic block in @p R. - /// - /// @param R The region we currently build branching conditions - /// for. - /// @param DT The DominatorTree for the current function. - /// @param LI The LoopInfo for the current function. - /// @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 &InvalidDomainMap); - - /// Propagate the domain constraints through the region @p R. - /// - /// @param R The region we currently build branching conditions - /// for. - /// @param DT The DominatorTree for the current function. - /// @param LI The LoopInfo for the current function. - /// @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 &InvalidDomainMap); - - /// Propagate invalid domains of statements through @p R. - /// - /// This method will propagate invalid statement domains through @p R and at - /// the same time add error block domains 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 DT The DominatorTree for the current function. - /// @param LI The LoopInfo for the current function. - /// @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 &InvalidDomainMap); - - /// Compute the domain for each basic block in @p R. - /// - /// @param R The region we currently traverse. - /// @param DT The DominatorTree for the current function. - /// @param LI The LoopInfo for the current function. - /// @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 &InvalidDomainMap); - /// Add parameter constraints to @p C that imply a non-empty domain. isl::set addNonEmptyDomainConstraints(isl::set C) const; @@ -2640,8 +2489,15 @@ ScopArrayInfoMap.erase(It); } + /// Set new isl context. void setContext(isl::set NewContext); + /// Update maximal loop depth. If @p Depth is smaller than current value, + /// then maximal loop depth is not updated. + void updateMaxLoopDepth(unsigned Depth) { + MaxLoopDepth = std::max(MaxLoopDepth, Depth); + } + /// Align the parameters in the statement to the scop context void realignParams(); @@ -2656,6 +2512,9 @@ /// Return true if the SCoP contained at least one error block. bool hasErrorBlock() const { return HasErrorBlock; } + /// Notify SCoP that it contains an error block + void notifyErrorBlock() { HasErrorBlock = true; } + /// Return true if the underlying region has a single exiting block. bool hasSingleExitEdge() const { return HasSingleExitEdge; } @@ -2700,6 +2559,9 @@ /// domain part associated with the piecewise affine function. isl::pw_aff getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr); + /// Check if an AddRec for the loop L is cached. + bool hasNSWAddRecForLoop(Loop *L) { return Affinator.hasNSWAddRecForLoop(L); } + /// Return the domain of @p Stmt. /// /// @param Stmt The statement for which the conditions should be returned. @@ -2710,6 +2572,15 @@ /// @param BB The block for which the conditions should be returned. isl::set getDomainConditions(BasicBlock *BB) const; + /// Return the domain of @p BB. If it does not exist, create an empty one. + isl::set &getOrInitEmptyDomain(BasicBlock *BB) { return DomainMap[BB]; } + + /// Check if domain is determined for @p BB. + bool isDomainDefined(BasicBlock *BB) const { return DomainMap.count(BB) > 0; } + + /// Set domain for @p BB. + void setDomain(BasicBlock *BB, isl::set &Domain) { DomainMap[BB] = Domain; } + /// Get a union set containing the iteration domains of all statements. isl::union_set getDomains() const; Index: polly/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/lib/Analysis/ScopBuilder.cpp +++ polly/lib/Analysis/ScopBuilder.cpp @@ -25,6 +25,7 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/EquivalenceClasses.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" @@ -153,6 +154,654 @@ "Store-level granularity")), cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory)); +/// Helper to treat non-affine regions and basic blocks the same. +/// +///{ + +/// Return the block that is the representing block for @p RN. +static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) { + return RN->isSubRegion() ? RN->getNodeAs()->getEntry() + : RN->getNodeAs(); +} + +/// Return the @p idx'th block that is executed after @p RN. +static inline BasicBlock * +getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) { + if (RN->isSubRegion()) { + assert(idx == 0); + return RN->getNodeAs()->getExit(); + } + return TI->getSuccessor(idx); +} + +static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI, + const DominatorTree &DT) { + if (!RN->isSubRegion()) + return isErrorBlock(*RN->getNodeAs(), R, LI, DT); + for (BasicBlock *BB : RN->getNodeAs()->blocks()) + if (isErrorBlock(*BB, R, LI, DT)) + return true; + return false; +} + +///} + +/// Create a map to map from a given iteration to a subsequent iteration. +/// +/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim +/// is incremented by one and all other dimensions are equal, e.g., +/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3] +/// +/// if @p Dim is 2 and @p SetSpace has 4 dimensions. +static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) { + isl::space MapSpace = SetSpace.map_from_set(); + isl::map NextIterationMap = isl::map::universe(MapSpace); + for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++) + if (u != Dim) + NextIterationMap = + NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u); + isl::constraint C = + isl::constraint::alloc_equality(isl::local_space(MapSpace)); + C = C.set_constant_si(1); + C = C.set_coefficient_si(isl::dim::in, Dim, 1); + C = C.set_coefficient_si(isl::dim::out, Dim, -1); + NextIterationMap = NextIterationMap.add_constraint(C); + return NextIterationMap; +} + +/// Add @p BSet to set @p BoundedParts if @p BSet is bounded. +static isl::set collectBoundedParts(isl::set S) { + isl::set BoundedParts = isl::set::empty(S.get_space()); + for (isl::basic_set BSet : S.get_basic_set_list()) + if (BSet.is_bounded()) + BoundedParts = BoundedParts.unite(isl::set(BSet)); + return BoundedParts; +} + +/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim. +/// +/// @returns A separation of @p S into first an unbounded then a bounded subset, +/// both with regards to the dimension @p Dim. +static std::pair partitionSetParts(isl::set S, + unsigned Dim) { + for (unsigned u = 0, e = S.n_dim(); u < e; u++) + S = S.lower_bound_si(isl::dim::set, u, 0); + + unsigned NumDimsS = S.n_dim(); + isl::set OnlyDimS = S; + + // Remove dimensions that are greater than Dim as they are not interesting. + assert(NumDimsS >= Dim + 1); + OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1); + + // Create artificial parametric upper bounds for dimensions smaller than Dim + // as we are not interested in them. + OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim); + + for (unsigned u = 0; u < Dim; u++) { + isl::constraint C = isl::constraint::alloc_inequality( + isl::local_space(OnlyDimS.get_space())); + C = C.set_coefficient_si(isl::dim::param, u, 1); + C = C.set_coefficient_si(isl::dim::set, u, -1); + OnlyDimS = OnlyDimS.add_constraint(C); + } + + // Collect all bounded parts of OnlyDimS. + isl::set BoundedParts = collectBoundedParts(OnlyDimS); + + // Create the dimensions greater than Dim again. + BoundedParts = + BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1); + + // Remove the artificial upper bound parameters again. + BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim); + + isl::set UnboundedParts = S.subtract(BoundedParts); + return std::make_pair(UnboundedParts, BoundedParts); +} + +/// Create the conditions under which @p L @p Pred @p R is true. +static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L, + isl::pw_aff R) { + switch (Pred) { + case ICmpInst::ICMP_EQ: + return L.eq_set(R); + case ICmpInst::ICMP_NE: + return L.ne_set(R); + case ICmpInst::ICMP_SLT: + return L.lt_set(R); + case ICmpInst::ICMP_SLE: + return L.le_set(R); + case ICmpInst::ICMP_SGT: + return L.gt_set(R); + case ICmpInst::ICMP_SGE: + return L.ge_set(R); + case ICmpInst::ICMP_ULT: + return L.lt_set(R); + case ICmpInst::ICMP_UGT: + return L.gt_set(R); + case ICmpInst::ICMP_ULE: + return L.le_set(R); + case ICmpInst::ICMP_UGE: + return L.ge_set(R); + default: + llvm_unreachable("Non integer predicate not supported"); + } +} + +isl::set ScopBuilder::adjustDomainDimensions(isl::set Dom, Loop *OldL, + Loop *NewL) { + // If the loops are the same there is nothing to do. + if (NewL == OldL) + return Dom; + + int OldDepth = scop->getRelativeLoopDepth(OldL); + int NewDepth = scop->getRelativeLoopDepth(NewL); + // If both loops are non-affine loops there is nothing to do. + if (OldDepth == -1 && NewDepth == -1) + return Dom; + + // Distinguish three cases: + // 1) The depth is the same but the loops are not. + // => One loop was left one was entered. + // 2) The depth increased from OldL to NewL. + // => One loop was entered, none was left. + // 3) The depth decreased from OldL to NewL. + // => Loops were left were difference of the depths defines how many. + if (OldDepth == NewDepth) { + assert(OldL->getParentLoop() == NewL->getParentLoop()); + Dom = Dom.project_out(isl::dim::set, NewDepth, 1); + Dom = Dom.add_dims(isl::dim::set, 1); + } else if (OldDepth < NewDepth) { + assert(OldDepth + 1 == NewDepth); + auto &R = scop->getRegion(); + (void)R; + assert(NewL->getParentLoop() == OldL || + ((!OldL || !R.contains(OldL)) && R.contains(NewL))); + Dom = Dom.add_dims(isl::dim::set, 1); + } else { + assert(OldDepth > NewDepth); + int Diff = OldDepth - NewDepth; + int NumDim = Dom.n_dim(); + assert(NumDim >= Diff); + Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff); + } + + return Dom; +} + +/// Compute the isl representation for the SCEV @p E in this BB. +/// +/// @param BB The BB for which isl representation is to be +/// computed. +/// @param InvalidDomainMap A map of BB to their invalid domains. +/// @param E The SCEV that should be translated. +/// @param NonNegative Flag to indicate the @p E has to be non-negative. +/// +/// Note that this function will also adjust the invalid context accordingly. + +__isl_give isl_pw_aff * +ScopBuilder::getPwAff(BasicBlock *BB, + DenseMap &InvalidDomainMap, + const SCEV *E, bool NonNegative) { + PWACtx PWAC = scop->getPwAff(E, BB, NonNegative); + InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second); + return PWAC.first.release(); +} + +/// Build condition sets for unsigned ICmpInst(s). +/// Special handling is required for unsigned operands to ensure that if +/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst +/// it should wrap around. +/// +/// @param IsStrictUpperBound holds information on the predicate relation +/// between TestVal and UpperBound, i.e, +/// TestVal < UpperBound OR TestVal <= UpperBound +__isl_give isl_set *ScopBuilder::buildUnsignedConditionSets( + BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, + const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound, + DenseMap &InvalidDomainMap, + bool IsStrictUpperBound) { + // Do not take NonNeg assumption on TestVal + // as it might have MSB (Sign bit) set. + isl_pw_aff *TestVal = getPwAff(BB, InvalidDomainMap, SCEV_TestVal, false); + // Take NonNeg assumption on UpperBound. + isl_pw_aff *UpperBound = + getPwAff(BB, InvalidDomainMap, SCEV_UpperBound, true); + + // 0 <= TestVal + isl_set *First = + isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space( + isl_pw_aff_get_domain_space(TestVal))), + isl_pw_aff_copy(TestVal)); + + isl_set *Second; + if (IsStrictUpperBound) + // TestVal < UpperBound + Second = isl_pw_aff_lt_set(TestVal, UpperBound); + else + // TestVal <= UpperBound + Second = isl_pw_aff_le_set(TestVal, UpperBound); + + isl_set *ConsequenceCondSet = isl_set_intersect(First, Second); + return ConsequenceCondSet; +} + +bool ScopBuilder::buildConditionSets( + BasicBlock *BB, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain, + DenseMap &InvalidDomainMap, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { + Value *Condition = getConditionFromTerminator(SI); + assert(Condition && "No condition for switch"); + + isl_pw_aff *LHS, *RHS; + LHS = getPwAff(BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L)); + + unsigned NumSuccessors = SI->getNumSuccessors(); + ConditionSets.resize(NumSuccessors); + for (auto &Case : SI->cases()) { + unsigned Idx = Case.getSuccessorIndex(); + ConstantInt *CaseValue = Case.getCaseValue(); + + RHS = getPwAff(BB, InvalidDomainMap, SE.getSCEV(CaseValue)); + isl_set *CaseConditionSet = + buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS), + isl::manage(RHS)) + .release(); + ConditionSets[Idx] = isl_set_coalesce( + isl_set_intersect(CaseConditionSet, isl_set_copy(Domain))); + } + + assert(ConditionSets[0] == nullptr && "Default condition set was set"); + isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]); + for (unsigned u = 2; u < NumSuccessors; u++) + ConditionSetUnion = + isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u])); + ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion); + + isl_pw_aff_free(LHS); + + return true; +} + +bool ScopBuilder::buildConditionSets( + BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L, + __isl_keep isl_set *Domain, + DenseMap &InvalidDomainMap, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { + isl_set *ConsequenceCondSet = nullptr; + + if (auto Load = dyn_cast(Condition)) { + const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L); + const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType()); + bool NonNeg = false; + isl_pw_aff *LHS = getPwAff(BB, InvalidDomainMap, LHSSCEV, NonNeg); + isl_pw_aff *RHS = getPwAff(BB, InvalidDomainMap, RHSSCEV, NonNeg); + ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS), + isl::manage(RHS)) + .release(); + } else if (auto *PHI = dyn_cast(Condition)) { + auto *Unique = dyn_cast( + getUniqueNonErrorValue(PHI, &scop->getRegion(), LI, DT)); + + if (Unique->isZero()) + ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain)); + else + ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain)); + } else if (auto *CCond = dyn_cast(Condition)) { + if (CCond->isZero()) + ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain)); + else + ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain)); + } else if (BinaryOperator *BinOp = dyn_cast(Condition)) { + auto Opcode = BinOp->getOpcode(); + assert(Opcode == Instruction::And || Opcode == Instruction::Or); + + bool Valid = buildConditionSets(BB, BinOp->getOperand(0), TI, L, Domain, + InvalidDomainMap, ConditionSets) && + buildConditionSets(BB, BinOp->getOperand(1), TI, L, Domain, + InvalidDomainMap, ConditionSets); + if (!Valid) { + while (!ConditionSets.empty()) + isl_set_free(ConditionSets.pop_back_val()); + return false; + } + + isl_set_free(ConditionSets.pop_back_val()); + isl_set *ConsCondPart0 = ConditionSets.pop_back_val(); + isl_set_free(ConditionSets.pop_back_val()); + isl_set *ConsCondPart1 = ConditionSets.pop_back_val(); + + if (Opcode == Instruction::And) + ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1); + else + ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1); + } else { + auto *ICond = dyn_cast(Condition); + assert(ICond && + "Condition of exiting branch was neither constant nor ICmp!"); + + Region &R = scop->getRegion(); + + isl_pw_aff *LHS, *RHS; + // For unsigned comparisons we assumed the signed bit of neither operand + // to be set. The comparison is equal to a signed comparison under this + // assumption. + bool NonNeg = ICond->isUnsigned(); + const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L), + *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L); + + LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT); + RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT); + + switch (ICond->getPredicate()) { + case ICmpInst::ICMP_ULT: + ConsequenceCondSet = + buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand, + RightOperand, InvalidDomainMap, true); + break; + case ICmpInst::ICMP_ULE: + ConsequenceCondSet = + buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand, + RightOperand, InvalidDomainMap, false); + break; + case ICmpInst::ICMP_UGT: + ConsequenceCondSet = + buildUnsignedConditionSets(BB, Condition, Domain, RightOperand, + LeftOperand, InvalidDomainMap, true); + break; + case ICmpInst::ICMP_UGE: + ConsequenceCondSet = + buildUnsignedConditionSets(BB, Condition, Domain, RightOperand, + LeftOperand, InvalidDomainMap, false); + break; + default: + LHS = getPwAff(BB, InvalidDomainMap, LeftOperand, NonNeg); + RHS = getPwAff(BB, InvalidDomainMap, RightOperand, NonNeg); + ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), + isl::manage(LHS), isl::manage(RHS)) + .release(); + break; + } + } + + // If no terminator was given we are only looking for parameter constraints + // under which @p Condition is true/false. + if (!TI) + ConsequenceCondSet = isl_set_params(ConsequenceCondSet); + assert(ConsequenceCondSet); + ConsequenceCondSet = isl_set_coalesce( + isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))); + + isl_set *AlternativeCondSet = nullptr; + bool TooComplex = + isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain; + + if (!TooComplex) { + AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain), + isl_set_copy(ConsequenceCondSet)); + TooComplex = + isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain; + } + + if (TooComplex) { + scop->invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(), + TI ? TI->getParent() : nullptr /* BasicBlock */); + isl_set_free(AlternativeCondSet); + isl_set_free(ConsequenceCondSet); + return false; + } + + ConditionSets.push_back(ConsequenceCondSet); + ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet)); + + return true; +} + +bool ScopBuilder::buildConditionSets( + BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain, + DenseMap &InvalidDomainMap, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { + if (SwitchInst *SI = dyn_cast(TI)) + return buildConditionSets(BB, SI, L, Domain, InvalidDomainMap, + ConditionSets); + + assert(isa(TI) && "Terminator was neither branch nor switch."); + + if (TI->getNumSuccessors() == 1) { + ConditionSets.push_back(isl_set_copy(Domain)); + return true; + } + + Value *Condition = getConditionFromTerminator(TI); + assert(Condition && "No condition for Terminator"); + + return buildConditionSets(BB, Condition, TI, L, Domain, InvalidDomainMap, + ConditionSets); +} + +bool ScopBuilder::propagateDomainConstraints( + Region *R, 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 + // information from the predecessors instead of pushing it to the successors. + // Additionally, we assume the domains to be already present in the domain + // map here. However, we iterate again in reverse post order so we know all + // predecessors have been visited before a block or non-affine subregion is + // visited. + + ReversePostOrderTraversal RTraversal(R); + for (auto *RN : RTraversal) { + // Recurse for affine subregions but go on for basic blocks and non-affine + // subregions. + if (RN->isSubRegion()) { + Region *SubRegion = RN->getNodeAs(); + if (!scop->isNonAffineSubRegion(SubRegion)) { + if (!propagateDomainConstraints(SubRegion, InvalidDomainMap)) + return false; + continue; + } + } + + BasicBlock *BB = getRegionNodeBasicBlock(RN); + isl::set &Domain = scop->getOrInitEmptyDomain(BB); + assert(Domain); + + // Under the union of all predecessor conditions we can reach this block. + isl::set PredDom = getPredecessorDomainConstraints(BB, Domain); + Domain = Domain.intersect(PredDom).coalesce(); + Domain = Domain.align_params(scop->getParamSpace()); + + Loop *BBLoop = getRegionNodeLoop(RN, LI); + if (BBLoop && BBLoop->getHeader() == BB && scop->contains(BBLoop)) + if (!addLoopBoundsToHeaderDomain(BBLoop, InvalidDomainMap)) + return false; + } + + return true; +} + +void ScopBuilder::propagateDomainConstraintsToRegionExit( + BasicBlock *BB, Loop *BBLoop, + SmallPtrSetImpl &FinishedExitBlocks, + DenseMap &InvalidDomainMap) { + // Check if the block @p BB is the entry of a region. If so we propagate it's + // domain to the exit block of the region. Otherwise we are done. + auto *RI = scop->getRegion().getRegionInfo(); + auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr; + auto *ExitBB = BBReg ? BBReg->getExit() : nullptr; + if (!BBReg || BBReg->getEntry() != BB || !scop->contains(ExitBB)) + return; + + // Do not propagate the domain if there is a loop backedge inside the region + // that would prevent the exit block from being executed. + auto *L = BBLoop; + while (L && scop->contains(L)) { + SmallVector LatchBBs; + BBLoop->getLoopLatches(LatchBBs); + for (auto *LatchBB : LatchBBs) + if (BB != LatchBB && BBReg->contains(LatchBB)) + return; + L = L->getParentLoop(); + } + + isl::set Domain = scop->getOrInitEmptyDomain(BB); + assert(Domain && "Cannot propagate a nullptr"); + + Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, scop->getBoxedLoops()); + + // Since the dimensions of @p BB and @p ExitBB might be different we have to + // adjust the domain before we can propagate it. + isl::set AdjustedDomain = adjustDomainDimensions(Domain, BBLoop, ExitBBLoop); + isl::set &ExitDomain = scop->getOrInitEmptyDomain(ExitBB); + + // If the exit domain is not yet created we set it otherwise we "add" the + // current domain. + ExitDomain = ExitDomain ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain; + + // Initialize the invalid domain. + InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space()); + + FinishedExitBlocks.insert(ExitBB); +} + +isl::set ScopBuilder::getPredecessorDomainConstraints(BasicBlock *BB, + isl::set Domain) { + // If @p BB is the ScopEntry we are done + if (scop->getRegion().getEntry() == BB) + return isl::set::universe(Domain.get_space()); + + // The region info of this function. + auto &RI = *scop->getRegion().getRegionInfo(); + + Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, scop->getBoxedLoops()); + + // A domain to collect all predecessor domains, thus all conditions under + // which the block is executed. To this end we start with the empty domain. + isl::set PredDom = isl::set::empty(Domain.get_space()); + + // Set of regions of which the entry block domain has been propagated to BB. + // all predecessors inside any of the regions can be skipped. + SmallSet PropagatedRegions; + + for (auto *PredBB : predecessors(BB)) { + // Skip backedges. + if (DT.dominates(BB, PredBB)) + continue; + + // If the predecessor is in a region we used for propagation we can skip it. + auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); }; + if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(), + PredBBInRegion)) { + continue; + } + + // Check if there is a valid region we can use for propagation, thus look + // for a region that contains the predecessor and has @p BB as exit block. + auto *PredR = RI.getRegionFor(PredBB); + while (PredR->getExit() != BB && !PredR->contains(BB)) + PredR->getParent(); + + // If a valid region for propagation was found use the entry of that region + // for propagation, otherwise the PredBB directly. + if (PredR->getExit() == BB) { + PredBB = PredR->getEntry(); + PropagatedRegions.insert(PredR); + } + + isl::set PredBBDom = scop->getDomainConditions(PredBB); + Loop *PredBBLoop = + getFirstNonBoxedLoopFor(PredBB, LI, scop->getBoxedLoops()); + PredBBDom = adjustDomainDimensions(PredBBDom, PredBBLoop, BBLoop); + PredDom = PredDom.unite(PredBBDom); + } + + return PredDom; +} + +bool ScopBuilder::addLoopBoundsToHeaderDomain( + Loop *L, DenseMap &InvalidDomainMap) { + int LoopDepth = scop->getRelativeLoopDepth(L); + assert(LoopDepth >= 0 && "Loop in region should have at least depth one"); + + BasicBlock *HeaderBB = L->getHeader(); + assert(scop->isDomainDefined(HeaderBB)); + isl::set &HeaderBBDom = scop->getOrInitEmptyDomain(HeaderBB); + + isl::map NextIterationMap = + createNextIterationMap(HeaderBBDom.get_space(), LoopDepth); + + isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space()); + + SmallVector LatchBlocks; + L->getLoopLatches(LatchBlocks); + + for (BasicBlock *LatchBB : LatchBlocks) { + // If the latch is only reachable via error statements we skip it. + if (!scop->isDomainDefined(LatchBB)) + continue; + + isl::set LatchBBDom = scop->getDomainConditions(LatchBB); + + isl::set BackedgeCondition = nullptr; + + Instruction *TI = LatchBB->getTerminator(); + BranchInst *BI = dyn_cast(TI); + assert(BI && "Only branch instructions allowed in loop latches"); + + if (BI->isUnconditional()) + BackedgeCondition = LatchBBDom; + else { + SmallVector ConditionSets; + int idx = BI->getSuccessor(0) != HeaderBB; + if (!buildConditionSets(LatchBB, TI, L, LatchBBDom.get(), + InvalidDomainMap, ConditionSets)) + return false; + + // Free the non back edge condition set as we do not need it. + isl_set_free(ConditionSets[1 - idx]); + + BackedgeCondition = isl::manage(ConditionSets[idx]); + } + + int LatchLoopDepth = scop->getRelativeLoopDepth(LI.getLoopFor(LatchBB)); + assert(LatchLoopDepth >= LoopDepth); + BackedgeCondition = BackedgeCondition.project_out( + isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth); + UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition); + } + + isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space()); + for (int i = 0; i < LoopDepth; i++) + ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i); + + isl::set UnionBackedgeConditionComplement = + UnionBackedgeCondition.complement(); + UnionBackedgeConditionComplement = + UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth, + 0); + UnionBackedgeConditionComplement = + UnionBackedgeConditionComplement.apply(ForwardMap); + HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement); + HeaderBBDom = HeaderBBDom.apply(NextIterationMap); + + auto Parts = partitionSetParts(HeaderBBDom, LoopDepth); + HeaderBBDom = Parts.second; + + // Check if there is a tagged AddRec for this loop and if so do not add + // the bounded assumptions to the context as they are already implied by the + // tag. + if (scop->hasNSWAddRecForLoop(L)) + return true; + + isl::set UnboundedCtx = Parts.first.params(); + scop->recordAssumption(INFINITELOOP, UnboundedCtx, + HeaderBB->getTerminator()->getDebugLoc(), + AS_RESTRICTION); + return true; +} + void ScopBuilder::buildInvariantEquivalenceClasses() { DenseMap, LoadInst *> EquivClasses; @@ -173,6 +822,260 @@ } } +bool ScopBuilder::buildDomains( + Region *R, DenseMap &InvalidDomainMap) { + bool IsOnlyNonAffineRegion = scop->isNonAffineSubRegion(R); + auto *EntryBB = R->getEntry(); + auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB); + int LD = scop->getRelativeLoopDepth(L); + auto *S = + isl_set_universe(isl_space_set_alloc(scop->getIslCtx().get(), 0, LD + 1)); + + while (LD-- >= 0) { + L = L->getParentLoop(); + } + + InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S))); + isl::noexceptions::set Domain = isl::manage(S); + scop->setDomain(EntryBB, Domain); + + if (IsOnlyNonAffineRegion) + return !containsErrorBlock(R->getNode(), *R, LI, DT); + + if (!buildDomainsWithBranchConstraints(R, InvalidDomainMap)) + return false; + + if (!propagateDomainConstraints(R, InvalidDomainMap)) + return false; + + // Error blocks and blocks dominated by them have been assumed to never be + // executed. Representing them in the Scop does not add any value. In fact, + // it is likely to cause issues during construction of the ScopStmts. The + // contents of error blocks have not been verified to be expressible and + // will cause problems when building up a ScopStmt for them. + // Furthermore, basic blocks dominated by error blocks may reference + // instructions in the error block which, if the error block is not modeled, + // 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 its + // InvalidDomain. This information is needed during load hoisting. + if (!propagateInvalidStmtDomains(R, InvalidDomainMap)) + return false; + + return true; +} + +bool ScopBuilder::buildDomainsWithBranchConstraints( + Region *R, DenseMap &InvalidDomainMap) { + // To create the domain for each block in R we iterate over all blocks and + // subregions in R and propagate the conditions under which the current region + // element is executed. To this end we iterate in reverse post order over R as + // it ensures that we first visit all predecessors of a region node (either a + // basic block or a subregion) before we visit the region node itself. + // Initially, only the domain for the SCoP region entry block is set and from + // there we propagate the current domain to all successors, however we add the + // condition that the successor is actually executed next. + // As we are only interested in non-loop carried constraints here we can + // simply skip loop back edges. + + SmallPtrSet FinishedExitBlocks; + ReversePostOrderTraversal RTraversal(R); + for (auto *RN : RTraversal) { + // Recurse for affine subregions but go on for basic blocks and non-affine + // subregions. + if (RN->isSubRegion()) { + Region *SubRegion = RN->getNodeAs(); + if (!scop->isNonAffineSubRegion(SubRegion)) { + if (!buildDomainsWithBranchConstraints(SubRegion, InvalidDomainMap)) + return false; + continue; + } + } + + if (containsErrorBlock(RN, scop->getRegion(), LI, DT)) + scop->notifyErrorBlock(); + ; + + BasicBlock *BB = getRegionNodeBasicBlock(RN); + Instruction *TI = BB->getTerminator(); + + if (isa(TI)) + continue; + + if (!scop->isDomainDefined(BB)) + continue; + isl::set Domain = scop->getDomainConditions(BB); + + scop->updateMaxLoopDepth(isl_set_n_dim(Domain.get())); + + auto *BBLoop = getRegionNodeLoop(RN, LI); + // 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, + 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 + // block. However, it is important to note that this is a local property + // with regards to the region @p R. To this end FinishedExitBlocks is a + // local variable. + auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) { + return FinishedExitBlocks.count(SuccBB); + }; + if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit)) + continue; + + // Build the condition sets for the successor nodes of the current region + // node. If it is a non-affine subregion we will always execute the single + // exit node, hence the single entry node domain is the condition set. For + // basic blocks we use the helper function buildConditionSets. + SmallVector ConditionSets; + if (RN->isSubRegion()) + ConditionSets.push_back(Domain.copy()); + else if (!buildConditionSets(BB, TI, BBLoop, Domain.get(), InvalidDomainMap, + ConditionSets)) + return false; + + // Now iterate over the successors and set their initial domain based on + // their condition set. We skip back edges here and have to be careful when + // we leave a loop not to keep constraints over a dimension that doesn't + // exist anymore. + assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size()); + for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) { + isl::set CondSet = isl::manage(ConditionSets[u]); + BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u); + + // Skip blocks outside the region. + if (!scop->contains(SuccBB)) + continue; + + // If we propagate the domain of some block to "SuccBB" we do not have to + // adjust the domain. + if (FinishedExitBlocks.count(SuccBB)) + continue; + + // Skip back edges. + if (DT.dominates(SuccBB, BB)) + continue; + + Loop *SuccBBLoop = + getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops()); + + CondSet = adjustDomainDimensions(CondSet, BBLoop, SuccBBLoop); + + // Set the domain for the successor or merge it with an existing domain in + // case there are multiple paths (without loop back edges) to the + // successor block. + isl::set &SuccDomain = scop->getOrInitEmptyDomain(SuccBB); + + if (SuccDomain) { + SuccDomain = SuccDomain.unite(CondSet).coalesce(); + } else { + // Initialize the invalid domain. + InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space()); + SuccDomain = CondSet; + } + + SuccDomain = SuccDomain.detect_equalities(); + + // Check if the maximal number of domain disjunctions was reached. + // In case this happens we will clean up and bail. + if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain) + continue; + + scop->invalidate(COMPLEXITY, DebugLoc()); + while (++u < ConditionSets.size()) + isl_set_free(ConditionSets[u]); + return false; + } + } + + return true; +} + +bool ScopBuilder::propagateInvalidStmtDomains( + Region *R, DenseMap &InvalidDomainMap) { + ReversePostOrderTraversal RTraversal(R); + for (auto *RN : RTraversal) { + + // Recurse for affine subregions but go on for basic blocks and non-affine + // subregions. + if (RN->isSubRegion()) { + Region *SubRegion = RN->getNodeAs(); + if (!scop->isNonAffineSubRegion(SubRegion)) { + propagateInvalidStmtDomains(SubRegion, InvalidDomainMap); + continue; + } + } + + bool ContainsErrorBlock = containsErrorBlock(RN, scop->getRegion(), LI, DT); + BasicBlock *BB = getRegionNodeBasicBlock(RN); + isl::set &Domain = scop->getOrInitEmptyDomain(BB); + assert(Domain && "Cannot propagate a nullptr"); + + isl::set InvalidDomain = InvalidDomainMap[BB]; + + bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain); + + if (!IsInvalidBlock) { + InvalidDomain = InvalidDomain.intersect(Domain); + } else { + InvalidDomain = Domain; + isl::set DomPar = Domain.params(); + scop->recordAssumption(ERRORBLOCK, DomPar, + BB->getTerminator()->getDebugLoc(), + AS_RESTRICTION); + Domain = isl::set::empty(Domain.get_space()); + } + + if (InvalidDomain.is_empty()) { + InvalidDomainMap[BB] = InvalidDomain; + continue; + } + + auto *BBLoop = getRegionNodeLoop(RN, LI); + auto *TI = BB->getTerminator(); + unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors(); + for (unsigned u = 0; u < NumSuccs; u++) { + auto *SuccBB = getRegionNodeSuccessor(RN, TI, u); + + // Skip successors outside the SCoP. + if (!scop->contains(SuccBB)) + continue; + + // Skip backedges. + if (DT.dominates(SuccBB, BB)) + continue; + + Loop *SuccBBLoop = + getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops()); + + auto AdjustedInvalidDomain = + adjustDomainDimensions(InvalidDomain, BBLoop, SuccBBLoop); + + isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB]; + SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain); + SuccInvalidDomain = SuccInvalidDomain.coalesce(); + + InvalidDomainMap[SuccBB] = SuccInvalidDomain; + + // Check if the maximal number of domain disjunctions was reached. + // In case this happens we will bail. + if (SuccInvalidDomain.n_basic_set() < MaxDisjunctsInDomain) + continue; + + InvalidDomainMap.erase(BB); + scop->invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent()); + return false; + } + + InvalidDomainMap[BB] = InvalidDomain; + } + + return true; +} + void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI, Region *NonAffineSubRegion, bool IsExitBlock) { @@ -660,8 +1563,8 @@ auto *Dom = InScop ? isl_set_copy(scop->getDomainConditions(BB).get()) : isl_set_copy(scop->getContext().get()); assert(Dom && "Cannot propagate a nullptr."); - bool Valid = buildConditionSets(*scop, BB, Val, TI, L, Dom, - InvalidDomainMap, ConditionSets); + bool Valid = buildConditionSets(BB, Val, TI, L, Dom, InvalidDomainMap, + ConditionSets); isl_set_free(Dom); if (!Valid) @@ -2683,12 +3586,6 @@ } #endif -/// Return the block that is the representing block for @p RN. -static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) { - return RN->isSubRegion() ? RN->getNodeAs()->getEntry() - : RN->getNodeAs(); -} - void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) { scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE)); @@ -2754,7 +3651,7 @@ /// A map from basic blocks to their invalid domains. DenseMap InvalidDomainMap; - if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) { + if (!buildDomains(&R, InvalidDomainMap)) { LLVM_DEBUG( dbgs() << "Bailing-out because buildDomains encountered problems\n"); return; Index: polly/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/lib/Analysis/ScopInfo.cpp +++ polly/lib/Analysis/ScopInfo.cpp @@ -1185,347 +1185,6 @@ Domain = Domain.gist_params(Ctx); } -/// Add @p BSet to set @p BoundedParts if @p BSet is bounded. -static isl::set collectBoundedParts(isl::set S) { - isl::set BoundedParts = isl::set::empty(S.get_space()); - for (isl::basic_set BSet : S.get_basic_set_list()) - if (BSet.is_bounded()) - BoundedParts = BoundedParts.unite(isl::set(BSet)); - return BoundedParts; -} - -/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim. -/// -/// @returns A separation of @p S into first an unbounded then a bounded subset, -/// both with regards to the dimension @p Dim. -static std::pair partitionSetParts(isl::set S, - unsigned Dim) { - for (unsigned u = 0, e = S.n_dim(); u < e; u++) - S = S.lower_bound_si(isl::dim::set, u, 0); - - unsigned NumDimsS = S.n_dim(); - isl::set OnlyDimS = S; - - // Remove dimensions that are greater than Dim as they are not interesting. - assert(NumDimsS >= Dim + 1); - OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1); - - // Create artificial parametric upper bounds for dimensions smaller than Dim - // as we are not interested in them. - OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim); - - for (unsigned u = 0; u < Dim; u++) { - isl::constraint C = isl::constraint::alloc_inequality( - isl::local_space(OnlyDimS.get_space())); - C = C.set_coefficient_si(isl::dim::param, u, 1); - C = C.set_coefficient_si(isl::dim::set, u, -1); - OnlyDimS = OnlyDimS.add_constraint(C); - } - - // Collect all bounded parts of OnlyDimS. - isl::set BoundedParts = collectBoundedParts(OnlyDimS); - - // Create the dimensions greater than Dim again. - BoundedParts = - BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1); - - // Remove the artificial upper bound parameters again. - BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim); - - isl::set UnboundedParts = S.subtract(BoundedParts); - return std::make_pair(UnboundedParts, BoundedParts); -} - -/// Create the conditions under which @p L @p Pred @p R is true. -static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L, - isl::pw_aff R) { - switch (Pred) { - case ICmpInst::ICMP_EQ: - return L.eq_set(R); - case ICmpInst::ICMP_NE: - return L.ne_set(R); - case ICmpInst::ICMP_SLT: - return L.lt_set(R); - case ICmpInst::ICMP_SLE: - return L.le_set(R); - case ICmpInst::ICMP_SGT: - return L.gt_set(R); - case ICmpInst::ICMP_SGE: - return L.ge_set(R); - case ICmpInst::ICMP_ULT: - return L.lt_set(R); - case ICmpInst::ICMP_UGT: - return L.gt_set(R); - case ICmpInst::ICMP_ULE: - return L.le_set(R); - case ICmpInst::ICMP_UGE: - return L.ge_set(R); - default: - llvm_unreachable("Non integer predicate not supported"); - } -} - -/// Compute the isl representation for the SCEV @p E in this BB. -/// -/// @param S The Scop in which @p BB resides in. -/// @param BB The BB for which isl representation is to be -/// computed. -/// @param InvalidDomainMap A map of BB to their invalid domains. -/// @param E The SCEV that should be translated. -/// @param NonNegative Flag to indicate the @p E has to be non-negative. -/// -/// Note that this function will also adjust the invalid context accordingly. - -__isl_give isl_pw_aff * -getPwAff(Scop &S, BasicBlock *BB, - DenseMap &InvalidDomainMap, const SCEV *E, - bool NonNegative = false) { - PWACtx PWAC = S.getPwAff(E, BB, NonNegative); - InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second); - return PWAC.first.release(); -} - -/// Build the conditions sets for the switch @p SI in the @p Domain. -/// -/// This will fill @p ConditionSets with the conditions under which control -/// will be moved from @p SI to its successors. Hence, @p ConditionSets will -/// have as many elements as @p SI has successors. -bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L, - __isl_keep isl_set *Domain, - DenseMap &InvalidDomainMap, - SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { - Value *Condition = getConditionFromTerminator(SI); - assert(Condition && "No condition for switch"); - - ScalarEvolution &SE = *S.getSE(); - isl_pw_aff *LHS, *RHS; - LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L)); - - unsigned NumSuccessors = SI->getNumSuccessors(); - ConditionSets.resize(NumSuccessors); - for (auto &Case : SI->cases()) { - unsigned Idx = Case.getSuccessorIndex(); - ConstantInt *CaseValue = Case.getCaseValue(); - - RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue)); - isl_set *CaseConditionSet = - buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS), - isl::manage(RHS)) - .release(); - ConditionSets[Idx] = isl_set_coalesce( - isl_set_intersect(CaseConditionSet, isl_set_copy(Domain))); - } - - assert(ConditionSets[0] == nullptr && "Default condition set was set"); - isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]); - for (unsigned u = 2; u < NumSuccessors; u++) - ConditionSetUnion = - isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u])); - ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion); - - isl_pw_aff_free(LHS); - - return true; -} - -/// Build condition sets for unsigned ICmpInst(s). -/// Special handling is required for unsigned operands to ensure that if -/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst -/// it should wrap around. -/// -/// @param IsStrictUpperBound holds information on the predicate relation -/// between TestVal and UpperBound, i.e, -/// TestVal < UpperBound OR TestVal <= UpperBound -__isl_give isl_set *polly::buildUnsignedConditionSets( - Scop &S, BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, - const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound, - DenseMap &InvalidDomainMap, - bool IsStrictUpperBound) { - // Do not take NonNeg assumption on TestVal - // as it might have MSB (Sign bit) set. - isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false); - // Take NonNeg assumption on UpperBound. - isl_pw_aff *UpperBound = - getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true); - - // 0 <= TestVal - isl_set *First = - isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space( - isl_pw_aff_get_domain_space(TestVal))), - isl_pw_aff_copy(TestVal)); - - isl_set *Second; - if (IsStrictUpperBound) - // TestVal < UpperBound - Second = isl_pw_aff_lt_set(TestVal, UpperBound); - else - // TestVal <= UpperBound - Second = isl_pw_aff_le_set(TestVal, UpperBound); - - isl_set *ConsequenceCondSet = isl_set_intersect(First, Second); - return ConsequenceCondSet; -} - -bool polly::buildConditionSets( - Scop &S, BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L, - __isl_keep isl_set *Domain, - DenseMap &InvalidDomainMap, - SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { - ScalarEvolution &SE = *S.getSE(); - isl_set *ConsequenceCondSet = nullptr; - - if (auto Load = dyn_cast(Condition)) { - const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L); - const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType()); - bool NonNeg = false; - isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg); - isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, RHSSCEV, NonNeg); - ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS), - isl::manage(RHS)) - .release(); - } else if (auto *PHI = dyn_cast(Condition)) { - auto *Unique = dyn_cast( - getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT())); - - if (Unique->isZero()) - ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain)); - else - ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain)); - } else if (auto *CCond = dyn_cast(Condition)) { - if (CCond->isZero()) - ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain)); - else - ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain)); - } else if (BinaryOperator *BinOp = dyn_cast(Condition)) { - auto Opcode = BinOp->getOpcode(); - assert(Opcode == Instruction::And || Opcode == Instruction::Or); - - bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain, - InvalidDomainMap, ConditionSets) && - buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain, - InvalidDomainMap, ConditionSets); - if (!Valid) { - while (!ConditionSets.empty()) - isl_set_free(ConditionSets.pop_back_val()); - return false; - } - - isl_set_free(ConditionSets.pop_back_val()); - isl_set *ConsCondPart0 = ConditionSets.pop_back_val(); - isl_set_free(ConditionSets.pop_back_val()); - isl_set *ConsCondPart1 = ConditionSets.pop_back_val(); - - if (Opcode == Instruction::And) - ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1); - else - ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1); - } else { - auto *ICond = dyn_cast(Condition); - assert(ICond && - "Condition of exiting branch was neither constant nor ICmp!"); - - LoopInfo &LI = *S.getLI(); - DominatorTree &DT = *S.getDT(); - Region &R = S.getRegion(); - - isl_pw_aff *LHS, *RHS; - // For unsigned comparisons we assumed the signed bit of neither operand - // to be set. The comparison is equal to a signed comparison under this - // assumption. - bool NonNeg = ICond->isUnsigned(); - const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L), - *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L); - - LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT); - RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT); - - switch (ICond->getPredicate()) { - case ICmpInst::ICMP_ULT: - ConsequenceCondSet = - buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand, - RightOperand, InvalidDomainMap, true); - break; - case ICmpInst::ICMP_ULE: - ConsequenceCondSet = - buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand, - RightOperand, InvalidDomainMap, false); - break; - case ICmpInst::ICMP_UGT: - ConsequenceCondSet = - buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand, - LeftOperand, InvalidDomainMap, true); - break; - case ICmpInst::ICMP_UGE: - ConsequenceCondSet = - buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand, - LeftOperand, InvalidDomainMap, false); - break; - default: - LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg); - RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg); - ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), - isl::manage(LHS), isl::manage(RHS)) - .release(); - break; - } - } - - // If no terminator was given we are only looking for parameter constraints - // under which @p Condition is true/false. - if (!TI) - ConsequenceCondSet = isl_set_params(ConsequenceCondSet); - assert(ConsequenceCondSet); - ConsequenceCondSet = isl_set_coalesce( - isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))); - - isl_set *AlternativeCondSet = nullptr; - bool TooComplex = - isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain; - - if (!TooComplex) { - AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain), - isl_set_copy(ConsequenceCondSet)); - TooComplex = - isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain; - } - - if (TooComplex) { - S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(), - TI ? TI->getParent() : nullptr /* BasicBlock */); - isl_set_free(AlternativeCondSet); - isl_set_free(ConsequenceCondSet); - return false; - } - - ConditionSets.push_back(ConsequenceCondSet); - ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet)); - - return true; -} - -bool polly::buildConditionSets( - Scop &S, BasicBlock *BB, Instruction *TI, Loop *L, - __isl_keep isl_set *Domain, - DenseMap &InvalidDomainMap, - SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { - if (SwitchInst *SI = dyn_cast(TI)) - return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap, - ConditionSets); - - assert(isa(TI) && "Terminator was neither branch nor switch."); - - if (TI->getNumSuccessors() == 1) { - ConditionSets.push_back(isl_set_copy(Domain)); - return true; - } - - Value *Condition = getConditionFromTerminator(TI); - assert(Condition && "No condition for Terminator"); - - return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap, - ConditionSets); -} - ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name, Loop *SurroundingLoop, std::vector EntryBlockInstructions) @@ -2008,38 +1667,6 @@ InvalidContext = InvalidContext.align_params(getParamSpace()); } -/// Helper to treat non-affine regions and basic blocks the same. -/// -///{ - -/// Return the block that is the representing block for @p RN. -static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) { - return RN->isSubRegion() ? RN->getNodeAs()->getEntry() - : RN->getNodeAs(); -} - -/// Return the @p idx'th block that is executed after @p RN. -static inline BasicBlock * -getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) { - if (RN->isSubRegion()) { - assert(idx == 0); - return RN->getNodeAs()->getExit(); - } - return TI->getSuccessor(idx); -} - -static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI, - const DominatorTree &DT) { - if (!RN->isSubRegion()) - return isErrorBlock(*RN->getNodeAs(), R, LI, DT); - for (BasicBlock *BB : RN->getNodeAs()->blocks()) - if (isErrorBlock(*BB, R, LI, DT)) - return true; - return false; -} - -///} - isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const { return getDomainConditions(Stmt->getEntryBlock()); } @@ -2056,548 +1683,6 @@ return getDomainConditions(BBR->getEntry()); } -bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI, - DenseMap &InvalidDomainMap) { - bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R); - auto *EntryBB = R->getEntry(); - auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB); - int LD = getRelativeLoopDepth(L); - auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx().get(), 0, LD + 1)); - - while (LD-- >= 0) { - L = L->getParentLoop(); - } - - InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S))); - DomainMap[EntryBB] = isl::manage(S); - - if (IsOnlyNonAffineRegion) - return !containsErrorBlock(R->getNode(), *R, LI, DT); - - if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap)) - return false; - - if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap)) - return false; - - // Error blocks and blocks dominated by them have been assumed to never be - // executed. Representing them in the Scop does not add any value. In fact, - // it is likely to cause issues during construction of the ScopStmts. The - // contents of error blocks have not been verified to be expressible and - // will cause problems when building up a ScopStmt for them. - // Furthermore, basic blocks dominated by error blocks may reference - // instructions in the error block which, if the error block is not modeled, - // 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 its - // InvalidDomain. This information is needed during load hoisting. - if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap)) - return false; - - return true; -} - -/// Adjust the dimensions of @p Dom that was constructed for @p OldL -/// to be compatible to domains constructed for loop @p NewL. -/// -/// This function assumes @p NewL and @p OldL are equal or there is a CFG -/// edge from @p OldL to @p NewL. -static isl::set adjustDomainDimensions(Scop &S, isl::set Dom, Loop *OldL, - Loop *NewL) { - // If the loops are the same there is nothing to do. - if (NewL == OldL) - return Dom; - - int OldDepth = S.getRelativeLoopDepth(OldL); - int NewDepth = S.getRelativeLoopDepth(NewL); - // If both loops are non-affine loops there is nothing to do. - if (OldDepth == -1 && NewDepth == -1) - return Dom; - - // Distinguish three cases: - // 1) The depth is the same but the loops are not. - // => One loop was left one was entered. - // 2) The depth increased from OldL to NewL. - // => One loop was entered, none was left. - // 3) The depth decreased from OldL to NewL. - // => Loops were left were difference of the depths defines how many. - if (OldDepth == NewDepth) { - assert(OldL->getParentLoop() == NewL->getParentLoop()); - Dom = Dom.project_out(isl::dim::set, NewDepth, 1); - Dom = Dom.add_dims(isl::dim::set, 1); - } else if (OldDepth < NewDepth) { - assert(OldDepth + 1 == NewDepth); - auto &R = S.getRegion(); - (void)R; - assert(NewL->getParentLoop() == OldL || - ((!OldL || !R.contains(OldL)) && R.contains(NewL))); - Dom = Dom.add_dims(isl::dim::set, 1); - } else { - assert(OldDepth > NewDepth); - int Diff = OldDepth - NewDepth; - int NumDim = Dom.n_dim(); - assert(NumDim >= Diff); - Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff); - } - - return Dom; -} - -bool Scop::propagateInvalidStmtDomains( - Region *R, DominatorTree &DT, LoopInfo &LI, - DenseMap &InvalidDomainMap) { - ReversePostOrderTraversal RTraversal(R); - for (auto *RN : RTraversal) { - - // Recurse for affine subregions but go on for basic blocks and non-affine - // subregions. - if (RN->isSubRegion()) { - Region *SubRegion = RN->getNodeAs(); - if (!isNonAffineSubRegion(SubRegion)) { - propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap); - continue; - } - } - - bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT); - BasicBlock *BB = getRegionNodeBasicBlock(RN); - isl::set &Domain = DomainMap[BB]; - assert(Domain && "Cannot propagate a nullptr"); - - isl::set InvalidDomain = InvalidDomainMap[BB]; - - bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain); - - if (!IsInvalidBlock) { - InvalidDomain = InvalidDomain.intersect(Domain); - } else { - InvalidDomain = Domain; - isl::set DomPar = Domain.params(); - recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(), - AS_RESTRICTION); - Domain = isl::set::empty(Domain.get_space()); - } - - if (InvalidDomain.is_empty()) { - InvalidDomainMap[BB] = InvalidDomain; - continue; - } - - auto *BBLoop = getRegionNodeLoop(RN, LI); - auto *TI = BB->getTerminator(); - unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors(); - for (unsigned u = 0; u < NumSuccs; u++) { - auto *SuccBB = getRegionNodeSuccessor(RN, TI, u); - - // Skip successors outside the SCoP. - if (!contains(SuccBB)) - continue; - - // Skip backedges. - if (DT.dominates(SuccBB, BB)) - continue; - - Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops()); - - auto AdjustedInvalidDomain = - adjustDomainDimensions(*this, InvalidDomain, BBLoop, SuccBBLoop); - - isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB]; - SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain); - SuccInvalidDomain = SuccInvalidDomain.coalesce(); - unsigned NumConjucts = SuccInvalidDomain.n_basic_set(); - - InvalidDomainMap[SuccBB] = SuccInvalidDomain; - - // Check if the maximal number of domain disjunctions was reached. - // In case this happens we will bail. - if (NumConjucts < MaxDisjunctsInDomain) - continue; - - InvalidDomainMap.erase(BB); - invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent()); - return false; - } - - InvalidDomainMap[BB] = InvalidDomain; - } - - return true; -} - -void Scop::propagateDomainConstraintsToRegionExit( - BasicBlock *BB, Loop *BBLoop, - SmallPtrSetImpl &FinishedExitBlocks, LoopInfo &LI, - DenseMap &InvalidDomainMap) { - // Check if the block @p BB is the entry of a region. If so we propagate it's - // domain to the exit block of the region. Otherwise we are done. - auto *RI = R.getRegionInfo(); - auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr; - auto *ExitBB = BBReg ? BBReg->getExit() : nullptr; - if (!BBReg || BBReg->getEntry() != BB || !contains(ExitBB)) - return; - - // Do not propagate the domain if there is a loop backedge inside the region - // that would prevent the exit block from being executed. - auto *L = BBLoop; - while (L && contains(L)) { - SmallVector LatchBBs; - BBLoop->getLoopLatches(LatchBBs); - for (auto *LatchBB : LatchBBs) - if (BB != LatchBB && BBReg->contains(LatchBB)) - return; - L = L->getParentLoop(); - } - - isl::set Domain = DomainMap[BB]; - assert(Domain && "Cannot propagate a nullptr"); - - Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, getBoxedLoops()); - - // Since the dimensions of @p BB and @p ExitBB might be different we have to - // adjust the domain before we can propagate it. - isl::set AdjustedDomain = - adjustDomainDimensions(*this, Domain, BBLoop, ExitBBLoop); - isl::set &ExitDomain = DomainMap[ExitBB]; - - // If the exit domain is not yet created we set it otherwise we "add" the - // current domain. - ExitDomain = ExitDomain ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain; - - // Initialize the invalid domain. - InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space()); - - FinishedExitBlocks.insert(ExitBB); -} - -bool Scop::buildDomainsWithBranchConstraints( - Region *R, DominatorTree &DT, LoopInfo &LI, - DenseMap &InvalidDomainMap) { - // To create the domain for each block in R we iterate over all blocks and - // subregions in R and propagate the conditions under which the current region - // element is executed. To this end we iterate in reverse post order over R as - // it ensures that we first visit all predecessors of a region node (either a - // basic block or a subregion) before we visit the region node itself. - // Initially, only the domain for the SCoP region entry block is set and from - // there we propagate the current domain to all successors, however we add the - // condition that the successor is actually executed next. - // As we are only interested in non-loop carried constraints here we can - // simply skip loop back edges. - - SmallPtrSet FinishedExitBlocks; - ReversePostOrderTraversal RTraversal(R); - for (auto *RN : RTraversal) { - // Recurse for affine subregions but go on for basic blocks and non-affine - // subregions. - if (RN->isSubRegion()) { - Region *SubRegion = RN->getNodeAs(); - if (!isNonAffineSubRegion(SubRegion)) { - if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI, - InvalidDomainMap)) - return false; - continue; - } - } - - if (containsErrorBlock(RN, getRegion(), LI, DT)) - HasErrorBlock = true; - - BasicBlock *BB = getRegionNodeBasicBlock(RN); - Instruction *TI = BB->getTerminator(); - - if (isa(TI)) - continue; - - isl::set Domain = DomainMap.lookup(BB); - if (!Domain) - continue; - MaxLoopDepth = std::max(MaxLoopDepth, isl_set_n_dim(Domain.get())); - - auto *BBLoop = getRegionNodeLoop(RN, LI); - // 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); - - // 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 - // block. However, it is important to note that this is a local property - // with regards to the region @p R. To this end FinishedExitBlocks is a - // local variable. - auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) { - return FinishedExitBlocks.count(SuccBB); - }; - if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit)) - continue; - - // Build the condition sets for the successor nodes of the current region - // node. If it is a non-affine subregion we will always execute the single - // exit node, hence the single entry node domain is the condition set. For - // basic blocks we use the helper function buildConditionSets. - SmallVector ConditionSets; - if (RN->isSubRegion()) - ConditionSets.push_back(Domain.copy()); - else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain.get(), - InvalidDomainMap, ConditionSets)) - return false; - - // Now iterate over the successors and set their initial domain based on - // their condition set. We skip back edges here and have to be careful when - // we leave a loop not to keep constraints over a dimension that doesn't - // exist anymore. - assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size()); - for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) { - isl::set CondSet = isl::manage(ConditionSets[u]); - BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u); - - // Skip blocks outside the region. - if (!contains(SuccBB)) - continue; - - // If we propagate the domain of some block to "SuccBB" we do not have to - // adjust the domain. - if (FinishedExitBlocks.count(SuccBB)) - continue; - - // Skip back edges. - if (DT.dominates(SuccBB, BB)) - continue; - - Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops()); - - CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop); - - // Set the domain for the successor or merge it with an existing domain in - // case there are multiple paths (without loop back edges) to the - // successor block. - isl::set &SuccDomain = DomainMap[SuccBB]; - - if (SuccDomain) { - SuccDomain = SuccDomain.unite(CondSet).coalesce(); - } else { - // Initialize the invalid domain. - InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space()); - SuccDomain = CondSet; - } - - SuccDomain = SuccDomain.detect_equalities(); - - // Check if the maximal number of domain disjunctions was reached. - // In case this happens we will clean up and bail. - if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain) - continue; - - invalidate(COMPLEXITY, DebugLoc()); - while (++u < ConditionSets.size()) - isl_set_free(ConditionSets[u]); - return false; - } - } - - return true; -} - -isl::set Scop::getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain, - DominatorTree &DT, - LoopInfo &LI) { - // If @p BB is the ScopEntry we are done - if (R.getEntry() == BB) - return isl::set::universe(Domain.get_space()); - - // The region info of this function. - auto &RI = *R.getRegionInfo(); - - Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, getBoxedLoops()); - - // A domain to collect all predecessor domains, thus all conditions under - // which the block is executed. To this end we start with the empty domain. - isl::set PredDom = isl::set::empty(Domain.get_space()); - - // Set of regions of which the entry block domain has been propagated to BB. - // all predecessors inside any of the regions can be skipped. - SmallSet PropagatedRegions; - - for (auto *PredBB : predecessors(BB)) { - // Skip backedges. - if (DT.dominates(BB, PredBB)) - continue; - - // If the predecessor is in a region we used for propagation we can skip it. - auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); }; - if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(), - PredBBInRegion)) { - continue; - } - - // Check if there is a valid region we can use for propagation, thus look - // for a region that contains the predecessor and has @p BB as exit block. - auto *PredR = RI.getRegionFor(PredBB); - while (PredR->getExit() != BB && !PredR->contains(BB)) - PredR->getParent(); - - // If a valid region for propagation was found use the entry of that region - // for propagation, otherwise the PredBB directly. - if (PredR->getExit() == BB) { - PredBB = PredR->getEntry(); - PropagatedRegions.insert(PredR); - } - - isl::set PredBBDom = getDomainConditions(PredBB); - Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops()); - PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop); - PredDom = PredDom.unite(PredBBDom); - } - - return PredDom; -} - -bool Scop::propagateDomainConstraints( - Region *R, DominatorTree &DT, LoopInfo &LI, - 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 - // information from the predecessors instead of pushing it to the successors. - // Additionally, we assume the domains to be already present in the domain - // map here. However, we iterate again in reverse post order so we know all - // predecessors have been visited before a block or non-affine subregion is - // visited. - - ReversePostOrderTraversal RTraversal(R); - for (auto *RN : RTraversal) { - // Recurse for affine subregions but go on for basic blocks and non-affine - // subregions. - if (RN->isSubRegion()) { - Region *SubRegion = RN->getNodeAs(); - if (!isNonAffineSubRegion(SubRegion)) { - if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap)) - return false; - continue; - } - } - - BasicBlock *BB = getRegionNodeBasicBlock(RN); - isl::set &Domain = DomainMap[BB]; - assert(Domain); - - // Under the union of all predecessor conditions we can reach this block. - isl::set PredDom = getPredecessorDomainConstraints(BB, Domain, DT, LI); - Domain = Domain.intersect(PredDom).coalesce(); - Domain = Domain.align_params(getParamSpace()); - - Loop *BBLoop = getRegionNodeLoop(RN, LI); - if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop)) - if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap)) - return false; - } - - return true; -} - -/// Create a map to map from a given iteration to a subsequent iteration. -/// -/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim -/// is incremented by one and all other dimensions are equal, e.g., -/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3] -/// -/// if @p Dim is 2 and @p SetSpace has 4 dimensions. -static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) { - isl::space MapSpace = SetSpace.map_from_set(); - isl::map NextIterationMap = isl::map::universe(MapSpace); - for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++) - if (u != Dim) - NextIterationMap = - NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u); - isl::constraint C = - isl::constraint::alloc_equality(isl::local_space(MapSpace)); - C = C.set_constant_si(1); - C = C.set_coefficient_si(isl::dim::in, Dim, 1); - C = C.set_coefficient_si(isl::dim::out, Dim, -1); - NextIterationMap = NextIterationMap.add_constraint(C); - return NextIterationMap; -} - -bool Scop::addLoopBoundsToHeaderDomain( - Loop *L, LoopInfo &LI, DenseMap &InvalidDomainMap) { - int LoopDepth = getRelativeLoopDepth(L); - assert(LoopDepth >= 0 && "Loop in region should have at least depth one"); - - BasicBlock *HeaderBB = L->getHeader(); - assert(DomainMap.count(HeaderBB)); - isl::set &HeaderBBDom = DomainMap[HeaderBB]; - - isl::map NextIterationMap = - createNextIterationMap(HeaderBBDom.get_space(), LoopDepth); - - isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space()); - - SmallVector LatchBlocks; - L->getLoopLatches(LatchBlocks); - - for (BasicBlock *LatchBB : LatchBlocks) { - // If the latch is only reachable via error statements we skip it. - isl::set LatchBBDom = DomainMap.lookup(LatchBB); - if (!LatchBBDom) - continue; - - isl::set BackedgeCondition = nullptr; - - Instruction *TI = LatchBB->getTerminator(); - BranchInst *BI = dyn_cast(TI); - assert(BI && "Only branch instructions allowed in loop latches"); - - if (BI->isUnconditional()) - BackedgeCondition = LatchBBDom; - else { - SmallVector ConditionSets; - int idx = BI->getSuccessor(0) != HeaderBB; - if (!buildConditionSets(*this, LatchBB, TI, L, LatchBBDom.get(), - InvalidDomainMap, ConditionSets)) - return false; - - // Free the non back edge condition set as we do not need it. - isl_set_free(ConditionSets[1 - idx]); - - BackedgeCondition = isl::manage(ConditionSets[idx]); - } - - int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB)); - assert(LatchLoopDepth >= LoopDepth); - BackedgeCondition = BackedgeCondition.project_out( - isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth); - UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition); - } - - isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space()); - for (int i = 0; i < LoopDepth; i++) - ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i); - - isl::set UnionBackedgeConditionComplement = - UnionBackedgeCondition.complement(); - UnionBackedgeConditionComplement = - UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth, - 0); - UnionBackedgeConditionComplement = - UnionBackedgeConditionComplement.apply(ForwardMap); - HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement); - HeaderBBDom = HeaderBBDom.apply(NextIterationMap); - - auto Parts = partitionSetParts(HeaderBBDom, LoopDepth); - HeaderBBDom = Parts.second; - - // Check if there is a tagged AddRec for this loop and if so do not add - // the bounded assumptions to the context as they are already implied by the - // tag. - if (Affinator.hasNSWAddRecForLoop(L)) - return true; - - isl::set UnboundedCtx = Parts.first.params(); - recordAssumption(INFINITELOOP, UnboundedCtx, - HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION); - return true; -} - int Scop::NextScopID = 0; std::string Scop::CurrentFunc;