1 /* Reassociation for trees.
2 Copyright (C) 2005, 2007, 2008 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"
27 #include "basic-block.h"
28 #include "diagnostic.h"
29 #include "tree-inline.h"
30 #include "tree-flow.h"
32 #include "tree-dump.h"
34 #include "tree-iterator.h"
35 #include "tree-pass.h"
36 #include "alloc-pool.h"
38 #include "langhooks.h"
39 #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 the ops are 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)
236 if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
237 && SSA_NAME_IS_DEFAULT_DEF (e))
238 return find_operand_rank (e);
240 stmt = SSA_NAME_DEF_STMT (e);
241 if (gimple_bb (stmt) == NULL)
244 if (!is_gimple_assign (stmt)
245 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
246 return bb_rank[gimple_bb (stmt)->index];
248 /* If we already have a rank for this expression, use that. */
249 rank = find_operand_rank (e);
253 /* Otherwise, find the maximum rank for the operands, or the bb
254 rank, whichever is less. */
256 maxrank = bb_rank[gimple_bb(stmt)->index];
257 if (gimple_assign_single_p (stmt))
259 tree rhs = gimple_assign_rhs1 (stmt);
260 n = TREE_OPERAND_LENGTH (rhs);
262 rank = MAX (rank, get_rank (rhs));
266 i < n && TREE_OPERAND (rhs, i) && rank != maxrank; i++)
267 rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
272 n = gimple_num_ops (stmt);
273 for (i = 1; i < n && rank != maxrank; i++)
275 gcc_assert (gimple_op (stmt, i));
276 rank = MAX(rank, get_rank (gimple_op (stmt, i)));
280 if (dump_file && (dump_flags & TDF_DETAILS))
282 fprintf (dump_file, "Rank for ");
283 print_generic_expr (dump_file, e, 0);
284 fprintf (dump_file, " is %ld\n", (rank + 1));
287 /* Note the rank in the hashtable so we don't recompute it. */
288 insert_operand_rank (e, (rank + 1));
292 /* Globals, etc, are rank 0 */
296 DEF_VEC_P(operand_entry_t);
297 DEF_VEC_ALLOC_P(operand_entry_t, heap);
299 /* We want integer ones to end up last no matter what, since they are
300 the ones we can do the most with. */
301 #define INTEGER_CONST_TYPE 1 << 3
302 #define FLOAT_CONST_TYPE 1 << 2
303 #define OTHER_CONST_TYPE 1 << 1
305 /* Classify an invariant tree into integer, float, or other, so that
306 we can sort them to be near other constants of the same type. */
308 constant_type (tree t)
310 if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
311 return INTEGER_CONST_TYPE;
312 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t)))
313 return FLOAT_CONST_TYPE;
315 return OTHER_CONST_TYPE;
318 /* qsort comparison function to sort operand entries PA and PB by rank
319 so that the sorted array is ordered by rank in decreasing order. */
321 sort_by_operand_rank (const void *pa, const void *pb)
323 const operand_entry_t oea = *(const operand_entry_t *)pa;
324 const operand_entry_t oeb = *(const operand_entry_t *)pb;
326 /* It's nicer for optimize_expression if constants that are likely
327 to fold when added/multiplied//whatever are put next to each
328 other. Since all constants have rank 0, order them by type. */
329 if (oeb->rank == 0 && oea->rank == 0)
330 return constant_type (oeb->op) - constant_type (oea->op);
332 /* Lastly, make sure the versions that are the same go next to each
333 other. We use SSA_NAME_VERSION because it's stable. */
334 if ((oeb->rank - oea->rank == 0)
335 && TREE_CODE (oea->op) == SSA_NAME
336 && TREE_CODE (oeb->op) == SSA_NAME)
337 return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
339 return oeb->rank - oea->rank;
342 /* Add an operand entry to *OPS for the tree operand OP. */
345 add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
347 operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
350 oe->rank = get_rank (op);
351 VEC_safe_push (operand_entry_t, heap, *ops, oe);
354 /* Return true if STMT is reassociable operation containing a binary
355 operation with tree code CODE, and is inside LOOP. */
358 is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop)
360 basic_block bb = gimple_bb (stmt);
362 if (gimple_bb (stmt) == NULL)
365 if (!flow_bb_inside_loop_p (loop, bb))
368 if (is_gimple_assign (stmt)
369 && gimple_assign_rhs_code (stmt) == code
370 && has_single_use (gimple_assign_lhs (stmt)))
377 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
378 operand of the negate operation. Otherwise, return NULL. */
381 get_unary_op (tree name, enum tree_code opcode)
383 gimple stmt = SSA_NAME_DEF_STMT (name);
385 if (!is_gimple_assign (stmt))
388 if (gimple_assign_rhs_code (stmt) == opcode)
389 return gimple_assign_rhs1 (stmt);
393 /* If CURR and LAST are a pair of ops that OPCODE allows us to
394 eliminate through equivalences, do so, remove them from OPS, and
395 return true. Otherwise, return false. */
398 eliminate_duplicate_pair (enum tree_code opcode,
399 VEC (operand_entry_t, heap) **ops,
402 operand_entry_t curr,
403 operand_entry_t last)
406 /* If we have two of the same op, and the opcode is & |, min, or max,
407 we can eliminate one of them.
408 If we have two of the same op, and the opcode is ^, we can
409 eliminate both of them. */
411 if (last && last->op == curr->op)
419 if (dump_file && (dump_flags & TDF_DETAILS))
421 fprintf (dump_file, "Equivalence: ");
422 print_generic_expr (dump_file, curr->op, 0);
423 fprintf (dump_file, " [&|minmax] ");
424 print_generic_expr (dump_file, last->op, 0);
425 fprintf (dump_file, " -> ");
426 print_generic_stmt (dump_file, last->op, 0);
429 VEC_ordered_remove (operand_entry_t, *ops, i);
430 reassociate_stats.ops_eliminated ++;
435 if (dump_file && (dump_flags & TDF_DETAILS))
437 fprintf (dump_file, "Equivalence: ");
438 print_generic_expr (dump_file, curr->op, 0);
439 fprintf (dump_file, " ^ ");
440 print_generic_expr (dump_file, last->op, 0);
441 fprintf (dump_file, " -> nothing\n");
444 reassociate_stats.ops_eliminated += 2;
446 if (VEC_length (operand_entry_t, *ops) == 2)
448 VEC_free (operand_entry_t, heap, *ops);
450 add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op),
456 VEC_ordered_remove (operand_entry_t, *ops, i-1);
457 VEC_ordered_remove (operand_entry_t, *ops, i-1);
469 /* If OPCODE is PLUS_EXPR, CURR->OP is really a negate expression,
470 look in OPS for a corresponding positive operation to cancel it
471 out. If we find one, remove the other from OPS, replace
472 OPS[CURRINDEX] with 0, and return true. Otherwise, return
476 eliminate_plus_minus_pair (enum tree_code opcode,
477 VEC (operand_entry_t, heap) **ops,
478 unsigned int currindex,
479 operand_entry_t curr)
485 if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
488 negateop = get_unary_op (curr->op, NEGATE_EXPR);
489 if (negateop == NULL_TREE)
492 /* Any non-negated version will have a rank that is one less than
493 the current rank. So once we hit those ranks, if we don't find
496 for (i = currindex + 1;
497 VEC_iterate (operand_entry_t, *ops, i, oe)
498 && oe->rank >= curr->rank - 1 ;
501 if (oe->op == negateop)
504 if (dump_file && (dump_flags & TDF_DETAILS))
506 fprintf (dump_file, "Equivalence: ");
507 print_generic_expr (dump_file, negateop, 0);
508 fprintf (dump_file, " + -");
509 print_generic_expr (dump_file, oe->op, 0);
510 fprintf (dump_file, " -> 0\n");
513 VEC_ordered_remove (operand_entry_t, *ops, i);
514 add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op),
516 VEC_ordered_remove (operand_entry_t, *ops, currindex);
517 reassociate_stats.ops_eliminated ++;
526 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
527 bitwise not expression, look in OPS for a corresponding operand to
528 cancel it out. If we find one, remove the other from OPS, replace
529 OPS[CURRINDEX] with 0, and return true. Otherwise, return
533 eliminate_not_pairs (enum tree_code opcode,
534 VEC (operand_entry_t, heap) **ops,
535 unsigned int currindex,
536 operand_entry_t curr)
542 if ((opcode != BIT_IOR_EXPR && opcode != BIT_AND_EXPR)
543 || TREE_CODE (curr->op) != SSA_NAME)
546 notop = get_unary_op (curr->op, BIT_NOT_EXPR);
547 if (notop == NULL_TREE)
550 /* Any non-not version will have a rank that is one less than
551 the current rank. So once we hit those ranks, if we don't find
554 for (i = currindex + 1;
555 VEC_iterate (operand_entry_t, *ops, i, oe)
556 && oe->rank >= curr->rank - 1;
561 if (dump_file && (dump_flags & TDF_DETAILS))
563 fprintf (dump_file, "Equivalence: ");
564 print_generic_expr (dump_file, notop, 0);
565 if (opcode == BIT_AND_EXPR)
566 fprintf (dump_file, " & ~");
567 else if (opcode == BIT_IOR_EXPR)
568 fprintf (dump_file, " | ~");
569 print_generic_expr (dump_file, oe->op, 0);
570 if (opcode == BIT_AND_EXPR)
571 fprintf (dump_file, " -> 0\n");
572 else if (opcode == BIT_IOR_EXPR)
573 fprintf (dump_file, " -> -1\n");
576 if (opcode == BIT_AND_EXPR)
577 oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node);
578 else if (opcode == BIT_IOR_EXPR)
579 oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
580 TYPE_PRECISION (TREE_TYPE (oe->op)));
582 reassociate_stats.ops_eliminated
583 += VEC_length (operand_entry_t, *ops) - 1;
584 VEC_free (operand_entry_t, heap, *ops);
586 VEC_safe_push (operand_entry_t, heap, *ops, oe);
594 /* Use constant value that may be present in OPS to try to eliminate
595 operands. Note that this function is only really used when we've
596 eliminated ops for other reasons, or merged constants. Across
597 single statements, fold already does all of this, plus more. There
598 is little point in duplicating logic, so I've only included the
599 identities that I could ever construct testcases to trigger. */
602 eliminate_using_constants (enum tree_code opcode,
603 VEC(operand_entry_t, heap) **ops)
605 operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
606 tree type = TREE_TYPE (oelast->op);
608 if (oelast->rank == 0
609 && (INTEGRAL_TYPE_P (type) || FLOAT_TYPE_P (type)))
614 if (integer_zerop (oelast->op))
616 if (VEC_length (operand_entry_t, *ops) != 1)
618 if (dump_file && (dump_flags & TDF_DETAILS))
619 fprintf (dump_file, "Found & 0, removing all other ops\n");
621 reassociate_stats.ops_eliminated
622 += VEC_length (operand_entry_t, *ops) - 1;
624 VEC_free (operand_entry_t, heap, *ops);
626 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
630 else if (integer_all_onesp (oelast->op))
632 if (VEC_length (operand_entry_t, *ops) != 1)
634 if (dump_file && (dump_flags & TDF_DETAILS))
635 fprintf (dump_file, "Found & -1, removing\n");
636 VEC_pop (operand_entry_t, *ops);
637 reassociate_stats.ops_eliminated++;
642 if (integer_all_onesp (oelast->op))
644 if (VEC_length (operand_entry_t, *ops) != 1)
646 if (dump_file && (dump_flags & TDF_DETAILS))
647 fprintf (dump_file, "Found | -1, removing all other ops\n");
649 reassociate_stats.ops_eliminated
650 += VEC_length (operand_entry_t, *ops) - 1;
652 VEC_free (operand_entry_t, heap, *ops);
654 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
658 else if (integer_zerop (oelast->op))
660 if (VEC_length (operand_entry_t, *ops) != 1)
662 if (dump_file && (dump_flags & TDF_DETAILS))
663 fprintf (dump_file, "Found | 0, removing\n");
664 VEC_pop (operand_entry_t, *ops);
665 reassociate_stats.ops_eliminated++;
670 if (integer_zerop (oelast->op)
671 || (FLOAT_TYPE_P (type)
672 && !HONOR_NANS (TYPE_MODE (type))
673 && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
674 && real_zerop (oelast->op)))
676 if (VEC_length (operand_entry_t, *ops) != 1)
678 if (dump_file && (dump_flags & TDF_DETAILS))
679 fprintf (dump_file, "Found * 0, removing all other ops\n");
681 reassociate_stats.ops_eliminated
682 += VEC_length (operand_entry_t, *ops) - 1;
683 VEC_free (operand_entry_t, heap, *ops);
685 VEC_safe_push (operand_entry_t, heap, *ops, oelast);
689 else if (integer_onep (oelast->op)
690 || (FLOAT_TYPE_P (type)
691 && !HONOR_SNANS (TYPE_MODE (type))
692 && real_onep (oelast->op)))
694 if (VEC_length (operand_entry_t, *ops) != 1)
696 if (dump_file && (dump_flags & TDF_DETAILS))
697 fprintf (dump_file, "Found * 1, removing\n");
698 VEC_pop (operand_entry_t, *ops);
699 reassociate_stats.ops_eliminated++;
707 if (integer_zerop (oelast->op)
708 || (FLOAT_TYPE_P (type)
709 && (opcode == PLUS_EXPR || opcode == MINUS_EXPR)
710 && fold_real_zero_addition_p (type, oelast->op,
711 opcode == MINUS_EXPR)))
713 if (VEC_length (operand_entry_t, *ops) != 1)
715 if (dump_file && (dump_flags & TDF_DETAILS))
716 fprintf (dump_file, "Found [|^+] 0, removing\n");
717 VEC_pop (operand_entry_t, *ops);
718 reassociate_stats.ops_eliminated++;
730 static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
733 /* Structure for tracking and counting operands. */
734 typedef struct oecount_s {
736 enum tree_code oecode;
741 DEF_VEC_ALLOC_O(oecount,heap);
743 /* The heap for the oecount hashtable and the sorted list of operands. */
744 static VEC (oecount, heap) *cvec;
746 /* Hash function for oecount. */
749 oecount_hash (const void *p)
751 const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42);
752 return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
755 /* Comparison function for oecount. */
758 oecount_eq (const void *p1, const void *p2)
760 const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42);
761 const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42);
762 return (c1->oecode == c2->oecode
763 && c1->op == c2->op);
766 /* Comparison function for qsort sorting oecount elements by count. */
769 oecount_cmp (const void *p1, const void *p2)
771 const oecount *c1 = (const oecount *)p1;
772 const oecount *c2 = (const oecount *)p2;
773 return c1->cnt - c2->cnt;
776 /* Walks the linear chain with result *DEF searching for an operation
777 with operand OP and code OPCODE removing that from the chain. *DEF
778 is updated if there is only one operand but no operation left. */
781 zero_one_operation (tree *def, enum tree_code opcode, tree op)
783 gimple stmt = SSA_NAME_DEF_STMT (*def);
787 tree name = gimple_assign_rhs1 (stmt);
789 /* If this is the operation we look for and one of the operands
790 is ours simply propagate the other operand into the stmts
792 if (gimple_assign_rhs_code (stmt) == opcode
794 || gimple_assign_rhs2 (stmt) == op))
798 gimple_stmt_iterator gsi;
800 name = gimple_assign_rhs2 (stmt);
801 gcc_assert (has_single_use (gimple_assign_lhs (stmt)));
802 single_imm_use (gimple_assign_lhs (stmt), &use, &use_stmt);
803 if (gimple_assign_lhs (stmt) == *def)
806 if (TREE_CODE (name) != SSA_NAME)
807 update_stmt (use_stmt);
808 gsi = gsi_for_stmt (stmt);
809 gsi_remove (&gsi, true);
814 /* Continue walking the chain. */
815 gcc_assert (name != op
816 && TREE_CODE (name) == SSA_NAME);
817 stmt = SSA_NAME_DEF_STMT (name);
822 /* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
823 the result. Places the statement after the definition of either
824 OP1 or OP2. Returns the new statement. */
827 build_and_add_sum (tree tmpvar, tree op1, tree op2, enum tree_code opcode)
829 gimple op1def = NULL, op2def = NULL;
830 gimple_stmt_iterator gsi;
834 /* Create the addition statement. */
835 sum = gimple_build_assign_with_ops (opcode, tmpvar, op1, op2);
836 op = make_ssa_name (tmpvar, sum);
837 gimple_assign_set_lhs (sum, op);
839 /* Find an insertion place and insert. */
840 if (TREE_CODE (op1) == SSA_NAME)
841 op1def = SSA_NAME_DEF_STMT (op1);
842 if (TREE_CODE (op2) == SSA_NAME)
843 op2def = SSA_NAME_DEF_STMT (op2);
844 if ((!op1def || gimple_nop_p (op1def))
845 && (!op2def || gimple_nop_p (op2def)))
847 gsi = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR));
848 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
850 else if ((!op1def || gimple_nop_p (op1def))
851 || (op2def && !gimple_nop_p (op2def)
852 && stmt_dominates_stmt_p (op1def, op2def)))
854 if (gimple_code (op2def) == GIMPLE_PHI)
856 gsi = gsi_start_bb (gimple_bb (op2def));
857 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
861 if (!stmt_ends_bb_p (op2def))
863 gsi = gsi_for_stmt (op2def);
864 gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
871 FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs)
872 if (e->flags & EDGE_FALLTHRU)
873 gsi_insert_on_edge_immediate (e, sum);
879 if (gimple_code (op1def) == GIMPLE_PHI)
881 gsi = gsi_start_bb (gimple_bb (op1def));
882 gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
886 if (!stmt_ends_bb_p (op1def))
888 gsi = gsi_for_stmt (op1def);
889 gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
896 FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs)
897 if (e->flags & EDGE_FALLTHRU)
898 gsi_insert_on_edge_immediate (e, sum);
907 /* Perform un-distribution of divisions and multiplications.
908 A * X + B * X is transformed into (A + B) * X and A / X + B / X
909 to (A + B) / X for real X.
911 The algorithm is organized as follows.
913 - First we walk the addition chain *OPS looking for summands that
914 are defined by a multiplication or a real division. This results
915 in the candidates bitmap with relevant indices into *OPS.
917 - Second we build the chains of multiplications or divisions for
918 these candidates, counting the number of occurences of (operand, code)
919 pairs in all of the candidates chains.
921 - Third we sort the (operand, code) pairs by number of occurence and
922 process them starting with the pair with the most uses.
924 * For each such pair we walk the candidates again to build a
925 second candidate bitmap noting all multiplication/division chains
926 that have at least one occurence of (operand, code).
928 * We build an alternate addition chain only covering these
929 candidates with one (operand, code) operation removed from their
930 multiplication/division chain.
932 * The first candidate gets replaced by the alternate addition chain
933 multiplied/divided by the operand.
935 * All candidate chains get disabled for further processing and
936 processing of (operand, code) pairs continues.
938 The alternate addition chains built are re-processed by the main
939 reassociation algorithm which allows optimizing a * x * y + b * y * x
940 to (a + b ) * x * y in one invocation of the reassociation pass. */
943 undistribute_ops_list (enum tree_code opcode,
944 VEC (operand_entry_t, heap) **ops, struct loop *loop)
946 unsigned int length = VEC_length (operand_entry_t, *ops);
949 sbitmap candidates, candidates2;
950 unsigned nr_candidates, nr_candidates2;
951 sbitmap_iterator sbi0;
952 VEC (operand_entry_t, heap) **subops;
954 bool changed = false;
957 || opcode != PLUS_EXPR)
960 /* Build a list of candidates to process. */
961 candidates = sbitmap_alloc (length);
962 sbitmap_zero (candidates);
964 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i)
966 enum tree_code dcode;
969 if (TREE_CODE (oe1->op) != SSA_NAME)
971 oe1def = SSA_NAME_DEF_STMT (oe1->op);
972 if (!is_gimple_assign (oe1def))
974 dcode = gimple_assign_rhs_code (oe1def);
975 if ((dcode != MULT_EXPR
976 && dcode != RDIV_EXPR)
977 || !is_reassociable_op (oe1def, dcode, loop))
980 SET_BIT (candidates, i);
984 if (nr_candidates < 2)
986 sbitmap_free (candidates);
990 if (dump_file && (dump_flags & TDF_DETAILS))
992 fprintf (dump_file, "searching for un-distribute opportunities ");
993 print_generic_expr (dump_file,
994 VEC_index (operand_entry_t, *ops,
995 sbitmap_first_set_bit (candidates))->op, 0);
996 fprintf (dump_file, " %d\n", nr_candidates);
999 /* Build linearized sub-operand lists and the counting table. */
1001 ctable = htab_create (15, oecount_hash, oecount_eq, NULL);
1002 subops = XCNEWVEC (VEC (operand_entry_t, heap) *,
1003 VEC_length (operand_entry_t, *ops));
1004 EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
1007 enum tree_code oecode;
1010 oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
1011 oecode = gimple_assign_rhs_code (oedef);
1012 linearize_expr_tree (&subops[i], oedef,
1013 associative_tree_code (oecode), false);
1015 for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
1023 VEC_safe_push (oecount, heap, cvec, &c);
1024 idx = VEC_length (oecount, cvec) + 41;
1025 slot = htab_find_slot (ctable, (void *)idx, INSERT);
1028 *slot = (void *)idx;
1032 VEC_pop (oecount, cvec);
1033 VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++;
1037 htab_delete (ctable);
1039 /* Sort the counting table. */
1040 qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec),
1041 sizeof (oecount), oecount_cmp);
1043 if (dump_file && (dump_flags & TDF_DETAILS))
1046 fprintf (dump_file, "Candidates:\n");
1047 for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j)
1049 fprintf (dump_file, " %u %s: ", c->cnt,
1050 c->oecode == MULT_EXPR
1051 ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
1052 print_generic_expr (dump_file, c->op, 0);
1053 fprintf (dump_file, "\n");
1057 /* Process the (operand, code) pairs in order of most occurence. */
1058 candidates2 = sbitmap_alloc (length);
1059 while (!VEC_empty (oecount, cvec))
1061 oecount *c = VEC_last (oecount, cvec);
1065 /* Now collect the operands in the outer chain that contain
1066 the common operand in their inner chain. */
1067 sbitmap_zero (candidates2);
1069 EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
1072 enum tree_code oecode;
1074 tree op = VEC_index (operand_entry_t, *ops, i)->op;
1076 /* If we undistributed in this chain already this may be
1078 if (TREE_CODE (op) != SSA_NAME)
1081 oedef = SSA_NAME_DEF_STMT (op);
1082 oecode = gimple_assign_rhs_code (oedef);
1083 if (oecode != c->oecode)
1086 for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
1088 if (oe1->op == c->op)
1090 SET_BIT (candidates2, i);
1097 if (nr_candidates2 >= 2)
1099 operand_entry_t oe1, oe2;
1102 int first = sbitmap_first_set_bit (candidates2);
1104 /* Build the new addition chain. */
1105 oe1 = VEC_index (operand_entry_t, *ops, first);
1106 if (dump_file && (dump_flags & TDF_DETAILS))
1108 fprintf (dump_file, "Building (");
1109 print_generic_expr (dump_file, oe1->op, 0);
1111 tmpvar = create_tmp_var (TREE_TYPE (oe1->op), NULL);
1112 add_referenced_var (tmpvar);
1113 zero_one_operation (&oe1->op, c->oecode, c->op);
1114 EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
1117 oe2 = VEC_index (operand_entry_t, *ops, i);
1118 if (dump_file && (dump_flags & TDF_DETAILS))
1120 fprintf (dump_file, " + ");
1121 print_generic_expr (dump_file, oe2->op, 0);
1123 zero_one_operation (&oe2->op, c->oecode, c->op);
1124 sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
1125 oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node);
1127 oe1->op = gimple_get_lhs (sum);
1130 /* Apply the multiplication/division. */
1131 prod = build_and_add_sum (tmpvar, oe1->op, c->op, c->oecode);
1132 if (dump_file && (dump_flags & TDF_DETAILS))
1134 fprintf (dump_file, ") %s ", c->oecode == MULT_EXPR ? "*" : "/");
1135 print_generic_expr (dump_file, c->op, 0);
1136 fprintf (dump_file, "\n");
1139 /* Record it in the addition chain and disable further
1140 undistribution with this op. */
1141 oe1->op = gimple_assign_lhs (prod);
1142 oe1->rank = get_rank (oe1->op);
1143 VEC_free (operand_entry_t, heap, subops[first]);
1148 VEC_pop (oecount, cvec);
1151 for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i)
1152 VEC_free (operand_entry_t, heap, subops[i]);
1154 VEC_free (oecount, heap, cvec);
1155 sbitmap_free (candidates);
1156 sbitmap_free (candidates2);
1162 /* Perform various identities and other optimizations on the list of
1163 operand entries, stored in OPS. The tree code for the binary
1164 operation between all the operands is OPCODE. */
1167 optimize_ops_list (enum tree_code opcode,
1168 VEC (operand_entry_t, heap) **ops)
1170 unsigned int length = VEC_length (operand_entry_t, *ops);
1173 operand_entry_t oelast = NULL;
1174 bool iterate = false;
1179 oelast = VEC_last (operand_entry_t, *ops);
1181 /* If the last two are constants, pop the constants off, merge them
1182 and try the next two. */
1183 if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
1185 operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
1187 if (oelm1->rank == 0
1188 && is_gimple_min_invariant (oelm1->op)
1189 && useless_type_conversion_p (TREE_TYPE (oelm1->op),
1190 TREE_TYPE (oelast->op)))
1192 tree folded = fold_binary (opcode, TREE_TYPE (oelm1->op),
1193 oelm1->op, oelast->op);
1195 if (folded && is_gimple_min_invariant (folded))
1197 if (dump_file && (dump_flags & TDF_DETAILS))
1198 fprintf (dump_file, "Merging constants\n");
1200 VEC_pop (operand_entry_t, *ops);
1201 VEC_pop (operand_entry_t, *ops);
1203 add_to_ops_vec (ops, folded);
1204 reassociate_stats.constants_eliminated++;
1206 optimize_ops_list (opcode, ops);
1212 eliminate_using_constants (opcode, ops);
1215 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
1219 if (eliminate_not_pairs (opcode, ops, i, oe))
1221 if (eliminate_duplicate_pair (opcode, ops, &done, i, oe, oelast)
1222 || (!done && eliminate_plus_minus_pair (opcode, ops, i, oe)))
1234 length = VEC_length (operand_entry_t, *ops);
1235 oelast = VEC_last (operand_entry_t, *ops);
1238 optimize_ops_list (opcode, ops);
1241 /* Return true if OPERAND is defined by a PHI node which uses the LHS
1242 of STMT in it's operands. This is also known as a "destructive
1243 update" operation. */
1246 is_phi_for_stmt (gimple stmt, tree operand)
1250 use_operand_p arg_p;
1253 if (TREE_CODE (operand) != SSA_NAME)
1256 lhs = gimple_assign_lhs (stmt);
1258 def_stmt = SSA_NAME_DEF_STMT (operand);
1259 if (gimple_code (def_stmt) != GIMPLE_PHI)
1262 FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
1263 if (lhs == USE_FROM_PTR (arg_p))
1268 /* Recursively rewrite our linearized statements so that the operators
1269 match those in OPS[OPINDEX], putting the computation in rank
1273 rewrite_expr_tree (gimple stmt, unsigned int opindex,
1274 VEC(operand_entry_t, heap) * ops)
1276 tree rhs1 = gimple_assign_rhs1 (stmt);
1277 tree rhs2 = gimple_assign_rhs2 (stmt);
1280 /* If we have three operands left, then we want to make sure the one
1281 that gets the double binary op are the ones with the same rank.
1283 The alternative we try is to see if this is a destructive
1284 update style statement, which is like:
1287 In that case, we want to use the destructive update form to
1288 expose the possible vectorizer sum reduction opportunity.
1289 In that case, the third operand will be the phi node.
1291 We could, of course, try to be better as noted above, and do a
1292 lot of work to try to find these opportunities in >3 operand
1293 cases, but it is unlikely to be worth it. */
1294 if (opindex + 3 == VEC_length (operand_entry_t, ops))
1296 operand_entry_t oe1, oe2, oe3;
1298 oe1 = VEC_index (operand_entry_t, ops, opindex);
1299 oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
1300 oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
1302 if ((oe1->rank == oe2->rank
1303 && oe2->rank != oe3->rank)
1304 || (is_phi_for_stmt (stmt, oe3->op)
1305 && !is_phi_for_stmt (stmt, oe1->op)
1306 && !is_phi_for_stmt (stmt, oe2->op)))
1308 struct operand_entry temp = *oe3;
1310 oe3->rank = oe1->rank;
1312 oe1->rank= temp.rank;
1314 else if ((oe1->rank == oe3->rank
1315 && oe2->rank != oe3->rank)
1316 || (is_phi_for_stmt (stmt, oe2->op)
1317 && !is_phi_for_stmt (stmt, oe1->op)
1318 && !is_phi_for_stmt (stmt, oe3->op)))
1320 struct operand_entry temp = *oe2;
1322 oe2->rank = oe1->rank;
1324 oe1->rank= temp.rank;
1328 /* The final recursion case for this function is that you have
1329 exactly two operations left.
1330 If we had one exactly one op in the entire list to start with, we
1331 would have never called this function, and the tail recursion
1332 rewrites them one at a time. */
1333 if (opindex + 2 == VEC_length (operand_entry_t, ops))
1335 operand_entry_t oe1, oe2;
1337 oe1 = VEC_index (operand_entry_t, ops, opindex);
1338 oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
1340 if (rhs1 != oe1->op || rhs2 != oe2->op)
1342 if (dump_file && (dump_flags & TDF_DETAILS))
1344 fprintf (dump_file, "Transforming ");
1345 print_gimple_stmt (dump_file, stmt, 0, 0);
1348 gimple_assign_set_rhs1 (stmt, oe1->op);
1349 gimple_assign_set_rhs2 (stmt, oe2->op);
1352 if (dump_file && (dump_flags & TDF_DETAILS))
1354 fprintf (dump_file, " into ");
1355 print_gimple_stmt (dump_file, stmt, 0, 0);
1362 /* If we hit here, we should have 3 or more ops left. */
1363 gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
1365 /* Rewrite the next operator. */
1366 oe = VEC_index (operand_entry_t, ops, opindex);
1371 if (dump_file && (dump_flags & TDF_DETAILS))
1373 fprintf (dump_file, "Transforming ");
1374 print_gimple_stmt (dump_file, stmt, 0, 0);
1377 gimple_assign_set_rhs2 (stmt, oe->op);
1380 if (dump_file && (dump_flags & TDF_DETAILS))
1382 fprintf (dump_file, " into ");
1383 print_gimple_stmt (dump_file, stmt, 0, 0);
1386 /* Recurse on the LHS of the binary operator, which is guaranteed to
1387 be the non-leaf side. */
1388 rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops);
1391 /* Transform STMT, which is really (A +B) + (C + D) into the left
1392 linear form, ((A+B)+C)+D.
1393 Recurse on D if necessary. */
1396 linearize_expr (gimple stmt)
1398 gimple_stmt_iterator gsinow, gsirhs;
1399 gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
1400 gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1401 enum tree_code rhscode = gimple_assign_rhs_code (stmt);
1402 gimple newbinrhs = NULL;
1403 struct loop *loop = loop_containing_stmt (stmt);
1405 gcc_assert (is_reassociable_op (binlhs, rhscode, loop)
1406 && is_reassociable_op (binrhs, rhscode, loop));
1408 gsinow = gsi_for_stmt (stmt);
1409 gsirhs = gsi_for_stmt (binrhs);
1410 gsi_move_before (&gsirhs, &gsinow);
1412 gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
1413 gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs));
1414 gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs));
1416 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
1417 newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
1419 if (dump_file && (dump_flags & TDF_DETAILS))
1421 fprintf (dump_file, "Linearized: ");
1422 print_gimple_stmt (dump_file, stmt, 0, 0);
1425 reassociate_stats.linearized++;
1426 update_stmt (binrhs);
1427 update_stmt (binlhs);
1430 gimple_set_visited (stmt, true);
1431 gimple_set_visited (binlhs, true);
1432 gimple_set_visited (binrhs, true);
1434 /* Tail recurse on the new rhs if it still needs reassociation. */
1435 if (newbinrhs && is_reassociable_op (newbinrhs, rhscode, loop))
1436 /* ??? This should probably be linearize_expr (newbinrhs) but I don't
1437 want to change the algorithm while converting to tuples. */
1438 linearize_expr (stmt);
1441 /* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return
1442 it. Otherwise, return NULL. */
1445 get_single_immediate_use (tree lhs)
1447 use_operand_p immuse;
1450 if (TREE_CODE (lhs) == SSA_NAME
1451 && single_imm_use (lhs, &immuse, &immusestmt)
1452 && is_gimple_assign (immusestmt))
1458 static VEC(tree, heap) *broken_up_subtracts;
1460 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
1461 representing the negated value. Insertions of any necessary
1462 instructions go before GSI.
1463 This function is recursive in that, if you hand it "a_5" as the
1464 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
1465 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */
1468 negate_value (tree tonegate, gimple_stmt_iterator *gsi)
1470 gimple negatedefstmt= NULL;
1471 tree resultofnegate;
1473 /* If we are trying to negate a name, defined by an add, negate the
1474 add operands instead. */
1475 if (TREE_CODE (tonegate) == SSA_NAME)
1476 negatedefstmt = SSA_NAME_DEF_STMT (tonegate);
1477 if (TREE_CODE (tonegate) == SSA_NAME
1478 && is_gimple_assign (negatedefstmt)
1479 && TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME
1480 && has_single_use (gimple_assign_lhs (negatedefstmt))
1481 && gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR)
1483 gimple_stmt_iterator gsi;
1484 tree rhs1 = gimple_assign_rhs1 (negatedefstmt);
1485 tree rhs2 = gimple_assign_rhs2 (negatedefstmt);
1487 gsi = gsi_for_stmt (negatedefstmt);
1488 rhs1 = negate_value (rhs1, &gsi);
1489 gimple_assign_set_rhs1 (negatedefstmt, rhs1);
1491 gsi = gsi_for_stmt (negatedefstmt);
1492 rhs2 = negate_value (rhs2, &gsi);
1493 gimple_assign_set_rhs2 (negatedefstmt, rhs2);
1495 update_stmt (negatedefstmt);
1496 return gimple_assign_lhs (negatedefstmt);
1499 tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
1500 resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true,
1501 NULL_TREE, true, GSI_SAME_STMT);
1502 VEC_safe_push (tree, heap, broken_up_subtracts, resultofnegate);
1503 return resultofnegate;
1506 /* Return true if we should break up the subtract in STMT into an add
1507 with negate. This is true when we the subtract operands are really
1508 adds, or the subtract itself is used in an add expression. In
1509 either case, breaking up the subtract into an add with negate
1510 exposes the adds to reassociation. */
1513 should_break_up_subtract (gimple stmt)
1515 tree lhs = gimple_assign_lhs (stmt);
1516 tree binlhs = gimple_assign_rhs1 (stmt);
1517 tree binrhs = gimple_assign_rhs2 (stmt);
1519 struct loop *loop = loop_containing_stmt (stmt);
1521 if (TREE_CODE (binlhs) == SSA_NAME
1522 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
1525 if (TREE_CODE (binrhs) == SSA_NAME
1526 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
1529 if (TREE_CODE (lhs) == SSA_NAME
1530 && (immusestmt = get_single_immediate_use (lhs))
1531 && is_gimple_assign (immusestmt)
1532 && (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR
1533 || gimple_assign_rhs_code (immusestmt) == MULT_EXPR))
1538 /* Transform STMT from A - B into A + -B. */
1541 break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip)
1543 tree rhs1 = gimple_assign_rhs1 (stmt);
1544 tree rhs2 = gimple_assign_rhs2 (stmt);
1546 if (dump_file && (dump_flags & TDF_DETAILS))
1548 fprintf (dump_file, "Breaking up subtract ");
1549 print_gimple_stmt (dump_file, stmt, 0, 0);
1552 rhs2 = negate_value (rhs2, gsip);
1553 gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2);
1557 /* Recursively linearize a binary expression that is the RHS of STMT.
1558 Place the operands of the expression tree in the vector named OPS. */
1561 linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
1562 bool is_associative, bool set_visited)
1564 gimple_stmt_iterator gsinow, gsilhs;
1565 tree binlhs = gimple_assign_rhs1 (stmt);
1566 tree binrhs = gimple_assign_rhs2 (stmt);
1567 gimple binlhsdef, binrhsdef;
1568 bool binlhsisreassoc = false;
1569 bool binrhsisreassoc = false;
1570 enum tree_code rhscode = gimple_assign_rhs_code (stmt);
1571 struct loop *loop = loop_containing_stmt (stmt);
1574 gimple_set_visited (stmt, true);
1576 if (TREE_CODE (binlhs) == SSA_NAME)
1578 binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1579 binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop);
1582 if (TREE_CODE (binrhs) == SSA_NAME)
1584 binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1585 binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop);
1588 /* If the LHS is not reassociable, but the RHS is, we need to swap
1589 them. If neither is reassociable, there is nothing we can do, so
1590 just put them in the ops vector. If the LHS is reassociable,
1591 linearize it. If both are reassociable, then linearize the RHS
1594 if (!binlhsisreassoc)
1598 /* If this is not a associative operation like division, give up. */
1599 if (!is_associative)
1601 add_to_ops_vec (ops, binrhs);
1605 if (!binrhsisreassoc)
1607 add_to_ops_vec (ops, binrhs);
1608 add_to_ops_vec (ops, binlhs);
1612 if (dump_file && (dump_flags & TDF_DETAILS))
1614 fprintf (dump_file, "swapping operands of ");
1615 print_gimple_stmt (dump_file, stmt, 0, 0);
1618 swap_tree_operands (stmt,
1619 gimple_assign_rhs1_ptr (stmt),
1620 gimple_assign_rhs2_ptr (stmt));
1623 if (dump_file && (dump_flags & TDF_DETAILS))
1625 fprintf (dump_file, " is now ");
1626 print_gimple_stmt (dump_file, stmt, 0, 0);
1629 /* We want to make it so the lhs is always the reassociative op,
1635 else if (binrhsisreassoc)
1637 linearize_expr (stmt);
1638 binlhs = gimple_assign_rhs1 (stmt);
1639 binrhs = gimple_assign_rhs2 (stmt);
1642 gcc_assert (TREE_CODE (binrhs) != SSA_NAME
1643 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
1645 gsinow = gsi_for_stmt (stmt);
1646 gsilhs = gsi_for_stmt (SSA_NAME_DEF_STMT (binlhs));
1647 gsi_move_before (&gsilhs, &gsinow);
1648 linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
1649 is_associative, set_visited);
1650 add_to_ops_vec (ops, binrhs);
1653 /* Repropagate the negates back into subtracts, since no other pass
1654 currently does it. */
1657 repropagate_negates (void)
1662 for (i = 0; VEC_iterate (tree, broken_up_subtracts, i, negate); i++)
1664 gimple user = get_single_immediate_use (negate);
1666 /* The negate operand can be either operand of a PLUS_EXPR
1667 (it can be the LHS if the RHS is a constant for example).
1669 Force the negate operand to the RHS of the PLUS_EXPR, then
1670 transform the PLUS_EXPR into a MINUS_EXPR. */
1672 && is_gimple_assign (user)
1673 && gimple_assign_rhs_code (user) == PLUS_EXPR)
1675 /* If the negated operand appears on the LHS of the
1676 PLUS_EXPR, exchange the operands of the PLUS_EXPR
1677 to force the negated operand to the RHS of the PLUS_EXPR. */
1678 if (gimple_assign_rhs1 (user) == negate)
1680 swap_tree_operands (user,
1681 gimple_assign_rhs1_ptr (user),
1682 gimple_assign_rhs2_ptr (user));
1685 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
1686 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */
1687 if (gimple_assign_rhs2 (user) == negate)
1689 tree rhs1 = gimple_assign_rhs1 (user);
1690 tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
1691 gimple_stmt_iterator gsi = gsi_for_stmt (user);
1692 gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
1699 /* Break up subtract operations in block BB.
1701 We do this top down because we don't know whether the subtract is
1702 part of a possible chain of reassociation except at the top.
1711 we want to break up k = t - q, but we won't until we've transformed q
1712 = b - r, which won't be broken up until we transform b = c - d.
1714 En passant, clear the GIMPLE visited flag on every statement. */
1717 break_up_subtract_bb (basic_block bb)
1719 gimple_stmt_iterator gsi;
1722 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1724 gimple stmt = gsi_stmt (gsi);
1725 gimple_set_visited (stmt, false);
1727 /* Look for simple gimple subtract operations. */
1728 if (is_gimple_assign (stmt)
1729 && gimple_assign_rhs_code (stmt) == MINUS_EXPR)
1731 tree lhs = gimple_assign_lhs (stmt);
1732 tree rhs1 = gimple_assign_rhs1 (stmt);
1733 tree rhs2 = gimple_assign_rhs2 (stmt);
1735 /* If associative-math we can do reassociation for
1736 non-integral types. Or, we can do reassociation for
1737 non-saturating fixed-point types. */
1738 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1739 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1740 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1741 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
1742 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
1743 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
1744 || !flag_associative_math)
1745 && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
1746 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
1747 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
1750 /* Check for a subtract used only in an addition. If this
1751 is the case, transform it into add of a negate for better
1752 reassociation. IE transform C = A-B into C = A + -B if C
1753 is only used in an addition. */
1754 if (should_break_up_subtract (stmt))
1755 break_up_subtract (stmt, &gsi);
1758 for (son = first_dom_son (CDI_DOMINATORS, bb);
1760 son = next_dom_son (CDI_DOMINATORS, son))
1761 break_up_subtract_bb (son);
1764 /* Reassociate expressions in basic block BB and its post-dominator as
1768 reassociate_bb (basic_block bb)
1770 gimple_stmt_iterator gsi;
1773 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1775 gimple stmt = gsi_stmt (gsi);
1777 if (is_gimple_assign (stmt))
1779 tree lhs, rhs1, rhs2;
1780 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1782 /* If this is not a gimple binary expression, there is
1783 nothing for us to do with it. */
1784 if (get_gimple_rhs_class (rhs_code) != GIMPLE_BINARY_RHS)
1787 /* If this was part of an already processed statement,
1788 we don't need to touch it again. */
1789 if (gimple_visited_p (stmt))
1791 /* This statement might have become dead because of previous
1793 if (has_zero_uses (gimple_get_lhs (stmt)))
1795 gsi_remove (&gsi, true);
1796 release_defs (stmt);
1797 /* We might end up removing the last stmt above which
1798 places the iterator to the end of the sequence.
1799 Reset it to the last stmt in this case which might
1800 be the end of the sequence as well if we removed
1801 the last statement of the sequence. In which case
1802 we need to bail out. */
1803 if (gsi_end_p (gsi))
1805 gsi = gsi_last_bb (bb);
1806 if (gsi_end_p (gsi))
1813 lhs = gimple_assign_lhs (stmt);
1814 rhs1 = gimple_assign_rhs1 (stmt);
1815 rhs2 = gimple_assign_rhs2 (stmt);
1817 /* If associative-math we can do reassociation for
1818 non-integral types. Or, we can do reassociation for
1819 non-saturating fixed-point types. */
1820 if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1821 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1822 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
1823 && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
1824 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
1825 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
1826 || !flag_associative_math)
1827 && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
1828 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
1829 || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
1832 if (associative_tree_code (rhs_code))
1834 VEC(operand_entry_t, heap) *ops = NULL;
1836 /* There may be no immediate uses left by the time we
1837 get here because we may have eliminated them all. */
1838 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
1841 gimple_set_visited (stmt, true);
1842 linearize_expr_tree (&ops, stmt, true, true);
1843 qsort (VEC_address (operand_entry_t, ops),
1844 VEC_length (operand_entry_t, ops),
1845 sizeof (operand_entry_t),
1846 sort_by_operand_rank);
1847 optimize_ops_list (rhs_code, &ops);
1848 if (undistribute_ops_list (rhs_code, &ops,
1849 loop_containing_stmt (stmt)))
1851 qsort (VEC_address (operand_entry_t, ops),
1852 VEC_length (operand_entry_t, ops),
1853 sizeof (operand_entry_t),
1854 sort_by_operand_rank);
1855 optimize_ops_list (rhs_code, &ops);
1858 if (VEC_length (operand_entry_t, ops) == 1)
1860 if (dump_file && (dump_flags & TDF_DETAILS))
1862 fprintf (dump_file, "Transforming ");
1863 print_gimple_stmt (dump_file, stmt, 0, 0);
1866 gimple_assign_set_rhs_from_tree (&gsi,
1867 VEC_last (operand_entry_t,
1871 if (dump_file && (dump_flags & TDF_DETAILS))
1873 fprintf (dump_file, " into ");
1874 print_gimple_stmt (dump_file, stmt, 0, 0);
1879 rewrite_expr_tree (stmt, 0, ops);
1882 VEC_free (operand_entry_t, heap, ops);
1886 for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
1888 son = next_dom_son (CDI_POST_DOMINATORS, son))
1889 reassociate_bb (son);
1892 void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
1893 void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
1895 /* Dump the operand entry vector OPS to FILE. */
1898 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
1903 for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++)
1905 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
1906 print_generic_expr (file, oe->op, 0);
1910 /* Dump the operand entry vector OPS to STDERR. */
1913 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
1915 dump_ops_vector (stderr, ops);
1921 break_up_subtract_bb (ENTRY_BLOCK_PTR);
1922 reassociate_bb (EXIT_BLOCK_PTR);
1925 /* Initialize the reassociation pass. */
1933 int *bbs = XNEWVEC (int, last_basic_block + 1);
1935 /* Find the loops, so that we can prevent moving calculations in
1937 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
1939 memset (&reassociate_stats, 0, sizeof (reassociate_stats));
1941 operand_entry_pool = create_alloc_pool ("operand entry pool",
1942 sizeof (struct operand_entry), 30);
1944 /* Reverse RPO (Reverse Post Order) will give us something where
1945 deeper loops come later. */
1946 pre_and_rev_post_order_compute (NULL, bbs, false);
1947 bb_rank = XCNEWVEC (long, last_basic_block + 1);
1948 operand_rank = pointer_map_create ();
1950 /* Give each argument a distinct rank. */
1951 for (param = DECL_ARGUMENTS (current_function_decl);
1953 param = TREE_CHAIN (param))
1955 if (gimple_default_def (cfun, param) != NULL)
1957 tree def = gimple_default_def (cfun, param);
1958 insert_operand_rank (def, ++rank);
1962 /* Give the chain decl a distinct rank. */
1963 if (cfun->static_chain_decl != NULL)
1965 tree def = gimple_default_def (cfun, cfun->static_chain_decl);
1967 insert_operand_rank (def, ++rank);
1970 /* Set up rank for each BB */
1971 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
1972 bb_rank[bbs[i]] = ++rank << 16;
1975 calculate_dominance_info (CDI_POST_DOMINATORS);
1976 broken_up_subtracts = NULL;
1979 /* Cleanup after the reassociation pass, and print stats if
1985 statistics_counter_event (cfun, "Linearized",
1986 reassociate_stats.linearized);
1987 statistics_counter_event (cfun, "Constants eliminated",
1988 reassociate_stats.constants_eliminated);
1989 statistics_counter_event (cfun, "Ops eliminated",
1990 reassociate_stats.ops_eliminated);
1991 statistics_counter_event (cfun, "Statements rewritten",
1992 reassociate_stats.rewritten);
1994 pointer_map_destroy (operand_rank);
1995 free_alloc_pool (operand_entry_pool);
1997 VEC_free (tree, heap, broken_up_subtracts);
1998 free_dominance_info (CDI_POST_DOMINATORS);
1999 loop_optimizer_finalize ();
2002 /* Gate and execute functions for Reassociation. */
2005 execute_reassoc (void)
2010 repropagate_negates ();
2017 gate_tree_ssa_reassoc (void)
2019 return flag_tree_reassoc != 0;
2022 struct gimple_opt_pass pass_reassoc =
2026 "reassoc", /* name */
2027 gate_tree_ssa_reassoc, /* gate */
2028 execute_reassoc, /* execute */
2031 0, /* static_pass_number */
2032 TV_TREE_REASSOC, /* tv_id */
2033 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2034 0, /* properties_provided */
2035 0, /* properties_destroyed */
2036 0, /* todo_flags_start */
2037 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */