gcc/tree-ssa-reassoc.c

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