This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for second problem in PR 18431
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 13 Nov 2004 21:13:25 +0100
- Subject: [patch] for second problem in PR 18431
Hello,
a poor code is produced in 64-bit for the pointer version of the
testcase. The reason is that we are unable to detect that index cannot
overflow and consequently we do not perform strength reduction.
But in fact even without the information about array bounds we can show
that there is no overflow. We only need to persuade fold to optimize
the following expression (type of var is int):
var <= 0 || ((long unsigned) (unsigned) (var - 1) < MAX_UNSIGNED_INT)
Without the patch, this gets simplified to
var <= 0 || ((unsigned) (var - 1) != MAX_UNSIGNED_INT)
The fold_sign_changed_comparison part of the patch ensures that this
gets optimized to
var <= 0 || (var - 1 != -1)
which fold is able to simplify to true.
fold_widened_comparison part splits the original functionality from
fold, and extends it a bit in case one of the operands is a constant --
the patch is a merge from lno-branch, so I just left this minor
improvement in it, although it is irrelevant for the PR).
The piece of the patch in associate_trees ensures that the expression
described above is produced; without it
var <= 0 || ((long unsigned) (unsigned) (var - 1 + 0) < MAX_UNSIGNED_INT)
is produced instead.
Bootstrapped & regtested on ia64, x86_64 and i686.
Zdenek
PR tree-optimization/18431
* fold-const.c (associate_trees): Do not produce x + 0.
(fold_widened_comparison, fold_sign_changed_comparison): New functions.
(fold): Use them.
* tree-ssa-loop-niter.c (upper_bound_in_type, lower_bound_in_type):
Export.
* tree.h (upper_bound_in_type, lower_bound_in_type): Declare.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.473
diff -c -3 -p -r1.473 fold-const.c
*** fold-const.c 10 Nov 2004 20:49:54 -0000 1.473
--- fold-const.c 13 Nov 2004 15:33:37 -0000
*************** associate_trees (tree t1, tree t2, enum
*** 1267,1273 ****
--- 1267,1281 ----
else if (TREE_CODE (t2) == NEGATE_EXPR)
return build2 (MINUS_EXPR, type, fold_convert (type, t1),
fold_convert (type, TREE_OPERAND (t2, 0)));
+ else if (integer_zerop (t2))
+ return fold_convert (type, t1);
}
+ else if (code == MINUS_EXPR)
+ {
+ if (integer_zerop (t2))
+ return fold_convert (type, t1);
+ }
+
return build2 (code, type, fold_convert (type, t1),
fold_convert (type, t2));
}
*************** tree_swap_operands_p (tree arg0, tree ar
*** 5972,5977 ****
--- 5980,6106 ----
return 0;
}
+ /* Fold comparison ARG0 CODE ARG1 (with result in TYPE), where
+ ARG0 is extended to a wider type. */
+
+ static tree
+ fold_widened_comparison (enum tree_code code, tree type, tree arg0, tree arg1)
+ {
+ tree arg0_unw = get_unwidened (arg0, NULL_TREE);
+ tree arg1_unw;
+ tree shorter_type, outer_type;
+ tree min, max;
+ bool above, below;
+
+ if (arg0_unw == arg0)
+ return NULL_TREE;
+ shorter_type = TREE_TYPE (arg0_unw);
+
+ arg1_unw = get_unwidened (arg1, shorter_type);
+ if (!arg1_unw)
+ return NULL_TREE;
+
+ /* If possible, express the comparison in the shorter mode. */
+ if ((code == EQ_EXPR || code == NE_EXPR
+ || TYPE_UNSIGNED (TREE_TYPE (arg0)) == TYPE_UNSIGNED (shorter_type))
+ && (TREE_TYPE (arg1_unw) == shorter_type
+ || (TREE_CODE (arg1_unw) == INTEGER_CST
+ && int_fits_type_p (arg1_unw, shorter_type))))
+ return fold (build (code, type, arg0_unw,
+ fold_convert (shorter_type, arg1_unw)));
+
+ if (TREE_CODE (arg1_unw) != INTEGER_CST)
+ return NULL_TREE;
+
+ /* If we are comparing with the integer that does not fit into the range
+ of the shorter type, the result is known. */
+ outer_type = TREE_TYPE (arg1_unw);
+ min = lower_bound_in_type (outer_type, shorter_type);
+ max = upper_bound_in_type (outer_type, shorter_type);
+
+ above = integer_nonzerop (fold_relational_const (LT_EXPR, type,
+ max, arg1_unw));
+ below = integer_nonzerop (fold_relational_const (LT_EXPR, type,
+ arg1_unw, min));
+
+ switch (code)
+ {
+ case EQ_EXPR:
+ if (above || below)
+ return constant_boolean_node (false, type);
+ break;
+
+ case NE_EXPR:
+ if (above || below)
+ return constant_boolean_node (true, type);
+ break;
+
+ case LT_EXPR:
+ case LE_EXPR:
+ if (above)
+ return constant_boolean_node (true, type);
+ else if (below)
+ return constant_boolean_node (false, type);;
+
+ case GT_EXPR:
+ case GE_EXPR:
+ if (above)
+ return constant_boolean_node (false, type);
+ else if (below)
+ return constant_boolean_node (true, type);;
+
+ default:
+ break;
+ }
+
+ return NULL_TREE;
+ }
+
+ /* Fold comparison ARG0 CODE ARG1 (with result in TYPE), where for
+ ARG0 just the signedness is changed. */
+
+ static tree
+ fold_sign_changed_comparison (enum tree_code code, tree type,
+ tree arg0, tree arg1)
+ {
+ tree arg0_inner;
+ tree inner_type, outer_type;
+ int ovflw, cst_ovflw;
+
+ if (TREE_CODE (arg0) != NOP_EXPR)
+ return NULL_TREE;
+
+ outer_type = TREE_TYPE (arg0);
+ arg0_inner = TREE_OPERAND (arg0, 0);
+ inner_type = TREE_TYPE (arg0_inner);
+
+ if (TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
+ return NULL_TREE;
+
+ if (TREE_CODE (arg1) != INTEGER_CST
+ && !(TREE_CODE (arg1) == NOP_EXPR
+ && TREE_TYPE (TREE_OPERAND (arg1, 0)) == inner_type))
+ return NULL_TREE;
+
+ if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
+ && code != NE_EXPR
+ && code != EQ_EXPR)
+ return NULL_TREE;
+
+ ovflw = TREE_OVERFLOW (arg1);
+ if (TREE_CODE (arg1) == INTEGER_CST)
+ cst_ovflw = TREE_CONSTANT_OVERFLOW (arg1);
+ else
+ cst_ovflw = ovflw;
+
+ arg1 = fold_convert (inner_type, arg1);
+ TREE_OVERFLOW (arg1) = ovflw;
+ if (TREE_CODE (arg1) == INTEGER_CST)
+ TREE_CONSTANT_OVERFLOW (arg1) = cst_ovflw;
+
+ return fold (build (code, type, arg0_inner, arg1));
+ }
+
/* Tries to replace &a[idx] CODE s * delta with &a[idx CODE delta], if s is
step of the array. TYPE is the type of the expression. ADDR is the address.
MULT is the multiplicative expression. If the function succeeds, the new
*************** fold (tree expr)
*** 8392,8413 ****
return fold (build2 (code, type,
TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
- /* If we are widening one operand of an integer comparison,
- see if the other operand is similarly being widened. Perhaps we
- can do the comparison in the narrower type. */
else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
! && TREE_CODE (arg0) == NOP_EXPR
! && (tem = get_unwidened (arg0, NULL_TREE)) != arg0
! && (code == EQ_EXPR || code == NE_EXPR
! || TYPE_UNSIGNED (TREE_TYPE (arg0))
! == TYPE_UNSIGNED (TREE_TYPE (tem)))
! && (t1 = get_unwidened (arg1, TREE_TYPE (tem))) != 0
! && (TREE_TYPE (t1) == TREE_TYPE (tem)
! || (TREE_CODE (t1) == INTEGER_CST
! && TREE_CODE (TREE_TYPE (tem)) == INTEGER_TYPE
! && int_fits_type_p (t1, TREE_TYPE (tem)))))
! return fold (build2 (code, type, tem,
! fold_convert (TREE_TYPE (tem), t1)));
/* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
constant, we can simplify it. */
--- 8521,8541 ----
return fold (build2 (code, type,
TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1)));
else if (TREE_CODE (TREE_TYPE (arg0)) == INTEGER_TYPE
! && TREE_CODE (arg0) == NOP_EXPR)
! {
! /* If we are widening one operand of an integer comparison,
! see if the other operand is similarly being widened. Perhaps we
! can do the comparison in the narrower type. */
! tem = fold_widened_comparison (code, type, arg0, arg1);
! if (tem)
! return tem;
!
! /* Or if we are changing signedness. */
! tem = fold_sign_changed_comparison (code, type, arg0, arg1);
! if (tem)
! return tem;
! }
/* If this is comparing a constant with a MIN_EXPR or a MAX_EXPR of a
constant, we can simplify it. */
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.15
diff -c -3 -p -r2.15 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 8 Nov 2004 22:38:12 -0000 2.15
--- tree-ssa-loop-niter.c 13 Nov 2004 15:33:37 -0000
*************** compare_trees (tree a, tree b)
*** 1106,1112 ****
/* Returns the largest value obtainable by casting something in INNER type to
OUTER type. */
! static tree
upper_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
--- 1106,1112 ----
/* Returns the largest value obtainable by casting something in INNER type to
OUTER type. */
! tree
upper_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
*************** upper_bound_in_type (tree outer, tree in
*** 1152,1158 ****
/* Returns the smallest value obtainable by casting something in INNER type to
OUTER type. */
! static tree
lower_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
--- 1152,1158 ----
/* Returns the smallest value obtainable by casting something in INNER type to
OUTER type. */
! tree
lower_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.651
diff -c -3 -p -r1.651 tree.h
*** tree.h 11 Nov 2004 23:15:48 -0000 1.651
--- tree.h 13 Nov 2004 15:33:37 -0000
*************** extern bool thread_through_all_blocks (v
*** 3924,3927 ****
--- 3924,3931 ----
/* In tree-gimple.c. */
extern tree get_base_address (tree t);
+ /* In tree-ssa-loop-niter.c. */
+ tree upper_bound_in_type (tree, tree);
+ tree lower_bound_in_type (tree, tree);
+
#endif /* GCC_TREE_H */