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       else if ((oe1->rank == oe3->rank
 861                 && oe2->rank != oe3->rank)
 862                || (is_phi_for_stmt (stmt, oe2->op)
 863                    && !is_phi_for_stmt (stmt, oe1->op)
 864                    && !is_phi_for_stmt (stmt, oe3->op)))
 865         {
 866           struct operand_entry temp = *oe2;
 867           oe2->op = oe1->op;
 868           oe2->rank = oe1->rank;
 869           oe1->op = temp.op;
 870           oe1->rank= temp.rank;
 871         }
 872     }
 873
 874   /* The final recursion case for this function is that you have
 875      exactly two operations left.
 876      If we had one exactly one op in the entire list to start with, we
 877      would have never called this function, and the tail recursion
 878      rewrites them one at a time.  */
 879   if (opindex + 2 == VEC_length (operand_entry_t, ops))
 880     {
 881       operand_entry_t oe1, oe2;
 882
 883       oe1 = VEC_index (operand_entry_t, ops, opindex);
 884       oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
 885
 886       if (TREE_OPERAND (rhs, 0) != oe1->op
 887           || TREE_OPERAND (rhs, 1) != oe2->op)
 888         {
 889
 890           if (dump_file && (dump_flags & TDF_DETAILS))
 891             {
 892               fprintf (dump_file, "Transforming ");
 893               print_generic_expr (dump_file, rhs, 0);
 894             }
 895
 896           TREE_OPERAND (rhs, 0) = oe1->op;
 897           TREE_OPERAND (rhs, 1) = oe2->op;
 898           update_stmt (stmt);
 899
 900           if (dump_file && (dump_flags & TDF_DETAILS))
 901             {
 902               fprintf (dump_file, " into ");
 903               print_generic_stmt (dump_file, rhs, 0);
 904             }
 905
 906         }
 907       return;
 908     }
 909
 910   /* If we hit here, we should have 3 or more ops left.  */
 911   gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
 912
 913   /* Rewrite the next operator.  */
 914   oe = VEC_index (operand_entry_t, ops, opindex);
 915
 916   if (oe->op != TREE_OPERAND (rhs, 1))
 917     {
 918
 919       if (dump_file && (dump_flags & TDF_DETAILS))
 920         {
 921           fprintf (dump_file, "Transforming ");
 922           print_generic_expr (dump_file, rhs, 0);
 923         }
 924
 925       TREE_OPERAND (rhs, 1) = oe->op;
 926       update_stmt (stmt);
 927
 928       if (dump_file && (dump_flags & TDF_DETAILS))
 929         {
 930           fprintf (dump_file, " into ");
 931           print_generic_stmt (dump_file, rhs, 0);
 932         }
 933     }
 934   /* Recurse on the LHS of the binary operator, which is guaranteed to
 935      be the non-leaf side.  */
 936   rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)),
 937                      opindex + 1, ops);
 938 }
 939
 940 /* Transform STMT, which is really (A +B) + (C + D) into the left
 941    linear form, ((A+B)+C)+D.
 942    Recurse on D if necessary.  */
 943
 944 static void
 945 linearize_expr (tree stmt)
 946 {
 947   block_stmt_iterator bsinow, bsirhs;
 948   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 949   enum tree_code rhscode = TREE_CODE (rhs);
 950   tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 951   tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
 952   tree newbinrhs = NULL_TREE;
 953   struct loop *loop = loop_containing_stmt (stmt);
 954
 955   gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs), loop)
 956               && is_reassociable_op (binrhs, TREE_CODE (rhs), loop));
 957
 958   bsinow = bsi_for_stmt (stmt);
 959   bsirhs = bsi_for_stmt (binrhs);
 960   bsi_move_before (&bsirhs, &bsinow);
 961
 962   TREE_OPERAND (rhs, 1) = TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs, 1), 0);
 963   if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME)
 964     newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
 965   TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs, 1), 0)
 966     = GIMPLE_STMT_OPERAND (binlhs, 0);
 967   TREE_OPERAND (rhs, 0) = GIMPLE_STMT_OPERAND (binrhs, 0);
 968
 969   if (dump_file && (dump_flags & TDF_DETAILS))
 970     {
 971       fprintf (dump_file, "Linearized: ");
 972       print_generic_stmt (dump_file, rhs, 0);
 973     }
 974
 975   reassociate_stats.linearized++;
 976   update_stmt (binrhs);
 977   update_stmt (binlhs);
 978   update_stmt (stmt);
 979   TREE_VISITED (binrhs) = 1;
 980   TREE_VISITED (binlhs) = 1;
 981   TREE_VISITED (stmt) = 1;
 982
 983   /* Tail recurse on the new rhs if it still needs reassociation.  */
 984   if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
 985     linearize_expr (stmt);
 986 }
 987
 988 /* If LHS has a single immediate use that is a GIMPLE_MODIFY_STMT, return
 989    it.  Otherwise, return NULL.  */
 990
 991 static tree
 992 get_single_immediate_use (tree lhs)
 993 {
 994   use_operand_p immuse;
 995   tree immusestmt;
 996
 997   if (TREE_CODE (lhs) == SSA_NAME
 998       && single_imm_use (lhs, &immuse, &immusestmt))
 999     {
1000       if (TREE_CODE (immusestmt) == RETURN_EXPR)
1001         immusestmt = TREE_OPERAND (immusestmt, 0);
1002       if (TREE_CODE (immusestmt) == GIMPLE_MODIFY_STMT)
1003         return immusestmt;
1004     }
1005   return NULL_TREE;
1006 }
1007 static VEC(tree, heap) *broken_up_subtracts;
1008
1009
1010 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
1011    representing the negated value.  Insertions of any necessary
1012    instructions go before BSI.
1013    This function is recursive in that, if you hand it "a_5" as the
1014    value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1015    transform b_3 + b_4 into a_5 = -b_3 + -b_4.  */
1016
1017 static tree
1018 negate_value (tree tonegate, block_stmt_iterator *bsi)
1019 {
1020   tree negatedef = tonegate;
1021   tree resultofnegate;
1022
1023   if (TREE_CODE (tonegate) == SSA_NAME)
1024     negatedef = SSA_NAME_DEF_STMT (tonegate);
1025
1026   /* If we are trying to negate a name, defined by an add, negate the
1027      add operands instead.  */
1028   if (TREE_CODE (tonegate) == SSA_NAME
1029       && TREE_CODE (negatedef) == GIMPLE_MODIFY_STMT
1030       && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef, 0)) == SSA_NAME
1031       && has_single_use (GIMPLE_STMT_OPERAND (negatedef, 0))
1032       && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef, 1)) == PLUS_EXPR)
1033     {
1034       block_stmt_iterator bsi;
1035       tree binop = GIMPLE_STMT_OPERAND (negatedef, 1);
1036
1037       bsi = bsi_for_stmt (negatedef);
1038       TREE_OPERAND (binop, 0) = negate_value (TREE_OPERAND (binop, 0),
1039                                               &bsi);
1040       bsi = bsi_for_stmt (negatedef);
1041       TREE_OPERAND (binop, 1) = negate_value (TREE_OPERAND (binop, 1),
1042                                               &bsi);
1043       update_stmt (negatedef);
1044       return GIMPLE_STMT_OPERAND (negatedef, 0);
1045     }
1046
1047   tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
1048   resultofnegate = force_gimple_operand_bsi (bsi, tonegate, true,
1049                                              NULL_TREE, true, BSI_SAME_STMT);
1050   VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
1051   return resultofnegate;
1052
1053 }
1054
1055 /* Return true if we should break up the subtract in STMT into an add
1056    with negate.  This is true when we the subtract operands are really
1057    adds, or the subtract itself is used in an add expression.  In
1058    either case, breaking up the subtract into an add with negate
1059    exposes the adds to reassociation.  */
1060
1061 static bool
1062 should_break_up_subtract (tree stmt)
1063 {
1064
1065   tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1066   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1067   tree binlhs = TREE_OPERAND (rhs, 0);
1068   tree binrhs = TREE_OPERAND (rhs, 1);
1069   tree immusestmt;
1070   struct loop *loop = loop_containing_stmt (stmt);
1071
1072   if (TREE_CODE (binlhs) == SSA_NAME
1073       && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
1074     return true;
1075
1076   if (TREE_CODE (binrhs) == SSA_NAME
1077       && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
1078     return true;
1079
1080   if (TREE_CODE (lhs) == SSA_NAME
1081       && (immusestmt = get_single_immediate_use (lhs))
1082       && TREE_CODE (GIMPLE_STMT_OPERAND (immusestmt, 1)) == PLUS_EXPR)
1083     return true;
1084   return false;
1085
1086 }
1087
1088 /* Transform STMT from A - B into A + -B.  */
1089
1090 static void
1091 break_up_subtract (tree stmt, block_stmt_iterator *bsi)
1092 {
1093   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1094
1095   if (dump_file && (dump_flags & TDF_DETAILS))
1096     {
1097       fprintf (dump_file, "Breaking up subtract ");
1098       print_generic_stmt (dump_file, stmt, 0);
1099     }
1100
1101   TREE_SET_CODE (GIMPLE_STMT_OPERAND (stmt, 1), PLUS_EXPR);
1102   TREE_OPERAND (rhs, 1) = negate_value (TREE_OPERAND (rhs, 1), bsi);
1103
1104   update_stmt (stmt);
1105 }
1106
1107 /* Recursively linearize a binary expression that is the RHS of STMT.
1108    Place the operands of the expression tree in the vector named OPS.  */
1109
1110 static void
1111 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, tree stmt)
1112 {
1113   block_stmt_iterator bsinow, bsilhs;
1114   tree rhs = GENERIC_TREE_OPERAND (stmt, 1);
1115   tree binrhs = TREE_OPERAND (rhs, 1);
1116   tree binlhs = TREE_OPERAND (rhs, 0);
1117   tree binlhsdef, binrhsdef;
1118   bool binlhsisreassoc = false;
1119   bool binrhsisreassoc = false;
1120   enum tree_code rhscode = TREE_CODE (rhs);
1121   struct loop *loop = loop_containing_stmt (stmt);
1122
1123   TREE_VISITED (stmt) = 1;
1124
1125   if (TREE_CODE (binlhs) == SSA_NAME)
1126     {
1127       binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1128       binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
1129     }
1130
1131   if (TREE_CODE (binrhs) == SSA_NAME)
1132     {
1133       binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1134       binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
1135     }
1136
1137   /* If the LHS is not reassociable, but the RHS is, we need to swap
1138      them.  If neither is reassociable, there is nothing we can do, so
1139      just put them in the ops vector.  If the LHS is reassociable,
1140      linearize it.  If both are reassociable, then linearize the RHS
1141      and the LHS.  */
1142
1143   if (!binlhsisreassoc)
1144     {
1145       tree temp;
1146
1147       if (!binrhsisreassoc)
1148         {
1149           add_to_ops_vec (ops, binrhs);
1150           add_to_ops_vec (ops, binlhs);
1151           return;
1152         }
1153
1154       if (dump_file && (dump_flags & TDF_DETAILS))
1155         {
1156           fprintf (dump_file, "swapping operands of ");
1157           print_generic_expr (dump_file, stmt, 0);
1158         }
1159
1160       swap_tree_operands (stmt, &TREE_OPERAND (rhs, 0),
1161                           &TREE_OPERAND (rhs, 1));
1162       update_stmt (stmt);
1163
1164       if (dump_file && (dump_flags & TDF_DETAILS))
1165         {
1166           fprintf (dump_file, " is now ");
1167           print_generic_stmt (dump_file, stmt, 0);
1168         }
1169
1170       /* We want to make it so the lhs is always the reassociative op,
1171          so swap.  */
1172       temp = binlhs;
1173       binlhs = binrhs;
1174       binrhs = temp;
1175     }
1176   else if (binrhsisreassoc)
1177     {
1178       linearize_expr (stmt);
1179       gcc_assert (rhs == GIMPLE_STMT_OPERAND (stmt, 1));
1180       binlhs = TREE_OPERAND (rhs, 0);
1181       binrhs = TREE_OPERAND (rhs, 1);
1182     }
1183
1184   gcc_assert (TREE_CODE (binrhs) != SSA_NAME
1185               || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
1186                                       rhscode, loop));
1187   bsinow = bsi_for_stmt (stmt);
1188   bsilhs = bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs));
1189   bsi_move_before (&bsilhs, &bsinow);
1190   linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs));
1191   add_to_ops_vec (ops, binrhs);
1192 }
1193
1194 /* Repropagate the negates back into subtracts, since no other pass
1195    currently does it.  */
1196
1197 static void
1198 repropagate_negates (void)
1199 {
1200   unsigned int i = 0;
1201   tree negate;
1202
1203   for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
1204     {
1205       tree user = get_single_immediate_use (negate);
1206
1207       /* The negate operand can be either operand of a PLUS_EXPR
1208          (it can be the LHS if the RHS is a constant for example).
1209
1210          Force the negate operand to the RHS of the PLUS_EXPR, then
1211          transform the PLUS_EXPR into a MINUS_EXPR.  */
1212       if (user
1213           && TREE_CODE (user) == GIMPLE_MODIFY_STMT
1214           && TREE_CODE (GIMPLE_STMT_OPERAND (user, 1)) == PLUS_EXPR)
1215         {
1216           tree rhs = GIMPLE_STMT_OPERAND (user, 1);
1217
1218           /* If the negated operand appears on the LHS of the
1219              PLUS_EXPR, exchange the operands of the PLUS_EXPR
1220              to force the negated operand to the RHS of the PLUS_EXPR.  */
1221           if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user, 1), 0) == negate)
1222             {
1223               tree temp = TREE_OPERAND (rhs, 0);
1224               TREE_OPERAND (rhs, 0) = TREE_OPERAND (rhs, 1);
1225               TREE_OPERAND (rhs, 1) = temp;
1226             }
1227
1228           /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1229              the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR.  */
1230           if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user, 1), 1) == negate)
1231             {
1232               TREE_SET_CODE (rhs, MINUS_EXPR);
1233               TREE_OPERAND (rhs, 1) = get_unary_op (negate, NEGATE_EXPR);
1234               update_stmt (user);
1235             }
1236         }
1237     }
1238 }
1239
1240 /* Break up subtract operations in block BB.
1241
1242    We do this top down because we don't know whether the subtract is
1243    part of a possible chain of reassociation except at the top.
1244
1245    IE given
1246    d = f + g
1247    c = a + e
1248    b = c - d
1249    q = b - r
1250    k = t - q
1251
1252    we want to break up k = t - q, but we won't until we've transformed q
1253    = b - r, which won't be broken up until we transform b = c - d.  */
1254
1255 static void
1256 break_up_subtract_bb (basic_block bb)
1257 {
1258   block_stmt_iterator bsi;
1259   basic_block son;
1260
1261   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1262     {
1263       tree stmt = bsi_stmt (bsi);
1264
1265       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1266         {
1267           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1268           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1269
1270           TREE_VISITED (stmt) = 0;
1271           /* If associative-math we can do reassociation for
1272              non-integral types.  Or, we can do reassociation for
1273              non-saturating fixed-point types.  */
1274           if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1275                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1276               && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
1277                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
1278                   || !flag_associative_math)
1279               && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs))
1280                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs))))
1281             continue;
1282
1283           /* Check for a subtract used only in an addition.  If this
1284              is the case, transform it into add of a negate for better
1285              reassociation.  IE transform C = A-B into C = A + -B if C
1286              is only used in an addition.  */
1287           if (TREE_CODE (rhs) == MINUS_EXPR)
1288             if (should_break_up_subtract (stmt))
1289               break_up_subtract (stmt, &bsi);
1290         }
1291     }
1292   for (son = first_dom_son (CDI_DOMINATORS, bb);
1293        son;
1294        son = next_dom_son (CDI_DOMINATORS, son))
1295     break_up_subtract_bb (son);
1296 }
1297
1298 /* Reassociate expressions in basic block BB and its post-dominator as
1299    children.  */
1300
1301 static void
1302 reassociate_bb (basic_block bb)
1303 {
1304   block_stmt_iterator bsi;
1305   basic_block son;
1306
1307   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1308     {
1309       tree stmt = bsi_stmt (bsi);
1310
1311       if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1312         {
1313           tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1314           tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1315
1316           /* If this was part of an already processed tree, we don't
1317              need to touch it again. */
1318           if (TREE_VISITED (stmt))
1319             continue;
1320
1321           /* If associative-math we can do reassociation for
1322              non-integral types.  Or, we can do reassociation for
1323              non-saturating fixed-point types.  */
1324           if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1325                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1326               && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
1327                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
1328                   || !flag_associative_math)
1329               && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs))
1330                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs))))
1331             continue;
1332
1333           if (associative_tree_code (TREE_CODE (rhs)))
1334             {
1335               VEC(operand_entry_t, heap) *ops = NULL;
1336
1337               /* There may be no immediate uses left by the time we
1338                  get here because we may have eliminated them all.  */
1339               if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
1340                 continue;
1341
1342               TREE_VISITED (stmt) = 1;
1343               linearize_expr_tree (&ops, stmt);
1344               qsort (VEC_address (operand_entry_t, ops),
1345                      VEC_length (operand_entry_t, ops),
1346                      sizeof (operand_entry_t),
1347                      sort_by_operand_rank);
1348               optimize_ops_list (TREE_CODE (rhs), &ops);
1349
1350               if (VEC_length (operand_entry_t, ops) == 1)
1351                 {
1352                   if (dump_file && (dump_flags & TDF_DETAILS))
1353                     {
1354                       fprintf (dump_file, "Transforming ");
1355                       print_generic_expr (dump_file, rhs, 0);
1356                     }
1357                   GIMPLE_STMT_OPERAND (stmt, 1)
1358                     = VEC_last (operand_entry_t, ops)->op;
1359                   update_stmt (stmt);
1360
1361                   if (dump_file && (dump_flags & TDF_DETAILS))
1362                     {
1363                       fprintf (dump_file, " into ");
1364                       print_generic_stmt (dump_file,
1365                                           GIMPLE_STMT_OPERAND (stmt, 1), 0);
1366                     }
1367                 }
1368               else
1369                 {
1370                   rewrite_expr_tree (stmt, 0, ops);
1371                 }
1372
1373               VEC_free (operand_entry_t, heap, ops);
1374             }
1375         }
1376     }
1377   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
1378        son;
1379        son = next_dom_son (CDI_POST_DOMINATORS, son))
1380     reassociate_bb (son);
1381 }
1382
1383 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
1384 void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
1385
1386 /* Dump the operand entry vector OPS to FILE.  */
1387
1388 void
1389 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
1390 {
1391   operand_entry_t oe;
1392   unsigned int i;
1393
1394   for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
1395     {
1396       fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
1397       print_generic_stmt (file, oe->op, 0);
1398     }
1399 }
1400
1401 /* Dump the operand entry vector OPS to STDERR.  */
1402
1403 void
1404 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
1405 {
1406   dump_ops_vector (stderr, ops);
1407 }
1408
1409 static void
1410 do_reassoc (void)
1411 {
1412   break_up_subtract_bb (ENTRY_BLOCK_PTR);
1413   reassociate_bb (EXIT_BLOCK_PTR);
1414 }
1415
1416 /* Initialize the reassociation pass.  */
1417
1418 static void
1419 init_reassoc (void)
1420 {
1421   int i;
1422   long rank = 2;
1423   tree param;
1424   int *bbs = XNEWVEC (int, last_basic_block + 1);
1425
1426   /* Find the loops, so that we can prevent moving calculations in
1427      them.  */
1428   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1429
1430   memset (&reassociate_stats, 0, sizeof (reassociate_stats));
1431
1432   operand_entry_pool = create_alloc_pool ("operand entry pool",
1433                                           sizeof (struct operand_entry), 30);
1434
1435   /* Reverse RPO (Reverse Post Order) will give us something where
1436      deeper loops come later.  */
1437   pre_and_rev_post_order_compute (NULL, bbs, false);
1438   bb_rank = XCNEWVEC (long, last_basic_block + 1);
1439   operand_rank = pointer_map_create ();
1440
1441   /* Give each argument a distinct rank.   */
1442   for (param = DECL_ARGUMENTS (current_function_decl);
1443        param;
1444        param = TREE_CHAIN (param))
1445     {
1446       if (gimple_default_def (cfun, param) != NULL)
1447         {
1448           tree def = gimple_default_def (cfun, param);
1449           insert_operand_rank (def, ++rank);
1450         }
1451     }
1452
1453   /* Give the chain decl a distinct rank. */
1454   if (cfun->static_chain_decl != NULL)
1455     {
1456       tree def = gimple_default_def (cfun, cfun->static_chain_decl);
1457       if (def != NULL)
1458         insert_operand_rank (def, ++rank);
1459     }
1460
1461   /* Set up rank for each BB  */
1462   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
1463     bb_rank[bbs[i]] = ++rank  << 16;
1464
1465   free (bbs);
1466   calculate_dominance_info (CDI_POST_DOMINATORS);
1467   broken_up_subtracts = NULL;
1468 }
1469
1470 /* Cleanup after the reassociation pass, and print stats if
1471    requested.  */
1472
1473 static void
1474 fini_reassoc (void)
1475 {
1476   if (dump_file && (dump_flags & TDF_STATS))
1477     {
1478       fprintf (dump_file, "Reassociation stats:\n");
1479       fprintf (dump_file, "Linearized: %d\n",
1480                reassociate_stats.linearized);
1481       fprintf (dump_file, "Constants eliminated: %d\n",
1482                reassociate_stats.constants_eliminated);
1483       fprintf (dump_file, "Ops eliminated: %d\n",
1484                reassociate_stats.ops_eliminated);
1485       fprintf (dump_file, "Statements rewritten: %d\n",
1486                reassociate_stats.rewritten);
1487     }
1488
1489   pointer_map_destroy (operand_rank);
1490   free_alloc_pool (operand_entry_pool);
1491   free (bb_rank);
1492   VEC_free (tree, heap, broken_up_subtracts);
1493   free_dominance_info (CDI_POST_DOMINATORS);
1494   loop_optimizer_finalize ();
1495 }
1496
1497 /* Gate and execute functions for Reassociation.  */
1498
1499 static unsigned int
1500 execute_reassoc (void)
1501 {
1502   init_reassoc ();
1503
1504   do_reassoc ();
1505   repropagate_negates ();
1506
1507   fini_reassoc ();
1508   return 0;
1509 }
1510
1511 static bool
1512 gate_tree_ssa_reassoc (void)
1513 {
1514   return flag_tree_reassoc != 0;
1515 }
1516
1517 struct tree_opt_pass pass_reassoc =
1518 {
1519   "reassoc",                            /* name */
1520   gate_tree_ssa_reassoc,                /* gate */
1521   execute_reassoc,                      /* execute */
1522   NULL,                                 /* sub */
1523   NULL,                                 /* next */
1524   0,                                    /* static_pass_number */
1525   TV_TREE_REASSOC,                      /* tv_id */
1526   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1527   0,                                    /* properties_provided */
1528   0,                                    /* properties_destroyed */
1529   0,                                    /* todo_flags_start */
1530   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1531   0                                     /* letter */
1532 };