Use schedule trees to represent execution order of statements

Instead of flat schedules, we now use so-called schedule trees to represent the
execution order of the statements in a SCoP. Schedule trees make it a lot easier
to analyze, understand and modify properties of a schedule, as specific nodes
in the tree can be choosen and possibly replaced.

This patch does not yet fully move our DependenceInfo pass to schedule trees,
as some additional performance analysis is needed here. (In general schedule
trees should be faster in compile-time, as the more structured representation
is generally easier to analyze and work with). We also can not yet perform the
reduction analysis on schedule trees.

For more information regarding schedule trees, please see Section 6 of
https://lirias.kuleuven.be/handle/123456789/497238

llvm-svn: 242130

6 files changed, 41 insertions, 41 deletions

diff --git a/polly/test/DeadCodeElimination/chained_iterations.ll b/polly/test/DeadCodeElimination/chained_iterations.ll
index 801f46e2cd6..d6aa3b07b9d 100644
--- a/polly/test/DeadCodeElimination/chained_iterations.ll
+++ b/polly/test/DeadCodeElimination/chained_iterations.ll
@@ -49,13 +49,13 @@ exit.3:
   ret void
 }
 
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_2(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_3(c1);
-
-; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK-DCE:   Stmt_for_body_3(c1);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_2(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_3(c0);
+
+; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK-DCE:   Stmt_for_body_3(c0);
 
diff --git a/polly/test/DeadCodeElimination/chained_iterations_2.ll b/polly/test/DeadCodeElimination/chained_iterations_2.ll
index d60525409b1..d2cbe7861d3 100644
--- a/polly/test/DeadCodeElimination/chained_iterations_2.ll
+++ b/polly/test/DeadCodeElimination/chained_iterations_2.ll
@@ -54,12 +54,12 @@ exit.3:
   ret void
 }
 
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_2(c1);
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_3(c1);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_2(c0);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_3(c0);
 
-; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK-DCE:   Stmt_for_body_3(c1);
+; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK-DCE:   Stmt_for_body_3(c0);
diff --git a/polly/test/DeadCodeElimination/computeout.ll b/polly/test/DeadCodeElimination/computeout.ll
index c53b247f286..cd5fbea06aa 100644
--- a/polly/test/DeadCodeElimination/computeout.ll
+++ b/polly/test/DeadCodeElimination/computeout.ll
@@ -51,13 +51,13 @@ exit.3:
 }
 
 ; CHECK-NOT: Stmt_S
-; CHECK: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK: Stmt_S3(c1);
-
-; TIMEOUT: for (int c1 = 0; c1 <= 99; c1 += 1)
-; TIMEOUT: Stmt_S1(c1);
-; TIMEOUT: for (int c1 = 0; c1 <= 9; c1 += 1)
-; TIMEOUT: Stmt_S2(c1);
-; TIMEOUT: for (int c1 = 0; c1 <= 199; c1 += 1)
-; TIMEOUT: Stmt_S3(c1);
+; CHECK: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK: Stmt_S3(c0);
+
+; TIMEOUT: for (int c0 = 0; c0 <= 99; c0 += 1)
+; TIMEOUT: Stmt_S1(c0);
+; TIMEOUT: for (int c0 = 0; c0 <= 9; c0 += 1)
+; TIMEOUT: Stmt_S2(c0);
+; TIMEOUT: for (int c0 = 0; c0 <= 199; c0 += 1)
+; TIMEOUT: Stmt_S3(c0);
 
diff --git a/polly/test/DeadCodeElimination/dead_iteration_elimination.ll b/polly/test/DeadCodeElimination/dead_iteration_elimination.ll
index c805616bb19..6d0f8c5040b 100644
--- a/polly/test/DeadCodeElimination/dead_iteration_elimination.ll
+++ b/polly/test/DeadCodeElimination/dead_iteration_elimination.ll
@@ -67,12 +67,12 @@ exit.4:
   ret void
 }
 
-; CHECK: for (int c1 = 50; c1 <= 99; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 110; c1 <= 199; c1 += 1)
-; CHECK:   Stmt_for_body_1(c1);
-; CHECK: for (int c1 = 0; c1 <= 49; c1 += 1)
-; CHECK:   Stmt_for_body_2(c1);
-; CHECK: for (int c1 = 0; c1 <= 69; c1 += 1)
-; CHECK:   Stmt_for_body_3(c1);
-; CHECK: for (int c1 = 0; c1 <= 9; c1 += 1)
+; CHECK: for (int c0 = 50; c0 <= 99; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 110; c0 <= 199; c0 += 1)
+; CHECK:   Stmt_for_body_1(c0);
+; CHECK: for (int c0 = 0; c0 <= 49; c0 += 1)
+; CHECK:   Stmt_for_body_2(c0);
+; CHECK: for (int c0 = 0; c0 <= 69; c0 += 1)
+; CHECK:   Stmt_for_body_3(c0);
+; CHECK: for (int c0 = 0; c0 <= 9; c0 += 1)
diff --git a/polly/test/DeadCodeElimination/non-affine-affine-mix.ll b/polly/test/DeadCodeElimination/non-affine-affine-mix.ll
index b88aff1809a..ffe5cb02a2d 100644
--- a/polly/test/DeadCodeElimination/non-affine-affine-mix.ll
+++ b/polly/test/DeadCodeElimination/non-affine-affine-mix.ll
@@ -11,10 +11,10 @@
 ; the size of A and as a result S1 may write for example to A[1024], which
 ; is not overwritten by S2.
 
-; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
-; CHECK:   Stmt_S1(c1);
-; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
-; CHECK:   Stmt_S2(c1);
+; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1)
+; CHECK:   Stmt_S1(c0);
+; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1)
+; CHECK:   Stmt_S2(c0);
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
diff --git a/polly/test/DeadCodeElimination/null_schedule.ll b/polly/test/DeadCodeElimination/null_schedule.ll
index 62b318aaf4a..ff0bbd76c2c 100644
--- a/polly/test/DeadCodeElimination/null_schedule.ll
+++ b/polly/test/DeadCodeElimination/null_schedule.ll
@@ -52,5 +52,5 @@ exit.3:
   ret void
 }
 
-; CHECK-DCE: for (int c1 = 0; c1 <= 199; c1 += 1)
-; CHECK-DCE:   Stmt_for_body_2(c1);
+; CHECK-DCE: for (int c0 = 0; c0 <= 199; c0 += 1)
+; CHECK-DCE:   Stmt_for_body_2(c0);