OSDN Git Service

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