Re: [Graphite] Fix type problems in loop ivs.

[Richard Guenther <richard dot guenther at gmail dot com>]

On Fri, Mar 5, 2010 at 3:14 PM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
> Hi,
>
> I would like to commit this patch that fixes the loop iv type problems in
> graphite.
>
> This resolves two P1 bug reports without any regressions in the graphite.exp
> testsuite neither on 64 nor on 32 bit linux. Only two test cases in libgomp
> changed, as autopar generates for these files an iv where we cannot yet
> prove, that it can be handled safely in graphite. This can be enhanced later on.
>
> The patch was bootstrapped on
> Linux tobias 2.6.33 #4 SMP PREEMPT Mon Mar 1 12:59:44 CET 2010 x86_64 Intel(R)
> Core(TM) i5 CPU M 520 @ 2.40GHz GenuineIntel GNU/Linux
>
> Linux tobias 2.6.33 #4 SMP PREEMPT Mon Mar 1 12:59:44 CET 2010 i686 Intel(R)
> Core(TM) i5 CPU M 520 @ 2.40GHz GenuineIntel GNU/Linux
>
> Also tested dealII on 64bit with -O2, which failed before.
>
> OK for trunk, if it passes the automatic spec 2006 tests on graphite branch?

This variant looks reasonable.  It's still ugly, but well - I hope
somebody is working on enhancing CLooG for a nicer fix.

The patch is ok if it passes testing.

Thanks,
Richard.

