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)
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/>. */
23 #include "coretypes.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"
35 #include "tree-iterator.h"
36 #include "tree-pass.h"
37 #include "alloc-pool.h"
39 #include "langhooks.h"
40 #include "pointer-set.h"
43 /* This is a simple global reassociation pass. It is, in part, based
44 on the LLVM pass of the same name (They do some things more/less
45 than we do, in different orders, etc).
47 It consists of five steps:
49 1. Breaking up subtract operations into addition + negate, where
50 it would promote the reassociation of adds.
52 2. Left linearization of the expression trees, so that (A+B)+(C+D)
53 becomes (((A+B)+C)+D), which is easier for us to rewrite later.
54 During linearization, we place the operands of the binary
55 expressions into a vector of operand_entry_t
57 3. Optimization of the operand lists, eliminating things like a +
60 4. Rewrite the expression trees we linearized and optimized so
61 they are in proper rank order.
63 5. Repropagate negates, as nothing else will clean it up ATM.
65 A bit of theory on #4, since nobody seems to write anything down
66 about why it makes sense to do it the way they do it:
68 We could do this much nicer theoretically, but don't (for reasons
69 explained after how to do it theoretically nice :P).
71 In order to promote the most redundancy elimination, you want
72 binary expressions whose operands are the same rank (or
73 preferably, the same value) exposed to the redundancy eliminator,
74 for possible elimination.
76 So the way to do this if we really cared, is to build the new op
77 tree from the leaves to the roots, merging as you go, and putting the
78 new op on the end of the worklist, until you are left with one
79 thing on the worklist.
81 IE if you have to rewrite the following set of operands (listed with
82 rank in parentheses), with opcode PLUS_EXPR:
84 a (1), b (1), c (1), d (2), e (2)
87 We start with our merge worklist empty, and the ops list with all of
90 You want to first merge all leaves of the same rank, as much as
93 So first build a binary op of
95 mergetmp = a + b, and put "mergetmp" on the merge worklist.
97 Because there is no three operand form of PLUS_EXPR, c is not going to
98 be exposed to redundancy elimination as a rank 1 operand.
100 So you might as well throw it on the merge worklist (you could also
101 consider it to now be a rank two operand, and merge it with d and e,
102 but in this case, you then have evicted e from a binary op. So at
103 least in this situation, you can't win.)
105 Then build a binary op of d + e
108 and put mergetmp2 on the merge worklist.
110 so merge worklist = {mergetmp, c, mergetmp2}
112 Continue building binary ops of these operations until you have only
113 one operation left on the worklist.
118 mergetmp3 = mergetmp + c
120 worklist = {mergetmp2, mergetmp3}
122 mergetmp4 = mergetmp2 + mergetmp3
124 worklist = {mergetmp4}
126 because we have one operation left, we can now just set the original
127 statement equal to the result of that operation.
129 This will at least expose a + b and d + e to redundancy elimination
130 as binary operations.
132 For extra points, you can reuse the old statements to build the
133 mergetmps, since you shouldn't run out.
135 So why don't we do this?
137 Because it's expensive, and rarely will help. Most trees we are
138 reassociating have 3 or less ops. If they have 2 ops, they already
139 will be written into a nice single binary op. If you have 3 ops, a
140 single simple check suffices to tell you whether the first two are of the
141 same rank. If so, you know to order it
144 newstmt = mergetmp + op3
148 newstmt = mergetmp + op1
150 If all three are of the same rank, you can't expose them all in a
151 single binary operator anyway, so the above is *still* the best you
154 Thus, this is what we do. When we have three ops left, we check to see
155 what order to put them in, and call it a day. As a nod to vector sum
156 reduction, we check if any of ops are a really a phi node that is a
157 destructive update for the associating op, and keep the destructive
158 update together for vector sum reduction recognition. */
165 int constants_eliminated
;
170 /* Operator, rank pair. */
171 typedef struct operand_entry
177 static alloc_pool operand_entry_pool
;
180 /* Starting rank number for a given basic block, so that we can rank
181 operations using unmovable instructions in that BB based on the bb
183 static long *bb_rank
;
185 /* Operand->rank hashtable. */
186 static struct pointer_map_t
*operand_rank
;
189 /* Look up the operand rank structure for expression E. */
192 find_operand_rank (tree e
)
194 void **slot
= pointer_map_contains (operand_rank
, e
);
195 return slot
? (long) *slot
: -1;
198 /* Insert {E,RANK} into the operand rank hashtable. */
201 insert_operand_rank (tree e
, long rank
)
204 gcc_assert (rank
> 0);
205 slot
= pointer_map_insert (operand_rank
, e
);
207 *slot
= (void *) rank
;
210 /* Given an expression E, return the rank of the expression. */
215 /* Constants have rank 0. */
216 if (is_gimple_min_invariant (e
))
219 /* SSA_NAME's have the rank of the expression they are the result
221 For globals and uninitialized values, the rank is 0.
222 For function arguments, use the pre-setup rank.
223 For PHI nodes, stores, asm statements, etc, we use the rank of
225 For simple operations, the rank is the maximum rank of any of
226 its operands, or the bb_rank, whichever is less.
227 I make no claims that this is optimal, however, it gives good
230 if (TREE_CODE (e
) == SSA_NAME
)
238 if (TREE_CODE (SSA_NAME_VAR (e
)) == PARM_DECL
239 && SSA_NAME_IS_DEFAULT_DEF (e
))
240 return find_operand_rank (e
);
242 stmt
= SSA_NAME_DEF_STMT (e
);
243 if (bb_for_stmt (stmt
) == NULL
)
246 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
247 || !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
))
248 return bb_rank
[bb_for_stmt (stmt
)->index
];
250 /* If we already have a rank for this expression, use that. */
251 rank
= find_operand_rank (e
);
255 /* Otherwise, find the maximum rank for the operands, or the bb
256 rank, whichever is less. */
258 maxrank
= bb_rank
[bb_for_stmt(stmt
)->index
];
259 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
260 n
= TREE_OPERAND_LENGTH (rhs
);
262 rank
= MAX (rank
, get_rank (rhs
));
267 && TREE_OPERAND (rhs
, i
)
270 rank
= MAX(rank
, get_rank (TREE_OPERAND (rhs
, i
)));
273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
275 fprintf (dump_file
, "Rank for ");
276 print_generic_expr (dump_file
, e
, 0);
277 fprintf (dump_file
, " is %ld\n", (rank
+ 1));
280 /* Note the rank in the hashtable so we don't recompute it. */
281 insert_operand_rank (e
, (rank
+ 1));
285 /* Globals, etc, are rank 0 */
289 DEF_VEC_P(operand_entry_t
);
290 DEF_VEC_ALLOC_P(operand_entry_t
, heap
);
292 /* We want integer ones to end up last no matter what, since they are
293 the ones we can do the most with. */
294 #define INTEGER_CONST_TYPE 1 << 3
295 #define FLOAT_CONST_TYPE 1 << 2
296 #define OTHER_CONST_TYPE 1 << 1
298 /* Classify an invariant tree into integer, float, or other, so that
299 we can sort them to be near other constants of the same type. */
301 constant_type (tree t
)
303 if (INTEGRAL_TYPE_P (TREE_TYPE (t
)))
304 return INTEGER_CONST_TYPE
;
305 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t
)))
306 return FLOAT_CONST_TYPE
;
308 return OTHER_CONST_TYPE
;
311 /* qsort comparison function to sort operand entries PA and PB by rank
312 so that the sorted array is ordered by rank in decreasing order. */
314 sort_by_operand_rank (const void *pa
, const void *pb
)
316 const operand_entry_t oea
= *(const operand_entry_t
*)pa
;
317 const operand_entry_t oeb
= *(const operand_entry_t
*)pb
;
319 /* It's nicer for optimize_expression if constants that are likely
320 to fold when added/multiplied//whatever are put next to each
321 other. Since all constants have rank 0, order them by type. */
322 if (oeb
->rank
== 0 && oea
->rank
== 0)
323 return constant_type (oeb
->op
) - constant_type (oea
->op
);
325 /* Lastly, make sure the versions that are the same go next to each
326 other. We use SSA_NAME_VERSION because it's stable. */
327 if ((oeb
->rank
- oea
->rank
== 0)
328 && TREE_CODE (oea
->op
) == SSA_NAME
329 && TREE_CODE (oeb
->op
) == SSA_NAME
)
330 return SSA_NAME_VERSION (oeb
->op
) - SSA_NAME_VERSION (oea
->op
);
332 return oeb
->rank
- oea
->rank
;
335 /* Add an operand entry to *OPS for the tree operand OP. */
338 add_to_ops_vec (VEC(operand_entry_t
, heap
) **ops
, tree op
)
340 operand_entry_t oe
= (operand_entry_t
) pool_alloc (operand_entry_pool
);
343 oe
->rank
= get_rank (op
);
344 VEC_safe_push (operand_entry_t
, heap
, *ops
, oe
);
347 /* Return true if STMT is reassociable operation containing a binary
348 operation with tree code CODE, and is inside LOOP. */
351 is_reassociable_op (tree stmt
, enum tree_code code
, struct loop
*loop
)
355 if (IS_EMPTY_STMT (stmt
))
358 bb
= bb_for_stmt (stmt
);
359 if (!flow_bb_inside_loop_p (loop
, bb
))
362 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
363 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == code
364 && has_single_use (GIMPLE_STMT_OPERAND (stmt
, 0)))
370 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
371 operand of the negate operation. Otherwise, return NULL. */
374 get_unary_op (tree name
, enum tree_code opcode
)
376 tree stmt
= SSA_NAME_DEF_STMT (name
);
379 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
382 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
383 if (TREE_CODE (rhs
) == opcode
)
384 return TREE_OPERAND (rhs
, 0);
388 /* If CURR and LAST are a pair of ops that OPCODE allows us to
389 eliminate through equivalences, do so, remove them from OPS, and
390 return true. Otherwise, return false. */
393 eliminate_duplicate_pair (enum tree_code opcode
,
394 VEC (operand_entry_t
, heap
) **ops
,
397 operand_entry_t curr
,
398 operand_entry_t last
)
401 /* If we have two of the same op, and the opcode is & |, min, or max,
402 we can eliminate one of them.
403 If we have two of the same op, and the opcode is ^, we can
404 eliminate both of them. */
406 if (last
&& last
->op
== curr
->op
)
414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
416 fprintf (dump_file
, "Equivalence: ");
417 print_generic_expr (dump_file
, curr
->op
, 0);
418 fprintf (dump_file
, " [&|minmax] ");
419 print_generic_expr (dump_file
, last
->op
, 0);
420 fprintf (dump_file
, " -> ");
421 print_generic_stmt (dump_file
, last
->op
, 0);
424 VEC_ordered_remove (operand_entry_t
, *ops
, i
);
425 reassociate_stats
.ops_eliminated
++;
430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
432 fprintf (dump_file
, "Equivalence: ");
433 print_generic_expr (dump_file
, curr
->op
, 0);
434 fprintf (dump_file
, " ^ ");
435 print_generic_expr (dump_file
, last
->op
, 0);
436 fprintf (dump_file
, " -> nothing\n");
439 reassociate_stats
.ops_eliminated
+= 2;
441 if (VEC_length (operand_entry_t
, *ops
) == 2)
443 VEC_free (operand_entry_t
, heap
, *ops
);
445 add_to_ops_vec (ops
, fold_convert (TREE_TYPE (last
->op
),
451 VEC_ordered_remove (operand_entry_t
, *ops
, i
-1);
452 VEC_ordered_remove (operand_entry_t
, *ops
, i
-1);
464 /* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
465 look in OPS for a corresponding positive operation to cancel it
466 out. If we find one, remove the other from OPS, replace
467 OPS[CURRINDEX] with 0, and return true. Otherwise, return
471 eliminate_plus_minus_pair (enum tree_code opcode
,
472 VEC (operand_entry_t
, heap
) **ops
,
473 unsigned int currindex
,
474 operand_entry_t curr
)
480 if (opcode
!= PLUS_EXPR
|| TREE_CODE (curr
->op
) != SSA_NAME
)
483 negateop
= get_unary_op (curr
->op
, NEGATE_EXPR
);
484 if (negateop
== NULL_TREE
)
487 /* Any non-negated version will have a rank that is one less than
488 the current rank. So once we hit those ranks, if we don't find
491 for (i
= currindex
+ 1;
492 VEC_iterate (operand_entry_t
, *ops
, i
, oe
)
493 && oe
->rank
>= curr
->rank
- 1 ;
496 if (oe
->op
== negateop
)
499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
501 fprintf (dump_file
, "Equivalence: ");
502 print_generic_expr (dump_file
, negateop
, 0);
503 fprintf (dump_file
, " + -");
504 print_generic_expr (dump_file
, oe
->op
, 0);
505 fprintf (dump_file
, " -> 0\n");
508 VEC_ordered_remove (operand_entry_t
, *ops
, i
);
509 add_to_ops_vec (ops
, fold_convert(TREE_TYPE (oe
->op
),
511 VEC_ordered_remove (operand_entry_t
, *ops
, currindex
);
512 reassociate_stats
.ops_eliminated
++;
521 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
522 bitwise not expression, look in OPS for a corresponding operand to
523 cancel it out. If we find one, remove the other from OPS, replace
524 OPS[CURRINDEX] with 0, and return true. Otherwise, return
528 eliminate_not_pairs (enum tree_code opcode
,
529 VEC (operand_entry_t
, heap
) **ops
,
530 unsigned int currindex
,
531 operand_entry_t curr
)
537 if ((opcode
!= BIT_IOR_EXPR
&& opcode
!= BIT_AND_EXPR
)
538 || TREE_CODE (curr
->op
) != SSA_NAME
)
541 notop
= get_unary_op (curr
->op
, BIT_NOT_EXPR
);
542 if (notop
== NULL_TREE
)
545 /* Any non-not version will have a rank that is one less than
546 the current rank. So once we hit those ranks, if we don't find
549 for (i
= currindex
+ 1;
550 VEC_iterate (operand_entry_t
, *ops
, i
, oe
)
551 && oe
->rank
>= curr
->rank
- 1;
556 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
558 fprintf (dump_file
, "Equivalence: ");
559 print_generic_expr (dump_file
, notop
, 0);
560 if (opcode
== BIT_AND_EXPR
)
561 fprintf (dump_file
, " & ~");
562 else if (opcode
== BIT_IOR_EXPR
)
563 fprintf (dump_file
, " | ~");
564 print_generic_expr (dump_file
, oe
->op
, 0);
565 if (opcode
== BIT_AND_EXPR
)
566 fprintf (dump_file
, " -> 0\n");
567 else if (opcode
== BIT_IOR_EXPR
)
568 fprintf (dump_file
, " -> -1\n");
571 if (opcode
== BIT_AND_EXPR
)
572 oe
->op
= fold_convert (TREE_TYPE (oe
->op
), integer_zero_node
);
573 else if (opcode
== BIT_IOR_EXPR
)
574 oe
->op
= build_low_bits_mask (TREE_TYPE (oe
->op
),
575 TYPE_PRECISION (TREE_TYPE (oe
->op
)));
577 reassociate_stats
.ops_eliminated
578 += VEC_length (operand_entry_t
, *ops
) - 1;
579 VEC_free (operand_entry_t
, heap
, *ops
);
581 VEC_safe_push (operand_entry_t
, heap
, *ops
, oe
);
589 /* Use constant value that may be present in OPS to try to eliminate
590 operands. Note that this function is only really used when we've
591 eliminated ops for other reasons, or merged constants. Across
592 single statements, fold already does all of this, plus more. There
593 is little point in duplicating logic, so I've only included the
594 identities that I could ever construct testcases to trigger. */
597 eliminate_using_constants (enum tree_code opcode
,
598 VEC(operand_entry_t
, heap
) **ops
)
600 operand_entry_t oelast
= VEC_last (operand_entry_t
, *ops
);
602 if (oelast
->rank
== 0 && INTEGRAL_TYPE_P (TREE_TYPE (oelast
->op
)))
607 if (integer_zerop (oelast
->op
))
609 if (VEC_length (operand_entry_t
, *ops
) != 1)
611 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
612 fprintf (dump_file
, "Found & 0, removing all other ops\n");
614 reassociate_stats
.ops_eliminated
615 += VEC_length (operand_entry_t
, *ops
) - 1;
617 VEC_free (operand_entry_t
, heap
, *ops
);
619 VEC_safe_push (operand_entry_t
, heap
, *ops
, oelast
);
623 else if (integer_all_onesp (oelast
->op
))
625 if (VEC_length (operand_entry_t
, *ops
) != 1)
627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
628 fprintf (dump_file
, "Found & -1, removing\n");
629 VEC_pop (operand_entry_t
, *ops
);
630 reassociate_stats
.ops_eliminated
++;
635 if (integer_all_onesp (oelast
->op
))
637 if (VEC_length (operand_entry_t
, *ops
) != 1)
639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
640 fprintf (dump_file
, "Found | -1, removing all other ops\n");
642 reassociate_stats
.ops_eliminated
643 += VEC_length (operand_entry_t
, *ops
) - 1;
645 VEC_free (operand_entry_t
, heap
, *ops
);
647 VEC_safe_push (operand_entry_t
, heap
, *ops
, oelast
);
651 else if (integer_zerop (oelast
->op
))
653 if (VEC_length (operand_entry_t
, *ops
) != 1)
655 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
656 fprintf (dump_file
, "Found | 0, removing\n");
657 VEC_pop (operand_entry_t
, *ops
);
658 reassociate_stats
.ops_eliminated
++;
663 if (integer_zerop (oelast
->op
))
665 if (VEC_length (operand_entry_t
, *ops
) != 1)
667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
668 fprintf (dump_file
, "Found * 0, removing all other ops\n");
670 reassociate_stats
.ops_eliminated
671 += VEC_length (operand_entry_t
, *ops
) - 1;
672 VEC_free (operand_entry_t
, heap
, *ops
);
674 VEC_safe_push (operand_entry_t
, heap
, *ops
, oelast
);
678 else if (integer_onep (oelast
->op
))
680 if (VEC_length (operand_entry_t
, *ops
) != 1)
682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
683 fprintf (dump_file
, "Found * 1, removing\n");
684 VEC_pop (operand_entry_t
, *ops
);
685 reassociate_stats
.ops_eliminated
++;
693 if (integer_zerop (oelast
->op
))
695 if (VEC_length (operand_entry_t
, *ops
) != 1)
697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
698 fprintf (dump_file
, "Found [|^+] 0, removing\n");
699 VEC_pop (operand_entry_t
, *ops
);
700 reassociate_stats
.ops_eliminated
++;
711 /* Perform various identities and other optimizations on the list of
712 operand entries, stored in OPS. The tree code for the binary
713 operation between all the operands is OPCODE. */
716 optimize_ops_list (enum tree_code opcode
,
717 VEC (operand_entry_t
, heap
) **ops
)
719 unsigned int length
= VEC_length (operand_entry_t
, *ops
);
722 operand_entry_t oelast
= NULL
;
723 bool iterate
= false;
728 oelast
= VEC_last (operand_entry_t
, *ops
);
730 /* If the last two are constants, pop the constants off, merge them
731 and try the next two. */
732 if (oelast
->rank
== 0 && is_gimple_min_invariant (oelast
->op
))
734 operand_entry_t oelm1
= VEC_index (operand_entry_t
, *ops
, length
- 2);
737 && is_gimple_min_invariant (oelm1
->op
)
738 && useless_type_conversion_p (TREE_TYPE (oelm1
->op
),
739 TREE_TYPE (oelast
->op
)))
741 tree folded
= fold_binary (opcode
, TREE_TYPE (oelm1
->op
),
742 oelm1
->op
, oelast
->op
);
744 if (folded
&& is_gimple_min_invariant (folded
))
746 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
747 fprintf (dump_file
, "Merging constants\n");
749 VEC_pop (operand_entry_t
, *ops
);
750 VEC_pop (operand_entry_t
, *ops
);
752 add_to_ops_vec (ops
, folded
);
753 reassociate_stats
.constants_eliminated
++;
755 optimize_ops_list (opcode
, ops
);
761 eliminate_using_constants (opcode
, ops
);
764 for (i
= 0; VEC_iterate (operand_entry_t
, *ops
, i
, oe
);)
768 if (eliminate_not_pairs (opcode
, ops
, i
, oe
))
770 if (eliminate_duplicate_pair (opcode
, ops
, &done
, i
, oe
, oelast
)
771 || (!done
&& eliminate_plus_minus_pair (opcode
, ops
, i
, oe
)))
783 length
= VEC_length (operand_entry_t
, *ops
);
784 oelast
= VEC_last (operand_entry_t
, *ops
);
787 optimize_ops_list (opcode
, ops
);
790 /* Return true if OPERAND is defined by a PHI node which uses the LHS
791 of STMT in it's operands. This is also known as a "destructive
792 update" operation. */
795 is_phi_for_stmt (tree stmt
, tree operand
)
798 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
802 if (TREE_CODE (operand
) != SSA_NAME
)
805 def_stmt
= SSA_NAME_DEF_STMT (operand
);
806 if (TREE_CODE (def_stmt
) != PHI_NODE
)
809 FOR_EACH_PHI_ARG (arg_p
, def_stmt
, i
, SSA_OP_USE
)
810 if (lhs
== USE_FROM_PTR (arg_p
))
815 /* Recursively rewrite our linearized statements so that the operators
816 match those in OPS[OPINDEX], putting the computation in rank
820 rewrite_expr_tree (tree stmt
, unsigned int opindex
,
821 VEC(operand_entry_t
, heap
) * ops
)
823 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
826 /* If we have three operands left, then we want to make sure the one
827 that gets the double binary op are the ones with the same rank.
829 The alternative we try is to see if this is a destructive
830 update style statement, which is like:
833 In that case, we want to use the destructive update form to
834 expose the possible vectorizer sum reduction opportunity.
835 In that case, the third operand will be the phi node.
837 We could, of course, try to be better as noted above, and do a
838 lot of work to try to find these opportunities in >3 operand
839 cases, but it is unlikely to be worth it. */
840 if (opindex
+ 3 == VEC_length (operand_entry_t
, ops
))
842 operand_entry_t oe1
, oe2
, oe3
;
844 oe1
= VEC_index (operand_entry_t
, ops
, opindex
);
845 oe2
= VEC_index (operand_entry_t
, ops
, opindex
+ 1);
846 oe3
= VEC_index (operand_entry_t
, ops
, opindex
+ 2);
848 if ((oe1
->rank
== oe2
->rank
849 && oe2
->rank
!= oe3
->rank
)
850 || (is_phi_for_stmt (stmt
, oe3
->op
)
851 && !is_phi_for_stmt (stmt
, oe1
->op
)
852 && !is_phi_for_stmt (stmt
, oe2
->op
)))
854 struct operand_entry temp
= *oe3
;
856 oe3
->rank
= oe1
->rank
;
858 oe1
->rank
= temp
.rank
;
860 else if ((oe1
->rank
== oe3
->rank
861 && oe2
->rank
!= oe3
->rank
)
862 || (is_phi_for_stmt (stmt
, oe2
->op
)
863 && !is_phi_for_stmt (stmt
, oe1
->op
)
864 && !is_phi_for_stmt (stmt
, oe3
->op
)))
866 struct operand_entry temp
= *oe2
;
868 oe2
->rank
= oe1
->rank
;
870 oe1
->rank
= temp
.rank
;
874 /* The final recursion case for this function is that you have
875 exactly two operations left.
876 If we had one exactly one op in the entire list to start with, we
877 would have never called this function, and the tail recursion
878 rewrites them one at a time. */
879 if (opindex
+ 2 == VEC_length (operand_entry_t
, ops
))
881 operand_entry_t oe1
, oe2
;
883 oe1
= VEC_index (operand_entry_t
, ops
, opindex
);
884 oe2
= VEC_index (operand_entry_t
, ops
, opindex
+ 1);
886 if (TREE_OPERAND (rhs
, 0) != oe1
->op
887 || TREE_OPERAND (rhs
, 1) != oe2
->op
)
890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
892 fprintf (dump_file
, "Transforming ");
893 print_generic_expr (dump_file
, rhs
, 0);
896 TREE_OPERAND (rhs
, 0) = oe1
->op
;
897 TREE_OPERAND (rhs
, 1) = oe2
->op
;
900 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
902 fprintf (dump_file
, " into ");
903 print_generic_stmt (dump_file
, rhs
, 0);
910 /* If we hit here, we should have 3 or more ops left. */
911 gcc_assert (opindex
+ 2 < VEC_length (operand_entry_t
, ops
));
913 /* Rewrite the next operator. */
914 oe
= VEC_index (operand_entry_t
, ops
, opindex
);
916 if (oe
->op
!= TREE_OPERAND (rhs
, 1))
919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
921 fprintf (dump_file
, "Transforming ");
922 print_generic_expr (dump_file
, rhs
, 0);
925 TREE_OPERAND (rhs
, 1) = oe
->op
;
928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
930 fprintf (dump_file
, " into ");
931 print_generic_stmt (dump_file
, rhs
, 0);
934 /* Recurse on the LHS of the binary operator, which is guaranteed to
935 be the non-leaf side. */
936 rewrite_expr_tree (SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0)),
940 /* Transform STMT, which is really (A +B) + (C + D) into the left
941 linear form, ((A+B)+C)+D.
942 Recurse on D if necessary. */
945 linearize_expr (tree stmt
)
947 block_stmt_iterator bsinow
, bsirhs
;
948 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
949 enum tree_code rhscode
= TREE_CODE (rhs
);
950 tree binrhs
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 1));
951 tree binlhs
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
952 tree newbinrhs
= NULL_TREE
;
953 struct loop
*loop
= loop_containing_stmt (stmt
);
955 gcc_assert (is_reassociable_op (binlhs
, TREE_CODE (rhs
), loop
)
956 && is_reassociable_op (binrhs
, TREE_CODE (rhs
), loop
));
958 bsinow
= bsi_for_stmt (stmt
);
959 bsirhs
= bsi_for_stmt (binrhs
);
960 bsi_move_before (&bsirhs
, &bsinow
);
962 TREE_OPERAND (rhs
, 1) = TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs
, 1), 0);
963 if (TREE_CODE (TREE_OPERAND (rhs
, 1)) == SSA_NAME
)
964 newbinrhs
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 1));
965 TREE_OPERAND (GIMPLE_STMT_OPERAND (binrhs
, 1), 0)
966 = GIMPLE_STMT_OPERAND (binlhs
, 0);
967 TREE_OPERAND (rhs
, 0) = GIMPLE_STMT_OPERAND (binrhs
, 0);
969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
971 fprintf (dump_file
, "Linearized: ");
972 print_generic_stmt (dump_file
, rhs
, 0);
975 reassociate_stats
.linearized
++;
976 update_stmt (binrhs
);
977 update_stmt (binlhs
);
979 TREE_VISITED (binrhs
) = 1;
980 TREE_VISITED (binlhs
) = 1;
981 TREE_VISITED (stmt
) = 1;
983 /* Tail recurse on the new rhs if it still needs reassociation. */
984 if (newbinrhs
&& is_reassociable_op (newbinrhs
, rhscode
, loop
))
985 linearize_expr (stmt
);
988 /* If LHS has a single immediate use that is a GIMPLE_MODIFY_STMT, return
989 it. Otherwise, return NULL. */
992 get_single_immediate_use (tree lhs
)
994 use_operand_p immuse
;
997 if (TREE_CODE (lhs
) == SSA_NAME
998 && single_imm_use (lhs
, &immuse
, &immusestmt
))
1000 if (TREE_CODE (immusestmt
) == RETURN_EXPR
)
1001 immusestmt
= TREE_OPERAND (immusestmt
, 0);
1002 if (TREE_CODE (immusestmt
) == GIMPLE_MODIFY_STMT
)
1007 static VEC(tree
, heap
) *broken_up_subtracts
;
1010 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
1011 representing the negated value. Insertions of any necessary
1012 instructions go before BSI.
1013 This function is recursive in that, if you hand it "a_5" as the
1014 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1015 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */
1018 negate_value (tree tonegate
, block_stmt_iterator
*bsi
)
1020 tree negatedef
= tonegate
;
1021 tree resultofnegate
;
1023 if (TREE_CODE (tonegate
) == SSA_NAME
)
1024 negatedef
= SSA_NAME_DEF_STMT (tonegate
);
1026 /* If we are trying to negate a name, defined by an add, negate the
1027 add operands instead. */
1028 if (TREE_CODE (tonegate
) == SSA_NAME
1029 && TREE_CODE (negatedef
) == GIMPLE_MODIFY_STMT
1030 && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef
, 0)) == SSA_NAME
1031 && has_single_use (GIMPLE_STMT_OPERAND (negatedef
, 0))
1032 && TREE_CODE (GIMPLE_STMT_OPERAND (negatedef
, 1)) == PLUS_EXPR
)
1034 block_stmt_iterator bsi
;
1035 tree binop
= GIMPLE_STMT_OPERAND (negatedef
, 1);
1037 bsi
= bsi_for_stmt (negatedef
);
1038 TREE_OPERAND (binop
, 0) = negate_value (TREE_OPERAND (binop
, 0),
1040 bsi
= bsi_for_stmt (negatedef
);
1041 TREE_OPERAND (binop
, 1) = negate_value (TREE_OPERAND (binop
, 1),
1043 update_stmt (negatedef
);
1044 return GIMPLE_STMT_OPERAND (negatedef
, 0);
1047 tonegate
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (tonegate
), tonegate
);
1048 resultofnegate
= force_gimple_operand_bsi (bsi
, tonegate
, true,
1049 NULL_TREE
, true, BSI_SAME_STMT
);
1050 VEC_safe_push (tree
, heap
, broken_up_subtracts
, resultofnegate
);
1051 return resultofnegate
;
1055 /* Return true if we should break up the subtract in STMT into an add
1056 with negate. This is true when we the subtract operands are really
1057 adds, or the subtract itself is used in an add expression. In
1058 either case, breaking up the subtract into an add with negate
1059 exposes the adds to reassociation. */
1062 should_break_up_subtract (tree stmt
)
1065 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1066 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1067 tree binlhs
= TREE_OPERAND (rhs
, 0);
1068 tree binrhs
= TREE_OPERAND (rhs
, 1);
1070 struct loop
*loop
= loop_containing_stmt (stmt
);
1072 if (TREE_CODE (binlhs
) == SSA_NAME
1073 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs
), PLUS_EXPR
, loop
))
1076 if (TREE_CODE (binrhs
) == SSA_NAME
1077 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs
), PLUS_EXPR
, loop
))
1080 if (TREE_CODE (lhs
) == SSA_NAME
1081 && (immusestmt
= get_single_immediate_use (lhs
))
1082 && TREE_CODE (GIMPLE_STMT_OPERAND (immusestmt
, 1)) == PLUS_EXPR
)
1088 /* Transform STMT from A - B into A + -B. */
1091 break_up_subtract (tree stmt
, block_stmt_iterator
*bsi
)
1093 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1097 fprintf (dump_file
, "Breaking up subtract ");
1098 print_generic_stmt (dump_file
, stmt
, 0);
1101 TREE_SET_CODE (GIMPLE_STMT_OPERAND (stmt
, 1), PLUS_EXPR
);
1102 TREE_OPERAND (rhs
, 1) = negate_value (TREE_OPERAND (rhs
, 1), bsi
);
1107 /* Recursively linearize a binary expression that is the RHS of STMT.
1108 Place the operands of the expression tree in the vector named OPS. */
1111 linearize_expr_tree (VEC(operand_entry_t
, heap
) **ops
, tree stmt
)
1113 block_stmt_iterator bsinow
, bsilhs
;
1114 tree rhs
= GENERIC_TREE_OPERAND (stmt
, 1);
1115 tree binrhs
= TREE_OPERAND (rhs
, 1);
1116 tree binlhs
= TREE_OPERAND (rhs
, 0);
1117 tree binlhsdef
, binrhsdef
;
1118 bool binlhsisreassoc
= false;
1119 bool binrhsisreassoc
= false;
1120 enum tree_code rhscode
= TREE_CODE (rhs
);
1121 struct loop
*loop
= loop_containing_stmt (stmt
);
1123 TREE_VISITED (stmt
) = 1;
1125 if (TREE_CODE (binlhs
) == SSA_NAME
)
1127 binlhsdef
= SSA_NAME_DEF_STMT (binlhs
);
1128 binlhsisreassoc
= is_reassociable_op (binlhsdef
, rhscode
, loop
);
1131 if (TREE_CODE (binrhs
) == SSA_NAME
)
1133 binrhsdef
= SSA_NAME_DEF_STMT (binrhs
);
1134 binrhsisreassoc
= is_reassociable_op (binrhsdef
, rhscode
, loop
);
1137 /* If the LHS is not reassociable, but the RHS is, we need to swap
1138 them. If neither is reassociable, there is nothing we can do, so
1139 just put them in the ops vector. If the LHS is reassociable,
1140 linearize it. If both are reassociable, then linearize the RHS
1143 if (!binlhsisreassoc
)
1147 if (!binrhsisreassoc
)
1149 add_to_ops_vec (ops
, binrhs
);
1150 add_to_ops_vec (ops
, binlhs
);
1154 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1156 fprintf (dump_file
, "swapping operands of ");
1157 print_generic_expr (dump_file
, stmt
, 0);
1160 swap_tree_operands (stmt
, &TREE_OPERAND (rhs
, 0),
1161 &TREE_OPERAND (rhs
, 1));
1164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1166 fprintf (dump_file
, " is now ");
1167 print_generic_stmt (dump_file
, stmt
, 0);
1170 /* We want to make it so the lhs is always the reassociative op,
1176 else if (binrhsisreassoc
)
1178 linearize_expr (stmt
);
1179 gcc_assert (rhs
== GIMPLE_STMT_OPERAND (stmt
, 1));
1180 binlhs
= TREE_OPERAND (rhs
, 0);
1181 binrhs
= TREE_OPERAND (rhs
, 1);
1184 gcc_assert (TREE_CODE (binrhs
) != SSA_NAME
1185 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs
),
1187 bsinow
= bsi_for_stmt (stmt
);
1188 bsilhs
= bsi_for_stmt (SSA_NAME_DEF_STMT (binlhs
));
1189 bsi_move_before (&bsilhs
, &bsinow
);
1190 linearize_expr_tree (ops
, SSA_NAME_DEF_STMT (binlhs
));
1191 add_to_ops_vec (ops
, binrhs
);
1194 /* Repropagate the negates back into subtracts, since no other pass
1195 currently does it. */
1198 repropagate_negates (void)
1203 for (i
= 0; VEC_iterate (tree
, broken_up_subtracts
, i
, negate
); i
++)
1205 tree user
= get_single_immediate_use (negate
);
1207 /* The negate operand can be either operand of a PLUS_EXPR
1208 (it can be the LHS if the RHS is a constant for example).
1210 Force the negate operand to the RHS of the PLUS_EXPR, then
1211 transform the PLUS_EXPR into a MINUS_EXPR. */
1213 && TREE_CODE (user
) == GIMPLE_MODIFY_STMT
1214 && TREE_CODE (GIMPLE_STMT_OPERAND (user
, 1)) == PLUS_EXPR
)
1216 tree rhs
= GIMPLE_STMT_OPERAND (user
, 1);
1218 /* If the negated operand appears on the LHS of the
1219 PLUS_EXPR, exchange the operands of the PLUS_EXPR
1220 to force the negated operand to the RHS of the PLUS_EXPR. */
1221 if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user
, 1), 0) == negate
)
1223 tree temp
= TREE_OPERAND (rhs
, 0);
1224 TREE_OPERAND (rhs
, 0) = TREE_OPERAND (rhs
, 1);
1225 TREE_OPERAND (rhs
, 1) = temp
;
1228 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1229 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */
1230 if (TREE_OPERAND (GIMPLE_STMT_OPERAND (user
, 1), 1) == negate
)
1232 TREE_SET_CODE (rhs
, MINUS_EXPR
);
1233 TREE_OPERAND (rhs
, 1) = get_unary_op (negate
, NEGATE_EXPR
);
1240 /* Break up subtract operations in block BB.
1242 We do this top down because we don't know whether the subtract is
1243 part of a possible chain of reassociation except at the top.
1252 we want to break up k = t - q, but we won't until we've transformed q
1253 = b - r, which won't be broken up until we transform b = c - d. */
1256 break_up_subtract_bb (basic_block bb
)
1258 block_stmt_iterator bsi
;
1261 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1263 tree stmt
= bsi_stmt (bsi
);
1265 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1267 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1268 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1270 TREE_VISITED (stmt
) = 0;
1271 /* If associative-math we can do reassociation for
1272 non-integral types. Or, we can do reassociation for
1273 non-saturating fixed-point types. */
1274 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1275 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
1276 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs
))
1277 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs
))
1278 || !flag_associative_math
)
1279 && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs
))
1280 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs
))))
1283 /* Check for a subtract used only in an addition. If this
1284 is the case, transform it into add of a negate for better
1285 reassociation. IE transform C = A-B into C = A + -B if C
1286 is only used in an addition. */
1287 if (TREE_CODE (rhs
) == MINUS_EXPR
)
1288 if (should_break_up_subtract (stmt
))
1289 break_up_subtract (stmt
, &bsi
);
1292 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
1294 son
= next_dom_son (CDI_DOMINATORS
, son
))
1295 break_up_subtract_bb (son
);
1298 /* Reassociate expressions in basic block BB and its post-dominator as
1302 reassociate_bb (basic_block bb
)
1304 block_stmt_iterator bsi
;
1307 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
1309 tree stmt
= bsi_stmt (bsi
);
1311 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1313 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1314 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1316 /* If this was part of an already processed tree, we don't
1317 need to touch it again. */
1318 if (TREE_VISITED (stmt
))
1321 /* If associative-math we can do reassociation for
1322 non-integral types. Or, we can do reassociation for
1323 non-saturating fixed-point types. */
1324 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1325 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
1326 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs
))
1327 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs
))
1328 || !flag_associative_math
)
1329 && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (rhs
))
1330 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(lhs
))))
1333 if (associative_tree_code (TREE_CODE (rhs
)))
1335 VEC(operand_entry_t
, heap
) *ops
= NULL
;
1337 /* There may be no immediate uses left by the time we
1338 get here because we may have eliminated them all. */
1339 if (TREE_CODE (lhs
) == SSA_NAME
&& has_zero_uses (lhs
))
1342 TREE_VISITED (stmt
) = 1;
1343 linearize_expr_tree (&ops
, stmt
);
1344 qsort (VEC_address (operand_entry_t
, ops
),
1345 VEC_length (operand_entry_t
, ops
),
1346 sizeof (operand_entry_t
),
1347 sort_by_operand_rank
);
1348 optimize_ops_list (TREE_CODE (rhs
), &ops
);
1350 if (VEC_length (operand_entry_t
, ops
) == 1)
1352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1354 fprintf (dump_file
, "Transforming ");
1355 print_generic_expr (dump_file
, rhs
, 0);
1357 GIMPLE_STMT_OPERAND (stmt
, 1)
1358 = VEC_last (operand_entry_t
, ops
)->op
;
1361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1363 fprintf (dump_file
, " into ");
1364 print_generic_stmt (dump_file
,
1365 GIMPLE_STMT_OPERAND (stmt
, 1), 0);
1370 rewrite_expr_tree (stmt
, 0, ops
);
1373 VEC_free (operand_entry_t
, heap
, ops
);
1377 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
1379 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1380 reassociate_bb (son
);
1383 void dump_ops_vector (FILE *file
, VEC (operand_entry_t
, heap
) *ops
);
1384 void debug_ops_vector (VEC (operand_entry_t
, heap
) *ops
);
1386 /* Dump the operand entry vector OPS to FILE. */
1389 dump_ops_vector (FILE *file
, VEC (operand_entry_t
, heap
) *ops
)
1394 for (i
= 0; VEC_iterate (operand_entry_t
, ops
, i
, oe
); i
++)
1396 fprintf (file
, "Op %d -> rank: %d, tree: ", i
, oe
->rank
);
1397 print_generic_stmt (file
, oe
->op
, 0);
1401 /* Dump the operand entry vector OPS to STDERR. */
1404 debug_ops_vector (VEC (operand_entry_t
, heap
) *ops
)
1406 dump_ops_vector (stderr
, ops
);
1412 break_up_subtract_bb (ENTRY_BLOCK_PTR
);
1413 reassociate_bb (EXIT_BLOCK_PTR
);
1416 /* Initialize the reassociation pass. */
1424 int *bbs
= XNEWVEC (int, last_basic_block
+ 1);
1426 /* Find the loops, so that we can prevent moving calculations in
1428 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
1430 memset (&reassociate_stats
, 0, sizeof (reassociate_stats
));
1432 operand_entry_pool
= create_alloc_pool ("operand entry pool",
1433 sizeof (struct operand_entry
), 30);
1435 /* Reverse RPO (Reverse Post Order) will give us something where
1436 deeper loops come later. */
1437 pre_and_rev_post_order_compute (NULL
, bbs
, false);
1438 bb_rank
= XCNEWVEC (long, last_basic_block
+ 1);
1439 operand_rank
= pointer_map_create ();
1441 /* Give each argument a distinct rank. */
1442 for (param
= DECL_ARGUMENTS (current_function_decl
);
1444 param
= TREE_CHAIN (param
))
1446 if (gimple_default_def (cfun
, param
) != NULL
)
1448 tree def
= gimple_default_def (cfun
, param
);
1449 insert_operand_rank (def
, ++rank
);
1453 /* Give the chain decl a distinct rank. */
1454 if (cfun
->static_chain_decl
!= NULL
)
1456 tree def
= gimple_default_def (cfun
, cfun
->static_chain_decl
);
1458 insert_operand_rank (def
, ++rank
);
1461 /* Set up rank for each BB */
1462 for (i
= 0; i
< n_basic_blocks
- NUM_FIXED_BLOCKS
; i
++)
1463 bb_rank
[bbs
[i
]] = ++rank
<< 16;
1466 calculate_dominance_info (CDI_POST_DOMINATORS
);
1467 broken_up_subtracts
= NULL
;
1470 /* Cleanup after the reassociation pass, and print stats if
1476 if (dump_file
&& (dump_flags
& TDF_STATS
))
1478 fprintf (dump_file
, "Reassociation stats:\n");
1479 fprintf (dump_file
, "Linearized: %d\n",
1480 reassociate_stats
.linearized
);
1481 fprintf (dump_file
, "Constants eliminated: %d\n",
1482 reassociate_stats
.constants_eliminated
);
1483 fprintf (dump_file
, "Ops eliminated: %d\n",
1484 reassociate_stats
.ops_eliminated
);
1485 fprintf (dump_file
, "Statements rewritten: %d\n",
1486 reassociate_stats
.rewritten
);
1489 pointer_map_destroy (operand_rank
);
1490 free_alloc_pool (operand_entry_pool
);
1492 VEC_free (tree
, heap
, broken_up_subtracts
);
1493 free_dominance_info (CDI_POST_DOMINATORS
);
1494 loop_optimizer_finalize ();
1497 /* Gate and execute functions for Reassociation. */
1500 execute_reassoc (void)
1505 repropagate_negates ();
1512 gate_tree_ssa_reassoc (void)
1514 return flag_tree_reassoc
!= 0;
1517 struct tree_opt_pass pass_reassoc
=
1519 "reassoc", /* name */
1520 gate_tree_ssa_reassoc
, /* gate */
1521 execute_reassoc
, /* execute */
1524 0, /* static_pass_number */
1525 TV_TREE_REASSOC
, /* tv_id */
1526 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
1527 0, /* properties_provided */
1528 0, /* properties_destroyed */
1529 0, /* todo_flags_start */
1530 TODO_dump_func
| TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */