Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -66,6 +66,7 @@ INFINITELOOP, INVARIANTLOAD, DELINEARIZATION, + AVOIDSINGLEITERATION, }; /// Enum to distinguish between assumptions and restrictions. @@ -1583,6 +1584,11 @@ /// @param NewDomain The new statement domain. void restrictDomain(isl::set NewDomain); + /// Update the domain of the statement. + /// + /// @param NewDomain The new statement domain. + void setDomain(isl::set NewDomain); + /// Get the loop for a dimension. /// /// @param Dimension The dimension of the induction variable @@ -1736,6 +1742,10 @@ /// A map from basic blocks to their domains. DenseMap DomainMap; + /// A set that contains restrictions added to eliminate singletons + /// from statement domains. + isl::set RestrictDomainParams; + /// Constraints on parameters. isl::set Context = nullptr; @@ -1969,6 +1979,7 @@ Loop *L, LoopInfo &LI, DenseMap &InvalidDomainMap); + void intersectBBDomainParams(); /// Compute the branching constraints for each basic block in @p R. /// /// @param R The region we currently build branching conditions @@ -2836,6 +2847,9 @@ /// @param BB The block for which the conditions should be returned. isl::set getDomainConditions(BasicBlock *BB) const; + /// Accessor function that returns RestrictDomainParams + isl::set getRestrictDomainParams() const { return RestrictDomainParams; } + /// Get a union set containing the iteration domains of all statements. isl::union_set getDomains() const; Index: lib/Analysis/ScopBuilder.cpp =================================================================== --- lib/Analysis/ScopBuilder.cpp +++ lib/Analysis/ScopBuilder.cpp @@ -1968,6 +1968,7 @@ scop->realignParams(); scop->addUserContext(); + scop->intersectBBDomainParams(); // After the context was fully constructed, thus all our knowledge about // the parameters is in there, we add all recorded assumptions to the // assumed/invalid context. Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -109,6 +109,8 @@ STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo"); STATISTIC(NumSingletonWritesInLoops, "Number of singleton writes nested in affine loops after ScopInfo"); +STATISTIC(AssumptionsAvoidSingleIter, + "Number of assumptions to skip singletons in statement domains."); int const polly::MaxDisjunctsInDomain = 20; @@ -189,6 +191,12 @@ "polly-print-instructions", cl::desc("Output instructions per ScopStmt"), cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory)); +static cl::opt + HandleDoWhile("polly-model-do-while", + cl::desc("Prune exeution domain of statements to ignore" + " disjunction sets that only have one instance"), + cl::Hidden, cl::ZeroOrMore, cl::init(false), + cl::cat(PollyCategory)); //===----------------------------------------------------------------------===// // Create a sequence of two schedules. Either argument may be null and is @@ -1204,6 +1212,8 @@ return M; } +void ScopStmt::setDomain(isl::set NewDomain) { Domain = NewDomain; } + void ScopStmt::restrictDomain(isl::set NewDomain) { assert(NewDomain.is_subset(Domain) && "New domain is not a subset of old domain!"); @@ -2169,6 +2179,9 @@ } AssumptionContext = AssumptionContext.gist_params(S.getContext()); + if (HandleDoWhile) + AssumptionContext = + AssumptionContext.intersect(S.getRestrictDomainParams()); return AssumptionContext; } @@ -2880,6 +2893,27 @@ return NextIterationMap; } +static bool hasSingleton(isl::set Set) { + if (Set.is_singleton()) + return true; + int Dims = Set.dim(isl::dim::set); + for (int i = 0; i < Dims; i++) { + // project out all dimensions that are not this dimension. + isl::set DimOnly = Set; + if (i > 0) // Remove left dimensions. + DimOnly = DimOnly.project_out(isl::dim::set, 0, i); + if (Dims - i - 1 > 0) // Remove right dimensions. + DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1); + if (DimOnly.is_singleton()) { + LLVM_DEBUG(dbgs() << "Found Singleton in Dim: " << i << " "; + DimOnly.dump(); + dbgs() << "\n";); + return true; + } + } + return false; +} + bool Scop::addLoopBoundsToHeaderDomain( Loop *L, LoopInfo &LI, DenseMap &InvalidDomainMap) { int LoopDepth = getRelativeLoopDepth(L); @@ -2960,6 +2994,42 @@ return true; } +void Scop::intersectBBDomainParams() { + if (!HandleDoWhile) + return; + for (ScopStmt &Stmt : *this) { + bool FoundSingleton = false; + isl::set UpperBoundParams = isl::set::empty(getParamSpace()); + isl::set Domain = Stmt.getDomain(); + for (isl::basic_set BSet : Domain.get_basic_set_list()) { + isl::set Set(BSet); + // Ignore the set that has only one iteration. + if (hasSingleton(Set)) { + FoundSingleton = true; + continue; + } + UpperBoundParams = UpperBoundParams.unite(BSet.lexmax().params()); + } + if (!UpperBoundParams.is_empty() && FoundSingleton) { + recordAssumption(AVOIDSINGLEITERATION, UpperBoundParams, + Stmt.getEntryBlock()->getTerminator()->getDebugLoc(), + AS_ASSUMPTION, nullptr); + RestrictDomainParams = RestrictDomainParams.intersect(UpperBoundParams); + } + } + + if (!RestrictDomainParams.plain_is_universe()) { + for (ScopStmt &Stmt : *this) { + isl::set Dom = Stmt.getDomain(); + isl::set NewDom = Dom.intersect_params(RestrictDomainParams); + NewDom = NewDom.coalesce(); + NewDom = NewDom.gist_params(RestrictDomainParams); + Stmt.setDomain(NewDom); + } + Schedule = Schedule.gist_domain_params(RestrictDomainParams); + } +} + MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) { Value *PointerBase = MA->getOriginalBaseAddr(); @@ -3221,6 +3291,7 @@ if (IslOnErrorAbort) isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT); buildContext(); + RestrictDomainParams = isl::set::universe(getParamSpace()); } Scop::~Scop() = default; @@ -3674,6 +3745,8 @@ return "Invariant load"; case DELINEARIZATION: return "Delinearization"; + case AVOIDSINGLEITERATION: + return "Avoid single iteration in loops"; } llvm_unreachable("Unknown AssumptionKind!"); } @@ -3744,6 +3817,9 @@ case DELINEARIZATION: AssumptionsDelinearization++; break; + case AVOIDSINGLEITERATION: + AssumptionsAvoidSingleIter++; + break; } auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t"; Index: test/ScopDetect/model-dowhile.ll =================================================================== --- /dev/null +++ test/ScopDetect/model-dowhile.ll @@ -0,0 +1,118 @@ +; REQUIRES: asserts + +; This test checks that model-do-while can eliminate singletons from statements +; with multidimensional domains. For the C test shown below we are able to +; remove checks where the statement has a singletons in only one of the +; dimensions of its domain. It is important to notice that assumptions +; we add to make this happen (Trip count > 0) are added to the assumed +; context and the run time condition of the loop. + +; Original C code: +; void foo (unsigned I, unsigned J, unsigned K) { +; unsigned i = 0; +; unsigned j = 0; +; unsigned k = 0; +; int A[80][80][80]; +; do { +; do { +; do { +; A[i][j][k]++; +; } while (++k < K); +; k =0; +; } while (++j < J); +; k =0; +; j =0; +; } while (++i %t1 +; RUN: opt -S -polly -O3 -debug-only=polly-ast -debug-only=polly-scops %s -polly-model-do-while=true &> %t2 + +; RUN: FileCheck %s < %t1 --check-prefix=NOMODEL +; RUN: FileCheck %s < %t2 --check-prefix=MODEL + +; MODEL: Assumed Context: +; MODEL-NEXT: [p_0, p_1, p_2] -> { : 0 < p_0 <= 80 and 0 < p_1 <= 80 and p_2 > 0 } + ; MODEL: :: isl ast :: foo :: +; MODEL: if (p_0 >= 1 && p_0 <= 80 && p_1 >= 1 && p_1 <= 80 && p_2 >= 1 && 0 == (p_0 <= -1 || p_1 <= -1 || p_2 <= -1)) +; MODEL: // 1st level tiling - Tiles +; MODEL-NEXT: for (int c0 = 0; c0 <= floord(p_2 - 1, 32); c0 += 1) +; MODEL-NEXT: for (int c1 = 0; c1 <= floord(p_1 - 1, 32); c1 += 1) +; MODEL-NEXT: for (int c2 = 0; c2 <= floord(p_0 - 1, 32); c2 += 1) { +; MODEL-NEXT: // 1st level tiling - Points +; MODEL-NEXT: for (int c3 = 0; c3 <= min(31, p_2 - 32 * c0 - 1); c3 += 1) +; MODEL-NEXT: for (int c4 = 0; c4 <= min(31, p_1 - 32 * c1 - 1); c4 += 1) +; MODEL-NEXT: for (int c5 = 0; c5 <= min(31, p_0 - 32 * c2 - 1); c5 += 1) +; MODEL-NEXT: Stmt2(32 * c0 + c3, 32 * c1 + c4, 32 * c2 + c5); +; MODEL-NOT: if (p_0 <= 0) +; MODEL-NOT: if (p_1 <= 0) +; MODEL-NOT: if (p_2 <= 0) + +; NOMODEL: Assumed Context: +; NOMODEL: [p_0, p_1, p_2] -> { : p_0 <= 80 and p_1 <= 80 } +; NOMODEL: :: isl ast :: foo +; NOMODEL: // 1st level tiling - Tiles +; NOMODEL-NEXT: { +; NOMODEL-NEXT: for (int c0 = 0; c0 <= floord(p_2 - 1, 32); c0 += 1) +; NOMODEL-NEXT: for (int c1 = 0; c1 <= floord(p_1 - 1, 32); c1 += 1) { +; NOMODEL-NEXT: for (int c2 = 0; c2 <= floord(p_0 - 1, 32); c2 += 1) { +; NOMODEL-NEXT: // 1st level tiling - Points +; NOMODEL-NEXT: for (int c3 = 0; c3 <= min(31, p_2 - 32 * c0 - 1); c3 += 1) +; NOMODEL-NEXT: for (int c4 = 0; c4 <= min(31, p_1 - 32 * c1 - 1); c4 += 1) +; NOMODEL-NEXT: for (int c5 = 0; c5 <= min(31, p_0 - 32 * c2 - 1); c5 += 1) +; NOMODEL-NEXT: Stmt2(32 * c0 + c3, 32 * c1 + c4, 32 * c2 + c5); +; NOMODEL: if (p_0 <= 0) +; NOMODEL: if (p_1 <= 0) +; NOMODEL: if (p_2 <= 0) + +; Function Attrs: nounwind readnone +define dso_local void @foo(i32* nocapture, i32, i32, i32) local_unnamed_addr { + %5 = alloca [80 x [80 x [80 x i32]]], align 4 + br label %6 + +;