diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h --- a/polly/include/polly/ScopBuilder.h +++ b/polly/include/polly/ScopBuilder.h @@ -30,6 +30,7 @@ /// Build the Polly IR (Scop and ScopStmt) on a Region. class ScopBuilder { + /// The AliasAnalysis to build AliasSetTracker. AliasAnalysis &AA; @@ -48,6 +49,9 @@ /// The ScalarEvolution to help building Scop. ScalarEvolution &SE; + /// An optimization diagnostic interface to add optimization remarks. + OptimizationRemarkEmitter &ORE; + /// Set of instructions that might read any memory location. SmallVector, 16> GlobalReads; @@ -117,8 +121,7 @@ // @} // Build the SCoP for Region @p R. - void buildScop(Region &R, AssumptionCache &AC, - OptimizationRemarkEmitter &ORE); + void buildScop(Region &R, AssumptionCache &AC); /// Create equivalence classes for required invariant accesses. /// @@ -175,6 +178,52 @@ /// @param Stmt The parent statement of the instruction void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt); + /// Build the alias checks for this SCoP. + bool buildAliasChecks(); + + /// A vector of memory accesses that belong to an alias group. + using AliasGroupTy = SmallVector; + + /// A vector of alias groups. + using AliasGroupVectorTy = SmallVector; + + /// Build a given alias group and its access data. + /// + /// @param AliasGroup The alias group to build. + /// @param HasWriteAccess A set of arrays through which memory is not only + /// read, but also written. + // + /// @returns True if __no__ error occurred, false otherwise. + bool buildAliasGroup(AliasGroupTy &AliasGroup, + DenseSet HasWriteAccess); + + /// Build all alias groups for this SCoP. + /// + /// @returns True if __no__ error occurred, false otherwise. + bool buildAliasGroups(); + + /// Build alias groups for all memory accesses in the Scop. + /// + /// Using the alias analysis and an alias set tracker we build alias sets + /// for all memory accesses inside the Scop. For each alias set we then map + /// the aliasing pointers back to the memory accesses we know, thus obtain + /// groups of memory accesses which might alias. We also collect the set of + /// arrays through which memory is written. + /// + /// @returns A pair consistent of a vector of alias groups and a set of arrays + /// through which memory is written. + std::tuple> + buildAliasGroupsForAccesses(); + + /// Split alias groups by iteration domains. + /// + /// We split each group based on the domains of the minimal/maximal accesses. + /// That means two minimal/maximal accesses are only in a group if their + /// access domains intersect. Otherwise, they are in different groups. + /// + /// @param AliasGroups The alias groups to split + void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups); + /// Build an instance of MemoryAccess from the Load/Store instruction. /// /// @param Inst The Load/Store instruction that access the memory @@ -344,6 +393,9 @@ /// @see MemoryKind void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI); + /// Wrapper function to calculate minimal/maximal accesses to each array. + bool calculateMinMaxAccess(AliasGroupTy AliasGroup, + Scop::MinMaxVectorTy &MinMaxAccesses); /// Build the domain of @p Stmt. void buildDomain(ScopStmt &Stmt); diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -2258,6 +2258,12 @@ Scop &operator=(const Scop &) = delete; ~Scop(); + /// Increment actual number of aliasing assumptions taken + /// + /// @param Step Number of new aliasing assumptions which should be added to + /// the number of already taken assumptions. + static void incrementNumberOfAliasingAssumptions(unsigned Step); + /// Get the count of copy statements added to this Scop. /// /// @return The count of copy statements added to this Scop. @@ -2589,59 +2595,17 @@ /// Return true if and only if the InvalidContext is trivial (=empty). bool hasTrivialInvalidContext() const { return InvalidContext.is_empty(); } - /// A vector of memory accesses that belong to an alias group. - using AliasGroupTy = SmallVector; - - /// A vector of alias groups. - using AliasGroupVectorTy = SmallVector; - - /// Build the alias checks for this SCoP. - bool buildAliasChecks(AliasAnalysis &AA); - - /// Build all alias groups for this SCoP. - /// - /// @returns True if __no__ error occurred, false otherwise. - bool buildAliasGroups(AliasAnalysis &AA); - - /// Build alias groups for all memory accesses in the Scop. - /// - /// Using the alias analysis and an alias set tracker we build alias sets - /// for all memory accesses inside the Scop. For each alias set we then map - /// the aliasing pointers back to the memory accesses we know, thus obtain - /// groups of memory accesses which might alias. We also collect the set of - /// arrays through which memory is written. - /// - /// @param AA A reference to the alias analysis. - /// - /// @returns A pair consistent of a vector of alias groups and a set of arrays - /// through which memory is written. - std::tuple> - buildAliasGroupsForAccesses(AliasAnalysis &AA); - - /// Split alias groups by iteration domains. - /// - /// We split each group based on the domains of the minimal/maximal accesses. - /// That means two minimal/maximal accesses are only in a group if their - /// access domains intersect. Otherwise, they are in different groups. - /// - /// @param AliasGroups The alias groups to split - void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups); - - /// Build a given alias group and its access data. - /// - /// @param AliasGroup The alias group to build. - /// @param HasWriteAccess A set of arrays through which memory is not only - /// read, but also written. - /// - /// @returns True if __no__ error occurred, false otherwise. - bool buildAliasGroup(Scop::AliasGroupTy &AliasGroup, - DenseSet HasWriteAccess); - /// Return all alias groups for this SCoP. const MinMaxVectorPairVectorTy &getAliasGroups() const { return MinMaxAliasGroups; } + void addAliasGroup(MinMaxVectorTy &MinMaxAccessesReadWrite, + MinMaxVectorTy &MinMaxAccessesReadOnly) { + MinMaxAliasGroups.emplace_back(); + MinMaxAliasGroups.back().first = MinMaxAccessesReadWrite; + MinMaxAliasGroups.back().second = MinMaxAccessesReadOnly; + } /// Get an isl string representing the context. std::string getContextStr() const; diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp --- a/polly/lib/Analysis/ScopBuilder.cpp +++ b/polly/lib/Analysis/ScopBuilder.cpp @@ -76,6 +76,13 @@ cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); +static cl::opt + OptComputeOut("polly-analysis-computeout", + cl::desc("Bound the scop analysis by a maximal amount of " + "computational steps (0 means no bound)"), + cl::Hidden, cl::init(800000), cl::ZeroOrMore, + cl::cat(PollyCategory)); + static cl::opt PollyAllowDereferenceOfAllFunctionParams( "polly-allow-dereference-of-all-function-parameters", cl::desc( @@ -86,6 +93,22 @@ " their loads. "), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); +static cl::opt RunTimeChecksMaxArraysPerGroup( + "polly-rtc-max-arrays-per-group", + cl::desc("The maximal number of arrays to compare in each alias group."), + cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory)); + +static cl::opt RunTimeChecksMaxAccessDisjuncts( + "polly-rtc-max-array-disjuncts", + cl::desc("The maximal number of disjunts allowed in memory accesses to " + "to build RTCs."), + cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory)); + +static cl::opt RunTimeChecksMaxParameters( + "polly-rtc-max-parameters", + cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden, + cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory)); + static cl::opt UnprofitableScalarAccs( "polly-unprofitable-scalar-accs", cl::desc("Count statements with scalar accesses as not optimizable"), @@ -1801,6 +1824,309 @@ } } +/// Add the minimal/maximal access in @p Set to @p User. +/// +/// @return True if more accesses should be added, false if we reached the +/// maximal number of run-time checks to be generated. +static bool buildMinMaxAccess(isl::set Set, + Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) { + isl::pw_multi_aff MinPMA, MaxPMA; + isl::pw_aff LastDimAff; + isl::aff OneAff; + unsigned Pos; + + Set = Set.remove_divs(); + polly::simplify(Set); + + if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts) + Set = Set.simple_hull(); + + // Restrict the number of parameters involved in the access as the lexmin/ + // lexmax computation will take too long if this number is high. + // + // Experiments with a simple test case using an i7 4800MQ: + // + // #Parameters involved | Time (in sec) + // 6 | 0.01 + // 7 | 0.04 + // 8 | 0.12 + // 9 | 0.40 + // 10 | 1.54 + // 11 | 6.78 + // 12 | 30.38 + // + if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) { + unsigned InvolvedParams = 0; + for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++) + if (Set.involves_dims(isl::dim::param, u, 1)) + InvolvedParams++; + + if (InvolvedParams > RunTimeChecksMaxParameters) + return false; + } + + MinPMA = Set.lexmin_pw_multi_aff(); + MaxPMA = Set.lexmax_pw_multi_aff(); + + MinPMA = MinPMA.coalesce(); + MaxPMA = MaxPMA.coalesce(); + + // Adjust the last dimension of the maximal access by one as we want to + // enclose the accessed memory region by MinPMA and MaxPMA. The pointer + // we test during code generation might now point after the end of the + // allocated array but we will never dereference it anyway. + assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) && + "Assumed at least one output dimension"); + + Pos = MaxPMA.dim(isl::dim::out) - 1; + LastDimAff = MaxPMA.get_pw_aff(Pos); + OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space())); + OneAff = OneAff.add_constant_si(1); + LastDimAff = LastDimAff.add(OneAff); + MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff); + + if (!MinPMA || !MaxPMA) + return false; + + MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA)); + + return true; +} + +/// Wrapper function to calculate minimal/maximal accesses to each array. +bool ScopBuilder::calculateMinMaxAccess(AliasGroupTy AliasGroup, + Scop::MinMaxVectorTy &MinMaxAccesses) { + MinMaxAccesses.reserve(AliasGroup.size()); + + isl::union_set Domains = scop->getDomains(); + isl::union_map Accesses = isl::union_map::empty(scop->getParamSpace()); + + for (MemoryAccess *MA : AliasGroup) + Accesses = Accesses.add_map(MA->getAccessRelation()); + + Accesses = Accesses.intersect_domain(Domains); + isl::union_set Locations = Accesses.range(); + + bool LimitReached = false; + for (isl::set Set : Locations.get_set_list()) { + LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, *scop); + if (LimitReached) + break; + } + + return !LimitReached; +} + +static isl::set getAccessDomain(MemoryAccess *MA) { + isl::set Domain = MA->getStatement()->getDomain(); + Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim()); + return Domain.reset_tuple_id(); +} + +bool ScopBuilder::buildAliasChecks() { + if (!PollyUseRuntimeAliasChecks) + return true; + + if (buildAliasGroups()) { + // Aliasing assumptions do not go through addAssumption but we still want to + // collect statistics so we do it here explicitly. + if (scop->getAliasGroups().size()) + Scop::incrementNumberOfAliasingAssumptions(1); + return true; + } + + // If a problem occurs while building the alias groups we need to delete + // this SCoP and pretend it wasn't valid in the first place. To this end + // we make the assumed context infeasible. + scop->invalidate(ALIASING, DebugLoc()); + + LLVM_DEBUG( + dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr() + << " could not be created as the number of parameters involved " + "is too high. The SCoP will be " + "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " + "the maximal number of parameters but be advised that the " + "compile time might increase exponentially.\n\n"); + return false; +} + +std::tuple> +ScopBuilder::buildAliasGroupsForAccesses() { + AliasSetTracker AST(AA); + + DenseMap PtrToAcc; + DenseSet HasWriteAccess; + for (ScopStmt &Stmt : *scop) { + + isl::set StmtDomain = Stmt.getDomain(); + bool StmtDomainEmpty = StmtDomain.is_empty(); + + // Statements with an empty domain will never be executed. + if (StmtDomainEmpty) + continue; + + for (MemoryAccess *MA : Stmt) { + if (MA->isScalarKind()) + continue; + if (!MA->isRead()) + HasWriteAccess.insert(MA->getScopArrayInfo()); + MemAccInst Acc(MA->getAccessInstruction()); + if (MA->isRead() && isa(Acc)) + PtrToAcc[cast(Acc)->getRawSource()] = MA; + else + PtrToAcc[Acc.getPointerOperand()] = MA; + AST.add(Acc); + } + } + + AliasGroupVectorTy AliasGroups; + for (AliasSet &AS : AST) { + if (AS.isMustAlias() || AS.isForwardingAliasSet()) + continue; + AliasGroupTy AG; + for (auto &PR : AS) + AG.push_back(PtrToAcc[PR.getValue()]); + if (AG.size() < 2) + continue; + AliasGroups.push_back(std::move(AG)); + } + + return std::make_tuple(AliasGroups, HasWriteAccess); +} + +bool ScopBuilder::buildAliasGroups() { + // To create sound alias checks we perform the following steps: + // o) We partition each group into read only and non read only accesses. + // o) For each group with more than one base pointer we then compute minimal + // and maximal accesses to each array of a group in read only and non + // read only partitions separately. + AliasGroupVectorTy AliasGroups; + DenseSet HasWriteAccess; + + std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses(); + + splitAliasGroupsByDomain(AliasGroups); + + for (AliasGroupTy &AG : AliasGroups) { + if (!scop->hasFeasibleRuntimeContext()) + return false; + + { + IslMaxOperationsGuard MaxOpGuard(scop->getIslCtx().get(), OptComputeOut); + bool Valid = buildAliasGroup(AG, HasWriteAccess); + if (!Valid) + return false; + } + if (isl_ctx_last_error(scop->getIslCtx().get()) == isl_error_quota) { + scop->invalidate(COMPLEXITY, DebugLoc()); + return false; + } + } + + return true; +} + +bool ScopBuilder::buildAliasGroup( + AliasGroupTy &AliasGroup, DenseSet HasWriteAccess) { + AliasGroupTy ReadOnlyAccesses; + AliasGroupTy ReadWriteAccesses; + SmallPtrSet ReadWriteArrays; + SmallPtrSet ReadOnlyArrays; + + if (AliasGroup.size() < 2) + return true; + + for (MemoryAccess *Access : AliasGroup) { + ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias", + Access->getAccessInstruction()) + << "Possibly aliasing pointer, use restrict keyword."); + const ScopArrayInfo *Array = Access->getScopArrayInfo(); + if (HasWriteAccess.count(Array)) { + ReadWriteArrays.insert(Array); + ReadWriteAccesses.push_back(Access); + } else { + ReadOnlyArrays.insert(Array); + ReadOnlyAccesses.push_back(Access); + } + } + + // If there are no read-only pointers, and less than two read-write pointers, + // no alias check is needed. + if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1) + return true; + + // If there is no read-write pointer, no alias check is needed. + if (ReadWriteArrays.empty()) + return true; + + // For non-affine accesses, no alias check can be generated as we cannot + // compute a sufficiently tight lower and upper bound: bail out. + for (MemoryAccess *MA : AliasGroup) { + if (!MA->isAffine()) { + scop->invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(), + MA->getAccessInstruction()->getParent()); + return false; + } + } + + // Ensure that for all memory accesses for which we generate alias checks, + // their base pointers are available. + for (MemoryAccess *MA : AliasGroup) { + if (MemoryAccess *BasePtrMA = scop->lookupBasePtrAccess(MA)) + scop->addRequiredInvariantLoad( + cast(BasePtrMA->getAccessInstruction())); + } + + // scop->getAliasGroups().emplace_back(); + // Scop::MinMaxVectorPairTy &pair = scop->getAliasGroups().back(); + Scop::MinMaxVectorTy MinMaxAccessesReadWrite; + Scop::MinMaxVectorTy MinMaxAccessesReadOnly; + + bool Valid; + + Valid = calculateMinMaxAccess(ReadWriteAccesses, MinMaxAccessesReadWrite); + + if (!Valid) + return false; + + // Bail out if the number of values we need to compare is too large. + // This is important as the number of comparisons grows quadratically with + // the number of values we need to compare. + if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() > + RunTimeChecksMaxArraysPerGroup) + return false; + + Valid = calculateMinMaxAccess(ReadOnlyAccesses, MinMaxAccessesReadOnly); + + scop->addAliasGroup(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly); + if (!Valid) + return false; + + return true; +} + +void ScopBuilder::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) { + for (unsigned u = 0; u < AliasGroups.size(); u++) { + AliasGroupTy NewAG; + AliasGroupTy &AG = AliasGroups[u]; + AliasGroupTy::iterator AGI = AG.begin(); + isl::set AGDomain = getAccessDomain(*AGI); + while (AGI != AG.end()) { + MemoryAccess *MA = *AGI; + isl::set MADomain = getAccessDomain(MA); + if (AGDomain.is_disjoint(MADomain)) { + NewAG.push_back(MA); + AGI = AG.erase(AGI); + } else { + AGDomain = AGDomain.unite(MADomain); + AGI++; + } + } + if (NewAG.size() > 1) + AliasGroups.push_back(std::move(NewAG)); + } +} + #ifndef NDEBUG static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) { auto PhysUse = VirtualUse::create(S, Op, &LI, false); @@ -1879,8 +2205,7 @@ : RN->getNodeAs(); } -void ScopBuilder::buildScop(Region &R, AssumptionCache &AC, - OptimizationRemarkEmitter &ORE) { +void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) { scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE)); buildStmts(R); @@ -2009,7 +2334,7 @@ addRecordedAssumptions(); scop->simplifyContexts(); - if (!scop->buildAliasChecks(AA)) { + if (!buildAliasChecks()) { LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n"); return; } @@ -2035,7 +2360,7 @@ const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, ScopDetection &SD, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE) - : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) { + : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE), ORE(ORE) { DebugLoc Beg, End; auto P = getBBPairForRegion(R); getDebugLocations(P, Beg, End); @@ -2044,7 +2369,7 @@ ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEntry", Beg, P.first) << Msg); - buildScop(*R, AC, ORE); + buildScop(*R, AC); LLVM_DEBUG(dbgs() << *scop); diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -117,34 +117,11 @@ // number of disjunct when adding non-convex sets to the context. static int const MaxDisjunctsInContext = 4; -static cl::opt - OptComputeOut("polly-analysis-computeout", - cl::desc("Bound the scop analysis by a maximal amount of " - "computational steps (0 means no bound)"), - cl::Hidden, cl::init(800000), cl::ZeroOrMore, - cl::cat(PollyCategory)); - static cl::opt PollyRemarksMinimal( "polly-remarks-minimal", cl::desc("Do not emit remarks about assumptions that are known"), cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory)); -static cl::opt RunTimeChecksMaxAccessDisjuncts( - "polly-rtc-max-array-disjuncts", - cl::desc("The maximal number of disjunts allowed in memory accesses to " - "to build RTCs."), - cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory)); - -static cl::opt RunTimeChecksMaxParameters( - "polly-rtc-max-parameters", - cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden, - cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory)); - -static cl::opt RunTimeChecksMaxArraysPerGroup( - "polly-rtc-max-arrays-per-group", - cl::desc("The maximal number of arrays to compare in each alias group."), - cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory)); - static cl::opt UserContextStr( "polly-context", cl::value_desc("isl parameter set"), cl::desc("Provide additional constraints on the context parameters"), @@ -1963,11 +1940,6 @@ return ParameterIds.lookup(Parameter); } -isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const { - isl::set DomainContext = getDomains().params(); - return C.intersect_params(DomainContext); -} - bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const { return DT.dominates(BB, getEntry()); } @@ -2205,105 +2177,6 @@ InvalidContext = InvalidContext.align_params(getParamSpace()); } -/// Add the minimal/maximal access in @p Set to @p User. -/// -/// @return True if more accesses should be added, false if we reached the -/// maximal number of run-time checks to be generated. -static bool buildMinMaxAccess(isl::set Set, - Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) { - isl::pw_multi_aff MinPMA, MaxPMA; - isl::pw_aff LastDimAff; - isl::aff OneAff; - unsigned Pos; - - Set = Set.remove_divs(); - polly::simplify(Set); - - if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts) - Set = Set.simple_hull(); - - // Restrict the number of parameters involved in the access as the lexmin/ - // lexmax computation will take too long if this number is high. - // - // Experiments with a simple test case using an i7 4800MQ: - // - // #Parameters involved | Time (in sec) - // 6 | 0.01 - // 7 | 0.04 - // 8 | 0.12 - // 9 | 0.40 - // 10 | 1.54 - // 11 | 6.78 - // 12 | 30.38 - // - if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) { - unsigned InvolvedParams = 0; - for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++) - if (Set.involves_dims(isl::dim::param, u, 1)) - InvolvedParams++; - - if (InvolvedParams > RunTimeChecksMaxParameters) - return false; - } - - MinPMA = Set.lexmin_pw_multi_aff(); - MaxPMA = Set.lexmax_pw_multi_aff(); - - MinPMA = MinPMA.coalesce(); - MaxPMA = MaxPMA.coalesce(); - - // Adjust the last dimension of the maximal access by one as we want to - // enclose the accessed memory region by MinPMA and MaxPMA. The pointer - // we test during code generation might now point after the end of the - // allocated array but we will never dereference it anyway. - assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) && - "Assumed at least one output dimension"); - - Pos = MaxPMA.dim(isl::dim::out) - 1; - LastDimAff = MaxPMA.get_pw_aff(Pos); - OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space())); - OneAff = OneAff.add_constant_si(1); - LastDimAff = LastDimAff.add(OneAff); - MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff); - - if (!MinPMA || !MaxPMA) - return false; - - MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA)); - - return true; -} - -static isl::set getAccessDomain(MemoryAccess *MA) { - isl::set Domain = MA->getStatement()->getDomain(); - Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim()); - return Domain.reset_tuple_id(); -} - -/// Wrapper function to calculate minimal/maximal accesses to each array. -static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S, - Scop::MinMaxVectorTy &MinMaxAccesses) { - MinMaxAccesses.reserve(AliasGroup.size()); - - isl::union_set Domains = S.getDomains(); - isl::union_map Accesses = isl::union_map::empty(S.getParamSpace()); - - for (MemoryAccess *MA : AliasGroup) - Accesses = Accesses.add_map(MA->getAccessRelation()); - - Accesses = Accesses.intersect_domain(Domains); - isl::union_set Locations = Accesses.range(); - - bool LimitReached = false; - for (isl::set Set : Locations.get_set_list()) { - LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, S); - if (LimitReached) - break; - } - - return !LimitReached; -} - /// Helper to treat non-affine regions and basic blocks the same. /// ///{ @@ -2960,225 +2833,6 @@ return true; } -MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) { - Value *PointerBase = MA->getOriginalBaseAddr(); - - auto *PointerBaseInst = dyn_cast(PointerBase); - if (!PointerBaseInst) - return nullptr; - - auto *BasePtrStmt = getStmtFor(PointerBaseInst); - if (!BasePtrStmt) - return nullptr; - - return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst); -} - -bool Scop::buildAliasChecks(AliasAnalysis &AA) { - if (!PollyUseRuntimeAliasChecks) - return true; - - if (buildAliasGroups(AA)) { - // Aliasing assumptions do not go through addAssumption but we still want to - // collect statistics so we do it here explicitly. - if (MinMaxAliasGroups.size()) - AssumptionsAliasing++; - return true; - } - - // If a problem occurs while building the alias groups we need to delete - // this SCoP and pretend it wasn't valid in the first place. To this end - // we make the assumed context infeasible. - invalidate(ALIASING, DebugLoc()); - - LLVM_DEBUG( - dbgs() << "\n\nNOTE: Run time checks for " << getNameStr() - << " could not be created as the number of parameters involved " - "is too high. The SCoP will be " - "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust " - "the maximal number of parameters but be advised that the " - "compile time might increase exponentially.\n\n"); - return false; -} - -std::tuple> -Scop::buildAliasGroupsForAccesses(AliasAnalysis &AA) { - AliasSetTracker AST(AA); - - DenseMap PtrToAcc; - DenseSet HasWriteAccess; - for (ScopStmt &Stmt : *this) { - - isl::set StmtDomain = Stmt.getDomain(); - bool StmtDomainEmpty = StmtDomain.is_empty(); - - // Statements with an empty domain will never be executed. - if (StmtDomainEmpty) - continue; - - for (MemoryAccess *MA : Stmt) { - if (MA->isScalarKind()) - continue; - if (!MA->isRead()) - HasWriteAccess.insert(MA->getScopArrayInfo()); - MemAccInst Acc(MA->getAccessInstruction()); - if (MA->isRead() && isa(Acc)) - PtrToAcc[cast(Acc)->getRawSource()] = MA; - else - PtrToAcc[Acc.getPointerOperand()] = MA; - AST.add(Acc); - } - } - - AliasGroupVectorTy AliasGroups; - for (AliasSet &AS : AST) { - if (AS.isMustAlias() || AS.isForwardingAliasSet()) - continue; - AliasGroupTy AG; - for (auto &PR : AS) - AG.push_back(PtrToAcc[PR.getValue()]); - if (AG.size() < 2) - continue; - AliasGroups.push_back(std::move(AG)); - } - - return std::make_tuple(AliasGroups, HasWriteAccess); -} - -void Scop::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) { - for (unsigned u = 0; u < AliasGroups.size(); u++) { - AliasGroupTy NewAG; - AliasGroupTy &AG = AliasGroups[u]; - AliasGroupTy::iterator AGI = AG.begin(); - isl::set AGDomain = getAccessDomain(*AGI); - while (AGI != AG.end()) { - MemoryAccess *MA = *AGI; - isl::set MADomain = getAccessDomain(MA); - if (AGDomain.is_disjoint(MADomain)) { - NewAG.push_back(MA); - AGI = AG.erase(AGI); - } else { - AGDomain = AGDomain.unite(MADomain); - AGI++; - } - } - if (NewAG.size() > 1) - AliasGroups.push_back(std::move(NewAG)); - } -} - -bool Scop::buildAliasGroups(AliasAnalysis &AA) { - // To create sound alias checks we perform the following steps: - // o) We partition each group into read only and non read only accesses. - // o) For each group with more than one base pointer we then compute minimal - // and maximal accesses to each array of a group in read only and non - // read only partitions separately. - AliasGroupVectorTy AliasGroups; - DenseSet HasWriteAccess; - - std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses(AA); - - splitAliasGroupsByDomain(AliasGroups); - - for (AliasGroupTy &AG : AliasGroups) { - if (!hasFeasibleRuntimeContext()) - return false; - - { - IslMaxOperationsGuard MaxOpGuard(getIslCtx().get(), OptComputeOut); - bool Valid = buildAliasGroup(AG, HasWriteAccess); - if (!Valid) - return false; - } - if (isl_ctx_last_error(getIslCtx().get()) == isl_error_quota) { - invalidate(COMPLEXITY, DebugLoc()); - return false; - } - } - - return true; -} - -bool Scop::buildAliasGroup(Scop::AliasGroupTy &AliasGroup, - DenseSet HasWriteAccess) { - AliasGroupTy ReadOnlyAccesses; - AliasGroupTy ReadWriteAccesses; - SmallPtrSet ReadWriteArrays; - SmallPtrSet ReadOnlyArrays; - - if (AliasGroup.size() < 2) - return true; - - for (MemoryAccess *Access : AliasGroup) { - ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias", - Access->getAccessInstruction()) - << "Possibly aliasing pointer, use restrict keyword."); - const ScopArrayInfo *Array = Access->getScopArrayInfo(); - if (HasWriteAccess.count(Array)) { - ReadWriteArrays.insert(Array); - ReadWriteAccesses.push_back(Access); - } else { - ReadOnlyArrays.insert(Array); - ReadOnlyAccesses.push_back(Access); - } - } - - // If there are no read-only pointers, and less than two read-write pointers, - // no alias check is needed. - if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1) - return true; - - // If there is no read-write pointer, no alias check is needed. - if (ReadWriteArrays.empty()) - return true; - - // For non-affine accesses, no alias check can be generated as we cannot - // compute a sufficiently tight lower and upper bound: bail out. - for (MemoryAccess *MA : AliasGroup) { - if (!MA->isAffine()) { - invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(), - MA->getAccessInstruction()->getParent()); - return false; - } - } - - // Ensure that for all memory accesses for which we generate alias checks, - // their base pointers are available. - for (MemoryAccess *MA : AliasGroup) { - if (MemoryAccess *BasePtrMA = lookupBasePtrAccess(MA)) - addRequiredInvariantLoad( - cast(BasePtrMA->getAccessInstruction())); - } - - MinMaxAliasGroups.emplace_back(); - MinMaxVectorPairTy &pair = MinMaxAliasGroups.back(); - MinMaxVectorTy &MinMaxAccessesReadWrite = pair.first; - MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second; - - bool Valid; - - Valid = - calculateMinMaxAccess(ReadWriteAccesses, *this, MinMaxAccessesReadWrite); - - if (!Valid) - return false; - - // Bail out if the number of values we need to compare is too large. - // This is important as the number of comparisons grows quadratically with - // the number of values we need to compare. - if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() > - RunTimeChecksMaxArraysPerGroup) - return false; - - Valid = - calculateMinMaxAccess(ReadOnlyAccesses, *this, MinMaxAccessesReadOnly); - - if (!Valid) - return false; - - return true; -} - /// Get the smallest loop that contains @p S but is not in @p S. static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) { // Start with the smallest loop containing the entry and expand that @@ -3647,11 +3301,30 @@ auto DomainContext = getDomains().params(); IsFeasible = !DomainContext.is_subset(NegativeContext); - IsFeasible &= !Context.is_subset(NegativeContext); + IsFeasible &= !getContext().is_subset(NegativeContext); return IsFeasible; } +isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const { + isl::set DomainContext = getDomains().params(); + return C.intersect_params(DomainContext); +} + +MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) { + Value *PointerBase = MA->getOriginalBaseAddr(); + + auto *PointerBaseInst = dyn_cast(PointerBase); + if (!PointerBaseInst) + return nullptr; + + auto *BasePtrStmt = getStmtFor(PointerBaseInst); + if (!BasePtrStmt) + return nullptr; + + return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst); +} + static std::string toString(AssumptionKind Kind) { switch (Kind) { case ALIASING: @@ -4380,6 +4053,10 @@ return false; } +void Scop::incrementNumberOfAliasingAssumptions(unsigned step) { + AssumptionsAliasing += step; +} + Scop::ScopStatistics Scop::getStatistics() const { ScopStatistics Result; #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)