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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 */
163static struct
164{
165  int linearized;
166  int constants_eliminated;
167  int ops_eliminated;
168  int rewritten;
169} reassociate_stats;
170
171/* Operator, rank pair.  */
172typedef struct operand_entry
173{
174  unsigned int rank;
175  tree op;
176} *operand_entry_t;
177
178static 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.  */
184static long *bb_rank;
185
186/* Operand->rank hashtable.  */
187static struct pointer_map_t *operand_rank;
188
189
190/* Look up the operand rank structure for expression E.  */
191
192static inline long
193find_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
201static inline void
202insert_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
213static long
214get_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
297DEF_VEC_P(operand_entry_t);
298DEF_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.  */
308static inline int
309constant_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.  */
321static int
322sort_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
345static void
346add_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
358static bool
359is_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
381static tree
382get_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
398static bool
399eliminate_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
476static bool
477eliminate_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
533static bool
534eliminate_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
602static void
603eliminate_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
731static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
732				 bool, bool);
733
734/* Structure for tracking and counting operands.  */
735typedef struct oecount_s {
736  int cnt;
737  enum tree_code oecode;
738  tree op;
739} oecount;
740
741DEF_VEC_O(oecount);
742DEF_VEC_ALLOC_O(oecount,heap);
743
744/* The heap for the oecount hashtable and the sorted list of operands.  */
745static VEC (oecount, heap) *cvec;
746
747/* Hash function for oecount.  */
748
749static hashval_t
750oecount_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
758static int
759oecount_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
769static int
770oecount_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
781static void
782zero_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
827static gimple
828build_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
943static bool
944undistribute_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
1167static void
1168optimize_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
1246static bool
1247is_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
1272static void
1273remove_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
1297static void
1298rewrite_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
1440static void
1441linearize_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
1489static gimple
1490get_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
1503static 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
1512static tree
1513negate_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
1557static bool
1558should_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
1585static void
1586break_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
1605static void
1606linearize_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			 && !stmt_could_throw_p (binlhsdef));
1625    }
1626
1627  if (TREE_CODE (binrhs) == SSA_NAME)
1628    {
1629      binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1630      binrhsisreassoc = (is_reassociable_op (binrhsdef, rhscode, loop)
1631			 && !stmt_could_throw_p (binrhsdef));
1632    }
1633
1634  /* If the LHS is not reassociable, but the RHS is, we need to swap
1635     them.  If neither is reassociable, there is nothing we can do, so
1636     just put them in the ops vector.  If the LHS is reassociable,
1637     linearize it.  If both are reassociable, then linearize the RHS
1638     and the LHS.  */
1639
1640  if (!binlhsisreassoc)
1641    {
1642      tree temp;
1643
1644      /* If this is not a associative operation like division, give up.  */
1645      if (!is_associative)
1646	{
1647	  add_to_ops_vec (ops, binrhs);
1648	  return;
1649	}
1650
1651      if (!binrhsisreassoc)
1652	{
1653	  add_to_ops_vec (ops, binrhs);
1654	  add_to_ops_vec (ops, binlhs);
1655	  return;
1656	}
1657
1658      if (dump_file && (dump_flags & TDF_DETAILS))
1659	{
1660	  fprintf (dump_file, "swapping operands of ");
1661	  print_gimple_stmt (dump_file, stmt, 0, 0);
1662	}
1663
1664      swap_tree_operands (stmt,
1665			  gimple_assign_rhs1_ptr (stmt),
1666			  gimple_assign_rhs2_ptr (stmt));
1667      update_stmt (stmt);
1668
1669      if (dump_file && (dump_flags & TDF_DETAILS))
1670	{
1671	  fprintf (dump_file, " is now ");
1672	  print_gimple_stmt (dump_file, stmt, 0, 0);
1673	}
1674
1675      /* We want to make it so the lhs is always the reassociative op,
1676	 so swap.  */
1677      temp = binlhs;
1678      binlhs = binrhs;
1679      binrhs = temp;
1680    }
1681  else if (binrhsisreassoc)
1682    {
1683      linearize_expr (stmt);
1684      binlhs = gimple_assign_rhs1 (stmt);
1685      binrhs = gimple_assign_rhs2 (stmt);
1686    }
1687
1688  gcc_assert (TREE_CODE (binrhs) != SSA_NAME
1689	      || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
1690				      rhscode, loop));
1691  linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
1692		       is_associative, set_visited);
1693  add_to_ops_vec (ops, binrhs);
1694}
1695
1696/* Repropagate the negates back into subtracts, since no other pass
1697   currently does it.  */
1698
1699static void
1700repropagate_negates (void)
1701{
1702  unsigned int i = 0;
1703  tree negate;
1704
1705  for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
1706    {
1707      gimple user = get_single_immediate_use (negate);
1708
1709      /* The negate operand can be either operand of a PLUS_EXPR
1710	 (it can be the LHS if the RHS is a constant for example).
1711
1712	 Force the negate operand to the RHS of the PLUS_EXPR, then
1713	 transform the PLUS_EXPR into a MINUS_EXPR.  */
1714      if (user
1715	  && is_gimple_assign (user)
1716	  && gimple_assign_rhs_code (user) == PLUS_EXPR)
1717	{
1718	  /* If the negated operand appears on the LHS of the
1719	     PLUS_EXPR, exchange the operands of the PLUS_EXPR
1720	     to force the negated operand to the RHS of the PLUS_EXPR.  */
1721	  if (gimple_assign_rhs1 (user) == negate)
1722	    {
1723	      swap_tree_operands (user,
1724				  gimple_assign_rhs1_ptr (user),
1725				  gimple_assign_rhs2_ptr (user));
1726	    }
1727
1728	  /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1729	     the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR.  */
1730	  if (gimple_assign_rhs2 (user) == negate)
1731	    {
1732	      tree rhs1 = gimple_assign_rhs1 (user);
1733	      tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
1734	      gimple_stmt_iterator gsi = gsi_for_stmt (user);
1735	      gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
1736	      update_stmt (user);
1737	    }
1738	}
1739    }
1740}
1741
1742/* Break up subtract operations in block BB.
1743
1744   We do this top down because we don't know whether the subtract is
1745   part of a possible chain of reassociation except at the top.
1746
1747   IE given
1748   d = f + g
1749   c = a + e
1750   b = c - d
1751   q = b - r
1752   k = t - q
1753
1754   we want to break up k = t - q, but we won't until we've transformed q
1755   = b - r, which won't be broken up until we transform b = c - d.
1756
1757   En passant, clear the GIMPLE visited flag on every statement.  */
1758
1759static void
1760break_up_subtract_bb (basic_block bb)
1761{
1762  gimple_stmt_iterator gsi;
1763  basic_block son;
1764
1765  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1766    {
1767      gimple stmt = gsi_stmt (gsi);
1768      gimple_set_visited (stmt, false);
1769
1770      /* Look for simple gimple subtract operations.  */
1771      if (is_gimple_assign (stmt)
1772	  && gimple_assign_rhs_code (stmt) == MINUS_EXPR)
1773	{
1774	  tree lhs = gimple_assign_lhs (stmt);
1775	  tree rhs1 = gimple_assign_rhs1 (stmt);
1776	  tree rhs2 = gimple_assign_rhs2 (stmt);
1777
1778	  /* If associative-math we can do reassociation for
1779	     non-integral types.  Or, we can do reassociation for
1780	     non-saturating fixed-point types.  */
1781	  if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1782	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1783	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1784	      && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
1785		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
1786		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
1787		  || !flag_associative_math)
1788	      && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
1789		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
1790		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
1791	    continue;
1792
1793	  /* Check for a subtract used only in an addition.  If this
1794	     is the case, transform it into add of a negate for better
1795	     reassociation.  IE transform C = A-B into C = A + -B if C
1796	     is only used in an addition.  */
1797	  if (should_break_up_subtract (stmt))
1798	    break_up_subtract (stmt, &gsi);
1799	}
1800    }
1801  for (son = first_dom_son (CDI_DOMINATORS, bb);
1802       son;
1803       son = next_dom_son (CDI_DOMINATORS, son))
1804    break_up_subtract_bb (son);
1805}
1806
1807/* Reassociate expressions in basic block BB and its post-dominator as
1808   children.  */
1809
1810static void
1811reassociate_bb (basic_block bb)
1812{
1813  gimple_stmt_iterator gsi;
1814  basic_block son;
1815
1816  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1817    {
1818      gimple stmt = gsi_stmt (gsi);
1819
1820      if (is_gimple_assign (stmt)
1821	  && !stmt_could_throw_p (stmt))
1822	{
1823	  tree lhs, rhs1, rhs2;
1824	  enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1825
1826	  /* If this is not a gimple binary expression, there is
1827	     nothing for us to do with it.  */
1828	  if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS)
1829	    continue;
1830
1831	  /* If this was part of an already processed statement,
1832	     we don't need to touch it again. */
1833	  if (gimple_visited_p (stmt))
1834	    {
1835	      /* This statement might have become dead because of previous
1836		 reassociations.  */
1837	      if (has_zero_uses (gimple_get_lhs (stmt)))
1838		{
1839		  gsi_remove (&gsi, true);
1840		  release_defs (stmt);
1841		  /* We might end up removing the last stmt above which
1842		     places the iterator to the end of the sequence.
1843		     Reset it to the last stmt in this case which might
1844		     be the end of the sequence as well if we removed
1845		     the last statement of the sequence.  In which case
1846		     we need to bail out.  */
1847		  if (gsi_end_p (gsi))
1848		    {
1849		      gsi = gsi_last_bb (bb);
1850		      if (gsi_end_p (gsi))
1851			break;
1852		    }
1853		}
1854	      continue;
1855	    }
1856
1857	  lhs = gimple_assign_lhs (stmt);
1858	  rhs1 = gimple_assign_rhs1 (stmt);
1859	  rhs2 = gimple_assign_rhs2 (stmt);
1860
1861	  /* If associative-math we can do reassociation for
1862	     non-integral types.  Or, we can do reassociation for
1863	     non-saturating fixed-point types.  */
1864	  if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1865	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1866	       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1867	      && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
1868		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
1869		  || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
1870		  || !flag_associative_math)
1871	      && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
1872		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
1873		  || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
1874	    continue;
1875
1876	  if (associative_tree_code (rhs_code))
1877	    {
1878	      VEC(operand_entry_t, heap) *ops = NULL;
1879
1880	      /* There may be no immediate uses left by the time we
1881		 get here because we may have eliminated them all.  */
1882	      if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
1883		continue;
1884
1885	      gimple_set_visited (stmt, true);
1886	      linearize_expr_tree (&ops, stmt, true, true);
1887	      qsort (VEC_address (operand_entry_t, ops),
1888		     VEC_length (operand_entry_t, ops),
1889		     sizeof (operand_entry_t),
1890		     sort_by_operand_rank);
1891	      optimize_ops_list (rhs_code, &ops);
1892	      if (undistribute_ops_list (rhs_code, &ops,
1893					 loop_containing_stmt (stmt)))
1894		{
1895		  qsort (VEC_address (operand_entry_t, ops),
1896			 VEC_length (operand_entry_t, ops),
1897			 sizeof (operand_entry_t),
1898			 sort_by_operand_rank);
1899		  optimize_ops_list (rhs_code, &ops);
1900		}
1901
1902	      if (VEC_length (operand_entry_t, ops) == 1)
1903		{
1904		  if (dump_file && (dump_flags & TDF_DETAILS))
1905		    {
1906		      fprintf (dump_file, "Transforming ");
1907		      print_gimple_stmt (dump_file, stmt, 0, 0);
1908		    }
1909
1910		  rhs1 = gimple_assign_rhs1 (stmt);
1911		  gimple_assign_set_rhs_from_tree (&gsi,
1912						   VEC_last (operand_entry_t,
1913							     ops)->op);
1914		  update_stmt (stmt);
1915		  remove_visited_stmt_chain (rhs1);
1916
1917		  if (dump_file && (dump_flags & TDF_DETAILS))
1918		    {
1919		      fprintf (dump_file, " into ");
1920		      print_gimple_stmt (dump_file, stmt, 0, 0);
1921		    }
1922		}
1923	      else
1924		rewrite_expr_tree (stmt, 0, ops, false);
1925
1926	      VEC_free (operand_entry_t, heap, ops);
1927	    }
1928	}
1929    }
1930  for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
1931       son;
1932       son = next_dom_son (CDI_POST_DOMINATORS, son))
1933    reassociate_bb (son);
1934}
1935
1936void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
1937void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
1938
1939/* Dump the operand entry vector OPS to FILE.  */
1940
1941void
1942dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
1943{
1944  operand_entry_t oe;
1945  unsigned int i;
1946
1947  for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
1948    {
1949      fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
1950      print_generic_expr (file, oe->op, 0);
1951    }
1952}
1953
1954/* Dump the operand entry vector OPS to STDERR.  */
1955
1956void
1957debug_ops_vector (VEC (operand_entry_t, heap) *ops)
1958{
1959  dump_ops_vector (stderr, ops);
1960}
1961
1962static void
1963do_reassoc (void)
1964{
1965  break_up_subtract_bb (ENTRY_BLOCK_PTR);
1966  reassociate_bb (EXIT_BLOCK_PTR);
1967}
1968
1969/* Initialize the reassociation pass.  */
1970
1971static void
1972init_reassoc (void)
1973{
1974  int i;
1975  long rank = 2;
1976  tree param;
1977  int *bbs = XNEWVEC (int, last_basic_block + 1);
1978
1979  /* Find the loops, so that we can prevent moving calculations in
1980     them.  */
1981  loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1982
1983  memset (&reassociate_stats, 0, sizeof (reassociate_stats));
1984
1985  operand_entry_pool = create_alloc_pool ("operand entry pool",
1986					  sizeof (struct operand_entry), 30);
1987
1988  /* Reverse RPO (Reverse Post Order) will give us something where
1989     deeper loops come later.  */
1990  pre_and_rev_post_order_compute (NULL, bbs, false);
1991  bb_rank = XCNEWVEC (long, last_basic_block + 1);
1992  operand_rank = pointer_map_create ();
1993
1994  /* Give each argument a distinct rank.   */
1995  for (param = DECL_ARGUMENTS (current_function_decl);
1996       param;
1997       param = TREE_CHAIN (param))
1998    {
1999      if (gimple_default_def (cfun, param) != NULL)
2000	{
2001	  tree def = gimple_default_def (cfun, param);
2002	  insert_operand_rank (def, ++rank);
2003	}
2004    }
2005
2006  /* Give the chain decl a distinct rank. */
2007  if (cfun->static_chain_decl != NULL)
2008    {
2009      tree def = gimple_default_def (cfun, cfun->static_chain_decl);
2010      if (def != NULL)
2011	insert_operand_rank (def, ++rank);
2012    }
2013
2014  /* Set up rank for each BB  */
2015  for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2016    bb_rank[bbs[i]] = ++rank  << 16;
2017
2018  free (bbs);
2019  calculate_dominance_info (CDI_POST_DOMINATORS);
2020  broken_up_subtracts = NULL;
2021}
2022
2023/* Cleanup after the reassociation pass, and print stats if
2024   requested.  */
2025
2026static void
2027fini_reassoc (void)
2028{
2029  statistics_counter_event (cfun, "Linearized",
2030			    reassociate_stats.linearized);
2031  statistics_counter_event (cfun, "Constants eliminated",
2032			    reassociate_stats.constants_eliminated);
2033  statistics_counter_event (cfun, "Ops eliminated",
2034			    reassociate_stats.ops_eliminated);
2035  statistics_counter_event (cfun, "Statements rewritten",
2036			    reassociate_stats.rewritten);
2037
2038  pointer_map_destroy (operand_rank);
2039  free_alloc_pool (operand_entry_pool);
2040  free (bb_rank);
2041  VEC_free (tree, heap, broken_up_subtracts);
2042  free_dominance_info (CDI_POST_DOMINATORS);
2043  loop_optimizer_finalize ();
2044}
2045
2046/* Gate and execute functions for Reassociation.  */
2047
2048static unsigned int
2049execute_reassoc (void)
2050{
2051  init_reassoc ();
2052
2053  do_reassoc ();
2054  repropagate_negates ();
2055
2056  fini_reassoc ();
2057  return 0;
2058}
2059
2060static bool
2061gate_tree_ssa_reassoc (void)
2062{
2063  return flag_tree_reassoc != 0;
2064}
2065
2066struct gimple_opt_pass pass_reassoc =
2067{
2068 {
2069  GIMPLE_PASS,
2070  "reassoc",				/* name */
2071  gate_tree_ssa_reassoc,		/* gate */
2072  execute_reassoc,			/* execute */
2073  NULL,					/* sub */
2074  NULL,					/* next */
2075  0,					/* static_pass_number */
2076  TV_TREE_REASSOC,			/* tv_id */
2077  PROP_cfg | PROP_ssa,			/* properties_required */
2078  0,					/* properties_provided */
2079  0,					/* properties_destroyed */
2080  0,					/* todo_flags_start */
2081  TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2082 }
2083};
2084
2085