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