OSDN Git Service

PR middle-end/40815
authormkuvyrkov <mkuvyrkov@138bc75d-0d04-0410-961f-82ee72b054a4>
Thu, 8 Apr 2010 08:20:36 +0000 (08:20 +0000)
committerMasaki Muranaka <monaka@monami-software.com>
Sun, 23 May 2010 00:51:38 +0000 (09:51 +0900)
* tree-ssa-reassoc.c (broken_up_substracts): Rename to plus_negates.
(negate_value): Move code to push elements to broken_up_substracts ...
(eliminate_plus_minus_pair): ... here.  Push operands that have no
negative pair to plus_negates.
(repropagate_negates, init_reassoc, fini_reassoc): Update.

PR middle-end/40815
* gcc.dg/tree-ssa/reassoc-19.c: New.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@158105 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/ChangeLog
gcc/testsuite/ChangeLog
gcc/tree-ssa-reassoc.c

index 6f2b7e0..fc4a4a9 100644 (file)
@@ -1,3 +1,12 @@
+2010-04-08  Maxim Kuvyrkov  <maxim@codesourcery.com>
+
+       PR middle-end/40815
+       * tree-ssa-reassoc.c (broken_up_substracts): Rename to plus_negates.
+       (negate_value): Move code to push elements to broken_up_substracts ...
+       (eliminate_plus_minus_pair): ... here.  Push operands that have no
+       negative pair to plus_negates.
+       (repropagate_negates, init_reassoc, fini_reassoc): Update.
+
 2010-04-07  Ralf Wildenhues  <Ralf.Wildenhues@gmx.de>
 
        * doc/install.texi (Configuration): Move description of
index d4ea278..30ee707 100644 (file)
@@ -1,3 +1,8 @@
+2010-04-08  Maxim Kuvyrkov  <maxim@codesourcery.com>
+
+       PR middle-end/40815
+       * gcc.dg/tree-ssa/reassoc-19.c: New.
+
 2010-04-07  Jakub Jelinek  <jakub@redhat.com>
 
        PR c/18624
index 40152d9..cf05de5 100644 (file)
@@ -22,17 +22,17 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
+#include "ggc.h"
 #include "tree.h"
 #include "basic-block.h"
 #include "diagnostic.h"
-#include "tree-pretty-print.h"
-#include "gimple-pretty-print.h"
 #include "tree-inline.h"
 #include "tree-flow.h"
 #include "gimple.h"
 #include "tree-dump.h"
 #include "timevar.h"
 #include "tree-iterator.h"
+#include "real.h"
 #include "tree-pass.h"
 #include "alloc-pool.h"
 #include "vec.h"
@@ -172,15 +172,11 @@ static struct
 typedef struct operand_entry
 {
   unsigned int rank;
-  int id;
   tree op;
 } *operand_entry_t;
 
 static alloc_pool operand_entry_pool;
 
-/* This is used to assign a unique ID to each struct operand_entry
-   so that qsort results are identical on different hosts.  */
-static int next_operand_entry_id;
 
 /* Starting rank number for a given basic block, so that we can rank
    operations using unmovable instructions in that BB based on the bb
@@ -332,31 +328,16 @@ sort_by_operand_rank (const void *pa, const void *pb)
      to fold when added/multiplied//whatever are put next to each
      other.  Since all constants have rank 0, order them by type.  */
   if (oeb->rank == 0 &&  oea->rank == 0)
-    {
-      if (constant_type (oeb->op) != constant_type (oea->op))
-       return constant_type (oeb->op) - constant_type (oea->op);
-      else
-       /* To make sorting result stable, we use unique IDs to determine
-          order.  */
-        return oeb->id - oea->id;
-    }
+    return constant_type (oeb->op) - constant_type (oea->op);
 
   /* Lastly, make sure the versions that are the same go next to each
      other.  We use SSA_NAME_VERSION because it's stable.  */
   if ((oeb->rank - oea->rank == 0)
       && TREE_CODE (oea->op) == SSA_NAME
       && TREE_CODE (oeb->op) == SSA_NAME)
