This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] PR/26847, missed optimizations in simplify_plus_minus
- From: Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Cc: Roger Sayle <roger at eyesopen dot com>
- Date: Sun, 13 Aug 2006 09:41:17 +0200
- Subject: [PATCH] PR/26847, missed optimizations in simplify_plus_minus
As drafted last February, this patch changes a bit the flow of
simplify_plus_minus to identify more canonicalization opportunities.
This fixes a missed-optimization on s390.
The early bail out is delayed after an insertion sort pass on
commutative_operand_precedence. If there is a swap, we go on with the
simplification loop. The insertion sort, also, groups together equal
operands so that we do not miss opportunities when simplifying, for
example, (r1 + 4) - (r2 + r1).
Furthermore, the insertion sort is redone after every pass of the
simplification loop, until this reaches a fixed point: this way, we can
replace the qsort already present in simplify_plus_minus. Note that it
is not necessary to run the sort when "changed" is false and the loop is
exited, because (obviously) no changes were made and the sorting order
was not hampered.
Despite not using qsort anymore, I still kept the comparison in an
external function, because it is quite bulky.
I took the opportunity to simplify the code and make it a little bit
faster: the old code runs at least two passes of the simplification
loop, the first one only to simplify constants against each other.
Instead, we can run the simplification loop backwards, from higher
indices (lower commutative_operand_precedence values) to lower indices
(higher commutative_operand_precedence). This way, CONST_INT and
CONST_DOUBLE RTXen (precedence -7..-4) are processed first, and since
constants can always simplify against each other, the effect of the
first pass are obtained immediately. For the same reason, we can remove
code to "avoid (-x + 1) -> ~x simplifications in the first pass": this
is done to combine the -1 with other constants, but this will have been
done already by the time we combine the -1 (precedence -7) with a CONST
or REG (precedence >= -3).
A couple of additional cleanups are done, in particular:
1) the setting of n_constants is done in the initial loop that expands
op0 and op1, instead of having a separate "for".
2) insertion sort is stable, so we can remove the "IX" field of struct
simplify_plus_minus_op_data.
Compile-time changes are in the noise; well, I saw a -0.3% improvement
but I wouldn't trust it very much.
Bootstrapped/regtested i686-pc-linux-gnu; in addition I tried reverting
the patch for PR28651, and checked that this patch would make that PR
resurface (it was masked on mainline because of the missed optimization
in simplify_plus_minus). Ok for mainline?
Paolo
2006-08-11 Paolo Bonzini <bonzini@gnu.org>
* simplify-rtx.c (struct simplify_plus_minus_op_data): Remove ix.
(simplify_plus_minus_op_data_cmp): Break ties on the address.
(simplify_plus_minus): Count n_constants while filling ops.
Replace qsort with insertion sort. Before going through the array
to simplify pairs, sort it. Delay early exit until after the first
sort -- if swaps occurred, go through the rest of the function.
Simplify pairs in reversed order, without special-casing the first
iteration. Pack ops after simplifying pairs.
Index: simplify-rtx.c
===================================================================
*** simplify-rtx.c (revision 115772)
--- simplify-rtx.c (working copy)
*************** struct simplify_plus_minus_op_data
*** 3185,3191 ****
{
rtx op;
short neg;
- short ix;
};
static int
--- 3185,3190 ----
*************** simplify_plus_minus_op_data_cmp (const v
*** 3199,3205 ****
- commutative_operand_precedence (d1->op));
if (result)
return result;
! return d1->ix - d2->ix;
}
static rtx
--- 3198,3210 ----
- commutative_operand_precedence (d1->op));
if (result)
return result;
!
! /* Group together equal operands to do more simplification (this is especially
! for REGs, which are unique). */
! if (d1->op != d2->op)
! return d1->op < d2->op ? -1 : 1;
!
! return 0;
}
static rtx
*************** simplify_plus_minus (enum rtx_code code,
*** 3209,3215 ****
struct simplify_plus_minus_op_data ops[8];
rtx result, tem;
int n_ops = 2, input_ops = 2;
! int first, changed, canonicalized = 0;
int i, j;
memset (ops, 0, sizeof ops);
--- 3214,3220 ----
struct simplify_plus_minus_op_data ops[8];
rtx result, tem;
int n_ops = 2, input_ops = 2;
! int changed, n_constants = 0, canonicalized = 0;
int i, j;
memset (ops, 0, sizeof ops);
*************** simplify_plus_minus (enum rtx_code code,
*** 3286,3291 ****
--- 3291,3297 ----
break;
case CONST_INT:
+ n_constants++;
if (this_neg)
{
ops[i].op = neg_const_int (mode, this_op);
*************** simplify_plus_minus (enum rtx_code code,
*** 3302,3319 ****
}
while (changed);
! gcc_assert (n_ops >= 2);
! if (!canonicalized)
! {
! int n_constants = 0;
!
! for (i = 0; i < n_ops; i++)
! if (GET_CODE (ops[i].op) == CONST_INT)
! n_constants++;
! if (n_constants <= 1)
! return NULL_RTX;
! }
/* If we only have two operands, we can avoid the loops. */
if (n_ops == 2)
--- 3308,3317 ----
}
while (changed);
! if (n_constants > 1)
! canonicalized = 1;
! gcc_assert (n_ops >= 2);
/* If we only have two operands, we can avoid the loops. */
if (n_ops == 2)
*************** simplify_plus_minus (enum rtx_code code,
*** 3342,3363 ****
return simplify_const_binary_operation (code, mode, lhs, rhs);
}
! /* 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;
--- 3340,3376 ----
return simplify_const_binary_operation (code, mode, lhs, rhs);
}
! /* Now simplify each pair of operands until nothing changes. */
do
{
! /* Insertion sort is good enough for an eight-element array. */
! for (i = 1; i < n_ops; i++)
! {
! struct simplify_plus_minus_op_data save;
! j = i - 1;
! if (simplify_plus_minus_op_data_cmp (&ops[j], &ops[i]) < 0)
! continue;
!
! canonicalized = 1;
! save = ops[i];
! do
! ops[j + 1] = ops[j];
! while (j-- && simplify_plus_minus_op_data_cmp (&ops[j], &save) > 0);
! ops[j + 1] = save;
! }
!
! /* This is only useful the first time through. */
! if (!canonicalized)
! return NULL_RTX;
! changed = 0;
! for (i = n_ops - 1; i > 0; i--)
! for (j = i - 1; j >= 0; j--)
{
! rtx lhs = ops[j].op, rhs = ops[i].op;
! int lneg = ops[j].neg, rneg = ops[i].neg;
! if (lhs != 0 && rhs != 0)
{
enum rtx_code ncode = PLUS;
*************** simplify_plus_minus (enum rtx_code code,
*** 3393,3405 ****
&& ! (GET_CODE (tem) == CONST
&& GET_CODE (XEXP (tem, 0)) == ncode
&& XEXP (XEXP (tem, 0), 0) == lhs
! && XEXP (XEXP (tem, 0), 1) == rhs)
! /* Don't allow -x + -1 -> ~x simplifications in the
! first pass. This allows us the chance to combine
! the -1 with other constants. */
! && ! (first
! && GET_CODE (tem) == NOT
! && XEXP (tem, 0) == rhs))
{
lneg &= rneg;
if (GET_CODE (tem) == NEG)
--- 3406,3412 ----
&& ! (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)
*************** simplify_plus_minus (enum rtx_code code,
*** 3415,3438 ****
}
}
! 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];
- /* Stabilize sort. */
- ops[i].ix = i;
- i++;
- }
- n_ops = i;
-
- /* Sort the operations based on swap_commutative_operands_p. */
- qsort (ops, n_ops, sizeof (*ops), simplify_plus_minus_op_data_cmp);
-
/* Create (minus -C X) instead of (neg (const (plus X C))). */
if (n_ops == 2
&& GET_CODE (ops[1].op) == CONST_INT
--- 3422,3438 ----
}
}
! /* 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];
! i++;
! }
! n_ops = i;
}
while (changed);
/* Create (minus -C X) instead of (neg (const (plus X C))). */
if (n_ops == 2
&& GET_CODE (ops[1].op) == CONST_INT