> Tobias
>
> PS: Thanks Richi, for proposing "fold_convert (sizetype, name)" for the conversion
> from pointers.
>
> Fix pr42644.
> Fix pr42130 (dealII).
>
> 2010-03-03 ?Tobias Grosser ?<grosser@fim.uni-passau.de>
>
> ? ? ? ?* gcc/graphite-clast-to-gimple.c (clast_to_gcc_expression): Also
> ? ? ? ?handle conversions from pointer to integers.
> ? ? ? ?(gcc_type_for_cloog_iv): Choose the smalles signed integer as an
> ? ? ? ?induction variable, to be able to work with code generated by
> ? ? ? ?CLooG.
> ? ? ? ?* gcc/graphite-sese-to-poly.c (scop_ivs_can_be_represented): New.
> ? ? ? ?(build_poly_scop): Bail out if we cannot codegen a loop.
> ? ? ? ?* gcc/testsuite/gcc.dg/graphite/id-18.c: New.
> ? ? ? ?* gcc/testsuite/gcc.dg/graphite/run-id-pr42644.c: New.
> ? ? ? ?* libgomp/testsuite/libgomp.graphite/force-parallel-1.c: Adjust.
> ? ? ? ?* libgomp/testsuite/libgomp.graphite/force-parallel-2.c: Adjust.
> ---
> ?gcc/graphite-clast-to-gimple.c ? ? ? ? ? ? ? ? ? ? | ? 67 +++++++++++++++++--
> ?gcc/graphite-sese-to-poly.c ? ? ? ? ? ? ? ? ? ? ? ?| ? 36 +++++++++++
> ?gcc/testsuite/gcc.dg/graphite/id-18.c ? ? ? ? ? ? ?| ? ?7 ++
> ?gcc/testsuite/gcc.dg/graphite/run-id-pr42644.c ? ? | ? 32 +++++++++
> ?.../testsuite/libgomp.graphite/force-parallel-1.c ?| ? ?2 +-
> ?.../testsuite/libgomp.graphite/force-parallel-2.c ?| ? ?2 +-
> ?6 files changed, 137 insertions(+), 9 deletions(-)
> ?create mode 100644 gcc/testsuite/gcc.dg/graphite/id-18.c
> ?create mode 100644 gcc/testsuite/gcc.dg/graphite/run-id-pr42644.c
>
> diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
> index 909392a..6ce01d5 100644
> --- a/gcc/graphite-clast-to-gimple.c
> +++ b/gcc/graphite-clast-to-gimple.c
> @@ -282,14 +282,24 @@ clast_to_gcc_expression (tree type, struct clast_expr *e,
> ? ? ? ? ? ? ?{
> ? ? ? ? ? ? ? ?tree name = clast_name_to_gcc (t->var, region, newivs,
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? newivs_index, params_index);
> - ? ? ? ? ? ? ? return fold_convert (type, name);
> +
> + ? ? ? ? ? ? ? if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
> + ? ? ? ? ? ? ? ? name = fold_convert (sizetype, name);
> +
> + ? ? ? ? ? ? ? name = fold_convert (type, name);
> + ? ? ? ? ? ? ? return name;
> ? ? ? ? ? ? ?}
>
> ? ? ? ? ? ?else if (value_mone_p (t->val))
> ? ? ? ? ? ? ?{
> ? ? ? ? ? ? ? ?tree name = clast_name_to_gcc (t->var, region, newivs,
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? newivs_index, params_index);
> +
> + ? ? ? ? ? ? ? if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
> + ? ? ? ? ? ? ? ? name = fold_convert (sizetype, name);
> +
> ? ? ? ? ? ? ? ?name = fold_convert (type, name);
> +
> ? ? ? ? ? ? ? ?return fold_build1 (NEGATE_EXPR, type, name);
> ? ? ? ? ? ? ?}
> ? ? ? ? ? ?else
> @@ -297,7 +307,12 @@ clast_to_gcc_expression (tree type, struct clast_expr *e,
> ? ? ? ? ? ? ? ?tree name = clast_name_to_gcc (t->var, region, newivs,
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? newivs_index, params_index);
> ? ? ? ? ? ? ? ?tree cst = gmp_cst_to_tree (type, t->val);
> +
> + ? ? ? ? ? ? ? if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
> + ? ? ? ? ? ? ? ? name = fold_convert (sizetype, name);
> +
> ? ? ? ? ? ? ? ?name = fold_convert (type, name);
> +
> ? ? ? ? ? ? ? ?if (!POINTER_TYPE_P (type))
> ? ? ? ? ? ? ? ? ?return fold_build2 (MULT_EXPR, type, cst, name);
>
> @@ -532,9 +547,16 @@ clast_get_body_of_loop (struct clast_stmt *stmt)
> ? gcc_unreachable ();
> ?}
>
> -/* Given a CLOOG_IV, returns the type that it should have in GCC land.
> - ? If the information is not available, i.e. in the case one of the
> - ? transforms created the loop, just return integer_type_node. ?*/
> +/* Given a CLOOG_IV, return the type that CLOOG_IV should have in GCC
> + ? land. ?The selected type is big enough to include the original loop
> + ? iteration variable, but signed to work with the subtractions CLooG
> + ? may have introduced. ?If such a type is not available, we fail.
> +
> + ? TODO: Do not always return long_long, but the smallest possible
> + ? type, that still holds the original type.
> +
> + ? TODO: Get the types using CLooG instead. ?This enables further
> + ? optimizations, but needs CLooG support. ?*/
>
> ?static tree
> ?gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
> @@ -546,9 +568,40 @@ gcc_type_for_cloog_iv (const char *cloog_iv, gimple_bb_p gbb)
> ? slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
>
> ? if (slot && *slot)
> - ? ?return ((ivtype_map_elt) *slot)->type;
> + ? ?{
> + ? ? ?tree type = ((ivtype_map_elt) *slot)->type;
> + ? ? ?int type_precision = TYPE_PRECISION (type);
> +
> + ? ? ?/* Find the smallest signed type possible. ?*/
> + ? ? ?if (!TYPE_UNSIGNED (type))
> + ? ? ? {
> + ? ? ? ? if (type_precision <= TYPE_PRECISION (integer_type_node))
> + ? ? ? ? ? return integer_type_node;
> +
> + ? ? ? ? if (type_precision <= TYPE_PRECISION (long_integer_type_node))
> + ? ? ? ? ? return long_integer_type_node;
> +
> + ? ? ? ? if (type_precision <= TYPE_PRECISION (long_long_integer_type_node))
> + ? ? ? ? ? return long_long_integer_type_node;
> +
> + ? ? ? ? gcc_unreachable ();
> + ? ? ? }
> +
> + ? ? ?if (type_precision < TYPE_PRECISION (integer_type_node))
> + ? ? ? return integer_type_node;
> +
> + ? ? ?if (type_precision < TYPE_PRECISION (long_integer_type_node))
> + ? ? ? return long_integer_type_node;
> +
> + ? ? ?if (type_precision < TYPE_PRECISION (long_long_integer_type_node))
> + ? ? ? return long_long_integer_type_node;
> +
> + ? ? ?/* There is no signed type available, that is large enough to hold the
> + ? ? ? ?original value. ?*/
> + ? ? ?gcc_unreachable ();
> + ? ?}
>
> - ?return integer_type_node;
> + ?return long_long_integer_type_node;
> ?}
>
> ?/* Returns the induction variable for the loop that gets translated to
> @@ -1046,7 +1099,7 @@ compute_cloog_iv_types_1 (poly_bb_p pbb, struct clast_user_stmt *user_stmt)
> ? ? ? if (slot && !*slot)
> ? ? ? ?{
> ? ? ? ? ?tree oldiv = pbb_to_depth_to_oldiv (pbb, index);
> - ? ? ? ? tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
> + ? ? ? ? tree type = TREE_TYPE (oldiv);
> ? ? ? ? ?*slot = new_ivtype_map_elt (tmp.cloog_iv, type);
> ? ? ? ?}
> ? ? }
> diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
> index 3ee431f..279a905 100644
> --- a/gcc/graphite-sese-to-poly.c
> +++ b/gcc/graphite-sese-to-poly.c
> @@ -2893,6 +2893,38 @@ scop_canonicalize_loops (scop_p scop)
> ? ? ? graphite_loop_normal_form (loop);
> ?}
>
> +/* Can all ivs be represented by a signed integer?
> + ? As CLooG might generate negative values in its expressions, signed loop ivs
> + ? are required in the backend. */
> +static bool
> +scop_ivs_can_be_represented (scop_p scop)
> +{
> + ?loop_iterator li;
> + ?loop_p loop;
> +
> + ?FOR_EACH_LOOP (li, loop, 0)
> + ? ?{
> + ? ? ?tree type;
> + ? ? ?int precision;
> +
> + ? ? ?if (!loop_in_sese_p (loop, SCOP_REGION (scop)))
> + ? ? ? continue;
> +
> + ? ? ?if (!loop->single_iv)
> + ? ? ? continue;
> +
> + ? ? ?type = TREE_TYPE(loop->single_iv);
> + ? ? ?precision = TYPE_PRECISION (type);
> +
> + ? ? ?if (TYPE_UNSIGNED (type)
> + ? ? ? ? && precision >= TYPE_PRECISION (long_long_integer_type_node))
> + ? ? ? return false;
> + ? ?}
> +
> + ?return true;
> +}
> +
> +
> ?/* Builds the polyhedral representation for a SESE region. ?*/
>
> ?bool
> @@ -2915,6 +2947,10 @@ build_poly_scop (scop_p scop)
> ? ? return false;
>
> ? scop_canonicalize_loops (scop);
> +
> + ?if (!scop_ivs_can_be_represented (scop))
> + ? ?return false;
> +
> ? build_sese_loop_nests (region);
> ? build_sese_conditions (region);
> ? find_scop_parameters (scop);
> diff --git a/gcc/testsuite/gcc.dg/graphite/id-18.c b/gcc/testsuite/gcc.dg/graphite/id-18.c
> new file mode 100644
> index 0000000..77628fa
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/id-18.c
> @@ -0,0 +1,7 @@
> +long do_hash (const char * lo, const char * hi)
> +{
> + ? ? ? int val = 0;
> + ? ? ? for (; lo < hi; ++lo)
> + ? ? ? ? ? ? ? val = *lo;
> + ? ? ? return val;
> +}
> diff --git a/gcc/testsuite/gcc.dg/graphite/run-id-pr42644.c b/gcc/testsuite/gcc.dg/graphite/run-id-pr42644.c
> new file mode 100644
> index 0000000..2e90064
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/graphite/run-id-pr42644.c
> @@ -0,0 +1,32 @@
> +/* Testcase extracted from test 183.equake in SPEC CPU2000. ?*/
> +double Ke[2], ds[2];
> +
> +void foo(double Ke[2], int i, double ds[], ?int column)
> +{
> + ?double tt, ts;
> + ?int j;
> +
> + ?for (j = 0; j < 2; j++)
> + ? ?{
> + ? ? ?++column;
> + ? ? ?ts = ds[i];
> + ? ? ?if (i == j)
> + ? ? ? tt = 123;
> + ? ? ?else
> + ? ? ? tt = 0;
> + ? ? ?Ke[column] = Ke[column] + ts + tt;
> + ? ?}
> +}
> +
> +int
> +main ()
> +{
> + ?int i, j;
> +
> + ?ds[0] = 1.0;
> + ?ds[1] = 1.0;
> +
> + ?foo(Ke, 0, ds, -1);
> +
> + ?return (int) Ke[0] != 124;
> +}
> diff --git a/libgomp/testsuite/libgomp.graphite/force-parallel-1.c b/libgomp/testsuite/libgomp.graphite/force-parallel-1.c
> index 7f043d8..1ad4b41 100644
> --- a/libgomp/testsuite/libgomp.graphite/force-parallel-1.c
> +++ b/libgomp/testsuite/libgomp.graphite/force-parallel-1.c
> @@ -23,7 +23,7 @@ int main(void)
> ?}
>
> ?/* Check that parallel code generation part make the right answer. ?*/
> -/* { dg-final { scan-tree-dump-times "1 loops carried no dependency" 2 "graphite" } } */
> +/* { dg-final { scan-tree-dump-times "1 loops carried no dependency" 1 "graphite" } } */
> ?/* { dg-final { cleanup-tree-dump "graphite" } } */
> ?/* { dg-final { scan-tree-dump-times "loopfn" 5 "optimized" } } */
> ?/* { dg-final { cleanup-tree-dump "parloops" } } */
> diff --git a/libgomp/testsuite/libgomp.graphite/force-parallel-2.c b/libgomp/testsuite/libgomp.graphite/force-parallel-2.c
> index 03d8236..1ce0feb 100644
> --- a/libgomp/testsuite/libgomp.graphite/force-parallel-2.c
> +++ b/libgomp/testsuite/libgomp.graphite/force-parallel-2.c
> @@ -23,7 +23,7 @@ int main(void)
> ?}
>
> ?/* Check that parallel code generation part make the right answer. ?*/
> -/* { dg-final { scan-tree-dump-times "2 loops carried no dependency" 2 "graphite" } } */
> +/* { dg-final { scan-tree-dump-times "2 loops carried no dependency" 1 "graphite" } } */
> ?/* { dg-final { cleanup-tree-dump "graphite" } } */
> ?/* { dg-final { scan-tree-dump-times "loopfn" 5 "optimized" } } */
> ?/* { dg-final { cleanup-tree-dump "parloops" } } */
> --
> 1.6.4.4
>
>