This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch][graphite] Fix PR43306, fix leslie3d and gamess compile time, fix documentation
- From: Sebastian Pop <sebpop at gmail dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, gcc-graphite <gcc-graphite at googlegroups dot com>
- Date: Tue, 9 Mar 2010 13:53:02 -0600
- Subject: [patch][graphite] Fix PR43306, fix leslie3d and gamess compile time, fix documentation
Hi,
I committed these patches to the Graphite branch for further testing.
For 43306, we had a problem in the analysis of data reference
accesses: basically we were allowing {0, +, {0, +, 4}_1}_2 as a simple
access function, but the translation of this scev into a polyhedral
representation fails as this is not a linear access function: the
stride in loop_2 is not constant, it has an evolution in loop_1. Note
that {{0, +, 4}_1, +, 1}_2 is a linear access function as the strides
in loop_1 and in loop_2 are constant.
To fix leslie3d and gamess from the CPU2006 benchmarks, I added a
limitation to the number of parameters that are allowed in a scop. From
now on the scops with more than 10 parameters will be discarded. This
limit can be changed using a parameter. We should also improve the
detection of scop parameters to detect relations between parameters.
I also have added a parameter for the number of basic blocks per
function that we currently have hardly fixed to 100.
I added the documentation for the undocumented loop blocking factor.
Sebastian Pop
--
AMD / Open Source Compiler Engineering / GNU Tools
From 76a3eb27130a455760121ad2fa4b82777b45a779 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 9 Mar 2010 10:40:14 -0600
Subject: [PATCH 1/5] Limit the number of parameters per SCoP.
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
* graphite-sese-to-poly.c (build_poly_scop): Limit scops following
the number of parameters in the scop. Use as an upper bound
PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS.
* params.def (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS): Declared.
* doc/invoke.texi: Document it.
---
gcc/ChangeLog.graphite | 8 ++++++++
gcc/doc/invoke.texi | 4 ++++
gcc/graphite-sese-to-poly.c | 5 +++++
gcc/params.def | 7 +++++++
4 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 163e05e..0bec105 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,11 @@
+2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+
+ * graphite-sese-to-poly.c (build_poly_scop): Limit scops following
+ the number of parameters in the scop. Use as an upper bound
+ PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS.
+ * params.def (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS): Declared.
+ * doc/invoke.texi: Document it.
+
2010-03-05 Sebastian Pop <sebastian.pop@amd.com>
* graphite-sese-to-poly.c (add_param_constraints): Use
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index f661001..393ae5f 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -8456,6 +8456,10 @@ parameters only when their cumulative size is less or equal to
@option{ipa-sra-ptr-growth-factor} times the size of the original
pointer parameter.
+@item graphite-max-nb-scop-params
+To avoid exponential effects in the Graphite loop transforms, the
+number of parameters in a SCoP is bounded by 10.
+
@end table
@end table
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 11bddf8..ae4a083 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2937,6 +2937,7 @@ build_poly_scop (scop_p scop)
{
sese region = SCOP_REGION (scop);
sbitmap reductions = sbitmap_alloc (last_basic_block * 2);
+ graphite_dim_t max_dim;
sbitmap_zero (reductions);
rewrite_commutative_reductions_out_of_ssa (region, reductions);
@@ -2960,6 +2961,10 @@ build_poly_scop (scop_p scop)
build_sese_conditions (region);
find_scop_parameters (scop);
+ max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
+ if (scop_nb_params (scop) > max_dim)
+ return false;
+
build_scop_iteration_domain (scop);
build_scop_context (scop);
diff --git a/gcc/params.def b/gcc/params.def
index 21dcb44..45fb916 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -740,6 +740,13 @@ DEFPARAM (PARAM_LOOP_BLOCK_TILE_SIZE,
"size of tiles for loop blocking",
51, 0, 0)
+/* Maximal number of parameters that we allow in a SCoP. */
+
+DEFPARAM (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS,
+ "graphite-max-nb-scop-params",
+ "maximal number of parameters in a SCoP",
+ 10, 0, 0)
+
/* Avoid doing loop invariant motion on very large loops. */
DEFPARAM (PARAM_LOOP_INVARIANT_MAX_BBS_IN_LOOP,
--
1.6.3.3
From 91d731cf3c9043dd51386abeb6796d94d273c059 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 9 Mar 2010 10:43:11 -0600
Subject: [PATCH 2/5] Make build_poly_scop not return a bool.
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
* graphite-sese-to-poly.c (build_poly_scop): Do not return bool.
* graphite-sese-to-poly.h (build_poly_scop): Same.
---
gcc/ChangeLog.graphite | 5 +++++
gcc/graphite-sese-to-poly.c | 14 +++++++-------
gcc/graphite-sese-to-poly.h | 2 +-
3 files changed, 13 insertions(+), 8 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 0bec105..52fd1ec 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,10 @@
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite-sese-to-poly.c (build_poly_scop): Do not return bool.
+ * graphite-sese-to-poly.h (build_poly_scop): Same.
+
+2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-sese-to-poly.c (build_poly_scop): Limit scops following
the number of parameters in the scop. Use as an upper bound
PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS.
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index ae4a083..75be56d 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -2932,7 +2932,7 @@ scop_ivs_can_be_represented (scop_p scop)
/* Builds the polyhedral representation for a SESE region. */
-bool
+void
build_poly_scop (scop_p scop)
{
sese region = SCOP_REGION (scop);
@@ -2950,12 +2950,11 @@ build_poly_scop (scop_p scop)
sense to optimize a scop containing only PBBs that do not belong
to any loops. */
if (nb_pbbs_in_loops (scop) == 0)
- return false;
+ return;
scop_canonicalize_loops (scop);
-
if (!scop_ivs_can_be_represented (scop))
- return false;
+ return;
build_sese_loop_nests (region);
build_sese_conditions (region);
@@ -2963,7 +2962,7 @@ build_poly_scop (scop_p scop)
max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
if (scop_nb_params (scop) > max_dim)
- return false;
+ return;
build_scop_iteration_domain (scop);
build_scop_context (scop);
@@ -2972,9 +2971,10 @@ build_poly_scop (scop_p scop)
scop_to_lst (scop);
build_scop_scattering (scop);
build_scop_drs (scop);
- POLY_SCOP_P (scop) = true;
- return true;
+ /* This SCoP has been translated to the polyhedral
+ representation. */
+ POLY_SCOP_P (scop) = true;
}
/* Always return false. Exercise the scop_to_clast function. */
diff --git a/gcc/graphite-sese-to-poly.h b/gcc/graphite-sese-to-poly.h
index 0737c49..3213471 100644
--- a/gcc/graphite-sese-to-poly.h
+++ b/gcc/graphite-sese-to-poly.h
@@ -28,7 +28,7 @@ struct base_alias_pair
int *alias_set;
};
-bool build_poly_scop (scop_p);
+void build_poly_scop (scop_p);
void check_poly_representation (scop_p);
#endif
--
1.6.3.3
From 1ff8635c30a993a7cd70824562d43f8580bdbb39 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 9 Mar 2010 10:50:36 -0600
Subject: [PATCH 3/5] Add PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION.
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
* graphite.c (graphite_initialize): To bound the number of bbs per
function, use PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION.
* params.def (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION): Declared.
* doc/invoke.texi: Document it.
---
gcc/ChangeLog.graphite | 7 +++++++
gcc/doc/invoke.texi | 5 +++++
gcc/graphite.c | 2 +-
gcc/params.def | 7 +++++++
4 files changed, 20 insertions(+), 1 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 52fd1ec..1d93b46 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,12 @@
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+ * graphite.c (graphite_initialize): To bound the number of bbs per
+ function, use PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION.
+ * params.def (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION): Declared.
+ * doc/invoke.texi: Document it.
+
+2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite-sese-to-poly.c (build_poly_scop): Do not return bool.
* graphite-sese-to-poly.h (build_poly_scop): Same.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 393ae5f..7cedbff 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -8460,6 +8460,11 @@ pointer parameter.
To avoid exponential effects in the Graphite loop transforms, the
number of parameters in a SCoP is bounded by 10.
+@item graphite-max-bbs-per-function
+To avoid exponential effects in the detection of SCoPs, the functions
+with more than 100 basic blocks are not handled by the Graphite loop
+transforms.
+
@end table
@end table
diff --git a/gcc/graphite.c b/gcc/graphite.c
index 9e61c00..98c728c 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -203,7 +203,7 @@ graphite_initialize (void)
if (number_of_loops () <= 1
/* FIXME: This limit on the number of basic blocks of a function
should be removed when the SCOP detection is faster. */
- || n_basic_blocks > 100)
+ || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
{
if (dump_file && (dump_flags & TDF_DETAILS))
print_global_statistics (dump_file);
diff --git a/gcc/params.def b/gcc/params.def
index 45fb916..e2e26b6 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -747,6 +747,13 @@ DEFPARAM (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS,
"maximal number of parameters in a SCoP",
10, 0, 0)
+/* Maximal number of basic blocks in the functions analyzed by Graphite. */
+
+DEFPARAM (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION,
+ "graphite-max-bbs-per-function",
+ "maximal number of basic blocks per function to be analyzed by Graphite",
+ 100, 0, 0)
+
/* Avoid doing loop invariant motion on very large loops. */
DEFPARAM (PARAM_LOOP_INVARIANT_MAX_BBS_IN_LOOP,
--
1.6.3.3
From 492adef77950d6851a574d8d480768f50f8c6de4 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 9 Mar 2010 12:58:27 -0600
Subject: [PATCH 4/5] Fix PR43306: correct evolution_function_right_is_integer_cst.
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
PR middle-end/43306
* tree-chrec.c (evolution_function_right_is_integer_cst): CHREC_RIGHT
should be an INTEGER_CST. Also handle CASE_CONVERT.
* gcc.dg/graphite/pr43306.c: New.
---
gcc/ChangeLog.graphite | 7 +++++++
gcc/testsuite/gcc.dg/graphite/pr43306.c | 9 +++++++++
gcc/tree-chrec.c | 12 +++++-------
3 files changed, 21 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/graphite/pr43306.c
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 1d93b46..f65ecb1 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,12 @@
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+ PR middle-end/43306
+ * tree-chrec.c (evolution_function_right_is_integer_cst): CHREC_RIGHT
+ should be an INTEGER_CST. Also handle CASE_CONVERT.
+ * gcc.dg/graphite/pr43306.c: New.
+
+2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+
* graphite.c (graphite_initialize): To bound the number of bbs per
function, use PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION.
* params.def (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION): Declared.
diff --git a/gcc/testsuite/gcc.dg/graphite/pr43306.c b/gcc/testsuite/gcc.dg/graphite/pr43306.c
new file mode 100644
index 0000000..43195e4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/pr43306.c
@@ -0,0 +1,9 @@
+/* { dg-options "-O1 -fstrict-overflow -fgraphite-identity" } */
+
+void foo(int x[])
+{
+ int i, j;
+ for (i = 0; i < 2; i++)
+ for (j = 0; j < 2; j++)
+ x[i] = x[i*j];
+}
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index 18ed4ed..52a3a0c 100644
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -1505,14 +1505,12 @@ evolution_function_right_is_integer_cst (const_tree chrec)
return true;
case POLYNOMIAL_CHREC:
- if (!evolution_function_right_is_integer_cst (CHREC_RIGHT (chrec)))
- return false;
-
- if (TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
- && !evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)))
- return false;
+ return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
+ && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
+ || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
- return true;
+ CASE_CONVERT:
+ return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
default:
return false;
--
1.6.3.3
From 5f4a7dd1c29e4e4f610ee4cb2540e3ecc8e4e31c Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Tue, 9 Mar 2010 13:36:41 -0600
Subject: [PATCH 5/5] Document PARAM_LOOP_BLOCK_TILE_SIZE.
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
* doc/invoke.texi (PARAM_LOOP_BLOCK_TILE_SIZE): Document.
---
gcc/ChangeLog.graphite | 4 ++++
gcc/doc/invoke.texi | 25 +++++++++++++++++--------
2 files changed, 21 insertions(+), 8 deletions(-)
diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index f65ecb1..c35d10c 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,5 +1,9 @@
2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+ * doc/invoke.texi (PARAM_LOOP_BLOCK_TILE_SIZE): Document.
+
+2010-03-09 Sebastian Pop <sebastian.pop@amd.com>
+
PR middle-end/43306
* tree-chrec.c (evolution_function_right_is_integer_cst): CHREC_RIGHT
should be an INTEGER_CST. Also handle CASE_CONVERT.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 7cedbff..78deec5 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -6642,7 +6642,9 @@ Graphite loop transformation infrastructure.
Perform loop strip mining transformations on loops. Strip mining
splits a loop into two nested loops. The outer loop has strides
equal to the strip size and the inner loop has strides of the
-original loop within a strip. For example, given a loop like:
+original loop within a strip. The strip length can be changed
+using the @option{loop-block-tile-size} parameter. For example,
+given a loop like:
@smallexample
DO I = 1, N
A(I) = A(I) + C
@@ -6650,8 +6652,8 @@ ENDDO
@end smallexample
loop strip mining will transform the loop as if the user had written:
@smallexample
-DO II = 1, N, 4
- DO I = II, min (II + 3, N)
+DO II = 1, N, 51
+ DO I = II, min (II + 50, N)
A(I) = A(I) + C
ENDDO
ENDDO
@@ -6664,7 +6666,9 @@ enable the Graphite loop transformation infrastructure.
@item -floop-block
Perform loop blocking transformations on loops. Blocking strip mines
each loop in the loop nest such that the memory accesses of the
-element loops fit inside caches. For example, given a loop like:
+element loops fit inside caches. The strip length can be changed
+using the @option{loop-block-tile-size} parameter. For example, given
+a loop like:
@smallexample
DO I = 1, N
DO J = 1, M
@@ -6674,10 +6678,10 @@ ENDDO
@end smallexample
loop blocking will transform the loop as if the user had written:
@smallexample
-DO II = 1, N, 64
- DO JJ = 1, M, 64
- DO I = II, min (II + 63, N)
- DO J = JJ, min (JJ + 63, M)
+DO II = 1, N, 51
+ DO JJ = 1, M, 51
+ DO I = II, min (II + 50, N)
+ DO J = JJ, min (JJ + 50, M)
A(J, I) = B(I) + C(J)
ENDDO
ENDDO
@@ -8465,6 +8469,11 @@ To avoid exponential effects in the detection of SCoPs, the functions
with more than 100 basic blocks are not handled by the Graphite loop
transforms.
+@item loop-block-tile-size
+The default factor for the loop blocking or strip mining transforms,
+enabled with @option{-floop-block} or @option{-floop-strip-mine}, is
+51.
+
@end table
@end table
--
1.6.3.3