OSDN Git Service

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