summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopInfo.h45
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp39
-rw-r--r--polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll2
-rw-r--r--polly/test/ScopInfo/long-sequence-of-error-blocks-2.ll3
-rw-r--r--polly/test/ScopInfo/long-sequence-of-error-blocks.ll2
-rw-r--r--polly/test/ScopInfo/loop-multiexit-succ-cond.ll2
-rw-r--r--polly/test/ScopInfo/pointer-comparison-no-nsw.ll2
-rw-r--r--polly/test/ScopInfo/pointer-comparison.ll2
-rw-r--r--polly/test/ScopInfo/remarks.ll6
-rw-r--r--polly/test/ScopInfo/user_provided_assumptions.ll2
-rw-r--r--polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll4
11 files changed, 89 insertions, 20 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 5c102e0766d..521aa5e9167 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1384,6 +1384,34 @@ private:
/// need to be "false". Otherwise they behave the same.
isl_set *InvalidContext;
+ /// @brief Helper struct to remember assumptions.
+ struct Assumption {
+
+ /// @brief The kind of the assumption (e.g., WRAPPING).
+ AssumptionKind Kind;
+
+ /// @brief Flag to distinguish assumptions and restrictions.
+ AssumptionSign Sign;
+
+ /// @brief The valid/invalid context if this is an assumption/restriction.
+ isl_set *Set;
+
+ /// @brief The location that caused this assumption.
+ DebugLoc Loc;
+ };
+
+ /// @brief Collection to hold taken assumptions.
+ ///
+ /// There are two reasons why we want to record assumptions first before we
+ /// add them to the assumed/invalid context:
+ /// 1) If the SCoP is not profitable or otherwise invalid without the
+ /// assumed/invalid context we do not have to compute it.
+ /// 2) Information about the context are gathered rather late in the SCoP
+ /// construction (basically after we know all parameters), thus the user
+ /// might see overly complicated assumptions to be taken while they will
+ /// only be simplified later on.
+ SmallVector<Assumption, 8> RecordedAssumptions;
+
/// @brief The schedule of the SCoP
///
/// The schedule of the SCoP describes the execution order of the statements
@@ -1926,6 +1954,23 @@ public:
void addAssumption(AssumptionKind Kind, __isl_take isl_set *Set, DebugLoc Loc,
AssumptionSign Sign);
+ /// @brief Record an assumption for later addition to the assumed context.
+ ///
+ /// This function will add the assumption to the RecordedAssumptions. This
+ /// collection will be added (@see addAssumption) to the assumed context once
+ /// all paramaters are known and the context is fully build.
+ ///
+ /// @param Kind The assumption kind describing the underlying cause.
+ /// @param Set The relations between parameters that are assumed to hold.
+ /// @param Loc The location in the source that caused this assumption.
+ /// @param Sign Enum to indicate if the assumptions in @p Set are positive
+ /// (needed/assumptions) or negative (invalid/restrictions).
+ void recordAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
+ DebugLoc Loc, AssumptionSign Sign);
+
+ /// @brief Add all recorded assumptions to the assumed context.
+ void addRecordedAssumptions();
+
/// @brief Mark the scop as invalid.
///
/// This method adds an assumption to the scop that is always invalid. As a
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 14e673cb7b4..97c3804cc3f 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -668,7 +668,8 @@ void MemoryAccess::assumeNoOutOfBound() {
const auto &Loc = getAccessInstruction()
? getAccessInstruction()->getDebugLoc()
: DebugLoc();
- Statement->getParent()->addAssumption(INBOUNDS, Outside, Loc, AS_ASSUMPTION);
+ Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
+ AS_ASSUMPTION);
isl_space_free(Space);
}
@@ -1419,8 +1420,8 @@ void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP,
isl_set_union(isl_set_copy(NotExecuted), InBound);
InBoundIfExecuted = isl_set_coalesce(InBoundIfExecuted);
- Parent.addAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc(),
- AS_ASSUMPTION);
+ Parent.recordAssumption(INBOUNDS, InBoundIfExecuted, GEP->getDebugLoc(),
+ AS_ASSUMPTION);
}
isl_local_space_free(LSpace);
@@ -2639,8 +2640,8 @@ void Scop::propagateDomainConstraints(Region *R, ScopDetection &SD,
if (containsErrorBlock(RN, getRegion(), LI, DT)) {
IsOptimized = true;
isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
- addAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
- AS_RESTRICTION);
+ recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
+ AS_RESTRICTION);
}
}
}
@@ -2740,8 +2741,8 @@ void Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
}
isl_set *UnboundedCtx = isl_set_params(Parts.first);
- addAssumption(INFINITELOOP, UnboundedCtx,
- HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
+ recordAssumption(INFINITELOOP, UnboundedCtx,
+ HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
}
void Scop::buildAliasChecks(AliasAnalysis &AA) {
@@ -3026,6 +3027,12 @@ void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
addParameterBounds();
addUserContext();
addWrappingContext();
+
+ // 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.
+ addRecordedAssumptions();
+
simplifyContexts();
buildAliasChecks(AA);
@@ -3043,6 +3050,9 @@ Scop::~Scop() {
for (auto It : DomainMap)
isl_set_free(It.second);
+ for (auto &AS : RecordedAssumptions)
+ isl_set_free(AS.Set);
+
// Free the alias groups
for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
@@ -3478,6 +3488,9 @@ bool Scop::trackAssumption(AssumptionKind Kind, __isl_keep isl_set *Set,
void Scop::addAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
DebugLoc Loc, AssumptionSign Sign) {
+ // Simplify the assumptions/restrictions first.
+ Set = isl_set_gist_params(Set, getContext());
+
if (!trackAssumption(Kind, Set, Loc, Sign)) {
isl_set_free(Set);
return;
@@ -3492,6 +3505,18 @@ void Scop::addAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
}
}
+void Scop::recordAssumption(AssumptionKind Kind, __isl_take isl_set *Set,
+ DebugLoc Loc, AssumptionSign Sign) {
+ RecordedAssumptions.push_back({Kind, Sign, Set, Loc});
+}
+
+void Scop::addRecordedAssumptions() {
+ while (!RecordedAssumptions.empty()) {
+ const Assumption &AS = RecordedAssumptions.pop_back_val();
+ addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign);
+ }
+}
+
void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc) {
addAssumption(Kind, isl_set_empty(getParamSpace()), Loc, AS_ASSUMPTION);
}
diff --git a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
index 0979e9aa3ea..6cd0b40a471 100644
--- a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
+++ b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
@@ -24,7 +24,7 @@
; INNERMOST-NEXT: Assumed Context:
; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : }
; INNERMOST-NEXT: Invalid Context:
-; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : p_0 < 0 }
+; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : 1 = 0 }
; INNERMOST-NEXT: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11>
; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13>
diff --git a/polly/test/ScopInfo/long-sequence-of-error-blocks-2.ll b/polly/test/ScopInfo/long-sequence-of-error-blocks-2.ll
index 5238800773f..6c97929ec0d 100644
--- a/polly/test/ScopInfo/long-sequence-of-error-blocks-2.ll
+++ b/polly/test/ScopInfo/long-sequence-of-error-blocks-2.ll
@@ -12,8 +12,7 @@ target triple = "x86_64-unknown-linux-gnu"
; CHECK: Assumed Context:
; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { : }
; CHECK: Invalid Context:
-; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { : (tmp17 < 0 and tmp21 < 0) or (tmp17 < 0 and tmp21 > 0) or (tmp17 > 0 and tmp21 < 0) or (tmp17 > 0 and tmp21 > 0) or (tmp37 < 0 and tmp41 < 0 and tmp46 > 0) or (tmp37 < 0 and tmp41 > 0 and tmp46 > 0) or (tmp37 > 0 and tmp41 < 0 and tmp46 > 0) or (tmp37 > 0 and tmp41 > 0 and tmp46 > 0) or (tmp27 = 3 and tmp31 <= 143) or (tmp56 = 0 and tmp52 < 0) or (tmp56 = 0 and tmp52 > 0) }
-
+; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31, tmp37, tmp41, tmp46, tmp52, tmp56, tmp62] -> { : (tmp37 < 0 and tmp41 < 0 and tmp46 > 0) or (tmp17 < 0 and tmp21 < 0) or (tmp17 < 0 and tmp21 > 0) or (tmp17 > 0 and tmp21 < 0) or (tmp17 > 0 and tmp21 > 0) or (tmp37 < 0 and tmp41 > 0 and tmp46 > 0) or (tmp37 > 0 and tmp41 < 0 and tmp46 > 0) or (tmp37 > 0 and tmp41 > 0 and tmp46 > 0) or (tmp27 = 3 and tmp31 <= 143) or (tmp56 = 0 and tmp52 < 0) or (tmp56 = 0 and tmp52 > 0) }
@global = external global [300 x i8], align 16
@global1 = external global %struct.hoge*, align 8
diff --git a/polly/test/ScopInfo/long-sequence-of-error-blocks.ll b/polly/test/ScopInfo/long-sequence-of-error-blocks.ll
index d420a625dd9..6b904c5ac71 100644
--- a/polly/test/ScopInfo/long-sequence-of-error-blocks.ll
+++ b/polly/test/ScopInfo/long-sequence-of-error-blocks.ll
@@ -12,7 +12,7 @@ target triple = "x86_64-unknown-linux-gnu"
; CHECK: Assumed Context:
; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31] -> { : }
; CHECK: Invalid Context:
-; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31] -> { : (tmp17 < 0 and tmp21 < 0) or (tmp17 < 0 and tmp21 > 0) or (tmp17 > 0 and tmp21 < 0) or (tmp17 > 0 and tmp21 > 0) or (tmp27 = 3 and tmp31 <= 143) }
+; CHECK-NEXT: [tmp17, tmp21, tmp27, tmp31] -> { : (tmp27 = 3 and tmp31 <= 143) or (tmp17 < 0 and tmp21 < 0) or (tmp17 < 0 and tmp21 > 0) or (tmp17 > 0 and tmp21 < 0) or (tmp17 > 0 and tmp21 > 0) }
;
; CHECK: Statements {
; CHECK-NEXT: Stmt_bb15
diff --git a/polly/test/ScopInfo/loop-multiexit-succ-cond.ll b/polly/test/ScopInfo/loop-multiexit-succ-cond.ll
index d8fbb2d9adf..368226ff244 100644
--- a/polly/test/ScopInfo/loop-multiexit-succ-cond.ll
+++ b/polly/test/ScopInfo/loop-multiexit-succ-cond.ll
@@ -6,7 +6,7 @@
; CHECK: Assumed Context:
; CHECK-NEXT: [count1, dobreak, count2] -> { : }
; CHECK-NEXT: Invalid Context:
-; CHECK-NEXT: [count1, dobreak, count2] -> { : count1 <= 0 or (count1 > 0 and dobreak > 0) or (count1 > 0 and dobreak <= 0 and count2 > 0) }
+; CHECK-NEXT: [count1, dobreak, count2] -> { : (count1 > 0 and dobreak > 0) or count1 <= 0 or (count1 > 0 and dobreak <= 0 and count2 > 0) }
;
; CHECK: Stmt_loop_enter
; CHECK-NEXT: Domain :=
diff --git a/polly/test/ScopInfo/pointer-comparison-no-nsw.ll b/polly/test/ScopInfo/pointer-comparison-no-nsw.ll
index 92519b271b9..d51148567e7 100644
--- a/polly/test/ScopInfo/pointer-comparison-no-nsw.ll
+++ b/polly/test/ScopInfo/pointer-comparison-no-nsw.ll
@@ -8,7 +8,7 @@
; }
;
; CHECK: Invalid Context:
-; CHECK-NEXT: [A, B] -> { : (4*floor((-A + B)/4) < -A + B and 4*floor((A - B)/4) < A - B) or (4*floor((-A + B)/4) = -A + B and B >= 9223372036854775808 + A) or (4*floor((-A + B)/4) = -A + B and B <= -4 + A) }
+; CHECK-NEXT: [A, B] -> { : (4*floor((-A + B)/4) = -A + B and B >= 9223372036854775808 + A) or (4*floor((A - B)/4) < A - B) or (4*floor((-A + B)/4) = -A + B and B <= -4 + A) }
;
; CHECK: Domain :=
; CHECK-NEXT: [A, B] -> { Stmt_while_body[i0] : 4*floor((A - B)/4) = A - B and B >= A and i0 >= 0 and 4i0 < -A + B }
diff --git a/polly/test/ScopInfo/pointer-comparison.ll b/polly/test/ScopInfo/pointer-comparison.ll
index fc65694018d..6069048524e 100644
--- a/polly/test/ScopInfo/pointer-comparison.ll
+++ b/polly/test/ScopInfo/pointer-comparison.ll
@@ -10,7 +10,7 @@
; }
;
; CHECK: Invalid Context:
-; CHECK-NEXT: [A, B] -> { : (4*floor((-A + B)/4) < -A + B and 4*floor((A - B)/4) < A - B) or (4*floor((-A + B)/4) = -A + B and B >= 9223372036854775808 + A) or (4*floor((-A + B)/4) = -A + B and B <= -4 + A) }
+; CHECK-NEXT: [A, B] -> { : (4*floor((-A + B)/4) = -A + B and B >= 9223372036854775808 + A) or (4*floor((A - B)/4) < A - B) or (4*floor((-A + B)/4) = -A + B and B <= -4 + A) }
;
; CHECK: Domain :=
; CHECK-NEXT: [A, B] -> { Stmt_while_body[i0] : 4*floor((A - B)/4) = A - B and B >= A and i0 >= 0 and 4i0 < -A + B }
diff --git a/polly/test/ScopInfo/remarks.ll b/polly/test/ScopInfo/remarks.ll
index c10fe001aca..b45bdf89273 100644
--- a/polly/test/ScopInfo/remarks.ll
+++ b/polly/test/ScopInfo/remarks.ll
@@ -1,10 +1,10 @@
; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops -disable-output < %s 2>&1 | FileCheck %s
;
; CHECK: remark: test/ScopInfo/remarks.c:4:7: SCoP begins here.
-; CHECK: remark: test/ScopInfo/remarks.c:8:5: Finite loop restriction: [N, M] -> { : N > 0 and (M <= -2 or M = -1) }
-; 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:9:7: Inbounds assumption: [N, M] -> { : N <= 0 or (N > 0 and M <= 100) }
; CHECK: remark: <unknown>:0:0: No-overflows restriction: [N, M, Debug] -> { : M <= -2147483649 - N or M >= 2147483648 - N }
+; CHECK: remark: test/ScopInfo/remarks.c:9:15: Inbounds assumption: [N, M, Debug] -> { : N <= 0 or (N > 0 and 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:9:18: Possibly aliasing pointer, use restrict keyword.
; CHECK: remark: test/ScopInfo/remarks.c:9:33: Possibly aliasing pointer, use restrict keyword.
; CHECK: remark: test/ScopInfo/remarks.c:9:15: Possibly aliasing pointer, use restrict keyword.
diff --git a/polly/test/ScopInfo/user_provided_assumptions.ll b/polly/test/ScopInfo/user_provided_assumptions.ll
index 22691ab5e7d..c8db0a5d3b5 100644
--- a/polly/test/ScopInfo/user_provided_assumptions.ll
+++ b/polly/test/ScopInfo/user_provided_assumptions.ll
@@ -9,7 +9,7 @@
; CHECK-NEXT: remark: <unknown>:0:0: SCoP ends here.
; SCOP: Context:
-; SCOP-NEXT: [N, M, Debug] -> { : Debug = 0 and 0 < N <= 2147483647 and 0 < M <= 2147483647 - N and M <= 100 }
+; SCOP-NEXT: [N, M, Debug] -> { : Debug = 0 and N > 0 and 0 < M <= 2147483647 - N and M <= 100 }
; SCOP: Assumed Context:
; SCOP-NEXT: [N, M, Debug] -> { : }
; SCOP: Invalid Context:
diff --git a/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll b/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll
index 2ee4cd67b2b..351ffe4697b 100644
--- a/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll
+++ b/polly/test/ScopInfo/user_provided_non_dominating_assumptions.ll
@@ -1,8 +1,8 @@
; RUN: opt %loadPolly -pass-remarks-analysis="polly-scops" -polly-scops -disable-output < %s 2>&1 | FileCheck %s
;
; CHECK: remark: <unknown>:0:0: SCoP begins here.
-; CHECK-NEXT: remark: <unknown>:0:0: Inbounds assumption: [i, N, p_2] -> { : N <= i or (N > i and p_2 <= 100) }
-; CHECK-NEXT: remark: <unknown>:0:0: Inbounds assumption: [i, N, p_2, M] -> { : N <= i or (N > i and p_2 <= 0) or (N > i and p_2 > 0 and M >= p_2) }
+; CHECK-NEXT: remark: <unknown>:0:0: Inbounds assumption: [i, N, p_2, M] -> { : N <= i or (N > i and p_2 <= 100) }
+; CHECK-NEXT: remark: <unknown>:0:0: Inbounds assumption: [i, N, p_2, M] -> { : N <= i or (N > i and p_2 > 0 and M >= p_2) or (p_2 = 0 and N > i) }
; CHECK-NEXT: remark: <unknown>:0:0: SCoP ends here.
;
; void f(int *restrict A, int *restrict B, int i, int N, int M, int C[100][100]) {
OpenPOWER on IntegriCloud