This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] PR opt/5263: Improve simplify_associative_operation
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 5 Nov 2003 23:08:34 -0700 (MST)
- Subject: [PATCH] PR opt/5263: Improve simplify_associative_operation
The following patch is my solution to resolve PR optimization/5263 which
is an enhancement request to improve GCC's optimizations. Currently
mainline GCC doesn't optimize expressions such as "a & b & ~a & ~b", as
the constant folding and RTL simplification routines tend to operate
locally, catching "a & ~a", or attempt to associate constants.
The proposed solution is to be a bit more aggressive in the function
simplify_associative_operation called from simplify_binary_operation.
The current implementation uses associative_constant_p to identify
constant operands to associate. By taking advantage of the fact that
simplify_binary_operation returns NULL_RTX if no simplification can
be made, we can probe whether "(x op y) op z" can be simplified further
by checking "(x op z) op y" and "x op (y op z)" recursively. This is
a generalization of the current "constant" rules to catch examples of
"(x op c1) op c2".
Unlike constant folding at the tree-level, the depth of RTL expressions
is bounded, so there's very little cost associated with this recursion.
Unfortunately, there is a single technicality: simplify_binary_operation
does not return NULL if "x op y" should be canonicalized using
commutativity, returning "y op x". Clearly, such reordering is not
particularly useful in determining that an expression is "simpler" than
the current one. To avoid potential problems, we can reorder operands
ourselves before calling simplify_binary_operation, so that a non-NULL
result is indeed a reduced expression.
Alas, simplify_binary_operation and simplify_relational_operation don't
order their raw operands using swap_commutative_operands_p, but instead
use their "true" operands, after calling avoid_constant_pool_reference.
The patch below simplifies this logic, by teaching s_c_o_p to make use
of avoid_constant_pool_reference itself.
The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all languages except treelang, and regression tested
with a top-level "make -k check" with no new failures. I've also
confirmed that this patch does indeed optimize "a & b & ~a".
Ok for mainline? I appreciate it may not be suitable during stage3,
but even if not, posting this message allows the patch below to be
associated with the PR entry in bugzilla.
2003-11-05 Roger Sayle <roger@eyesopen.com>
PR optimization/5263
* simplify-rtx.c (associative_constant_p): Delete.
(simplify_associative_operation): Rewrite to linearize terms, and
attempt to simplify new term against both left and right subterms.
(simplify_binary_operation): Call swap_commutative_operands_p on
op0 and op1, not trueop0 and trueop1. Move the initialization of
trueop0 and trueop1 down to where first needed.
(simplify_relational_operation): Likewise.
* rtlanal.c (commutative_operand_precedence): Also order constant
operands using avoid_constant_pool_reference.
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.165
diff -c -3 -p -r1.165 simplify-rtx.c
*** simplify-rtx.c 2 Nov 2003 13:56:40 -0000 1.165
--- simplify-rtx.c 2 Nov 2003 21:58:35 -0000
*************** static rtx neg_const_int (enum machine_m
*** 53,59 ****
static int simplify_plus_minus_op_data_cmp (const void *, const void *);
static rtx simplify_plus_minus (enum rtx_code, enum machine_mode, rtx,
rtx, int);
- static bool associative_constant_p (rtx);
static rtx simplify_associative_operation (enum rtx_code, enum machine_mode,
rtx, rtx);
--- 53,58 ----
*************** simplify_unary_operation (enum rtx_code
*** 1064,1130 ****
}
}
! /* Subroutine of simplify_associative_operation. Return true if rtx OP
! is a suitable integer or floating point immediate constant. */
! static bool
! associative_constant_p (rtx op)
! {
! if (GET_CODE (op) == CONST_INT
! || GET_CODE (op) == CONST_DOUBLE)
! return true;
! op = avoid_constant_pool_reference (op);
! return GET_CODE (op) == CONST_INT
! || GET_CODE (op) == CONST_DOUBLE;
! }
- /* Subroutine of simplify_binary_operation to simplify an associative
- binary operation CODE with result mode MODE, operating on OP0 and OP1.
- Return 0 if no simplification is possible. */
static rtx
simplify_associative_operation (enum rtx_code code, enum machine_mode mode,
rtx op0, rtx op1)
{
rtx tem;
! /* Simplify (x op c1) op c2 as x op (c1 op c2). */
! if (GET_CODE (op0) == code
! && associative_constant_p (op1)
! && associative_constant_p (XEXP (op0, 1)))
{
! tem = simplify_binary_operation (code, mode, XEXP (op0, 1), op1);
! if (! tem)
! return tem;
! return simplify_gen_binary (code, mode, XEXP (op0, 0), tem);
! }
! /* Simplify (x op c1) op (y op c2) as (x op y) op (c1 op c2). */
! if (GET_CODE (op0) == code
! && GET_CODE (op1) == code
! && associative_constant_p (XEXP (op0, 1))
! && associative_constant_p (XEXP (op1, 1)))
! {
! rtx c = simplify_binary_operation (code, mode,
! XEXP (op0, 1), XEXP (op1, 1));
! if (! c)
! return 0;
! tem = simplify_gen_binary (code, mode, XEXP (op0, 0), XEXP (op1, 0));
! return simplify_gen_binary (code, mode, tem, c);
! }
! /* Canonicalize (x op c) op y as (x op y) op c. */
! if (GET_CODE (op0) == code
! && associative_constant_p (XEXP (op0, 1)))
! {
! tem = simplify_gen_binary (code, mode, XEXP (op0, 0), op1);
! return simplify_gen_binary (code, mode, tem, XEXP (op0, 1));
}
! /* Canonicalize x op (y op c) as (x op y) op c. */
! if (GET_CODE (op1) == code
! && associative_constant_p (XEXP (op1, 1)))
{
! tem = simplify_gen_binary (code, mode, op0, XEXP (op1, 0));
! return simplify_gen_binary (code, mode, tem, XEXP (op1, 1));
}
return 0;
--- 1063,1121 ----
}
}
! /* Subroutine of simplify_binary_operation to simplify a commutative,
! associative binary operation CODE with result mode MODE, operating
! on OP0 and OP1. CODE is currently one of PLUS, MULT, AND, IOR, XOR,
! SMIN, SMAX, UMIN or UMAX. Return zero if no simplification or
! canonicalization is possible. */
static rtx
simplify_associative_operation (enum rtx_code code, enum machine_mode mode,
rtx op0, rtx op1)
{
rtx tem;
! /* Linearize the operator to the left. */
! if (GET_CODE (op1) == code)
{
! /* "(a op b) op (c op d)" becomes "((a op b) op c) op d)". */
! if (GET_CODE (op0) == code)
! {
! tem = simplify_gen_binary (code, mode, op0, XEXP (op1, 0));
! return simplify_gen_binary (code, mode, tem, XEXP (op1, 1));
! }
! /* "a op (b op c)" becomes "(b op c) op a". */
! if (! swap_commutative_operands_p (op1, op0))
! return simplify_gen_binary (code, mode, op1, op0);
! tem = op0;
! op0 = op1;
! op1 = tem;
}
! if (GET_CODE (op0) == code)
{
! /* Canonicalize "(x op c) op y" as "(x op y) op c". */
! if (swap_commutative_operands_p (XEXP (op0, 1), op1))
! {
! tem = simplify_gen_binary (code, mode, XEXP (op0, 0), op1);
! return simplify_gen_binary (code, mode, tem, XEXP (op0, 1));
! }
!
! /* Attempt to simplify "(a op b) op c" as "a op (b op c)". */
! tem = swap_commutative_operands_p (XEXP (op0, 1), op1)
! ? simplify_binary_operation (code, mode, op1, XEXP (op0, 1))
! : simplify_binary_operation (code, mode, XEXP (op0, 1), op1);
! if (tem != 0)
! return simplify_gen_binary (code, mode, XEXP (op0, 0), tem);
!
! /* Attempt to simplify "(a op b) op c" as "(a op c) op b". */
! tem = swap_commutative_operands_p (XEXP (op0, 0), op1)
! ? simplify_binary_operation (code, mode, op1, XEXP (op0, 0))
! : simplify_binary_operation (code, mode, XEXP (op0, 0), op1);
! if (tem != 0)
! return simplify_gen_binary (code, mode, tem, XEXP (op0, 1));
}
return 0;
*************** simplify_binary_operation (enum rtx_code
*** 1142,1150 ****
HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
HOST_WIDE_INT val;
unsigned int width = GET_MODE_BITSIZE (mode);
rtx tem;
- rtx trueop0 = avoid_constant_pool_reference (op0);
- rtx trueop1 = avoid_constant_pool_reference (op1);
/* Relational operations don't work here. We must know the mode
of the operands in order to do the comparison correctly.
--- 1133,1140 ----
HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
HOST_WIDE_INT val;
unsigned int width = GET_MODE_BITSIZE (mode);
+ rtx trueop0, trueop1;
rtx tem;
/* Relational operations don't work here. We must know the mode
of the operands in order to do the comparison correctly.
*************** simplify_binary_operation (enum rtx_code
*** 1156,1167 ****
/* Make sure the constant is second. */
if (GET_RTX_CLASS (code) == 'c'
! && swap_commutative_operands_p (trueop0, trueop1))
{
tem = op0, op0 = op1, op1 = tem;
- tem = trueop0, trueop0 = trueop1, trueop1 = tem;
}
if (VECTOR_MODE_P (mode)
&& GET_CODE (trueop0) == CONST_VECTOR
&& GET_CODE (trueop1) == CONST_VECTOR)
--- 1146,1159 ----
/* Make sure the constant is second. */
if (GET_RTX_CLASS (code) == 'c'
! && swap_commutative_operands_p (op0, op1))
{
tem = op0, op0 = op1, op1 = tem;
}
+ trueop0 = avoid_constant_pool_reference (op0);
+ trueop1 = avoid_constant_pool_reference (op1);
+
if (VECTOR_MODE_P (mode)
&& GET_CODE (trueop0) == CONST_VECTOR
&& GET_CODE (trueop1) == CONST_VECTOR)
*************** simplify_relational_operation (enum rtx_
*** 2495,2515 ****
if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
- trueop0 = avoid_constant_pool_reference (op0);
- trueop1 = avoid_constant_pool_reference (op1);
-
/* We can't simplify MODE_CC values since we don't know what the
actual comparison is. */
if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC || CC0_P (op0))
return 0;
/* Make sure the constant is second. */
! if (swap_commutative_operands_p (trueop0, trueop1))
{
tem = op0, op0 = op1, op1 = tem;
- tem = trueop0, trueop0 = trueop1, trueop1 = tem;
code = swap_condition (code);
}
/* For integer comparisons of A and B maybe we can simplify A - B and can
then simplify a comparison of that with zero. If A and B are both either
--- 2487,2506 ----
if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
/* We can't simplify MODE_CC values since we don't know what the
actual comparison is. */
if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC || CC0_P (op0))
return 0;
/* Make sure the constant is second. */
! if (swap_commutative_operands_p (op0, op1))
{
tem = op0, op0 = op1, op1 = tem;
code = swap_condition (code);
}
+
+ trueop0 = avoid_constant_pool_reference (op0);
+ trueop1 = avoid_constant_pool_reference (op1);
/* For integer comparisons of A and B maybe we can simplify A - B and can
then simplify a comparison of that with zero. If A and B are both either
Index: rtlanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtlanal.c,v
retrieving revision 1.169
diff -c -3 -p -r1.169 rtlanal.c
*** rtlanal.c 18 Oct 2003 18:45:16 -0000 1.169
--- rtlanal.c 2 Nov 2003 21:58:36 -0000
*************** commutative_operand_precedence (rtx op)
*** 3023,3028 ****
--- 3023,3033 ----
{
/* Constants always come the second operand. Prefer "nice" constants. */
if (GET_CODE (op) == CONST_INT)
+ return -7;
+ if (GET_CODE (op) == CONST_DOUBLE)
+ return -6;
+ op = avoid_constant_pool_reference (op);
+ if (GET_CODE (op) == CONST_INT)
return -5;
if (GET_CODE (op) == CONST_DOUBLE)
return -4;
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