OSDN Git Service

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