This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [testcase] simplify_binary_operation test (was Re: -freduce-all-givs and fortran)
On Fri, Sep 07, 2001 at 03:55:14AM -0400, Jakub Jelinek wrote:
> Here is a small testcase which kills cc1 on x86 with your patch.
> It creates endless recursion between 2 simplify_binary_operation's and
> simplify_plus_minus because simplify_binary_operation at the end adds CONST
> back.
Actually, that explanation isn't quite complete. It takes at
least two rounds in simplify_plus_minus to tickle the problem.
Consider arguments:
code = plus
op0 = (reg X)
op1 = (const (plus (symbol_ref Y)
(const_int Z))))
simplify_plus_minus will break this into
(reg X)
(symbol_ref Y)
(const_int Z)
then in the first round reconstruct the (const (plus ...)).
In the second round it will invoke simplify_binary_operation
with the original operands. Which equals infinite recursion.
I've been poking at this problem in between other work all day.
I'm currently testing the following patch, which looks promising.
r~
* loop.c (record_giv): Avoid simplifying MULT to ASHIFT.
(express_from_1): Wrap lines.
* rtlanal.c (commutative_operand_precedence): Rename from
operand_preference; export.
* rtl.h: Declare it.
* simplify-rtx.c (simplify_gen_binary): Tidy +/- const_int handling.
(simplify_binary_operation): Invoke simplify_plus_minus on
(CONST (PLUS ...)) as well.
(struct simplify_plus_minus_op_data): New.
(simplify_plus_minus_op_data_cmp): New.
(simplify_plus_minus): Use them. Avoid infinite recursion with
simplify_binary_operation wrt CONST.
Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.353
diff -c -p -d -r1.353 loop.c
*** loop.c 2001/09/03 20:54:01 1.353
--- loop.c 2001/09/07 06:33:23
*************** record_giv (loop, v, insn, src_reg, dest
*** 4922,4930 ****
rtx set = single_set (insn);
rtx temp;
! /* Attempt to prove constantness of the values. */
temp = simplify_rtx (add_val);
! if (temp)
add_val = temp;
v->insn = insn;
--- 4922,4933 ----
rtx set = single_set (insn);
rtx temp;
! /* Attempt to prove constantness of the values. Don't let simplity_rtx
! undo the MULT canonicalization that we performed earlier. */
temp = simplify_rtx (add_val);
! if (temp
! && ! (GET_CODE (add_val) == MULT
! && GET_CODE (temp) == ASHIFT))
add_val = temp;
v->insn = insn;
*************** express_from_1 (a, b, mult)
*** 6371,6377 ****
}
else if (CONSTANT_P (a))
{
! return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), b, a);
}
else if (GET_CODE (b) == PLUS)
{
--- 6374,6383 ----
}
else if (CONSTANT_P (a))
{
! enum machine_mode mode_a = GET_MODE (a);
! enum machine_mode mode_b = GET_MODE (b);
! enum machine_mode mode = mode_b == VOIDmode ? mode_a : mode_b;
! return simplify_gen_binary (MINUS, mode, b, a);
}
else if (GET_CODE (b) == PLUS)
{
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.294
diff -c -p -d -r1.294 rtl.h
*** rtl.h 2001/08/30 20:44:50 1.294
--- rtl.h 2001/09/07 06:33:23
*************** extern int reg_used_between_p PARAMS ((
*** 1374,1379 ****
--- 1374,1380 ----
extern int reg_referenced_between_p PARAMS ((rtx, rtx, rtx));
extern int reg_set_between_p PARAMS ((rtx, rtx, rtx));
extern int regs_set_between_p PARAMS ((rtx, rtx, rtx));
+ extern int commutative_operand_precedence PARAMS ((rtx));
extern int swap_commutative_operands_p PARAMS ((rtx, rtx));
extern int modified_between_p PARAMS ((rtx, rtx, rtx));
extern int no_labels_between_p PARAMS ((rtx, rtx));
Index: rtlanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtlanal.c,v
retrieving revision 1.108
diff -c -p -d -r1.108 rtlanal.c
*** rtlanal.c 2001/08/22 14:35:37 1.108
--- rtlanal.c 2001/09/07 06:33:23
*************** Software Foundation, 59 Temple Place - S
*** 30,36 ****
static void set_of_1 PARAMS ((rtx, rtx, void *));
static void insn_dependent_p_1 PARAMS ((rtx, rtx, void *));
static int computed_jump_p_1 PARAMS ((rtx));
- static int operand_preference PARAMS ((rtx));
static void parms_set PARAMS ((rtx, rtx, void *));
/* Bit flags that specify the machine subtype we are compiling for.
--- 30,35 ----
*************** regno_use_in (regno, x)
*** 2558,2565 ****
We use negative values to indicate a preference for the first operand
and positive values for the second operand. */
! static int
! operand_preference (op)
rtx op;
{
/* Constants always come the second operand. Prefer "nice" constants. */
--- 2557,2564 ----
We use negative values to indicate a preference for the first operand
and positive values for the second operand. */
! int
! commutative_operand_precedence (op)
rtx op;
{
/* Constants always come the second operand. Prefer "nice" constants. */
*************** int
*** 2597,2603 ****
swap_commutative_operands_p (x, y)
rtx x, y;
{
! return operand_preference (x) < operand_preference (y);
}
/* Return 1 if X is an autoincrement side effect and the register is
--- 2596,2603 ----
swap_commutative_operands_p (x, y)
rtx x, y;
{
! return (commutative_operand_precedence (x)
! < commutative_operand_precedence (y));
}
/* Return 1 if X is an autoincrement side effect and the register is
Index: simplify-rtx.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/simplify-rtx.c,v
retrieving revision 1.81
diff -c -p -d -r1.81 simplify-rtx.c
*** simplify-rtx.c 2001/09/06 23:33:56 1.81
--- simplify-rtx.c 2001/09/07 06:33:23
*************** Software Foundation, 59 Temple Place - S
*** 95,100 ****
--- 95,102 ----
#define HWI_SIGN_EXTEND(low) \
((((HOST_WIDE_INT) low) < 0) ? ((HOST_WIDE_INT) -1) : ((HOST_WIDE_INT) 0))
+ static int simplify_plus_minus_op_data_cmp PARAMS ((const void *,
+ const void *));
static rtx simplify_plus_minus PARAMS ((enum rtx_code,
enum machine_mode, rtx, rtx));
static void check_fold_consts PARAMS ((PTR));
*************** simplify_gen_binary (code, mode, op0, op
*** 130,141 ****
/* Handle addition and subtraction of CONST_INT specially. Otherwise,
just form the operation. */
! if (code == PLUS && GET_CODE (op1) == CONST_INT
! && GET_MODE (op0) != VOIDmode)
! return plus_constant (op0, INTVAL (op1));
! else if (code == MINUS && GET_CODE (op1) == CONST_INT
! && GET_MODE (op0) != VOIDmode)
! return plus_constant (op0, - INTVAL (op1));
else
return gen_rtx_fmt_ee (code, mode, op0, op1);
}
--- 132,146 ----
/* Handle addition and subtraction of CONST_INT specially. Otherwise,
just form the operation. */
! if (GET_CODE (op1) == CONST_INT
! && GET_MODE (op0) != VOIDmode
! && (code == PLUS || code == MINUS))
! {
! HOST_WIDE_INT value = INTVAL (op1);
! if (code == MINUS)
! value = -value;
! return plus_constant (op0, value);
! }
else
return gen_rtx_fmt_ee (code, mode, op0, op1);
}
*************** simplify_binary_operation (code, mode, o
*** 1124,1130 ****
if (INTEGRAL_MODE_P (mode)
&& (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
! || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
&& (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
return tem;
break;
--- 1129,1139 ----
if (INTEGRAL_MODE_P (mode)
&& (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
! || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS
! || (GET_CODE (op0) == CONST
! && GET_CODE (XEXP (op0, 0)) == PLUS)
! || (GET_CODE (op1) == CONST
! && GET_CODE (XEXP (op1, 0)) == PLUS))
&& (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
return tem;
break;
*************** simplify_binary_operation (code, mode, o
*** 1162,1169 ****
#endif
return xop00;
}
-
break;
case MINUS:
/* None of these optimizations can be done for IEEE
floating point. */
--- 1171,1178 ----
#endif
return xop00;
}
break;
+
case MINUS:
/* None of these optimizations can be done for IEEE
floating point. */
*************** simplify_binary_operation (code, mode, o
*** 1257,1263 ****
if (INTEGRAL_MODE_P (mode)
&& (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
! || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS)
&& (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
return tem;
--- 1266,1276 ----
if (INTEGRAL_MODE_P (mode)
&& (GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS
! || GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS
! || (GET_CODE (op0) == CONST
! && GET_CODE (XEXP (op0, 0)) == PLUS)
! || (GET_CODE (op1) == CONST
! && GET_CODE (XEXP (op1, 0)) == PLUS))
&& (tem = simplify_plus_minus (code, mode, op0, op1)) != 0)
return tem;
*************** simplify_binary_operation (code, mode, o
*** 1680,1696 ****
and do all possible simplifications until no more changes occur. Then
we rebuild the operation. */
static rtx
simplify_plus_minus (code, mode, op0, op1)
enum rtx_code code;
enum machine_mode mode;
rtx op0, op1;
{
! rtx ops[8];
! int negs[8];
rtx result, tem;
! int n_ops = 2, input_ops = 2, input_consts = 0, n_consts = 0;
! int first = 1, negate = 0, changed;
int i, j;
memset ((char *) ops, 0, sizeof ops);
--- 1693,1726 ----
and do all possible simplifications until no more changes occur. Then
we rebuild the operation. */
+ struct simplify_plus_minus_op_data
+ {
+ rtx op;
+ int neg;
+ };
+
+ static int
+ simplify_plus_minus_op_data_cmp (p1, p2)
+ const void *p1;
+ const void *p2;
+ {
+ const struct simplify_plus_minus_op_data *d1 = p1;
+ const struct simplify_plus_minus_op_data *d2 = p2;
+
+ return (commutative_operand_precedence (d2->op)
+ - commutative_operand_precedence (d1->op));
+ }
+
static rtx
simplify_plus_minus (code, mode, op0, op1)
enum rtx_code code;
enum machine_mode mode;
rtx op0, op1;
{
! struct simplify_plus_minus_op_data ops[8];
rtx result, tem;
! int n_ops = 2, input_ops = 2, input_consts = 0, n_consts;
! int first, negate, changed;
int i, j;
memset ((char *) ops, 0, sizeof ops);
*************** simplify_plus_minus (code, mode, op0, op
*** 1699,1851 ****
changed. If we run out of room in our array, give up; this should
almost never happen. */
! ops[0] = op0, ops[1] = op1, negs[0] = 0, negs[1] = (code == MINUS);
! changed = 1;
! while (changed)
{
changed = 0;
for (i = 0; i < n_ops; i++)
! switch (GET_CODE (ops[i]))
! {
! case PLUS:
! case MINUS:
! if (n_ops == 7)
! return 0;
! ops[n_ops] = XEXP (ops[i], 1);
! negs[n_ops++] = GET_CODE (ops[i]) == MINUS ? !negs[i] : negs[i];
! ops[i] = XEXP (ops[i], 0);
! input_ops++;
! changed = 1;
! break;
! case NEG:
! ops[i] = XEXP (ops[i], 0);
! negs[i] = ! negs[i];
! changed = 1;
! break;
! case CONST:
! ops[i] = XEXP (ops[i], 0);
! input_consts++;
! changed = 1;
! break;
! case NOT:
! /* ~a -> (-a - 1) */
! if (n_ops != 7)
! {
! ops[n_ops] = constm1_rtx;
! negs[n_ops++] = negs[i];
! ops[i] = XEXP (ops[i], 0);
! negs[i] = ! negs[i];
! changed = 1;
! }
! break;
! case CONST_INT:
! if (negs[i])
! ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0, changed = 1;
! break;
! default:
! break;
! }
}
/* If we only have two operands, we can't do anything. */
if (n_ops <= 2)
! return 0;
/* Now simplify each pair of operands until nothing changes. The first
time through just simplify constants against each other. */
! changed = 1;
! while (changed)
{
changed = first;
for (i = 0; i < n_ops - 1; i++)
for (j = i + 1; j < n_ops; j++)
! if (ops[i] != 0 && ops[j] != 0
! && (! first || (CONSTANT_P (ops[i]) && CONSTANT_P (ops[j]))))
! {
! rtx lhs = ops[i], rhs = ops[j];
! enum rtx_code ncode = PLUS;
! if (negs[i] && ! negs[j])
! lhs = ops[j], rhs = ops[i], ncode = MINUS;
! else if (! negs[i] && negs[j])
! ncode = MINUS;
! tem = simplify_binary_operation (ncode, mode, lhs, rhs);
! if (tem)
! {
! ops[i] = tem, ops[j] = 0;
! negs[i] = negs[i] && negs[j];
! if (GET_CODE (tem) == NEG)
! ops[i] = XEXP (tem, 0), negs[i] = ! negs[i];
! if (GET_CODE (ops[i]) == CONST_INT && negs[i])
! ops[i] = GEN_INT (- INTVAL (ops[i])), negs[i] = 0;
! changed = 1;
! }
! }
first = 0;
}
!
! /* Pack all the operands to the lower-numbered entries and give up if
! we didn't reduce the number of operands we had. Make sure we
! count a CONST as two operands. If we have the same number of
! operands, but have made more CONSTs than we had, this is also
! an improvement, so accept it. */
for (i = 0, j = 0; j < n_ops; j++)
! if (ops[j] != 0)
! {
! ops[i] = ops[j], negs[i++] = negs[j];
! if (GET_CODE (ops[j]) == CONST)
! n_consts++;
! }
! if (i + n_consts > input_ops
! || (i + n_consts == input_ops && n_consts <= input_consts))
! return 0;
! n_ops = i;
! /* If we have a CONST_INT, put it last. */
! for (i = 0; i < n_ops - 1; i++)
! if (GET_CODE (ops[i]) == CONST_INT)
! {
! tem = ops[n_ops - 1], ops[n_ops - 1] = ops[i] , ops[i] = tem;
! j = negs[n_ops - 1], negs[n_ops - 1] = negs[i], negs[i] = j;
! }
/* Put a non-negated operand first. If there aren't any, make all
operands positive and negate the whole thing later. */
- for (i = 0; i < n_ops && negs[i]; i++)
- ;
if (i == n_ops)
{
for (i = 0; i < n_ops; i++)
! negs[i] = 0;
negate = 1;
}
else if (i != 0)
{
! tem = ops[0], ops[0] = ops[i], ops[i] = tem;
! j = negs[0], negs[0] = negs[i], negs[i] = j;
}
/* Now make the result by performing the requested operations. */
! result = ops[0];
for (i = 1; i < n_ops; i++)
! result = simplify_gen_binary (negs[i] ? MINUS : PLUS, mode, result, ops[i]);
return negate ? gen_rtx_NEG (mode, result) : result;
}
--- 1729,1932 ----
changed. If we run out of room in our array, give up; this should
almost never happen. */
! ops[0].op = op0;
! ops[0].neg = 0;
! ops[1].op = op1;
! ops[1].neg = (code == MINUS);
! do
{
changed = 0;
for (i = 0; i < n_ops; i++)
! {
! rtx this_op = ops[i].op;
! int this_neg = ops[i].neg;
! enum rtx_code this_code = GET_CODE (this_op);
! switch (this_code)
! {
! case PLUS:
! case MINUS:
! if (n_ops == 7)
! return 0;
! ops[n_ops].op = XEXP (this_op, 1);
! ops[n_ops].neg = (this_code == MINUS) - this_neg;
! n_ops++;
! ops[i].op = XEXP (this_op, 0);
! input_ops++;
! changed = 1;
! break;
! case NEG:
! ops[i].op = XEXP (this_op, 0);
! ops[i].neg = ! this_neg;
! changed = 1;
! break;
! case CONST:
! ops[i].op = XEXP (this_op, 0);
! input_consts++;
! changed = 1;
! break;
! case NOT:
! /* ~a -> (-a - 1) */
! if (n_ops != 7)
! {
! ops[n_ops].op = constm1_rtx;
! ops[n_ops].neg = this_neg;
! ops[i].op = XEXP (this_op, 0);
! ops[i].neg = !this_neg;
! changed = 1;
! }
! break;
!
! case CONST_INT:
! if (this_neg)
! {
! ops[i].op = GEN_INT (- INTVAL (this_op));
! ops[i].neg = 0;
! changed = 1;
! }
! break;
!
! default:
! break;
! }
! }
}
+ while (changed);
/* If we only have two operands, we can't do anything. */
if (n_ops <= 2)
! return NULL_RTX;
/* Now simplify each pair of operands until nothing changes. The first
time through just simplify constants against each other. */
! first = 1;
! do
{
changed = first;
for (i = 0; i < n_ops - 1; i++)
for (j = i + 1; j < n_ops; j++)
! {
! rtx lhs = ops[i].op, rhs = ops[j].op;
! int lneg = ops[i].neg, rneg = ops[j].neg;
! if (lhs != 0 && rhs != 0
! && (! first || (CONSTANT_P (lhs) && CONSTANT_P (rhs))))
! {
! enum rtx_code ncode = PLUS;
! if (lneg != rneg)
! {
! ncode = MINUS;
! if (lneg)
! tem = lhs, lhs = rhs, rhs = tem;
! }
! else if (swap_commutative_operands_p (lhs, rhs))
! tem = lhs, lhs = rhs, rhs = tem;
! tem = simplify_binary_operation (ncode, mode, lhs, rhs);
+ /* Reject "simplifications" that just wrap the two
+ arguments in a CONST. Failure to do so can result
+ in infinite recursion with simplify_binary_operation
+ when it calls us to simplify CONST operations. */
+ if (tem
+ && ! (GET_CODE (tem) == CONST
+ && GET_CODE (XEXP (tem, 0)) == ncode
+ && XEXP (XEXP (tem, 0), 0) == lhs
+ && XEXP (XEXP (tem, 0), 1) == rhs))
+ {
+ lneg &= rneg;
+ if (GET_CODE (tem) == NEG)
+ tem = XEXP (tem, 0), lneg = !lneg;
+ if (GET_CODE (tem) == CONST_INT && lneg)
+ tem = GEN_INT (- INTVAL (tem)), lneg = 0;
+
+ ops[i].op = tem;
+ ops[i].neg = lneg;
+ ops[j].op = NULL_RTX;
+ changed = 1;
+ }
+ }
+ }
+
first = 0;
}
! while (changed);
+ /* Pack all the operands to the lower-numbered entries. */
for (i = 0, j = 0; j < n_ops; j++)
! if (ops[j].op)
! ops[i++] = ops[j];
! n_ops = i;
! /* Sort the operations based on swap_commutative_operands_p. */
! qsort (ops, n_ops, sizeof (*ops), simplify_plus_minus_op_data_cmp);
! /* We suppressed creation of trivial CONST expressions in the
! combination loop to avoid recursion. Create one manually now.
! The combination loop should have ensured that there is exactly
! one CONST_INT, and the sort will have ensured that it is last
! in the array and that any other constant will be next-to-last. */
! if (n_ops > 1
! && GET_CODE (ops[n_ops - 1].op) == CONST_INT
! && CONSTANT_P (ops[n_ops - 2].op))
! {
! HOST_WIDE_INT value = INTVAL (ops[n_ops - 1].op);
! if (ops[n_ops - 1].neg)
! value = -value;
! ops[n_ops - 2].op = plus_constant (ops[n_ops - 2].op, value);
! n_ops--;
! }
!
! /* Count the number of CONSTs that we generated. */
! n_consts = 0;
! for (i = 0; i < n_ops; i++)
! if (GET_CODE (ops[i].op) == CONST)
! n_consts++;
!
! /* Give up if we didn't reduce the number of operands we had. Make
! sure we count a CONST as two operands. If we have the same
! number of operands, but have made more CONSTs than before, this
! is also an improvement, so accept it. */
! if (n_ops + n_consts > input_ops
! || (n_ops + n_consts == input_ops && n_consts <= input_consts))
! return NULL_RTX;
/* Put a non-negated operand first. If there aren't any, make all
operands positive and negate the whole thing later. */
+ negate = 0;
+ for (i = 0; i < n_ops && ops[i].neg; i++)
+ continue;
if (i == n_ops)
{
for (i = 0; i < n_ops; i++)
! ops[i].neg = 0;
negate = 1;
}
else if (i != 0)
{
! tem = ops[0].op;
! ops[0] = ops[i];
! ops[i].op = tem;
! ops[i].neg = 1;
}
/* Now make the result by performing the requested operations. */
! result = ops[0].op;
for (i = 1; i < n_ops; i++)
! result = gen_rtx_fmt_ee (ops[i].neg ? MINUS : PLUS,
! mode, result, ops[i].op);
return negate ? gen_rtx_NEG (mode, result) : result;
}