-    {
-      if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
-       return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
-      else
-       return oeb->id - oea->id;
-    }
+    return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
 
-  if (oeb->rank != oea->rank)
-    return oeb->rank - oea->rank;
-  else
-    return oeb->id - oea->id;
+  return oeb->rank - oea->rank;
 }
 
 /* Add an operand entry to *OPS for the tree operand OP.  */
@@ -368,7 +349,6 @@ add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
 
   oe->op = op;
   oe->rank = get_rank (op);
-  oe->id = next_operand_entry_id++;
   VEC_safe_push (operand_entry_t, heap, *ops, oe);
 }
 
@@ -489,11 +469,11 @@ eliminate_duplicate_pair (enum tree_code opcode,
 
 static VEC(tree, heap) *plus_negates;
 
-/* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
-   expression, look in OPS for a corresponding positive operation to cancel
-   it out.  If we find one, remove the other from OPS, replace
-   OPS[CURRINDEX] with 0 or -1, respectively, and return true.  Otherwise,
-   return false. */
+/* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
+   look in OPS for a corresponding positive operation to cancel it
+   out.  If we find one, remove the other from OPS, replace
+   OPS[CURRINDEX] with 0, and return true.  Otherwise, return
+   false. */
 
 static bool
 eliminate_plus_minus_pair (enum tree_code opcode,
@@ -502,7 +482,6 @@ eliminate_plus_minus_pair (enum tree_code opcode,
                           operand_entry_t curr)
 {
   tree negateop;
-  tree notop;
   unsigned int i;
   operand_entry_t oe;
 
@@ -510,8 +489,7 @@ eliminate_plus_minus_pair (enum tree_code opcode,
     return false;
 
   negateop = get_unary_op (curr->op, NEGATE_EXPR);
-  notop = get_unary_op (curr->op, BIT_NOT_EXPR);
-  if (negateop == NULL_TREE && notop == NULL_TREE)
+  if (negateop == NULL_TREE)
     return false;
 
   /* Any non-negated version will have a rank that is one less than
@@ -543,32 +521,11 @@ eliminate_plus_minus_pair (enum tree_code opcode,
 
          return true;
        }
-      else if (oe->op == notop)
-       {
-         tree op_type = TREE_TYPE (oe->op);
-
-         if (dump_file && (dump_flags & TDF_DETAILS))
-           {
-             fprintf (dump_file, "Equivalence: ");
-             print_generic_expr (dump_file, notop, 0);
-             fprintf (dump_file, " + ~");
-             print_generic_expr (dump_file, oe->op, 0);
-             fprintf (dump_file, " -> -1\n");
-           }
-
-         VEC_ordered_remove (operand_entry_t, *ops, i);
-         add_to_ops_vec (ops, build_int_cst_type (op_type, -1));
-         VEC_ordered_remove (operand_entry_t, *ops, currindex);
-         reassociate_stats.ops_eliminated ++;
-
-         return true;
-       }
     }
 
   /* CURR->OP is a negate expr in a plus expr: save it for later
      inspection in repropagate_negates().  */
-  if (negateop != NULL_TREE)
-    VEC_safe_push (tree, heap, plus_negates, curr->op);
+  VEC_safe_push (tree, heap, plus_negates, curr->op);
 
   return false;
 }
@@ -783,7 +740,6 @@ static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
 /* Structure for tracking and counting operands.  */
 typedef struct oecount_s {
   int cnt;
-  int id;
   enum tree_code oecode;
   tree op;
 } oecount;
@@ -821,11 +777,7 @@ oecount_cmp (const void *p1, const void *p2)
 {
   const oecount *c1 = (const oecount *)p1;
   const oecount *c2 = (const oecount *)p2;
-  if (c1->cnt != c2->cnt)
-    return c1->cnt - c2->cnt;
-  else
-    /* If counts are identical, use unique IDs to stabilize qsort.  */
-    return c1->id - c2->id;
+  return c1->cnt - c2->cnt;
 }
 
 /* Walks the linear chain with result *DEF searching for an operation
@@ -1007,7 +959,6 @@ undistribute_ops_list (enum tree_code opcode,
   VEC (operand_entry_t, heap) **subops;
   htab_t ctable;
   bool changed = false;
-  int next_oecount_id = 0;
 
   if (length <= 1
       || opcode != PLUS_EXPR)
@@ -1075,7 +1026,6 @@ undistribute_ops_list (enum tree_code opcode,
          size_t idx;
          c.oecode = oecode;
          c.cnt = 1;
-         c.id = next_oecount_id++;
          c.op = oe1->op;
          VEC_safe_push (oecount, heap, cvec, &c);
          idx = VEC_length (oecount, cvec) + 41;
@@ -1165,7 +1115,7 @@ undistribute_ops_list (enum tree_code opcode,
              fprintf (dump_file, "Building (");
              print_generic_expr (dump_file, oe1->op, 0);
            }
-         tmpvar = create_tmp_reg (TREE_TYPE (oe1->op), NULL);
+         tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL);
          add_referenced_var (tmpvar);
          zero_one_operation (&oe1->op, c->oecode, c->op);
          EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
@@ -1215,113 +1165,6 @@ undistribute_ops_list (enum tree_code opcode,
   return changed;
 }
 
-/* If OPCODE is BIT_IOR_EXPR or BIT_AND_EXPR and CURR is a comparison
-   expression, examine the other OPS to see if any of them are comparisons
-   of the same values, which we may be able to combine or eliminate.
-   For example, we can rewrite (a < b) | (a == b) as (a <= b).  */
-
-static bool
-eliminate_redundant_comparison (enum tree_code opcode,
-                               VEC (operand_entry_t, heap) **ops,
-                               unsigned int currindex,
-                               operand_entry_t curr)
-{
-  tree op1, op2;
-  enum tree_code lcode, rcode;
-  gimple def1, def2;
-  int i;
-  operand_entry_t oe;
-
-  if (opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
-    return false;
-
-  /* Check that CURR is a comparison.  */
-  if (TREE_CODE (curr->op) != SSA_NAME)
-    return false;
-  def1 = SSA_NAME_DEF_STMT (curr->op);
-  if (!is_gimple_assign (def1))
-    return false;
-  lcode = gimple_assign_rhs_code (def1);
-  if (TREE_CODE_CLASS (lcode) != tcc_comparison)
-    return false;
-  op1 = gimple_assign_rhs1 (def1);
-  op2 = gimple_assign_rhs2 (def1);
-
-  /* Now look for a similar comparison in the remaining OPS.  */
-  for (i = currindex + 1;
-       VEC_iterate (operand_entry_t, *ops, i, oe);
-       i++)
-    {
-      tree t;
-
-      if (TREE_CODE (oe->op) != SSA_NAME)
-       continue;
-      def2 = SSA_NAME_DEF_STMT (oe->op);
-      if (!is_gimple_assign (def2))
-       continue;
-      rcode = gimple_assign_rhs_code (def2);
-      if (TREE_CODE_CLASS (rcode) != tcc_comparison)
-       continue;
-      if (operand_equal_p (op1, gimple_assign_rhs1 (def2), 0)
-         && operand_equal_p (op2, gimple_assign_rhs2 (def2), 0))
-       ;
-      else if (operand_equal_p (op1, gimple_assign_rhs2 (def2), 0)
-              && operand_equal_p (op2, gimple_assign_rhs1 (def2), 0))
-       rcode = swap_tree_comparison (rcode);
-      else
-       continue;
-
-      /* If we got here, we have a match.  See if we can combine the
-        two comparisons.  */
-      t = combine_comparisons (UNKNOWN_LOCATION,
-                              (opcode == BIT_IOR_EXPR
-                               ? TRUTH_OR_EXPR : TRUTH_AND_EXPR),
-                              lcode, rcode, TREE_TYPE (curr->op), op1, op2);
-      if (!t)
-       continue;
-      if (dump_file && (dump_flags & TDF_DETAILS))
-       {
-         fprintf (dump_file, "Equivalence: ");
-         print_generic_expr (dump_file, curr->op, 0);
-         fprintf (dump_file, " %s ", op_symbol_code (opcode));
-         print_generic_expr (dump_file, oe->op, 0);
-         fprintf (dump_file, " -> ");
-         print_generic_expr (dump_file, t, 0);
-         fprintf (dump_file, "\n");
-       }
-
-      /* Now we can delete oe, as it has been subsumed by the new combined
-         expression t.  */
-      VEC_ordered_remove (operand_entry_t, *ops, i);
-      reassociate_stats.ops_eliminated ++;
-
-      /* If t is the same as curr->op, we're done.  Otherwise we must
-        replace curr->op with t.  Special case is if we got a constant
-        back, in which case we add it to the end instead of in place of
-        the current entry.  */
-      if (TREE_CODE (t) == INTEGER_CST)
-       {
-         VEC_ordered_remove (operand_entry_t, *ops, currindex);
-         add_to_ops_vec (ops, t);
-       }
-      else if (TREE_CODE (t) != lcode)
-       {
-         tree tmpvar;
-         gimple sum;
-         enum tree_code subcode;
-         tree newop1;
-         tree newop2;
-         tmpvar = create_tmp_var (TREE_TYPE (t), NULL);
-         add_referenced_var (tmpvar);
-         extract_ops_from_tree (t, &subcode, &newop1, &newop2);
-         sum = build_and_add_sum (tmpvar, newop1, newop2, subcode);
-         curr->op = gimple_get_lhs (sum);
-       }
-      return true;
-    }
-
-  return false;
-}
 
 /* Perform various identities and other optimizations on the list of
    operand entries, stored in OPS.  The tree code for the binary
@@ -1383,8 +1226,7 @@ optimize_ops_list (enum tree_code opcode,
       if (eliminate_not_pairs (opcode, ops, i, oe))
        return;
       if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
-         || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))
-         || (!done && eliminate_redundant_comparison (opcode, ops, i, oe)))
+         || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
        {
          if (done)
            return;
@@ -1865,15 +1707,14 @@ repropagate_negates (void)
     {
       gimple user = get_single_immediate_use (negate);
 
-      if (!user || !is_gimple_assign (user))
-       continue;
-
       /* The negate operand can be either operand of a PLUS_EXPR
         (it can be the LHS if the RHS is a constant for example).
 
         Force the negate operand to the RHS of the PLUS_EXPR, then
         transform the PLUS_EXPR into a MINUS_EXPR.  */
-      if (gimple_assign_rhs_code (user) == PLUS_EXPR)
+      if (user
+         && is_gimple_assign (user)
+         && gimple_assign_rhs_code (user) == PLUS_EXPR)
        {
          /* If the negated operand appears on the LHS of the
             PLUS_EXPR, exchange the operands of the PLUS_EXPR
@@ -1896,63 +1737,9 @@ repropagate_negates (void)
              update_stmt (user);
            }
        }
-      else if (gimple_assign_rhs_code (user) == MINUS_EXPR)
-       {
-         if (gimple_assign_rhs1 (user) == negate)
-           {
-             /* We have
-                  x = -a
-                  y = x - b
-                which we transform into
-                  x = a + b
-                  y = -x .
-                This pushes down the negate which we possibly can merge
-                into some other operation, hence insert it into the
-                plus_negates vector.  */
-             gimple feed = SSA_NAME_DEF_STMT (negate);
-             tree a = gimple_assign_rhs1 (feed);
-             tree rhs2 = gimple_assign_rhs2 (user);
-             gimple_stmt_iterator gsi = gsi_for_stmt (feed), gsi2;
-             gimple_replace_lhs (feed, negate);
-             gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, a, rhs2);
-             update_stmt (gsi_stmt (gsi));
-             gsi2 = gsi_for_stmt (user);
-             gimple_assign_set_rhs_with_ops (&gsi2, NEGATE_EXPR, negate, NULL);
-             update_stmt (gsi_stmt (gsi2));
-             gsi_move_before (&gsi, &gsi2);
-             VEC_safe_push (tree, heap, plus_negates,
-                            gimple_assign_lhs (gsi_stmt (gsi2)));
-           }
-         else
-           {
-             /* Transform "x = -a; y = b - x" into "y = b + a", getting
-                rid of one operation.  */
-             gimple feed = SSA_NAME_DEF_STMT (negate);
-             tree a = gimple_assign_rhs1 (feed);
-             tree rhs1 = gimple_assign_rhs1 (user);
-             gimple_stmt_iterator gsi = gsi_for_stmt (user);
-             gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, rhs1, a);
-             update_stmt (gsi_stmt (gsi));
-           }
-       }
     }
 }
 
