[patch] for PR 18529
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Mon Nov 22 20:27:00 GMT 2004
Hello,
> > here is the new version of the patch, with subst renamed and the
> > a == b && something transformation moved out of fold.
>
> Many thanks, this is *much* better. tree_simplify_using_condition
> is clearly the correct place for this, and allows even stronger
> optimization than your original changes to "fold".
>
> My only remaining comments are
> (1) that for the time being, "simplify_replace_tree" can be kept local
> to tree-ssa-loop-niter.c, and made static. This also avoids adding
> the prototype to tree.h. If at some point in the future, someone
> else requires this functionality, it can be moved to fold-const.c
> and prototyped in tree.h, so that it can be shared.
more likely, when someone else requires this functionality, he will
write it from scratch, since he just will not expect this function to
be hidden in tree-ssa-loop-niter.c (happened to me several times :-( ).
Anyway, done.
> (2) The comments in my previous mail's about in the inefficient use
> of operand_equal_p in fold_to_nonsharp_ineq_using_bound. You should
> either call "fold" for strong equivalence, or alternatively continue
> to use "weak" equivalence, but with the more efficient implememtation
> suggested previously.
Done.
Bootstrapped & regtested on i686 and ia64.
Zdenek
PR tree-optimization/18529
* fold-const.c (fold_to_nonsharp_ineq_using_bound): New function.
(simple_operand_p): Use STRIP_NOPS. Consider SSA names simple.
(fold): Call fold_to_nonsharp_ineq_using_bound.
* tree-ssa-loop-niter.c (simplify_replace_tree): New function.
(number_of_iterations_cond): Fold the expressions before futher
processing.
(tree_simplify_using_condition): Handle case when cond or expr is
an EQ_EXPR specially.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.475
diff -c -3 -p -r1.475 fold-const.c
*** fold-const.c 18 Nov 2004 12:09:36 -0000 1.475
--- fold-const.c 22 Nov 2004 16:41:07 -0000
*************** static int
*** 3424,3436 ****
simple_operand_p (tree exp)
{
/* Strip any conversions that don't change the machine mode. */
! while ((TREE_CODE (exp) == NOP_EXPR
! || TREE_CODE (exp) == CONVERT_EXPR)
! && (TYPE_MODE (TREE_TYPE (exp))
! == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
! exp = TREE_OPERAND (exp, 0);
return (CONSTANT_CLASS_P (exp)
|| (DECL_P (exp)
&& ! TREE_ADDRESSABLE (exp)
&& ! TREE_THIS_VOLATILE (exp)
--- 3424,3433 ----
simple_operand_p (tree exp)
{
/* Strip any conversions that don't change the machine mode. */
! STRIP_NOPS (exp);
return (CONSTANT_CLASS_P (exp)
+ || TREE_CODE (exp) == SSA_NAME
|| (DECL_P (exp)
&& ! TREE_ADDRESSABLE (exp)
&& ! TREE_THIS_VOLATILE (exp)
*************** try_move_mult_to_index (tree type, enum
*** 6180,6185 ****
--- 6177,6227 ----
return build1 (ADDR_EXPR, type, ret);
}
+
+ /* Fold A < X && A + 1 > Y to A < X && A >= Y. Normally A + 1 > Y
+ means A >= Y && A != MAX, but in this case we know that
+ A < X <= MAX. INEQ is A + 1 > Y, BOUND is A < X. */
+
+ static tree
+ fold_to_nonsharp_ineq_using_bound (tree ineq, tree bound)
+ {
+ tree a, typea, type = TREE_TYPE (ineq), a1, diff, y;
+
+ if (TREE_CODE (bound) == LT_EXPR)
+ a = TREE_OPERAND (bound, 0);
+ else if (TREE_CODE (bound) == GT_EXPR)
+ a = TREE_OPERAND (bound, 1);
+ else
+ return NULL_TREE;
+
+ typea = TREE_TYPE (a);
+ if (!INTEGRAL_TYPE_P (typea)
+ && !POINTER_TYPE_P (typea))
+ return NULL_TREE;
+
+ if (TREE_CODE (ineq) == LT_EXPR)
+ {
+ a1 = TREE_OPERAND (ineq, 1);
+ y = TREE_OPERAND (ineq, 0);
+ }
+ else if (TREE_CODE (ineq) == GT_EXPR)
+ {
+ a1 = TREE_OPERAND (ineq, 0);
+ y = TREE_OPERAND (ineq, 1);
+ }
+ else
+ return NULL_TREE;
+
+ if (TREE_TYPE (a1) != typea)
+ return NULL_TREE;
+
+ diff = fold (build2 (MINUS_EXPR, typea, a1, a));
+ if (!integer_onep (diff))
+ return NULL_TREE;
+
+ return fold (build2 (GE_EXPR, type, a, y));
+ }
+
/* Perform constant folding and related simplification of EXPR.
The related simplifications include x*1 => x, x*0 => 0, etc.,
and application of the associative law.
*************** fold (tree expr)
*** 8023,8028 ****
--- 8065,8086 ----
&& operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
return omit_one_operand (type, integer_zero_node, arg0);
+ /* A < X && A + 1 > Y ==> A < X && A >= Y. Normally A + 1 > Y
+ means A >= Y && A != MAX, but in this case we know that
+ A < X <= MAX. */
+
+ if (!TREE_SIDE_EFFECTS (arg0)
+ && !TREE_SIDE_EFFECTS (arg1))
+ {
+ tem = fold_to_nonsharp_ineq_using_bound (arg0, arg1);
+ if (tem)
+ return fold (build2 (code, type, tem, arg1));
+
+ tem = fold_to_nonsharp_ineq_using_bound (arg1, arg0);
+ if (tem)
+ return fold (build2 (code, type, arg0, tem));
+ }
+
truth_andor:
/* We only do these simplifications if we are optimizing. */
if (!optimize)
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.16
diff -c -3 -p -r2.16 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 15 Nov 2004 00:18:33 -0000 2.16
--- tree-ssa-loop-niter.c 22 Nov 2004 16:41:07 -0000
*************** number_of_iterations_cond (tree type, tr
*** 372,383 ****
if (zero_p (step0))
{
! base0 = build2 (PLUS_EXPR, type, base0, delta);
base0 = fold (build2 (MINUS_EXPR, type, base0, step));
}
else
{
! base1 = build2 (MINUS_EXPR, type, base1, delta);
base1 = fold (build2 (PLUS_EXPR, type, base1, step));
}
--- 372,383 ----
if (zero_p (step0))
{
! base0 = fold (build2 (PLUS_EXPR, type, base0, delta));
base0 = fold (build2 (MINUS_EXPR, type, base0, step));
}
else
{
! base1 = fold (build2 (MINUS_EXPR, type, base1, delta));
base1 = fold (build2 (PLUS_EXPR, type, base1, step));
}
*************** simplify_using_outer_evolutions (struct
*** 555,560 ****
--- 555,595 ----
return expr;
}
+ /* Substitute NEW for OLD in EXPR and fold the result. */
+
+ static tree
+ simplify_replace_tree (tree expr, tree old, tree new)
+ {
+ unsigned i, n;
+ tree ret = NULL_TREE, e, se;
+
+ if (!expr)
+ return NULL_TREE;
+
+ if (expr == old
+ || operand_equal_p (expr, old, 0))
+ return unshare_expr (new);
+
+ if (!EXPR_P (expr))
+ return expr;
+
+ n = TREE_CODE_LENGTH (TREE_CODE (expr));
+ for (i = 0; i < n; i++)
+ {
+ e = TREE_OPERAND (expr, i);
+ se = simplify_replace_tree (e, old, new);
+ if (e == se)
+ continue;
+
+ if (!ret)
+ ret = copy_node (expr);
+
+ TREE_OPERAND (ret, i) = se;
+ }
+
+ return (ret ? fold (ret) : expr);
+ }
+
/* Tries to simplify EXPR using the condition COND. Returns the simplified
expression (or EXPR unchanged, if no simplification was possible).*/
*************** tree_simplify_using_condition (tree cond
*** 603,608 ****
--- 638,688 ----
return expr;
}
+ /* In case COND is equality, we may be able to simplify EXPR by copy/constant
+ propagation, and vice versa. Fold does not handle this, since it is
+ considered too expensive. */
+ if (TREE_CODE (cond) == EQ_EXPR)
+ {
+ e0 = TREE_OPERAND (cond, 0);
+ e1 = TREE_OPERAND (cond, 1);
+
+ /* We know that e0 == e1. Check whether we cannot simplify expr
+ using this fact. */
+ e = simplify_replace_tree (expr, e0, e1);
+ if (zero_p (e) || nonzero_p (e))
+ return e;
+
+ e = simplify_replace_tree (expr, e1, e0);
+ if (zero_p (e) || nonzero_p (e))
+ return e;
+ }
+ if (TREE_CODE (expr) == EQ_EXPR)
+ {
+ e0 = TREE_OPERAND (expr, 0);
+ e1 = TREE_OPERAND (expr, 1);
+
+ /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
+ e = simplify_replace_tree (cond, e0, e1);
+ if (zero_p (e))
+ return e;
+ e = simplify_replace_tree (cond, e1, e0);
+ if (zero_p (e))
+ return e;
+ }
+ if (TREE_CODE (expr) == NE_EXPR)
+ {
+ e0 = TREE_OPERAND (expr, 0);
+ e1 = TREE_OPERAND (expr, 1);
+
+ /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
+ e = simplify_replace_tree (cond, e0, e1);
+ if (zero_p (e))
+ return boolean_true_node;
+ e = simplify_replace_tree (cond, e1, e0);
+ if (zero_p (e))
+ return boolean_true_node;
+ }
+
/* Check whether COND ==> EXPR. */
notcond = invert_truthvalue (cond);
e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
More information about the Gcc-patches
mailing list