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); + /// Set 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,14 @@ Loop *L, LoopInfo &LI, DenseMap &InvalidDomainMap); + /// Update statement domains and parameters to ignore the execution + /// of statements that have only one iteration. + void ignoreSingleIterationDomains(); + + /// Ensure assumptions added to prevent execution of + /// statements of one iteration are preset in the AssumedContext. + void enforceAssumptionsForAvoidsingleIter(); + /// Compute the branching constraints for each basic block in @p R. /// /// @param R The region we currently build branching conditions @@ -2836,6 +2854,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,12 +1968,14 @@ scop->realignParams(); scop->addUserContext(); + scop->ignoreSingleIterationDomains(); // After the context was fully constructed, thus all our knowledge about // the parameters is in there, we add all recorded assumptions to the // assumed/invalid context. scop->addRecordedAssumptions(); scop->simplifyContexts(); + scop->enforceAssumptionsForAvoidsingleIter(); if (!scop->buildAliasChecks(AA)) { LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n"); return; 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-avoid-singular-loops", + 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!"); @@ -2880,6 +2890,32 @@ return NextIterationMap; } +/// Check if the execution domain represented in the @p Set +/// is a singleton. +/// This method also check multi dimensional schedules for +/// the existence of Singleton by projecting out all but one +/// dimension each time. +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); + // 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 +2996,45 @@ return true; } +void Scop::ignoreSingleIterationDomains() { + 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); + } +} + +void Scop::enforceAssumptionsForAvoidsingleIter() { + AssumedContext = AssumedContext.intersect(getRestrictDomainParams()); +} + MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) { Value *PointerBase = MA->getOriginalBaseAddr(); @@ -3221,6 +3296,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 +3750,8 @@ return "Invariant load"; case DELINEARIZATION: return "Delinearization"; + case AVOIDSINGLEITERATION: + return "Avoid single iteration in loops"; } llvm_unreachable("Unknown AssumptionKind!"); } @@ -3744,6 +3822,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,113 @@ +; REQUIRES: asserts +; RUN: opt %loadPolly -S -O3 -debug-only=polly-ast -debug-only=polly-scops -polly-ast -polly-avoid-singular-loops=false --disable-output %s |& FileCheck %s --check-prefix=NOMODEL +; RUN: opt %loadPolly -S -O3 -debug-only=polly-ast -debug-only=polly-scops -polly-ast -polly-avoid-singular-loops=true --disable-output %s |& FileCheck %s --check-prefix=MODEL + +; 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 { : arg3 <= 80 and arg2 <= 80 } +; NOMODEL: :: isl ast :: foo :: +; NOMODEL: if (arg3 <= 80 && arg2 <= 80 && 0 == (arg3 <= -1 || arg2 <= -1 || arg1 <= -1)) +; NOMODEL: for (int c0 = 0; c0 < arg1; c0 += 1) +; NOMODEL-NEXT: for (int c1 = 0; c1 < arg2; c1 += 1) { +; NOMODEL-NEXT: for (int c2 = 0; c2 < arg3; c2 += 1) +; NOMODEL-NEXT: Stmt_bb10(c0, c1, c2); +; NOMODEL-NEXT: if (arg3 <= 0) +; NOMODEL-NEXT: Stmt_bb10(c0, c1, 0); +; NOMODEL-NEXT: } +; NOMODEL-NEXT: if (arg2 <= 0) +; NOMODEL-NEXT: for (int c0 = 0; c0 < arg1; c0 += 1) { +; NOMODEL-NEXT: for (int c2 = 0; c2 < arg3; c2 += 1) +; NOMODEL-NEXT: Stmt_bb10(c0, 0, c2); +; NOMODEL-NEXT: if (arg3 <= 0) +; NOMODEL-NEXT: Stmt_bb10(c0, 0, 0); +; NOMODEL-NEXT: } +; NOMODEL-NEXT: if (arg1 <= 0) { +; NOMODEL-NEXT: for (int c1 = 0; c1 < arg2; c1 += 1) { +; NOMODEL-NEXT: for (int c2 = 0; c2 < arg3; c2 += 1) +; NOMODEL-NEXT: Stmt_bb10(0, c1, c2); +; NOMODEL-NEXT: if (arg3 <= 0) +; NOMODEL-NEXT: Stmt_bb10(0, c1, 0); +; NOMODEL-NEXT: } +; NOMODEL-NEXT: if (arg2 <= 0) { +; NOMODEL-NEXT: for (int c2 = 0; c2 < arg3; c2 += 1) +; NOMODEL-NEXT: Stmt_bb10(0, 0, c2); +; NOMODEL-NEXT: if (arg3 <= 0) +; NOMODEL-NEXT: Stmt_bb10(0, 0, 0); +; NOMODEL-NEXT: } +; NOMODEL-NEXT: } +; NOMODEL-NEXT: } + +; MODEL: Assumed Context: +; MODEL-NEXT: [arg3, arg2, arg1] -> { : 0 < arg3 <= 80 and 0 < arg2 <= 80 and arg1 > 0 } + +; MODEL: :: isl ast :: foo +; MODEL: if (arg3 >= 1 && arg3 <= 80 && arg2 >= 1 && arg2 <= 80 && arg1 >= 1 && 0 == (arg3 <= -1 || arg2 <= -1 || arg1 <= -1)) +; MODEL: for (int c0 = 0; c0 < arg1; c0 += 1) +; MODEL-NEXT: for (int c1 = 0; c1 < arg2; c1 += 1) +; MODEL-NEXT: for (int c2 = 0; c2 < arg3; c2 += 1) +; MODEL-NEXT: Stmt_bb10(c0, c1, c2); + +define dso_local void @foo(i32* nocapture %arg, i32 %arg1, i32 %arg2, i32 %arg3) local_unnamed_addr { +bb: + %tmp = alloca [80 x [80 x [80 x i32]]], align 4 + br label %bb4 + +bb4: ; preds = %bb + %tmp5 = bitcast [80 x [80 x [80 x i32]]]* %tmp to i8* + br label %bb6 + +bb6: ; preds = %bb20, %bb4 + %tmp7 = phi i32 [ 0, %bb4 ], [ %tmp21, %bb20 ] + br label %bb8 + +bb8: ; preds = %bb17, %bb6 + %tmp9 = phi i32 [ 0, %bb6 ], [ %tmp18, %bb17 ] + br label %bb10 + +bb10: ; preds = %bb10, %bb8 + %tmp11 = phi i32 [ 0, %bb8 ], [ %tmp15, %bb10 ] + %tmp12 = getelementptr inbounds [80 x [80 x [80 x i32]]], [80 x [80 x [80 x i32]]]* %tmp, i32 0, i32 %tmp7, i32 %tmp9, i32 %tmp11 + %tmp13 = load i32, i32* %tmp12, align 4 + %tmp14 = add nsw i32 %tmp13, 1 + store i32 %tmp14, i32* %tmp12, align 4 + %tmp15 = add nuw i32 %tmp11, 1 + %tmp16 = icmp ult i32 %tmp15, %arg3 + br i1 %tmp16, label %bb10, label %bb17 + +bb17: ; preds = %bb10 + %tmp18 = add nuw i32 %tmp9, 1 + %tmp19 = icmp ult i32 %tmp18, %arg2 + br i1 %tmp19, label %bb8, label %bb20 + +bb20: ; preds = %bb17 + %tmp21 = add nuw i32 %tmp7, 1 + %tmp22 = icmp ult i32 %tmp21, %arg1 + br i1 %tmp22, label %bb6, label %bb23 + +bb23: ; preds = %bb20 + ret void +}