[clang] [clang-tools-extra] [llvm] [polly] Reduction series : Refactor reduction detection code (PR #72343)
https://github.com/kartcq created
https://github.com/llvm/llvm-project/pull/72343
None
>From 3a8c2b0b7485ea6ee3d45b87132554a2b812aa50 Mon Sep 17 00:00:00 2001
From: kartcq
Date: Mon, 6 Nov 2023 03:42:09 -0800
Subject: [PATCH] [polly][NFC] Refactor reduction detection code for modularity
This patch pulls out the memory checks from the base reduction detection
algorithm. This is the first one in the reduction patch series, to
reduce diff in future patches.
---
polly/lib/Analysis/ScopBuilder.cpp | 78 ++
1 file changed, 48 insertions(+), 30 deletions(-)
diff --git a/polly/lib/Analysis/ScopBuilder.cpp
b/polly/lib/Analysis/ScopBuilder.cpp
index c34413812d9464e..0af0f6915b14585 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -2510,6 +2510,48 @@ static MemoryAccess::ReductionType
getReductionType(const BinaryOperator *BinOp,
}
}
+/// True if @p AllAccs intersects with @p MemAccs execpt @p LoadMA and @p
+/// StoreMA
+bool hasIntersectingAccesses(isl::set AllAccs, MemoryAccess *LoadMA,
+ MemoryAccess *StoreMA, isl::set Domain,
+ SmallVector &MemAccs) {
+ bool HasIntersectingAccs = false;
+ for (MemoryAccess *MA : MemAccs) {
+if (MA == LoadMA || MA == StoreMA)
+ continue;
+
+isl::map AccRel = MA->getAccessRelation().intersect_domain(Domain);
+isl::set Accs = AccRel.range();
+
+if (AllAccs.has_equal_space(Accs)) {
+ isl::set OverlapAccs = Accs.intersect(AllAccs);
+ bool DoesIntersect = !OverlapAccs.is_empty();
+ HasIntersectingAccs |= DoesIntersect;
+}
+ }
+ return HasIntersectingAccs;
+}
+
+/// Test if the accesses of @p LoadMA and @p StoreMA can form a reduction
+bool checkCandidatePairAccesses(MemoryAccess *LoadMA, MemoryAccess *StoreMA,
+isl::set Domain,
+SmallVector &MemAccs) {
+ isl::map LoadAccs = LoadMA->getAccessRelation();
+ isl::map StoreAccs = StoreMA->getAccessRelation();
+
+ // Skip those with obviously unequal base addresses.
+ bool Valid = LoadAccs.has_equal_space(StoreAccs);
+
+ // And check if the remaining for overlap with other memory accesses.
+ if (Valid) {
+isl::map AllAccsRel = LoadAccs.unite(StoreAccs);
+AllAccsRel = AllAccsRel.intersect_domain(Domain);
+isl::set AllAccs = AllAccsRel.range();
+Valid = !hasIntersectingAccesses(AllAccs, LoadMA, StoreMA, Domain,
MemAccs);
+ }
+ return Valid;
+}
+
void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
SmallVector Loads;
SmallVector, 4> Candidates;
@@ -2528,34 +2570,10 @@ void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
// Then check each possible candidate pair.
for (const auto &CandidatePair : Candidates) {
-bool Valid = true;
-isl::map LoadAccs = CandidatePair.first->getAccessRelation();
-isl::map StoreAccs = CandidatePair.second->getAccessRelation();
-
-// Skip those with obviously unequal base addresses.
-if (!LoadAccs.has_equal_space(StoreAccs)) {
- continue;
-}
-
-// And check if the remaining for overlap with other memory accesses.
-isl::map AllAccsRel = LoadAccs.unite(StoreAccs);
-AllAccsRel = AllAccsRel.intersect_domain(Stmt.getDomain());
-isl::set AllAccs = AllAccsRel.range();
-
-for (MemoryAccess *MA : Stmt) {
- if (MA == CandidatePair.first || MA == CandidatePair.second)
-continue;
-
- isl::map AccRel =
- MA->getAccessRelation().intersect_domain(Stmt.getDomain());
- isl::set Accs = AccRel.range();
-
- if (AllAccs.has_equal_space(Accs)) {
-isl::set OverlapAccs = Accs.intersect(AllAccs);
-Valid = Valid && OverlapAccs.is_empty();
- }
-}
-
+MemoryAccess *LoadMA = CandidatePair.first;
+MemoryAccess *StoreMA = CandidatePair.second;
+bool Valid = checkCandidatePairAccesses(LoadMA, StoreMA, Stmt.getDomain(),
+Stmt.MemAccs);
if (!Valid)
continue;
@@ -2566,8 +2584,8 @@ void ScopBuilder::checkForReductions(ScopStmt &Stmt) {
// If no overlapping access was found we mark the load and store as
// reduction like.
-CandidatePair.first->markAsReductionLike(RT);
-CandidatePair.second->markAsReductionLike(RT);
+LoadMA->markAsReductionLike(RT);
+StoreMA->markAsReductionLike(RT);
}
}
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang-tools-extra] [llvm] [polly] Reduction series : Refactor reduction detection code (PR #72343)
https://github.com/kartcq edited https://github.com/llvm/llvm-project/pull/72343 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [polly] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
https://github.com/kartcq created
https://github.com/llvm/llvm-project/pull/75141
[polly][ScheduleOptimizer] Bail out on exceeding Schedule compute's ISL quota.
There is no upper cap set on current Schedule Optimizer to compute schedule. In
some cases a very long compile time taken to compute the schedule resulting in
hang kind of behavior. This patch introduces a flag 'polly-schedule-computeout'
to pass the cap which is initialized to 30. This patch handles the compute
out cases by bailing out and exiting gracefully.
This patch fixes the bug reported under polly :
[https://github.com/llvm/llvm-project/issues/69090](https://github.com/llvm/llvm-project/issues/69090)
>From 98745d850c588eaf9b5d2ac6f71c79873107501f Mon Sep 17 00:00:00 2001
From: kartcq
Date: Mon, 11 Dec 2023 05:22:33 -0800
Subject: [PATCH] [polly][ScheduleOptimizer] Bail out on exceeding Schedule
compute's ISL quota
There is no upper cap set on current Schedule Optimizer to compute schedule. In
some cases a very long compile time taken to compute the schedule resulting in
hang kind of behavior. This patch introduces a flag 'polly-schedule-computeout'
to pass the cap which is initialized to 30. This patch handles the compute
out cases by bailing out and exiting gracefully.
Change-Id: Id506832df4ae8d3f140579ba10cf570e18efac62
---
polly/lib/Transform/ScheduleOptimizer.cpp | 25 +
.../ScheduleOptimizer/schedule_computeout.ll | 97 +++
2 files changed, 122 insertions(+)
create mode 100644 polly/test/ScheduleOptimizer/schedule_computeout.ll
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp
b/polly/lib/Transform/ScheduleOptimizer.cpp
index 35a0a4def0403d..8ee2b66339adbc 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -96,6 +96,13 @@ static cl::opt
cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
cl::init("yes"), cl::cat(PollyCategory));
+static cl::opt
+ScheduleComputeOut("polly-schedule-computeout",
+ cl::desc("Bound the scheduler by maximal amount"
+"of computational steps. "),
+ cl::Hidden, cl::init(30), cl::ZeroOrMore,
+ cl::cat(PollyCategory));
+
static cl::opt
GreedyFusion("polly-loopfusion-greedy",
cl::desc("Aggressively try to fuse everything"), cl::Hidden,
@@ -860,7 +867,25 @@ static void runIslScheduleOptimizer(
SC = SC.set_proximity(Proximity);
SC = SC.set_validity(Validity);
SC = SC.set_coincidence(Validity);
+
+// Save error handling behavior
+long MaxOperations = isl_ctx_get_max_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, ScheduleComputeOut);
Schedule = SC.compute_schedule();
+bool ScheduleQuota = false;
+if (isl_ctx_last_error(Ctx) == isl_error_quota) {
+ isl_ctx_reset_error(Ctx);
+ LLVM_DEBUG(
+ dbgs() << "Schedule optimizer calculation exceeds ISL quota\n");
+ ScheduleQuota = true;
+}
+isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT);
+isl_ctx_reset_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, MaxOperations);
+
+if (ScheduleQuota)
+ return;
+
isl_options_set_on_error(Ctx, OnErrorStatus);
ScopsRescheduled++;
diff --git a/polly/test/ScheduleOptimizer/schedule_computeout.ll
b/polly/test/ScheduleOptimizer/schedule_computeout.ll
new file mode 100644
index 00..3e768e02c8a740
--- /dev/null
+++ b/polly/test/ScheduleOptimizer/schedule_computeout.ll
@@ -0,0 +1,97 @@
+; RUN: opt -S -polly-optree -polly-delicm -polly-opt-isl
-polly-schedule-computeout=10 -debug-only="polly-opt-isl" < %s 2>&1 |
FileCheck %s
+; Bailout if the computations of schedule compute exceeds the max scheduling
quota.
+; Max compute out is initialized to 30, Here it is set to 10 for test
purpose.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+@a = dso_local local_unnamed_addr global ptr null, align 8
+@b = dso_local local_unnamed_addr global ptr null, align 8
+@c = dso_local local_unnamed_addr global ptr null, align 8
+
+define dso_local void @foo(i32 noundef %I, i32 noundef %J, i32 noundef %K1,
i32 noundef %K2, i32 noundef %L1, i32 noundef %L2) local_unnamed_addr {
+entry:
+ %j = alloca i32, align 4
+ store volatile i32 0, ptr %j, align 4
+ %j.0.j.0.j.0.54 = load volatile i32, ptr %j, align 4
+ %cmp55 = icmp slt i32 %j.0.j.0.j.0.54, %J
+ br i1 %cmp55, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph: ; preds = %entry
+ %0 = load ptr, ptr @a, align 8
+ %1 = load ptr, ptr @b, align 8
+ %2 = load ptr, ptr %1, align 8
+ %cmp352 = icmp slt i32 %L1, %L2
+ %cmp750 = icmp slt i32 %K1, %K2
+ %3 = sext i32 %K1 to i64
+ %4 = sext i32 %L1 to i64
+ br label %for.body
+
+for.cond.cleanup:
[polly] [clang] [llvm] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
https://github.com/kartcq edited https://github.com/llvm/llvm-project/pull/75141 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[polly] [clang] [llvm] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
https://github.com/kartcq updated
https://github.com/llvm/llvm-project/pull/75141
>From 98745d850c588eaf9b5d2ac6f71c79873107501f Mon Sep 17 00:00:00 2001
From: kartcq
Date: Mon, 11 Dec 2023 05:22:33 -0800
Subject: [PATCH 1/2] [polly][ScheduleOptimizer] Bail out on exceeding Schedule
compute's ISL quota
There is no upper cap set on current Schedule Optimizer to compute schedule. In
some cases a very long compile time taken to compute the schedule resulting in
hang kind of behavior. This patch introduces a flag 'polly-schedule-computeout'
to pass the cap which is initialized to 30. This patch handles the compute
out cases by bailing out and exiting gracefully.
Change-Id: Id506832df4ae8d3f140579ba10cf570e18efac62
---
polly/lib/Transform/ScheduleOptimizer.cpp | 25 +
.../ScheduleOptimizer/schedule_computeout.ll | 97 +++
2 files changed, 122 insertions(+)
create mode 100644 polly/test/ScheduleOptimizer/schedule_computeout.ll
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp
b/polly/lib/Transform/ScheduleOptimizer.cpp
index 35a0a4def0403d..8ee2b66339adbc 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -96,6 +96,13 @@ static cl::opt
cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
cl::init("yes"), cl::cat(PollyCategory));
+static cl::opt
+ScheduleComputeOut("polly-schedule-computeout",
+ cl::desc("Bound the scheduler by maximal amount"
+"of computational steps. "),
+ cl::Hidden, cl::init(30), cl::ZeroOrMore,
+ cl::cat(PollyCategory));
+
static cl::opt
GreedyFusion("polly-loopfusion-greedy",
cl::desc("Aggressively try to fuse everything"), cl::Hidden,
@@ -860,7 +867,25 @@ static void runIslScheduleOptimizer(
SC = SC.set_proximity(Proximity);
SC = SC.set_validity(Validity);
SC = SC.set_coincidence(Validity);
+
+// Save error handling behavior
+long MaxOperations = isl_ctx_get_max_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, ScheduleComputeOut);
Schedule = SC.compute_schedule();
+bool ScheduleQuota = false;
+if (isl_ctx_last_error(Ctx) == isl_error_quota) {
+ isl_ctx_reset_error(Ctx);
+ LLVM_DEBUG(
+ dbgs() << "Schedule optimizer calculation exceeds ISL quota\n");
+ ScheduleQuota = true;
+}
+isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT);
+isl_ctx_reset_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, MaxOperations);
+
+if (ScheduleQuota)
+ return;
+
isl_options_set_on_error(Ctx, OnErrorStatus);
ScopsRescheduled++;
diff --git a/polly/test/ScheduleOptimizer/schedule_computeout.ll
b/polly/test/ScheduleOptimizer/schedule_computeout.ll
new file mode 100644
index 00..3e768e02c8a740
--- /dev/null
+++ b/polly/test/ScheduleOptimizer/schedule_computeout.ll
@@ -0,0 +1,97 @@
+; RUN: opt -S -polly-optree -polly-delicm -polly-opt-isl
-polly-schedule-computeout=10 -debug-only="polly-opt-isl" < %s 2>&1 |
FileCheck %s
+; Bailout if the computations of schedule compute exceeds the max scheduling
quota.
+; Max compute out is initialized to 30, Here it is set to 10 for test
purpose.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+@a = dso_local local_unnamed_addr global ptr null, align 8
+@b = dso_local local_unnamed_addr global ptr null, align 8
+@c = dso_local local_unnamed_addr global ptr null, align 8
+
+define dso_local void @foo(i32 noundef %I, i32 noundef %J, i32 noundef %K1,
i32 noundef %K2, i32 noundef %L1, i32 noundef %L2) local_unnamed_addr {
+entry:
+ %j = alloca i32, align 4
+ store volatile i32 0, ptr %j, align 4
+ %j.0.j.0.j.0.54 = load volatile i32, ptr %j, align 4
+ %cmp55 = icmp slt i32 %j.0.j.0.j.0.54, %J
+ br i1 %cmp55, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph: ; preds = %entry
+ %0 = load ptr, ptr @a, align 8
+ %1 = load ptr, ptr @b, align 8
+ %2 = load ptr, ptr %1, align 8
+ %cmp352 = icmp slt i32 %L1, %L2
+ %cmp750 = icmp slt i32 %K1, %K2
+ %3 = sext i32 %K1 to i64
+ %4 = sext i32 %L1 to i64
+ br label %for.body
+
+for.cond.cleanup: ; preds =
%for.cond.cleanup4, %entry
+ ret void
+
+for.body: ; preds =
%for.cond.cleanup4, %for.body.lr.ph
+ br i1 %cmp352, label %for.cond6.preheader.preheader, label %for.cond.cleanup4
+
+for.cond6.preheader.preheader:; preds = %for.body
+ %wide.trip.count66 = sext i32 %L2 to i64
+ br label %for.cond6.preheader
+
+for.cond6.preheader: ; preds =
%for.cond.cleanup8, %for.cond6.preheader.preheader
+ %indvars.iv61 = phi i64 [ %4, %for.cond6.preheader.preheader ], [
%indvars.iv.next62, %fo
[polly] [clang] [llvm] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
https://github.com/kartcq updated
https://github.com/llvm/llvm-project/pull/75141
>From 98745d850c588eaf9b5d2ac6f71c79873107501f Mon Sep 17 00:00:00 2001
From: kartcq
Date: Mon, 11 Dec 2023 05:22:33 -0800
Subject: [PATCH 1/3] [polly][ScheduleOptimizer] Bail out on exceeding Schedule
compute's ISL quota
There is no upper cap set on current Schedule Optimizer to compute schedule. In
some cases a very long compile time taken to compute the schedule resulting in
hang kind of behavior. This patch introduces a flag 'polly-schedule-computeout'
to pass the cap which is initialized to 30. This patch handles the compute
out cases by bailing out and exiting gracefully.
Change-Id: Id506832df4ae8d3f140579ba10cf570e18efac62
---
polly/lib/Transform/ScheduleOptimizer.cpp | 25 +
.../ScheduleOptimizer/schedule_computeout.ll | 97 +++
2 files changed, 122 insertions(+)
create mode 100644 polly/test/ScheduleOptimizer/schedule_computeout.ll
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp
b/polly/lib/Transform/ScheduleOptimizer.cpp
index 35a0a4def0403d..8ee2b66339adbc 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -96,6 +96,13 @@ static cl::opt
cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
cl::init("yes"), cl::cat(PollyCategory));
+static cl::opt
+ScheduleComputeOut("polly-schedule-computeout",
+ cl::desc("Bound the scheduler by maximal amount"
+"of computational steps. "),
+ cl::Hidden, cl::init(30), cl::ZeroOrMore,
+ cl::cat(PollyCategory));
+
static cl::opt
GreedyFusion("polly-loopfusion-greedy",
cl::desc("Aggressively try to fuse everything"), cl::Hidden,
@@ -860,7 +867,25 @@ static void runIslScheduleOptimizer(
SC = SC.set_proximity(Proximity);
SC = SC.set_validity(Validity);
SC = SC.set_coincidence(Validity);
+
+// Save error handling behavior
+long MaxOperations = isl_ctx_get_max_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, ScheduleComputeOut);
Schedule = SC.compute_schedule();
+bool ScheduleQuota = false;
+if (isl_ctx_last_error(Ctx) == isl_error_quota) {
+ isl_ctx_reset_error(Ctx);
+ LLVM_DEBUG(
+ dbgs() << "Schedule optimizer calculation exceeds ISL quota\n");
+ ScheduleQuota = true;
+}
+isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT);
+isl_ctx_reset_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, MaxOperations);
+
+if (ScheduleQuota)
+ return;
+
isl_options_set_on_error(Ctx, OnErrorStatus);
ScopsRescheduled++;
diff --git a/polly/test/ScheduleOptimizer/schedule_computeout.ll
b/polly/test/ScheduleOptimizer/schedule_computeout.ll
new file mode 100644
index 00..3e768e02c8a740
--- /dev/null
+++ b/polly/test/ScheduleOptimizer/schedule_computeout.ll
@@ -0,0 +1,97 @@
+; RUN: opt -S -polly-optree -polly-delicm -polly-opt-isl
-polly-schedule-computeout=10 -debug-only="polly-opt-isl" < %s 2>&1 |
FileCheck %s
+; Bailout if the computations of schedule compute exceeds the max scheduling
quota.
+; Max compute out is initialized to 30, Here it is set to 10 for test
purpose.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+@a = dso_local local_unnamed_addr global ptr null, align 8
+@b = dso_local local_unnamed_addr global ptr null, align 8
+@c = dso_local local_unnamed_addr global ptr null, align 8
+
+define dso_local void @foo(i32 noundef %I, i32 noundef %J, i32 noundef %K1,
i32 noundef %K2, i32 noundef %L1, i32 noundef %L2) local_unnamed_addr {
+entry:
+ %j = alloca i32, align 4
+ store volatile i32 0, ptr %j, align 4
+ %j.0.j.0.j.0.54 = load volatile i32, ptr %j, align 4
+ %cmp55 = icmp slt i32 %j.0.j.0.j.0.54, %J
+ br i1 %cmp55, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph: ; preds = %entry
+ %0 = load ptr, ptr @a, align 8
+ %1 = load ptr, ptr @b, align 8
+ %2 = load ptr, ptr %1, align 8
+ %cmp352 = icmp slt i32 %L1, %L2
+ %cmp750 = icmp slt i32 %K1, %K2
+ %3 = sext i32 %K1 to i64
+ %4 = sext i32 %L1 to i64
+ br label %for.body
+
+for.cond.cleanup: ; preds =
%for.cond.cleanup4, %entry
+ ret void
+
+for.body: ; preds =
%for.cond.cleanup4, %for.body.lr.ph
+ br i1 %cmp352, label %for.cond6.preheader.preheader, label %for.cond.cleanup4
+
+for.cond6.preheader.preheader:; preds = %for.body
+ %wide.trip.count66 = sext i32 %L2 to i64
+ br label %for.cond6.preheader
+
+for.cond6.preheader: ; preds =
%for.cond.cleanup8, %for.cond6.preheader.preheader
+ %indvars.iv61 = phi i64 [ %4, %for.cond6.preheader.preheader ], [
%indvars.iv.next62, %fo
[clang] [polly] [llvm] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
https://github.com/kartcq updated
https://github.com/llvm/llvm-project/pull/75141
>From 98745d850c588eaf9b5d2ac6f71c79873107501f Mon Sep 17 00:00:00 2001
From: kartcq
Date: Mon, 11 Dec 2023 05:22:33 -0800
Subject: [PATCH 1/4] [polly][ScheduleOptimizer] Bail out on exceeding Schedule
compute's ISL quota
There is no upper cap set on current Schedule Optimizer to compute schedule. In
some cases a very long compile time taken to compute the schedule resulting in
hang kind of behavior. This patch introduces a flag 'polly-schedule-computeout'
to pass the cap which is initialized to 30. This patch handles the compute
out cases by bailing out and exiting gracefully.
Change-Id: Id506832df4ae8d3f140579ba10cf570e18efac62
---
polly/lib/Transform/ScheduleOptimizer.cpp | 25 +
.../ScheduleOptimizer/schedule_computeout.ll | 97 +++
2 files changed, 122 insertions(+)
create mode 100644 polly/test/ScheduleOptimizer/schedule_computeout.ll
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp
b/polly/lib/Transform/ScheduleOptimizer.cpp
index 35a0a4def0403d..8ee2b66339adbc 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -96,6 +96,13 @@ static cl::opt
cl::desc("Maximize the band depth (yes/no)"), cl::Hidden,
cl::init("yes"), cl::cat(PollyCategory));
+static cl::opt
+ScheduleComputeOut("polly-schedule-computeout",
+ cl::desc("Bound the scheduler by maximal amount"
+"of computational steps. "),
+ cl::Hidden, cl::init(30), cl::ZeroOrMore,
+ cl::cat(PollyCategory));
+
static cl::opt
GreedyFusion("polly-loopfusion-greedy",
cl::desc("Aggressively try to fuse everything"), cl::Hidden,
@@ -860,7 +867,25 @@ static void runIslScheduleOptimizer(
SC = SC.set_proximity(Proximity);
SC = SC.set_validity(Validity);
SC = SC.set_coincidence(Validity);
+
+// Save error handling behavior
+long MaxOperations = isl_ctx_get_max_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, ScheduleComputeOut);
Schedule = SC.compute_schedule();
+bool ScheduleQuota = false;
+if (isl_ctx_last_error(Ctx) == isl_error_quota) {
+ isl_ctx_reset_error(Ctx);
+ LLVM_DEBUG(
+ dbgs() << "Schedule optimizer calculation exceeds ISL quota\n");
+ ScheduleQuota = true;
+}
+isl_options_set_on_error(Ctx, ISL_ON_ERROR_ABORT);
+isl_ctx_reset_operations(Ctx);
+isl_ctx_set_max_operations(Ctx, MaxOperations);
+
+if (ScheduleQuota)
+ return;
+
isl_options_set_on_error(Ctx, OnErrorStatus);
ScopsRescheduled++;
diff --git a/polly/test/ScheduleOptimizer/schedule_computeout.ll
b/polly/test/ScheduleOptimizer/schedule_computeout.ll
new file mode 100644
index 00..3e768e02c8a740
--- /dev/null
+++ b/polly/test/ScheduleOptimizer/schedule_computeout.ll
@@ -0,0 +1,97 @@
+; RUN: opt -S -polly-optree -polly-delicm -polly-opt-isl
-polly-schedule-computeout=10 -debug-only="polly-opt-isl" < %s 2>&1 |
FileCheck %s
+; Bailout if the computations of schedule compute exceeds the max scheduling
quota.
+; Max compute out is initialized to 30, Here it is set to 10 for test
purpose.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+@a = dso_local local_unnamed_addr global ptr null, align 8
+@b = dso_local local_unnamed_addr global ptr null, align 8
+@c = dso_local local_unnamed_addr global ptr null, align 8
+
+define dso_local void @foo(i32 noundef %I, i32 noundef %J, i32 noundef %K1,
i32 noundef %K2, i32 noundef %L1, i32 noundef %L2) local_unnamed_addr {
+entry:
+ %j = alloca i32, align 4
+ store volatile i32 0, ptr %j, align 4
+ %j.0.j.0.j.0.54 = load volatile i32, ptr %j, align 4
+ %cmp55 = icmp slt i32 %j.0.j.0.j.0.54, %J
+ br i1 %cmp55, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph: ; preds = %entry
+ %0 = load ptr, ptr @a, align 8
+ %1 = load ptr, ptr @b, align 8
+ %2 = load ptr, ptr %1, align 8
+ %cmp352 = icmp slt i32 %L1, %L2
+ %cmp750 = icmp slt i32 %K1, %K2
+ %3 = sext i32 %K1 to i64
+ %4 = sext i32 %L1 to i64
+ br label %for.body
+
+for.cond.cleanup: ; preds =
%for.cond.cleanup4, %entry
+ ret void
+
+for.body: ; preds =
%for.cond.cleanup4, %for.body.lr.ph
+ br i1 %cmp352, label %for.cond6.preheader.preheader, label %for.cond.cleanup4
+
+for.cond6.preheader.preheader:; preds = %for.body
+ %wide.trip.count66 = sext i32 %L2 to i64
+ br label %for.cond6.preheader
+
+for.cond6.preheader: ; preds =
%for.cond.cleanup8, %for.cond6.preheader.preheader
+ %indvars.iv61 = phi i64 [ %4, %for.cond6.preheader.preheader ], [
%indvars.iv.next62, %fo
[clang] [polly] [llvm] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
kartcq wrote: Thanks for your comments @efriedma-quic **> The isl_options_set_on_error thing still seems like an issue; there's a path to restore on_error, but it doesn't run if the quota is hit.** Your concern makes sense. I have removed the early return there. **> Do we actually need to explicitly check hasQuotaExceeded() at all? If there's an error, the schedule should be null, and there's already a check for `if (Schedule.is_null())`.** I will still choose to keep hasQuotaExceeded() function to add a debug print indicating the reason for bailout as quota exceeded. https://github.com/llvm/llvm-project/pull/75141 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [polly] [llvm] [polly][ScheduleOptimizer] Fix long compile time(hang) reported in polly (PR #75141)
kartcq wrote: ping @efriedma-quic @xgupta https://github.com/llvm/llvm-project/pull/75141 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[polly] [clang-tools-extra] [llvm] [clang] [polly] Add polly-debug flag to print debug info from all parts of polly (PR #78549)
https://github.com/kartcq updated
https://github.com/llvm/llvm-project/pull/78549
>From 1aeb149cb15e83c8880a99aa94db224737331aa6 Mon Sep 17 00:00:00 2001
From: kartcq
Date: Fri, 15 Dec 2023 02:58:40 -0800
Subject: [PATCH 1/3] [polly] Add polly-debug flag to print debug info from all
parts of polly
This flag enable the user to print debug Info from all the passes and
helpers inside polly at once. This will help a novice user as well to
work in polly without explicitly having to know which parts of polly has
actually kicked in and pass them via -debug-only.
Change-Id: I6ddb03d5e7debac16413fb364afb8811139c8073
---
polly/include/polly/Support/PollyDebug.inc| 33 +++
polly/lib/Analysis/DependenceInfo.cpp | 1 +
polly/lib/Analysis/PolyhedralInfo.cpp | 1 +
polly/lib/Analysis/PruneUnprofitable.cpp | 1 +
polly/lib/Analysis/ScopBuilder.cpp| 1 +
polly/lib/Analysis/ScopDetection.cpp | 1 +
polly/lib/Analysis/ScopInfo.cpp | 1 +
polly/lib/CMakeLists.txt | 1 +
polly/lib/CodeGen/CodeGeneration.cpp | 1 +
polly/lib/CodeGen/IslAst.cpp | 1 +
polly/lib/Support/PollyDebug.cpp | 27 +++
polly/lib/Support/SCEVValidator.cpp | 1 +
polly/lib/Transform/DeLICM.cpp| 1 +
polly/lib/Transform/FlattenAlgo.cpp | 1 +
polly/lib/Transform/FlattenSchedule.cpp | 1 +
polly/lib/Transform/ForwardOpTree.cpp | 1 +
polly/lib/Transform/ManualOptimizer.cpp | 1 +
polly/lib/Transform/MatmulOptimizer.cpp | 1 +
polly/lib/Transform/ScheduleOptimizer.cpp | 1 +
polly/lib/Transform/ScheduleTreeTransform.cpp | 1 +
polly/lib/Transform/ScopInliner.cpp | 1 +
polly/lib/Transform/Simplify.cpp | 1 +
polly/lib/Transform/ZoneAlgo.cpp | 1 +
23 files changed, 81 insertions(+)
create mode 100644 polly/include/polly/Support/PollyDebug.inc
create mode 100644 polly/lib/Support/PollyDebug.cpp
diff --git a/polly/include/polly/Support/PollyDebug.inc
b/polly/include/polly/Support/PollyDebug.inc
new file mode 100644
index 0..84f13991251d9
--- /dev/null
+++ b/polly/include/polly/Support/PollyDebug.inc
@@ -0,0 +1,33 @@
+//===-PollyDebug.inc -Provide support for debugging Polly passes-*- C++
-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+//
+// Functions to aid printing Debug Info of all polly passes.
+//
+//===--===//
+
+
+#ifndef POLLY_DEBUG_H
+#define POLLY_DEBUG_H
+
+#include "llvm/Support/Debug.h"
+namespace polly {
+using namespace llvm;
+bool getPollyDebugFlag();
+#ifndef NDEBUG
+#undef LLVM_DEBUG
+#define LLVM_DEBUG(X)
\
+ do {
\
+if (polly::getPollyDebugFlag()) {
\
+ X;
\
+} else {
\
+ DEBUG_WITH_TYPE(DEBUG_TYPE, X);
\
+}
\
+ } while (0)
+#endif
+} // namespace polly
+#endif
diff --git a/polly/lib/Analysis/DependenceInfo.cpp
b/polly/lib/Analysis/DependenceInfo.cpp
index 69257c603877e..5df2e1329687c 100644
--- a/polly/lib/Analysis/DependenceInfo.cpp
+++ b/polly/lib/Analysis/DependenceInfo.cpp
@@ -39,6 +39,7 @@
using namespace polly;
using namespace llvm;
+#include "polly/Support/PollyDebug.inc"
#define DEBUG_TYPE "polly-dependence"
static cl::opt OptComputeOut(
diff --git a/polly/lib/Analysis/PolyhedralInfo.cpp
b/polly/lib/Analysis/PolyhedralInfo.cpp
index 5c77be0a9a1fa..5c7e61f0531d9 100644
--- a/polly/lib/Analysis/PolyhedralInfo.cpp
+++ b/polly/lib/Analysis/PolyhedralInfo.cpp
@@ -32,6 +32,7 @@
using namespace llvm;
using namespace polly;
+#include "polly/Support/PollyDebug.inc"
#define DEBUG_TYPE "polyhedral-info"
static cl::opt CheckParallel("polly-check-parallel",
diff --git a/polly/lib/Analysis/PruneUnprofitable.cpp
b/polly/lib/Analysis/PruneUnprofitable.cpp
index db4a3d73dc33a..c73de1c143ac6 100644
--- a/polly/lib/Analysis/PruneUnprofitable.cpp
+++ b/polly/lib/Analysis/PruneUnprofitable.cpp
@@ -22,6 +22,7 @@
using namespace llvm;
using namespace polly;
+#include "polly/Support/PollyDebug.inc"
#define DEBUG_TYPE "polly-prune-unprofitable"
namespace {
diff --git a/polly/lib/Analysis/ScopBuilder.cpp
b/polly/lib/Analysis/ScopBuilder.cpp
index c62cb2a85c835..b94b36bb22aa2 1006
[polly] [clang-tools-extra] [llvm] [clang] [polly] Add polly-debug flag to print debug info from all parts of polly (PR #78549)
https://github.com/kartcq updated
https://github.com/llvm/llvm-project/pull/78549
>From 1aeb149cb15e83c8880a99aa94db224737331aa6 Mon Sep 17 00:00:00 2001
From: kartcq
Date: Fri, 15 Dec 2023 02:58:40 -0800
Subject: [PATCH 1/3] [polly] Add polly-debug flag to print debug info from all
parts of polly
This flag enable the user to print debug Info from all the passes and
helpers inside polly at once. This will help a novice user as well to
work in polly without explicitly having to know which parts of polly has
actually kicked in and pass them via -debug-only.
Change-Id: I6ddb03d5e7debac16413fb364afb8811139c8073
---
polly/include/polly/Support/PollyDebug.inc| 33 +++
polly/lib/Analysis/DependenceInfo.cpp | 1 +
polly/lib/Analysis/PolyhedralInfo.cpp | 1 +
polly/lib/Analysis/PruneUnprofitable.cpp | 1 +
polly/lib/Analysis/ScopBuilder.cpp| 1 +
polly/lib/Analysis/ScopDetection.cpp | 1 +
polly/lib/Analysis/ScopInfo.cpp | 1 +
polly/lib/CMakeLists.txt | 1 +
polly/lib/CodeGen/CodeGeneration.cpp | 1 +
polly/lib/CodeGen/IslAst.cpp | 1 +
polly/lib/Support/PollyDebug.cpp | 27 +++
polly/lib/Support/SCEVValidator.cpp | 1 +
polly/lib/Transform/DeLICM.cpp| 1 +
polly/lib/Transform/FlattenAlgo.cpp | 1 +
polly/lib/Transform/FlattenSchedule.cpp | 1 +
polly/lib/Transform/ForwardOpTree.cpp | 1 +
polly/lib/Transform/ManualOptimizer.cpp | 1 +
polly/lib/Transform/MatmulOptimizer.cpp | 1 +
polly/lib/Transform/ScheduleOptimizer.cpp | 1 +
polly/lib/Transform/ScheduleTreeTransform.cpp | 1 +
polly/lib/Transform/ScopInliner.cpp | 1 +
polly/lib/Transform/Simplify.cpp | 1 +
polly/lib/Transform/ZoneAlgo.cpp | 1 +
23 files changed, 81 insertions(+)
create mode 100644 polly/include/polly/Support/PollyDebug.inc
create mode 100644 polly/lib/Support/PollyDebug.cpp
diff --git a/polly/include/polly/Support/PollyDebug.inc
b/polly/include/polly/Support/PollyDebug.inc
new file mode 100644
index 0..84f13991251d9
--- /dev/null
+++ b/polly/include/polly/Support/PollyDebug.inc
@@ -0,0 +1,33 @@
+//===-PollyDebug.inc -Provide support for debugging Polly passes-*- C++
-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM
Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===--===//
+//
+// Functions to aid printing Debug Info of all polly passes.
+//
+//===--===//
+
+
+#ifndef POLLY_DEBUG_H
+#define POLLY_DEBUG_H
+
+#include "llvm/Support/Debug.h"
+namespace polly {
+using namespace llvm;
+bool getPollyDebugFlag();
+#ifndef NDEBUG
+#undef LLVM_DEBUG
+#define LLVM_DEBUG(X)
\
+ do {
\
+if (polly::getPollyDebugFlag()) {
\
+ X;
\
+} else {
\
+ DEBUG_WITH_TYPE(DEBUG_TYPE, X);
\
+}
\
+ } while (0)
+#endif
+} // namespace polly
+#endif
diff --git a/polly/lib/Analysis/DependenceInfo.cpp
b/polly/lib/Analysis/DependenceInfo.cpp
index 69257c603877e..5df2e1329687c 100644
--- a/polly/lib/Analysis/DependenceInfo.cpp
+++ b/polly/lib/Analysis/DependenceInfo.cpp
@@ -39,6 +39,7 @@
using namespace polly;
using namespace llvm;
+#include "polly/Support/PollyDebug.inc"
#define DEBUG_TYPE "polly-dependence"
static cl::opt OptComputeOut(
diff --git a/polly/lib/Analysis/PolyhedralInfo.cpp
b/polly/lib/Analysis/PolyhedralInfo.cpp
index 5c77be0a9a1fa..5c7e61f0531d9 100644
--- a/polly/lib/Analysis/PolyhedralInfo.cpp
+++ b/polly/lib/Analysis/PolyhedralInfo.cpp
@@ -32,6 +32,7 @@
using namespace llvm;
using namespace polly;
+#include "polly/Support/PollyDebug.inc"
#define DEBUG_TYPE "polyhedral-info"
static cl::opt CheckParallel("polly-check-parallel",
diff --git a/polly/lib/Analysis/PruneUnprofitable.cpp
b/polly/lib/Analysis/PruneUnprofitable.cpp
index db4a3d73dc33a..c73de1c143ac6 100644
--- a/polly/lib/Analysis/PruneUnprofitable.cpp
+++ b/polly/lib/Analysis/PruneUnprofitable.cpp
@@ -22,6 +22,7 @@
using namespace llvm;
using namespace polly;
+#include "polly/Support/PollyDebug.inc"
#define DEBUG_TYPE "polly-prune-unprofitable"
namespace {
diff --git a/polly/lib/Analysis/ScopBuilder.cpp
b/polly/lib/Analysis/ScopBuilder.cpp
index c62cb2a85c835..b94b36bb22aa2 1006
