From b94863001a4ffbb332be6771b8f74fb797ea08aa Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Sat, 3 Mar 2018 19:27:54 +0000 Subject: [PATCH] [ScopInfo] Do not use the set dimension ids to carry loop information isl does not guarantee that set dimension ids will be preserved, so using them to carry information is not a good idea. Furthermore, the loop information can be derived without problem from the statement itself. As this even requires less code than propagating loop information on set dimension ids, starting from this commit we just derive the loop information in collectSurroundingLoops directly from the IR. Interestingly this also results in a couple of isl sets to take a simpler representation. llvm-svn: 326664 --- polly/lib/Analysis/ScopBuilder.cpp | 17 +++++++-- polly/lib/Analysis/ScopInfo.cpp | 45 +++--------------------- polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll | 2 +- polly/test/ScopInfo/phi_scalar_simple_1.ll | 4 +-- polly/test/ScopInfo/remarks.ll | 2 +- 5 files changed, 22 insertions(+), 48 deletions(-) diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp index aa11452..3d1e292 100644 --- a/polly/lib/Analysis/ScopBuilder.cpp +++ b/polly/lib/Analysis/ScopBuilder.cpp @@ -1190,10 +1190,21 @@ void ScopBuilder::buildDomain(ScopStmt &Stmt) { void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) { isl::set Domain = Stmt.getDomain(); - for (unsigned u = 0, e = Domain.dim(isl::dim::set); u < e; u++) { - isl::id DimId = Domain.get_dim_id(isl::dim::set, u); - Stmt.NestLoops.push_back(static_cast(DimId.get_user())); + BasicBlock *BB = Stmt.getEntryBlock(); + + Loop *L = LI.getLoopFor(BB); + + while (L && Stmt.isRegionStmt() && Stmt.getRegion()->contains(L)) + L = L->getParentLoop(); + + SmallVector Loops; + + while (L && Stmt.getParent()->getRegion().contains(L)) { + Loops.push_back(L); + L = L->getParentLoop(); } + + Stmt.NestLoops.insert(Stmt.NestLoops.begin(), Loops.rbegin(), Loops.rend()); } /// Return the reduction type for a given binary operator. diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 9c0a037..e68551b 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -1372,16 +1372,6 @@ partitionSetParts(__isl_take isl_set *S, unsigned Dim) { return std::make_pair(UnboundedParts, BoundedParts); } -/// Set the dimension Ids from @p From in @p To. -static __isl_give isl_set *setDimensionIds(__isl_keep isl_set *From, - __isl_take isl_set *To) { - for (unsigned u = 0, e = isl_set_n_dim(From); u < e; u++) { - isl_id *DimId = isl_set_get_dim_id(From, isl_dim_set, u); - To = isl_set_set_dim_id(To, isl_dim_set, u, DimId); - } - return To; -} - /// Create the conditions under which @p L @p Pred @p R is true. static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, __isl_take isl_pw_aff *L, @@ -1412,18 +1402,6 @@ static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, } } -/// Create the conditions under which @p L @p Pred @p R is true. -/// -/// Helper function that will make sure the dimensions of the result have the -/// same isl_id's as the @p Domain. -static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, - __isl_take isl_pw_aff *L, - __isl_take isl_pw_aff *R, - __isl_keep isl_set *Domain) { - isl_set *ConsequenceCondSet = buildConditionSet(Pred, L, R); - return setDimensionIds(Domain, ConsequenceCondSet); -} - /// Compute the isl representation for the SCEV @p E in this BB. /// /// @param S The Scop in which @p BB resides in. @@ -1468,7 +1446,7 @@ bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L, RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue)); isl_set *CaseConditionSet = - buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS, Domain); + buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS); ConditionSets[Idx] = isl_set_coalesce( isl_set_intersect(CaseConditionSet, isl_set_copy(Domain))); } @@ -1478,8 +1456,7 @@ bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L, for (unsigned u = 2; u < NumSuccessors; u++) ConditionSetUnion = isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u])); - ConditionSets[0] = setDimensionIds( - Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion)); + ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion); isl_pw_aff_free(LHS); @@ -1522,7 +1499,6 @@ buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition, Second = isl_pw_aff_le_set(TestVal, UpperBound); isl_set *ConsequenceCondSet = isl_set_intersect(First, Second); - ConsequenceCondSet = setDimensionIds(Domain, ConsequenceCondSet); return ConsequenceCondSet; } @@ -1547,8 +1523,7 @@ bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition, 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, LHS, RHS, Domain); + ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, LHS, RHS); } else if (auto *PHI = dyn_cast(Condition)) { auto *Unique = dyn_cast( getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT())); @@ -1629,8 +1604,7 @@ bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition, default: LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg); RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg); - ConsequenceCondSet = - buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain); + ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), LHS, RHS); break; } } @@ -2518,14 +2492,6 @@ static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI, ///} -static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain, - unsigned Dim, Loop *L) { - Domain = isl_set_lower_bound_si(Domain, isl_dim_set, Dim, -1); - isl_id *DimId = - isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast(L)); - return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId); -} - isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const { return getDomainConditions(Stmt->getEntryBlock()); } @@ -2551,7 +2517,6 @@ bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI, auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx().get(), 0, LD + 1)); while (LD-- >= 0) { - S = addDomainDimId(S, LD + 1, L); L = L->getParentLoop(); } @@ -2614,7 +2579,6 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S, assert(OldL->getParentLoop() == NewL->getParentLoop()); Dom = isl_set_project_out(Dom, isl_dim_set, NewDepth, 1); Dom = isl_set_add_dims(Dom, isl_dim_set, 1); - Dom = addDomainDimId(Dom, NewDepth, NewL); } else if (OldDepth < NewDepth) { assert(OldDepth + 1 == NewDepth); auto &R = S.getRegion(); @@ -2622,7 +2586,6 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S, assert(NewL->getParentLoop() == OldL || ((!OldL || !R.contains(OldL)) && R.contains(NewL))); Dom = isl_set_add_dims(Dom, isl_dim_set, 1); - Dom = addDomainDimId(Dom, NewDepth, NewL); } else { assert(OldDepth > NewDepth); int Diff = OldDepth - NewDepth; diff --git a/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll b/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll index fbe722e..beb31a0 100644 --- a/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll +++ b/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll @@ -11,7 +11,7 @@ ; CHECK: Assumed Context: ; CHECK-NEXT: [o, m, n] -> { : } ; CHECK-NEXT: Invalid Context: -; CHECK-NEXT: [o, m, n] -> { : o < 0 or m < 0 or (o >= 0 and m >= 0 and n <= 0) or (m = 0 and o >= 0 and n > 0) or (o = 0 and m > 0 and n > 0) } +; CHECK-NEXT: [o, m, n] -> { : o < 0 or m < 0 or n <= 0 or (m <= 0 and n > 0) or (o <= 0 and m > 0 and n > 0) } ; ; CHECK: p0: %o diff --git a/polly/test/ScopInfo/phi_scalar_simple_1.ll b/polly/test/ScopInfo/phi_scalar_simple_1.ll index 0b7ec16..b35fcf16 100644 --- a/polly/test/ScopInfo/phi_scalar_simple_1.ll +++ b/polly/test/ScopInfo/phi_scalar_simple_1.ll @@ -17,9 +17,9 @@ ; CHECK: Statements { ; CHECK-NEXT: Stmt_for_cond ; CHECK-NEXT: Domain := -; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] : N >= 2 and 0 <= i0 < N; Stmt_for_cond[0] : N <= 1 }; +; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] : 0 <= i0 < N; Stmt_for_cond[0] : N <= 0 }; ; CHECK-NEXT: Schedule := -; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] -> [i0, 0, 0, 0] : N >= 2 and i0 < N; Stmt_for_cond[0] -> [0, 0, 0, 0] : N <= 1 }; +; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] -> [i0, 0, 0, 0] : i0 < N; Stmt_for_cond[0] -> [0, 0, 0, 0] : N <= 0 }; ; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK-NEXT: [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0__phi[] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] diff --git a/polly/test/ScopInfo/remarks.ll b/polly/test/ScopInfo/remarks.ll index 316f3f1..7e81311 100644 --- a/polly/test/ScopInfo/remarks.ll +++ b/polly/test/ScopInfo/remarks.ll @@ -4,7 +4,7 @@ ; CHECK: remark: test/ScopInfo/remarks.c:4:7: SCoP begins here. ; CHECK: remark: test/ScopInfo/remarks.c:9:15: Inbounds assumption: [N, M, Debug] -> { : M <= 100 } ; CHECK: remark: test/ScopInfo/remarks.c:13:7: No-error restriction: [N, M, Debug] -> { : N > 0 and M >= 0 and (Debug < 0 or Debug > 0) } -; CHECK: remark: test/ScopInfo/remarks.c:8:5: Finite loop restriction: [N, M, Debug] -> { : N > 0 and (M <= -2 or M = -1) } +; CHECK: remark: test/ScopInfo/remarks.c:8:5: Finite loop restriction: [N, M, Debug] -> { : N > 0 and M < 0 } ; CHECK: remark: test/ScopInfo/remarks.c:4:7: No-overflows restriction: [N, M, Debug] -> { : M <= -2147483649 - N or M >= 2147483648 - N } ; CHECK: remark: test/ScopInfo/remarks.c:9:18: Possibly aliasing pointer, use restrict keyword. ; CHECK: remark: test/ScopInfo/remarks.c:9:33: Possibly aliasing pointer, use restrict keyword. -- 2.7.4