gcc/tree-ssa-reassoc.c

   1 /* Reassociation for trees.
   2    Copyright (C) 2005, 2007 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "basic-block.h"
  29 #include "diagnostic.h"
  30 #include "tree-inline.h"
  31 #include "tree-flow.h"
  32 #include "tree-gimple.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "tree-iterator.h"
  36 #include "tree-pass.h"
  37 #include "alloc-pool.h"
  38 #include "vec.h"
  39 #include "langhooks.h"
  40 #include "pointer-set.h"
  41 #include "cfgloop.h"
  42
  43 /*  This is a simple global reassociation pass.  It is, in part, based
  44     on the LLVM pass of the same name (They do some things more/less
  45     than we do, in different orders, etc).
  46
  47     It consists of five steps:
  48
  49     1. Breaking up subtract operations into addition + negate, where
  50     it would promote the reassociation of adds.
  51
  52     2. Left linearization of the expression trees, so that (A+B)+(C+D)
  53     becomes (((A+B)+C)+D), which is easier for us to rewrite later.
  54     During linearization, we place the operands of the binary
  55     expressions into a vector of operand_entry_t
  56
  57     3. Optimization of the operand lists, eliminating things like a +
  58     -a, a & a, etc.
  59
  60     4. Rewrite the expression trees we linearized and optimized so
  61     they are in proper rank order.
  62
  63     5. Repropagate negates, as nothing else will clean it up ATM.
  64
  65     A bit of theory on #4, since nobody seems to write anything down
  66     about why it makes sense to do it the way they do it:
  67
  68     We could do this much nicer theoretically, but don't (for reasons
  69     explained after how to do it theoretically nice :P).
  70
  71     In order to promote the most redundancy elimination, you want
  72     binary expressions whose operands are the same rank (or
  73     preferably, the same value) exposed to the redundancy eliminator,
  74     for possible elimination.
  75
  76     So the way to do this if we really cared, is to build the new op
  77     tree from the leaves to the roots, merging as you go, and putting the
  78     new op on the end of the worklist, until you are left with one
  79     thing on the worklist.
  80
  81     IE if you have to rewrite the following set of operands (listed with
  82     rank in parentheses), with opcode PLUS_EXPR:
  83
  84     a (1),  b (1),  c (1),  d (2), e (2)
  85
  86
  87     We start with our merge worklist empty, and the ops list with all of
  88     those on it.
  89
  90     You want to first merge all leaves of the same rank, as much as
  91     possible.
  92
  93     So first build a binary op of
  94
  95     mergetmp = a + b, and put "mergetmp" on the merge worklist.
  96
  97     Because there is no three operand form of PLUS_EXPR, c is not going to
  98     be exposed to redundancy elimination as a rank 1 operand.
  99
 100     So you might as well throw it on the merge worklist (you could also
 101     consider it to now be a rank two operand, and merge it with d and e,
 102     but in this case, you then have evicted e from a binary op. So at
 103     least in this situation, you can't win.)
 104
 105     Then build a binary op of d + e
 106     mergetmp2 = d + e
 107
 108     and put mergetmp2 on the merge worklist.
 109
 110     so merge worklist = {mergetmp, c, mergetmp2}
 111
 112     Continue building binary ops of these operations until you have only
 113     one operation left on the worklist.
 114
 115     So we have
 116
 117     build binary op
 118     mergetmp3 = mergetmp + c
 119
 120     worklist = {mergetmp2, mergetmp3}
 121
 122     mergetmp4 = mergetmp2 + mergetmp3
 123
 124     worklist = {mergetmp4}
 125
 126     because we have one operation left, we can now just set the original
 127     statement equal to the result of that operation.
 128
 129     This will at least expose a + b  and d + e to redundancy elimination
 130     as binary operations.
 131
 132     For extra points, you can reuse the old statements to build the
 133     mergetmps, since you shouldn't run out.
 134
 135     So why don't we do this?
 136
 137     Because it's expensive, and rarely will help.  Most trees we are
 138     reassociating have 3 or less ops.  If they have 2 ops, they already
 139     will be written into a nice single binary op.  If you have 3 ops, a
 140     single simple check suffices to tell you whether the first two are of the
 141     same rank.  If so, you know to order it
 142
 143     mergetmp = op1 + op2
 144     newstmt = mergetmp + op3
 145
 146     instead of
 147     mergetmp = op2 + op3
 148     newstmt = mergetmp + op1
 149
 150     If all three are of the same rank, you can't expose them all in a
 151     single binary operator anyway, so the above is *still* the best you
 152     can do.
 153
 154     Thus, this is what we do.  When we have three ops left, we check to see
 155     what order to put them in, and call it a day.  As a nod to vector sum
 156     reduction, we check if any of ops are a really a phi node that is a
 157     destructive update for the associating op, and keep the destructive
 158     update together for vector sum reduction recognition.  */
 159
 160
 161 /* Statistics */
 162 static struct
 163 {
 164   int linearized;
 165   int constants_eliminated;
 166   int ops_eliminated;
 167   int rewritten;
 168 } reassociate_stats;
 169
 170 /* Operator, rank pair.  */
 171 typedef struct operand_entry
 172 {
 173   unsigned int rank;
 174   tree op;
 175 } *operand_entry_t;
 176
 177 static alloc_pool operand_entry_pool;
 178
 179
 180 /* Starting rank number for a given basic block, so that we can rank
 181    operations using unmovable instructions in that BB based on the bb
 182    depth.  */
 183 static long *bb_rank;
 184
 185 /* Operand->rank hashtable.  */
 186 static struct pointer_map_t *operand_rank;
 187
 188
 189 /* Look up the operand rank structure for expression E.  */
 190
 191 static inline long
 192 find_operand_rank (tree e)
 193 {
 194   void **slot = pointer_map_contains (operand_rank, e);
 195   return slot ? (long) *slot : -1;
 196 }
 197
 198 /* Insert {E,RANK} into the operand rank hashtable.  */
 199
 200 static inline void
 201 insert_operand_rank (tree e, long rank)
 202 {
 203   void **slot;
 204   gcc_assert (rank > 0);
 205   slot = pointer_map_insert (operand_rank, e);
 206   gcc_assert (!*slot);
 207   *slot = (void *) rank;
 208 }
 209
 210 /* Given an expression E, return the rank of the expression.  */
 211
 212 static long
 213 get_rank (tree e)
 214 {
 215   /* Constants have rank 0.  */
 216   if (is_gimple_min_invariant (e))
 217     return 0;
 218
 219   /* SSA_NAME's have the rank of the expression they are the result
 220      of.
 221      For globals and uninitialized values, the rank is 0.
 222      For function arguments, use the pre-setup rank.
 223      For PHI nodes, stores, asm statements, etc, we use the rank of
 224      the BB.
 225      For simple operations, the rank is the maximum rank of any of
 226      its operands, or the bb_rank, whichever is less.
 227      I make no claims that this is optimal, however, it gives good
 228      results.  */
 229
 230   if (TREE_CODE (e) == SSA_NAME)
 231     {
 232       tree stmt;
 233       tree rhs;
 234       long rank, maxrank;
 235       int i;
 236       int n;
 237
 238       if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
 239           && SSA_NAME_IS_DEFAULT_DEF (e))
 240         return find_operand_rank (e);
 241
 242       stmt = SSA_NAME_DEF_STMT (e);
 243       if (bb_for_stmt (stmt) == NULL)
 244         return 0;
 245
 246       if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
 247           || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 248         return bb_rank[bb_for_stmt (stmt)->index];
 249
 250       /* If we already have a rank for this expression, use that.  */
 251       rank = find_operand_rank (e);
 252       if (rank != -1)
 253         return rank;
 254
 255       /* Otherwise, find the maximum rank for the operands, or the bb
 256          rank, whichever is less.   */
 257       rank = 0;
 258       maxrank = bb_rank[bb_for_stmt(stmt)->index];
 259       rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 260       n = TREE_OPERAND_LENGTH (rhs);
 261       if (n == 0)
 262         rank = MAX (rank, get_rank (rhs));
 263       else
 264         {
 265           for (i = 0;
 266                i < n
 267                  && TREE_OPERAND (rhs, i)
 268                  && rank != maxrank;
 269                i++)
 270             rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
 271         }
 272
 273       if (dump_file && (dump_flags & TDF_DETAILS))
 274         {
 275           fprintf (dump_file, "Rank for ");
 276           print_generic_expr (dump_file, e, 0);
 277           fprintf (dump_file, " is %ld\n", (rank + 1));
 278         }
 279
 280       /* Note the rank in the hashtable so we don't recompute it.  */
 281       insert_operand_rank (e, (rank + 1));
 282       return (rank + 1);
 283     }
 284
 285   /* Globals, etc,  are rank 0 */
 286   return 0;
 287 }
 288
 289 DEF_VEC_P(operand_entry_t);
 290 DEF_VEC_ALLOC_P(operand_entry_t, heap);
 291
 292 /* We want integer ones to end up last no matter what, since they are
 293    the ones we can do the most with.  */
 294 #define INTEGER_CONST_TYPE 1 << 3
 295 #define FLOAT_CONST_TYPE 1 << 2
 296 #define OTHER_CONST_TYPE 1 << 1
 297
 298 /* Classify an invariant tree into integer, float, or other, so that
 299    we can sort them to be near other constants of the same type.  */
 300 static inline int
 301 constant_type (tree t)
 302 {
 303   if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
 304     return INTEGER_CONST_TYPE;
 305   else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
 306     return FLOAT_CONST_TYPE;
 307   else
 308     return OTHER_CONST_TYPE;
 309 }
 310
 311 /* qsort comparison function to sort operand entries PA and PB by rank
 312    so that the sorted array is ordered by rank in decreasing order.  */
 313 static int
 314 sort_by_operand_rank (const void *pa, const void *pb)
 315 {
 316   const operand_entry_t oea = *(const operand_entry_t *)pa;
 317   const operand_entry_t oeb = *(const operand_entry_t *)pb;
 318
 319   /* It's nicer for optimize_expression if constants that are likely
 320      to fold when added/multiplied//whatever are put next to each
 321      other.  Since all constants have rank 0, order them by type.  */
 322   if (oeb->rank == 0 &&  oea->rank == 0)
 323     return constant_type (oeb->op) - constant_type (oea->op);
 324
 325   /* Lastly, make sure the versions that are the same go next to each
 326      other.  We use SSA_NAME_VERSION because it's stable.  */
 327   if ((oeb->rank - oea->rank == 0)
 328       && TREE_CODE (oea->op) == SSA_NAME
 329       && TREE_CODE (oeb->op) == SSA_NAME)
 330     return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
 331
 332   return oeb->rank - oea->rank;
 333 }
 334
 335 /* Add an operand entry to *OPS for the tree operand OP.  */
 336
 337 static void
 338 add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
 339 {
 340   operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
 341
 342   oe->op = op;
 343   oe->rank = get_rank (op);
 344   VEC_safe_push (operand_entry_t, heap, *ops, oe);
 345 }
 346
 347 /* Return true if STMT is reassociable operation containing a binary
 348    operation with tree code CODE, and is inside LOOP.  */
 349
 350 static bool
 351 is_reassociable_op (tree stmt, enum tree_code code, struct loop *loop)
 352 {
 353   basic_block bb;
 354
 355   if (IS_EMPTY_STMT (stmt))
 356     return false;
 357
 358   bb = bb_for_stmt (stmt);
 359   if (!flow_bb_inside_loop_p (loop, bb))
 360     return false;
 361
 362   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 363       && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == code
 364       && has_single_use (GIMPLE_STMT_OPERAND (stmt, 0)))
 365     return true;
 366   return false;
 367 }
 368
 369
 370 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
 371    operand of the negate operation.  Otherwise, return NULL.  */
 372
 373 static tree
 374 get_unary_op (tree name, enum tree_code opcode)
 375 {
 376   tree stmt = SSA_NAME_DEF_STMT (name);
 377   tree rhs;
 378
 379   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 380     return NULL_TREE;
 381
 382   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 383   if (TREE_CODE (rhs) == opcode)
 384     return TREE_OPERAND (rhs, 0);
 385   return NULL_TREE;
 386 }
 387
 388 /* If CURR and LAST are a pair of ops that OPCODE allows us to
 389    eliminate through equivalences, do so, remove them from OPS, and
 390    return true.  Otherwise, return false.  */
 391
 392 static bool
 393 eliminate_duplicate_pair (enum tree_code opcode,
 394                           VEC (operand_entry_t, heap) **ops,
 395                           bool *all_done,
 396                           unsigned int i,
 397                           operand_entry_t curr,
 398                           operand_entry_t last)
 399 {
 400
 401   /* If we have two of the same op, and the opcode is & |, min, or max,
 402      we can eliminate one of them.
 403      If we have two of the same op, and the opcode is ^, we can
 404      eliminate both of them.  */
 405
 406   if (last && last->op == curr->op)
 407     {
 408       switch (opcode)
 409         {
 410         case MAX_EXPR:
 411         case MIN_EXPR:
 412         case BIT_IOR_EXPR:
 413         case BIT_AND_EXPR:
 414           if (dump_file && (dump_flags & TDF_DETAILS))
 415             {
 416               fprintf (dump_file, "Equivalence: ");
 417               print_generic_expr (dump_file, curr->op, 0);
 418               fprintf (dump_file, " [&|minmax] ");
 419               print_generic_expr (dump_file, last->op, 0);
 420               fprintf (dump_file, " -> ");
 421               print_generic_stmt (dump_file, last->op, 0);
 422             }
 423
 424           VEC_ordered_remove (operand_entry_t, *ops, i);
 425           reassociate_stats.ops_eliminated ++;
 426
 427           return true;
 428
 429         case BIT_XOR_EXPR:
 430           if (dump_file && (dump_flags & TDF_DETAILS))
 431             {
 432               fprintf (dump_file, "Equivalence: ");
 433               print_generic_expr (dump_file, curr->op, 0);
 434               fprintf (dump_file, " ^ ");
 435               print_generic_expr (dump_file, last->op, 0);
 436               fprintf (dump_file, " -> nothing\n");
 437             }
 438
 439           reassociate_stats.ops_eliminated += 2;
 440
 441           if (VEC_length (operand_entry_t, *ops) == 2)
 442             {
 443               VEC_free (operand_entry_t, heap, *ops);
 444               *ops = NULL;
 445               add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
 446                                                  integer_zero_node));
 447               *all_done = true;
 448             }
 449           else
 450             {
 451               VEC_ordered_remove (operand_entry_t, *ops, i-1);
 452               VEC_ordered_remove (operand_entry_t, *ops, i-1);
 453             }
 454
 455           return true;
 456
 457         default:
 458           break;
 459         }
 460     }
 461   return false;
 462 }
 463
 464 /* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
 465    look in OPS for a corresponding positive operation to cancel it
 466    out.  If we find one, remove the other from OPS, replace
 467    OPS[CURRINDEX] with 0, and return true.  Otherwise, return
 468    false. */
 469
 470 static bool
 471 eliminate_plus_minus_pair (enum tree_code opcode,
 472                            VEC (operand_entry_t, heap) **ops,
 473                            unsigned int currindex,
 474                            operand_entry_t curr)
 475 {
 476   tree negateop;
 477   unsigned int i;
 478   operand_entry_t oe;
 479
 480   if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
 481     return false;
 482
 483   negateop = get_unary_op (curr->op, NEGATE_EXPR);
 484   if (negateop == NULL_TREE)
 485     return false;
 486
 487   /* Any non-negated version will have a rank that is one less than
 488      the current rank.  So once we hit those ranks, if we don't find
 489      one, we can stop.  */
 490
 491   for (i = currindex + 1;
 492        VEC_iterate (operand_entry_t, *ops, i, oe)
 493        && oe->rank >= curr->rank - 1 ;
 494        i++)
 495     {
 496       if (oe->op == negateop)
 497         {
 498
 499           if (dump_file && (dump_flags & TDF_DETAILS))
 500             {
 501               fprintf (dump_file, "Equivalence: ");
 502               print_generic_expr (dump_file, negateop, 0);
 503               fprintf (dump_file, " + -");
 504               print_generic_expr (dump_file, oe->op, 0);
 505               fprintf (dump_file, " -> 0\n");
 506             }
 507
 508           VEC_ordered_remove (operand_entry_t, *ops, i);
 509           add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
 510                                             integer_zero_node));
 511           VEC_ordered_remove (operand_entry_t, *ops, currindex);
 512           reassociate_stats.ops_eliminated ++;
 513
 514           return true;
 515         }
 516     }
 517
 518   return false;
 519 }
 520
 521 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
 522    bitwise not expression, look in OPS for a corresponding operand to
 523    cancel it out.  If we find one, remove the other from OPS, replace
 524    OPS[CURRINDEX] with 0, and return true.  Otherwise, return
 525    false. */
 526
 527 static bool
 528 eliminate_not_pairs (enum tree_code opcode,
 529                      VEC (operand_entry_t, heap) **ops,
 530                      unsigned int currindex,
 531                      operand_entry_t curr)
 532 {
 533   tree notop;
 534   unsigned int i;
 535   operand_entry_t oe;
 536
 537   if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
 538       || TREE_CODE (curr->op) != SSA_NAME)
 539     return false;
 540
 541   notop = get_unary_op (curr->op, BIT_NOT_EXPR);
 542   if (notop == NULL_TREE)
 543     return false;
 544
 545   /* Any non-not version will have a rank that is one less than
 546      the current rank.  So once we hit those ranks, if we don't find
 547      one, we can stop.  */
 548
 549   for (i = currindex + 1;
 550        VEC_iterate (operand_entry_t, *ops, i, oe)
 551        && oe->rank >= curr->rank - 1;
 552        i++)
 553     {
 554       if (oe->op == notop)
 555         {
 556           if (dump_file && (dump_flags & TDF_DETAILS))
 557             {
 558               fprintf (dump_file, "Equivalence: ");
 559               print_generic_expr (dump_file, notop, 0);
 560               if (opcode == BIT_AND_EXPR)
 561                 fprintf (dump_file, " & ~");
 562               else if (opcode == BIT_IOR_EXPR)
 563                 fprintf (dump_file, " | ~");
 564               print_generic_expr (dump_file, oe->op, 0);
 565               if (opcode == BIT_AND_EXPR)
 566                 fprintf (dump_file, " -> 0\n");
 567               else if (opcode == BIT_IOR_EXPR)
 568                 fprintf (dump_file, " -> -1\n");
 569             }
 570
 571           if (opcode == BIT_AND_EXPR)
 572             oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
 573           else if (opcode == BIT_IOR_EXPR)
 574             oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
 575                                           TYPE_PRECISION (TREE_TYPE (oe->op)));
 576
 577           reassociate_stats.ops_eliminated
 578             += VEC_length (operand_entry_t, *ops) - 1;
 579           VEC_free (operand_entry_t, heap, *ops);
 580           *ops = NULL;
 581           VEC_safe_push (operand_entry_t, heap, *ops, oe);
 582           return true;
 583         }
 584     }
 585
 586   return false;
 587 }
 588
 589 /* Use constant value that may be present in OPS to try to eliminate
 590    operands.  Note that this function is only really used when we've
 591    eliminated ops for other reasons, or merged constants.  Across
 592    single statements, fold already does all of this, plus more.  There
 593    is little point in duplicating logic, so I've only included the
 594    identities that I could ever construct testcases to trigger.  */
 595
 596 static void
 597 eliminate_using_constants (enum tree_code opcode,
 598                            VEC(operand_entry_t, heap) **ops)
 599 {
 600   operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
 601
 602   if (oelast->rank == 0 && INTEGRAL_TYPE_P (TREE_TYPE (oelast->op)))
 603     {
 604       switch (opcode)
 605         {
 606         case BIT_AND_EXPR:
 607           if (integer_zerop (oelast->op))
 608             {
 609               if (VEC_length (operand_entry_t, *ops) != 1)
 610                 {
 611                   if (dump_file && (dump_flags & TDF_DETAILS))
 612                     fprintf (dump_file, "Found & 0, removing all other ops\n");
 613
 614                   reassociate_stats.ops_eliminated
 615                     += VEC_length (operand_entry_t, *ops) - 1;
 616
 617                   VEC_free (operand_entry_t, heap, *ops);
 618                   *ops = NULL;
 619                   VEC_safe_push (operand_entry_t, heap, *ops, oelast);
 620                   return;
 621                 }
 622             }
 623           else if (integer_all_onesp (oelast->op))
 624             {
 625               if (VEC_length (operand_entry_t, *ops) != 1)
 626                 {
 627                   if (dump_file && (dump_flags & TDF_DETAILS))
 628                     fprintf (dump_file, "Found & -1, removing\n");
 629                   VEC_pop (operand_entry_t, *ops);
 630                   reassociate_stats.ops_eliminated++;
 631                 }
 632             }
 633           break;
 634         case BIT_IOR_EXPR:
 635           if (integer_all_onesp (oelast->op))
 636             {
 637               if (VEC_length (operand_entry_t, *ops) != 1)
 638                 {
 639                   if (dump_file && (dump_flags & TDF_DETAILS))
 640                     fprintf (dump_file, "Found | -1, removing all other ops\n");
 641
 642                   reassociate_stats.ops_eliminated
 643                     += VEC_length (operand_entry_t, *ops) - 1;
 644
 645                   VEC_free (operand_entry_t, heap, *ops);
 646                   *ops = NULL;
 647                   VEC_safe_push (operand_entry_t, heap, *ops, oelast);
 648                   return;
 649                 }
 650             }
 651           else if (integer_zerop (oelast->op))
 652             {
 653               if (VEC_length (operand_entry_t, *ops) != 1)
 654                 {
 655                   if (dump_file && (dump_flags & TDF_DETAILS))
 656                     fprintf (dump_file, "Found | 0, removing\n");
 657                   VEC_pop (operand_entry_t, *ops);
 658                   reassociate_stats.ops_eliminated++;
 659                 }
 660             }
 661           break;
 662         case MULT_EXPR:
 663           if (integer_zerop (oelast->op))
 664             {
 665               if (VEC_length (operand_entry_t, *ops) != 1)
 666                 {
 667                   if (dump_file && (dump_flags & TDF_DETAILS))
 668                     fprintf (dump_file, "Found * 0, removing all other ops\n");
 669
 670                   reassociate_stats.ops_eliminated
 671                     += VEC_length (operand_entry_t, *ops) - 1;
 672                   VEC_free (operand_entry_t, heap, *ops);
 673                   *ops = NULL;
 674                   VEC_safe_push (operand_entry_t, heap, *ops, oelast);
 675                   return;
 676                 }
 677             }
 678           else if (integer_onep (oelast->op))
 679             {
 680               if (VEC_length (operand_entry_t, *ops) != 1)
 681                 {
 682                   if (dump_file && (dump_flags & TDF_DETAILS))
 683                     fprintf (dump_file, "Found * 1, removing\n");
 684                   VEC_pop (operand_entry_t, *ops);
 685                   reassociate_stats.ops_eliminated++;
 686                   return;
 687                 }
 688             }
 689           break;
 690         case BIT_XOR_EXPR:
 691         case PLUS_EXPR:
 692         case MINUS_EXPR:
 693           if (integer_zerop (oelast->op))
 694             {
 695               if (VEC_length (operand_entry_t, *ops) != 1)
 696                 {
 697                   if (dump_file && (dump_flags & TDF_DETAILS))
 698                     fprintf (dump_file, "Found [|^+] 0, removing\n");
 699                   VEC_pop (operand_entry_t, *ops);
 700                   reassociate_stats.ops_eliminated++;
 701                   return;
 702                 }
 703             }
 704           break;
 705         default:
 706           break;
 707         }
 708     }
 709 }
 710
 711 /* Perform various identities and other optimizations on the list of
 712    operand entries, stored in OPS.  The tree code for the binary
 713    operation between all the operands is OPCODE.  */
 714
 715 static void
 716 optimize_ops_list (enum tree_code opcode,
 717                    VEC (operand_entry_t, heap) **ops)
 718 {
 719   unsigned int length = VEC_length (operand_entry_t, *ops);
 720   unsigned int i;
 721   operand_entry_t oe;
 722   operand_entry_t oelast = NULL;
 723   bool iterate = false;
 724
 725   if (length == 1)
 726     return;
 727
 728   oelast = VEC_last (operand_entry_t, *ops);
 729
 730   /* If the last two are constants, pop the constants off, merge them
 731      and try the next two.  */
 732   if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
 733     {
 734       operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
 735
 736       if (oelm1->rank == 0
 737           && is_gimple_min_invariant (oelm1->op)
 738           && useless_type_conversion_p (TREE_TYPE (oelm1->op),
 739                                        TREE_TYPE (oelast->op)))
 740         {
 741           tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
 742                                      oelm1->op, oelast->op);
 743
 744           if (folded && is_gimple_min_invariant (folded))
 745             {
 746               if (dump_file && (dump_flags & TDF_DETAILS))
 747                 fprintf (dump_file, "Merging constants\n");
 748
 749               VEC_pop (operand_entry_t, *ops);
 750               VEC_pop (operand_entry_t, *ops);
 751
 752               add_to_ops_vec (ops, folded);
 753               reassociate_stats.constants_eliminated++;
 754
 755               optimize_ops_list (opcode, ops);
 756               return;
 757             }
 758         }
 759     }
 760
 761   eliminate_using_constants (opcode, ops);
 762   oelast = NULL;
 763
 764   for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
 765     {
 766       bool done = false;
 767
 768       if (eliminate_not_pairs (opcode, ops, i, oe))
 769         return;
 770       if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
 771           || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
 772         {
 773           if (done)
 774             return;
 775           iterate = true;
 776           oelast = NULL;
 777           continue;
 778         }
 779       oelast = oe;
 780       i++;
 781     }
 782
 783   length  = VEC_length (operand_entry_t, *ops);
 784   oelast = VEC_last (operand_entry_t, *ops);
 785
 786   if (iterate)
 787     optimize_ops_list (opcode, ops);
 788 }
 789
 790 /* Return true if OPERAND is defined by a PHI node which uses the LHS
 791    of STMT in it's operands.  This is also known as a "destructive
 792    update" operation.  */
 793
 794 static bool
 795 is_phi_for_stmt (tree stmt, tree operand)
 796 {
 797   tree def_stmt;
 798   tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 799   use_operand_p arg_p;
 800   ssa_op_iter i;
 801
 802   if (TREE_CODE (operand) != SSA_NAME)
 803     return false;
 804
 805   def_stmt = SSA_NAME_DEF_STMT (operand);
 806   if (TREE_CODE (def_stmt) != PHI_NODE)
 807     return false;
 808
 809   FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
 810     if (lhs == USE_FROM_PTR (arg_p))
 811       return true;
 812   return false;
 813 }
 814
 815 /* Recursively rewrite our linearized statements so that the operators
 816    match those in OPS[OPINDEX], putting the computation in rank
 817    order.  */
 818
 819 static void
 820 rewrite_expr_tree (tree stmt, unsigned int opindex,
 821                    VEC(operand_entry_t, heap) * ops)
 822 {
 823   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 824   operand_entry_t oe;
 825
 826   /* If we have three operands left, then we want to make sure the one
 827      that gets the double binary op are the ones with the same rank.
 828
 829      The alternative we try is to see if this is a destructive
 830      update style statement, which is like:
 831      b = phi (a, ...)
 832      a = c + b;
 833      In that case, we want to use the destructive update form to
 834      expose the possible vectorizer sum reduction opportunity.
 835      In that case, the third operand will be the phi node.
 836
 837      We could, of course, try to be better as noted above, and do a
 838      lot of work to try to find these opportunities in >3 operand
 839      cases, but it is unlikely to be worth it.  */
 840   if (opindex + 3 == VEC_length (operand_entry_t, ops))
 841     {
 842       operand_entry_t oe1, oe2, oe3;
 843
 844       oe1 = VEC_index (operand_entry_t, ops, opindex);
 845       oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
 846       oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
 847
 848       if ((oe1->rank == oe2->rank
 849            && oe2->rank != oe3->rank)
 850           || (is_phi_for_stmt (stmt, oe3->op)
 851               && !is_phi_for_stmt (stmt, oe1->op)
 852               && !is_phi_for_stmt (stmt, oe2->op)))
 853         {
 854           struct operand_entry temp = *oe3;
 855           oe3->op = oe1->op;
 856           oe3->rank = oe1->rank;
 857           oe1->op = temp.op;
 858           oe1->rank= temp.rank;
 859         }
 860     }
 861
 862   /* The final recursion case for this function is that you have
 863      exactly two operations left.
 864      If we had one exactly one op in the entire list to start with, we
 865      would have never called this function, and the tail recursion
 866      rewrites them one at a time.  */
 867   if (opindex + 2 == VEC_length (operand_entry_t, ops))
 868     {
 869       operand_entry_t oe1, oe2;
 870
 871       oe1 = VEC_index (operand_entry_t, ops, opindex);
 872       oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
 873
 874       if (TREE_OPERAND (rhs, 0) != oe1->op
 875           || TREE_OPERAND (rhs, 1) != oe2->op)
 876         {
 877
 878           if (dump_file && (dump_flags & TDF_DETAILS))
 879             {
 880               fprintf (dump_file, "Transforming ");
 881               print_generic_expr (dump_file, rhs, 0);
 882             }
 883
 884           TREE_OPERAND (rhs, 0) = oe1->op;
 885           TREE_OPERAND (rhs, 1) = oe2->op;
 886           update_stmt (stmt);
 887
 888           if (dump_file && (dump_flags & TDF_DETAILS))
 889             {
 890               fprintf (dump_file, " into ");
 891               print_generic_stmt (dump_file, rhs, 0);
 892             }
 893
 894         }
 895       return;
 896     }
 897
 898   /* If we hit here, we should have 3 or more ops left.  */
 899   gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
 900
 901   /* Rewrite the next operator.  */
 902   oe = VEC_index (operand_entry_t, ops, opindex);
 903
 904   if (oe->op != TREE_OPERAND (rhs, 1))
 905     {
 906
 907       if (dump_file && (dump_flags & TDF_DETAILS))
 908         {
 909           fprintf (dump_file, "Transforming ");
 910           print_generic_expr (dump_file, rhs, 0);
 911         }
 912
 913       TREE_OPERAND (rhs, 1) = oe->op;
 914       update_stmt (stmt);
 915
 916       if (dump_file && (dump_flags & TDF_DETAILS))
 917         {
 918           fprintf (dump_file, " into ");
 919           print_generic_stmt (dump_file, rhs, 0);
 920         }
 921     }
 922   /* Recurse on the LHS of the binary operator, which is guaranteed to
 923      be the non-leaf side.  */
 924   rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)),
 925                      opindex + 1, ops);
 926 }
 927
 928 /* Transform STMT, which is really (A +B) + (C + D) into the left
 929    linear form, ((A+B)+C)+D.
 930    Recurse on D if necessary.  */
 931
 932 static void
 933 linearize_expr (tree stmt)
 934 {
 935   block_stmt_iterator bsinow, bsirhs;
 936   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 937   enum tree_code rhscode = TREE_CODE (rhs);
 938   tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 939   tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 940   tree newbinrhs = NULL_TREE;
 941   struct loop *loop = loop_containing_stmt (stmt);
 942
 943   gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs), loop)
 944               && is_reassociable_op (binrhs, TREE_CODE (rhs), loop));
 945
 946   bsinow = bsi_for_stmt (stmt);
 947   bsirhs = bsi_for_stmt (binrhs);
 948   bsi_move_before (&bsirhs, &bsinow);
 949
 950   TREE_OPERAND (rhs, 1) = TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs, 1), 0);
 951   if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME)
 952     newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 953   TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs, 1), 0)
 954     = GIMPLE_STMT_OPERAND (binlhs, 0);
 955   TREE_OPERAND (rhs, 0) = GIMPLE_STMT_OPERAND (binrhs, 0);
 956
 957   if (dump_file && (dump_flags & TDF_DETAILS))
 958     {
 959       fprintf (dump_file, "Linearized: ");
 960       print_generic_stmt (dump_file, rhs, 0);
 961     }
 962
 963   reassociate_stats.linearized++;
 964   update_stmt (binrhs);
 965   update_stmt (binlhs);
 966   update_stmt (stmt);
 967   TREE_VISITED (binrhs) = 1;
 968   TREE_VISITED (binlhs) = 1;
 969   TREE_VISITED (stmt) = 1;
 970
 971   /* Tail recurse on the new rhs if it still needs reassociation.  */
 972   if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
 973     linearize_expr (stmt);
 974 }
 975
 976 /* If LHS has a single immediate use that is a GIMPLE_MODIFY_STMT, return
 977    it.  Otherwise, return NULL.  */
 978
 979 static tree
 980 get_single_immediate_use (tree lhs)
 981 {
 982   use_operand_p immuse;
 983   tree immusestmt;
 984
 985   if (TREE_CODE (lhs) == SSA_NAME
 986       && single_imm_use (lhs, &immuse, &immusestmt))
 987     {
 988       if (TREE_CODE (immusestmt) == RETURN_EXPR)
 989         immusestmt = TREE_OPERAND (immusestmt, 0);
 990       if (TREE_CODE (immusestmt) == GIMPLE_MODIFY_STMT)
 991         return immusestmt;
 992     }
 993   return NULL_TREE;
 994 }
 995 static VEC(tree, heap) *broken_up_subtracts;
 996
 997
 998 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
 999    representing the negated value.  Insertions of any necessary
