This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Simplify/improve fold_Nary_to_constant
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Jeff Law <law at redhat dot com>
- Date: Sun, 3 Apr 2005 19:13:26 -0600 (MDT)
- Subject: [PATCH] Simplify/improve fold_Nary_to_constant
Now that Kazu has reorganized fold's internal APIs, its possible to
trivially implement fold_binary_to_constant using fold_binary and
fold_unary_to_constant using fold_unary. Using the obvious two line
implementations of these functions, avoids creating the tree node
that was the original motiviation for these routines, but also allows
us to catch more optimizations and at the same time reduce the code
duplication.
This patch shrinks fold-const.c by nearly 500 lines (or by over 4%).
Here are some statistics that show that the potential increase in
memory usage, due to constructing a tree that we then ignore, is
negligable:
fold_unary_to_constant is called 31453 times building stage2, stage3
and the libraries of a GCC bootstrap on i686-pc-linux-gnu. Of these,
30222 (96%) result in fold_unary returning a constant, and all of the
remaining 1231 return NULL_TREE. Hence, fold_unary_to_constant never
wastes/leaks memory as every time fold_unary allocates a tree node,
we return it.
fold_binary_to_constant is called 183865 times; in 160301 (87%) of the
time we return a constant, 15727 (9%) fold_binary returns a non-constant
non-NULL tree, and 7837 (4%) of the time fold_binary returns a NULL_TREE.
Hence, during the "hour" of bootstrap we leak approximately 16K tree
nodes. This is a fraction of invert_truthvalue's leakage, for example.
I suspect many of these cases, may be placing constants as the second
operand of commutative operators, which can potentially be avoided...
I'm investigating.
Jeff, what do you think?
2005-04-03 Roger Sayle <roger@eyesopen.com>
* fold-const.c (fold_relational_hi_lo): Delete function and prototype.
(fold_binary): Update comment mentioning fold_relational_hi_lo.
(fold_binary_to_constant): Simplify using fold_binary.
(fold_unary_to_constant): Likewise, simplify using fold_unary.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.552
diff -c -3 -p -r1.552 fold-const.c
*** fold-const.c 1 Apr 2005 14:36:33 -0000 1.552
--- fold-const.c 3 Apr 2005 20:06:10 -0000
*************** static bool reorder_operands_p (tree, tr
*** 133,140 ****
static tree fold_negate_const (tree, tree);
static tree fold_not_const (tree, tree);
static tree fold_relational_const (enum tree_code, tree, tree, tree);
- static tree fold_relational_hi_lo (enum tree_code *, const tree,
- tree *, tree *);
static bool tree_expr_nonzero_p (tree);
/* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
--- 133,138 ----
*************** fold_binary (enum tree_code code, tree t
*** 9003,9012 ****
}
/* Comparisons with the highest or lowest possible integer of
! the specified size will have known values.
!
! This is quite similar to fold_relational_hi_lo, however,
! attempts to share the code have been nothing but trouble. */
{
int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
--- 9001,9007 ----
}
/* Comparisons with the highest or lowest possible integer of
! the specified size will have known values. */
{
int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (arg1)));
*************** tree_expr_nonzero_p (tree t)
*** 10745,10899 ****
return false;
}
- /* See if we are applying CODE, a relational to the highest or lowest
- possible integer of TYPE. If so, then the result is a compile
- time constant. */
-
- static tree
- fold_relational_hi_lo (enum tree_code *code_p, const tree type, tree *op0_p,
- tree *op1_p)
- {
- tree op0 = *op0_p;
- tree op1 = *op1_p;
- enum tree_code code = *code_p;
- int width = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (op1)));
-
- if (TREE_CODE (op1) == INTEGER_CST
- && ! TREE_CONSTANT_OVERFLOW (op1)
- && width <= HOST_BITS_PER_WIDE_INT
- && (INTEGRAL_TYPE_P (TREE_TYPE (op1))
- || POINTER_TYPE_P (TREE_TYPE (op1))))
- {
- unsigned HOST_WIDE_INT signed_max;
- unsigned HOST_WIDE_INT max, min;
-
- signed_max = ((unsigned HOST_WIDE_INT) 1 << (width - 1)) - 1;
-
- if (TYPE_UNSIGNED (TREE_TYPE (op1)))
- {
- max = ((unsigned HOST_WIDE_INT) 2 << (width - 1)) - 1;
- min = 0;
- }
- else
- {
- max = signed_max;
- min = ((unsigned HOST_WIDE_INT) -1 << (width - 1));
- }
-
- if (TREE_INT_CST_HIGH (op1) == 0
- && TREE_INT_CST_LOW (op1) == max)
- switch (code)
- {
- case GT_EXPR:
- return omit_one_operand (type, integer_zero_node, op0);
-
- case GE_EXPR:
- *code_p = EQ_EXPR;
- break;
- case LE_EXPR:
- return omit_one_operand (type, integer_one_node, op0);
-
- case LT_EXPR:
- *code_p = NE_EXPR;
- break;
-
- /* The GE_EXPR and LT_EXPR cases above are not normally
- reached because of previous transformations. */
-
- default:
- break;
- }
- else if (TREE_INT_CST_HIGH (op1) == 0
- && TREE_INT_CST_LOW (op1) == max - 1)
- switch (code)
- {
- case GT_EXPR:
- *code_p = EQ_EXPR;
- *op1_p = const_binop (PLUS_EXPR, op1, integer_one_node, 0);
- break;
- case LE_EXPR:
- *code_p = NE_EXPR;
- *op1_p = const_binop (PLUS_EXPR, op1, integer_one_node, 0);
- break;
- default:
- break;
- }
- else if (TREE_INT_CST_HIGH (op1) == (min ? -1 : 0)
- && TREE_INT_CST_LOW (op1) == min)
- switch (code)
- {
- case LT_EXPR:
- return omit_one_operand (type, integer_zero_node, op0);
-
- case LE_EXPR:
- *code_p = EQ_EXPR;
- break;
-
- case GE_EXPR:
- return omit_one_operand (type, integer_one_node, op0);
-
- case GT_EXPR:
- *code_p = NE_EXPR;
- break;
-
- default:
- break;
- }
- else if (TREE_INT_CST_HIGH (op1) == (min ? -1 : 0)
- && TREE_INT_CST_LOW (op1) == min + 1)
- switch (code)
- {
- case GE_EXPR:
- *code_p = NE_EXPR;
- *op1_p = const_binop (MINUS_EXPR, op1, integer_one_node, 0);
- break;
- case LT_EXPR:
- *code_p = EQ_EXPR;
- *op1_p = const_binop (MINUS_EXPR, op1, integer_one_node, 0);
- break;
- default:
- break;
- }
-
- else if (TREE_INT_CST_HIGH (op1) == 0
- && TREE_INT_CST_LOW (op1) == signed_max
- && TYPE_UNSIGNED (TREE_TYPE (op1))
- /* signed_type does not work on pointer types. */
- && INTEGRAL_TYPE_P (TREE_TYPE (op1)))
- {
- /* The following case also applies to X < signed_max+1
- and X >= signed_max+1 because previous transformations. */
- if (code == LE_EXPR || code == GT_EXPR)
- {
- tree st0, st1, exp, retval;
- st0 = lang_hooks.types.signed_type (TREE_TYPE (op0));
- st1 = lang_hooks.types.signed_type (TREE_TYPE (op1));
-
- exp = build2 (code == LE_EXPR ? GE_EXPR: LT_EXPR,
- type,
- fold_convert (st0, op0),
- fold_convert (st1, integer_zero_node));
-
- retval = fold_binary_to_constant (TREE_CODE (exp),
- TREE_TYPE (exp),
- TREE_OPERAND (exp, 0),
- TREE_OPERAND (exp, 1));
-
- /* If we are in gimple form, then returning EXP would create
- non-gimple expressions. Clearing it is safe and insures
- we do not allow a non-gimple expression to escape. */
- if (in_gimple_form)
- exp = NULL;
-
- return (retval ? retval : exp);
- }
- }
- }
-
- return NULL_TREE;
- }
-
-
/* Given the components of a binary expression CODE, TYPE, OP0 and OP1,
attempt to fold the expression to a constant without modifying TYPE,
OP0 or OP1.
--- 10740,10745 ----
*************** fold_relational_hi_lo (enum tree_code *c
*** 10910,11191 ****
tree
fold_binary_to_constant (enum tree_code code, tree type, tree op0, tree op1)
{
! int wins = 1;
! tree subop0;
! tree subop1;
! tree tem;
!
! /* If this is a commutative operation, and ARG0 is a constant, move it
! to ARG1 to reduce the number of tests below. */
! if (commutative_tree_code (code)
! && (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST))
! {
! tem = op0;
! op0 = op1;
! op1 = tem;
! }
!
! /* If either operand is a complex type, extract its real component. */
! if (TREE_CODE (op0) == COMPLEX_CST)
! subop0 = TREE_REALPART (op0);
! else
! subop0 = op0;
!
! if (TREE_CODE (op1) == COMPLEX_CST)
! subop1 = TREE_REALPART (op1);
! else
! subop1 = op1;
!
! /* Note if either argument is not a real or integer constant.
! With a few exceptions, simplification is limited to cases
! where both arguments are constants. */
! if ((TREE_CODE (subop0) != INTEGER_CST
! && TREE_CODE (subop0) != REAL_CST)
! || (TREE_CODE (subop1) != INTEGER_CST
! && TREE_CODE (subop1) != REAL_CST))
! wins = 0;
!
! switch (code)
! {
! case PLUS_EXPR:
! /* (plus (address) (const_int)) is a constant. */
! if (TREE_CODE (op0) == PLUS_EXPR
! && TREE_CODE (op1) == INTEGER_CST
! && (TREE_CODE (TREE_OPERAND (op0, 0)) == ADDR_EXPR
! || (TREE_CODE (TREE_OPERAND (op0, 0)) == NOP_EXPR
! && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (op0, 0), 0))
! == ADDR_EXPR)))
! && TREE_CODE (TREE_OPERAND (op0, 1)) == INTEGER_CST)
! {
! return build2 (PLUS_EXPR, type, TREE_OPERAND (op0, 0),
! const_binop (PLUS_EXPR, op1,
! TREE_OPERAND (op0, 1), 0));
! }
! case BIT_XOR_EXPR:
!
! binary:
! if (!wins)
! return NULL_TREE;
!
! /* Both arguments are constants. Simplify. */
! tem = const_binop (code, op0, op1, 0);
! if (tem != NULL_TREE)
! {
! /* The return value should always have the same type as
! the original expression. */
! if (TREE_TYPE (tem) != type)
! tem = fold_convert (type, tem);
!
! return tem;
! }
! return NULL_TREE;
!
! case MINUS_EXPR:
! /* Fold &x - &x. This can happen from &x.foo - &x.
! This is unsafe for certain floats even in non-IEEE formats.
! In IEEE, it is unsafe because it does wrong for NaNs.
! Also note that operand_equal_p is always false if an
! operand is volatile. */
! if (! FLOAT_TYPE_P (type) && operand_equal_p (op0, op1, 0))
! return fold_convert (type, integer_zero_node);
!
! goto binary;
!
! case MULT_EXPR:
! case BIT_AND_EXPR:
! /* Special case multiplication or bitwise AND where one argument
! is zero. */
! if (! FLOAT_TYPE_P (type) && integer_zerop (op1))
! return omit_one_operand (type, op1, op0);
! else
! if (!HONOR_NANS (TYPE_MODE (TREE_TYPE (op0)))
! && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
! && real_zerop (op1))
! return omit_one_operand (type, op1, op0);
!
! goto binary;
!
! case BIT_IOR_EXPR:
! /* Special case when we know the result will be all ones. */
! if (integer_all_onesp (op1))
! return omit_one_operand (type, op1, op0);
!
! goto binary;
!
! case TRUNC_DIV_EXPR:
! case ROUND_DIV_EXPR:
! case FLOOR_DIV_EXPR:
! case CEIL_DIV_EXPR:
! case EXACT_DIV_EXPR:
! case TRUNC_MOD_EXPR:
! case ROUND_MOD_EXPR:
! case FLOOR_MOD_EXPR:
! case CEIL_MOD_EXPR:
! case RDIV_EXPR:
! /* Division by zero is undefined. */
! if (integer_zerop (op1))
! return NULL_TREE;
!
! if (TREE_CODE (op1) == REAL_CST
! && !MODE_HAS_INFINITIES (TYPE_MODE (TREE_TYPE (op1)))
! && real_zerop (op1))
! return NULL_TREE;
!
! goto binary;
!
! case MIN_EXPR:
! if (INTEGRAL_TYPE_P (type)
! && operand_equal_p (op1, TYPE_MIN_VALUE (type), OEP_ONLY_CONST))
! return omit_one_operand (type, op1, op0);
!
! goto binary;
!
! case MAX_EXPR:
! if (INTEGRAL_TYPE_P (type)
! && TYPE_MAX_VALUE (type)
! && operand_equal_p (op1, TYPE_MAX_VALUE (type), OEP_ONLY_CONST))
! return omit_one_operand (type, op1, op0);
!
! goto binary;
!
! case RSHIFT_EXPR:
! /* Optimize -1 >> x for arithmetic right shifts. */
! if (integer_all_onesp (op0) && ! TYPE_UNSIGNED (type))
! return omit_one_operand (type, op0, op1);
! /* ... fall through ... */
!
! case LSHIFT_EXPR:
! if (integer_zerop (op0))
! return omit_one_operand (type, op0, op1);
!
! /* Since negative shift count is not well-defined, don't
! try to compute it in the compiler. */
! if (TREE_CODE (op1) == INTEGER_CST && tree_int_cst_sgn (op1) < 0)
! return NULL_TREE;
!
! goto binary;
!
! case LROTATE_EXPR:
! case RROTATE_EXPR:
! /* -1 rotated either direction by any amount is still -1. */
! if (integer_all_onesp (op0))
! return omit_one_operand (type, op0, op1);
!
! /* 0 rotated either direction by any amount is still zero. */
! if (integer_zerop (op0))
! return omit_one_operand (type, op0, op1);
!
! goto binary;
!
! case COMPLEX_EXPR:
! if (wins)
! return build_complex (type, op0, op1);
! return NULL_TREE;
!
! case LT_EXPR:
! case LE_EXPR:
! case GT_EXPR:
! case GE_EXPR:
! case EQ_EXPR:
! case NE_EXPR:
! /* If one arg is a real or integer constant, put it last. */
! if ((TREE_CODE (op0) == INTEGER_CST
! && TREE_CODE (op1) != INTEGER_CST)
! || (TREE_CODE (op0) == REAL_CST
! && TREE_CODE (op0) != REAL_CST))
! {
! tree temp;
!
! temp = op0;
! op0 = op1;
! op1 = temp;
! code = swap_tree_comparison (code);
! }
!
! /* Change X >= C to X > (C - 1) and X < C to X <= (C - 1) if C > 0.
! This transformation affects the cases which are handled in later
! optimizations involving comparisons with non-negative constants. */
! if (TREE_CODE (op1) == INTEGER_CST
! && TREE_CODE (op0) != INTEGER_CST
! && tree_int_cst_sgn (op1) > 0)
! {
! switch (code)
! {
! case GE_EXPR:
! code = GT_EXPR;
! op1 = const_binop (MINUS_EXPR, op1, integer_one_node, 0);
! break;
!
! case LT_EXPR:
! code = LE_EXPR;
! op1 = const_binop (MINUS_EXPR, op1, integer_one_node, 0);
! break;
!
! default:
! break;
! }
! }
!
! tem = fold_relational_hi_lo (&code, type, &op0, &op1);
! if (tem)
! return tem;
!
! /* Fall through. */
!
! case ORDERED_EXPR:
! case UNORDERED_EXPR:
! case UNLT_EXPR:
! case UNLE_EXPR:
! case UNGT_EXPR:
! case UNGE_EXPR:
! case UNEQ_EXPR:
! case LTGT_EXPR:
! if (!wins)
! return NULL_TREE;
!
! return fold_relational_const (code, type, op0, op1);
!
! case RANGE_EXPR:
! /* This could probably be handled. */
! return NULL_TREE;
!
! case TRUTH_AND_EXPR:
! /* If second arg is constant zero, result is zero, but first arg
! must be evaluated. */
! if (integer_zerop (op1))
! return omit_one_operand (type, op1, op0);
! /* Likewise for first arg, but note that only the TRUTH_AND_EXPR
! case will be handled here. */
! if (integer_zerop (op0))
! return omit_one_operand (type, op0, op1);
! if (TREE_CODE (op0) == INTEGER_CST && TREE_CODE (op1) == INTEGER_CST)
! return constant_boolean_node (true, type);
! return NULL_TREE;
!
! case TRUTH_OR_EXPR:
! /* If second arg is constant true, result is true, but we must
! evaluate first arg. */
! if (TREE_CODE (op1) == INTEGER_CST && ! integer_zerop (op1))
! return omit_one_operand (type, op1, op0);
! /* Likewise for first arg, but note this only occurs here for
! TRUTH_OR_EXPR. */
! if (TREE_CODE (op0) == INTEGER_CST && ! integer_zerop (op0))
! return omit_one_operand (type, op0, op1);
! if (TREE_CODE (op0) == INTEGER_CST && TREE_CODE (op1) == INTEGER_CST)
! return constant_boolean_node (false, type);
! return NULL_TREE;
!
! case TRUTH_XOR_EXPR:
! if (TREE_CODE (op0) == INTEGER_CST && TREE_CODE (op1) == INTEGER_CST)
! {
! int x = ! integer_zerop (op0) ^ ! integer_zerop (op1);
! return constant_boolean_node (x, type);
! }
! return NULL_TREE;
!
! default:
! return NULL_TREE;
! }
}
/* Given the components of a unary expression CODE, TYPE and OP0,
--- 10756,10763 ----
tree
fold_binary_to_constant (enum tree_code code, tree type, tree op0, tree op1)
{
! tree tem = fold_binary (code, type, op0, op1);
! return (tem && TREE_CONSTANT (tem)) ? tem : NULL_TREE;
}
/* Given the components of a unary expression CODE, TYPE and OP0,
*************** fold_binary_to_constant (enum tree_code
*** 11204,11274 ****
tree
fold_unary_to_constant (enum tree_code code, tree type, tree op0)
{
! /* Make sure we have a suitable constant argument. */
! if (code == NOP_EXPR || code == FLOAT_EXPR || code == CONVERT_EXPR)
! {
! tree subop;
!
! if (TREE_CODE (op0) == COMPLEX_CST)
! subop = TREE_REALPART (op0);
! else
! subop = op0;
!
! if (TREE_CODE (subop) != INTEGER_CST && TREE_CODE (subop) != REAL_CST)
! return NULL_TREE;
! }
!
! switch (code)
! {
! case NOP_EXPR:
! case FLOAT_EXPR:
! case CONVERT_EXPR:
! case FIX_TRUNC_EXPR:
! case FIX_FLOOR_EXPR:
! case FIX_CEIL_EXPR:
! case FIX_ROUND_EXPR:
! return fold_convert_const (code, type, op0);
!
! case NEGATE_EXPR:
! if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
! return fold_negate_const (op0, type);
! else
! return NULL_TREE;
!
! case ABS_EXPR:
! if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST)
! return fold_abs_const (op0, type);
! else
! return NULL_TREE;
!
! case BIT_NOT_EXPR:
! if (TREE_CODE (op0) == INTEGER_CST)
! return fold_not_const (op0, type);
! else
! return NULL_TREE;
!
! case REALPART_EXPR:
! if (TREE_CODE (op0) == COMPLEX_CST)
! return TREE_REALPART (op0);
! else
! return NULL_TREE;
!
! case IMAGPART_EXPR:
! if (TREE_CODE (op0) == COMPLEX_CST)
! return TREE_IMAGPART (op0);
! else
! return NULL_TREE;
!
! case CONJ_EXPR:
! if (TREE_CODE (op0) == COMPLEX_CST
! && TREE_CODE (TREE_TYPE (op0)) == COMPLEX_TYPE)
! return build_complex (type, TREE_REALPART (op0),
! negate_expr (TREE_IMAGPART (op0)));
! return NULL_TREE;
!
! default:
! return NULL_TREE;
! }
}
/* If EXP represents referencing an element in a constant string
--- 10776,10783 ----
tree
fold_unary_to_constant (enum tree_code code, tree type, tree op0)
{
! tree tem = fold_unary (code, type, op0);
! return (tem && TREE_CONSTANT (tem)) ? tem : NULL_TREE;
}
/* If EXP represents referencing an element in a constant string
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833