-/* Returns true if OP is of a type for which we can do reassociation.
-   That is for integral or non-saturating fixed-point types, and for
-   floating point type when associative-math is enabled.  */
-
-static bool
-can_reassociate_p (tree op)
-{
-  tree type = TREE_TYPE (op);
-  if (INTEGRAL_TYPE_P (type)
-      || NON_SAT_FIXED_POINT_TYPE_P (type)
-      || (flag_associative_math && FLOAT_TYPE_P (type)))
-    return true;
-  return false;
-}
-
 /* Break up subtract operations in block BB.
 
    We do this top down because we don't know whether the subtract is
@@ -1981,15 +1768,27 @@ break_up_subtract_bb (basic_block bb)
       gimple stmt = gsi_stmt (gsi);
       gimple_set_visited (stmt, false);
 
-      if (!is_gimple_assign (stmt)
-         || !can_reassociate_p (gimple_assign_lhs (stmt)))
-       continue;
-
       /* Look for simple gimple subtract operations.  */
-      if (gimple_assign_rhs_code (stmt) == MINUS_EXPR)
+      if (is_gimple_assign (stmt)
+         && gimple_assign_rhs_code (stmt) == MINUS_EXPR)
        {
-         if (!can_reassociate_p (gimple_assign_rhs1 (stmt))
-             || !can_reassociate_p (gimple_assign_rhs2 (stmt)))
+         tree lhs = gimple_assign_lhs (stmt);
+         tree rhs1 = gimple_assign_rhs1 (stmt);
+         tree rhs2 = gimple_assign_rhs2 (stmt);
+
+         /* If associative-math we can do reassociation for
+            non-integral types.  Or, we can do reassociation for
+            non-saturating fixed-point types.  */
+         if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+              || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+              || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
+             && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
+                 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
+                 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
+                 || !flag_associative_math)
+             && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
+                 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
+                 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
            continue;
 
          /* Check for a subtract used only in an addition.  If this
@@ -1999,9 +1798,6 @@ break_up_subtract_bb (basic_block bb)
          if (should_break_up_subtract (stmt))
            break_up_subtract (stmt, &gsi);
        }
-      else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR
-              && can_reassociate_p (gimple_assign_rhs1 (stmt)))
-       VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt));
     }
   for (son = first_dom_son (CDI_DOMINATORS, bb);
        son;
@@ -2062,9 +1858,19 @@ reassociate_bb (basic_block bb)
          rhs1 = gimple_assign_rhs1 (stmt);
          rhs2 = gimple_assign_rhs2 (stmt);
 
-         if (!can_reassociate_p (lhs)
-             || !can_reassociate_p (rhs1)
-             || !can_reassociate_p (rhs2))
+         /* If associative-math we can do reassociation for
+            non-integral types.  Or, we can do reassociation for
+            non-saturating fixed-point types.  */
+         if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+              || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+              || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
+             && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
+                 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
+                 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
+                 || !flag_associative_math)
+             && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
+                 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
+                 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
            continue;
 
          if (associative_tree_code (rhs_code))
@@ -2178,7 +1984,6 @@ init_reassoc (void)
 
   operand_entry_pool = create_alloc_pool ("operand entry pool",
                                          sizeof (struct operand_entry), 30);
-  next_operand_entry_id = 0;
 
   /* Reverse RPO (Reverse Post Order) will give us something where
      deeper loops come later.  */