1000    instructions go before BSI.
1001    This function is recursive in that, if you hand it "a_5" as the
1002    value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1003    transform b_3 + b_4 into a_5 = -b_3 + -b_4.  */
1004
1005 static tree
1006 negate_value (tree tonegate, block_stmt_iterator *bsi)
1007 {
1008   tree negatedef = tonegate;
1009   tree resultofnegate;
1010
1011   if (TREE_CODE (tonegate) == SSA_NAME)
1012     negatedef = SSA_NAME_DEF_STMT (tonegate);
1013
1014   /* If we are trying to negate a name, defined by an add, negate the
1015      add operands instead.  */
1016   if (TREE_CODE (tonegate) == SSA_NAME
1017       && TREE_CODE (negatedef) == GIMPLE_MODIFY_STMT
1018       && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef, 0)) == SSA_NAME
1019       && has_single_use (GIMPLE_STMT_OPERAND (negatedef, 0))
1020       && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef, 1)) == PLUS_EXPR)
1021     {
1022       block_stmt_iterator bsi;
1023       tree binop = GIMPLE_STMT_OPERAND (negatedef, 1);
1024
1025       bsi = bsi_for_stmt (negatedef);
1026       TREE_OPERAND (binop, 0) = negate_value (TREE_OPERAND (binop, 0),
1027                                               &bsi);
1028       bsi = bsi_for_stmt (negatedef);
1029       TREE_OPERAND (binop, 1) = negate_value (TREE_OPERAND (binop, 1),
1030                                               &bsi);
1031       update_stmt (negatedef);
1032       return GIMPLE_STMT_OPERAND (negatedef, 0);
1033     }
1034
1035   tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
1036   resultofnegate = force_gimple_operand_bsi (bsi, tonegate, true,
1037                                              NULL_TREE, true, BSI_SAME_STMT);
1038   VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
1039   return resultofnegate;
1040
1041 }
1042
1043 /* Return true if we should break up the subtract in STMT into an add
1044    with negate.  This is true when we the subtract operands are really
1045    adds, or the subtract itself is used in an add expression.  In
1046    either case, breaking up the subtract into an add with negate
1047    exposes the adds to reassociation.  */
1048
1049 static bool
1050 should_break_up_subtract (tree stmt)
1051 {
1052
1053   tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1054   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1055   tree binlhs = TREE_OPERAND (rhs, 0);
1056   tree binrhs = TREE_OPERAND (rhs, 1);
1057   tree immusestmt;
1058   struct loop *loop = loop_containing_stmt (stmt);
1059
1060   if (TREE_CODE (binlhs) == SSA_NAME
1061       && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
1062     return true;
1063
1064   if (TREE_CODE (binrhs) == SSA_NAME
1065       && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
1066     return true;
1067
1068   if (TREE_CODE (lhs) == SSA_NAME
1069       && (immusestmt = get_single_immediate_use (lhs))
1070       && TREE_CODE (GIMPLE_STMT_OPERAND (immusestmt, 1)) == PLUS_EXPR)
1071     return true;
1072   return false;
1073
1074 }
1075
1076 /* Transform STMT from A - B into A + -B.  */
1077
1078 static void
1079 break_up_subtract (tree stmt, block_stmt_iterator *bsi)
1080 {
1081   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1082
1083   if (dump_file && (dump_flags & TDF_DETAILS))
1084     {
1085       fprintf (dump_file, "Breaking up subtract ");
1086       print_generic_stmt (dump_file, stmt, 0);
1087     }
1088
1089   TREE_SET_CODE (GIMPLE_STMT_OPERAND (stmt, 1), PLUS_EXPR);
1090   TREE_OPERAND (rhs, 1) = negate_value (TREE_OPERAND (rhs, 1), bsi);
1091
1092   update_stmt (stmt);
1093 }
1094
1095 /* Recursively linearize a binary expression that is the RHS of STMT.
1096    Place the operands of the expression tree in the vector named OPS.  */
1097
1098 static void
1099 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, tree stmt)
1100 {
1101   block_stmt_iterator bsinow, bsilhs;
1102   tree rhs = GENERIC_TREE_OPERAND (stmt, 1);
1103   tree binrhs = TREE_OPERAND (rhs, 1);
1104   tree binlhs = TREE_OPERAND (rhs, 0);
1105   tree binlhsdef, binrhsdef;
1106   bool binlhsisreassoc = false;
1107   bool binrhsisreassoc = false;
1108   enum tree_code rhscode = TREE_CODE (rhs);
1109   struct loop *loop = loop_containing_stmt (stmt);
1110
1111   TREE_VISITED (stmt) = 1;
1112
1113   if (TREE_CODE (binlhs) == SSA_NAME)
1114     {
1115       binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1116       binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
1117     }
1118
1119   if (TREE_CODE (binrhs) == SSA_NAME)
1120     {
1121       binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1122       binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
1123     }
1124
1125   /* If the LHS is not reassociable, but the RHS is, we need to swap
1126      them.  If neither is reassociable, there is nothing we can do, so
1127      just put them in the ops vector.  If the LHS is reassociable,
1128      linearize it.  If both are reassociable, then linearize the RHS
1129      and the LHS.  */
1130
1131   if (!binlhsisreassoc)
1132     {
1133       tree temp;
1134
1135       if (!binrhsisreassoc)
1136         {
1137           add_to_ops_vec (ops, binrhs);
1138           add_to_ops_vec (ops, binlhs);
1139           return;
1140         }
1141
1142       if (dump_file && (dump_flags & TDF_DETAILS))
1143         {
1144           fprintf (dump_file, "swapping operands of ");
1145           print_generic_expr (dump_file, stmt, 0);
1146         }
1147
1148       swap_tree_operands (stmt, &TREE_OPERAND (rhs, 0),
1149                           &TREE_OPERAND (rhs, 1));
1150       update_stmt (stmt);
1151
1152       if (dump_file && (dump_flags & TDF_DETAILS))
1153         {
1154           fprintf (dump_file, " is now ");
1155           print_generic_stmt (dump_file, stmt, 0);
1156         }
1157
1158       /* We want to make it so the lhs is always the reassociative op,
1159          so swap.  */
1160       temp = binlhs;
1161       binlhs = binrhs;
1162       binrhs = temp;
1163     }
1164   else if (binrhsisreassoc)
1165     {
1166       linearize_expr (stmt);
1167       gcc_assert (rhs == GIMPLE_STMT_OPERAND (stmt, 1));
1168       binlhs = TREE_OPERAND (rhs, 0);
1169       binrhs = TREE_OPERAND (rhs, 1);
1170     }
1171
1172   gcc_assert (TREE_CODE (binrhs) != SSA_NAME
1173               || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
1174                                       rhscode, loop));
1175   bsinow = bsi_for_stmt (stmt);
1176   bsilhs = bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs));
1177   bsi_move_before (&bsilhs, &bsinow);
1178   linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs));
1179   add_to_ops_vec (ops, binrhs);
1180 }
1181
1182 /* Repropagate the negates back into subtracts, since no other pass
1183    currently does it.  */
1184
1185 static void
1186 repropagate_negates (void)
1187 {
1188   unsigned int i = 0;
1189   tree negate;
1190
1191   for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
1192     {
1193       tree user = get_single_immediate_use (negate);
1194
1195       /* The negate operand can be either operand of a PLUS_EXPR
1196          (it can be the LHS if the RHS is a constant for example).
1197
1198          Force the negate operand to the RHS of the PLUS_EXPR, then
1199          transform the PLUS_EXPR into a MINUS_EXPR.  */
1200       if (user
1201           && TREE_CODE (user) == GIMPLE_MODIFY_STMT
1202           && TREE_CODE (GIMPLE_STMT_OPERAND (user, 1)) == PLUS_EXPR)
1203         {
1204           tree rhs = GIMPLE_STMT_OPERAND (user, 1);
1205
1206           /* If the negated operand appears on the LHS of the
1207              PLUS_EXPR, exchange the operands of the PLUS_EXPR
1208              to force the negated operand to the RHS of the PLUS_EXPR.  */
1209           if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user, 1), 0) == negate)
1210             {
1211               tree temp = TREE_OPERAND (rhs, 0);
1212               TREE_OPERAND (rhs, 0) = TREE_OPERAND (rhs, 1);
1213               TREE_OPERAND (rhs, 1) = temp;
1214             }
1215
1216           /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1217              the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR.  */
1218           if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user, 1), 1) == negate)
1219             {
1220               TREE_SET_CODE (rhs, MINUS_EXPR);
1221               TREE_OPERAND (rhs, 1) = get_unary_op (negate, NEGATE_EXPR);
1222               update_stmt (user);
1223             }
1224         }
1225     }
1226 }
1227
1228 /* Break up subtract operations in block BB.
1229
1230    We do this top down because we don't know whether the subtract is
1231    part of a possible chain of reassociation except at the top.
1232
1233    IE given
1234    d = f + g
1235    c = a + e
1236    b = c - d
1237    q = b - r
1238    k = t - q
1239
1240    we want to break up k = t - q, but we won't until we've transformed q
1241    = b - r, which won't be broken up until we transform b = c - d.  */
1242
1243 static void
1244 break_up_subtract_bb (basic_block bb)
1245 {
1246   block_stmt_iterator bsi;
1247   basic_block son;
1248
1249   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1250     {
1251       tree stmt = bsi_stmt (bsi);
1252
1253       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1254         {
1255           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1256           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1257
1258           TREE_VISITED (stmt) = 0;
1259           /* If associative-math we can do reassociation for
1260              non-integral types.  Or, we can do reassociation for
1261              non-saturating fixed-point types.  */
1262           if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1263                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1264               && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
1265                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
1266                   || !flag_associative_math)
1267               && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs))
1268                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs))))
1269             continue;
1270
1271           /* Check for a subtract used only in an addition.  If this
1272              is the case, transform it into add of a negate for better
1273              reassociation.  IE transform C = A-B into C = A + -B if C
1274              is only used in an addition.  */
1275           if (TREE_CODE (rhs) == MINUS_EXPR)
1276             if (should_break_up_subtract (stmt))
1277               break_up_subtract (stmt, &bsi);
1278         }
1279     }
1280   for (son = first_dom_son (CDI_DOMINATORS, bb);
1281        son;
1282        son = next_dom_son (CDI_DOMINATORS, son))
1283     break_up_subtract_bb (son);
1284 }
1285
1286 /* Reassociate expressions in basic block BB and its post-dominator as
1287    children.  */
1288
1289 static void
1290 reassociate_bb (basic_block bb)
1291 {
1292   block_stmt_iterator bsi;
1293   basic_block son;
1294
1295   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1296     {
1297       tree stmt = bsi_stmt (bsi);
1298
1299       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1300         {
1301           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1302           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1303
1304           /* If this was part of an already processed tree, we don't
1305              need to touch it again. */
1306           if (TREE_VISITED (stmt))
1307             continue;
1308
1309           /* If associative-math we can do reassociation for
1310              non-integral types.  Or, we can do reassociation for
1311              non-saturating fixed-point types.  */
1312           if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1313                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1314               && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
1315                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
1316                   || !flag_associative_math)
1317               && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs))
1318                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs))))
1319             continue;
1320
1321           if (associative_tree_code (TREE_CODE (rhs)))
1322             {
1323               VEC(operand_entry_t, heap) *ops = NULL;
1324
1325               /* There may be no immediate uses left by the time we
1326                  get here because we may have eliminated them all.  */
1327               if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
1328                 continue;
1329
1330               TREE_VISITED (stmt) = 1;
1331               linearize_expr_tree (&ops, stmt);
1332               qsort (VEC_address (operand_entry_t, ops),
1333                      VEC_length (operand_entry_t, ops),
1334                      sizeof (operand_entry_t),
1335                      sort_by_operand_rank);
1336               optimize_ops_list (TREE_CODE (rhs), &ops);
1337
1338               if (VEC_length (operand_entry_t, ops) == 1)
1339                 {
1340                   if (dump_file && (dump_flags & TDF_DETAILS))
1341                     {
1342                       fprintf (dump_file, "Transforming ");
1343                       print_generic_expr (dump_file, rhs, 0);
1344                     }
1345                   GIMPLE_STMT_OPERAND (stmt, 1)
1346                     = VEC_last (operand_entry_t, ops)->op;
1347                   update_stmt (stmt);
1348
1349                   if (dump_file && (dump_flags & TDF_DETAILS))
1350                     {
1351                       fprintf (dump_file, " into ");
1352                       print_generic_stmt (dump_file,
1353                                           GIMPLE_STMT_OPERAND (stmt, 1), 0);
1354                     }
1355                 }
1356               else
1357                 {
1358                   rewrite_expr_tree (stmt, 0, ops);
1359                 }
1360
1361               VEC_free (operand_entry_t, heap, ops);
1362             }
1363         }
1364     }
1365   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
1366        son;
1367        son = next_dom_son (CDI_POST_DOMINATORS, son))
1368     reassociate_bb (son);
1369 }
1370
1371 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
1372 void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
1373
1374 /* Dump the operand entry vector OPS to FILE.  */
1375
1376 void
1377 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
1378 {
1379   operand_entry_t oe;
1380   unsigned int i;
1381
1382   for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
1383     {
1384       fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
1385       print_generic_stmt (file, oe->op, 0);
1386     }
1387 }
1388
1389 /* Dump the operand entry vector OPS to STDERR.  */
1390
1391 void
1392 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
1393 {
1394   dump_ops_vector (stderr, ops);
1395 }
1396
1397 static void
1398 do_reassoc (void)
1399 {
1400   break_up_subtract_bb (ENTRY_BLOCK_PTR);
1401   reassociate_bb (EXIT_BLOCK_PTR);
1402 }
1403
1404 /* Initialize the reassociation pass.  */
1405
1406 static void
1407 init_reassoc (void)
1408 {
1409   int i;
1410   long rank = 2;
1411   tree param;
1412   int *bbs = XNEWVEC (int, last_basic_block + 1);
1413
1414   /* Find the loops, so that we can prevent moving calculations in
1415      them.  */
1416   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1417
1418   memset (&reassociate_stats, 0, sizeof (reassociate_stats));
1419
1420   operand_entry_pool = create_alloc_pool ("operand entry pool",
1421                                           sizeof (struct operand_entry), 30);
1422
1423   /* Reverse RPO (Reverse Post Order) will give us something where
1424      deeper loops come later.  */
1425   pre_and_rev_post_order_compute (NULL, bbs, false);
1426   bb_rank = XCNEWVEC (long, last_basic_block + 1);
1427   operand_rank = pointer_map_create ();
1428
1429   /* Give each argument a distinct rank.   */
1430   for (param = DECL_ARGUMENTS (current_function_decl);
1431        param;
1432        param = TREE_CHAIN (param))
1433     {
1434       if (gimple_default_def (cfun, param) != NULL)
1435         {
1436           tree def = gimple_default_def (cfun, param);
1437           insert_operand_rank (def, ++rank);
1438         }
1439     }
1440
1441   /* Give the chain decl a distinct rank. */
1442   if (cfun->static_chain_decl != NULL)
1443     {
1444       tree def = gimple_default_def (cfun, cfun->static_chain_decl);
1445       if (def != NULL)
1446         insert_operand_rank (def, ++rank);
1447     }
1448
1449   /* Set up rank for each BB  */
1450   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
1451     bb_rank[bbs[i]] = ++rank  << 16;
1452
1453   free (bbs);
1454   calculate_dominance_info (CDI_POST_DOMINATORS);
1455   broken_up_subtracts = NULL;
1456 }
1457
1458 /* Cleanup after the reassociation pass, and print stats if
1459    requested.  */
1460
1461 static void
1462 fini_reassoc (void)
1463 {
1464   if (dump_file && (dump_flags & TDF_STATS))
1465     {
1466       fprintf (dump_file, "Reassociation stats:\n");
1467       fprintf (dump_file, "Linearized: %d\n",
1468                reassociate_stats.linearized);
1469       fprintf (dump_file, "Constants eliminated: %d\n",
1470                reassociate_stats.constants_eliminated);
1471       fprintf (dump_file, "Ops eliminated: %d\n",
1472                reassociate_stats.ops_eliminated);
1473       fprintf (dump_file, "Statements rewritten: %d\n",
1474                reassociate_stats.rewritten);
1475     }
1476
1477   pointer_map_destroy (operand_rank);
1478   free_alloc_pool (operand_entry_pool);
1479   free (bb_rank);
1480   VEC_free (tree, heap, broken_up_subtracts);
1481   free_dominance_info (CDI_POST_DOMINATORS);
1482   loop_optimizer_finalize ();
1483 }
1484
1485 /* Gate and execute functions for Reassociation.  */
1486
1487 static unsigned int
1488 execute_reassoc (void)
1489 {
1490   init_reassoc ();
1491
1492   do_reassoc ();
1493   repropagate_negates ();
1494
1495   fini_reassoc ();
1496   return 0;
1497 }
1498
1499 static bool
1500 gate_tree_ssa_reassoc (void)
1501 {
1502   return flag_tree_reassoc != 0;
1503 }
1504
1505 struct tree_opt_pass pass_reassoc =
1506 {
1507   "reassoc",                            /* name */
1508   gate_tree_ssa_reassoc,                /* gate */
1509   execute_reassoc,                      /* execute */
1510   NULL,                                 /* sub */
1511   NULL,                                 /* next */
1512   0,                                    /* static_pass_number */
1513   TV_TREE_REASSOC,                      /* tv_id */
1514   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1515   0,                                    /* properties_provided */
1516   0,                                    /* properties_destroyed */
1517   0,                                    /* todo_flags_start */
1518   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1519   0                                     /* letter */
1520 };