OSDN Git Service

5f7c6b721d8e1af5f50a59ed5ad16b1658d9e731
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-reassoc.c
1 /* Reassociation for trees.
2    Copyright (C) 2005, 2007, 2008, 2009, 2010 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 "ggc.h"
26 #include "tree.h"
27 #include "basic-block.h"
28 #include "diagnostic.h"
29 #include "tree-inline.h"
30 #include "tree-flow.h"
31 #include "gimple.h"
32 #include "tree-dump.h"
33 #include "timevar.h"
34 #include "tree-iterator.h"
35 #include "real.h"
36 #include "tree-pass.h"
37 #include "alloc-pool.h"
38 #include "vec.h"
39 #include "langhooks.h"
40 #include "pointer-set.h"
41 #include "cfgloop.h"
42 #include "flags.h"
43
44 /*  This is a simple global reassociation pass.  It is, in part, based
45     on the LLVM pass of the same name (They do some things more/less
46     than we do, in different orders, etc).
47
48     It consists of five steps:
49
50     1. Breaking up subtract operations into addition + negate, where
51     it would promote the reassociation of adds.
52
53     2. Left linearization of the expression trees, so that (A+B)+(C+D)
54     becomes (((A+B)+C)+D), which is easier for us to rewrite later.
55     During linearization, we place the operands of the binary
56     expressions into a vector of operand_entry_t
57
58     3. Optimization of the operand lists, eliminating things like a +
59     -a, a & a, etc.
60
61     4. Rewrite the expression trees we linearized and optimized so
62     they are in proper rank order.
63
64     5. Repropagate negates, as nothing else will clean it up ATM.
65
66     A bit of theory on #4, since nobody seems to write anything down
67     about why it makes sense to do it the way they do it:
68
69     We could do this much nicer theoretically, but don't (for reasons
70     explained after how to do it theoretically nice :P).
71
72     In order to promote the most redundancy elimination, you want
73     binary expressions whose operands are the same rank (or
74     preferably, the same value) exposed to the redundancy eliminator,
75     for possible elimination.
76
77     So the way to do this if we really cared, is to build the new op
78     tree from the leaves to the roots, merging as you go, and putting the
79     new op on the end of the worklist, until you are left with one
80     thing on the worklist.
81
82     IE if you have to rewrite the following set of operands (listed with
83     rank in parentheses), with opcode PLUS_EXPR:
84
85     a (1),  b (1),  c (1),  d (2), e (2)
86
87
88     We start with our merge worklist empty, and the ops list with all of
89     those on it.
90
91     You want to first merge all leaves of the same rank, as much as
92     possible.
93
94     So first build a binary op of
95
96     mergetmp = a + b, and put "mergetmp" on the merge worklist.
97
98     Because there is no three operand form of PLUS_EXPR, c is not going to
99     be exposed to redundancy elimination as a rank 1 operand.
100
101     So you might as well throw it on the merge worklist (you could also
102     consider it to now be a rank two operand, and merge it with d and e,
103     but in this case, you then have evicted e from a binary op. So at
104     least in this situation, you can't win.)
105
106     Then build a binary op of d + e
107     mergetmp2 = d + e
108
109     and put mergetmp2 on the merge worklist.
110
111     so merge worklist = {mergetmp, c, mergetmp2}
112
113     Continue building binary ops of these operations until you have only
114     one operation left on the worklist.
115
116     So we have
117
118     build binary op
119     mergetmp3 = mergetmp + c
120
121     worklist = {mergetmp2, mergetmp3}
122
123     mergetmp4 = mergetmp2 + mergetmp3
124
125     worklist = {mergetmp4}
126
127     because we have one operation left, we can now just set the original
128     statement equal to the result of that operation.
129
130     This will at least expose a + b  and d + e to redundancy elimination
131     as binary operations.
132
133     For extra points, you can reuse the old statements to build the
134     mergetmps, since you shouldn't run out.
135
136     So why don't we do this?
137
138     Because it's expensive, and rarely will help.  Most trees we are
139     reassociating have 3 or less ops.  If they have 2 ops, they already
140     will be written into a nice single binary op.  If you have 3 ops, a
141     single simple check suffices to tell you whether the first two are of the
142     same rank.  If so, you know to order it
143
144     mergetmp = op1 + op2
145     newstmt = mergetmp + op3
146
147     instead of
148     mergetmp = op2 + op3
149     newstmt = mergetmp + op1
150
151     If all three are of the same rank, you can't expose them all in a
152     single binary operator anyway, so the above is *still* the best you
153     can do.
154
155     Thus, this is what we do.  When we have three ops left, we check to see
156     what order to put them in, and call it a day.  As a nod to vector sum
157     reduction, we check if any of the ops are really a phi node that is a
158     destructive update for the associating op, and keep the destructive
159     update together for vector sum reduction recognition.  */
160
161
162 /* Statistics */
163 static struct
164 {
165   int linearized;
166   int constants_eliminated;
167   int ops_eliminated;
168   int rewritten;
169 } reassociate_stats;
170
171 /* Operator, rank pair.  */
172 typedef struct operand_entry
173 {
174   unsigned int rank;
175   tree op;
176 } *operand_entry_t;
177
178 static alloc_pool operand_entry_pool;
179
180
181 /* Starting rank number for a given basic block, so that we can rank
182    operations using unmovable instructions in that BB based on the bb
183    depth.  */
184 static long *bb_rank;
185
186 /* Operand->rank hashtable.  */
187 static struct pointer_map_t *operand_rank;
188
189
190 /* Look up the operand rank structure for expression E.  */
191
192 static inline long
193 find_operand_rank (tree e)
194 {
195   void **slot = pointer_map_contains (operand_rank, e);
196   return slot ? (long) (intptr_t) *slot : -1;
197 }
198
199 /* Insert {E,RANK} into the operand rank hashtable.  */
200
201 static inline void
202 insert_operand_rank (tree e, long rank)
203 {
204   void **slot;
205   gcc_assert (rank > 0);
206   slot = pointer_map_insert (operand_rank, e);
207   gcc_assert (!*slot);
208   *slot = (void *) (intptr_t) rank;
209 }
210
211 /* Given an expression E, return the rank of the expression.  */
212
213 static long
214 get_rank (tree e)
215 {
216   /* Constants have rank 0.  */
217   if (is_gimple_min_invariant (e))
218     return 0;
219
220   /* SSA_NAME's have the rank of the expression they are the result
221      of.
222      For globals and uninitialized values, the rank is 0.
223      For function arguments, use the pre-setup rank.
224      For PHI nodes, stores, asm statements, etc, we use the rank of
225      the BB.
226      For simple operations, the rank is the maximum rank of any of
227      its operands, or the bb_rank, whichever is less.
228      I make no claims that this is optimal, however, it gives good
229      results.  */
230
231   if (TREE_CODE (e) == SSA_NAME)
232     {
233       gimple stmt;
234       long rank, maxrank;
235       int i, n;
236
237       if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
238           && SSA_NAME_IS_DEFAULT_DEF (e))
239         return find_operand_rank (e);
240
241       stmt = SSA_NAME_DEF_STMT (e);
242       if (gimple_bb (stmt) == NULL)
243         return 0;
244
245       if (!is_gimple_assign (stmt)
246           || gimple_vdef (stmt))
247         return bb_rank[gimple_bb (stmt)->index];
248
249       /* If we already have a rank for this expression, use that.  */
250       rank = find_operand_rank (e);
251       if (rank != -1)
252         return rank;
253
254       /* Otherwise, find the maximum rank for the operands, or the bb
255          rank, whichever is less.   */
256       rank = 0;
257       maxrank = bb_rank[gimple_bb(stmt)->index];
258       if (gimple_assign_single_p (stmt))
259         {
260           tree rhs = gimple_assign_rhs1 (stmt);
261           n = TREE_OPERAND_LENGTH (rhs);
262           if (n == 0)
263             rank = MAX (rank, get_rank (rhs));
264           else
265             {
266               for (i = 0;
267                    i < n && TREE_OPERAND (rhs, i) && rank != maxrank; i++)
268                 rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
269             }
270         }
271       else
272         {
273           n = gimple_num_ops (stmt);
274           for (i = 1; i < n && rank != maxrank; i++)
275             {
276               gcc_assert (gimple_op (stmt, i));
277               rank = MAX(rank, get_rank (gimple_op (stmt, i)));
278             }
279         }
280
281       if (dump_file && (dump_flags & TDF_DETAILS))
282         {
283           fprintf (dump_file, "Rank for ");
284           print_generic_expr (dump_file, e, 0);
285           fprintf (dump_file, " is %ld\n", (rank + 1));
286         }
287
288       /* Note the rank in the hashtable so we don't recompute it.  */
289       insert_operand_rank (e, (rank + 1));
290       return (rank + 1);
291     }
292
293   /* Globals, etc,  are rank 0 */
294   return 0;
295 }
296
297 DEF_VEC_P(operand_entry_t);
298 DEF_VEC_ALLOC_P(operand_entry_t, heap);
299
300 /* We want integer ones to end up last no matter what, since they are
301    the ones we can do the most with.  */
302 #define INTEGER_CONST_TYPE 1 << 3
303 #define FLOAT_CONST_TYPE 1 << 2
304 #define OTHER_CONST_TYPE 1 << 1
305
306 /* Classify an invariant tree into integer, float, or other, so that
307    we can sort them to be near other constants of the same type.  */
308 static inline int
309 constant_type (tree t)
310 {
311   if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
312     return INTEGER_CONST_TYPE;
313   else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
314     return FLOAT_CONST_TYPE;
315   else
316     return OTHER_CONST_TYPE;
317 }
318
319 /* qsort comparison function to sort operand entries PA and PB by rank
320    so that the sorted array is ordered by rank in decreasing order.  */
321 static int
322 sort_by_operand_rank (const void *pa, const void *pb)
323 {
324   const operand_entry_t oea = *(const operand_entry_t *)pa;
325   const operand_entry_t oeb = *(const operand_entry_t *)pb;
326
327   /* It's nicer for optimize_expression if constants that are likely
328      to fold when added/multiplied//whatever are put next to each
329      other.  Since all constants have rank 0, order them by type.  */
330   if (oeb->rank == 0 &&  oea->rank == 0)
331     return constant_type (oeb->op) - constant_type (oea->op);
332
333   /* Lastly, make sure the versions that are the same go next to each
334      other.  We use SSA_NAME_VERSION because it's stable.  */
335   if ((oeb->rank - oea->rank == 0)
336       && TREE_CODE (oea->op) == SSA_NAME
337       && TREE_CODE (oeb->op) == SSA_NAME)
338     return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
339
340   return oeb->rank - oea->rank;
341 }
342
343 /* Add an operand entry to *OPS for the tree operand OP.  */
344
345 static void
346 add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
347 {
348   operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
349
350   oe->op = op;
351   oe->rank = get_rank (op);
352   VEC_safe_push (operand_entry_t, heap, *ops, oe);
353 }
354
355 /* Return true if STMT is reassociable operation containing a binary
356    operation with tree code CODE, and is inside LOOP.  */
357
358 static bool
359 is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop)
360 {
361   basic_block bb = gimple_bb (stmt);
362
363   if (gimple_bb (stmt) == NULL)
364     return false;
365
366   if (!flow_bb_inside_loop_p (loop, bb))
367     return false;
368
369   if (is_gimple_assign (stmt)
370       && gimple_assign_rhs_code (stmt) == code
371       && has_single_use (gimple_assign_lhs (stmt)))
372     return true;
373
374   return false;
375 }
376
377
378 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
379    operand of the negate operation.  Otherwise, return NULL.  */
380
381 static tree
382 get_unary_op (tree name, enum tree_code opcode)
383 {
384   gimple stmt = SSA_NAME_DEF_STMT (name);
385
386   if (!is_gimple_assign (stmt))
387     return NULL_TREE;
388
389   if (gimple_assign_rhs_code (stmt) == opcode)
390     return gimple_assign_rhs1 (stmt);
391   return NULL_TREE;
392 }
393
394 /* If CURR and LAST are a pair of ops that OPCODE allows us to
395    eliminate through equivalences, do so, remove them from OPS, and
396    return true.  Otherwise, return false.  */
397
398 static bool
399 eliminate_duplicate_pair (enum tree_code opcode,
400                           VEC (operand_entry_t, heap) **ops,
401                           bool *all_done,
402                           unsigned int i,
403                           operand_entry_t curr,
404                           operand_entry_t last)
405 {
406
407   /* If we have two of the same op, and the opcode is & |, min, or max,
408      we can eliminate one of them.
409      If we have two of the same op, and the opcode is ^, we can
410      eliminate both of them.  */
411
412   if (last && last->op == curr->op)
413     {
414       switch (opcode)
415         {
416         case MAX_EXPR:
417         case MIN_EXPR:
418         case BIT_IOR_EXPR:
419         case BIT_AND_EXPR:
420           if (dump_file && (dump_flags & TDF_DETAILS))
421             {
422               fprintf (dump_file, "Equivalence: ");
423               print_generic_expr (dump_file, curr->op, 0);
424               fprintf (dump_file, " [&|minmax] ");
425               print_generic_expr (dump_file, last->op, 0);
426               fprintf (dump_file, " -> ");
427               print_generic_stmt (dump_file, last->op, 0);
428             }
429
430           VEC_ordered_remove (operand_entry_t, *ops, i);
431           reassociate_stats.ops_eliminated ++;
432
433           return true;
434
435         case BIT_XOR_EXPR:
436           if (dump_file && (dump_flags & TDF_DETAILS))
437             {
438               fprintf (dump_file, "Equivalence: ");
439               print_generic_expr (dump_file, curr->op, 0);
440               fprintf (dump_file, " ^ ");
441               print_generic_expr (dump_file, last->op, 0);
442               fprintf (dump_file, " -> nothing\n");
443             }
444
445           reassociate_stats.ops_eliminated += 2;
446
447           if (VEC_length (operand_entry_t, *ops) == 2)
448             {
449               VEC_free (operand_entry_t, heap, *ops);
450               *ops = NULL;
451               add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
452                                                  integer_zero_node));
453               *all_done = true;
454             }
455           else
456             {
457               VEC_ordered_remove (operand_entry_t, *ops, i-1);
458               VEC_ordered_remove (operand_entry_t, *ops, i-1);
459             }
460
461           return true;
462
463         default:
464           break;
465         }
466     }
467   return false;
468 }
469
470 /* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
471    look in OPS for a corresponding positive operation to cancel it
472    out.  If we find one, remove the other from OPS, replace
473    OPS[CURRINDEX] with 0, and return true.  Otherwise, return
474    false. */
475
476 static bool
477 eliminate_plus_minus_pair (enum tree_code opcode,
478                            VEC (operand_entry_t, heap) **ops,
479                            unsigned int currindex,
480                            operand_entry_t curr)
481 {
482   tree negateop;
483   unsigned int i;
484   operand_entry_t oe;
485
486   if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
487     return false;
488
489   negateop = get_unary_op (curr->op, NEGATE_EXPR);
490   if (negateop == NULL_TREE)
491     return false;
492
493   /* Any non-negated version will have a rank that is one less than
494      the current rank.  So once we hit those ranks, if we don't find
495      one, we can stop.  */
496
497   for (i = currindex + 1;
498        VEC_iterate (operand_entry_t, *ops, i, oe)
499        && oe->rank >= curr->rank - 1 ;
500        i++)
501     {
502       if (oe->op == negateop)
503         {
504
505           if (dump_file && (dump_flags & TDF_DETAILS))
506             {
507               fprintf (dump_file, "Equivalence: ");
508               print_generic_expr (dump_file, negateop, 0);
509               fprintf (dump_file, " + -");
510               print_generic_expr (dump_file, oe->op, 0);
511               fprintf (dump_file, " -> 0\n");
512             }
513
514           VEC_ordered_remove (operand_entry_t, *ops, i);
515           add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
516                                             integer_zero_node));
517           VEC_ordered_remove (operand_entry_t, *ops, currindex);
518           reassociate_stats.ops_eliminated ++;
519
520           return true;
521         }
522     }
523
524   return false;
525 }
526
527 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
528    bitwise not expression, look in OPS for a corresponding operand to
529    cancel it out.  If we find one, remove the other from OPS, replace
530    OPS[CURRINDEX] with 0, and return true.  Otherwise, return
531    false. */
532
533 static bool
534 eliminate_not_pairs (enum tree_code opcode,
535                      VEC (operand_entry_t, heap) **ops,
536                      unsigned int currindex,
537                      operand_entry_t curr)
538 {
539   tree notop;
540   unsigned int i;
541   operand_entry_t oe;
542
543   if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
544       || TREE_CODE (curr->op) != SSA_NAME)
545     return false;
546
547   notop = get_unary_op (curr->op, BIT_NOT_EXPR);
548   if (notop == NULL_TREE)
549     return false;
550
551   /* Any non-not version will have a rank that is one less than
552      the current rank.  So once we hit those ranks, if we don't find
553      one, we can stop.  */
554
555   for (i = currindex + 1;
556        VEC_iterate (operand_entry_t, *ops, i, oe)
557        && oe->rank >= curr->rank - 1;
558        i++)
559     {
560       if (oe->op == notop)
561         {
562           if (dump_file && (dump_flags & TDF_DETAILS))
563             {
564               fprintf (dump_file, "Equivalence: ");
565               print_generic_expr (dump_file, notop, 0);
566               if (opcode == BIT_AND_EXPR)
567                 fprintf (dump_file, " & ~");
568               else if (opcode == BIT_IOR_EXPR)
569                 fprintf (dump_file, " | ~");
570               print_generic_expr (dump_file, oe->op, 0);
571               if (opcode == BIT_AND_EXPR)
572                 fprintf (dump_file, " -> 0\n");
573               else if (opcode == BIT_IOR_EXPR)
574                 fprintf (dump_file, " -> -1\n");
575             }
576
577           if (opcode == BIT_AND_EXPR)
578             oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
579           else if (opcode == BIT_IOR_EXPR)
580             oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
581                                           TYPE_PRECISION (TREE_TYPE (oe->op)));
582
583           reassociate_stats.ops_eliminated
584             += VEC_length (operand_entry_t, *ops) - 1;
585           VEC_free (operand_entry_t, heap, *ops);
586           *ops = NULL;
587           VEC_safe_push (operand_entry_t, heap, *ops, oe);
588           return true;
589         }
590     }
591
592   return false;
593 }
594
595 /* Use constant value that may be present in OPS to try to eliminate
596    operands.  Note that this function is only really used when we've
597    eliminated ops for other reasons, or merged constants.  Across
598    single statements, fold already does all of this, plus more.  There
599    is little point in duplicating logic, so I've only included the
600    identities that I could ever construct testcases to trigger.  */
601
602 static void
603 eliminate_using_constants (enum tree_code opcode,
604                            VEC(operand_entry_t, heap) **ops)
605 {
606   operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
607   tree type = TREE_TYPE (oelast->op);
608
609   if (oelast->rank == 0
610       && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type)))
611     {
612       switch (opcode)
613         {
614         case BIT_AND_EXPR:
615           if (integer_zerop (oelast->op))
616             {
617               if (VEC_length (operand_entry_t, *ops) != 1)
618                 {
619                   if (dump_file && (dump_flags & TDF_DETAILS))
620                     fprintf (dump_file, "Found & 0, removing all other ops\n");
621
622                   reassociate_stats.ops_eliminated
623                     += VEC_length (operand_entry_t, *ops) - 1;
624
625                   VEC_free (operand_entry_t, heap, *ops);
626                   *ops = NULL;
627                   VEC_safe_push (operand_entry_t, heap, *ops, oelast);
628                   return;
629                 }
630             }
631           else if (integer_all_onesp (oelast->op))
632             {
633               if (VEC_length (operand_entry_t, *ops) != 1)
634                 {
635                   if (dump_file && (dump_flags & TDF_DETAILS))
636                     fprintf (dump_file, "Found & -1, removing\n");
637                   VEC_pop (operand_entry_t, *ops);
638                   reassociate_stats.ops_eliminated++;
639                 }
640             }
641           break;
642         case BIT_IOR_EXPR:
643           if (integer_all_onesp (oelast->op))
644             {
645               if (VEC_length (operand_entry_t, *ops) != 1)
646                 {
647                   if (dump_file && (dump_flags & TDF_DETAILS))
648                     fprintf (dump_file, "Found | -1, removing all other ops\n");
649
650                   reassociate_stats.ops_eliminated
651                     += VEC_length (operand_entry_t, *ops) - 1;
652
653                   VEC_free (operand_entry_t, heap, *ops);
654                   *ops = NULL;
655                   VEC_safe_push (operand_entry_t, heap, *ops, oelast);
656                   return;
657                 }
658             }
659           else if (integer_zerop (oelast->op))
660             {
661               if (VEC_length (operand_entry_t, *ops) != 1)
662                 {
663                   if (dump_file && (dump_flags & TDF_DETAILS))
664                     fprintf (dump_file, "Found | 0, removing\n");
665                   VEC_pop (operand_entry_t, *ops);
666                   reassociate_stats.ops_eliminated++;
667                 }
668             }
669           break;
670         case MULT_EXPR:
671           if (integer_zerop (oelast->op)
672               || (FLOAT_TYPE_P (type)
673                   && !HONOR_NANS (TYPE_MODE (type))
674                   && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
675                   && real_zerop (oelast->op)))
676             {
677               if (VEC_length (operand_entry_t, *ops) != 1)
678                 {
679                   if (dump_file && (dump_flags & TDF_DETAILS))
680                     fprintf (dump_file, "Found * 0, removing all other ops\n");
681
682                   reassociate_stats.ops_eliminated
683                     += VEC_length (operand_entry_t, *ops) - 1;
684                   VEC_free (operand_entry_t, heap, *ops);
685                   *ops = NULL;
686                   VEC_safe_push (operand_entry_t, heap, *ops, oelast);
687                   return;
688                 }
689             }
690           else if (integer_onep (oelast->op)
691                    || (FLOAT_TYPE_P (type)
692                        && !HONOR_SNANS (TYPE_MODE (type))
693                        && real_onep (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 * 1, removing\n");
699                   VEC_pop (operand_entry_t, *ops);
700                   reassociate_stats.ops_eliminated++;
701                   return;
702                 }
703             }
704           break;
705         case BIT_XOR_EXPR:
706         case PLUS_EXPR:
707         case MINUS_EXPR:
708           if (integer_zerop (oelast->op)
709               || (FLOAT_TYPE_P (type)
710                   && (opcode == PLUS_EXPR || opcode == MINUS_EXPR)
711                   && fold_real_zero_addition_p (type, oelast->op,
712                                                 opcode == MINUS_EXPR)))
713             {
714               if (VEC_length (operand_entry_t, *ops) != 1)
715                 {
716                   if (dump_file && (dump_flags & TDF_DETAILS))
717                     fprintf (dump_file, "Found [|^+] 0, removing\n");
718                   VEC_pop (operand_entry_t, *ops);
719                   reassociate_stats.ops_eliminated++;
720                   return;
721                 }
722             }
723           break;
724         default:
725           break;
726         }
727     }
728 }
729
730
731 static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
732                                  bool, bool);
733
734 /* Structure for tracking and counting operands.  */
735 typedef struct oecount_s {
736   int cnt;
737   enum tree_code oecode;
738   tree op;
739 } oecount;
740
741 DEF_VEC_O(oecount);
742 DEF_VEC_ALLOC_O(oecount,heap);
743
744 /* The heap for the oecount hashtable and the sorted list of operands.  */
745 static VEC (oecount, heap) *cvec;
746
747 /* Hash function for oecount.  */
748
749 static hashval_t
750 oecount_hash (const void *p)
751 {
752   const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42);
753   return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
754 }
755
756 /* Comparison function for oecount.  */
757
758 static int
759 oecount_eq (const void *p1, const void *p2)
760 {
761   const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42);
762   const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42);
763   return (c1->oecode == c2->oecode
764           && c1->op == c2->op);
765 }
766
767 /* Comparison function for qsort sorting oecount elements by count.  */
768
769 static int
770 oecount_cmp (const void *p1, const void *p2)
771 {
772   const oecount *c1 = (const oecount *)p1;
773   const oecount *c2 = (const oecount *)p2;
774   return c1->cnt - c2->cnt;
775 }
776
777 /* Walks the linear chain with result *DEF searching for an operation
778    with operand OP and code OPCODE removing that from the chain.  *DEF
779    is updated if there is only one operand but no operation left.  */
780
781 static void
782 zero_one_operation (tree *def, enum tree_code opcode, tree op)
783 {
784   gimple stmt = SSA_NAME_DEF_STMT (*def);
785
786   do
787     {
788       tree name = gimple_assign_rhs1 (stmt);
789
790       /* If this is the operation we look for and one of the operands
791          is ours simply propagate the other operand into the stmts
792          single use.  */
793       if (gimple_assign_rhs_code (stmt) == opcode
794           && (name == op
795               || gimple_assign_rhs2 (stmt) == op))
796         {
797           gimple use_stmt;
798           use_operand_p use;
799           gimple_stmt_iterator gsi;
800           if (name == op)
801             name = gimple_assign_rhs2 (stmt);
802           gcc_assert (has_single_use (gimple_assign_lhs (stmt)));
803           single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt);
804           if (gimple_assign_lhs (stmt) == *def)
805             *def = name;
806           SET_USE (use, name);
807           if (TREE_CODE (name) != SSA_NAME)
808             update_stmt (use_stmt);
809           gsi = gsi_for_stmt (stmt);
810           gsi_remove (&gsi, true);
811           release_defs (stmt);
812           return;
813         }
814
815       /* Continue walking the chain.  */
816       gcc_assert (name != op
817                   && TREE_CODE (name) == SSA_NAME);
818       stmt = SSA_NAME_DEF_STMT (name);
819     }
820   while (1);
821 }
822
823 /* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
824    the result.  Places the statement after the definition of either
825    OP1 or OP2.  Returns the new statement.  */
826
827 static gimple
828 build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode)
829 {
830   gimple op1def = NULL, op2def = NULL;
831   gimple_stmt_iterator gsi;
832   tree op;
833   gimple sum;
834
835   /* Create the addition statement.  */
836   sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2);
837   op = make_ssa_name (tmpvar, sum);
838   gimple_assign_set_lhs (sum, op);
839
840   /* Find an insertion place and insert.  */
841   if (TREE_CODE (op1) == SSA_NAME)
842     op1def = SSA_NAME_DEF_STMT (op1);
843   if (TREE_CODE (op2) == SSA_NAME)
844     op2def = SSA_NAME_DEF_STMT (op2);
845   if ((!op1def || gimple_nop_p (op1def))
846       && (!op2def || gimple_nop_p (op2def)))
847     {
848       gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
849       gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
850     }
851   else if ((!op1def || gimple_nop_p (op1def))
852            || (op2def && !gimple_nop_p (op2def)
853                && stmt_dominates_stmt_p (op1def, op2def)))
854     {
855       if (gimple_code (op2def) == GIMPLE_PHI)
856         {
857           gsi = gsi_after_labels (gimple_bb (op2def));
858           gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
859         }
860       else
861         {
862           if (!stmt_ends_bb_p (op2def))
863             {
864               gsi = gsi_for_stmt (op2def);
865               gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
866             }
867           else
868             {
869               edge e;
870               edge_iterator ei;
871
872               FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs)
873                 if (e->flags & EDGE_FALLTHRU)
874                   gsi_insert_on_edge_immediate (e, sum);
875             }
876         }
877     }
878   else
879     {
880       if (gimple_code (op1def) == GIMPLE_PHI)
881         {
882           gsi = gsi_after_labels (gimple_bb (op1def));
883           gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
884         }
885       else
886         {
887           if (!stmt_ends_bb_p (op1def))
888             {
889               gsi = gsi_for_stmt (op1def);
890               gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
891             }
892           else
893             {
894               edge e;
895               edge_iterator ei;
896
897               FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs)
898                 if (e->flags & EDGE_FALLTHRU)
899                   gsi_insert_on_edge_immediate (e, sum);
900             }
901         }
902     }
903   update_stmt (sum);
904
905   return sum;
906 }
907
908 /* Perform un-distribution of divisions and multiplications.
909    A * X + B * X is transformed into (A + B) * X and A / X + B / X
910    to (A + B) / X for real X.
911
912    The algorithm is organized as follows.
913
914     - First we walk the addition chain *OPS looking for summands that
915       are defined by a multiplication or a real division.  This results
916       in the candidates bitmap with relevant indices into *OPS.
917
918     - Second we build the chains of multiplications or divisions for
919       these candidates, counting the number of occurences of (operand, code)
920       pairs in all of the candidates chains.
921
922     - Third we sort the (operand, code) pairs by number of occurence and
923       process them starting with the pair with the most uses.
924
925       * For each such pair we walk the candidates again to build a
926         second candidate bitmap noting all multiplication/division chains
927         that have at least one occurence of (operand, code).
928
929       * We build an alternate addition chain only covering these
930         candidates with one (operand, code) operation removed from their
931         multiplication/division chain.
932
933       * The first candidate gets replaced by the alternate addition chain
934         multiplied/divided by the operand.
935
936       * All candidate chains get disabled for further processing and
937         processing of (operand, code) pairs continues.
938
939   The alternate addition chains built are re-processed by the main
940   reassociation algorithm which allows optimizing a * x * y + b * y * x
941   to (a + b ) * x * y in one invocation of the reassociation pass.  */
942
943 static bool
944 undistribute_ops_list (enum tree_code opcode,
945                        VEC (operand_entry_t, heap) **ops, struct loop *loop)
946 {
947   unsigned int length = VEC_length (operand_entry_t, *ops);
948   operand_entry_t oe1;
949   unsigned i, j;
950   sbitmap candidates, candidates2;
951   unsigned nr_candidates, nr_candidates2;
952   sbitmap_iterator sbi0;
953   VEC (operand_entry_t, heap) **subops;
954   htab_t ctable;
955   bool changed = false;
956
957   if (length <= 1
958       || opcode != PLUS_EXPR)
959     return false;
960
961   /* Build a list of candidates to process.  */
962   candidates = sbitmap_alloc (length);
963   sbitmap_zero (candidates);
964   nr_candidates = 0;
965   for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i)
966     {
967       enum tree_code dcode;
968       gimple oe1def;
969
970       if (TREE_CODE (oe1->op) != SSA_NAME)
971         continue;
972       oe1def = SSA_NAME_DEF_STMT (oe1->op);
973       if (!is_gimple_assign (oe1def))
974         continue;
975       dcode = gimple_assign_rhs_code (oe1def);
976       if ((dcode != MULT_EXPR
977            && dcode != RDIV_EXPR)
978           || !is_reassociable_op (oe1def, dcode, loop))
979         continue;
980
981       SET_BIT (candidates, i);
982       nr_candidates++;
983     }
984
985   if (nr_candidates < 2)
986     {
987       sbitmap_free (candidates);
988       return false;
989     }
990
991   if (dump_file && (dump_flags & TDF_DETAILS))
992     {
993       fprintf (dump_file, "searching for un-distribute opportunities ");
994       print_generic_expr (dump_file,
995         VEC_index (operand_entry_t, *ops,
996                    sbitmap_first_set_bit (candidates))->op, 0);
997       fprintf (dump_file, " %d\n", nr_candidates);
998     }
999
1000   /* Build linearized sub-operand lists and the counting table.  */
1001   cvec = NULL;
1002   ctable = htab_create (15, oecount_hash, oecount_eq, NULL);
1003   subops = XCNEWVEC (VEC (operand_entry_t, heap) *,
1004                      VEC_length (operand_entry_t, *ops));
1005   EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
1006     {
1007       gimple oedef;
1008       enum tree_code oecode;
1009       unsigned j;
1010
1011       oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
1012       oecode = gimple_assign_rhs_code (oedef);
1013       linearize_expr_tree (&subops[i], oedef,
1014                            associative_tree_code (oecode), false);
1015
1016       for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
1017         {
1018           oecount c;
1019           void **slot;
1020           size_t idx;
1021           c.oecode = oecode;
1022           c.cnt = 1;
1023           c.op = oe1->op;
1024           VEC_safe_push (oecount, heap, cvec, &c);
1025           idx = VEC_length (oecount, cvec) + 41;
1026           slot = htab_find_slot (ctable, (void *)idx, INSERT);
1027           if (!*slot)
1028             {
1029               *slot = (void *)idx;
1030             }
1031           else
1032             {
1033               VEC_pop (oecount, cvec);
1034               VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++;
1035             }
1036         }
1037     }
1038   htab_delete (ctable);
1039
1040   /* Sort the counting table.  */
1041   qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec),
1042          sizeof (oecount), oecount_cmp);
1043
1044   if (dump_file && (dump_flags & TDF_DETAILS))
1045     {
1046       oecount *c;
1047       fprintf (dump_file, "Candidates:\n");
1048       for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j)
1049         {
1050           fprintf (dump_file, "  %u %s: ", c->cnt,
1051                    c->oecode == MULT_EXPR
1052                    ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
1053           print_generic_expr (dump_file, c->op, 0);
1054           fprintf (dump_file, "\n");
1055         }
1056     }
1057
1058   /* Process the (operand, code) pairs in order of most occurence.  */
1059   candidates2 = sbitmap_alloc (length);
1060   while (!VEC_empty (oecount, cvec))
1061     {
1062       oecount *c = VEC_last (oecount, cvec);
1063       if (c->cnt < 2)
1064         break;
1065
1066       /* Now collect the operands in the outer chain that contain
1067          the common operand in their inner chain.  */
1068       sbitmap_zero (candidates2);
1069       nr_candidates2 = 0;
1070       EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
1071         {
1072           gimple oedef;
1073           enum tree_code oecode;
1074           unsigned j;
1075           tree op = VEC_index (operand_entry_t, *ops, i)->op;
1076
1077           /* If we undistributed in this chain already this may be
1078              a constant.  */
1079           if (TREE_CODE (op) != SSA_NAME)
1080             continue;
1081
1082           oedef = SSA_NAME_DEF_STMT (op);
1083           oecode = gimple_assign_rhs_code (oedef);
1084           if (oecode != c->oecode)
1085             continue;
1086
1087           for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
1088             {
1089               if (oe1->op == c->op)
1090                 {
1091                   SET_BIT (candidates2, i);
1092                   ++nr_candidates2;
1093                   break;
1094                 }
1095             }
1096         }
1097
1098       if (nr_candidates2 >= 2)
1099         {
1100           operand_entry_t oe1, oe2;
1101           tree tmpvar;
1102           gimple prod;
1103           int first = sbitmap_first_set_bit (candidates2);
1104
1105           /* Build the new addition chain.  */
1106           oe1 = VEC_index (operand_entry_t, *ops, first);
1107           if (dump_file && (dump_flags & TDF_DETAILS))
1108             {
1109               fprintf (dump_file, "Building (");
1110               print_generic_expr (dump_file, oe1->op, 0);
1111             }
1112           tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL);
1113           add_referenced_var (tmpvar);
1114           zero_one_operation (&oe1->op, c->oecode, c->op);
1115           EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
1116             {
1117               gimple sum;
1118               oe2 = VEC_index (operand_entry_t, *ops, i);
1119               if (dump_file && (dump_flags & TDF_DETAILS))
1120                 {
1121                   fprintf (dump_file, " + ");
1122                   print_generic_expr (dump_file, oe2->op, 0);
1123                 }
1124               zero_one_operation (&oe2->op, c->oecode, c->op);
1125               sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
1126               oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node);
1127               oe2->rank = 0;
1128               oe1->op = gimple_get_lhs (sum);
1129             }
1130
1131           /* Apply the multiplication/division.  */
1132           prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode);
1133           if (dump_file && (dump_flags & TDF_DETAILS))
1134             {
1135               fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/");
1136               print_generic_expr (dump_file, c->op, 0);
1137               fprintf (dump_file, "\n");
1138             }
1139
1140           /* Record it in the addition chain and disable further
1141              undistribution with this op.  */
1142           oe1->op = gimple_assign_lhs (prod);
1143           oe1->rank = get_rank (oe1->op);
1144           VEC_free (operand_entry_t, heap, subops[first]);
1145
1146           changed = true;
1147         }
1148
1149       VEC_pop (oecount, cvec);
1150     }
1151
1152   for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i)
1153     VEC_free (operand_entry_t, heap, subops[i]);
1154   free (subops);
1155   VEC_free (oecount, heap, cvec);
1156   sbitmap_free (candidates);
1157   sbitmap_free (candidates2);
1158
1159   return changed;
1160 }
1161
1162
1163 /* Perform various identities and other optimizations on the list of
1164    operand entries, stored in OPS.  The tree code for the binary
1165    operation between all the operands is OPCODE.  */
1166
1167 static void
1168 optimize_ops_list (enum tree_code opcode,
1169                    VEC (operand_entry_t, heap) **ops)
1170 {
1171   unsigned int length = VEC_length (operand_entry_t, *ops);
1172   unsigned int i;
1173   operand_entry_t oe;
1174   operand_entry_t oelast = NULL;
1175   bool iterate = false;
1176
1177   if (length == 1)
1178     return;
1179
1180   oelast = VEC_last (operand_entry_t, *ops);
1181
1182   /* If the last two are constants, pop the constants off, merge them
1183      and try the next two.  */
1184   if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
1185     {
1186       operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
1187
1188       if (oelm1->rank == 0
1189           && is_gimple_min_invariant (oelm1->op)
1190           && useless_type_conversion_p (TREE_TYPE (oelm1->op),
1191                                        TREE_TYPE (oelast->op)))
1192         {
1193           tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
1194                                      oelm1->op, oelast->op);
1195
1196           if (folded && is_gimple_min_invariant (folded))
1197             {
1198               if (dump_file && (dump_flags & TDF_DETAILS))
1199                 fprintf (dump_file, "Merging constants\n");
1200
1201               VEC_pop (operand_entry_t, *ops);
1202               VEC_pop (operand_entry_t, *ops);
1203
1204               add_to_ops_vec (ops, folded);
1205               reassociate_stats.constants_eliminated++;
1206
1207               optimize_ops_list (opcode, ops);
1208               return;
1209             }
1210         }
1211     }
1212
1213   eliminate_using_constants (opcode, ops);
1214   oelast = NULL;
1215
1216   for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
1217     {
1218       bool done = false;
1219
1220       if (eliminate_not_pairs (opcode, ops, i, oe))
1221         return;
1222       if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
1223           || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
1224         {
1225           if (done)
1226             return;
1227           iterate = true;
1228           oelast = NULL;
1229           continue;
1230         }
1231       oelast = oe;
1232       i++;
1233     }
1234
1235   length  = VEC_length (operand_entry_t, *ops);
1236   oelast = VEC_last (operand_entry_t, *ops);
1237
1238   if (iterate)
1239     optimize_ops_list (opcode, ops);
1240 }
1241
1242 /* Return true if OPERAND is defined by a PHI node which uses the LHS
1243    of STMT in it's operands.  This is also known as a "destructive
1244    update" operation.  */
1245
1246 static bool
1247 is_phi_for_stmt (gimple stmt, tree operand)
1248 {
1249   gimple def_stmt;
1250   tree lhs;
1251   use_operand_p arg_p;
1252   ssa_op_iter i;
1253
1254   if (TREE_CODE (operand) != SSA_NAME)
1255     return false;
1256
1257   lhs = gimple_assign_lhs (stmt);
1258
1259   def_stmt = SSA_NAME_DEF_STMT (operand);
1260   if (gimple_code (def_stmt) != GIMPLE_PHI)
1261     return false;
1262
1263   FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
1264     if (lhs == USE_FROM_PTR (arg_p))
1265       return true;
1266   return false;
1267 }
1268
1269 /* Remove def stmt of VAR if VAR has zero uses and recurse
1270    on rhs1 operand if so.  */
1271
1272 static void
1273 remove_visited_stmt_chain (tree var)
1274 {
1275   gimple stmt;
1276   gimple_stmt_iterator gsi;
1277
1278   while (1)
1279     {
1280       if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
1281         return;
1282       stmt = SSA_NAME_DEF_STMT (var);
1283       if (!is_gimple_assign (stmt)
1284           || !gimple_visited_p (stmt))
1285         return;
1286       var = gimple_assign_rhs1 (stmt);
1287       gsi = gsi_for_stmt (stmt);
1288       gsi_remove (&gsi, true);
1289       release_defs (stmt);
1290     }
1291 }
1292
1293 /* Recursively rewrite our linearized statements so that the operators
1294    match those in OPS[OPINDEX], putting the computation in rank
1295    order.  */
1296
1297 static void
1298 rewrite_expr_tree (gimple stmt, unsigned int opindex,
1299                    VEC(operand_entry_t, heap) * ops, bool moved)
1300 {
1301   tree rhs1 = gimple_assign_rhs1 (stmt);
1302   tree rhs2 = gimple_assign_rhs2 (stmt);
1303   operand_entry_t oe;
1304
1305   /* If we have three operands left, then we want to make sure the one
1306      that gets the double binary op are the ones with the same rank.
1307
1308      The alternative we try is to see if this is a destructive
1309      update style statement, which is like:
1310      b = phi (a, ...)
1311      a = c + b;
1312      In that case, we want to use the destructive update form to
1313      expose the possible vectorizer sum reduction opportunity.
1314      In that case, the third operand will be the phi node.
1315
1316      We could, of course, try to be better as noted above, and do a
1317      lot of work to try to find these opportunities in >3 operand
1318      cases, but it is unlikely to be worth it.  */
1319   if (opindex + 3 == VEC_length (operand_entry_t, ops))
1320     {
1321       operand_entry_t oe1, oe2, oe3;
1322
1323       oe1 = VEC_index (operand_entry_t, ops, opindex);
1324       oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
1325       oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
1326
1327       if ((oe1->rank == oe2->rank
1328            && oe2->rank != oe3->rank)
1329           || (is_phi_for_stmt (stmt, oe3->op)
1330               && !is_phi_for_stmt (stmt, oe1->op)
1331               && !is_phi_for_stmt (stmt, oe2->op)))
1332         {
1333           struct operand_entry temp = *oe3;
1334           oe3->op = oe1->op;
1335           oe3->rank = oe1->rank;
1336           oe1->op = temp.op;
1337           oe1->rank= temp.rank;
1338         }
1339       else if ((oe1->rank == oe3->rank
1340                 && oe2->rank != oe3->rank)
1341                || (is_phi_for_stmt (stmt, oe2->op)
1342                    && !is_phi_for_stmt (stmt, oe1->op)
1343                    && !is_phi_for_stmt (stmt, oe3->op)))
1344         {
1345           struct operand_entry temp = *oe2;
1346           oe2->op = oe1->op;
1347           oe2->rank = oe1->rank;
1348           oe1->op = temp.op;
1349           oe1->rank= temp.rank;
1350         }
1351     }
1352
1353   /* The final recursion case for this function is that you have
1354      exactly two operations left.
1355      If we had one exactly one op in the entire list to start with, we
1356      would have never called this function, and the tail recursion
1357      rewrites them one at a time.  */
1358   if (opindex + 2 == VEC_length (operand_entry_t, ops))
1359     {
1360       operand_entry_t oe1, oe2;
1361
1362       oe1 = VEC_index (operand_entry_t, ops, opindex);
1363       oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
1364
1365       if (rhs1 != oe1->op || rhs2 != oe2->op)
1366         {
1367           if (dump_file && (dump_flags & TDF_DETAILS))
1368             {
1369               fprintf (dump_file, "Transforming ");
1370               print_gimple_stmt (dump_file, stmt, 0, 0);
1371             }
1372
1373           gimple_assign_set_rhs1 (stmt, oe1->op);
1374           gimple_assign_set_rhs2 (stmt, oe2->op);
1375           update_stmt (stmt);
1376           if (rhs1 != oe1->op && rhs1 != oe2->op)
1377             remove_visited_stmt_chain (rhs1);
1378
1379           if (dump_file && (dump_flags & TDF_DETAILS))
1380             {
1381               fprintf (dump_file, " into ");
1382               print_gimple_stmt (dump_file, stmt, 0, 0);
1383             }
1384
1385         }
1386       return;
1387     }
1388
1389   /* If we hit here, we should have 3 or more ops left.  */
1390   gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
1391
1392   /* Rewrite the next operator.  */
1393   oe = VEC_index (operand_entry_t, ops, opindex);
1394
1395   if (oe->op != rhs2)
1396     {
1397       if (!moved)
1398         {
1399           gimple_stmt_iterator gsinow, gsirhs1;
1400           gimple stmt1 = stmt, stmt2;
1401           unsigned int count;
1402
1403           gsinow = gsi_for_stmt (stmt);
1404           count = VEC_length (operand_entry_t, ops) - opindex - 2;
1405           while (count-- != 0)
1406             {
1407               stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
1408               gsirhs1 = gsi_for_stmt (stmt2);
1409               gsi_move_before (&gsirhs1, &gsinow);
1410               gsi_prev (&gsinow);
1411               stmt1 = stmt2;
1412             }
1413           moved = true;
1414         }
1415
1416       if (dump_file && (dump_flags & TDF_DETAILS))
1417         {
1418           fprintf (dump_file, "Transforming ");
1419           print_gimple_stmt (dump_file, stmt, 0, 0);
1420         }
1421
1422       gimple_assign_set_rhs2 (stmt, oe->op);
1423       update_stmt (stmt);
1424
1425       if (dump_file && (dump_flags & TDF_DETAILS))
1426         {
1427           fprintf (dump_file, " into ");
1428           print_gimple_stmt (dump_file, stmt, 0, 0);
1429         }
1430     }
1431   /* Recurse on the LHS of the binary operator, which is guaranteed to
1432      be the non-leaf side.  */
1433   rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved);
1434 }
1435
1436 /* Transform STMT, which is really (A +B) + (C + D) into the left
1437    linear form, ((A+B)+C)+D.
1438    Recurse on D if necessary.  */
1439
1440 static void
1441 linearize_expr (gimple stmt)
1442 {
1443   gimple_stmt_iterator gsinow, gsirhs;
1444   gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
1445   gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1446   enum tree_code rhscode = gimple_assign_rhs_code (stmt);
1447   gimple newbinrhs = NULL;
1448   struct loop *loop = loop_containing_stmt (stmt);
1449
1450   gcc_assert (is_reassociable_op (binlhs, rhscode, loop)
1451               && is_reassociable_op (binrhs, rhscode, loop));
1452
1453   gsinow = gsi_for_stmt (stmt);
1454   gsirhs = gsi_for_stmt (binrhs);
1455   gsi_move_before (&gsirhs, &gsinow);
1456
1457   gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
1458   gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs));
1459   gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs));
1460
1461   if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
1462     newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1463
1464   if (dump_file && (dump_flags & TDF_DETAILS))
1465     {
1466       fprintf (dump_file, "Linearized: ");
1467       print_gimple_stmt (dump_file, stmt, 0, 0);
1468     }
1469
1470   reassociate_stats.linearized++;
1471   update_stmt (binrhs);
1472   update_stmt (binlhs);
1473   update_stmt (stmt);
1474
1475   gimple_set_visited (stmt, true);
1476   gimple_set_visited (binlhs, true);
1477   gimple_set_visited (binrhs, true);
1478
1479   /* Tail recurse on the new rhs if it still needs reassociation.  */
1480   if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
1481     /* ??? This should probably be linearize_expr (newbinrhs) but I don't
1482            want to change the algorithm while converting to tuples.  */
1483     linearize_expr (stmt);
1484 }
1485
1486 /* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return
1487    it.  Otherwise, return NULL.  */
1488
1489 static gimple
1490 get_single_immediate_use (tree lhs)
1491 {
1492   use_operand_p immuse;
1493   gimple immusestmt;
1494
1495   if (TREE_CODE (lhs) == SSA_NAME
1496       && single_imm_use (lhs, &immuse, &immusestmt)
1497       && is_gimple_assign (immusestmt))
1498     return immusestmt;
1499
1500   return NULL;
1501 }
1502
1503 static VEC(tree, heap) *broken_up_subtracts;
1504
1505 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
1506    representing the negated value.  Insertions of any necessary
1507    instructions go before GSI.
1508    This function is recursive in that, if you hand it "a_5" as the
1509    value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1510    transform b_3 + b_4 into a_5 = -b_3 + -b_4.  */
1511
1512 static tree
1513 negate_value (tree tonegate, gimple_stmt_iterator *gsi)
1514 {
1515   gimple negatedefstmt= NULL;
1516   tree resultofnegate;
1517
1518   /* If we are trying to negate a name, defined by an add, negate the
1519      add operands instead.  */
1520   if (TREE_CODE (tonegate) == SSA_NAME)
1521     negatedefstmt = SSA_NAME_DEF_STMT (tonegate);
1522   if (TREE_CODE (tonegate) == SSA_NAME
1523       && is_gimple_assign (negatedefstmt)
1524       && TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME
1525       && has_single_use (gimple_assign_lhs (negatedefstmt))
1526       && gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR)
1527     {
1528       gimple_stmt_iterator gsi;
1529       tree rhs1 = gimple_assign_rhs1 (negatedefstmt);
1530       tree rhs2 = gimple_assign_rhs2 (negatedefstmt);
1531
1532       gsi = gsi_for_stmt (negatedefstmt);
1533       rhs1 = negate_value (rhs1, &gsi);
1534       gimple_assign_set_rhs1 (negatedefstmt, rhs1);
1535
1536       gsi = gsi_for_stmt (negatedefstmt);
1537       rhs2 = negate_value (rhs2, &gsi);
1538       gimple_assign_set_rhs2 (negatedefstmt, rhs2);
1539
1540       update_stmt (negatedefstmt);
1541       return gimple_assign_lhs (negatedefstmt);
1542     }
1543
1544   tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
1545   resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true,
1546                                              NULL_TREE, true, GSI_SAME_STMT);
1547   VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
1548   return resultofnegate;
1549 }
1550
1551 /* Return true if we should break up the subtract in STMT into an add
1552    with negate.  This is true when we the subtract operands are really
1553    adds, or the subtract itself is used in an add expression.  In
1554    either case, breaking up the subtract into an add with negate
1555    exposes the adds to reassociation.  */
1556
1557 static bool
1558 should_break_up_subtract (gimple stmt)
1559 {
1560   tree lhs = gimple_assign_lhs (stmt);
1561   tree binlhs = gimple_assign_rhs1 (stmt);
1562   tree binrhs = gimple_assign_rhs2 (stmt);
1563   gimple immusestmt;
1564   struct loop *loop = loop_containing_stmt (stmt);
1565
1566   if (TREE_CODE (binlhs) == SSA_NAME
1567       && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
1568     return true;
1569
1570   if (TREE_CODE (binrhs) == SSA_NAME
1571       && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
1572     return true;
1573
1574   if (TREE_CODE (lhs) == SSA_NAME
1575       && (immusestmt = get_single_immediate_use (lhs))
1576       && is_gimple_assign (immusestmt)
1577       && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR
1578           ||  gimple_assign_rhs_code (immusestmt) == MULT_EXPR))
1579     return true;
1580   return false;
1581 }
1582
1583 /* Transform STMT from A - B into A + -B.  */
1584
1585 static void
1586 break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip)
1587 {
1588   tree rhs1 = gimple_assign_rhs1 (stmt);
1589   tree rhs2 = gimple_assign_rhs2 (stmt);
1590
1591   if (dump_file && (dump_flags & TDF_DETAILS))
1592     {
1593       fprintf (dump_file, "Breaking up subtract ");
1594       print_gimple_stmt (dump_file, stmt, 0, 0);
1595     }
1596
1597   rhs2 = negate_value (rhs2, gsip);
1598   gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2);
1599   update_stmt (stmt);
1600 }
1601
1602 /* Recursively linearize a binary expression that is the RHS of STMT.
1603    Place the operands of the expression tree in the vector named OPS.  */
1604
1605 static void
1606 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
1607                      bool is_associative, bool set_visited)
1608 {
1609   tree binlhs = gimple_assign_rhs1 (stmt);
1610   tree binrhs = gimple_assign_rhs2 (stmt);
1611   gimple binlhsdef, binrhsdef;
1612   bool binlhsisreassoc = false;
1613   bool binrhsisreassoc = false;
1614   enum tree_code rhscode = gimple_assign_rhs_code (stmt);
1615   struct loop *loop = loop_containing_stmt (stmt);
1616
1617   if (set_visited)
1618     gimple_set_visited (stmt, true);
1619
1620   if (TREE_CODE (binlhs) == SSA_NAME)
1621     {
1622       binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1623       binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
1624     }
1625
1626   if (TREE_CODE (binrhs) == SSA_NAME)
1627     {
1628       binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1629       binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
1630     }
1631
1632   /* If the LHS is not reassociable, but the RHS is, we need to swap
1633      them.  If neither is reassociable, there is nothing we can do, so
1634      just put them in the ops vector.  If the LHS is reassociable,
1635      linearize it.  If both are reassociable, then linearize the RHS
1636      and the LHS.  */
1637
1638   if (!binlhsisreassoc)
1639     {
1640       tree temp;
1641
1642       /* If this is not a associative operation like division, give up.  */
1643       if (!is_associative)
1644         {
1645           add_to_ops_vec (ops, binrhs);
1646           return;
1647         }
1648
1649       if (!binrhsisreassoc)
1650         {
1651           add_to_ops_vec (ops, binrhs);
1652           add_to_ops_vec (ops, binlhs);
1653           return;
1654         }
1655
1656       if (dump_file && (dump_flags & TDF_DETAILS))
1657         {
1658           fprintf (dump_file, "swapping operands of ");
1659           print_gimple_stmt (dump_file, stmt, 0, 0);
1660         }
1661
1662       swap_tree_operands (stmt,
1663                           gimple_assign_rhs1_ptr (stmt),
1664                           gimple_assign_rhs2_ptr (stmt));
1665       update_stmt (stmt);
1666
1667       if (dump_file && (dump_flags & TDF_DETAILS))
1668         {
1669           fprintf (dump_file, " is now ");
1670           print_gimple_stmt (dump_file, stmt, 0, 0);
1671         }
1672
1673       /* We want to make it so the lhs is always the reassociative op,
1674          so swap.  */
1675       temp = binlhs;
1676       binlhs = binrhs;
1677       binrhs = temp;
1678     }
1679   else if (binrhsisreassoc)
1680     {
1681       linearize_expr (stmt);
1682       binlhs = gimple_assign_rhs1 (stmt);
1683       binrhs = gimple_assign_rhs2 (stmt);
1684     }
1685
1686   gcc_assert (TREE_CODE (binrhs) != SSA_NAME
1687               || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
1688                                       rhscode, loop));
1689   linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
1690                        is_associative, set_visited);
1691   add_to_ops_vec (ops, binrhs);
1692 }
1693
1694 /* Repropagate the negates back into subtracts, since no other pass
1695    currently does it.  */
1696
1697 static void
1698 repropagate_negates (void)
1699 {
1700   unsigned int i = 0;
1701   tree negate;
1702
1703   for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
1704     {
1705       gimple user = get_single_immediate_use (negate);
1706
1707       /* The negate operand can be either operand of a PLUS_EXPR
1708          (it can be the LHS if the RHS is a constant for example).
1709
1710          Force the negate operand to the RHS of the PLUS_EXPR, then
1711          transform the PLUS_EXPR into a MINUS_EXPR.  */
1712       if (user
1713           && is_gimple_assign (user)
1714           && gimple_assign_rhs_code (user) == PLUS_EXPR)
1715         {
1716           /* If the negated operand appears on the LHS of the
1717              PLUS_EXPR, exchange the operands of the PLUS_EXPR
1718              to force the negated operand to the RHS of the PLUS_EXPR.  */
1719           if (gimple_assign_rhs1 (user) == negate)
1720             {
1721               swap_tree_operands (user,
1722                                   gimple_assign_rhs1_ptr (user),
1723                                   gimple_assign_rhs2_ptr (user));
1724             }
1725
1726           /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1727              the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR.  */
1728           if (gimple_assign_rhs2 (user) == negate)
1729             {
1730               tree rhs1 = gimple_assign_rhs1 (user);
1731               tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
1732               gimple_stmt_iterator gsi = gsi_for_stmt (user);
1733               gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
1734               update_stmt (user);
1735             }
1736         }
1737     }
1738 }
1739
1740 /* Break up subtract operations in block BB.
1741
1742    We do this top down because we don't know whether the subtract is
1743    part of a possible chain of reassociation except at the top.
1744
1745    IE given
1746    d = f + g
1747    c = a + e
1748    b = c - d
1749    q = b - r
1750    k = t - q
1751
1752    we want to break up k = t - q, but we won't until we've transformed q
1753    = b - r, which won't be broken up until we transform b = c - d.
1754
1755    En passant, clear the GIMPLE visited flag on every statement.  */
1756
1757 static void
1758 break_up_subtract_bb (basic_block bb)
1759 {
1760   gimple_stmt_iterator gsi;
1761   basic_block son;
1762
1763   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1764     {
1765       gimple stmt = gsi_stmt (gsi);
1766       gimple_set_visited (stmt, false);
1767
1768       /* Look for simple gimple subtract operations.  */
1769       if (is_gimple_assign (stmt)
1770           && gimple_assign_rhs_code (stmt) == MINUS_EXPR)
1771         {
1772           tree lhs = gimple_assign_lhs (stmt);
1773           tree rhs1 = gimple_assign_rhs1 (stmt);
1774           tree rhs2 = gimple_assign_rhs2 (stmt);
1775
1776           /* If associative-math we can do reassociation for
1777              non-integral types.  Or, we can do reassociation for
1778              non-saturating fixed-point types.  */
1779           if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1780                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1781                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1782               && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
1783                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
1784                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
1785                   || !flag_associative_math)
1786               && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
1787                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
1788                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
1789             continue;
1790
1791           /* Check for a subtract used only in an addition.  If this
1792              is the case, transform it into add of a negate for better
1793              reassociation.  IE transform C = A-B into C = A + -B if C
1794              is only used in an addition.  */
1795           if (should_break_up_subtract (stmt))
1796             break_up_subtract (stmt, &gsi);
1797         }
1798     }
1799   for (son = first_dom_son (CDI_DOMINATORS, bb);
1800        son;
1801        son = next_dom_son (CDI_DOMINATORS, son))
1802     break_up_subtract_bb (son);
1803 }
1804
1805 /* Reassociate expressions in basic block BB and its post-dominator as
1806    children.  */
1807
1808 static void
1809 reassociate_bb (basic_block bb)
1810 {
1811   gimple_stmt_iterator gsi;
1812   basic_block son;
1813
1814   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1815     {
1816       gimple stmt = gsi_stmt (gsi);
1817
1818       if (is_gimple_assign (stmt))
1819         {
1820           tree lhs, rhs1, rhs2;
1821           enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1822
1823           /* If this is not a gimple binary expression, there is
1824              nothing for us to do with it.  */
1825           if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS)
1826             continue;
1827
1828           /* If this was part of an already processed statement,
1829              we don't need to touch it again. */
1830           if (gimple_visited_p (stmt))
1831             {
1832               /* This statement might have become dead because of previous
1833                  reassociations.  */
1834               if (has_zero_uses (gimple_get_lhs (stmt)))
1835                 {
1836                   gsi_remove (&gsi, true);
1837                   release_defs (stmt);
1838                   /* We might end up removing the last stmt above which
1839                      places the iterator to the end of the sequence.
1840                      Reset it to the last stmt in this case which might
1841                      be the end of the sequence as well if we removed
1842                      the last statement of the sequence.  In which case
1843                      we need to bail out.  */
1844                   if (gsi_end_p (gsi))
1845                     {
1846                       gsi = gsi_last_bb (bb);
1847                       if (gsi_end_p (gsi))
1848                         break;
1849                     }
1850                 }
1851               continue;
1852             }
1853
1854           lhs = gimple_assign_lhs (stmt);
1855           rhs1 = gimple_assign_rhs1 (stmt);
1856           rhs2 = gimple_assign_rhs2 (stmt);
1857
1858           /* If associative-math we can do reassociation for
1859              non-integral types.  Or, we can do reassociation for
1860              non-saturating fixed-point types.  */
1861           if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1862                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1863                || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1864               && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
1865                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
1866                   || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
1867                   || !flag_associative_math)
1868               && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
1869                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
1870                   || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
1871             continue;
1872
1873           if (associative_tree_code (rhs_code))
1874             {
1875               VEC(operand_entry_t, heap) *ops = NULL;
1876
1877               /* There may be no immediate uses left by the time we
1878                  get here because we may have eliminated them all.  */
1879               if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
1880                 continue;
1881
1882               gimple_set_visited (stmt, true);
1883               linearize_expr_tree (&ops, stmt, true, true);
1884               qsort (VEC_address (operand_entry_t, ops),
1885                      VEC_length (operand_entry_t, ops),
1886                      sizeof (operand_entry_t),
1887                      sort_by_operand_rank);
1888               optimize_ops_list (rhs_code, &ops);
1889               if (undistribute_ops_list (rhs_code, &ops,
1890                                          loop_containing_stmt (stmt)))
1891                 {
1892                   qsort (VEC_address (operand_entry_t, ops),
1893                          VEC_length (operand_entry_t, ops),
1894                          sizeof (operand_entry_t),
1895                          sort_by_operand_rank);
1896                   optimize_ops_list (rhs_code, &ops);
1897                 }
1898
1899               if (VEC_length (operand_entry_t, ops) == 1)
1900                 {
1901                   if (dump_file && (dump_flags & TDF_DETAILS))
1902                     {
1903                       fprintf (dump_file, "Transforming ");
1904                       print_gimple_stmt (dump_file, stmt, 0, 0);
1905                     }
1906
1907                   rhs1 = gimple_assign_rhs1 (stmt);
1908                   gimple_assign_set_rhs_from_tree (&gsi,
1909                                                    VEC_last (operand_entry_t,
1910                                                              ops)->op);
1911                   update_stmt (stmt);
1912                   remove_visited_stmt_chain (rhs1);
1913
1914                   if (dump_file && (dump_flags & TDF_DETAILS))
1915                     {
1916                       fprintf (dump_file, " into ");
1917                       print_gimple_stmt (dump_file, stmt, 0, 0);
1918                     }
1919                 }
1920               else
1921                 rewrite_expr_tree (stmt, 0, ops, false);
1922
1923               VEC_free (operand_entry_t, heap, ops);
1924             }
1925         }
1926     }
1927   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
1928        son;
1929        son = next_dom_son (CDI_POST_DOMINATORS, son))
1930     reassociate_bb (son);
1931 }
1932
1933 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
1934 void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
1935
1936 /* Dump the operand entry vector OPS to FILE.  */
1937
1938 void
1939 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
1940 {
1941   operand_entry_t oe;
1942   unsigned int i;
1943
1944   for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
1945     {
1946       fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
1947       print_generic_expr (file, oe->op, 0);
1948     }
1949 }
1950
1951 /* Dump the operand entry vector OPS to STDERR.  */
1952
1953 void
1954 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
1955 {
1956   dump_ops_vector (stderr, ops);
1957 }
1958
1959 static void
1960 do_reassoc (void)
1961 {
1962   break_up_subtract_bb (ENTRY_BLOCK_PTR);
1963   reassociate_bb (EXIT_BLOCK_PTR);
1964 }
1965
1966 /* Initialize the reassociation pass.  */
1967
1968 static void
1969 init_reassoc (void)
1970 {
1971   int i;
1972   long rank = 2;
1973   tree param;
1974   int *bbs = XNEWVEC (int, last_basic_block + 1);
1975
1976   /* Find the loops, so that we can prevent moving calculations in
1977      them.  */
1978   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1979
1980   memset (&reassociate_stats, 0, sizeof (reassociate_stats));
1981
1982   operand_entry_pool = create_alloc_pool ("operand entry pool",
1983                                           sizeof (struct operand_entry), 30);
1984
1985   /* Reverse RPO (Reverse Post Order) will give us something where
1986      deeper loops come later.  */
1987   pre_and_rev_post_order_compute (NULL, bbs, false);
1988   bb_rank = XCNEWVEC (long, last_basic_block + 1);
1989   operand_rank = pointer_map_create ();
1990
1991   /* Give each argument a distinct rank.   */
1992   for (param = DECL_ARGUMENTS (current_function_decl);
1993        param;
1994        param = TREE_CHAIN (param))
1995     {
1996       if (gimple_default_def (cfun, param) != NULL)
1997         {
1998           tree def = gimple_default_def (cfun, param);
1999           insert_operand_rank (def, ++rank);
2000         }
2001     }
2002
2003   /* Give the chain decl a distinct rank. */
2004   if (cfun->static_chain_decl != NULL)
2005     {
2006       tree def = gimple_default_def (cfun, cfun->static_chain_decl);
2007       if (def != NULL)
2008         insert_operand_rank (def, ++rank);
2009     }
2010
2011   /* Set up rank for each BB  */
2012   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2013     bb_rank[bbs[i]] = ++rank  << 16;
2014
2015   free (bbs);
2016   calculate_dominance_info (CDI_POST_DOMINATORS);
2017   broken_up_subtracts = NULL;
2018 }
2019
2020 /* Cleanup after the reassociation pass, and print stats if
2021    requested.  */
2022
2023 static void
2024 fini_reassoc (void)
2025 {
2026   statistics_counter_event (cfun, "Linearized",
2027                             reassociate_stats.linearized);
2028   statistics_counter_event (cfun, "Constants eliminated",
2029                             reassociate_stats.constants_eliminated);
2030   statistics_counter_event (cfun, "Ops eliminated",
2031                             reassociate_stats.ops_eliminated);
2032   statistics_counter_event (cfun, "Statements rewritten",
2033                             reassociate_stats.rewritten);
2034
2035   pointer_map_destroy (operand_rank);
2036   free_alloc_pool (operand_entry_pool);
2037   free (bb_rank);
2038   VEC_free (tree, heap, broken_up_subtracts);
2039   free_dominance_info (CDI_POST_DOMINATORS);
2040   loop_optimizer_finalize ();
2041 }
2042
2043 /* Gate and execute functions for Reassociation.  */
2044
2045 static unsigned int
2046 execute_reassoc (void)
2047 {
2048   init_reassoc ();
2049
2050   do_reassoc ();
2051   repropagate_negates ();
2052
2053   fini_reassoc ();
2054   return 0;
2055 }
2056
2057 static bool
2058 gate_tree_ssa_reassoc (void)
2059 {
2060   return flag_tree_reassoc != 0;
2061 }
2062
2063 struct gimple_opt_pass pass_reassoc =
2064 {
2065  {
2066   GIMPLE_PASS,
2067   "reassoc",                            /* name */
2068   gate_tree_ssa_reassoc,                /* gate */
2069   execute_reassoc,                      /* execute */
2070   NULL,                                 /* sub */
2071   NULL,                                 /* next */
2072   0,                                    /* static_pass_number */
2073   TV_TREE_REASSOC,                      /* tv_id */
2074   PROP_cfg | PROP_ssa,                  /* properties_required */
2075   0,                                    /* properties_provided */
2076   0,                                    /* properties_destroyed */
2077   0,                                    /* todo_flags_start */
2078   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2079  }
2080 };
2081