Index: polly/include/polly/ScopBuilder.h =================================================================== --- polly/include/polly/ScopBuilder.h +++ polly/include/polly/ScopBuilder.h @@ -442,6 +442,10 @@ /// Add user provided parameter constraints to context (command line). void addUserContext(); + /// Add user provided parameter constraints to context (source code). + void addUserAssumptions(AssumptionCache &AC, + DenseMap &InvalidDomainMap); + /// Add all recorded assumptions to the assumed context. void addRecordedAssumptions(); Index: polly/include/polly/ScopInfo.h =================================================================== --- polly/include/polly/ScopInfo.h +++ polly/include/polly/ScopInfo.h @@ -1642,6 +1642,44 @@ 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 /// /// A Scop is the polyhedral representation of a control flow region detected @@ -2040,29 +2078,12 @@ /// Build the Context of the Scop. void buildContext(); - /// Add user provided parameter constraints to context (source code). - void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI, - DenseMap &InvalidDomainMap); - /// Add the bounds of the parameters to the context. void addParameterBounds(); /// Simplify the assumed and invalid context. void simplifyContexts(); - /// Get the representing SCEV for @p S if applicable, otherwise @p S. - /// - /// Invariant loads of the same location are put in an equivalence class and - /// only one of them is chosen as a representing element that will be - /// modeled as a parameter. The others have to be normalized, i.e., - /// replaced by the representing element of their equivalence class, in order - /// to get the correct parameter value, e.g., in the SCEVAffinator. - /// - /// @param S The SCEV to normalize. - /// - /// @return The representing SCEV for invariant loads or @p S if none. - const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const; - /// Create a new SCoP statement for @p BB. /// /// A new statement for @p BB will be created and added to the statement @@ -2205,6 +2226,9 @@ /// @return The count of parameters used in this Scop. size_t getNumParams() const { return Parameters.size(); } + /// Return whether given SCEV is used as the parameter in this Scop. + bool isParam(const SCEV *Param) const { return Parameters.count(Param); } + /// Take a list of parameters and add the new ones to the scop. void addParams(const ParameterSetTy &NewParameters); @@ -2769,6 +2793,19 @@ /// statement. long getNextStmtIdx() { return StmtIdx++; } + /// Get the representing SCEV for @p S if applicable, otherwise @p S. + /// + /// Invariant loads of the same location are put in an equivalence class and + /// only one of them is chosen as a representing element that will be + /// modeled as a parameter. The others have to be normalized, i.e., + /// replaced by the representing element of their equivalence class, in order + /// to get the correct parameter value, e.g., in the SCEVAffinator. + /// + /// @param S The SCEV to normalize. + /// + /// @return The representing SCEV for invariant loads or @p S if none. + const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const; + /// Return the MemoryAccess that writes an llvm::Value, represented by a /// ScopArrayInfo. /// Index: polly/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/lib/Analysis/ScopBuilder.cpp +++ polly/lib/Analysis/ScopBuilder.cpp @@ -27,6 +27,7 @@ #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" @@ -621,6 +622,82 @@ scop->clearRecordedAssumptions(); } +void ScopBuilder::addUserAssumptions( + AssumptionCache &AC, DenseMap &InvalidDomainMap) { + for (auto &Assumption : AC.assumptions()) { + auto *CI = dyn_cast_or_null(Assumption); + if (!CI || CI->getNumArgOperands() != 1) + continue; + + bool InScop = scop->contains(CI); + if (!InScop && !scop->isDominatedBy(DT, CI->getParent())) + continue; + + auto *L = LI.getLoopFor(CI->getParent()); + auto *Val = CI->getArgOperand(0); + ParameterSetTy DetectedParams; + auto &R = scop->getRegion(); + if (!isAffineConstraint(Val, &R, L, SE, DetectedParams)) { + ORE.emit( + OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI) + << "Non-affine user assumption ignored."); + continue; + } + + // Collect all newly introduced parameters. + ParameterSetTy NewParams; + for (auto *Param : DetectedParams) { + Param = extractConstantFactor(Param, SE).second; + Param = scop->getRepresentingInvariantLoadSCEV(Param); + if (scop->isParam(Param)) + continue; + NewParams.insert(Param); + } + + SmallVector ConditionSets; + auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr; + BasicBlock *BB = InScop ? CI->getParent() : R.getEntry(); + 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); + isl_set_free(Dom); + + if (!Valid) + continue; + + isl_set *AssumptionCtx = nullptr; + if (InScop) { + AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1])); + isl_set_free(ConditionSets[0]); + } else { + AssumptionCtx = isl_set_complement(ConditionSets[1]); + AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]); + } + + // Project out newly introduced parameters as they are not otherwise useful. + if (!NewParams.empty()) { + for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) { + auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u); + auto *Param = static_cast(isl_id_get_user(Id)); + isl_id_free(Id); + + if (!NewParams.count(Param)) + continue; + + AssumptionCtx = + isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1); + } + } + ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI) + << "Use user assumption: " << stringFromIslObj(AssumptionCtx)); + isl::set newContext = + scop->getContext().intersect(isl::manage(AssumptionCtx)); + scop->setContext(newContext); + } +} + bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) { Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); @@ -2683,7 +2760,7 @@ return; } - scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap); + addUserAssumptions(AC, InvalidDomainMap); // Initialize the invalid domain. for (ScopStmt &Stmt : scop->Stmts) Index: polly/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/lib/Analysis/ScopInfo.cpp +++ polly/lib/Analysis/ScopInfo.cpp @@ -1336,12 +1336,11 @@ /// @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) { +__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); @@ -1367,18 +1366,11 @@ return ConsequenceCondSet; } -/// 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) { +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; @@ -1511,15 +1503,11 @@ return true; } -/// 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) { +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); @@ -1898,79 +1886,6 @@ return DT.dominates(BB, getEntry()); } -void Scop::addUserAssumptions( - AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI, - DenseMap &InvalidDomainMap) { - for (auto &Assumption : AC.assumptions()) { - auto *CI = dyn_cast_or_null(Assumption); - if (!CI || CI->getNumArgOperands() != 1) - continue; - - bool InScop = contains(CI); - if (!InScop && !isDominatedBy(DT, CI->getParent())) - continue; - - auto *L = LI.getLoopFor(CI->getParent()); - auto *Val = CI->getArgOperand(0); - ParameterSetTy DetectedParams; - if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) { - ORE.emit( - OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI) - << "Non-affine user assumption ignored."); - continue; - } - - // Collect all newly introduced parameters. - ParameterSetTy NewParams; - for (auto *Param : DetectedParams) { - Param = extractConstantFactor(Param, *SE).second; - Param = getRepresentingInvariantLoadSCEV(Param); - if (Parameters.count(Param)) - continue; - NewParams.insert(Param); - } - - SmallVector ConditionSets; - auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr; - BasicBlock *BB = InScop ? CI->getParent() : getRegion().getEntry(); - auto *Dom = InScop ? DomainMap[BB].copy() : Context.copy(); - assert(Dom && "Cannot propagate a nullptr."); - bool Valid = buildConditionSets(*this, BB, Val, TI, L, Dom, - InvalidDomainMap, ConditionSets); - isl_set_free(Dom); - - if (!Valid) - continue; - - isl_set *AssumptionCtx = nullptr; - if (InScop) { - AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1])); - isl_set_free(ConditionSets[0]); - } else { - AssumptionCtx = isl_set_complement(ConditionSets[1]); - AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]); - } - - // Project out newly introduced parameters as they are not otherwise useful. - if (!NewParams.empty()) { - for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) { - auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u); - auto *Param = static_cast(isl_id_get_user(Id)); - isl_id_free(Id); - - if (!NewParams.count(Param)) - continue; - - AssumptionCtx = - isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1); - } - } - ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI) - << "Use user assumption: " << stringFromIslObj(AssumptionCtx)); - Context = Context.intersect(isl::manage(AssumptionCtx)); - } -} - void Scop::buildContext() { isl::space Space = isl::space::params_alloc(getIslCtx(), 0); Context = isl::set::universe(Space); @@ -2902,6 +2817,7 @@ } isl::set Scop::getContext() const { return Context; } + isl::space Scop::getParamSpace() const { return getContext().get_space(); } isl::space Scop::getFullParamSpace() const {