Richard Guenther wrote:
> On Thu, Mar 8, 2012 at 3:29 PM, Ulrich Weigand <uweig...@de.ibm.com> wrote:
> > - Should I try to improve forwprop to handle casts and additional re-
> > association cases until it handles the above expression?
>
> Yes, ideally by trying to sub-divide this task into separate profitable
> transforms. Maybe Andrew can chime in here?
I finally got some time to look into this in detail. The various special-
case transforms in associate_plusminus all transform a plus/minus expression
tree into either a single operand, a negated operand, or a single plus or
minus of two operands. This is valid as long as we can prove that the
newly introduced expression can never overflow (if we're doing signed
arithmetic). This is true in those special cases due to either:
- If all sub-expressions of the contracted plus/minus tree are themselves
performed in signed arithmetic and thus are guaranteed to never overflow,
their result equals the "true" arithmetic result if we were to perform
the computation in the actual integers with unlimited precision.
Now, "true" arithmetic is associative. Thus, if we re-associate the
expression tree such that everything cancels out and just a single
operation A +/- B (or -A) remains, the "true" result of that operation
must equal the true result of the original expression -- which means
in particular that it lies within the range of the underlying data
type, and hence that final operation itself cannot overflow.
- In the case of introducing a negation, we only need to be sure that
its operand can never be the minimum value of its type range. This
can on occasion be proven via a form of value range tracking.
For example, when performing the transformation ~A + 1 --> -A, we note
that ~A cannot be INT_MAX, since we can add 1 to it without overflow;
and therefore A cannot be INT_MIN.
Now, using those two rules, we can actually prove many more cases where
reassociation is possible. For example, we can transform (A + (B + C)) - C
to A + B (due to the first rule). We can also transform the original
expression resulting from end-of-loop value computation
(A + 1) + (int) ((unsigned) ~A + (unsigned) B)
into just "B" -- this can never overflow since we aren't even introducing
any new expression.
The following patch rewrites associate_plusminus to remove all the
explicitly coded special cases, and instead performs a scan of the
plus/minus tree similar to what is done in tree-ssa-reassoc (and also
in simplify-rtx for that matter). If this results in an expression
tree that collapses to just a single operand, or just a single newly
introduced operation, and -in the latter case- one of the two rules
above ensure the new operation is safe, the transformation is performed.
This still passes all reassoc tests, and in fact allows to remove XFAILs
from two of them. It also catches the end-of-loop value computation case.
Tested on i386-linux with no regressions.
OK for mainline?
Bye,
Ulrich
ChangeLog:
gcc/
* tree-ssa-forwprop.c (enum plus_minus_op_range,
struct plus_minus_op_data, struct plus_minus_data): New types.
(next_plus_minus_op, remove_plus_minus_op, add_plus_minus_op,
add_plus_minus_ops, setup_plus_minus_ops): New functions.
(associate_plusminus): Reimplement.
gcc/testsuite/
* gcc.dg/tree-ssa/reassoc-2.c: Remove XFAIL.
* gcc.dg/tree-ssa/reassoc-9.c: Update test, remove XFAIL.
* gcc.dg/tree-ssa/reassoc-23.c: Update test.
* gcc.dg/tree-ssa/reassoc-26.c: New test.
Index: gcc/testsuite/gcc.dg/tree-ssa/reassoc-23.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/reassoc-23.c (revision 187653)
--- gcc/testsuite/gcc.dg/tree-ssa/reassoc-23.c (working copy)
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O2 -fdump-tree-reassoc1" } */
unsigned int
foo(unsigned int a, unsigned int b, unsigned int c, unsigned int d,
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O2 -fdump-tree-optimized" } */
unsigned int
foo(unsigned int a, unsigned int b, unsigned int c, unsigned int d,
*************** foo(unsigned int a, unsigned int b, unsi
*** 13,17 ****
return e;
}
! /* { dg-final { scan-tree-dump-times "= 20" 1 "reassoc1"} } */
! /* { dg-final { cleanup-tree-dump "reassoc1" } } */
--- 13,17 ----
return e;
}
! /* { dg-final { scan-tree-dump-times "return 20" 1 "optimized"} } */
! /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/reassoc-26.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/reassoc-26.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/reassoc-26.c (revision 0)
***************
*** 0 ****
--- 1,17 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+
+ int
+ foo (int start, int end)
+ {
+ int i;
+
+ for (i = start; i < end; i++)
+ ;
+
+ return i;
+ }
+
+ /* Verify that the end-of-loop value is simplified to just "end". */
+ /* { dg-final { scan-tree-dump-times "i_. = end_." 1 "optimized"} } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/reassoc-2.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/reassoc-2.c (revision 187653)
--- gcc/testsuite/gcc.dg/tree-ssa/reassoc-2.c (working copy)
*************** int b0, b1, b2, b3, b4,e;
*** 14,20 ****
return e;
}
! /* We can't reassociate the expressions due to undefined signed overflow. */
!
! /* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" { xfail *-*-* }
} } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
--- 14,18 ----
return e;
}
! /* { dg-final { scan-tree-dump-times "return 0" 1 "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/reassoc-9.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/reassoc-9.c (revision 187653)
--- gcc/testsuite/gcc.dg/tree-ssa/reassoc-9.c (working copy)
***************
*** 1,5 ****
/* { dg-do compile } */
! /* { dg-options "-O2 -fdump-tree-reassoc1" } */
int main(int a, int b, int c, int d, int e, int f, int g, int h)
{
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O2 -fdump-tree-optimized" } */
int main(int a, int b, int c, int d, int e, int f, int g, int h)
{
*************** int main(int a, int b, int c, int d, int
*** 11,18 ****
return e;
}
! /* We can always re-associate to a final constant but the current
! implementation does not allow easy roll-back without IL changes. */
!
! /* { dg-final { scan-tree-dump-times "= 20" 1 "reassoc1" { xfail *-*-* } } }
*/
! /* { dg-final { cleanup-tree-dump "reassoc1" } } */
--- 11,15 ----
return e;
}
! /* { dg-final { scan-tree-dump-times "return 20" 1 "optimized" } } */
! /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/tree-ssa-forwprop.c
===================================================================
*** gcc/tree-ssa-forwprop.c (revision 187653)
--- gcc/tree-ssa-forwprop.c (working copy)
*************** simplify_bitwise_binary (gimple_stmt_ite
*** 2188,2462 ****
}
! /* Perform re-associations of the plus or minus statement STMT that are
! always permitted. Returns true if the CFG was changed. */
static bool
! associate_plusminus (gimple_stmt_iterator *gsi)
{
! gimple stmt = gsi_stmt (*gsi);
! tree rhs1 = gimple_assign_rhs1 (stmt);
! tree rhs2 = gimple_assign_rhs2 (stmt);
! enum tree_code code = gimple_assign_rhs_code (stmt);
! bool changed;
! /* We can't reassociate at all for saturating types. */
! if (TYPE_SATURATING (TREE_TYPE (rhs1)))
! return false;
! /* First contract negates. */
! do
{
! changed = false;
! /* A +- (-B) -> A -+ B. */
! if (TREE_CODE (rhs2) == SSA_NAME)
{
! gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
! if (is_gimple_assign (def_stmt)
! && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
! && can_propagate_from (def_stmt))
! {
! code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
! gimple_assign_set_rhs_code (stmt, code);
! rhs2 = gimple_assign_rhs1 (def_stmt);
! gimple_assign_set_rhs2 (stmt, rhs2);
! gimple_set_modified (stmt, true);
! changed = true;
! }
}
! /* (-A) + B -> B - A. */
! if (TREE_CODE (rhs1) == SSA_NAME
! && code == PLUS_EXPR)
{
! gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
! if (is_gimple_assign (def_stmt)
! && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
! && can_propagate_from (def_stmt))
{
! code = MINUS_EXPR;
! gimple_assign_set_rhs_code (stmt, code);
! rhs1 = rhs2;
! gimple_assign_set_rhs1 (stmt, rhs1);
! rhs2 = gimple_assign_rhs1 (def_stmt);
! gimple_assign_set_rhs2 (stmt, rhs2);
! gimple_set_modified (stmt, true);
! changed = true;
}
}
}
- while (changed);
! /* We can't reassociate floating-point or fixed-point plus or minus
! because of saturation to +-Inf. */
! if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
! || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
! goto out;
!
! /* Second match patterns that allow contracting a plus-minus pair
! irrespective of overflow issues.
!
! (A +- B) - A -> +- B
! (A +- B) -+ B -> A
! (CST +- A) +- CST -> CST +- A
! (A + CST) +- CST -> A + CST
! ~A + A -> -1
! ~A + 1 -> -A
! A - (A +- B) -> -+ B
! A +- (B +- A) -> +- B
! CST +- (CST +- A) -> CST +- A
! CST +- (A +- CST) -> CST +- A
! A + ~A -> -1
! via commutating the addition and contracting operations to zero
! by reassociation. */
! if (TREE_CODE (rhs1) == SSA_NAME)
{
! gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
! if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
{
! enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
! if (def_code == PLUS_EXPR
! || def_code == MINUS_EXPR)
! {
! tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
! tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
! if (operand_equal_p (def_rhs1, rhs2, 0)
! && code == MINUS_EXPR)
! {
! /* (A +- B) - A -> +- B. */
! code = ((def_code == PLUS_EXPR)
! ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
! rhs1 = def_rhs2;
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
! else if (operand_equal_p (def_rhs2, rhs2, 0)
! && code != def_code)
! {
! /* (A +- B) -+ B -> A. */
! code = TREE_CODE (def_rhs1);
! rhs1 = def_rhs1;
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
! else if (TREE_CODE (rhs2) == INTEGER_CST
! && TREE_CODE (def_rhs1) == INTEGER_CST)
! {
! /* (CST +- A) +- CST -> CST +- A. */
! tree cst = fold_binary (code, TREE_TYPE (rhs1),
! def_rhs1, rhs2);
! if (cst && !TREE_OVERFLOW (cst))
! {
! code = def_code;
! gimple_assign_set_rhs_code (stmt, code);
! rhs1 = cst;
! gimple_assign_set_rhs1 (stmt, rhs1);
! rhs2 = def_rhs2;
! gimple_assign_set_rhs2 (stmt, rhs2);
! gimple_set_modified (stmt, true);
! }
! }
! else if (TREE_CODE (rhs2) == INTEGER_CST
! && TREE_CODE (def_rhs2) == INTEGER_CST
! && def_code == PLUS_EXPR)
! {
! /* (A + CST) +- CST -> A + CST. */
! tree cst = fold_binary (code, TREE_TYPE (rhs1),
! def_rhs2, rhs2);
! if (cst && !TREE_OVERFLOW (cst))
! {
! code = PLUS_EXPR;
! gimple_assign_set_rhs_code (stmt, code);
! rhs1 = def_rhs1;
! gimple_assign_set_rhs1 (stmt, rhs1);
! rhs2 = cst;
! gimple_assign_set_rhs2 (stmt, rhs2);
! gimple_set_modified (stmt, true);
! }
! }
! }
! else if (def_code == BIT_NOT_EXPR
! && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
{
! tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
! if (code == PLUS_EXPR
! && operand_equal_p (def_rhs1, rhs2, 0))
! {
! /* ~A + A -> -1. */
! code = INTEGER_CST;
! rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
! else if (code == PLUS_EXPR
! && integer_onep (rhs1))
! {
! /* ~A + 1 -> -A. */
! code = NEGATE_EXPR;
! rhs1 = def_rhs1;
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
}
}
}
! if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
{
! gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
! if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
! {
! enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
! if (def_code == PLUS_EXPR
! || def_code == MINUS_EXPR)
! {
! tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
! tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
! if (operand_equal_p (def_rhs1, rhs1, 0)
! && code == MINUS_EXPR)
! {
! /* A - (A +- B) -> -+ B. */
! code = ((def_code == PLUS_EXPR)
! ? NEGATE_EXPR : TREE_CODE (def_rhs2));
! rhs1 = def_rhs2;
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
! else if (operand_equal_p (def_rhs2, rhs1, 0)
! && code != def_code)
! {
! /* A +- (B +- A) -> +- B. */
! code = ((code == PLUS_EXPR)
! ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
! rhs1 = def_rhs1;
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
! else if (TREE_CODE (rhs1) == INTEGER_CST
! && TREE_CODE (def_rhs1) == INTEGER_CST)
! {
! /* CST +- (CST +- A) -> CST +- A. */
! tree cst = fold_binary (code, TREE_TYPE (rhs2),
! rhs1, def_rhs1);
! if (cst && !TREE_OVERFLOW (cst))
{
! code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
! gimple_assign_set_rhs_code (stmt, code);
! rhs1 = cst;
! gimple_assign_set_rhs1 (stmt, rhs1);
! rhs2 = def_rhs2;
! gimple_assign_set_rhs2 (stmt, rhs2);
! gimple_set_modified (stmt, true);
! }
! }
! else if (TREE_CODE (rhs1) == INTEGER_CST
! && TREE_CODE (def_rhs2) == INTEGER_CST)
! {
! /* CST +- (A +- CST) -> CST +- A. */
! tree cst = fold_binary (def_code == code
! ? PLUS_EXPR : MINUS_EXPR,
! TREE_TYPE (rhs2),
! rhs1, def_rhs2);
! if (cst && !TREE_OVERFLOW (cst))
! {
! rhs1 = cst;
! gimple_assign_set_rhs1 (stmt, rhs1);
! rhs2 = def_rhs1;
! gimple_assign_set_rhs2 (stmt, rhs2);
! gimple_set_modified (stmt, true);
}
}
}
! else if (def_code == BIT_NOT_EXPR
! && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
! {
! tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
! if (code == PLUS_EXPR
! && operand_equal_p (def_rhs1, rhs1, 0))
! {
! /* A + ~A -> -1. */
! code = INTEGER_CST;
! rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
! rhs2 = NULL_TREE;
! gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! }
}
}
}
--- 2188,2661 ----
}
! /* Data structures to hold plus/minus operand information during
! re-association. */
!
! /* Range information. We only track whether we are sure that an operand
! cannot equal the minimum value of its type (RANGE_NOT_MIN), or that it
! cannot equal the maximum value of its type (RANGE_NOT_MAX). */
!
! enum plus_minus_op_range
! {
! RANGE_UNKNOWN = 0,
! RANGE_NOT_MIN,
! RANGE_NOT_MAX
! };
!
! /* A single operand. OP is the operand, NEG is true if the operand needs
! to be negated, and RANGE holds operand range information we were able
! to track. */
!
! struct plus_minus_op_data
! {
! tree op;
! bool neg;
! enum plus_minus_op_range range;
! };
!
! /* All operands of the expression. The value of the expression is considered
! the sum of all operands, negated if indicated. There is no implicit order
! of the operands; this data structure is only used in contexts where we
! know addition is associative. */
!
! struct plus_minus_data
! {
! /* Operand array and number of current operands. We do not bother to
! dynamically resize the array; 8 operands ought to be enough for the
! vast majority of cases. */
! struct plus_minus_op_data ops[8];
! unsigned int n_ops;
!
! /* Used for iterating through all operands. */
! unsigned int curr_op;
!
! /* True if we have successfully applied some simplification operation. */
! bool simplified;
!
! /* True if we ran into a failure (e.g. the ops array overflowed). The
! rest of the data structure is no longer reliable in that case. */
! bool failed;
! };
!
! /* Iterate through the OPS operand array. Return false if we are already
! at the end of the array. Otherwise, return true and set OP to the index
! of the next operand to be considered. */
static bool
! next_plus_minus_op (struct plus_minus_data *ops, unsigned int *op)
{
! if (ops->curr_op < ops->n_ops)
! {
! *op = ops->curr_op++;
! return true;
! }
!
! return false;
! }
!
! /* Remove operand with index OP from the OPS operand array. */
!
! static void
! remove_plus_minus_op (struct plus_minus_data *ops, unsigned int op)
! {
! if (op + 1 < ops->n_ops)
! memmove (&ops->ops[op], &ops->ops[op + 1],
! sizeof (struct plus_minus_op_data) * (ops->n_ops - op - 1));
!
! ops->n_ops--;
!
! if (op < ops->curr_op)
! ops->curr_op--;
!
! ops->simplified = true;
! }
! /* Add NEW_OP at the end of the OPS operand array. If possible, perform
! simplifications that are guaranteed to leave the total value of the
! expression encoded by OPS unchanged:
! - cancel NEW_OP against an equivalent but negated operand
! - simplify constant integer operands (without overflow).
! Assumes operands can be freely re-associated. */
!
! static void
! add_plus_minus_op (struct plus_minus_data *ops,
! struct plus_minus_op_data *new_op)
! {
! struct plus_minus_op_data cst_op;
! unsigned int i;
!
! if (ops->failed)
! return;
! if (TREE_CODE (new_op->op) == INTEGER_CST && new_op->neg)
{
! tree cst = fold_unary_to_constant (NEGATE_EXPR,
! TREE_TYPE (new_op->op), new_op->op);
! if (cst && !TREE_OVERFLOW (cst))
! {
! new_op = &cst_op;
! cst_op.op = cst;
! cst_op.neg = false;
! cst_op.range = RANGE_UNKNOWN;
! ops->simplified = true;
! }
! }
! for (i = 0; i < ops->n_ops; i++)
! {
! if (operand_equal_p (new_op->op, ops->ops[i].op, 0)
! && new_op->neg != ops->ops[i].neg)
{
! remove_plus_minus_op (ops, i);
! ops->simplified = true;
! return;
}
! if (TREE_CODE (new_op->op) == INTEGER_CST && !new_op->neg
! && TREE_CODE (ops->ops[i].op) == INTEGER_CST && !ops->ops[i].neg)
{
! tree cst = fold_binary (PLUS_EXPR, TREE_TYPE (new_op->op),
! new_op->op, ops->ops[i].op);
! if (cst && !TREE_OVERFLOW (cst))
{
! if (integer_zerop (cst))
! remove_plus_minus_op (ops, i);
! else
! ops->ops[i].op = cst;
!
! ops->simplified = true;
! return;
}
}
}
! if (ops->n_ops < ARRAY_SIZE (ops->ops))
! {
! ops->ops[ops->n_ops++] = *new_op;
! return;
! }
!
! /* If we run out of room in the array, give up. This should
! almost never happen. */
! ops->n_ops = 0;
! ops->failed = true;
! return;
! }
!
! /* Add up to two operands LHS/RHS (as indicated by N_OPS) to the
! OPS operand array. If OUTER_NEG is true, operands are to be
! negated before adding them to the array. */
!
! static void
! add_plus_minus_ops (struct plus_minus_data *ops,
! unsigned int n_ops,
! struct plus_minus_op_data *lhs,
! struct plus_minus_op_data *rhs,
! bool outer_neg)
! {
! lhs->neg ^= outer_neg;
! rhs->neg ^= outer_neg;
!
! if (n_ops >= 1)
! add_plus_minus_op (ops, lhs);
! if (n_ops >= 2)
! add_plus_minus_op (ops, rhs);
! }
!
! /* Extract plus/minus operands from STMT. Stores up to two operands in
! LHS and RHS and returns the number of operands stored. If no operands
! could be extracted, returns 0.
!
! The routine guarantees that a plus/minus expression formed from LHS
! and RHS will evaluate to the same value as STMT, using modulo arithmetic.
! If STMT is of integral type and TRUE_ARITHMETIC is true, the routine
! guarantees in addition that this property holds true when performing
! operations in "true" integer arithmetic.
! OUTER_RANGE encodes range information known about the result of STMT;
! this may be used to infer range data on LHS and/or RHS. */
! static unsigned int
! setup_plus_minus_ops (gimple stmt, struct plus_minus_op_data *lhs,
! struct plus_minus_op_data *rhs,
! enum plus_minus_op_range outer_range,
! bool true_arithmetic)
! {
! enum tree_code this_code = gimple_assign_rhs_code (stmt);
! tree type = TREE_TYPE (gimple_assign_lhs (stmt));
!
! switch (this_code)
{
! case PLUS_EXPR:
! case MINUS_EXPR:
! /* If we have an integral type where overflow wraps, we can only
! guarantee that LHS plus RHS equal STMT in modulo arithmetic,
! so fail if "true" arithmetic is requested. For integral types
! where overflow does *not* wrap, we can assume that STMT does
! not overflow, and thus the equality holds in "true" arithmetic
! as well.
!
! For floating point types, we -strictly speaking- could never
! extract operands due to rounding effect and saturation at
! +/-Inf. However, the -flag-associative-math setting directs
! the compiler to ignore such effect; respect it.
!
! Fixed point types can never be re-associated. */
! if ((INTEGRAL_TYPE_P (type)
! && (!TYPE_OVERFLOW_WRAPS (type) || !true_arithmetic))
! || (FLOAT_TYPE_P (type)
! && flag_associative_math))
! {
! lhs->op = gimple_assign_rhs1 (stmt);
! lhs->neg = false;
! lhs->range = RANGE_UNKNOWN;
!
! rhs->op = gimple_assign_rhs2 (stmt);
! rhs->neg = (this_code == MINUS_EXPR);
! rhs->range = RANGE_UNKNOWN;
!
! /* For integer types that cannot overflow, the fact that a constant
! is added to / subtracted from an operand allows us to deduce
! range information about that operand. */
! if (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type)
! && TREE_CODE (rhs->op) == INTEGER_CST)
! {
! int sgn = tree_int_cst_sgn (rhs->op);
! if (sgn != 0)
! {
! bool neg_p = (sgn < 0) ^ (this_code == MINUS_EXPR);
! lhs->range = neg_p? RANGE_NOT_MIN : RANGE_NOT_MAX;
! }
! }
!
! return 2;
! }
! break;
!
! case NEGATE_EXPR:
! /* For integral types, we can extract a negation in the same set
! of circumstances we could extract a PLUS or MINUS, see above.
!
! We can always extract a negation for types that use a separate
! sign bit: floating-point types and signed fixed-point types. */
! if ((INTEGRAL_TYPE_P (type)
! && (!TYPE_OVERFLOW_WRAPS (type) || !true_arithmetic))
! || FLOAT_TYPE_P (type)
! || (FIXED_POINT_TYPE_P (type) && !TYPE_UNSIGNED (type)))
! {
! lhs->op = gimple_assign_rhs1 (stmt);
! lhs->neg = true;
! lhs->range = RANGE_UNKNOWN;
!
! /* For integer types that cannot overflow, the fact that a
! negation is performed allows us to deduce range information
! about its operand. */
! if (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type))
! lhs->range = RANGE_NOT_MIN;
!
! return 1;
! }
! break;
!
! case BIT_NOT_EXPR:
! /* We transform ~A into -A - 1. This is allowed only for integral
! types, and only in modulo arithmetic. */
! if (INTEGRAL_TYPE_P (type) && !true_arithmetic)
{
! rhs->op = build_int_cst_type (type, -1);
! rhs->neg = false;
! rhs->range = RANGE_UNKNOWN;
!
! lhs->op = gimple_assign_rhs1 (stmt);
! lhs->neg = true;
! lhs->range = RANGE_UNKNOWN;
!
! /* For all integer types, BIT_NOT_EXPR transforms the maximum
! value of its range to the minmum value and vice versa. */
! if (outer_range == RANGE_NOT_MIN)
! lhs->range = RANGE_NOT_MAX;
! else if (outer_range == RANGE_NOT_MAX)
! lhs->range = RANGE_NOT_MIN;
!
! return 2;
! }
! break;
!
! CASE_CONVERT:
! /* We look through conversions between integral types of the same
! precision. This is in general allowed only in modulo arithmetic.
! This case is used in particular to handle constructs like
! (int) ((unsigned) A + (unsigned) B)
! which are on occasion produced by other optimization passes that
! want to avoid introducing undefined overflows. */
! if (INTEGRAL_TYPE_P (type) && !true_arithmetic)
! {
! tree op = gimple_assign_rhs1 (stmt);
!
! if (TREE_TYPE (op) && INTEGRAL_TYPE_P (TREE_TYPE (op))
! && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op)))
{
! lhs->op = op;
! lhs->neg = false;
! lhs->range = RANGE_UNKNOWN;
!
! return 1;
}
}
+ break;
+
+ default:
+ break;
}
! return 0;
! }
!
! /* Perform re-associations of the plus or minus statement STMT that are
! always permitted. Returns true if the CFG was changed. */
!
! static bool
! associate_plusminus (gimple_stmt_iterator *gsi)
! {
! gimple stmt = gsi_stmt (*gsi);
! tree type = TREE_TYPE (gimple_assign_lhs (stmt));
! struct plus_minus_data ops;
! struct plus_minus_op_data lhs, rhs;
! unsigned int n_ops;
! bool no_overflow;
! bool true_arithmetic;
! unsigned int i;
! int pass;
!
! /* The type of STMT determines whether we are allowed to create new
! operations in that type that may introduce overflows. */
! no_overflow = (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type));
!
! /* Initialize OPS array from STMT. */
! memset (&ops, 0, sizeof ops);
! n_ops = setup_plus_minus_ops (stmt, &lhs, &rhs, RANGE_UNKNOWN, no_overflow);
! add_plus_minus_ops (&ops, n_ops, &lhs, &rhs, false);
!
! /* Iterate over OPS array and perform simplifications. If we cannot
! introduce new overflows, we first perform only simplifications that
! are valid in "true" arithmetic, and in a second pass then perform
! all simplifications valid in modulo arithmetic. If we *are* allowed
! to introduce new overflows, we skip the first pass. */
! for (pass = 0; pass < 2; pass++)
{
! if (pass == 0)
! true_arithmetic = no_overflow;
! else if (true_arithmetic)
! true_arithmetic = false;
! else
! break;
!
! ops.curr_op = 0;
! while (next_plus_minus_op (&ops, &i))
! {
! tree this_op = ops.ops[i].op;
! bool this_neg = ops.ops[i].neg;
! enum plus_minus_op_range this_range = ops.ops[i].range;
!
! /* For each operand in the array that is an SSA_NAME, see whether
! we can extract additional plus/minus operands from its def. */
! if (TREE_CODE (this_op) == SSA_NAME)
! {
! gimple def_stmt = SSA_NAME_DEF_STMT (this_op);
! if (is_gimple_assign (def_stmt)
! && can_propagate_from (def_stmt))
! {
! n_ops = setup_plus_minus_ops (def_stmt, &lhs, &rhs,
! this_range, true_arithmetic);
! if (n_ops > 0)
{
! remove_plus_minus_op (&ops, i);
! add_plus_minus_ops (&ops, n_ops, &lhs, &rhs, this_neg);
}
}
}
!
! /* After every simplification, check whether OPS array can now be
! represented by a new statement. */
!
! /* If we have just a single, non-negated operand left, we replace
! the whole expression by that operand. */
! if (ops.n_ops == 1 && !ops.ops[0].neg
! && useless_type_conversion_p (TREE_TYPE (ops.ops[0].op), type))
! {
! gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (ops.ops[0].op),
! ops.ops[0].op, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! goto out;
! }
!
! /* If we have a single *negated* operand left, check whether we are
! allowed to introduce a new NEGATE_EXPR. We can do that if:
! - we may introduce new overflows,
! - all simplifications were performed in "true" arithmetic,
! because then the true value of the negated operand is in
! the original range of the type, or
! - we were able to otherwise prove the operand cannot be the
! minimum value of its type. */
! if (ops.n_ops == 1 && ops.ops[0].neg
! && useless_type_conversion_p (TREE_TYPE (ops.ops[0].op), type)
! && (!no_overflow || true_arithmetic
! || ops.ops[0].range == RANGE_NOT_MIN))
! {
! gimple_assign_set_rhs_with_ops (gsi, NEGATE_EXPR,
! ops.ops[0].op, NULL_TREE);
! gcc_assert (gsi_stmt (*gsi) == stmt);
! gimple_set_modified (stmt, true);
! goto out;
! }
!
! /* If we have two operands left (and some simplifcation took place,
! so we're not simply looking at the original two operands), and
! at most one of them is negated, check whether we are allowed to
! introduce a new PLUS_EXPR or MINUS_EXPR. This follows the same
! rules as above, except that range information doesn't help.
!
! Note that even after we've replaced the original expression with
! a new PLUS or MINUS, we continue further simplications -- maybe
! we are still able to find an even simpler equivalence. */
! if (ops.n_ops == 2 && ops.simplified
! && !ops.ops[0].neg && !ops.ops[1].neg
! && useless_type_conversion_p (TREE_TYPE (ops.ops[0].op), type)
! && useless_type_conversion_p (TREE_TYPE (ops.ops[1].op), type)
! && (!no_overflow || true_arithmetic))
! {
! gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
! gimple_assign_set_rhs1 (stmt, ops.ops[0].op);
! gimple_assign_set_rhs2 (stmt, ops.ops[1].op);
! gimple_set_modified (stmt, true);
! ops.simplified = false;
! }
!
! if (ops.n_ops == 2 && ops.simplified
! && !ops.ops[0].neg && ops.ops[1].neg
! && useless_type_conversion_p (TREE_TYPE (ops.ops[0].op), type)
! && useless_type_conversion_p (TREE_TYPE (ops.ops[1].op), type)
! && (!no_overflow || true_arithmetic))
! {
! gimple_assign_set_rhs_code (stmt, MINUS_EXPR);
! gimple_assign_set_rhs1 (stmt, ops.ops[0].op);
! gimple_assign_set_rhs2 (stmt, ops.ops[1].op);
! gimple_set_modified (stmt, true);
! ops.simplified = false;
! }
!
! if (ops.n_ops == 2 && ops.simplified
! && ops.ops[0].neg && !ops.ops[1].neg
! && useless_type_conversion_p (TREE_TYPE (ops.ops[0].op), type)
! && useless_type_conversion_p (TREE_TYPE (ops.ops[1].op), type)
! && (!no_overflow || true_arithmetic))
! {
! gimple_assign_set_rhs_code (stmt, MINUS_EXPR);
! gimple_assign_set_rhs1 (stmt, ops.ops[1].op);
! gimple_assign_set_rhs2 (stmt, ops.ops[0].op);
! gimple_set_modified (stmt, true);
! ops.simplified = false;
}
}
}
--
Dr. Ulrich Weigand
GNU Toolchain for Linux on System z and Cell BE
ulrich.weig...@de.ibm.com
