1 /* Reassociation for trees.
2 Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin <dan@dberlin.org>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-inline.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "tree-iterator.h"
36 #include "tree-pass.h"
37 #include "alloc-pool.h"
39 #include "langhooks.h"
40 #include "pointer-set.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 +
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
91 You want to first merge all leaves of the same rank, as much as
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
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.
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
145 newstmt = mergetmp + 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
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. */
166 int constants_eliminated;
171 /* Operator, rank pair. */
172 typedef struct operand_entry
179 static alloc_pool operand_entry_pool;
181 /* This is used to assign a unique ID to each struct operand_entry
182 so that qsort results are identical on different hosts. */
183 static int next_operand_entry_id;
185 /* Starting rank number for a given basic block, so that we can rank
186 operations using unmovable instructions in that BB based on the bb
188 static long *bb_rank;
190 /* Operand->rank hashtable. */
191 static struct pointer_map_t *operand_rank;
194 static long get_rank (tree);
197 /* Bias amount for loop-carried phis. We want this to be larger than
198 the depth of any reassociation tree we can see, but not larger than
199 the rank difference between two blocks. */
200 #define PHI_LOOP_BIAS (1 << 15)
202 /* Rank assigned to a phi statement. If STMT is a loop-carried phi of
203 an innermost loop, and the phi has only a single use which is inside
204 the loop, then the rank is the block rank of the loop latch plus an
205 extra bias for the loop-carried dependence. This causes expressions
206 calculated into an accumulator variable to be independent for each
207 iteration of the loop. If STMT is some other phi, the rank is the
208 block rank of its containing block. */
210 phi_rank (gimple stmt)
212 basic_block bb = gimple_bb (stmt);
213 struct loop *father = bb->loop_father;
219 /* We only care about real loops (those with a latch). */
221 return bb_rank[bb->index];
223 /* Interesting phis must be in headers of innermost loops. */
224 if (bb != father->header
226 return bb_rank[bb->index];
228 /* Ignore virtual SSA_NAMEs. */
229 res = gimple_phi_result (stmt);
230 if (!is_gimple_reg (SSA_NAME_VAR (res)))
231 return bb_rank[bb->index];
233 /* The phi definition must have a single use, and that use must be
234 within the loop. Otherwise this isn't an accumulator pattern. */
235 if (!single_imm_use (res, &use, &use_stmt)
236 || gimple_bb (use_stmt)->loop_father != father)
237 return bb_rank[bb->index];
239 /* Look for phi arguments from within the loop. If found, bias this phi. */
240 for (i = 0; i < gimple_phi_num_args (stmt); i++)
242 tree arg = gimple_phi_arg_def (stmt, i);
243 if (TREE_CODE (arg) == SSA_NAME
244 && !SSA_NAME_IS_DEFAULT_DEF (arg))
246 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
247 if (gimple_bb (def_stmt)->loop_father == father)
248 return bb_rank[father->latch->index] + PHI_LOOP_BIAS;
252 /* Must be an uninteresting phi. */
253 return bb_rank[bb->index];
256 /* If EXP is an SSA_NAME defined by a PHI statement that represents a
257 loop-carried dependence of an innermost loop, return TRUE; else
260 loop_carried_phi (tree exp)
265 if (TREE_CODE (exp) != SSA_NAME
266 || SSA_NAME_IS_DEFAULT_DEF (exp))
269 phi_stmt = SSA_NAME_DEF_STMT (exp);
271 if (gimple_code (SSA_NAME_DEF_STMT (exp)) != GIMPLE_PHI)
274 /* Non-loop-carried phis have block rank. Loop-carried phis have
275 an additional bias added in. If this phi doesn't have block rank,
276 it's biased and should not be propagated. */
277 block_rank = bb_rank[gimple_bb (phi_stmt)->index];
279 if (phi_rank (phi_stmt) != block_rank)
285 /* Return the maximum of RANK and the rank that should be propagated
286 from expression OP. For most operands, this is just the rank of OP.
287 For loop-carried phis, the value is zero to avoid undoing the bias
288 in favor of the phi. */
290 propagate_rank (long rank, tree op)
294 if (loop_carried_phi (op))
297 op_rank = get_rank (op);
299 return MAX (rank, op_rank);
302 /* Look up the operand rank structure for expression E. */
305 find_operand_rank (tree e)
307 void **slot = pointer_map_contains (operand_rank, e);
308 return slot ? (long) (intptr_t) *slot : -1;
311 /* Insert {E,RANK} into the operand rank hashtable. */
314 insert_operand_rank (tree e, long rank)
317 gcc_assert (rank > 0);
318 slot = pointer_map_insert (operand_rank, e);
320 *slot = (void *) (intptr_t) rank;
323 /* Given an expression E, return the rank of the expression. */
328 /* Constants have rank 0. */
329 if (is_gimple_min_invariant (e))
332 /* SSA_NAME's have the rank of the expression they are the result
334 For globals and uninitialized values, the rank is 0.
335 For function arguments, use the pre-setup rank.
336 For PHI nodes, stores, asm statements, etc, we use the rank of
338 For simple operations, the rank is the maximum rank of any of
339 its operands, or the bb_rank, whichever is less.
340 I make no claims that this is optimal, however, it gives good
343 /* We make an exception to the normal ranking system to break
344 dependences of accumulator variables in loops. Suppose we
345 have a simple one-block loop containing:
352 As shown, each iteration of the calculation into x is fully
353 dependent upon the iteration before it. We would prefer to
354 see this in the form:
361 If the loop is unrolled, the calculations of b and c from
362 different iterations can be interleaved.
364 To obtain this result during reassociation, we bias the rank
365 of the phi definition x_1 upward, when it is recognized as an
366 accumulator pattern. The artificial rank causes it to be
367 added last, providing the desired independence. */
369 if (TREE_CODE (e) == SSA_NAME)
376 if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
377 && SSA_NAME_IS_DEFAULT_DEF (e))
378 return find_operand_rank (e);
380 stmt = SSA_NAME_DEF_STMT (e);
381 if (gimple_bb (stmt) == NULL)
384 if (gimple_code (stmt) == GIMPLE_PHI)
385 return phi_rank (stmt);
387 if (!is_gimple_assign (stmt)
388 || gimple_vdef (stmt))
389 return bb_rank[gimple_bb (stmt)->index];
391 /* If we already have a rank for this expression, use that. */
392 rank = find_operand_rank (e);
396 /* Otherwise, find the maximum rank for the operands. As an
397 exception, remove the bias from loop-carried phis when propagating
398 the rank so that dependent operations are not also biased. */
400 if (gimple_assign_single_p (stmt))
402 tree rhs = gimple_assign_rhs1 (stmt);
403 n = TREE_OPERAND_LENGTH (rhs);
405 rank = propagate_rank (rank, rhs);
408 for (i = 0; i < n; i++)
410 op = TREE_OPERAND (rhs, i);
413 rank = propagate_rank (rank, op);
419 n = gimple_num_ops (stmt);
420 for (i = 1; i < n; i++)
422 op = gimple_op (stmt, i);
424 rank = propagate_rank (rank, op);
428 if (dump_file && (dump_flags & TDF_DETAILS))
430 fprintf (dump_file, "Rank for ");
431 print_generic_expr (dump_file, e, 0);
432 fprintf (dump_file, " is %ld\n", (rank + 1));
435 /* Note the rank in the hashtable so we don't recompute it. */
436 insert_operand_rank (e, (rank + 1));
440 /* Globals, etc, are rank 0 */
444 DEF_VEC_P(operand_entry_t);
445 DEF_VEC_ALLOC_P(operand_entry_t, heap);
447 /* We want integer ones to end up last no matter what, since they are
448 the ones we can do the most with. */
449 #define INTEGER_CONST_TYPE 1 << 3
450 #define FLOAT_CONST_TYPE 1 << 2
451 #define OTHER_CONST_TYPE 1 << 1
453 /* Classify an invariant tree into integer, float, or other, so that
454 we can sort them to be near other constants of the same type. */
456 constant_type (tree t)
458 if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
459 return INTEGER_CONST_TYPE;
460 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
461 return FLOAT_CONST_TYPE;
463 return OTHER_CONST_TYPE;
466 /* qsort comparison function to sort operand entries PA and PB by rank
467 so that the sorted array is ordered by rank in decreasing order. */
469 sort_by_operand_rank (const void *pa, const void *pb)
471 const operand_entry_t oea = *(const operand_entry_t *)pa;
472 const operand_entry_t oeb = *(const operand_entry_t *)pb;
474 /* It's nicer for optimize_expression if constants that are likely
475 to fold when added/multiplied//whatever are put next to each
476 other. Since all constants have rank 0, order them by type. */
477 if (oeb->rank == 0 && oea->rank == 0)
479 if (constant_type (oeb->op) != constant_type (oea->op))
480 return constant_type (oeb->op) - constant_type (oea->op);
482 /* To make sorting result stable, we use unique IDs to determine
484 return oeb->id - oea->id;
487 /* Lastly, make sure the versions that are the same go next to each
488 other. We use SSA_NAME_VERSION because it's stable. */
489 if ((oeb->rank - oea->rank == 0)
490 && TREE_CODE (oea->op) == SSA_NAME
491 && TREE_CODE (oeb->op) == SSA_NAME)
493 if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
494 return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
496 return oeb->id - oea->id;
499 if (oeb->rank != oea->rank)
500 return oeb->rank - oea->rank;
502 return oeb->id - oea->id;
505 /* Add an operand entry to *OPS for the tree operand OP. */
508 add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
510 operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
513 oe->rank = get_rank (op);
514 oe->id = next_operand_entry_id++;
515 VEC_safe_push (operand_entry_t, heap, *ops, oe);
518 /* Return true if STMT is reassociable operation containing a binary
519 operation with tree code CODE, and is inside LOOP. */
522 is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop)
524 basic_block bb = gimple_bb (stmt);
526 if (gimple_bb (stmt) == NULL)
529 if (!flow_bb_inside_loop_p (loop, bb))
532 if (is_gimple_assign (stmt)
533 && gimple_assign_rhs_code (stmt) == code
534 && has_single_use (gimple_assign_lhs (stmt)))
541 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
542 operand of the negate operation. Otherwise, return NULL. */
545 get_unary_op (tree name, enum tree_code opcode)
547 gimple stmt = SSA_NAME_DEF_STMT (name);
549 if (!is_gimple_assign (stmt))
552 if (gimple_assign_rhs_code (stmt) == opcode)
553 return gimple_assign_rhs1 (stmt);
557 /* If CURR and LAST are a pair of ops that OPCODE allows us to
558 eliminate through equivalences, do so, remove them from OPS, and
559 return true. Otherwise, return false. */
562 eliminate_duplicate_pair (enum tree_code opcode,
563 VEC (operand_entry_t, heap) **ops,
566 operand_entry_t curr,
567 operand_entry_t last)
570 /* If we have two of the same op, and the opcode is & |, min, or max,
571 we can eliminate one of them.
572 If we have two of the same op, and the opcode is ^, we can
573 eliminate both of them. */
575 if (last && last->op == curr->op)
583 if (dump_file && (dump_flags & TDF_DETAILS))
585 fprintf (dump_file, "Equivalence: ");
586 print_generic_expr (dump_file, curr->op, 0);
587 fprintf (dump_file, " [&|minmax] ");
588 print_generic_expr (dump_file, last->op, 0);
589 fprintf (dump_file, " -> ");
590 print_generic_stmt (dump_file, last->op, 0);
593 VEC_ordered_remove (operand_entry_t, *ops, i);
594 reassociate_stats.ops_eliminated ++;
599 if (dump_file && (dump_flags & TDF_DETAILS))
601 fprintf (dump_file, "Equivalence: ");
602 print_generic_expr (dump_file, curr->op, 0);
603 fprintf (dump_file, " ^ ");
604 print_generic_expr (dump_file, last->op, 0);
605 fprintf (dump_file, " -> nothing\n");
608 reassociate_stats.ops_eliminated += 2;
610 if (VEC_length (operand_entry_t, *ops) == 2)
612 VEC_free (operand_entry_t, heap, *ops);
614 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (last->op)));
619 VEC_ordered_remove (operand_entry_t, *ops, i-1);
620 VEC_ordered_remove (operand_entry_t, *ops, i-1);
632 static VEC(tree, heap) *plus_negates;
634 /* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
635 expression, look in OPS for a corresponding positive operation to cancel
636 it out. If we find one, remove the other from OPS, replace
637 OPS[CURRINDEX] with 0 or -1, respectively, and return true. Otherwise,
641 eliminate_plus_minus_pair (enum tree_code opcode,
642 VEC (operand_entry_t, heap) **ops,
643 unsigned int currindex,
644 operand_entry_t curr)
651 if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
654 negateop = get_unary_op (curr->op, NEGATE_EXPR);
655 notop = get_unary_op (curr->op, BIT_NOT_EXPR);
656 if (negateop == NULL_TREE && notop == NULL_TREE)
659 /* Any non-negated version will have a rank that is one less than
660 the current rank. So once we hit those ranks, if we don't find
663 for (i = currindex + 1;
664 VEC_iterate (operand_entry_t, *ops, i, oe)
665 && oe->rank >= curr->rank - 1 ;
668 if (oe->op == negateop)
671 if (dump_file && (dump_flags & TDF_DETAILS))
673 fprintf (dump_file, "Equivalence: ");
674 print_generic_expr (dump_file, negateop, 0);
675 fprintf (dump_file, " + -");
676 print_generic_expr (dump_file, oe->op, 0);
677 fprintf (dump_file, " -> 0\n");
680 VEC_ordered_remove (operand_entry_t, *ops, i);
681 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (oe->op)));
682 VEC_ordered_remove (operand_entry_t, *ops, currindex);
683 reassociate_stats.ops_eliminated ++;
687 else if (oe->op == notop)
689 tree op_type = TREE_TYPE (oe->op);
691 if (dump_file && (dump_flags & TDF_DETAILS))
693 fprintf (dump_file, "Equivalence: ");
694 print_generic_expr (dump_file, notop, 0);
695 fprintf (dump_file, " + ~");
696 print_generic_expr (dump_file, oe->op, 0);
697 fprintf (dump_file, " -> -1\n");
700 VEC_ordered_remove (operand_entry_t, *ops, i);
701 add_to_ops_vec (ops, build_int_cst_type (op_type, -1));
702 VEC_ordered_remove (operand_entry_t, *ops, currindex);
703 reassociate_stats.ops_eliminated ++;
709 /* CURR->OP is a negate expr in a plus expr: save it for later
710 inspection in repropagate_negates(). */
711 if (negateop != NULL_TREE)
712 VEC_safe_push (tree, heap, plus_negates, curr->op);
717 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
718 bitwise not expression, look in OPS for a corresponding operand to
719 cancel it out. If we find one, remove the other from OPS, replace
720 OPS[CURRINDEX] with 0, and return true. Otherwise, return
724 eliminate_not_pairs (enum tree_code opcode,
725 VEC (operand_entry_t, heap) **ops,
726 unsigned int currindex,
727 operand_entry_t curr)
733 if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
734 || TREE_CODE (curr->op) != SSA_NAME)
737 notop = get_unary_op (curr->op, BIT_NOT_EXPR);
738 if (notop == NULL_TREE)
741 /* Any non-not version will have a rank that is one less than
742 the current rank. So once we hit those ranks, if we don't find
745 for (i = currindex + 1;
746 VEC_iterate (operand_entry_t, *ops, i, oe)
747 && oe->rank >= curr->rank - 1;
752 if (dump_file && (dump_flags & TDF_DETAILS))
754 fprintf (dump_file, "Equivalence: ");
755 print_generic_expr (dump_file, notop, 0);
756 if (opcode == BIT_AND_EXPR)
757 fprintf (dump_file, " & ~");
758 else if (opcode == BIT_IOR_EXPR)
759 fprintf (dump_file, " | ~");
760 print_generic_expr (dump_file, oe->op, 0);
761 if (opcode == BIT_AND_EXPR)
762 fprintf (dump_file, " -> 0\n");
763 else if (opcode == BIT_IOR_EXPR)
764 fprintf (dump_file, " -> -1\n");
767 if (opcode == BIT_AND_EXPR)
768 oe->op = build_zero_cst (TREE_TYPE (oe->op));
769 else if (opcode == BIT_IOR_EXPR)
770 oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
771 TYPE_PRECISION (TREE_TYPE (oe->op)));
773 reassociate_stats.ops_eliminated
774 += VEC_length (operand_entry_t, *ops) - 1;
775 VEC_free (operand_entry_t, heap, *ops);
777 VEC_safe_push (operand_entry_t, heap, *ops, oe);
785 /* Use constant value that may be present in OPS to try to eliminate
786 operands. Note that this function is only really used when we've
787 eliminated ops for other reasons, or merged constants. Across
788 single statements, fold already does all of this, plus more. There
789 is little point in duplicating logic, so I've only included the
790 identities that I could ever construct testcases to trigger. */
793 eliminate_using_constants (enum tree_code opcode,
794 VEC(operand_entry_t, heap) **ops)
796 operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
797 tree type = TREE_TYPE (oelast->op);
799 if (oelast->rank == 0
800 && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type)))
805 if (integer_zerop (oelast->op))
807 if (VEC_length (operand_entry_t, *ops) != 1)
809 if (dump_file && (dump_flags & TDF_DETAILS))
810 fprintf (dump_file, "Found & 0, removing all other ops\n");
812 reassociate_stats.ops_eliminated
813 += VEC_length (operand_entry_t, *ops) - 1;
815 VEC_free (operand_entry_t, heap, *ops);
817 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
821 else if (integer_all_onesp (oelast->op))
823 if (VEC_length (operand_entry_t, *ops) != 1)
825 if (dump_file && (dump_flags & TDF_DETAILS))
826 fprintf (dump_file, "Found & -1, removing\n");
827 VEC_pop (operand_entry_t, *ops);
828 reassociate_stats.ops_eliminated++;
833 if (integer_all_onesp (oelast->op))
835 if (VEC_length (operand_entry_t, *ops) != 1)
837 if (dump_file && (dump_flags & TDF_DETAILS))
838 fprintf (dump_file, "Found | -1, removing all other ops\n");
840 reassociate_stats.ops_eliminated
841 += VEC_length (operand_entry_t, *ops) - 1;
843 VEC_free (operand_entry_t, heap, *ops);
845 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
849 else if (integer_zerop (oelast->op))
851 if (VEC_length (operand_entry_t, *ops) != 1)
853 if (dump_file && (dump_flags & TDF_DETAILS))
854 fprintf (dump_file, "Found | 0, removing\n");
855 VEC_pop (operand_entry_t, *ops);
856 reassociate_stats.ops_eliminated++;
861 if (integer_zerop (oelast->op)
862 || (FLOAT_TYPE_P (type)
863 && !HONOR_NANS (TYPE_MODE (type))
864 && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
865 && real_zerop (oelast->op)))
867 if (VEC_length (operand_entry_t, *ops) != 1)
869 if (dump_file && (dump_flags & TDF_DETAILS))
870 fprintf (dump_file, "Found * 0, removing all other ops\n");
872 reassociate_stats.ops_eliminated
873 += VEC_length (operand_entry_t, *ops) - 1;
874 VEC_free (operand_entry_t, heap, *ops);
876 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
880 else if (integer_onep (oelast->op)
881 || (FLOAT_TYPE_P (type)
882 && !HONOR_SNANS (TYPE_MODE (type))
883 && real_onep (oelast->op)))
885 if (VEC_length (operand_entry_t, *ops) != 1)
887 if (dump_file && (dump_flags & TDF_DETAILS))
888 fprintf (dump_file, "Found * 1, removing\n");
889 VEC_pop (operand_entry_t, *ops);
890 reassociate_stats.ops_eliminated++;
898 if (integer_zerop (oelast->op)
899 || (FLOAT_TYPE_P (type)
900 && (opcode == PLUS_EXPR || opcode == MINUS_EXPR)
901 && fold_real_zero_addition_p (type, oelast->op,
902 opcode == MINUS_EXPR)))
904 if (VEC_length (operand_entry_t, *ops) != 1)
906 if (dump_file && (dump_flags & TDF_DETAILS))
907 fprintf (dump_file, "Found [|^+] 0, removing\n");
908 VEC_pop (operand_entry_t, *ops);
909 reassociate_stats.ops_eliminated++;
921 static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
924 /* Structure for tracking and counting operands. */
925 typedef struct oecount_s {
928 enum tree_code oecode;
933 DEF_VEC_ALLOC_O(oecount,heap);
935 /* The heap for the oecount hashtable and the sorted list of operands. */
936 static VEC (oecount, heap) *cvec;
938 /* Hash function for oecount. */
941 oecount_hash (const void *p)
943 const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42);
944 return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
947 /* Comparison function for oecount. */
950 oecount_eq (const void *p1, const void *p2)
952 const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42);
953 const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42);
954 return (c1->oecode == c2->oecode
955 && c1->op == c2->op);
958 /* Comparison function for qsort sorting oecount elements by count. */
961 oecount_cmp (const void *p1, const void *p2)
963 const oecount *c1 = (const oecount *)p1;
964 const oecount *c2 = (const oecount *)p2;
965 if (c1->cnt != c2->cnt)
966 return c1->cnt - c2->cnt;
968 /* If counts are identical, use unique IDs to stabilize qsort. */
969 return c1->id - c2->id;
972 /* Walks the linear chain with result *DEF searching for an operation
973 with operand OP and code OPCODE removing that from the chain. *DEF
974 is updated if there is only one operand but no operation left. */
977 zero_one_operation (tree *def, enum tree_code opcode, tree op)
979 gimple stmt = SSA_NAME_DEF_STMT (*def);
983 tree name = gimple_assign_rhs1 (stmt);
985 /* If this is the operation we look for and one of the operands
986 is ours simply propagate the other operand into the stmts
988 if (gimple_assign_rhs_code (stmt) == opcode
990 || gimple_assign_rhs2 (stmt) == op))
994 gimple_stmt_iterator gsi;
996 name = gimple_assign_rhs2 (stmt);
997 gcc_assert (has_single_use (gimple_assign_lhs (stmt)));
998 single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt);
999 if (gimple_assign_lhs (stmt) == *def)
1001 SET_USE (use, name);
1002 if (TREE_CODE (name) != SSA_NAME)
1003 update_stmt (use_stmt);
1004 gsi = gsi_for_stmt (stmt);
1005 gsi_remove (&gsi, true);
1006 release_defs (stmt);
1010 /* Continue walking the chain. */
1011 gcc_assert (name != op
1012 && TREE_CODE (name) == SSA_NAME);
1013 stmt = SSA_NAME_DEF_STMT (name);
1018 /* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
1019 the result. Places the statement after the definition of either
1020 OP1 or OP2. Returns the new statement. */
1023 build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode)
1025 gimple op1def = NULL, op2def = NULL;
1026 gimple_stmt_iterator gsi;
1030 /* Create the addition statement. */
1031 sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2);
1032 op = make_ssa_name (tmpvar, sum);
1033 gimple_assign_set_lhs (sum, op);
1035 /* Find an insertion place and insert. */
1036 if (TREE_CODE (op1) == SSA_NAME)
1037 op1def = SSA_NAME_DEF_STMT (op1);
1038 if (TREE_CODE (op2) == SSA_NAME)
1039 op2def = SSA_NAME_DEF_STMT (op2);
1040 if ((!op1def || gimple_nop_p (op1def))
1041 && (!op2def || gimple_nop_p (op2def)))
1043 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
1044 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
1046 else if ((!op1def || gimple_nop_p (op1def))
1047 || (op2def && !gimple_nop_p (op2def)
1048 && stmt_dominates_stmt_p (op1def, op2def)))
1050 if (gimple_code (op2def) == GIMPLE_PHI)
1052 gsi = gsi_after_labels (gimple_bb (op2def));
1053 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
1057 if (!stmt_ends_bb_p (op2def))
1059 gsi = gsi_for_stmt (op2def);
1060 gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
1067 FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs)
1068 if (e->flags & EDGE_FALLTHRU)
1069 gsi_insert_on_edge_immediate (e, sum);
1075 if (gimple_code (op1def) == GIMPLE_PHI)
1077 gsi = gsi_after_labels (gimple_bb (op1def));
1078 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
1082 if (!stmt_ends_bb_p (op1def))
1084 gsi = gsi_for_stmt (op1def);
1085 gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
1092 FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs)
1093 if (e->flags & EDGE_FALLTHRU)
1094 gsi_insert_on_edge_immediate (e, sum);
1103 /* Perform un-distribution of divisions and multiplications.
1104 A * X + B * X is transformed into (A + B) * X and A / X + B / X
1105 to (A + B) / X for real X.
1107 The algorithm is organized as follows.
1109 - First we walk the addition chain *OPS looking for summands that
1110 are defined by a multiplication or a real division. This results
1111 in the candidates bitmap with relevant indices into *OPS.
1113 - Second we build the chains of multiplications or divisions for
1114 these candidates, counting the number of occurences of (operand, code)
1115 pairs in all of the candidates chains.
1117 - Third we sort the (operand, code) pairs by number of occurence and
1118 process them starting with the pair with the most uses.
1120 * For each such pair we walk the candidates again to build a
1121 second candidate bitmap noting all multiplication/division chains
1122 that have at least one occurence of (operand, code).
1124 * We build an alternate addition chain only covering these
1125 candidates with one (operand, code) operation removed from their
1126 multiplication/division chain.
1128 * The first candidate gets replaced by the alternate addition chain
1129 multiplied/divided by the operand.
1131 * All candidate chains get disabled for further processing and
1132 processing of (operand, code) pairs continues.
1134 The alternate addition chains built are re-processed by the main
1135 reassociation algorithm which allows optimizing a * x * y + b * y * x
1136 to (a + b ) * x * y in one invocation of the reassociation pass. */
1139 undistribute_ops_list (enum tree_code opcode,
1140 VEC (operand_entry_t, heap) **ops, struct loop *loop)
1142 unsigned int length = VEC_length (operand_entry_t, *ops);
1143 operand_entry_t oe1;
1145 sbitmap candidates, candidates2;
1146 unsigned nr_candidates, nr_candidates2;
1147 sbitmap_iterator sbi0;
1148 VEC (operand_entry_t, heap) **subops;
1150 bool changed = false;
1151 int next_oecount_id = 0;
1154 || opcode != PLUS_EXPR)
1157 /* Build a list of candidates to process. */
1158 candidates = sbitmap_alloc (length);
1159 sbitmap_zero (candidates);
1161 FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe1)
1163 enum tree_code dcode;
1166 if (TREE_CODE (oe1->op) != SSA_NAME)
1168 oe1def = SSA_NAME_DEF_STMT (oe1->op);
1169 if (!is_gimple_assign (oe1def))
1171 dcode = gimple_assign_rhs_code (oe1def);
1172 if ((dcode != MULT_EXPR
1173 && dcode != RDIV_EXPR)
1174 || !is_reassociable_op (oe1def, dcode, loop))
1177 SET_BIT (candidates, i);
1181 if (nr_candidates < 2)
1183 sbitmap_free (candidates);
1187 if (dump_file && (dump_flags & TDF_DETAILS))
1189 fprintf (dump_file, "searching for un-distribute opportunities ");
1190 print_generic_expr (dump_file,
1191 VEC_index (operand_entry_t, *ops,
1192 sbitmap_first_set_bit (candidates))->op, 0);
1193 fprintf (dump_file, " %d\n", nr_candidates);
1196 /* Build linearized sub-operand lists and the counting table. */
1198 ctable = htab_create (15, oecount_hash, oecount_eq, NULL);
1199 subops = XCNEWVEC (VEC (operand_entry_t, heap) *,
1200 VEC_length (operand_entry_t, *ops));
1201 EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
1204 enum tree_code oecode;
1207 oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
1208 oecode = gimple_assign_rhs_code (oedef);
1209 linearize_expr_tree (&subops[i], oedef,
1210 associative_tree_code (oecode), false);
1212 FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
1219 c.id = next_oecount_id++;
1221 VEC_safe_push (oecount, heap, cvec, &c);
1222 idx = VEC_length (oecount, cvec) + 41;
1223 slot = htab_find_slot (ctable, (void *)idx, INSERT);
1226 *slot = (void *)idx;
1230 VEC_pop (oecount, cvec);
1231 VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++;
1235 htab_delete (ctable);
1237 /* Sort the counting table. */
1238 VEC_qsort (oecount, cvec, oecount_cmp);
1240 if (dump_file && (dump_flags & TDF_DETAILS))
1243 fprintf (dump_file, "Candidates:\n");
1244 FOR_EACH_VEC_ELT (oecount, cvec, j, c)
1246 fprintf (dump_file, " %u %s: ", c->cnt,
1247 c->oecode == MULT_EXPR
1248 ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
1249 print_generic_expr (dump_file, c->op, 0);
1250 fprintf (dump_file, "\n");
1254 /* Process the (operand, code) pairs in order of most occurence. */
1255 candidates2 = sbitmap_alloc (length);
1256 while (!VEC_empty (oecount, cvec))
1258 oecount *c = VEC_last (oecount, cvec);
1262 /* Now collect the operands in the outer chain that contain
1263 the common operand in their inner chain. */
1264 sbitmap_zero (candidates2);
1266 EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
1269 enum tree_code oecode;
1271 tree op = VEC_index (operand_entry_t, *ops, i)->op;
1273 /* If we undistributed in this chain already this may be
1275 if (TREE_CODE (op) != SSA_NAME)
1278 oedef = SSA_NAME_DEF_STMT (op);
1279 oecode = gimple_assign_rhs_code (oedef);
1280 if (oecode != c->oecode)
1283 FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
1285 if (oe1->op == c->op)
1287 SET_BIT (candidates2, i);
1294 if (nr_candidates2 >= 2)
1296 operand_entry_t oe1, oe2;
1299 int first = sbitmap_first_set_bit (candidates2);
1301 /* Build the new addition chain. */
1302 oe1 = VEC_index (operand_entry_t, *ops, first);
1303 if (dump_file && (dump_flags & TDF_DETAILS))
1305 fprintf (dump_file, "Building (");
1306 print_generic_expr (dump_file, oe1->op, 0);
1308 tmpvar = create_tmp_reg (TREE_TYPE (oe1->op), NULL);
1309 add_referenced_var (tmpvar);
1310 zero_one_operation (&oe1->op, c->oecode, c->op);
1311 EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
1314 oe2 = VEC_index (operand_entry_t, *ops, i);
1315 if (dump_file && (dump_flags & TDF_DETAILS))
1317 fprintf (dump_file, " + ");
1318 print_generic_expr (dump_file, oe2->op, 0);
1320 zero_one_operation (&oe2->op, c->oecode, c->op);
1321 sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
1322 oe2->op = build_zero_cst (TREE_TYPE (oe2->op));
1324 oe1->op = gimple_get_lhs (sum);
1327 /* Apply the multiplication/division. */
1328 prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode);
1329 if (dump_file && (dump_flags & TDF_DETAILS))
1331 fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/");
1332 print_generic_expr (dump_file, c->op, 0);
1333 fprintf (dump_file, "\n");
1336 /* Record it in the addition chain and disable further
1337 undistribution with this op. */
1338 oe1->op = gimple_assign_lhs (prod);
1339 oe1->rank = get_rank (oe1->op);
1340 VEC_free (operand_entry_t, heap, subops[first]);
1345 VEC_pop (oecount, cvec);
1348 for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i)
1349 VEC_free (operand_entry_t, heap, subops[i]);
1351 VEC_free (oecount, heap, cvec);
1352 sbitmap_free (candidates);
1353 sbitmap_free (candidates2);
1358 /* If OPCODE is BIT_IOR_EXPR or BIT_AND_EXPR and CURR is a comparison
1359 expression, examine the other OPS to see if any of them are comparisons
1360 of the same values, which we may be able to combine or eliminate.
1361 For example, we can rewrite (a < b) | (a == b) as (a <= b). */
1364 eliminate_redundant_comparison (enum tree_code opcode,
1365 VEC (operand_entry_t, heap) **ops,
1366 unsigned int currindex,
1367 operand_entry_t curr)
1370 enum tree_code lcode, rcode;
1375 if (opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
1378 /* Check that CURR is a comparison. */
1379 if (TREE_CODE (curr->op) != SSA_NAME)
1381 def1 = SSA_NAME_DEF_STMT (curr->op);
1382 if (!is_gimple_assign (def1))
1384 lcode = gimple_assign_rhs_code (def1);
1385 if (TREE_CODE_CLASS (lcode) != tcc_comparison)
1387 op1 = gimple_assign_rhs1 (def1);
1388 op2 = gimple_assign_rhs2 (def1);
1390 /* Now look for a similar comparison in the remaining OPS. */
1391 for (i = currindex + 1;
1392 VEC_iterate (operand_entry_t, *ops, i, oe);
1397 if (TREE_CODE (oe->op) != SSA_NAME)
1399 def2 = SSA_NAME_DEF_STMT (oe->op);
1400 if (!is_gimple_assign (def2))
1402 rcode = gimple_assign_rhs_code (def2);
1403 if (TREE_CODE_CLASS (rcode) != tcc_comparison)
1406 /* If we got here, we have a match. See if we can combine the
1408 if (opcode == BIT_IOR_EXPR)
1409 t = maybe_fold_or_comparisons (lcode, op1, op2,
1410 rcode, gimple_assign_rhs1 (def2),
1411 gimple_assign_rhs2 (def2));
1413 t = maybe_fold_and_comparisons (lcode, op1, op2,
1414 rcode, gimple_assign_rhs1 (def2),
1415 gimple_assign_rhs2 (def2));
1419 /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
1420 always give us a boolean_type_node value back. If the original
1421 BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
1422 we need to convert. */
1423 if (!useless_type_conversion_p (TREE_TYPE (curr->op), TREE_TYPE (t)))
1424 t = fold_convert (TREE_TYPE (curr->op), t);
1426 if (TREE_CODE (t) != INTEGER_CST
1427 && !operand_equal_p (t, curr->op, 0))
1429 enum tree_code subcode;
1430 tree newop1, newop2;
1431 if (!COMPARISON_CLASS_P (t))
1433 extract_ops_from_tree (t, &subcode, &newop1, &newop2);
1434 STRIP_USELESS_TYPE_CONVERSION (newop1);
1435 STRIP_USELESS_TYPE_CONVERSION (newop2);
1436 if (!is_gimple_val (newop1) || !is_gimple_val (newop2))
1440 if (dump_file && (dump_flags & TDF_DETAILS))
1442 fprintf (dump_file, "Equivalence: ");
1443 print_generic_expr (dump_file, curr->op, 0);
1444 fprintf (dump_file, " %s ", op_symbol_code (opcode));
1445 print_generic_expr (dump_file, oe->op, 0);
1446 fprintf (dump_file, " -> ");
1447 print_generic_expr (dump_file, t, 0);
1448 fprintf (dump_file, "\n");
1451 /* Now we can delete oe, as it has been subsumed by the new combined
1453 VEC_ordered_remove (operand_entry_t, *ops, i);
1454 reassociate_stats.ops_eliminated ++;
1456 /* If t is the same as curr->op, we're done. Otherwise we must
1457 replace curr->op with t. Special case is if we got a constant
1458 back, in which case we add it to the end instead of in place of
1459 the current entry. */
1460 if (TREE_CODE (t) == INTEGER_CST)
1462 VEC_ordered_remove (operand_entry_t, *ops, currindex);
1463 add_to_ops_vec (ops, t);
1465 else if (!operand_equal_p (t, curr->op, 0))
1469 enum tree_code subcode;
1472 gcc_assert (COMPARISON_CLASS_P (t));
1473 tmpvar = create_tmp_var (TREE_TYPE (t), NULL);
1474 add_referenced_var (tmpvar);
1475 extract_ops_from_tree (t, &subcode, &newop1, &newop2);
1476 STRIP_USELESS_TYPE_CONVERSION (newop1);
1477 STRIP_USELESS_TYPE_CONVERSION (newop2);
1478 gcc_checking_assert (is_gimple_val (newop1)
1479 && is_gimple_val (newop2));
1480 sum = build_and_add_sum (tmpvar, newop1, newop2, subcode);
1481 curr->op = gimple_get_lhs (sum);
1489 /* Perform various identities and other optimizations on the list of
1490 operand entries, stored in OPS. The tree code for the binary
1491 operation between all the operands is OPCODE. */
1494 optimize_ops_list (enum tree_code opcode,
1495 VEC (operand_entry_t, heap) **ops)
1497 unsigned int length = VEC_length (operand_entry_t, *ops);
1500 operand_entry_t oelast = NULL;
1501 bool iterate = false;
1506 oelast = VEC_last (operand_entry_t, *ops);
1508 /* If the last two are constants, pop the constants off, merge them
1509 and try the next two. */
1510 if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
1512 operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
1514 if (oelm1->rank == 0
1515 && is_gimple_min_invariant (oelm1->op)
1516 && useless_type_conversion_p (TREE_TYPE (oelm1->op),
1517 TREE_TYPE (oelast->op)))
1519 tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
1520 oelm1->op, oelast->op);
1522 if (folded && is_gimple_min_invariant (folded))
1524 if (dump_file && (dump_flags & TDF_DETAILS))
1525 fprintf (dump_file, "Merging constants\n");
1527 VEC_pop (operand_entry_t, *ops);
1528 VEC_pop (operand_entry_t, *ops);
1530 add_to_ops_vec (ops, folded);
1531 reassociate_stats.constants_eliminated++;
1533 optimize_ops_list (opcode, ops);
1539 eliminate_using_constants (opcode, ops);
1542 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
1546 if (eliminate_not_pairs (opcode, ops, i, oe))
1548 if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
1549 || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe))
1550 || (!done && eliminate_redundant_comparison (opcode, ops, i, oe)))
1562 length = VEC_length (operand_entry_t, *ops);
1563 oelast = VEC_last (operand_entry_t, *ops);
1566 optimize_ops_list (opcode, ops);
1569 /* Return true if OPERAND is defined by a PHI node which uses the LHS
1570 of STMT in it's operands. This is also known as a "destructive
1571 update" operation. */
1574 is_phi_for_stmt (gimple stmt, tree operand)
1578 use_operand_p arg_p;
1581 if (TREE_CODE (operand) != SSA_NAME)
1584 lhs = gimple_assign_lhs (stmt);
1586 def_stmt = SSA_NAME_DEF_STMT (operand);
1587 if (gimple_code (def_stmt) != GIMPLE_PHI)
1590 FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
1591 if (lhs == USE_FROM_PTR (arg_p))
1596 /* Remove def stmt of VAR if VAR has zero uses and recurse
1597 on rhs1 operand if so. */
1600 remove_visited_stmt_chain (tree var)
1603 gimple_stmt_iterator gsi;
1607 if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
1609 stmt = SSA_NAME_DEF_STMT (var);
1610 if (!is_gimple_assign (stmt)
1611 || !gimple_visited_p (stmt))
1613 var = gimple_assign_rhs1 (stmt);
1614 gsi = gsi_for_stmt (stmt);
1615 gsi_remove (&gsi, true);
1616 release_defs (stmt);
1620 /* Recursively rewrite our linearized statements so that the operators
1621 match those in OPS[OPINDEX], putting the computation in rank
1625 rewrite_expr_tree (gimple stmt, unsigned int opindex,
1626 VEC(operand_entry_t, heap) * ops, bool moved)
1628 tree rhs1 = gimple_assign_rhs1 (stmt);
1629 tree rhs2 = gimple_assign_rhs2 (stmt);
1632 /* If we have three operands left, then we want to make sure the one
1633 that gets the double binary op are the ones with the same rank.
1635 The alternative we try is to see if this is a destructive
1636 update style statement, which is like:
1639 In that case, we want to use the destructive update form to
1640 expose the possible vectorizer sum reduction opportunity.
1641 In that case, the third operand will be the phi node.
1643 We could, of course, try to be better as noted above, and do a
1644 lot of work to try to find these opportunities in >3 operand
1645 cases, but it is unlikely to be worth it. */
1646 if (opindex + 3 == VEC_length (operand_entry_t, ops))
1648 operand_entry_t oe1, oe2, oe3;
1650 oe1 = VEC_index (operand_entry_t, ops, opindex);
1651 oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
1652 oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
1654 if ((oe1->rank == oe2->rank
1655 && oe2->rank != oe3->rank)
1656 || (is_phi_for_stmt (stmt, oe3->op)
1657 && !is_phi_for_stmt (stmt, oe1->op)
1658 && !is_phi_for_stmt (stmt, oe2->op)))
1660 struct operand_entry temp = *oe3;
1662 oe3->rank = oe1->rank;
1664 oe1->rank= temp.rank;
1666 else if ((oe1->rank == oe3->rank
1667 && oe2->rank != oe3->rank)
1668 || (is_phi_for_stmt (stmt, oe2->op)
1669 && !is_phi_for_stmt (stmt, oe1->op)
1670 && !is_phi_for_stmt (stmt, oe3->op)))
1672 struct operand_entry temp = *oe2;
1674 oe2->rank = oe1->rank;
1676 oe1->rank= temp.rank;
1680 /* The final recursion case for this function is that you have
1681 exactly two operations left.
1682 If we had one exactly one op in the entire list to start with, we
1683 would have never called this function, and the tail recursion
1684 rewrites them one at a time. */
1685 if (opindex + 2 == VEC_length (operand_entry_t, ops))
1687 operand_entry_t oe1, oe2;
1689 oe1 = VEC_index (operand_entry_t, ops, opindex);
1690 oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
1692 if (rhs1 != oe1->op || rhs2 != oe2->op)
1694 if (dump_file && (dump_flags & TDF_DETAILS))
1696 fprintf (dump_file, "Transforming ");
1697 print_gimple_stmt (dump_file, stmt, 0, 0);
1700 gimple_assign_set_rhs1 (stmt, oe1->op);
1701 gimple_assign_set_rhs2 (stmt, oe2->op);
1703 if (rhs1 != oe1->op && rhs1 != oe2->op)
1704 remove_visited_stmt_chain (rhs1);
1706 if (dump_file && (dump_flags & TDF_DETAILS))
1708 fprintf (dump_file, " into ");
1709 print_gimple_stmt (dump_file, stmt, 0, 0);
1716 /* If we hit here, we should have 3 or more ops left. */
1717 gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
1719 /* Rewrite the next operator. */
1720 oe = VEC_index (operand_entry_t, ops, opindex);
1726 gimple_stmt_iterator gsinow, gsirhs1;
1727 gimple stmt1 = stmt, stmt2;
1730 gsinow = gsi_for_stmt (stmt);
1731 count = VEC_length (operand_entry_t, ops) - opindex - 2;
1732 while (count-- != 0)
1734 stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
1735 gsirhs1 = gsi_for_stmt (stmt2);
1736 gsi_move_before (&gsirhs1, &gsinow);
1743 if (dump_file && (dump_flags & TDF_DETAILS))
1745 fprintf (dump_file, "Transforming ");
1746 print_gimple_stmt (dump_file, stmt, 0, 0);
1749 gimple_assign_set_rhs2 (stmt, oe->op);
1752 if (dump_file && (dump_flags & TDF_DETAILS))
1754 fprintf (dump_file, " into ");
1755 print_gimple_stmt (dump_file, stmt, 0, 0);
1758 /* Recurse on the LHS of the binary operator, which is guaranteed to
1759 be the non-leaf side. */
1760 rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved);
1763 /* Transform STMT, which is really (A +B) + (C + D) into the left
1764 linear form, ((A+B)+C)+D.
1765 Recurse on D if necessary. */
1768 linearize_expr (gimple stmt)
1770 gimple_stmt_iterator gsinow, gsirhs;
1771 gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
1772 gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1773 enum tree_code rhscode = gimple_assign_rhs_code (stmt);
1774 gimple newbinrhs = NULL;
1775 struct loop *loop = loop_containing_stmt (stmt);
1777 gcc_assert (is_reassociable_op (binlhs, rhscode, loop)
1778 && is_reassociable_op (binrhs, rhscode, loop));
1780 gsinow = gsi_for_stmt (stmt);
1781 gsirhs = gsi_for_stmt (binrhs);
1782 gsi_move_before (&gsirhs, &gsinow);
1784 gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
1785 gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs));
1786 gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs));
1788 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
1789 newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1791 if (dump_file && (dump_flags & TDF_DETAILS))
1793 fprintf (dump_file, "Linearized: ");
1794 print_gimple_stmt (dump_file, stmt, 0, 0);
1797 reassociate_stats.linearized++;
1798 update_stmt (binrhs);
1799 update_stmt (binlhs);
1802 gimple_set_visited (stmt, true);
1803 gimple_set_visited (binlhs, true);
1804 gimple_set_visited (binrhs, true);
1806 /* Tail recurse on the new rhs if it still needs reassociation. */
1807 if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
1808 /* ??? This should probably be linearize_expr (newbinrhs) but I don't
1809 want to change the algorithm while converting to tuples. */
1810 linearize_expr (stmt);
1813 /* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return
1814 it. Otherwise, return NULL. */
1817 get_single_immediate_use (tree lhs)
1819 use_operand_p immuse;
1822 if (TREE_CODE (lhs) == SSA_NAME
1823 && single_imm_use (lhs, &immuse, &immusestmt)
1824 && is_gimple_assign (immusestmt))
1830 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
1831 representing the negated value. Insertions of any necessary
1832 instructions go before GSI.
1833 This function is recursive in that, if you hand it "a_5" as the
1834 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1835 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */
1838 negate_value (tree tonegate, gimple_stmt_iterator *gsi)
1840 gimple negatedefstmt= NULL;
1841 tree resultofnegate;
1843 /* If we are trying to negate a name, defined by an add, negate the
1844 add operands instead. */
1845 if (TREE_CODE (tonegate) == SSA_NAME)
1846 negatedefstmt = SSA_NAME_DEF_STMT (tonegate);
1847 if (TREE_CODE (tonegate) == SSA_NAME
1848 && is_gimple_assign (negatedefstmt)
1849 && TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME
1850 && has_single_use (gimple_assign_lhs (negatedefstmt))
1851 && gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR)
1853 gimple_stmt_iterator gsi;
1854 tree rhs1 = gimple_assign_rhs1 (negatedefstmt);
1855 tree rhs2 = gimple_assign_rhs2 (negatedefstmt);
1857 gsi = gsi_for_stmt (negatedefstmt);
1858 rhs1 = negate_value (rhs1, &gsi);
1859 gimple_assign_set_rhs1 (negatedefstmt, rhs1);
1861 gsi = gsi_for_stmt (negatedefstmt);
1862 rhs2 = negate_value (rhs2, &gsi);
1863 gimple_assign_set_rhs2 (negatedefstmt, rhs2);
1865 update_stmt (negatedefstmt);
1866 return gimple_assign_lhs (negatedefstmt);
1869 tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
1870 resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true,
1871 NULL_TREE, true, GSI_SAME_STMT);
1872 return resultofnegate;
1875 /* Return true if we should break up the subtract in STMT into an add
1876 with negate. This is true when we the subtract operands are really
1877 adds, or the subtract itself is used in an add expression. In
1878 either case, breaking up the subtract into an add with negate
1879 exposes the adds to reassociation. */
1882 should_break_up_subtract (gimple stmt)
1884 tree lhs = gimple_assign_lhs (stmt);
1885 tree binlhs = gimple_assign_rhs1 (stmt);
1886 tree binrhs = gimple_assign_rhs2 (stmt);
1888 struct loop *loop = loop_containing_stmt (stmt);
1890 if (TREE_CODE (binlhs) == SSA_NAME
1891 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
1894 if (TREE_CODE (binrhs) == SSA_NAME
1895 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
1898 if (TREE_CODE (lhs) == SSA_NAME
1899 && (immusestmt = get_single_immediate_use (lhs))
1900 && is_gimple_assign (immusestmt)
1901 && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR
1902 || gimple_assign_rhs_code (immusestmt) == MULT_EXPR))
1907 /* Transform STMT from A - B into A + -B. */
1910 break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip)
1912 tree rhs1 = gimple_assign_rhs1 (stmt);
1913 tree rhs2 = gimple_assign_rhs2 (stmt);
1915 if (dump_file && (dump_flags & TDF_DETAILS))
1917 fprintf (dump_file, "Breaking up subtract ");
1918 print_gimple_stmt (dump_file, stmt, 0, 0);
1921 rhs2 = negate_value (rhs2, gsip);
1922 gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2);
1926 /* Recursively linearize a binary expression that is the RHS of STMT.
1927 Place the operands of the expression tree in the vector named OPS. */
1930 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
1931 bool is_associative, bool set_visited)
1933 tree binlhs = gimple_assign_rhs1 (stmt);
1934 tree binrhs = gimple_assign_rhs2 (stmt);
1935 gimple binlhsdef, binrhsdef;
1936 bool binlhsisreassoc = false;
1937 bool binrhsisreassoc = false;
1938 enum tree_code rhscode = gimple_assign_rhs_code (stmt);
1939 struct loop *loop = loop_containing_stmt (stmt);
1942 gimple_set_visited (stmt, true);
1944 if (TREE_CODE (binlhs) == SSA_NAME)
1946 binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1947 binlhsisreassoc = (is_reassociable_op (binlhsdef, rhscode, loop)
1948 && !stmt_could_throw_p (binlhsdef));
1951 if (TREE_CODE (binrhs) == SSA_NAME)
1953 binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1954 binrhsisreassoc = (is_reassociable_op (binrhsdef, rhscode, loop)
1955 && !stmt_could_throw_p (binrhsdef));
1958 /* If the LHS is not reassociable, but the RHS is, we need to swap
1959 them. If neither is reassociable, there is nothing we can do, so
1960 just put them in the ops vector. If the LHS is reassociable,
1961 linearize it. If both are reassociable, then linearize the RHS
1964 if (!binlhsisreassoc)
1968 /* If this is not a associative operation like division, give up. */
1969 if (!is_associative)
1971 add_to_ops_vec (ops, binrhs);
1975 if (!binrhsisreassoc)
1977 add_to_ops_vec (ops, binrhs);
1978 add_to_ops_vec (ops, binlhs);
1982 if (dump_file && (dump_flags & TDF_DETAILS))
1984 fprintf (dump_file, "swapping operands of ");
1985 print_gimple_stmt (dump_file, stmt, 0, 0);
1988 swap_tree_operands (stmt,
1989 gimple_assign_rhs1_ptr (stmt),
1990 gimple_assign_rhs2_ptr (stmt));
1993 if (dump_file && (dump_flags & TDF_DETAILS))
1995 fprintf (dump_file, " is now ");
1996 print_gimple_stmt (dump_file, stmt, 0, 0);
1999 /* We want to make it so the lhs is always the reassociative op,
2005 else if (binrhsisreassoc)
2007 linearize_expr (stmt);
2008 binlhs = gimple_assign_rhs1 (stmt);
2009 binrhs = gimple_assign_rhs2 (stmt);
2012 gcc_assert (TREE_CODE (binrhs) != SSA_NAME
2013 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
2015 linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
2016 is_associative, set_visited);
2017 add_to_ops_vec (ops, binrhs);
2020 /* Repropagate the negates back into subtracts, since no other pass
2021 currently does it. */
2024 repropagate_negates (void)
2029 FOR_EACH_VEC_ELT (tree, plus_negates, i, negate)
2031 gimple user = get_single_immediate_use (negate);
2033 if (!user || !is_gimple_assign (user))
2036 /* The negate operand can be either operand of a PLUS_EXPR
2037 (it can be the LHS if the RHS is a constant for example).
2039 Force the negate operand to the RHS of the PLUS_EXPR, then
2040 transform the PLUS_EXPR into a MINUS_EXPR. */
2041 if (gimple_assign_rhs_code (user) == PLUS_EXPR)
2043 /* If the negated operand appears on the LHS of the
2044 PLUS_EXPR, exchange the operands of the PLUS_EXPR
2045 to force the negated operand to the RHS of the PLUS_EXPR. */
2046 if (gimple_assign_rhs1 (user) == negate)
2048 swap_tree_operands (user,
2049 gimple_assign_rhs1_ptr (user),
2050 gimple_assign_rhs2_ptr (user));
2053 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
2054 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */
2055 if (gimple_assign_rhs2 (user) == negate)
2057 tree rhs1 = gimple_assign_rhs1 (user);
2058 tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
2059 gimple_stmt_iterator gsi = gsi_for_stmt (user);
2060 gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
2064 else if (gimple_assign_rhs_code (user) == MINUS_EXPR)
2066 if (gimple_assign_rhs1 (user) == negate)
2071 which we transform into
2074 This pushes down the negate which we possibly can merge
2075 into some other operation, hence insert it into the
2076 plus_negates vector. */
2077 gimple feed = SSA_NAME_DEF_STMT (negate);
2078 tree a = gimple_assign_rhs1 (feed);
2079 tree rhs2 = gimple_assign_rhs2 (user);
2080 gimple_stmt_iterator gsi = gsi_for_stmt (feed), gsi2;
2081 gimple_replace_lhs (feed, negate);
2082 gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, a, rhs2);
2083 update_stmt (gsi_stmt (gsi));
2084 gsi2 = gsi_for_stmt (user);
2085 gimple_assign_set_rhs_with_ops (&gsi2, NEGATE_EXPR, negate, NULL);
2086 update_stmt (gsi_stmt (gsi2));
2087 gsi_move_before (&gsi, &gsi2);
2088 VEC_safe_push (tree, heap, plus_negates,
2089 gimple_assign_lhs (gsi_stmt (gsi2)));
2093 /* Transform "x = -a; y = b - x" into "y = b + a", getting
2094 rid of one operation. */
2095 gimple feed = SSA_NAME_DEF_STMT (negate);
2096 tree a = gimple_assign_rhs1 (feed);
2097 tree rhs1 = gimple_assign_rhs1 (user);
2098 gimple_stmt_iterator gsi = gsi_for_stmt (user);
2099 gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, rhs1, a);
2100 update_stmt (gsi_stmt (gsi));
2106 /* Returns true if OP is of a type for which we can do reassociation.
2107 That is for integral or non-saturating fixed-point types, and for
2108 floating point type when associative-math is enabled. */
2111 can_reassociate_p (tree op)
2113 tree type = TREE_TYPE (op);
2114 if ((INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type))
2115 || NON_SAT_FIXED_POINT_TYPE_P (type)
2116 || (flag_associative_math && FLOAT_TYPE_P (type)))
2121 /* Break up subtract operations in block BB.
2123 We do this top down because we don't know whether the subtract is
2124 part of a possible chain of reassociation except at the top.
2133 we want to break up k = t - q, but we won't until we've transformed q
2134 = b - r, which won't be broken up until we transform b = c - d.
2136 En passant, clear the GIMPLE visited flag on every statement. */
2139 break_up_subtract_bb (basic_block bb)
2141 gimple_stmt_iterator gsi;
2144 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2146 gimple stmt = gsi_stmt (gsi);
2147 gimple_set_visited (stmt, false);
2149 if (!is_gimple_assign (stmt)
2150 || !can_reassociate_p (gimple_assign_lhs (stmt)))
2153 /* Look for simple gimple subtract operations. */
2154 if (gimple_assign_rhs_code (stmt) == MINUS_EXPR)
2156 if (!can_reassociate_p (gimple_assign_rhs1 (stmt))
2157 || !can_reassociate_p (gimple_assign_rhs2 (stmt)))
2160 /* Check for a subtract used only in an addition. If this
2161 is the case, transform it into add of a negate for better
2162 reassociation. IE transform C = A-B into C = A + -B if C
2163 is only used in an addition. */
2164 if (should_break_up_subtract (stmt))
2165 break_up_subtract (stmt, &gsi);
2167 else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR
2168 && can_reassociate_p (gimple_assign_rhs1 (stmt)))
2169 VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt));
2171 for (son = first_dom_son (CDI_DOMINATORS, bb);
2173 son = next_dom_son (CDI_DOMINATORS, son))
2174 break_up_subtract_bb (son);
2177 /* Reassociate expressions in basic block BB and its post-dominator as
2181 reassociate_bb (basic_block bb)
2183 gimple_stmt_iterator gsi;
2186 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
2188 gimple stmt = gsi_stmt (gsi);
2190 if (is_gimple_assign (stmt)
2191 && !stmt_could_throw_p (stmt))
2193 tree lhs, rhs1, rhs2;
2194 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
2196 /* If this is not a gimple binary expression, there is
2197 nothing for us to do with it. */
2198 if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS)
2201 /* If this was part of an already processed statement,
2202 we don't need to touch it again. */
2203 if (gimple_visited_p (stmt))
2205 /* This statement might have become dead because of previous
2207 if (has_zero_uses (gimple_get_lhs (stmt)))
2209 gsi_remove (&gsi, true);
2210 release_defs (stmt);
2211 /* We might end up removing the last stmt above which
2212 places the iterator to the end of the sequence.
2213 Reset it to the last stmt in this case which might
2214 be the end of the sequence as well if we removed
2215 the last statement of the sequence. In which case
2216 we need to bail out. */
2217 if (gsi_end_p (gsi))
2219 gsi = gsi_last_bb (bb);
2220 if (gsi_end_p (gsi))
2227 lhs = gimple_assign_lhs (stmt);
2228 rhs1 = gimple_assign_rhs1 (stmt);
2229 rhs2 = gimple_assign_rhs2 (stmt);
2231 /* For non-bit or min/max operations we can't associate
2232 all types. Verify that here. */
2233 if (rhs_code != BIT_IOR_EXPR
2234 && rhs_code != BIT_AND_EXPR
2235 && rhs_code != BIT_XOR_EXPR
2236 && rhs_code != MIN_EXPR
2237 && rhs_code != MAX_EXPR
2238 && (!can_reassociate_p (lhs)
2239 || !can_reassociate_p (rhs1)
2240 || !can_reassociate_p (rhs2)))
2243 if (associative_tree_code (rhs_code))
2245 VEC(operand_entry_t, heap) *ops = NULL;
2247 /* There may be no immediate uses left by the time we
2248 get here because we may have eliminated them all. */
2249 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
2252 gimple_set_visited (stmt, true);
2253 linearize_expr_tree (&ops, stmt, true, true);
2254 VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
2255 optimize_ops_list (rhs_code, &ops);
2256 if (undistribute_ops_list (rhs_code, &ops,
2257 loop_containing_stmt (stmt)))
2259 VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
2260 optimize_ops_list (rhs_code, &ops);
2263 if (VEC_length (operand_entry_t, ops) == 1)
2265 if (dump_file && (dump_flags & TDF_DETAILS))
2267 fprintf (dump_file, "Transforming ");
2268 print_gimple_stmt (dump_file, stmt, 0, 0);
2271 rhs1 = gimple_assign_rhs1 (stmt);
2272 gimple_assign_set_rhs_from_tree (&gsi,
2273 VEC_last (operand_entry_t,
2276 remove_visited_stmt_chain (rhs1);
2278 if (dump_file && (dump_flags & TDF_DETAILS))
2280 fprintf (dump_file, " into ");
2281 print_gimple_stmt (dump_file, stmt, 0, 0);
2285 rewrite_expr_tree (stmt, 0, ops, false);
2287 VEC_free (operand_entry_t, heap, ops);
2291 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
2293 son = next_dom_son (CDI_POST_DOMINATORS, son))
2294 reassociate_bb (son);
2297 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
2298 void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
2300 /* Dump the operand entry vector OPS to FILE. */
2303 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
2308 FOR_EACH_VEC_ELT (operand_entry_t, ops, i, oe)
2310 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
2311 print_generic_expr (file, oe->op, 0);
2315 /* Dump the operand entry vector OPS to STDERR. */
2318 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
2320 dump_ops_vector (stderr, ops);
2326 break_up_subtract_bb (ENTRY_BLOCK_PTR);
2327 reassociate_bb (EXIT_BLOCK_PTR);
2330 /* Initialize the reassociation pass. */
2338 int *bbs = XNEWVEC (int, last_basic_block + 1);
2340 /* Find the loops, so that we can prevent moving calculations in
2342 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
2344 memset (&reassociate_stats, 0, sizeof (reassociate_stats));
2346 operand_entry_pool = create_alloc_pool ("operand entry pool",
2347 sizeof (struct operand_entry), 30);
2348 next_operand_entry_id = 0;
2350 /* Reverse RPO (Reverse Post Order) will give us something where
2351 deeper loops come later. */
2352 pre_and_rev_post_order_compute (NULL, bbs, false);
2353 bb_rank = XCNEWVEC (long, last_basic_block + 1);
2354 operand_rank = pointer_map_create ();
2356 /* Give each argument a distinct rank. */
2357 for (param = DECL_ARGUMENTS (current_function_decl);
2359 param = DECL_CHAIN (param))
2361 if (gimple_default_def (cfun, param) != NULL)
2363 tree def = gimple_default_def (cfun, param);
2364 insert_operand_rank (def, ++rank);
2368 /* Give the chain decl a distinct rank. */
2369 if (cfun->static_chain_decl != NULL)
2371 tree def = gimple_default_def (cfun, cfun->static_chain_decl);
2373 insert_operand_rank (def, ++rank);
2376 /* Set up rank for each BB */
2377 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2378 bb_rank[bbs[i]] = ++rank << 16;
2381 calculate_dominance_info (CDI_POST_DOMINATORS);
2382 plus_negates = NULL;
2385 /* Cleanup after the reassociation pass, and print stats if
2391 statistics_counter_event (cfun, "Linearized",
2392 reassociate_stats.linearized);
2393 statistics_counter_event (cfun, "Constants eliminated",
2394 reassociate_stats.constants_eliminated);
2395 statistics_counter_event (cfun, "Ops eliminated",
2396 reassociate_stats.ops_eliminated);
2397 statistics_counter_event (cfun, "Statements rewritten",
2398 reassociate_stats.rewritten);
2400 pointer_map_destroy (operand_rank);
2401 free_alloc_pool (operand_entry_pool);
2403 VEC_free (tree, heap, plus_negates);
2404 free_dominance_info (CDI_POST_DOMINATORS);
2405 loop_optimizer_finalize ();
2408 /* Gate and execute functions for Reassociation. */
2411 execute_reassoc (void)
2416 repropagate_negates ();
2423 gate_tree_ssa_reassoc (void)
2425 return flag_tree_reassoc != 0;
2428 struct gimple_opt_pass pass_reassoc =
2432 "reassoc", /* name */
2433 gate_tree_ssa_reassoc, /* gate */
2434 execute_reassoc, /* execute */
2437 0, /* static_pass_number */
2438 TV_TREE_REASSOC, /* tv_id */
2439 PROP_cfg | PROP_ssa, /* properties_required */
2440 0, /* properties_provided */
2441 0, /* properties_destroyed */
2442 0, /* todo_flags_start */
2445 | TODO_ggc_collect /* todo_flags_finish */