diff options
Diffstat (limited to 'gcc/testsuite/gcc.dg/tree-ssa-chrec')
73 files changed, 2587 insertions, 0 deletions
diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/20040216-1.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/20040216-1.c new file mode 100644 index 00000000000..1d1784e011b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/20040216-1.c @@ -0,0 +1,27 @@ +/* APPLE LOCAL file lno */ +/* Test dependence graph. */ + +/* { dg-do compile } */ +/* { dg-options "-O2 -floop-test -c -fdump-tree-all" } */ + +#define N 16 +void bar(int *); +void foo() +{ + int i,j; + int A[N]; + int X[N]; + int Y[N]; + int Z[N]; + + for (i=2; i<9; i++) + { + X[i] = Y[i] + Z[i]; + A[i] = X[i-1] + 1; + } + + bar (A); +} + +/* Find 4 Dependence nodes */ +/* { dg-final { scan-tree-dump-times "Dependence Node" 4 "lptest"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-01.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-01.c new file mode 100644 index 00000000000..b7ac0083fb4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-01.c @@ -0,0 +1,36 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int main(void) +{ + unsigned a; + int b; + int c; + + /* loop_1 runs exactly 4 times. */ + for (a = 22; a < 50; a+=1) + { + /* loop_2 runs exactly 6 times. On exit, the variable B is equal to 53. */ + for (b = 23; b < 50; b+=5) + { + ++a; + + /* loop_3 runs {{77, +, -7}_1, +, -1}_2 times. */ + for (c = a; c < 100; c++) + { + + } + } + } +} + +/* The analyzer has to detect the following evolution functions: + b -> {23, +, 5}_2 + a -> {{22, +, 7}_1, +, 1}_2 + c -> {{{23, +, 7}_1, +, 1}_2, +, 1}_3 +*/ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 4" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 6" 1 "lptest"} } */ + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-02.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-02.c new file mode 100644 index 00000000000..2dce3aa1aa6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-02.c @@ -0,0 +1,29 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int main(void) +{ + int a; + int b; + int *c; + + /* The following loop runs exactly 3 times. */ + for (a = 11; a < 50; a++) + { + /* The following loop runs exactly 9 times. */ + for (b = 8; b < 50; b+=5) + { + c[a + 5] = 5; + c[b] = 6; + a+=2; + } + } +} + +/* The analyzer has to detect the following evolution functions: + b -> {8, +, 5}_2 + a -> {{11, +, 19}_1, +, 2}_2 +*/ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 3" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 9" 1 "lptest"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-03.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-03.c new file mode 100644 index 00000000000..6c8870af942 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-03.c @@ -0,0 +1,30 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-stats" } */ + + +int main(void) +{ + int a; + int b; + int *c; + + /* loop_1 runs exactly 5 times. */ + for (a = 11; a < 50; a++) + { + /* loop_2 runs exactly 7 times. */ + for (b = 8; b < 50; b+=5) + { + c[a++] = 5; + c[b++] = 6; + } + } +} + +/* The analyzer has to detect the following evolution functions: + b -> {8, +, 6}_2 + a -> {{11, +, 8}_1, +, 1}_2 +*/ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 5" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 7" 1 "lptest"} } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-04.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-04.c new file mode 100644 index 00000000000..0efebb01a3e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-04.c @@ -0,0 +1,22 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -ftree-elim-checks -fdump-tree-lptest-details -fdump-tree-elck-details -fdump-tree-optimized" } */ + +void remove_me (void); + +int main(void) +{ + int a; + int b = 22; + + /* loop_1 runs exactly 28 times. */ + for (a = 22; a < 50; a++) /* a -> {22, +, 1}_1 */ + { + if (a > b) /* This condition is always false. */ + remove_me (); + b = b + 2; /* b -> {22, +, 2}_1 */ + } +} + +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 28" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-05.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-05.c new file mode 100644 index 00000000000..09df0c89050 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-05.c @@ -0,0 +1,33 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main(void) +{ + int a; + int b; + int c; + + /* nb_iterations 28 */ + for (a = 22; a < 50; a++) + { + /* nb_iterations 6 */ + for (b = 23; b < 50; b+=5) + { + /* nb_iterations {78, +, -1}_1 */ + for (c = a; c < 100; c++) + { + + } + } + } +} + +/* The analyzer has to detect the following evolution functions: + a -> {22, +, 1}_1 + b -> {23, +, 5}_2 + c -> {{22, +, 1}_1, +, 1}_3 +*/ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 28" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 6" 1 "lptest"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-06.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-06.c new file mode 100644 index 00000000000..a2b9abdcdba --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-06.c @@ -0,0 +1,51 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -ftree-elim-checks -fdump-tree-lptest-details -fdump-tree-optimized" } */ + +void remove_me (void); + +int main(void) +{ + int a; + int b; + int c; + + /* loop_1 runs 2 times. */ + for (a = 22; a < 83; a+=1) /* a -> {22, +, 60}_1 */ + { + c = a; + + /* loop_2 runs exactly 6 times. */ + for (b = 23; b < 50; b+=5) /* b -> {23, +, 5}_2 */ + { + ++a; + } + /* The following stmt exercises the value of B on the exit of the loop. + In this case the value of B out of the loop is that of the evolution + function of B applied to the number of iterations the inner loop_2 runs. + Value (B) = {23, +, 5}_2 (6) = 53. */ + + /* At this point, the variable A has the evolution function: + {{22, +, 6}_1, +, 1}_2. */ + if (b != 53 + || a != c + 6) + remove_me (); + + a = a + b; + /* At this point, the variable A has the evolution function: + {{22, +, 59}_1, +, 1}_2. The evolution of the variable B in + the loop_2 does not matter, and is not recorded in the + evolution of A. The above statement is equivalent to: + "a = a + 53", ie. the scalar value of B on exit of the loop_2. */ + + if (a != c + 59) + remove_me (); + + /* And finally the a+=1 from the FOR_STMT produces the evolution + function: {{22, +, 60}_1, +, 1}_2. */ + } +} + +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 2" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 6" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-07.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-07.c new file mode 100644 index 00000000000..ca00f4a1c53 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-07.c @@ -0,0 +1,28 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -ftree-elim-checks -fdump-tree-optimized" } */ + +void remove_me (void); + +int main(void) +{ + int a = -100; + int b = 2; + int d = -1; + int e = -100; + + while (a) + { + /* Exercises higher order polynomials. */ + a = a + b; /* a -> {-100, +, {2, +, 3}_1}_1 */ + b = b + 3; /* b -> {2, +, 3}_1 */ + + d = d + 3; /* d -> {-1, +, 3}_1 */ + e = e + d; /* e -> {-100, +, {2, +, 3}_1}_1 */ + + if (a != e) /* a -> {-98, +, {5, +, 3}_1}_1 */ + remove_me (); + } +} + +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-08.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-08.c new file mode 100644 index 00000000000..48296fa46f4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-08.c @@ -0,0 +1,32 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -ftree-elim-checks -fdump-tree-optimized" } */ + +void remove_me (void); + +int main(void) +{ + int a = -100; + int b = 2; + int c = 3; + int d = -5; + int e = 3; + int f = -100; + + while (a) + { + /* Exercises higher order polynomials. */ + a = a + b; /* a -> {-100, +, 2, +, 3, +, 4}_1 */ + b = b + c; /* b -> {2, +, 3, +, 4}_1 */ + c = c + 4; /* c -> {3, +, 4}_1 */ + + d = d + 4; /* d -> {-5, +, 4}_1 */ + e = e + d; /* e -> {3, +, -1, +, 4}_1 */ + f = f + e; /* f -> {-100, +, 2, +, 3, +, 4}_1 */ + + if (a != f) /* (a == f) -> {-98, +, 5, +, 7, +, 4}_1 */ + remove_me (); + } +} + +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-09.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-09.c new file mode 100644 index 00000000000..406544f3b7d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-09.c @@ -0,0 +1,42 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int main(void) +{ + int a = -100; + int b = 2; + int c = 3; + int d = 4; + int e = 5; + + while (a) + { + /* Exercises the cycle detector: a -> b -> (c -> d -> e -> c)*. */ + a += b; + b += c; + c += d; + d += e; + e += c; + } +} + +/* This is what is commonly called a "mixer". It whirls the data in a + strongly connected component. We expect the following evolution + functions: + + e -> {5, +, c_13}_1 + d -> {4, +, {5, +, c_13}_1}_1 + c -> {3, +, {4, +, {5, +, c_13}_1}_1}_1 + b -> {2, +, {3, +, {4, +, {5, +, c_13}_1}_1}_1}_1 + a -> {-100, +, {2, +, {3, +, {4, +, {5, +, c_13}_1}_1}_1}_1}_1 +*/ + +/* FIXME: + For the moment this testcase does not test for anything, but for + not ICEing, and for documentation purposes (okay here is the + definition of a mixer). However, I'm considering testing something + around the lines of ssa-chrec-08.c, ie. build two mixers, and then + compare their values. But that is difficult, and low priority. */ + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-10.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-10.c new file mode 100644 index 00000000000..7054ebd4513 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-10.c @@ -0,0 +1,31 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest " } */ + +void bar (int); + +int foo (void) +{ + int a; + int x; + int c[100][100]; + + /* loop_1 runs 39 times. */ + for (a = 11; a < 50; a++) + { + /* Array access functions have to be analyzed. */ + x = a + 5; + c[x][a+1] = c[x+2][a+3] + c[x-1][a+2]; + } + bar (c[1][2]); +} + +/* The analyzer has to detect the scalar functions: + a -> {11, +, 1}_1 + x -> {16, +, 1}_1 + x+2 -> {18, +, 1}_1 + x-1 -> {15, +, 1}_1 +*/ + +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 39" 1 "lptest"} } */ +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-10.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-10.c.ddall new file mode 100644 index 00000000000..5cbc752367f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-10.c.ddall @@ -0,0 +1,59 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + +(Data Dep (A = 0, B = 2): + (subscript 0: + access_fn_A: {14, +, 1}_1 + access_fn_B: {12, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {2, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {18, +, 1}_1 + access_fn_B: {16, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {2, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(2 +) +(2 +) + ) +) +(Data Dep (A = 1, B = 2): (no dependence) +) +(Data Dep (A = 2, B = 2): + (subscript 0: + access_fn_A: {12, +, 1}_1 + access_fn_B: {12, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {16, +, 1}_1 + access_fn_B: {16, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(0 +) + ) +) +(Data Dep (A = 2, B = 3): (no dependence) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-11.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-11.c new file mode 100644 index 00000000000..7e1779f97b4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-11.c @@ -0,0 +1,60 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main(void) +{ + int a = -100; + int b = 2; + + int f = 6; + int g = 7; + int h = 8; + + /* Exercises complex loop exit conditions. + FIXME: This is a strange case where the compiler cc1 and the wrapper gcc + don't produce the same representation: + + (with gcc from command line) + + T.1_9 = f_2 | a_1; + if (T.1_9 == 0) + { + goto <UL47e0>; + } + + versus (with cc1 called from gdb): + + if (f_2 == 0) + { + if (a_1 == 0) + { + goto <ULc7e0>; + } + else + { + (void)0 + } + } + else + { + (void)0 + }; + */ + while (f || a) + { + a += b; + + f += g; + g += h; + } +} + +/* + g -> {7, +, 8}_1 + f -> {6, +, {7, +, 8}_1}_1 + a -> {-100, +, 2}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-12.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-12.c new file mode 100644 index 00000000000..067bfcb2474 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-12.c @@ -0,0 +1,33 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int a = -100; + int b = 2; + int c = 3; + int d = 4; + + while (a) + { + a = a + b; + + /* Exercises if-phi-nodes. */ + if (bar ()) + b = b + c; + + c = c + d; + } +} + +/* The analyzer has to detect the following evolution functions: + c -> {3, +, 4}_1 + b -> {2, +, {[0, 3], +, [0, 4]}_1}_1 + a -> {-100, +, {2, +, {[0, 3], +, [0, 4]}_1}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-13.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-13.c new file mode 100644 index 00000000000..cb785d020f4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-13.c @@ -0,0 +1,33 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int foo (void); + +int main (void) +{ + int a = -100; + int b = 2; + int c = 3; + + while (a) + { + /* Exercises if-phi-nodes. */ + if (foo ()) + a += b; + else + a += c; + + b++; + c++; + } +} + +/* The analyzer has to detect the following evolution function: + a -> {-100, +, {[2, 3], +, 1}_1}_1 +*/ + +/* FIXME. */ + + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-14.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-14.c new file mode 100644 index 00000000000..c0258c81aba --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-14.c @@ -0,0 +1,37 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int foo (void); + +int main (void) +{ + int a = -100; + int b = 2; + int c = 3; + int d = 4; + + while (d) + { + if (foo ()) + a += b; + else + a += c; + + b += 1; + c += 5; + + /* Exercises the initial condition of A after the if-phi-node. */ + d = d + a; + } +} + +/* The analyzer has to detect the following evolution function: + b -> {2, +, 1}_1 + c -> {3, +, 5}_1 + a -> {-100, +, {[2, 3], +, [1, 5]}_1}_1 + d -> {4, +, {[-98, -97], +, {[2, 3], +, [1, 5]}_1}_1}_1 +*/ + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-15.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-15.c new file mode 100644 index 00000000000..800866b677b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-15.c @@ -0,0 +1,24 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main (void) +{ + int a; + int b; + int c; + + /* Exercises the MINUS_EXPR. loop_1 runs 50 times. */ + for (a = 100; a > 50; a--) + { + + } +} + +/* The analyzer has to detect the following evolution function: + a -> {100, +, -1}_1 +*/ + +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 50" 1 "lptest"} } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-16.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-16.c new file mode 100644 index 00000000000..a80414abb83 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-16.c @@ -0,0 +1,27 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main (void) +{ + int a = -100; + int b = 2; + int c = 3; + int d = 4; + + /* Determining the number of iterations for the != or == is work in + progress. Same for polynomials of degree >= 2, where we have to + find the zeros of the polynomial. */ + while (d) + { + a += 23; + d = a + d; + } +} + +/* a -> {-100, +, 23}_1 + d -> {4, +, {-77, +, 23}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-17.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-17.c new file mode 100644 index 00000000000..1e7ac50e013 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-17.c @@ -0,0 +1,36 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +void foo () +{ + int a = -100; + int b = 2; + + while (b) + { + if (bar ()) + a += 3; + else + a = 2; + + /* Exercises the case when one of the branches of the if-phi-node is a constant. + FIXME: + - What is the chrec representation of such an evolution? + - Does this kind of code exist in real codes? */ + b += a; + } +} + +/* For the moment the analyzer is expected to output a "don't know" answer, + both for the initial condition and for the evolution part. This is done + in the merge condition branches information. + + a -> [-oo, +oo] + b -> {2, +, a_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-18.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-18.c new file mode 100644 index 00000000000..f72aaa1f542 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-18.c @@ -0,0 +1,32 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo (int x) +{ + int a = -100; + int b = 2; + + while (b) + { + if (x) + a += 3; + else + a += bar (); + + /* Exercises the case when one of the branches of the if-phi-node cannot + be determined: [-oo, +oo]. + Since the evolution function is too difficult to handle in the expanded + form, we have to keep it in its symbolic form: "b -> {2, +, a_1}_1". */ + b += a; + } +} + +/* a -> {-100, +, [min<t, 3>, max<t, 3>]}_1 + b -> {2, +, {[min<t, 3>, max<t, 3>] - 100, +, [min<t, 3>, max<t, 3>]}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-19.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-19.c new file mode 100644 index 00000000000..bb3a5b183ae --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-19.c @@ -0,0 +1,21 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int b = 2; + + while (b) + { + /* Exercises the MULT_EXPR. */ + b = 2*b; + } +} + +/* b -> {2, *, 2}_1 +*/ + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-20.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-20.c new file mode 100644 index 00000000000..e5a24d80a8f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-20.c @@ -0,0 +1,30 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 3; + int b = 2; + + while (a) + { + b += 5; + a += b; + + /* Exercises the sum of a polynomial of degree 2 with an + evolution of degree 1: + + (loop_num = 1, chrec_var = {3, +, 7, +, 5}, to_add = 2). + The result should be: {3, +, 9, +, 5}. */ + a += 2; + } +} + +/* + b -> {2, +, 5}_1 + a -> {3, +, {9, +, 5}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-21.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-21.c new file mode 100644 index 00000000000..82c5ccb49db --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-21.c @@ -0,0 +1,22 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 3; + int b = 2; + + while (b) + { + a *= 4; + b *= a; + } +} + +/* a -> {3, *, 4}_1 + b -> {{2, *, 12}_1, *, 4}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-22.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-22.c new file mode 100644 index 00000000000..a439099e4df --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-22.c @@ -0,0 +1,24 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 2; + int b = 4; + + while (a) + { + a *= 3; + a *= b; + b *= 5; + } +} + +/* + b -> {4, *, 5}_1 + a -> {2, *, {12, *, 5}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-23.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-23.c new file mode 100644 index 00000000000..c12bc4bf469 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-23.c @@ -0,0 +1,22 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 1; + int b = 1; + + while (a) + { + a *= b; + b += 1; + } +} + +/* a -> {1, *, {1, +, 1}_1}_1 +*/ + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-24.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-24.c new file mode 100644 index 00000000000..96095cd4d4e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-24.c @@ -0,0 +1,30 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int c; + + /* This exercises the initial condition propagator: + Interval Copy Constant Propagation (ICCP). */ + if (bar ()) + c = 2; + else + c = 3; + + while (c) + { + c += 5; + } +} + +/* + c -> {[2, 3], +, 5}_1 +*/ + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-25.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-25.c new file mode 100644 index 00000000000..43b1dc5bd37 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-25.c @@ -0,0 +1,29 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int c = 7; + + /* This exercises the initial condition propagator: + Interval Copy Constant Propagation (ICCP). */ + if (bar ()) + c = 2; + else + c += 3; + + while (c) + { + c += 5; + } +} + +/* + c -> {[2, 10], +, 5}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-26.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-26.c new file mode 100644 index 00000000000..f7025534118 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-26.c @@ -0,0 +1,26 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int a = -100; + int b = -10; + + /* This exercises a code with two loop nests. */ + + while (a) + a++; + + while (b) + b++; +} + +/* a -> {-100, +, 1}_1 + b -> {-10, +, 1}_2 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-27.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-27.c new file mode 100644 index 00000000000..92c627d324c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-27.c @@ -0,0 +1,41 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int a = -100; + + /* This exercises a code with two loop nests. */ + + /* loop_1 runs 100 times. */ + while (a < 0) + a++; + + a -= 77; + + /* loop_2 runs 26 times. */ + while (a < 0) + a+=3; +} + +/* The analyzer sees two loop nests: + for the first, it determines the evolution: + a -> {-100, +, 1}_1 + + and for the second, it determines that the first loop ends at 0 and then: + a -> {-77, +, 3}_2 + + When the constant propagation is postponed, the analyzer detects + for the second loop the evolution function: + a -> {a_5, +, 3}_2 + +*/ + +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 100" 1 "lptest"} } */ +/* { dg-final { scan-tree-dump-times "set_nb_iterations_in_loop = 26" 1 "lptest"} } */ + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-28.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-28.c new file mode 100644 index 00000000000..a05930fb0df --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-28.c @@ -0,0 +1,40 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int i; + int a = 2; + + while (a) + { + a *= 3; + + for (i = 0; i < 100; i++) + a += 4; + } +} + +/* FIXME: We have to transform the evolution function of "a" into an infinite + sum, a -> {//2, *, 2//}, and then to add the 400 from the inner sum... + But this is quite difficult, and cases like this one do not happen often. + + (Francois Irigoin consider that this case falls into the 0.01 percent + rule, and it is no worth to implement a solution for this testcase in a + production compiler. ) +*/ + +/* Do nothing for this testcase. + The following evolutions are detected: + + i -> {0, +, 1}_2 + a -> {{2, *, [-oo, +oo]}_1, +, 4}_2 + +*/ + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-29.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-29.c new file mode 100644 index 00000000000..5d639a9dfae --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-29.c @@ -0,0 +1,41 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int bar (void); + +int foo () +{ + int i; + int a = 2; + + while (a) + { + a *= 3; + a += 5; + } +} + +/* FIXME: This exposes a problem in the representation. Is it + possible to have an exponential and a polynomial together? + + The first assignment constructs "a -> {2, *, 3}_1", + while the second adds 5 as a polynomial function. + + The following two representations are not correct: + "a -> {{2, *, 3}_1, +, 5}_1" + "a -> {{2, +, 5}_1, *, 3}_1" + + The right solution is: + "a -> {2, *, 3}_1 + {0, +, 5}_1" + but this exposes yet again the "exp + poly" problem: the representation + is not homogen. Going into a Taylor decomposition could solve this problem. + + This is too difficult for the moment, and does not happen often. +*/ + +/* Do nothing for this testcase. */ + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-30.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-30.c new file mode 100644 index 00000000000..1b511fd0e92 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-30.c @@ -0,0 +1,22 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +void foo (int); + +int main () +{ + int c[100][200]; + int a; + int x; + + for (a = 1; a < 50; a++) + { + x = a; + c[x-7][1] = c[x+2][3] + c[x-1][2]; + c[x][2] = c[x+2][3]; + } + foo (c[12][13]); +} + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-30.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-30.c.ddall new file mode 100644 index 00000000000..78404a624fe --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-30.c.ddall @@ -0,0 +1,96 @@ +;; APPLE LOCAL file lno +;; Function main (main) + +(Data Dep (A = 0, B = 2): (no dependence) +) +(Data Dep (A = 0, B = 4): (no dependence) +) +(Data Dep (A = 1, B = 2): (no dependence) +) +(Data Dep (A = 1, B = 4): + (subscript 0: + access_fn_A: 2 + access_fn_B: 2 + iterations_that_access_an_element_twice_in_A: 0 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {0, +, 1}_1 + access_fn_B: {1, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {1, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(-1 +) + ) +) +(Data Dep (A = 2, B = 2): + (subscript 0: + access_fn_A: 1 + access_fn_B: 1 + iterations_that_access_an_element_twice_in_A: 0 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {-6, +, 1}_1 + access_fn_B: {-6, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(0 +) + ) +) +(Data Dep (A = 2, B = 3): (no dependence) +) +(Data Dep (A = 2, B = 4): (no dependence) +) +(Data Dep (A = 2, B = 5): (no dependence) +) +(Data Dep (A = 3, B = 4): (no dependence) +) +(Data Dep (A = 4, B = 4): + (subscript 0: + access_fn_A: 2 + access_fn_B: 2 + iterations_that_access_an_element_twice_in_A: 0 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {1, +, 1}_1 + access_fn_B: {1, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(0 +) + ) +) +(Data Dep (A = 4, B = 5): (no dependence) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-31.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-31.c new file mode 100644 index 00000000000..6e1f7167705 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-31.c @@ -0,0 +1,20 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +void bar (short); + +#define N 100 +foo (){ + short a[N]; + short b[N]; + short c[N]; + int i; + + for (i=0; i<N; i++){ + a[i] = b[i] + c[i]; + } + bar (a[2]); +} + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-31.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-31.c.ddall new file mode 100644 index 00000000000..636d4f94c48 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-31.c.ddall @@ -0,0 +1,37 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + +(Data Dep (A = 0, B = 2): (no dependence) +) +(Data Dep (A = 1, B = 2): (no dependence) +) +(Data Dep (A = 2, B = 2): + (subscript 0: + access_fn_A: {0, +, 1}_1 + access_fn_B: {0, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) + ) +) +(Data Dep (A = 2, B = 3): + (subscript 0: + access_fn_A: {0, +, 1}_1 + access_fn_B: 2 + iterations_that_access_an_element_twice_in_A: 2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(-2 +) + ) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-32.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-32.c new file mode 100644 index 00000000000..25db7da6ba9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-32.c @@ -0,0 +1,36 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +void bar (short); + +#define N 100 +#define NPad 10 +#define M 32 +void foo() +{ + short coef[M]; + short input[N]; + short output[N]; + + int i,j,k; + int sum; + + for (i = 0; i < N; i++) { + sum = 0; + for (j = 0; j < M; j++) { + sum += input[i+NPad-j] * coef[j]; + } + output[i] = sum; + } + bar (sum); +} + +/* The following evolution functions have to be detected: + + i -> {0, +, 1}_1 + j -> {0, +, 1}_2 + +*/ + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-32.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-32.c.ddall new file mode 100644 index 00000000000..c3e83533cab --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-32.c.ddall @@ -0,0 +1,5 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-33.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-33.c new file mode 100644 index 00000000000..c2879e2faa4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-33.c @@ -0,0 +1,47 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +void bar (int); + +#define N 100 +#define NPad 10 +#define M 32 + +void foo () +{ + short coefs[2*M]; + short input[2*N]; + short output[2*N]; + + int sum_real, sum_imag; + int i,j,k; + + k = NPad; + for (i = 0; i < N; i++) + { + sum_real = 0; + sum_imag = 0; + for (j = 0; j < M; j++) + { + sum_real += + input[2*k-2*j+1]*coefs[2*j+1] - input[2*k-2*j]*coefs[2*j]; + + sum_imag += + input[2*k-2*j]*coefs[2*j+1] + input[2*k-2*j+1]*coefs[2*j]; + } + output[2*i+1] = sum_imag; + output[2*i] = sum_real; + k++; + } + bar (sum_imag); +} + +/* The following evolution functions have to be detected: + + i -> {0, +, 1}_1 + j -> {0, +, 1}_2 + +*/ + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-33.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-33.c.ddall new file mode 100644 index 00000000000..c3e83533cab --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-33.c.ddall @@ -0,0 +1,5 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-34.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-34.c new file mode 100644 index 00000000000..f3369502aa1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-34.c @@ -0,0 +1,34 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +void bar (int); + +#define M 16 +#define N 8 + +short foo (short image[][M], short block[][N]){ + int sad, diff = 0; + int i, j; + int tmp; + + for (i = 0; i < N; i++) { + sad = 0; + for (j = 0; j < N; j++) { + tmp = image[i][j] - block[i][j]; + sad += (tmp < 0) ? -tmp : tmp; + } + diff += sad; + } + + return diff; +} + +/* The following evolution functions have to be detected: + + i -> {0, +, 1}_1 + j -> {0, +, 1}_2 + +*/ + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-34.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-34.c.ddall new file mode 100644 index 00000000000..c3e83533cab --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-34.c.ddall @@ -0,0 +1,5 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-35.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-35.c new file mode 100644 index 00000000000..e17b5a6c6c1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-35.c @@ -0,0 +1,35 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +#define L 100 +#define M 100 +#define N 100 + +int bar (float); + +int foo (float A[][M][N]) +{ + int i, j, k; + + for (i = 0; i < L; i++) + for (j = 0; j < M; j++) + for (k = 0; k < N; k++) + A[i][j][j] = A[i][j][k]; + + return bar (A[10][11][12]); +} + +/* The following evolution functions have to be detected: + + i -> {0, +, 1}_1 + j -> {0, +, 1}_2 + k -> {0, +, 1}_3 + + For the subscript [j] vs. [k], "{0, +, 1}_2" vs. "{0, +, 1}_3" + the overlapping elements are respectively located at iterations: + {0, +, 1}_3 and {0, +, 1}_2. + +*/ + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-35.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-35.c.ddall new file mode 100644 index 00000000000..a1039a40f7d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-35.c.ddall @@ -0,0 +1,59 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + +(Data Dep (A = 0, B = 1): + (subscript 0: + access_fn_A: {0, +, 1}_3 + access_fn_B: {0, +, 1}_2 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_3 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {0, +, 1}_2 + access_fn_B: {0, +, 1}_2 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +([-oo, +oo] +) +(0 +) + ) +) +(Data Dep (A = 1, B = 1): + (subscript 0: + access_fn_A: {0, +, 1}_2 + access_fn_B: {0, +, 1}_2 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {0, +, 1}_2 + access_fn_B: {0, +, 1}_2 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(0 +) + ) +) +(Data Dep (A = 1, B = 2): (no dependence) +) +(Data Dep (A = 1, B = 3): (don't know) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-36.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-36.c new file mode 100644 index 00000000000..40a71819b6e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-36.c @@ -0,0 +1,28 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +int foo (int); + +int main () +{ + int res; + int c[100][200]; + int a; + int x; + + for (a = 1; a < 50; a++) + { + c[a+1][a] = 2; + res += c[a][a]; + + /* This case exercises the subscript coupling detection: the dependence + detectors have to determine that there is no dependence between + c[a+1][a] and c[a][a]. */ + } + + return res + foo (c[12][13]); +} + +/* { dg-final { diff-tree-dumps "ddall" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-36.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-36.c.ddall new file mode 100644 index 00000000000..a355c7f2a32 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-36.c.ddall @@ -0,0 +1,59 @@ +;; APPLE LOCAL file lno +;; Function main (main) + +(Data Dep (A = 0, B = 0): + (subscript 0: + access_fn_A: {1, +, 1}_1 + access_fn_B: {1, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {2, +, 1}_1 + access_fn_B: {2, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(0 +) + ) +) +(Data Dep (A = 0, B = 1): (no dependence) +) +(Data Dep (A = 0, B = 2): + (subscript 0: + access_fn_A: {1, +, 1}_1 + access_fn_B: 13 + iterations_that_access_an_element_twice_in_A: 12 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {2, +, 1}_1 + access_fn_B: 12 + iterations_that_access_an_element_twice_in_A: 10 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(-12 +) +(-10 +) + ) +) +(Data Dep (A = 0, B = 3): (don't know) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-37.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-37.c new file mode 100644 index 00000000000..746a81e68fe --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-37.c @@ -0,0 +1,30 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a; + int b = 2; + int c = 11; + + for (a = -123; a < 0; c += 12, b += 5) + { + a += b; + + /* The next stmt exercises the add_function_to_loop_evolution + (loop_num = 1, chrec_before = {-123, +, {2, +, 5}_1}_1, to_add = {11, +, 12}_1). + The result should be: {-123, +, {13, +, 17}_1}_1. */ + a += c; + } +} + +/* + b -> {2, +, 5}_1 + c -> {11, +, 12}_1 + a -> {-123, +, {13, +, 17}_1}_1 +*/ + + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-38.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-38.c new file mode 100644 index 00000000000..bdfe8bc6bfd --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-38.c @@ -0,0 +1,49 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 3; + int b = 2; + int c = 11; + int d = -5; + + while (a) + { + b += 5; + a += b; + + for (d = -5; d < 0; d++) + { + /* Exercises the build_polynomial_evolution_in_loop function in the following context: + (add_to_evolution + loop_num = 2 + chrec_before = {3, +, 7, +, 5}_1 + to_add = {11, +, 12}_1 + res = {{3, +, 7, +, 5}_1, +, {11, +, 12}_1}_2 + ) + + This also exercises the chrec_apply function in the following context: + (chrec_apply + var = 2 + chrec = {0, +, {11, +, 12}_1}_2 + x = 5 + res = {55, +, 60}_1 + ) + */ + a += c; + } + c += 12; + } +} + +/* + b -> {2, +, 5}_1 + c -> {11, +, 12}_1 + d -> {-5, +, 1}_2 + a -> {{3, +, 62, +, 65}_1, +, {11, +, 12}_1}_2 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-39.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-39.c new file mode 100644 index 00000000000..87d844482e7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-39.c @@ -0,0 +1,46 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int foo (int ParmN) +{ + int a = 3; + int b = 2; + int d = -5; + + while (a) + { + b += 25; + a += b; + + for (d = -5; d < 0; d++) + { + /* Exercises the build_polynomial_evolution_in_loop in the following context: + (add_to_evolution + loop_num = 2 + chrec_before = {3, +, {27, +, 25}_1}_1 + to_add = ParmN_15 + res = {{3, +, {27, +, 25}_1}_1, +, ParmN_15}_2 + ) + + Then it exercises the add_expr_to_loop_evolution in the following context: + (add_to_evolution + loop_num = 1 + chrec_before = {{3, +, {27, +, 25}_1}_1, +, ParmN_15}_2 + to_add = ParmN_15 * 5 + res = {{3, +, {ParmN_15 * 5 + 27, +, 25}_1}_1, +, ParmN_15}_2 + ) + */ + a += ParmN; + } + } +} + +/* + b -> {2, +, 25}_1 + d -> {-5, +, 1}_2 + a -> {{3, +, {ParmN * 5 + 27, +, 25}_1}_1, +, ParmN}_2 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-40.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-40.c new file mode 100644 index 00000000000..7a1ecf7d5bd --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-40.c @@ -0,0 +1,23 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 1; + int b = 1; + + while (a) + { + a += b; + b *= 2; + } +} + +/* + b -> {1, *, 2}_1 + a -> {1, +, {1, *, 2}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-41.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-41.c new file mode 100644 index 00000000000..ab93fbcaf98 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-41.c @@ -0,0 +1,53 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 2; + int b = 4; + int c = 2; + + while (a) + { + a *= 3; + for (c = -10; c < 0; c++) + { + /* Exercises the build_exponential_evolution_in_loop function in the following context: + (multiply_evolution + loop_num = 2 + chrec_before = {2, *, 3}_1 + to_mult = {4, *, 5}_1 + res = {{2, *, 3}_1, *, {4, *, 5}_1}_2 + ) + + Then it exerces the chrec_apply in the following context: + (chrec_apply + var = 2 + chrec = {0, +, {4, *, 5}_1}_2 + x = 10 + res = {40, *, 5}_1 + ) + + Finally it tests the + (add_to_evolution + loop_num = 1 + chrec_before = {{2, *, 3}_1, *, {4, *, 5}_1}_2 + to_add = {40, *, 5}_1 + res = {{2, *, {120, *, 5}_1}_1, *, {4, *, 5}_1}_2 + ) + */ + a *= b; + } + b *= 5; + } +} + +/* + c -> {-10, +, 1}_2 + b -> {4, *, 5}_1 + a -> {{2, *, {120, *, 5}_1}_1, *, {4, *, 5}_1}_2 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-42.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-42.c new file mode 100644 index 00000000000..33378ddfa9c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-42.c @@ -0,0 +1,31 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 1; + int b = 2; + int c = 0; + int d = 5; + + while (a) + { + a += b; + a += d; + + b += c; + c += 1; + d += 9; + } +} + +/* + c -> {0, +, 1}_1 + b -> {2, +, 0, +, 1}_1 + d -> {5, +, 9}_1 + a -> {1, +, 7, +, 9, +, 1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-43.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-43.c new file mode 100644 index 00000000000..329f205506f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-43.c @@ -0,0 +1,65 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + + +int main () +{ + int a = 1; + int b = 2; + int c = 0; + int d = 5; + int e; + + while (a) + { + /* The following statement produces the evolution function: + (add_to_evolution + loop_num = 1 + chrec_before = 1 + to_add = {{2, +, 0}_1, +, 10}_1 + res = {{{1, +, 2}_1, +, 0}_1, +, 10}_1 + ) + Note that the evolution of B in the inner loop_2 is not + relevant to the evolution of A in the loop_1. */ + a += b; + + /* And finally the following statement produces the expected scev: + (add_to_evolution + loop_num = 1 + chrec_before = {{{1, +, 2}_1, +, 0}_1, +, 10}_1 + to_add = {5, +, 9}_1 + res = {{{1, +, 7}_1, +, 9}_1, +, 10}_1 + ) + That ends this not so formal proof ("CQFD" in french ;-). */ + a += d; + + for (e = 0; e < 10; e++) + b += c; + /* After having analyzed this loop, the overall effect is added to the evolution of b. + This corresponds to the following operation: + (add_to_evolution + loop_num = 1 + chrec_before = {2, +, {0, +, 1}_1}_2 + to_add = {0, +, 10}_1 + res = {{{2, +, 0}_1, +, 10}_1, +, {0, +, 1}_1}_2 + ). + Note that the variable c has not yet been updated in the loop, and thus its value + at this version is "{0, +, 1}_1". Since the loop_2 runs exactly 10 times, the overall + effect of the loop is "10 * {0, +, 1}_1": that is the TO_ADD argument. + */ + + c += 1; + d += 9; + } +} + +/* + c -> {0, +, 1}_1 + e -> {0, +, 1}_2 + b -> {{2, +, 0, +, 10}_1, +, {0, +, 1}_1}_2 + d -> {5, +, 9}_1 + a -> {1, +, 7, +, 9, +, 10}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-44.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-44.c new file mode 100644 index 00000000000..86308138d37 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-44.c @@ -0,0 +1,39 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +/* That's a reduced testcase of one of my favourite simulation programs. + This is also known under the name: "Newton's falling apple". + The general version is known under the name: "the N-body simulation problem". + + The physics terminology is the best to describe the scalar evolution algorithm: + - first determine the initial conditions of the system, + - then analyze its evolution. +*/ + +double Newton_s_apple () +{ + /* Initial conditions. */ + double g = -10.0; + double speed_z = 0; + double altitude = 3000; + double delta_t = 0.1; + double total_time = 0; + + /* Laws of evolution. */ + while (altitude > 0.0) + { + speed_z += g * delta_t; + altitude += speed_z * delta_t; + total_time += delta_t; + } + + return total_time; +} + +/* + speed_z -> {0.0, +, -1.0e+0}_1 + altitude -> {3.0e+3, +, {(0.0 + -1.0e+0) * 1.00000000000000005551115123125782702118158340454e-1, +, -1.0e+0 * 1.00000000000000005551115123125782702118158340454e-1}_1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-45.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-45.c new file mode 100644 index 00000000000..40f09a236f3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-45.c @@ -0,0 +1,45 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +/* That's a reduced testcase of one of my favourite simulation programs. + This is also known under the name: "Newton's falling apple". + The general version is known under the name: "the N-body simulation problem". + + The physics terminology is the best to describe the scalar evolution algorithm: + - first determine the initial conditions of the system, + - then analyze its evolution. +*/ + +double Newton_s_apple () +{ + /* Initial conditions. */ + double g = 10.0; + double speed_z = 0; + double altitude = 3000; + double delta_t = 0.1; + double total_time = 0; + + /* Laws of evolution. */ + while (altitude > 0.0) + { + speed_z += g * delta_t; + altitude -= speed_z * delta_t; + total_time += delta_t; + } + + return total_time; +} + +/* + speed_z -> {0.0, +, 1.0e+0}_1 + altitude -> {3.0e+3, +, {(0.0 + 1.0e+0) * 1.00000000000000005551115123125782702118158340454e-1 * -1, +, 1.0e+0 * 1.00000000000000005551115123125782702118158340454e-1 * -1}_1}_1 + + When computing evolutions in the "symbolic as long as possible" strategy, + the analyzer extracts only the following: + + altitude -> {3.0e+3, +, T.2_11 * -1}_1 + +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-46.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-46.c new file mode 100644 index 00000000000..b97d6f87fab --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-46.c @@ -0,0 +1,19 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int +foo (int i, + int precision) +{ + i = precision - i - 1; + + /* At this point the analyzer is confused by the initialisation of "i". + It keeps the initial condition under a symbolic form: "i_1". */ + + while (--i); +} + +/* i -> {i_1, +, -1}_1 */ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-47.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-47.c new file mode 100644 index 00000000000..bd5afc50b7e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-47.c @@ -0,0 +1,36 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int +foo (int unknown_parm, int a, int b) +{ + int p; + + if (unknown_parm) + { + p = a + 2; + } + else + { + p = b + 1; + } + + /* At this point the initial condition of "p" is unknown. + In this case, the analyzer has to keep the initial condition under a symbolic form. */ + + while (p) + p--; + +} + +/* + p -> {p_1, +, -1}_1 + + or, when the Value Range Propagation does its work: + + p -> {[MIN_EXPR <p_4, p_6>, MAX_EXPR <p_4, p_6>], +, -1}_1 + +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-48.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-48.c new file mode 100644 index 00000000000..fbd3c98bb29 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-48.c @@ -0,0 +1,30 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int +foo (int *c) +{ + int i; + int j = 10; + + for (i = 0; i < 5; i++) + { + for (j = 10;; j--) + { + if (j == 0) + break; + + *(c + j) = *(c + j) - 1; + } + } + + return j; +} + +/* + j -> {10, +, -1}_2 + i -> {0, +, 1}_1 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-49.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-49.c new file mode 100644 index 00000000000..413758aa6f6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-49.c @@ -0,0 +1,26 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int +foo (int *c) +{ + int i = 0; + int j = 10; + + while (1) + { + if (i == j) + break; + + i++; + j--; + } + + return j; +} + +/* i -> {0, +, 1}_1 */ +/* j -> {10, +, -1}_1 */ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-50.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-50.c new file mode 100644 index 00000000000..b3ea5b5dfb9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-50.c @@ -0,0 +1,27 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int +foo (int *c) +{ + int i = 0; + int j = 10; + + while (1) + { + /* This case exercises the number of iterations detector for + {0, +, 1}_1 == {10, +, -1}_1 + */ + if (i == j) + break; + + i++; + j--; + } + + return j; +} + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-51.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-51.c new file mode 100644 index 00000000000..c0a7f51f8ff --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-51.c @@ -0,0 +1,23 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int +foo (int j) +{ + int i = 0; + int temp_var; + + while (i < 100) + { + /* This exercises the analyzer on strongly connected + components: here "i -> temp_var -> i". */ + temp_var = i + j; + i = temp_var + 2; + } + + return i; +} + +/* FIXME. */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-52.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-52.c new file mode 100644 index 00000000000..94f43e3d51a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-52.c @@ -0,0 +1,23 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +int bar (int); + +int foo (void) +{ + int a; + int parm = 11; + int x; + int c[100]; + + for (a = parm; a < 50; a++) + { + /* Array access functions have to be analyzed. */ + x = a + 5; + c[x] = c[x+2] + c[x-1]; + } + bar (c[1]); +} + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-52.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-52.c.ddall new file mode 100644 index 00000000000..91beef19c92 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-52.c.ddall @@ -0,0 +1,49 @@ +;; APPLE LOCAL file lno +;; Function foo (foo) + +(Data Dep (A = 0, B = 2): + (subscript 0: + access_fn_A: {18, +, 1}_1 + access_fn_B: {16, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {2, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(2 +) + ) +) +(Data Dep (A = 1, B = 2): + (subscript 0: + access_fn_A: {15, +, 1}_1 + access_fn_B: {16, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {1, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(-1 +) + ) +) +(Data Dep (A = 2, B = 2): + (subscript 0: + access_fn_A: {16, +, 1}_1 + access_fn_B: {16, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) + ) +) +(Data Dep (A = 2, B = 3): (no dependence) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-53.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-53.c new file mode 100644 index 00000000000..3933c21e360 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-53.c @@ -0,0 +1,129 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details " } */ + +#define N 16 + +void fbar (float *); +void ibar (int *); +void sbar (short *); + +/* Should be vectorized */ + +foo (int n) +{ + float a[N+1]; + float b[N]; + float c[N]; + float d[N]; + int ia[N]; + int ib[N]; + int ic[N]; + double da[N]; + double db[N]; + short sa[N]; + short sb[N]; + short sc[N]; + int i,j; + int diff = 0; + char cb[N]; + char cc[N]; + char image[N][N]; + char block[N][N]; + + /* Not vetorizable yet (unknown loop bound). */ + for (i = 0; i < n; i++){ + a[i] = b[i]; + } + fbar (a); + + /* Vectorizable. */ + for (i = 0; i < N; i++){ + a[i] = b[i]; + } + fbar (a); + + /* Not Vectorizable (mode not supported). */ + for (i = 0; i < N; i++){ + da[i] = db[i]; + } + fbar (a); + + /* Not vetorizable yet (constant assignment). */ + for (i = 0; i < N; i++){ + a[i] = 5; + } + fbar (a); + + /* Vectorizable. */ + for (i = 0; i < N; i++){ + a[i] = b[i] + c[i] + d[i]; + } + fbar (a); + + /* Vectorizable. */ + for (i = 0; i < N; i++){ + a[i] = b[i] * c[i]; + } + fbar (a); + + /* Vectorizable. */ + for (i = 0; i < N/2; i++){ + a[i] = b[i+N/2] * c[i+N/2] - b[i] * c[i]; + d[i] = b[i] * c[i+N/2] + b[i+N/2] * c[i]; + } + fbar (a); + + /* Not vetorizable yet (too conservative dependence test). */ + for (i = 0; i < N/2; i++){ + a[i] = b[i+N/2] * c[i+N/2] - b[i] * c[i]; + a[i+N/2] = b[i] * c[i+N/2] + b[i+N/2] * c[i]; + } + fbar (a); + + /* Not vetorizable yet (access pattern). */ + for (i = 0; i < N/2; i++){ + a[i] = b[2*i+1] * c[2*i+1] - b[2*i] * c[2*i]; + d[i] = b[2*i] * c[2*i+1] + b[2*i+1] * c[2*i]; + } + fbar (a); + + /* Not vetorizable yet (too conservative dependence test; access pattern). */ + for (i = 0; i < N/2; i++){ + a[2*i] = b[2*i+1] * c[2*i+1] - b[2*i] * c[2*i]; + a[2*i+1] = b[2*i] * c[2*i+1] + b[2*i+1] * c[2*i]; + } + fbar (a); + + /* Not vetorizable yet (no support for integer mult). */ + for (i = 0; i < N; i++){ + ia[i] = ib[i] * ic[i]; + } + ibar (ia); + + /* Vectorizable. */ + for (i = 0; i < N; i++){ + a[i] = b[i] + c[i]; + d[i] = b[i] + c[i]; + ia[i] = ib[i] + ic[i]; + } + ibar (ia); + fbar (a); + fbar (d); + + /* Not vectorizable yet (two types with different nunits in vector). */ + for (i = 0; i < N; i++){ + ia[i] = ib[i] + ic[i]; + sa[i] = sb[i] + sc[i]; + } + ibar (ia); + sbar (sa); + + /* Not vetorizable yet (too conservative dependence test). */ + for (i = 0; i < N; i++){ + a[i] = b[i] + c[i]; + a[i+1] = b[i] + c[i]; + } + fbar (a); +} + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-54.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-54.c new file mode 100644 index 00000000000..1f64eb4e22d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-54.c @@ -0,0 +1,34 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int main(void) +{ + int a = 5; + int b = 6; + int c = 20; + + while (a <= 100) + { + int i; + + a = b; + for (i = 0; i <= 12; i++) + { + a++; + } + b = b + c; + } +} + +/* This example has been distilled from Pattern1 that cannot be + handled: "Big steps, small steps" from the ICS'01 paper "Monotonic + Evolution" by Peng Wu. + + The analyzer has to detect the following evolution functions: + i -> {0, +, 1}_2 + b -> {6, +, 20}_1 + a -> {{6, +, 20}_1, +, 1}_2 +*/ + +/* FIXME. */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-55.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-55.c new file mode 100644 index 00000000000..4c53f8f6688 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-55.c @@ -0,0 +1,17 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest-details" } */ + +int main(int argc) +{ + int I, J; + const int N = 30; + const int M = 40; + for (J = argc; J < N; J += 3) + { + for (I = J; I < M; I++) + { + printf ("%d %d\n", I, J); + } + } +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-56.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-56.c new file mode 100644 index 00000000000..80d896d2a02 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-56.c @@ -0,0 +1,22 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -ftree-elim-checks -fdump-tree-elck-details -fdump-tree-optimized" } */ + +void remove_me (void); + +int main (void) +{ + int a = -100; + int b = 0; + int c = 3; + + for (a = 0; a < 100; a++) + { + b = b + 3; + if (b != c) + remove_me (); + c = c + 3; + } +} + +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-57.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-57.c new file mode 100644 index 00000000000..ae2de4c80ed --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-57.c @@ -0,0 +1,24 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -ftree-elim-checks -fdump-tree-elck-details -fdump-tree-optimized" } */ + +void remove_me (void); + +int main (void) +{ + int a = -100; + int b = 0; + int c = 3; + + for (a = 0; a < 100; a++) + { + if (b > c) + remove_me (); + b = b + 2; + c = c + 3; + } +} + + +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-58.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-58.c new file mode 100644 index 00000000000..a66ab94481f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-58.c @@ -0,0 +1,23 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -ftree-elim-checks -fdump-tree-elck-details -fdump-tree-optimized" } */ + +void remove_me (void); + +int main (void) +{ + int a, b; + int N = 100; + + a = 0; + b = 0; + while (a < N) + { + if (b >= 5*N - 4) + remove_me (); + a++; + b+=5; + } +} + +/* { dg-final { scan-tree-dump-times "remove_me" 0 "optimized"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-59.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-59.c new file mode 100644 index 00000000000..e65e52825fe --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-59.c @@ -0,0 +1,19 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest " } */ + +extern int foo (float A[100][200]); + +int bar () +{ + int i, j; + float A[100][200]; + + for (i=0; i<5; i++) + for (j=0; j<5; j++) + A[i][j] = A[i+1][j]; + foo (A); + return A[1][2]; +} + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-59.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-59.c.ddall new file mode 100644 index 00000000000..2b2235a44c3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-59.c.ddall @@ -0,0 +1,80 @@ +;; APPLE LOCAL file lno +;; Function bar (bar) + +(Data Dep (A = 0, B = 1): + (subscript 0: + access_fn_A: {0, +, 1}_2 + access_fn_B: {0, +, 1}_2 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {1, +, 1}_1 + access_fn_B: {0, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {1, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(1 +) + ) +) +(Data Dep (A = 1, B = 1): + (subscript 0: + access_fn_A: {0, +, 1}_2 + access_fn_B: {0, +, 1}_2 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_2 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {0, +, 1}_1 + access_fn_B: {0, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) +(0 +) + ) +) +(Data Dep (A = 1, B = 2): + (subscript 0: + access_fn_A: {0, +, 1}_2 + access_fn_B: 2 + iterations_that_access_an_element_twice_in_A: 2 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + + (subscript 1: + access_fn_A: {0, +, 1}_1 + access_fn_B: 1 + iterations_that_access_an_element_twice_in_A: 1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: 0 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(-2 +) +(-1 +) + ) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-60.c b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-60.c new file mode 100644 index 00000000000..7dd730ce9bc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-60.c @@ -0,0 +1,22 @@ +/* APPLE LOCAL file lno */ +/* { dg-do compile } */ +/* { dg-options "-O1 -floop-test -fdump-tree-lptest " } */ + +extern int foo (float A[100]); + +int bar () +{ + int i, j; + float A[100]; + + for (i=0; i<5; i++) + { + A[i * 3] = i + 3; + A[i + 7] = i; + } + + foo (A); + return A[1]; +} + +/* { dg-final { diff-tree-dumps "ddall" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-60.c.ddall b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-60.c.ddall new file mode 100644 index 00000000000..88b906fd0f7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/ssa-chrec-60.c.ddall @@ -0,0 +1,51 @@ +;; APPLE LOCAL file lno +;; Function bar (bar) + +(Data Dep (A = 0, B = 0): + (subscript 0: + access_fn_A: {0, +, 3}_1 + access_fn_B: {0, +, 3}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) + ) +) +(Data Dep (A = 0, B = 1): + (subscript 0: + access_fn_A: {0, +, 3}_1 + access_fn_B: {7, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {3, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {2, +, 3}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +([-oo, +oo] +) + ) +) +(Data Dep (A = 0, B = 2): (no dependence) +) +(Data Dep (A = 1, B = 1): + (subscript 0: + access_fn_A: {7, +, 1}_1 + access_fn_B: {7, +, 1}_1 + iterations_that_access_an_element_twice_in_A: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_A: [-oo, +oo] + iterations_that_access_an_element_twice_in_B: {0, +, 1}_1 + last_iteration_that_access_an_element_twice_in_B: [-oo, +oo] + ) + (Distance Vector: +(0 +) + ) +) +(Data Dep (A = 1, B = 2): (no dependence) +) + + diff --git a/gcc/testsuite/gcc.dg/tree-ssa-chrec/tree-ssa-scev.exp b/gcc/testsuite/gcc.dg/tree-ssa-chrec/tree-ssa-scev.exp new file mode 100644 index 00000000000..46fcf02054f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa-chrec/tree-ssa-scev.exp @@ -0,0 +1,36 @@ +# APPLE LOCAL file lno +# Copyright (C) 1997 Free Software Foundation, Inc. + +# This program is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 2 of the License, or +# (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +# GCC testsuite that uses the `dg.exp' driver. + +# Load support procs. +load_lib gcc-dg.exp + +# If a testcase doesn't have special options, use these. +global DEFAULT_CFLAGS +if ![info exists DEFAULT_CFLAGS] then { + set DEFAULT_CFLAGS " -ansi -pedantic-errors" +} + +# Initialize `dg'. +dg-init + +# Main loop. +dg-runtest [lsort [glob -nocomplain $srcdir/$subdir/*.\[cS\]]] "" $DEFAULT_CFLAGS + +# All done. +dg-finish |