Daily bump.
[official-gcc.git] / gcc / tree-ssa-reassoc.c
blob19e10398168b7e2910c5fa35cca220b09951ac5b
1 /* Reassociation for trees.
2 Copyright (C) 2005, 2007 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dan@dberlin.org>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "errors.h"
26 #include "ggc.h"
27 #include "tree.h"
28 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
32 #include "tree-gimple.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "tree-iterator.h"
36 #include "tree-pass.h"
37 #include "alloc-pool.h"
38 #include "vec.h"
39 #include "langhooks.h"
40 #include "pointer-set.h"
41 #include "cfgloop.h"
42 #include "flags.h"
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).
48 It consists of five steps:
50 1. Breaking up subtract operations into addition + negate, where
51 it would promote the reassociation of adds.
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
58 3. Optimization of the operand lists, eliminating things like a +
59 -a, a & a, etc.
61 4. Rewrite the expression trees we linearized and optimized so
62 they are in proper rank order.
64 5. Repropagate negates, as nothing else will clean it up ATM.
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:
69 We could do this much nicer theoretically, but don't (for reasons
70 explained after how to do it theoretically nice :P).
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.
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.
82 IE if you have to rewrite the following set of operands (listed with
83 rank in parentheses), with opcode PLUS_EXPR:
85 a (1), b (1), c (1), d (2), e (2)
88 We start with our merge worklist empty, and the ops list with all of
89 those on it.
91 You want to first merge all leaves of the same rank, as much as
92 possible.
94 So first build a binary op of
96 mergetmp = a + b, and put "mergetmp" on the merge worklist.
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.
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.)
106 Then build a binary op of d + e
107 mergetmp2 = d + e
109 and put mergetmp2 on the merge worklist.
111 so merge worklist = {mergetmp, c, mergetmp2}
113 Continue building binary ops of these operations until you have only
114 one operation left on the worklist.
116 So we have
118 build binary op
119 mergetmp3 = mergetmp + c
121 worklist = {mergetmp2, mergetmp3}
123 mergetmp4 = mergetmp2 + mergetmp3
125 worklist = {mergetmp4}
127 because we have one operation left, we can now just set the original
128 statement equal to the result of that operation.
130 This will at least expose a + b and d + e to redundancy elimination
131 as binary operations.
133 For extra points, you can reuse the old statements to build the
134 mergetmps, since you shouldn't run out.
136 So why don't we do this?
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
144 mergetmp = op1 + op2
145 newstmt = mergetmp + op3
147 instead of
148 mergetmp = op2 + op3
149 newstmt = mergetmp + op1
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.
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 ops are a 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. */
162 /* Statistics */
163 static struct
165 int linearized;
166 int constants_eliminated;
167 int ops_eliminated;
168 int rewritten;
169 } reassociate_stats;
171 /* Operator, rank pair. */
172 typedef struct operand_entry
174 unsigned int rank;
175 tree op;
176 } *operand_entry_t;
178 static alloc_pool operand_entry_pool;
181 /* Starting rank number for a given basic block, so that we can rank
182 operations using unmovable instructions in that BB based on the bb
183 depth. */
184 static long *bb_rank;
186 /* Operand->rank hashtable. */
187 static struct pointer_map_t *operand_rank;
190 /* Look up the operand rank structure for expression E. */
192 static inline long
193 find_operand_rank (tree e)
195 void **slot = pointer_map_contains (operand_rank, e);
196 return slot ? (long) *slot : -1;
199 /* Insert {E,RANK} into the operand rank hashtable. */
201 static inline void
202 insert_operand_rank (tree e, long rank)
204 void **slot;
205 gcc_assert (rank > 0);
206 slot = pointer_map_insert (operand_rank, e);
207 gcc_assert (!*slot);
208 *slot = (void *) rank;
211 /* Given an expression E, return the rank of the expression. */
213 static long
214 get_rank (tree e)
216 /* Constants have rank 0. */
217 if (is_gimple_min_invariant (e))
218 return 0;
220 /* SSA_NAME's have the rank of the expression they are the result
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. */
231 if (TREE_CODE (e) == SSA_NAME)
233 tree stmt;
234 tree rhs;
235 long rank, maxrank;
236 int i;
237 int n;
239 if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
240 && SSA_NAME_IS_DEFAULT_DEF (e))
241 return find_operand_rank (e);
243 stmt = SSA_NAME_DEF_STMT (e);
244 if (bb_for_stmt (stmt) == NULL)
245 return 0;
247 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
248 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
249 return bb_rank[bb_for_stmt (stmt)->index];
251 /* If we already have a rank for this expression, use that. */
252 rank = find_operand_rank (e);
253 if (rank != -1)
254 return rank;
256 /* Otherwise, find the maximum rank for the operands, or the bb
257 rank, whichever is less. */
258 rank = 0;
259 maxrank = bb_rank[bb_for_stmt(stmt)->index];
260 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
261 n = TREE_OPERAND_LENGTH (rhs);
262 if (n == 0)
263 rank = MAX (rank, get_rank (rhs));
264 else
266 for (i = 0;
267 i < n
268 && TREE_OPERAND (rhs, i)
269 && rank != maxrank;
270 i++)
271 rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
274 if (dump_file && (dump_flags & TDF_DETAILS))
276 fprintf (dump_file, "Rank for ");
277 print_generic_expr (dump_file, e, 0);
278 fprintf (dump_file, " is %ld\n", (rank + 1));
281 /* Note the rank in the hashtable so we don't recompute it. */
282 insert_operand_rank (e, (rank + 1));
283 return (rank + 1);
286 /* Globals, etc, are rank 0 */
287 return 0;
290 DEF_VEC_P(operand_entry_t);
291 DEF_VEC_ALLOC_P(operand_entry_t, heap);
293 /* We want integer ones to end up last no matter what, since they are
294 the ones we can do the most with. */
295 #define INTEGER_CONST_TYPE 1 << 3
296 #define FLOAT_CONST_TYPE 1 << 2
297 #define OTHER_CONST_TYPE 1 << 1
299 /* Classify an invariant tree into integer, float, or other, so that
300 we can sort them to be near other constants of the same type. */
301 static inline int
302 constant_type (tree t)
304 if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
305 return INTEGER_CONST_TYPE;
306 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
307 return FLOAT_CONST_TYPE;
308 else
309 return OTHER_CONST_TYPE;
312 /* qsort comparison function to sort operand entries PA and PB by rank
313 so that the sorted array is ordered by rank in decreasing order. */
314 static int
315 sort_by_operand_rank (const void *pa, const void *pb)
317 const operand_entry_t oea = *(const operand_entry_t *)pa;
318 const operand_entry_t oeb = *(const operand_entry_t *)pb;
320 /* It's nicer for optimize_expression if constants that are likely
321 to fold when added/multiplied//whatever are put next to each
322 other. Since all constants have rank 0, order them by type. */
323 if (oeb->rank == 0 && oea->rank == 0)
324 return constant_type (oeb->op) - constant_type (oea->op);
326 /* Lastly, make sure the versions that are the same go next to each
327 other. We use SSA_NAME_VERSION because it's stable. */
328 if ((oeb->rank - oea->rank == 0)
329 && TREE_CODE (oea->op) == SSA_NAME
330 && TREE_CODE (oeb->op) == SSA_NAME)
331 return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
333 return oeb->rank - oea->rank;
336 /* Add an operand entry to *OPS for the tree operand OP. */
338 static void
339 add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
341 operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
343 oe->op = op;
344 oe->rank = get_rank (op);
345 VEC_safe_push (operand_entry_t, heap, *ops, oe);
348 /* Return true if STMT is reassociable operation containing a binary
349 operation with tree code CODE, and is inside LOOP. */
351 static bool
352 is_reassociable_op (tree stmt, enum tree_code code, struct loop *loop)
354 basic_block bb;
356 if (IS_EMPTY_STMT (stmt))
357 return false;
359 bb = bb_for_stmt (stmt);
360 if (!flow_bb_inside_loop_p (loop, bb))
361 return false;
363 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
364 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == code
365 && has_single_use (GIMPLE_STMT_OPERAND (stmt, 0)))
366 return true;
367 return false;
371 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
372 operand of the negate operation. Otherwise, return NULL. */
374 static tree
375 get_unary_op (tree name, enum tree_code opcode)
377 tree stmt = SSA_NAME_DEF_STMT (name);
378 tree rhs;
380 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
381 return NULL_TREE;
383 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
384 if (TREE_CODE (rhs) == opcode)
385 return TREE_OPERAND (rhs, 0);
386 return NULL_TREE;
389 /* If CURR and LAST are a pair of ops that OPCODE allows us to
390 eliminate through equivalences, do so, remove them from OPS, and
391 return true. Otherwise, return false. */
393 static bool
394 eliminate_duplicate_pair (enum tree_code opcode,
395 VEC (operand_entry_t, heap) **ops,
396 bool *all_done,
397 unsigned int i,
398 operand_entry_t curr,
399 operand_entry_t last)
402 /* If we have two of the same op, and the opcode is & |, min, or max,
403 we can eliminate one of them.
404 If we have two of the same op, and the opcode is ^, we can
405 eliminate both of them. */
407 if (last && last->op == curr->op)
409 switch (opcode)
411 case MAX_EXPR:
412 case MIN_EXPR:
413 case BIT_IOR_EXPR:
414 case BIT_AND_EXPR:
415 if (dump_file && (dump_flags & TDF_DETAILS))
417 fprintf (dump_file, "Equivalence: ");
418 print_generic_expr (dump_file, curr->op, 0);
419 fprintf (dump_file, " [&|minmax] ");
420 print_generic_expr (dump_file, last->op, 0);
421 fprintf (dump_file, " -> ");
422 print_generic_stmt (dump_file, last->op, 0);
425 VEC_ordered_remove (operand_entry_t, *ops, i);
426 reassociate_stats.ops_eliminated ++;
428 return true;
430 case BIT_XOR_EXPR:
431 if (dump_file && (dump_flags & TDF_DETAILS))
433 fprintf (dump_file, "Equivalence: ");
434 print_generic_expr (dump_file, curr->op, 0);
435 fprintf (dump_file, " ^ ");
436 print_generic_expr (dump_file, last->op, 0);
437 fprintf (dump_file, " -> nothing\n");
440 reassociate_stats.ops_eliminated += 2;
442 if (VEC_length (operand_entry_t, *ops) == 2)
444 VEC_free (operand_entry_t, heap, *ops);
445 *ops = NULL;
446 add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
447 integer_zero_node));
448 *all_done = true;
450 else
452 VEC_ordered_remove (operand_entry_t, *ops, i-1);
453 VEC_ordered_remove (operand_entry_t, *ops, i-1);
456 return true;
458 default:
459 break;
462 return false;
465 /* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
466 look in OPS for a corresponding positive operation to cancel it
467 out. If we find one, remove the other from OPS, replace
468 OPS[CURRINDEX] with 0, and return true. Otherwise, return
469 false. */
471 static bool
472 eliminate_plus_minus_pair (enum tree_code opcode,
473 VEC (operand_entry_t, heap) **ops,
474 unsigned int currindex,
475 operand_entry_t curr)
477 tree negateop;
478 unsigned int i;
479 operand_entry_t oe;
481 if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
482 return false;
484 negateop = get_unary_op (curr->op, NEGATE_EXPR);
485 if (negateop == NULL_TREE)
486 return false;
488 /* Any non-negated version will have a rank that is one less than
489 the current rank. So once we hit those ranks, if we don't find
490 one, we can stop. */
492 for (i = currindex + 1;
493 VEC_iterate (operand_entry_t, *ops, i, oe)
494 && oe->rank >= curr->rank - 1 ;
495 i++)
497 if (oe->op == negateop)
500 if (dump_file && (dump_flags & TDF_DETAILS))
502 fprintf (dump_file, "Equivalence: ");
503 print_generic_expr (dump_file, negateop, 0);
504 fprintf (dump_file, " + -");
505 print_generic_expr (dump_file, oe->op, 0);
506 fprintf (dump_file, " -> 0\n");
509 VEC_ordered_remove (operand_entry_t, *ops, i);
510 add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
511 integer_zero_node));
512 VEC_ordered_remove (operand_entry_t, *ops, currindex);
513 reassociate_stats.ops_eliminated ++;
515 return true;
519 return false;
522 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
523 bitwise not expression, look in OPS for a corresponding operand to
524 cancel it out. If we find one, remove the other from OPS, replace
525 OPS[CURRINDEX] with 0, and return true. Otherwise, return
526 false. */
528 static bool
529 eliminate_not_pairs (enum tree_code opcode,
530 VEC (operand_entry_t, heap) **ops,
531 unsigned int currindex,
532 operand_entry_t curr)
534 tree notop;
535 unsigned int i;
536 operand_entry_t oe;
538 if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
539 || TREE_CODE (curr->op) != SSA_NAME)
540 return false;
542 notop = get_unary_op (curr->op, BIT_NOT_EXPR);
543 if (notop == NULL_TREE)
544 return false;
546 /* Any non-not version will have a rank that is one less than
547 the current rank. So once we hit those ranks, if we don't find
548 one, we can stop. */
550 for (i = currindex + 1;
551 VEC_iterate (operand_entry_t, *ops, i, oe)
552 && oe->rank >= curr->rank - 1;
553 i++)
555 if (oe->op == notop)
557 if (dump_file && (dump_flags & TDF_DETAILS))
559 fprintf (dump_file, "Equivalence: ");
560 print_generic_expr (dump_file, notop, 0);
561 if (opcode == BIT_AND_EXPR)
562 fprintf (dump_file, " & ~");
563 else if (opcode == BIT_IOR_EXPR)
564 fprintf (dump_file, " | ~");
565 print_generic_expr (dump_file, oe->op, 0);
566 if (opcode == BIT_AND_EXPR)
567 fprintf (dump_file, " -> 0\n");
568 else if (opcode == BIT_IOR_EXPR)
569 fprintf (dump_file, " -> -1\n");
572 if (opcode == BIT_AND_EXPR)
573 oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
574 else if (opcode == BIT_IOR_EXPR)
575 oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
576 TYPE_PRECISION (TREE_TYPE (oe->op)));
578 reassociate_stats.ops_eliminated
579 += VEC_length (operand_entry_t, *ops) - 1;
580 VEC_free (operand_entry_t, heap, *ops);
581 *ops = NULL;
582 VEC_safe_push (operand_entry_t, heap, *ops, oe);
583 return true;
587 return false;
590 /* Use constant value that may be present in OPS to try to eliminate
591 operands. Note that this function is only really used when we've
592 eliminated ops for other reasons, or merged constants. Across
593 single statements, fold already does all of this, plus more. There
594 is little point in duplicating logic, so I've only included the
595 identities that I could ever construct testcases to trigger. */
597 static void
598 eliminate_using_constants (enum tree_code opcode,
599 VEC(operand_entry_t, heap) **ops)
601 operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
602 tree type = TREE_TYPE (oelast->op);
604 if (oelast->rank == 0
605 && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type)))
607 switch (opcode)
609 case BIT_AND_EXPR:
610 if (integer_zerop (oelast->op))
612 if (VEC_length (operand_entry_t, *ops) != 1)
614 if (dump_file && (dump_flags & TDF_DETAILS))
615 fprintf (dump_file, "Found & 0, removing all other ops\n");
617 reassociate_stats.ops_eliminated
618 += VEC_length (operand_entry_t, *ops) - 1;
620 VEC_free (operand_entry_t, heap, *ops);
621 *ops = NULL;
622 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
623 return;
626 else if (integer_all_onesp (oelast->op))
628 if (VEC_length (operand_entry_t, *ops) != 1)
630 if (dump_file && (dump_flags & TDF_DETAILS))
631 fprintf (dump_file, "Found & -1, removing\n");
632 VEC_pop (operand_entry_t, *ops);
633 reassociate_stats.ops_eliminated++;
636 break;
637 case BIT_IOR_EXPR:
638 if (integer_all_onesp (oelast->op))
640 if (VEC_length (operand_entry_t, *ops) != 1)
642 if (dump_file && (dump_flags & TDF_DETAILS))
643 fprintf (dump_file, "Found | -1, removing all other ops\n");
645 reassociate_stats.ops_eliminated
646 += VEC_length (operand_entry_t, *ops) - 1;
648 VEC_free (operand_entry_t, heap, *ops);
649 *ops = NULL;
650 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
651 return;
654 else if (integer_zerop (oelast->op))
656 if (VEC_length (operand_entry_t, *ops) != 1)
658 if (dump_file && (dump_flags & TDF_DETAILS))
659 fprintf (dump_file, "Found | 0, removing\n");
660 VEC_pop (operand_entry_t, *ops);
661 reassociate_stats.ops_eliminated++;
664 break;
665 case MULT_EXPR:
666 if (integer_zerop (oelast->op)
667 || (FLOAT_TYPE_P (type)
668 && !HONOR_NANS (TYPE_MODE (type))
669 && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
670 && real_zerop (oelast->op)))
672 if (VEC_length (operand_entry_t, *ops) != 1)
674 if (dump_file && (dump_flags & TDF_DETAILS))
675 fprintf (dump_file, "Found * 0, removing all other ops\n");
677 reassociate_stats.ops_eliminated
678 += VEC_length (operand_entry_t, *ops) - 1;
679 VEC_free (operand_entry_t, heap, *ops);
680 *ops = NULL;
681 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
682 return;
685 else if (integer_onep (oelast->op)
686 || (FLOAT_TYPE_P (type)
687 && !HONOR_SNANS (TYPE_MODE (type))
688 && real_onep (oelast->op)))
690 if (VEC_length (operand_entry_t, *ops) != 1)
692 if (dump_file && (dump_flags & TDF_DETAILS))
693 fprintf (dump_file, "Found * 1, removing\n");
694 VEC_pop (operand_entry_t, *ops);
695 reassociate_stats.ops_eliminated++;
696 return;
699 break;
700 case BIT_XOR_EXPR:
701 case PLUS_EXPR:
702 case MINUS_EXPR:
703 if (integer_zerop (oelast->op)
704 || (FLOAT_TYPE_P (type)
705 && (opcode == PLUS_EXPR || opcode == MINUS_EXPR)
706 && fold_real_zero_addition_p (type, oelast->op,
707 opcode == MINUS_EXPR)))
709 if (VEC_length (operand_entry_t, *ops) != 1)
711 if (dump_file && (dump_flags & TDF_DETAILS))
712 fprintf (dump_file, "Found [|^+] 0, removing\n");
713 VEC_pop (operand_entry_t, *ops);
714 reassociate_stats.ops_eliminated++;
715 return;
718 break;
719 default:
720 break;
725 /* Perform various identities and other optimizations on the list of
726 operand entries, stored in OPS. The tree code for the binary
727 operation between all the operands is OPCODE. */
729 static void
730 optimize_ops_list (enum tree_code opcode,
731 VEC (operand_entry_t, heap) **ops)
733 unsigned int length = VEC_length (operand_entry_t, *ops);
734 unsigned int i;
735 operand_entry_t oe;
736 operand_entry_t oelast = NULL;
737 bool iterate = false;
739 if (length == 1)
740 return;
742 oelast = VEC_last (operand_entry_t, *ops);
744 /* If the last two are constants, pop the constants off, merge them
745 and try the next two. */
746 if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
748 operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
750 if (oelm1->rank == 0
751 && is_gimple_min_invariant (oelm1->op)
752 && useless_type_conversion_p (TREE_TYPE (oelm1->op),
753 TREE_TYPE (oelast->op)))
755 tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
756 oelm1->op, oelast->op);
758 if (folded && is_gimple_min_invariant (folded))
760 if (dump_file && (dump_flags & TDF_DETAILS))
761 fprintf (dump_file, "Merging constants\n");
763 VEC_pop (operand_entry_t, *ops);
764 VEC_pop (operand_entry_t, *ops);
766 add_to_ops_vec (ops, folded);
767 reassociate_stats.constants_eliminated++;
769 optimize_ops_list (opcode, ops);
770 return;
775 eliminate_using_constants (opcode, ops);
776 oelast = NULL;
778 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
780 bool done = false;
782 if (eliminate_not_pairs (opcode, ops, i, oe))
783 return;
784 if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
785 || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
787 if (done)
788 return;
789 iterate = true;
790 oelast = NULL;
791 continue;
793 oelast = oe;
794 i++;
797 length = VEC_length (operand_entry_t, *ops);
798 oelast = VEC_last (operand_entry_t, *ops);
800 if (iterate)
801 optimize_ops_list (opcode, ops);
804 /* Return true if OPERAND is defined by a PHI node which uses the LHS
805 of STMT in it's operands. This is also known as a "destructive
806 update" operation. */
808 static bool
809 is_phi_for_stmt (tree stmt, tree operand)
811 tree def_stmt;
812 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
813 use_operand_p arg_p;
814 ssa_op_iter i;
816 if (TREE_CODE (operand) != SSA_NAME)
817 return false;
819 def_stmt = SSA_NAME_DEF_STMT (operand);
820 if (TREE_CODE (def_stmt) != PHI_NODE)
821 return false;
823 FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
824 if (lhs == USE_FROM_PTR (arg_p))
825 return true;
826 return false;
829 /* Recursively rewrite our linearized statements so that the operators
830 match those in OPS[OPINDEX], putting the computation in rank
831 order. */
833 static void
834 rewrite_expr_tree (tree stmt, unsigned int opindex,
835 VEC(operand_entry_t, heap) * ops)
837 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
838 operand_entry_t oe;
840 /* If we have three operands left, then we want to make sure the one
841 that gets the double binary op are the ones with the same rank.
843 The alternative we try is to see if this is a destructive
844 update style statement, which is like:
845 b = phi (a, ...)
846 a = c + b;
847 In that case, we want to use the destructive update form to
848 expose the possible vectorizer sum reduction opportunity.
849 In that case, the third operand will be the phi node.
851 We could, of course, try to be better as noted above, and do a
852 lot of work to try to find these opportunities in >3 operand
853 cases, but it is unlikely to be worth it. */
854 if (opindex + 3 == VEC_length (operand_entry_t, ops))
856 operand_entry_t oe1, oe2, oe3;
858 oe1 = VEC_index (operand_entry_t, ops, opindex);
859 oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
860 oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
862 if ((oe1->rank == oe2->rank
863 && oe2->rank != oe3->rank)
864 || (is_phi_for_stmt (stmt, oe3->op)
865 && !is_phi_for_stmt (stmt, oe1->op)
866 && !is_phi_for_stmt (stmt, oe2->op)))
868 struct operand_entry temp = *oe3;
869 oe3->op = oe1->op;
870 oe3->rank = oe1->rank;
871 oe1->op = temp.op;
872 oe1->rank= temp.rank;
874 else if ((oe1->rank == oe3->rank
875 && oe2->rank != oe3->rank)
876 || (is_phi_for_stmt (stmt, oe2->op)
877 && !is_phi_for_stmt (stmt, oe1->op)
878 && !is_phi_for_stmt (stmt, oe3->op)))
880 struct operand_entry temp = *oe2;
881 oe2->op = oe1->op;
882 oe2->rank = oe1->rank;
883 oe1->op = temp.op;
884 oe1->rank= temp.rank;
888 /* The final recursion case for this function is that you have
889 exactly two operations left.
890 If we had one exactly one op in the entire list to start with, we
891 would have never called this function, and the tail recursion
892 rewrites them one at a time. */
893 if (opindex + 2 == VEC_length (operand_entry_t, ops))
895 operand_entry_t oe1, oe2;
897 oe1 = VEC_index (operand_entry_t, ops, opindex);
898 oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
900 if (TREE_OPERAND (rhs, 0) != oe1->op
901 || TREE_OPERAND (rhs, 1) != oe2->op)
904 if (dump_file && (dump_flags & TDF_DETAILS))
906 fprintf (dump_file, "Transforming ");
907 print_generic_expr (dump_file, rhs, 0);
910 TREE_OPERAND (rhs, 0) = oe1->op;
911 TREE_OPERAND (rhs, 1) = oe2->op;
912 update_stmt (stmt);
914 if (dump_file && (dump_flags & TDF_DETAILS))
916 fprintf (dump_file, " into ");
917 print_generic_stmt (dump_file, rhs, 0);
921 return;
924 /* If we hit here, we should have 3 or more ops left. */
925 gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
927 /* Rewrite the next operator. */
928 oe = VEC_index (operand_entry_t, ops, opindex);
930 if (oe->op != TREE_OPERAND (rhs, 1))
933 if (dump_file && (dump_flags & TDF_DETAILS))
935 fprintf (dump_file, "Transforming ");
936 print_generic_expr (dump_file, rhs, 0);
939 TREE_OPERAND (rhs, 1) = oe->op;
940 update_stmt (stmt);
942 if (dump_file && (dump_flags & TDF_DETAILS))
944 fprintf (dump_file, " into ");
945 print_generic_stmt (dump_file, rhs, 0);
948 /* Recurse on the LHS of the binary operator, which is guaranteed to
949 be the non-leaf side. */
950 rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0)),
951 opindex + 1, ops);
954 /* Transform STMT, which is really (A +B) + (C + D) into the left
955 linear form, ((A+B)+C)+D.
956 Recurse on D if necessary. */
958 static void
959 linearize_expr (tree stmt)
961 block_stmt_iterator bsinow, bsirhs;
962 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
963 enum tree_code rhscode = TREE_CODE (rhs);
964 tree binrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
965 tree binlhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
966 tree newbinrhs = NULL_TREE;
967 struct loop *loop = loop_containing_stmt (stmt);
969 gcc_assert (is_reassociable_op (binlhs, TREE_CODE (rhs), loop)
970 && is_reassociable_op (binrhs, TREE_CODE (rhs), loop));
972 bsinow = bsi_for_stmt (stmt);
973 bsirhs = bsi_for_stmt (binrhs);
974 bsi_move_before (&bsirhs, &bsinow);
976 TREE_OPERAND (rhs, 1) = TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs, 1), 0);
977 if (TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME)
978 newbinrhs = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
979 TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs, 1), 0)
980 = GIMPLE_STMT_OPERAND (binlhs, 0);
981 TREE_OPERAND (rhs, 0) = GIMPLE_STMT_OPERAND (binrhs, 0);
983 if (dump_file && (dump_flags & TDF_DETAILS))
985 fprintf (dump_file, "Linearized: ");
986 print_generic_stmt (dump_file, rhs, 0);
989 reassociate_stats.linearized++;
990 update_stmt (binrhs);
991 update_stmt (binlhs);
992 update_stmt (stmt);
993 TREE_VISITED (binrhs) = 1;
994 TREE_VISITED (binlhs) = 1;
995 TREE_VISITED (stmt) = 1;
997 /* Tail recurse on the new rhs if it still needs reassociation. */
998 if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
999 linearize_expr (stmt);
1002 /* If LHS has a single immediate use that is a GIMPLE_MODIFY_STMT, return
1003 it. Otherwise, return NULL. */
1005 static tree
1006 get_single_immediate_use (tree lhs)
1008 use_operand_p immuse;
1009 tree immusestmt;
1011 if (TREE_CODE (lhs) == SSA_NAME
1012 && single_imm_use (lhs, &immuse, &immusestmt))
1014 if (TREE_CODE (immusestmt) == RETURN_EXPR)
1015 immusestmt = TREE_OPERAND (immusestmt, 0);
1016 if (TREE_CODE (immusestmt) == GIMPLE_MODIFY_STMT)
1017 return immusestmt;
1019 return NULL_TREE;
1021 static VEC(tree, heap) *broken_up_subtracts;
1024 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
1025 representing the negated value. Insertions of any necessary
1026 instructions go before BSI.
1027 This function is recursive in that, if you hand it "a_5" as the
1028 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1029 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */
1031 static tree
1032 negate_value (tree tonegate, block_stmt_iterator *bsi)
1034 tree negatedef = tonegate;
1035 tree resultofnegate;
1037 if (TREE_CODE (tonegate) == SSA_NAME)
1038 negatedef = SSA_NAME_DEF_STMT (tonegate);
1040 /* If we are trying to negate a name, defined by an add, negate the
1041 add operands instead. */
1042 if (TREE_CODE (tonegate) == SSA_NAME
1043 && TREE_CODE (negatedef) == GIMPLE_MODIFY_STMT
1044 && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef, 0)) == SSA_NAME
1045 && has_single_use (GIMPLE_STMT_OPERAND (negatedef, 0))
1046 && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef, 1)) == PLUS_EXPR)
1048 block_stmt_iterator bsi;
1049 tree binop = GIMPLE_STMT_OPERAND (negatedef, 1);
1051 bsi = bsi_for_stmt (negatedef);
1052 TREE_OPERAND (binop, 0) = negate_value (TREE_OPERAND (binop, 0),
1053 &bsi);
1054 bsi = bsi_for_stmt (negatedef);
1055 TREE_OPERAND (binop, 1) = negate_value (TREE_OPERAND (binop, 1),
1056 &bsi);
1057 update_stmt (negatedef);
1058 return GIMPLE_STMT_OPERAND (negatedef, 0);
1061 tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
1062 resultofnegate = force_gimple_operand_bsi (bsi, tonegate, true,
1063 NULL_TREE, true, BSI_SAME_STMT);
1064 VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
1065 return resultofnegate;
1069 /* Return true if we should break up the subtract in STMT into an add
1070 with negate. This is true when we the subtract operands are really
1071 adds, or the subtract itself is used in an add expression. In
1072 either case, breaking up the subtract into an add with negate
1073 exposes the adds to reassociation. */
1075 static bool
1076 should_break_up_subtract (tree stmt)
1079 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1080 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1081 tree binlhs = TREE_OPERAND (rhs, 0);
1082 tree binrhs = TREE_OPERAND (rhs, 1);
1083 tree immusestmt;
1084 struct loop *loop = loop_containing_stmt (stmt);
1086 if (TREE_CODE (binlhs) == SSA_NAME
1087 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
1088 return true;
1090 if (TREE_CODE (binrhs) == SSA_NAME
1091 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
1092 return true;
1094 if (TREE_CODE (lhs) == SSA_NAME
1095 && (immusestmt = get_single_immediate_use (lhs))
1096 && TREE_CODE (GIMPLE_STMT_OPERAND (immusestmt, 1)) == PLUS_EXPR)
1097 return true;
1098 return false;
1102 /* Transform STMT from A - B into A + -B. */
1104 static void
1105 break_up_subtract (tree stmt, block_stmt_iterator *bsi)
1107 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1109 if (dump_file && (dump_flags & TDF_DETAILS))
1111 fprintf (dump_file, "Breaking up subtract ");
1112 print_generic_stmt (dump_file, stmt, 0);
1115 TREE_SET_CODE (GIMPLE_STMT_OPERAND (stmt, 1), PLUS_EXPR);
1116 TREE_OPERAND (rhs, 1) = negate_value (TREE_OPERAND (rhs, 1), bsi);
1118 update_stmt (stmt);
1121 /* Recursively linearize a binary expression that is the RHS of STMT.
1122 Place the operands of the expression tree in the vector named OPS. */
1124 static void
1125 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, tree stmt)
1127 block_stmt_iterator bsinow, bsilhs;
1128 tree rhs = GENERIC_TREE_OPERAND (stmt, 1);
1129 tree binrhs = TREE_OPERAND (rhs, 1);
1130 tree binlhs = TREE_OPERAND (rhs, 0);
1131 tree binlhsdef, binrhsdef;
1132 bool binlhsisreassoc = false;
1133 bool binrhsisreassoc = false;
1134 enum tree_code rhscode = TREE_CODE (rhs);
1135 struct loop *loop = loop_containing_stmt (stmt);
1137 TREE_VISITED (stmt) = 1;
1139 if (TREE_CODE (binlhs) == SSA_NAME)
1141 binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1142 binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
1145 if (TREE_CODE (binrhs) == SSA_NAME)
1147 binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1148 binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
1151 /* If the LHS is not reassociable, but the RHS is, we need to swap
1152 them. If neither is reassociable, there is nothing we can do, so
1153 just put them in the ops vector. If the LHS is reassociable,
1154 linearize it. If both are reassociable, then linearize the RHS
1155 and the LHS. */
1157 if (!binlhsisreassoc)
1159 tree temp;
1161 if (!binrhsisreassoc)
1163 add_to_ops_vec (ops, binrhs);
1164 add_to_ops_vec (ops, binlhs);
1165 return;
1168 if (dump_file && (dump_flags & TDF_DETAILS))
1170 fprintf (dump_file, "swapping operands of ");
1171 print_generic_expr (dump_file, stmt, 0);
1174 swap_tree_operands (stmt, &TREE_OPERAND (rhs, 0),
1175 &TREE_OPERAND (rhs, 1));
1176 update_stmt (stmt);
1178 if (dump_file && (dump_flags & TDF_DETAILS))
1180 fprintf (dump_file, " is now ");
1181 print_generic_stmt (dump_file, stmt, 0);
1184 /* We want to make it so the lhs is always the reassociative op,
1185 so swap. */
1186 temp = binlhs;
1187 binlhs = binrhs;
1188 binrhs = temp;
1190 else if (binrhsisreassoc)
1192 linearize_expr (stmt);
1193 gcc_assert (rhs == GIMPLE_STMT_OPERAND (stmt, 1));
1194 binlhs = TREE_OPERAND (rhs, 0);
1195 binrhs = TREE_OPERAND (rhs, 1);
1198 gcc_assert (TREE_CODE (binrhs) != SSA_NAME
1199 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
1200 rhscode, loop));
1201 bsinow = bsi_for_stmt (stmt);
1202 bsilhs = bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs));
1203 bsi_move_before (&bsilhs, &bsinow);
1204 linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs));
1205 add_to_ops_vec (ops, binrhs);
1208 /* Repropagate the negates back into subtracts, since no other pass
1209 currently does it. */
1211 static void
1212 repropagate_negates (void)
1214 unsigned int i = 0;
1215 tree negate;
1217 for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
1219 tree user = get_single_immediate_use (negate);
1221 /* The negate operand can be either operand of a PLUS_EXPR
1222 (it can be the LHS if the RHS is a constant for example).
1224 Force the negate operand to the RHS of the PLUS_EXPR, then
1225 transform the PLUS_EXPR into a MINUS_EXPR. */
1226 if (user
1227 && TREE_CODE (user) == GIMPLE_MODIFY_STMT
1228 && TREE_CODE (GIMPLE_STMT_OPERAND (user, 1)) == PLUS_EXPR)
1230 tree rhs = GIMPLE_STMT_OPERAND (user, 1);
1232 /* If the negated operand appears on the LHS of the
1233 PLUS_EXPR, exchange the operands of the PLUS_EXPR
1234 to force the negated operand to the RHS of the PLUS_EXPR. */
1235 if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user, 1), 0) == negate)
1237 tree temp = TREE_OPERAND (rhs, 0);
1238 TREE_OPERAND (rhs, 0) = TREE_OPERAND (rhs, 1);
1239 TREE_OPERAND (rhs, 1) = temp;
1242 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1243 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */
1244 if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user, 1), 1) == negate)
1246 TREE_SET_CODE (rhs, MINUS_EXPR);
1247 TREE_OPERAND (rhs, 1) = get_unary_op (negate, NEGATE_EXPR);
1248 update_stmt (user);
1254 /* Break up subtract operations in block BB.
1256 We do this top down because we don't know whether the subtract is
1257 part of a possible chain of reassociation except at the top.
1259 IE given
1260 d = f + g
1261 c = a + e
1262 b = c - d
1263 q = b - r
1264 k = t - q
1266 we want to break up k = t - q, but we won't until we've transformed q
1267 = b - r, which won't be broken up until we transform b = c - d. */
1269 static void
1270 break_up_subtract_bb (basic_block bb)
1272 block_stmt_iterator bsi;
1273 basic_block son;
1275 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1277 tree stmt = bsi_stmt (bsi);
1279 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1281 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1282 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1284 TREE_VISITED (stmt) = 0;
1285 /* If associative-math we can do reassociation for
1286 non-integral types. Or, we can do reassociation for
1287 non-saturating fixed-point types. */
1288 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1289 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1290 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
1291 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
1292 || !flag_associative_math)
1293 && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs))
1294 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs))))
1295 continue;
1297 /* Check for a subtract used only in an addition. If this
1298 is the case, transform it into add of a negate for better
1299 reassociation. IE transform C = A-B into C = A + -B if C
1300 is only used in an addition. */
1301 if (TREE_CODE (rhs) == MINUS_EXPR)
1302 if (should_break_up_subtract (stmt))
1303 break_up_subtract (stmt, &bsi);
1306 for (son = first_dom_son (CDI_DOMINATORS, bb);
1307 son;
1308 son = next_dom_son (CDI_DOMINATORS, son))
1309 break_up_subtract_bb (son);
1312 /* Reassociate expressions in basic block BB and its post-dominator as
1313 children. */
1315 static void
1316 reassociate_bb (basic_block bb)
1318 block_stmt_iterator bsi;
1319 basic_block son;
1321 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
1323 tree stmt = bsi_stmt (bsi);
1325 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1327 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1328 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1330 /* If this was part of an already processed tree, we don't
1331 need to touch it again. */
1332 if (TREE_VISITED (stmt))
1333 continue;
1335 /* If associative-math we can do reassociation for
1336 non-integral types. Or, we can do reassociation for
1337 non-saturating fixed-point types. */
1338 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1339 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
1340 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
1341 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
1342 || !flag_associative_math)
1343 && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs))
1344 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs))))
1345 continue;
1347 if (associative_tree_code (TREE_CODE (rhs)))
1349 VEC(operand_entry_t, heap) *ops = NULL;
1351 /* There may be no immediate uses left by the time we
1352 get here because we may have eliminated them all. */
1353 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
1354 continue;
1356 TREE_VISITED (stmt) = 1;
1357 linearize_expr_tree (&ops, stmt);
1358 qsort (VEC_address (operand_entry_t, ops),
1359 VEC_length (operand_entry_t, ops),
1360 sizeof (operand_entry_t),
1361 sort_by_operand_rank);
1362 optimize_ops_list (TREE_CODE (rhs), &ops);
1364 if (VEC_length (operand_entry_t, ops) == 1)
1366 if (dump_file && (dump_flags & TDF_DETAILS))
1368 fprintf (dump_file, "Transforming ");
1369 print_generic_expr (dump_file, rhs, 0);
1371 GIMPLE_STMT_OPERAND (stmt, 1)
1372 = VEC_last (operand_entry_t, ops)->op;
1373 update_stmt (stmt);
1375 if (dump_file && (dump_flags & TDF_DETAILS))
1377 fprintf (dump_file, " into ");
1378 print_generic_stmt (dump_file,
1379 GIMPLE_STMT_OPERAND (stmt, 1), 0);
1382 else
1384 rewrite_expr_tree (stmt, 0, ops);
1387 VEC_free (operand_entry_t, heap, ops);
1391 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
1392 son;
1393 son = next_dom_son (CDI_POST_DOMINATORS, son))
1394 reassociate_bb (son);
1397 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
1398 void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
1400 /* Dump the operand entry vector OPS to FILE. */
1402 void
1403 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
1405 operand_entry_t oe;
1406 unsigned int i;
1408 for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
1410 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
1411 print_generic_stmt (file, oe->op, 0);
1415 /* Dump the operand entry vector OPS to STDERR. */
1417 void
1418 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
1420 dump_ops_vector (stderr, ops);
1423 static void
1424 do_reassoc (void)
1426 break_up_subtract_bb (ENTRY_BLOCK_PTR);
1427 reassociate_bb (EXIT_BLOCK_PTR);
1430 /* Initialize the reassociation pass. */
1432 static void
1433 init_reassoc (void)
1435 int i;
1436 long rank = 2;
1437 tree param;
1438 int *bbs = XNEWVEC (int, last_basic_block + 1);
1440 /* Find the loops, so that we can prevent moving calculations in
1441 them. */
1442 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1444 memset (&reassociate_stats, 0, sizeof (reassociate_stats));
1446 operand_entry_pool = create_alloc_pool ("operand entry pool",
1447 sizeof (struct operand_entry), 30);
1449 /* Reverse RPO (Reverse Post Order) will give us something where
1450 deeper loops come later. */
1451 pre_and_rev_post_order_compute (NULL, bbs, false);
1452 bb_rank = XCNEWVEC (long, last_basic_block + 1);
1453 operand_rank = pointer_map_create ();
1455 /* Give each argument a distinct rank. */
1456 for (param = DECL_ARGUMENTS (current_function_decl);
1457 param;
1458 param = TREE_CHAIN (param))
1460 if (gimple_default_def (cfun, param) != NULL)
1462 tree def = gimple_default_def (cfun, param);
1463 insert_operand_rank (def, ++rank);
1467 /* Give the chain decl a distinct rank. */
1468 if (cfun->static_chain_decl != NULL)
1470 tree def = gimple_default_def (cfun, cfun->static_chain_decl);
1471 if (def != NULL)
1472 insert_operand_rank (def, ++rank);
1475 /* Set up rank for each BB */
1476 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
1477 bb_rank[bbs[i]] = ++rank << 16;
1479 free (bbs);
1480 calculate_dominance_info (CDI_POST_DOMINATORS);
1481 broken_up_subtracts = NULL;
1484 /* Cleanup after the reassociation pass, and print stats if
1485 requested. */
1487 static void
1488 fini_reassoc (void)
1490 if (dump_file && (dump_flags & TDF_STATS))
1492 fprintf (dump_file, "Reassociation stats:\n");
1493 fprintf (dump_file, "Linearized: %d\n",
1494 reassociate_stats.linearized);
1495 fprintf (dump_file, "Constants eliminated: %d\n",
1496 reassociate_stats.constants_eliminated);
1497 fprintf (dump_file, "Ops eliminated: %d\n",
1498 reassociate_stats.ops_eliminated);
1499 fprintf (dump_file, "Statements rewritten: %d\n",
1500 reassociate_stats.rewritten);
1503 pointer_map_destroy (operand_rank);
1504 free_alloc_pool (operand_entry_pool);
1505 free (bb_rank);
1506 VEC_free (tree, heap, broken_up_subtracts);
1507 free_dominance_info (CDI_POST_DOMINATORS);
1508 loop_optimizer_finalize ();
1511 /* Gate and execute functions for Reassociation. */
1513 static unsigned int
1514 execute_reassoc (void)
1516 init_reassoc ();
1518 do_reassoc ();
1519 repropagate_negates ();
1521 fini_reassoc ();
1522 return 0;
1525 static bool
1526 gate_tree_ssa_reassoc (void)
1528 return flag_tree_reassoc != 0;
1531 struct gimple_opt_pass pass_reassoc =
1534 GIMPLE_PASS,
1535 "reassoc", /* name */
1536 gate_tree_ssa_reassoc, /* gate */
1537 execute_reassoc, /* execute */
1538 NULL, /* sub */
1539 NULL, /* next */
1540 0, /* static_pass_number */
1541 TV_TREE_REASSOC, /* tv_id */
1542 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
1543 0, /* properties_provided */
1544 0, /* properties_destroyed */
1545 0, /* todo_flags_start */
1546 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */