From 7e2ac86c349ecfe90cc98f24230659136806fefa Mon Sep 17 00:00:00 2001 From: Zdenek Dvorak Date: Wed, 10 Jan 2007 01:44:26 +0100 Subject: [PATCH] re PR middle-end/30322 (((-i-1) + i) +1) is turned into ~i + (i+1) and never into 0 on the tree level) PR tree-optimization/30322 * tree-ssa-loop-ivopts.c (fold_affine_expr, iv_value): Removed. (cand_value_at): Return the value as aff_tree. (may_eliminate_iv): Convert the bound from aff_tree to tree. * tree-affine.c (aff_combination_add_cst, aff_combination_add_product, aff_combination_mult): New functions. (aff_combination_add): Use aff_combination_add_cst. (aff_combination_convert): Allow conversions to a wider type. (tree_to_aff_combination): Handle BIT_NOT_EXPR. * tree-affine.h (aff_combination_mult): Declare. * gcc.dg/tree-ssa/loop-21.c: New test. From-SVN: r120630 --- gcc/ChangeLog | 13 ++++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/tree-ssa/loop-21.c | 17 +++++ gcc/tree-affine.c | 89 +++++++++++++++++++++++-- gcc/tree-affine.h | 1 + gcc/tree-ssa-loop-ivopts.c | 53 +++++---------- 6 files changed, 138 insertions(+), 40 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-21.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c0c883874a63..b85f8bbbe86f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +2007-01-09 Zdenek Dvorak + + PR tree-optimization/30322 + * tree-ssa-loop-ivopts.c (fold_affine_expr, iv_value): Removed. + (cand_value_at): Return the value as aff_tree. + (may_eliminate_iv): Convert the bound from aff_tree to tree. + * tree-affine.c (aff_combination_add_cst, aff_combination_add_product, + aff_combination_mult): New functions. + (aff_combination_add): Use aff_combination_add_cst. + (aff_combination_convert): Allow conversions to a wider type. + (tree_to_aff_combination): Handle BIT_NOT_EXPR. + * tree-affine.h (aff_combination_mult): Declare. + 2007-01-09 Carlos O'Donell * doc/tm.texi: Update documentation to reflect reality of exec diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 4d097ea1e017..2e2ebd5c9759 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2007-01-09 Zdenek Dvorak + + PR tree-optimization/30322 + * gcc.dg/tree-ssa/loop-21.c: New test. + 2007-01-08 Geoffrey Keating * g++.dg/rtti/darwin-builtin-linkage.C: New. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-21.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-21.c new file mode 100644 index 000000000000..59a17cb5e7f6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-21.c @@ -0,0 +1,17 @@ +/* PR tree-optimization/30322 */ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-final_cleanup" } */ + +extern void op( int, int); +void foo(int f0, int f1, int e0, int e1) +{ + int i0, i1; + + for (i1 = f1; i1 <= e1; ++i1) + for (i0 = f0; i0 <= e0; ++i0) + op(i0, i1); +} + +/* { dg-final { scan-tree-dump-times "~" 0 "final_cleanup" } } */ +/* { dg-final { cleanup-tree-dump "final_cleanup" } } */ diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index 762e82e0b4a5..43b251ddd90d 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -180,6 +180,14 @@ aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale) comb->rest = elt; } +/* Adds CST to C. */ + +static void +aff_combination_add_cst (aff_tree *c, double_int cst) +{ + c->offset = double_int_ext_for_comb (double_int_add (c->offset, cst), c); +} + /* Adds COMB2 to COMB1. */ void @@ -187,9 +195,7 @@ aff_combination_add (aff_tree *comb1, aff_tree *comb2) { unsigned i; - comb1->offset - = double_int_ext_for_comb (double_int_add (comb1->offset, comb2->offset), - comb1); + aff_combination_add_cst (comb1, comb2->offset); for (i = 0; i < comb2->n; i++) aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef); if (comb2->rest) @@ -204,7 +210,13 @@ aff_combination_convert (aff_tree *comb, tree type) unsigned i, j; tree comb_type = comb->type; - gcc_assert (TYPE_PRECISION (type) <= TYPE_PRECISION (comb_type)); + if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type)) + { + tree val = fold_convert (type, aff_combination_to_tree (comb)); + tree_to_aff_combination (val, type, comb); + return; + } + comb->type = type; if (comb->rest) comb->rest = fold_convert (type, comb->rest); @@ -276,6 +288,13 @@ tree_to_aff_combination (tree expr, tree type, aff_tree *comb) aff_combination_scale (comb, double_int_minus_one); return; + case BIT_NOT_EXPR: + /* ~x = -x - 1 */ + tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); + aff_combination_scale (comb, double_int_minus_one); + aff_combination_add_cst (comb, double_int_minus_one); + return; + case ADDR_EXPR: core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, &toffset, &mode, &unsignedp, &volatilep, @@ -412,3 +431,65 @@ aff_combination_remove_elt (aff_tree *comb, unsigned m) comb->n++; } } + +/* Adds C * COEF * VAL to R. VAL may be NULL, in that case only + C * COEF is added to R. */ + + +static void +aff_combination_add_product (aff_tree *c, double_int coef, tree val, + aff_tree *r) +{ + unsigned i; + tree aval, type; + + for (i = 0; i < c->n; i++) + { + aval = c->elts[i].val; + if (val) + { + type = TREE_TYPE (aval); + aval = fold_build2 (MULT_EXPR, type, aval, + fold_convert (type, val)); + } + + aff_combination_add_elt (r, aval, + double_int_mul (coef, c->elts[i].coef)); + } + + if (c->rest) + { + aval = c->rest; + if (val) + { + type = TREE_TYPE (aval); + aval = fold_build2 (MULT_EXPR, type, aval, + fold_convert (type, val)); + } + + aff_combination_add_elt (r, aval, coef); + } + + if (val) + aff_combination_add_elt (r, val, + double_int_mul (coef, c->offset)); + else + aff_combination_add_cst (r, double_int_mul (coef, c->offset)); +} + +/* Multiplies C1 by C2, storing the result to R */ + +void +aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) +{ + unsigned i; + gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type)); + + aff_combination_zero (r, c1->type); + + for (i = 0; i < c2->n; i++) + aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); + if (c2->rest) + aff_combination_add_product (c1, double_int_one, c2->rest, r); + aff_combination_add_product (c1, c2->offset, NULL, r); +} diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h index b83a501c8684..51af99acec26 100644 --- a/gcc/tree-affine.h +++ b/gcc/tree-affine.h @@ -62,6 +62,7 @@ double_int double_int_ext_for_comb (double_int, aff_tree *); void aff_combination_const (aff_tree *, tree, double_int); void aff_combination_elt (aff_tree *, tree, tree); void aff_combination_scale (aff_tree *, double_int); +void aff_combination_mult (aff_tree *, aff_tree *, aff_tree *); void aff_combination_add (aff_tree *, aff_tree *); void aff_combination_add_elt (aff_tree *, tree, double_int); void aff_combination_remove_elt (aff_tree *, unsigned); diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 411cad22544c..a11165d7b851 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -2565,21 +2565,6 @@ constant_multiple_of (tree top, tree bot, double_int *mul) } } -/* Folds EXPR using the affine expressions framework. */ - -static tree -fold_affine_expr (tree expr) -{ - tree type = TREE_TYPE (expr); - struct affine_tree_combination comb; - - if (TYPE_PRECISION (type) > HOST_BITS_PER_WIDE_INT) - return expr; - - tree_to_aff_combination (expr, type, &comb); - return aff_combination_to_tree (&comb); -} - /* If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the same precision that is at least as wide as the precision of TYPE, stores BA to A and BB to B, and returns the type of BA. Otherwise, returns the @@ -3557,32 +3542,26 @@ determine_use_iv_cost_address (struct ivopts_data *data, return cost != INFTY; } -/* Computes value of induction variable IV in iteration NITER. */ +/* Computes value of candidate CAND at position AT in iteration NITER, and + stores it to VAL. */ -static tree -iv_value (struct iv *iv, tree niter) +static void +cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter, + aff_tree *val) { - tree val; + aff_tree step, delta, nit; + struct iv *iv = cand->iv; tree type = TREE_TYPE (iv->base); - niter = fold_convert (type, niter); - val = fold_build2 (MULT_EXPR, type, iv->step, niter); - - return fold_build2 (PLUS_EXPR, type, iv->base, val); -} - -/* Computes value of candidate CAND at position AT in iteration NITER. */ - -static tree -cand_value_at (struct loop *loop, struct iv_cand *cand, tree at, tree niter) -{ - tree val = iv_value (cand->iv, niter); - tree type = TREE_TYPE (cand->iv->base); - + tree_to_aff_combination (iv->step, type, &step); + tree_to_aff_combination (niter, TREE_TYPE (niter), &nit); + aff_combination_convert (&nit, type); + aff_combination_mult (&nit, &step, &delta); if (stmt_after_increment (loop, cand, at)) - val = fold_build2 (PLUS_EXPR, type, val, cand->iv->step); + aff_combination_add (&delta, &step); - return val; + tree_to_aff_combination (iv->base, type, val); + aff_combination_add (val, &delta); } /* Returns period of induction variable iv. */ @@ -3637,6 +3616,7 @@ may_eliminate_iv (struct ivopts_data *data, tree nit, nit_type; tree wider_type, period, per_type; struct loop *loop = data->current_loop; + aff_tree bnd; if (TREE_CODE (cand->iv->step) != INTEGER_CST) return false; @@ -3681,7 +3661,8 @@ may_eliminate_iv (struct ivopts_data *data, fold_convert (wider_type, nit)))) return false; - *bound = fold_affine_expr (cand_value_at (loop, cand, use->stmt, nit)); + cand_value_at (loop, cand, use->stmt, nit, &bnd); + *bound = aff_combination_to_tree (&bnd); return true; } -- 2.43.5