1 /* Reassociation for trees.
2 Copyright (C) 2005-2015 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"
24 #include "hash-table.h"
31 #include "double-int.h"
38 #include "fold-const.h"
39 #include "stor-layout.h"
41 #include "hard-reg-set.h"
43 #include "dominance.h"
46 #include "basic-block.h"
47 #include "gimple-pretty-print.h"
48 #include "tree-inline.h"
50 #include "tree-ssa-alias.h"
51 #include "internal-fn.h"
52 #include "gimple-fold.h"
54 #include "gimple-expr.h"
57 #include "gimple-iterator.h"
58 #include "gimplify-me.h"
59 #include "gimple-ssa.h"
61 #include "tree-phinodes.h"
62 #include "ssa-iterators.h"
63 #include "stringpool.h"
64 #include "tree-ssanames.h"
65 #include "tree-ssa-loop-niter.h"
66 #include "tree-ssa-loop.h"
69 #include "statistics.h"
71 #include "fixed-value.h"
72 #include "insn-config.h"
83 #include "tree-iterator.h"
84 #include "tree-pass.h"
85 #include "alloc-pool.h"
86 #include "langhooks.h"
90 #include "diagnostic-core.h"
93 #include "insn-codes.h"
96 /* This is a simple global reassociation pass. It is, in part, based
97 on the LLVM pass of the same name (They do some things more/less
98 than we do, in different orders, etc).
100 It consists of five steps:
102 1. Breaking up subtract operations into addition + negate, where
103 it would promote the reassociation of adds.
105 2. Left linearization of the expression trees, so that (A+B)+(C+D)
106 becomes (((A+B)+C)+D), which is easier for us to rewrite later.
107 During linearization, we place the operands of the binary
108 expressions into a vector of operand_entry_t
110 3. Optimization of the operand lists, eliminating things like a +
113 3a. Combine repeated factors with the same occurrence counts
114 into a __builtin_powi call that will later be optimized into
115 an optimal number of multiplies.
117 4. Rewrite the expression trees we linearized and optimized so
118 they are in proper rank order.
120 5. Repropagate negates, as nothing else will clean it up ATM.
122 A bit of theory on #4, since nobody seems to write anything down
123 about why it makes sense to do it the way they do it:
125 We could do this much nicer theoretically, but don't (for reasons
126 explained after how to do it theoretically nice :P).
128 In order to promote the most redundancy elimination, you want
129 binary expressions whose operands are the same rank (or
130 preferably, the same value) exposed to the redundancy eliminator,
131 for possible elimination.
133 So the way to do this if we really cared, is to build the new op
134 tree from the leaves to the roots, merging as you go, and putting the
135 new op on the end of the worklist, until you are left with one
136 thing on the worklist.
138 IE if you have to rewrite the following set of operands (listed with
139 rank in parentheses), with opcode PLUS_EXPR:
141 a (1), b (1), c (1), d (2), e (2)
144 We start with our merge worklist empty, and the ops list with all of
147 You want to first merge all leaves of the same rank, as much as
150 So first build a binary op of
152 mergetmp = a + b, and put "mergetmp" on the merge worklist.
154 Because there is no three operand form of PLUS_EXPR, c is not going to
155 be exposed to redundancy elimination as a rank 1 operand.
157 So you might as well throw it on the merge worklist (you could also
158 consider it to now be a rank two operand, and merge it with d and e,
159 but in this case, you then have evicted e from a binary op. So at
160 least in this situation, you can't win.)
162 Then build a binary op of d + e
165 and put mergetmp2 on the merge worklist.
167 so merge worklist = {mergetmp, c, mergetmp2}
169 Continue building binary ops of these operations until you have only
170 one operation left on the worklist.
175 mergetmp3 = mergetmp + c
177 worklist = {mergetmp2, mergetmp3}
179 mergetmp4 = mergetmp2 + mergetmp3
181 worklist = {mergetmp4}
183 because we have one operation left, we can now just set the original
184 statement equal to the result of that operation.
186 This will at least expose a + b and d + e to redundancy elimination
187 as binary operations.
189 For extra points, you can reuse the old statements to build the
190 mergetmps, since you shouldn't run out.
192 So why don't we do this?
194 Because it's expensive, and rarely will help. Most trees we are
195 reassociating have 3 or less ops. If they have 2 ops, they already
196 will be written into a nice single binary op. If you have 3 ops, a
197 single simple check suffices to tell you whether the first two are of the
198 same rank. If so, you know to order it
201 newstmt = mergetmp + op3
205 newstmt = mergetmp + op1
207 If all three are of the same rank, you can't expose them all in a
208 single binary operator anyway, so the above is *still* the best you
211 Thus, this is what we do. When we have three ops left, we check to see
212 what order to put them in, and call it a day. As a nod to vector sum
213 reduction, we check if any of the ops are really a phi node that is a
214 destructive update for the associating op, and keep the destructive
215 update together for vector sum reduction recognition. */
222 int constants_eliminated
;
225 int pows_encountered
;
229 /* Operator, rank pair. */
230 typedef struct operand_entry
238 static alloc_pool operand_entry_pool
;
240 /* This is used to assign a unique ID to each struct operand_entry
241 so that qsort results are identical on different hosts. */
242 static int next_operand_entry_id
;
244 /* Starting rank number for a given basic block, so that we can rank
245 operations using unmovable instructions in that BB based on the bb
247 static long *bb_rank
;
249 /* Operand->rank hashtable. */
250 static hash_map
<tree
, long> *operand_rank
;
252 /* Vector of SSA_NAMEs on which after reassociate_bb is done with
253 all basic blocks the CFG should be adjusted - basic blocks
254 split right after that SSA_NAME's definition statement and before
255 the only use, which must be a bit ior. */
256 static vec
<tree
> reassoc_branch_fixups
;
259 static long get_rank (tree
);
260 static bool reassoc_stmt_dominates_stmt_p (gimple
, gimple
);
262 /* Wrapper around gsi_remove, which adjusts gimple_uid of debug stmts
263 possibly added by gsi_remove. */
266 reassoc_remove_stmt (gimple_stmt_iterator
*gsi
)
268 gimple stmt
= gsi_stmt (*gsi
);
270 if (!MAY_HAVE_DEBUG_STMTS
|| gimple_code (stmt
) == GIMPLE_PHI
)
271 return gsi_remove (gsi
, true);
273 gimple_stmt_iterator prev
= *gsi
;
275 unsigned uid
= gimple_uid (stmt
);
276 basic_block bb
= gimple_bb (stmt
);
277 bool ret
= gsi_remove (gsi
, true);
278 if (!gsi_end_p (prev
))
281 prev
= gsi_start_bb (bb
);
282 gimple end_stmt
= gsi_stmt (*gsi
);
283 while ((stmt
= gsi_stmt (prev
)) != end_stmt
)
285 gcc_assert (stmt
&& is_gimple_debug (stmt
) && gimple_uid (stmt
) == 0);
286 gimple_set_uid (stmt
, uid
);
292 /* Bias amount for loop-carried phis. We want this to be larger than
293 the depth of any reassociation tree we can see, but not larger than
294 the rank difference between two blocks. */
295 #define PHI_LOOP_BIAS (1 << 15)
297 /* Rank assigned to a phi statement. If STMT is a loop-carried phi of
298 an innermost loop, and the phi has only a single use which is inside
299 the loop, then the rank is the block rank of the loop latch plus an
300 extra bias for the loop-carried dependence. This causes expressions
301 calculated into an accumulator variable to be independent for each
302 iteration of the loop. If STMT is some other phi, the rank is the
303 block rank of its containing block. */
305 phi_rank (gimple stmt
)
307 basic_block bb
= gimple_bb (stmt
);
308 struct loop
*father
= bb
->loop_father
;
314 /* We only care about real loops (those with a latch). */
316 return bb_rank
[bb
->index
];
318 /* Interesting phis must be in headers of innermost loops. */
319 if (bb
!= father
->header
321 return bb_rank
[bb
->index
];
323 /* Ignore virtual SSA_NAMEs. */
324 res
= gimple_phi_result (stmt
);
325 if (virtual_operand_p (res
))
326 return bb_rank
[bb
->index
];
328 /* The phi definition must have a single use, and that use must be
329 within the loop. Otherwise this isn't an accumulator pattern. */
330 if (!single_imm_use (res
, &use
, &use_stmt
)
331 || gimple_bb (use_stmt
)->loop_father
!= father
)
332 return bb_rank
[bb
->index
];
334 /* Look for phi arguments from within the loop. If found, bias this phi. */
335 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
337 tree arg
= gimple_phi_arg_def (stmt
, i
);
338 if (TREE_CODE (arg
) == SSA_NAME
339 && !SSA_NAME_IS_DEFAULT_DEF (arg
))
341 gimple def_stmt
= SSA_NAME_DEF_STMT (arg
);
342 if (gimple_bb (def_stmt
)->loop_father
== father
)
343 return bb_rank
[father
->latch
->index
] + PHI_LOOP_BIAS
;
347 /* Must be an uninteresting phi. */
348 return bb_rank
[bb
->index
];
351 /* If EXP is an SSA_NAME defined by a PHI statement that represents a
352 loop-carried dependence of an innermost loop, return TRUE; else
355 loop_carried_phi (tree exp
)
360 if (TREE_CODE (exp
) != SSA_NAME
361 || SSA_NAME_IS_DEFAULT_DEF (exp
))
364 phi_stmt
= SSA_NAME_DEF_STMT (exp
);
366 if (gimple_code (SSA_NAME_DEF_STMT (exp
)) != GIMPLE_PHI
)
369 /* Non-loop-carried phis have block rank. Loop-carried phis have
370 an additional bias added in. If this phi doesn't have block rank,
371 it's biased and should not be propagated. */
372 block_rank
= bb_rank
[gimple_bb (phi_stmt
)->index
];
374 if (phi_rank (phi_stmt
) != block_rank
)
380 /* Return the maximum of RANK and the rank that should be propagated
381 from expression OP. For most operands, this is just the rank of OP.
382 For loop-carried phis, the value is zero to avoid undoing the bias
383 in favor of the phi. */
385 propagate_rank (long rank
, tree op
)
389 if (loop_carried_phi (op
))
392 op_rank
= get_rank (op
);
394 return MAX (rank
, op_rank
);
397 /* Look up the operand rank structure for expression E. */
400 find_operand_rank (tree e
)
402 long *slot
= operand_rank
->get (e
);
403 return slot
? *slot
: -1;
406 /* Insert {E,RANK} into the operand rank hashtable. */
409 insert_operand_rank (tree e
, long rank
)
411 gcc_assert (rank
> 0);
412 gcc_assert (!operand_rank
->put (e
, rank
));
415 /* Given an expression E, return the rank of the expression. */
420 /* SSA_NAME's have the rank of the expression they are the result
422 For globals and uninitialized values, the rank is 0.
423 For function arguments, use the pre-setup rank.
424 For PHI nodes, stores, asm statements, etc, we use the rank of
426 For simple operations, the rank is the maximum rank of any of
427 its operands, or the bb_rank, whichever is less.
428 I make no claims that this is optimal, however, it gives good
431 /* We make an exception to the normal ranking system to break
432 dependences of accumulator variables in loops. Suppose we
433 have a simple one-block loop containing:
440 As shown, each iteration of the calculation into x is fully
441 dependent upon the iteration before it. We would prefer to
442 see this in the form:
449 If the loop is unrolled, the calculations of b and c from
450 different iterations can be interleaved.
452 To obtain this result during reassociation, we bias the rank
453 of the phi definition x_1 upward, when it is recognized as an
454 accumulator pattern. The artificial rank causes it to be
455 added last, providing the desired independence. */
457 if (TREE_CODE (e
) == SSA_NAME
)
464 if (SSA_NAME_IS_DEFAULT_DEF (e
))
465 return find_operand_rank (e
);
467 stmt
= SSA_NAME_DEF_STMT (e
);
468 if (gimple_code (stmt
) == GIMPLE_PHI
)
469 return phi_rank (stmt
);
471 if (!is_gimple_assign (stmt
))
472 return bb_rank
[gimple_bb (stmt
)->index
];
474 /* If we already have a rank for this expression, use that. */
475 rank
= find_operand_rank (e
);
479 /* Otherwise, find the maximum rank for the operands. As an
480 exception, remove the bias from loop-carried phis when propagating
481 the rank so that dependent operations are not also biased. */
482 /* Simply walk over all SSA uses - this takes advatage of the
483 fact that non-SSA operands are is_gimple_min_invariant and
486 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
487 rank
= propagate_rank (rank
, op
);
489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
491 fprintf (dump_file
, "Rank for ");
492 print_generic_expr (dump_file
, e
, 0);
493 fprintf (dump_file
, " is %ld\n", (rank
+ 1));
496 /* Note the rank in the hashtable so we don't recompute it. */
497 insert_operand_rank (e
, (rank
+ 1));
501 /* Constants, globals, etc., are rank 0 */
506 /* We want integer ones to end up last no matter what, since they are
507 the ones we can do the most with. */
508 #define INTEGER_CONST_TYPE 1 << 3
509 #define FLOAT_CONST_TYPE 1 << 2
510 #define OTHER_CONST_TYPE 1 << 1
512 /* Classify an invariant tree into integer, float, or other, so that
513 we can sort them to be near other constants of the same type. */
515 constant_type (tree t
)
517 if (INTEGRAL_TYPE_P (TREE_TYPE (t
)))
518 return INTEGER_CONST_TYPE
;
519 else if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (t
)))
520 return FLOAT_CONST_TYPE
;
522 return OTHER_CONST_TYPE
;
525 /* qsort comparison function to sort operand entries PA and PB by rank
526 so that the sorted array is ordered by rank in decreasing order. */
528 sort_by_operand_rank (const void *pa
, const void *pb
)
530 const operand_entry_t oea
= *(const operand_entry_t
*)pa
;
531 const operand_entry_t oeb
= *(const operand_entry_t
*)pb
;
533 /* It's nicer for optimize_expression if constants that are likely
534 to fold when added/multiplied//whatever are put next to each
535 other. Since all constants have rank 0, order them by type. */
536 if (oeb
->rank
== 0 && oea
->rank
== 0)
538 if (constant_type (oeb
->op
) != constant_type (oea
->op
))
539 return constant_type (oeb
->op
) - constant_type (oea
->op
);
541 /* To make sorting result stable, we use unique IDs to determine
543 return oeb
->id
- oea
->id
;
546 /* Lastly, make sure the versions that are the same go next to each
548 if ((oeb
->rank
- oea
->rank
== 0)
549 && TREE_CODE (oea
->op
) == SSA_NAME
550 && TREE_CODE (oeb
->op
) == SSA_NAME
)
552 /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
553 versions of removed SSA_NAMEs, so if possible, prefer to sort
554 based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
556 if (!SSA_NAME_IS_DEFAULT_DEF (oea
->op
)
557 && !SSA_NAME_IS_DEFAULT_DEF (oeb
->op
)
558 && SSA_NAME_VERSION (oeb
->op
) != SSA_NAME_VERSION (oea
->op
))
560 gimple stmta
= SSA_NAME_DEF_STMT (oea
->op
);
561 gimple stmtb
= SSA_NAME_DEF_STMT (oeb
->op
);
562 basic_block bba
= gimple_bb (stmta
);
563 basic_block bbb
= gimple_bb (stmtb
);
566 if (bb_rank
[bbb
->index
] != bb_rank
[bba
->index
])
567 return bb_rank
[bbb
->index
] - bb_rank
[bba
->index
];
571 bool da
= reassoc_stmt_dominates_stmt_p (stmta
, stmtb
);
572 bool db
= reassoc_stmt_dominates_stmt_p (stmtb
, stmta
);
578 if (SSA_NAME_VERSION (oeb
->op
) != SSA_NAME_VERSION (oea
->op
))
579 return SSA_NAME_VERSION (oeb
->op
) - SSA_NAME_VERSION (oea
->op
);
581 return oeb
->id
- oea
->id
;
584 if (oeb
->rank
!= oea
->rank
)
585 return oeb
->rank
- oea
->rank
;
587 return oeb
->id
- oea
->id
;
590 /* Add an operand entry to *OPS for the tree operand OP. */
593 add_to_ops_vec (vec
<operand_entry_t
> *ops
, tree op
)
595 operand_entry_t oe
= (operand_entry_t
) pool_alloc (operand_entry_pool
);
598 oe
->rank
= get_rank (op
);
599 oe
->id
= next_operand_entry_id
++;
604 /* Add an operand entry to *OPS for the tree operand OP with repeat
608 add_repeat_to_ops_vec (vec
<operand_entry_t
> *ops
, tree op
,
609 HOST_WIDE_INT repeat
)
611 operand_entry_t oe
= (operand_entry_t
) pool_alloc (operand_entry_pool
);
614 oe
->rank
= get_rank (op
);
615 oe
->id
= next_operand_entry_id
++;
619 reassociate_stats
.pows_encountered
++;
622 /* Return true if STMT is reassociable operation containing a binary
623 operation with tree code CODE, and is inside LOOP. */
626 is_reassociable_op (gimple stmt
, enum tree_code code
, struct loop
*loop
)
628 basic_block bb
= gimple_bb (stmt
);
630 if (gimple_bb (stmt
) == NULL
)
633 if (!flow_bb_inside_loop_p (loop
, bb
))
636 if (is_gimple_assign (stmt
)
637 && gimple_assign_rhs_code (stmt
) == code
638 && has_single_use (gimple_assign_lhs (stmt
)))
645 /* Given NAME, if NAME is defined by a unary operation OPCODE, return the
646 operand of the negate operation. Otherwise, return NULL. */
649 get_unary_op (tree name
, enum tree_code opcode
)
651 gimple stmt
= SSA_NAME_DEF_STMT (name
);
653 if (!is_gimple_assign (stmt
))
656 if (gimple_assign_rhs_code (stmt
) == opcode
)
657 return gimple_assign_rhs1 (stmt
);
661 /* If CURR and LAST are a pair of ops that OPCODE allows us to
662 eliminate through equivalences, do so, remove them from OPS, and
663 return true. Otherwise, return false. */
666 eliminate_duplicate_pair (enum tree_code opcode
,
667 vec
<operand_entry_t
> *ops
,
670 operand_entry_t curr
,
671 operand_entry_t last
)
674 /* If we have two of the same op, and the opcode is & |, min, or max,
675 we can eliminate one of them.
676 If we have two of the same op, and the opcode is ^, we can
677 eliminate both of them. */
679 if (last
&& last
->op
== curr
->op
)
687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
689 fprintf (dump_file
, "Equivalence: ");
690 print_generic_expr (dump_file
, curr
->op
, 0);
691 fprintf (dump_file
, " [&|minmax] ");
692 print_generic_expr (dump_file
, last
->op
, 0);
693 fprintf (dump_file
, " -> ");
694 print_generic_stmt (dump_file
, last
->op
, 0);
697 ops
->ordered_remove (i
);
698 reassociate_stats
.ops_eliminated
++;
703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
705 fprintf (dump_file
, "Equivalence: ");
706 print_generic_expr (dump_file
, curr
->op
, 0);
707 fprintf (dump_file
, " ^ ");
708 print_generic_expr (dump_file
, last
->op
, 0);
709 fprintf (dump_file
, " -> nothing\n");
712 reassociate_stats
.ops_eliminated
+= 2;
714 if (ops
->length () == 2)
717 add_to_ops_vec (ops
, build_zero_cst (TREE_TYPE (last
->op
)));
722 ops
->ordered_remove (i
-1);
723 ops
->ordered_remove (i
-1);
735 static vec
<tree
> plus_negates
;
737 /* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
738 expression, look in OPS for a corresponding positive operation to cancel
739 it out. If we find one, remove the other from OPS, replace
740 OPS[CURRINDEX] with 0 or -1, respectively, and return true. Otherwise,
744 eliminate_plus_minus_pair (enum tree_code opcode
,
745 vec
<operand_entry_t
> *ops
,
746 unsigned int currindex
,
747 operand_entry_t curr
)
754 if (opcode
!= PLUS_EXPR
|| TREE_CODE (curr
->op
) != SSA_NAME
)
757 negateop
= get_unary_op (curr
->op
, NEGATE_EXPR
);
758 notop
= get_unary_op (curr
->op
, BIT_NOT_EXPR
);
759 if (negateop
== NULL_TREE
&& notop
== NULL_TREE
)
762 /* Any non-negated version will have a rank that is one less than
763 the current rank. So once we hit those ranks, if we don't find
766 for (i
= currindex
+ 1;
767 ops
->iterate (i
, &oe
)
768 && oe
->rank
>= curr
->rank
- 1 ;
771 if (oe
->op
== negateop
)
774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
776 fprintf (dump_file
, "Equivalence: ");
777 print_generic_expr (dump_file
, negateop
, 0);
778 fprintf (dump_file
, " + -");
779 print_generic_expr (dump_file
, oe
->op
, 0);
780 fprintf (dump_file
, " -> 0\n");
783 ops
->ordered_remove (i
);
784 add_to_ops_vec (ops
, build_zero_cst (TREE_TYPE (oe
->op
)));
785 ops
->ordered_remove (currindex
);
786 reassociate_stats
.ops_eliminated
++;
790 else if (oe
->op
== notop
)
792 tree op_type
= TREE_TYPE (oe
->op
);
794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
796 fprintf (dump_file
, "Equivalence: ");
797 print_generic_expr (dump_file
, notop
, 0);
798 fprintf (dump_file
, " + ~");
799 print_generic_expr (dump_file
, oe
->op
, 0);
800 fprintf (dump_file
, " -> -1\n");
803 ops
->ordered_remove (i
);
804 add_to_ops_vec (ops
, build_int_cst_type (op_type
, -1));
805 ops
->ordered_remove (currindex
);
806 reassociate_stats
.ops_eliminated
++;
812 /* CURR->OP is a negate expr in a plus expr: save it for later
813 inspection in repropagate_negates(). */
814 if (negateop
!= NULL_TREE
)
815 plus_negates
.safe_push (curr
->op
);
820 /* If OPCODE is BIT_IOR_EXPR, BIT_AND_EXPR, and, CURR->OP is really a
821 bitwise not expression, look in OPS for a corresponding operand to
822 cancel it out. If we find one, remove the other from OPS, replace
823 OPS[CURRINDEX] with 0, and return true. Otherwise, return
827 eliminate_not_pairs (enum tree_code opcode
,
828 vec
<operand_entry_t
> *ops
,
829 unsigned int currindex
,
830 operand_entry_t curr
)
836 if ((opcode
!= BIT_IOR_EXPR
&& opcode
!= BIT_AND_EXPR
)
837 || TREE_CODE (curr
->op
) != SSA_NAME
)
840 notop
= get_unary_op (curr
->op
, BIT_NOT_EXPR
);
841 if (notop
== NULL_TREE
)
844 /* Any non-not version will have a rank that is one less than
845 the current rank. So once we hit those ranks, if we don't find
848 for (i
= currindex
+ 1;
849 ops
->iterate (i
, &oe
)
850 && oe
->rank
>= curr
->rank
- 1;
855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
857 fprintf (dump_file
, "Equivalence: ");
858 print_generic_expr (dump_file
, notop
, 0);
859 if (opcode
== BIT_AND_EXPR
)
860 fprintf (dump_file
, " & ~");
861 else if (opcode
== BIT_IOR_EXPR
)
862 fprintf (dump_file
, " | ~");
863 print_generic_expr (dump_file
, oe
->op
, 0);
864 if (opcode
== BIT_AND_EXPR
)
865 fprintf (dump_file
, " -> 0\n");
866 else if (opcode
== BIT_IOR_EXPR
)
867 fprintf (dump_file
, " -> -1\n");
870 if (opcode
== BIT_AND_EXPR
)
871 oe
->op
= build_zero_cst (TREE_TYPE (oe
->op
));
872 else if (opcode
== BIT_IOR_EXPR
)
873 oe
->op
= build_all_ones_cst (TREE_TYPE (oe
->op
));
875 reassociate_stats
.ops_eliminated
+= ops
->length () - 1;
877 ops
->quick_push (oe
);
885 /* Use constant value that may be present in OPS to try to eliminate
886 operands. Note that this function is only really used when we've
887 eliminated ops for other reasons, or merged constants. Across
888 single statements, fold already does all of this, plus more. There
889 is little point in duplicating logic, so I've only included the
890 identities that I could ever construct testcases to trigger. */
893 eliminate_using_constants (enum tree_code opcode
,
894 vec
<operand_entry_t
> *ops
)
896 operand_entry_t oelast
= ops
->last ();
897 tree type
= TREE_TYPE (oelast
->op
);
899 if (oelast
->rank
== 0
900 && (INTEGRAL_TYPE_P (type
) || FLOAT_TYPE_P (type
)))
905 if (integer_zerop (oelast
->op
))
907 if (ops
->length () != 1)
909 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
910 fprintf (dump_file
, "Found & 0, removing all other ops\n");
912 reassociate_stats
.ops_eliminated
+= ops
->length () - 1;
915 ops
->quick_push (oelast
);
919 else if (integer_all_onesp (oelast
->op
))
921 if (ops
->length () != 1)
923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
924 fprintf (dump_file
, "Found & -1, removing\n");
926 reassociate_stats
.ops_eliminated
++;
931 if (integer_all_onesp (oelast
->op
))
933 if (ops
->length () != 1)
935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
936 fprintf (dump_file
, "Found | -1, removing all other ops\n");
938 reassociate_stats
.ops_eliminated
+= ops
->length () - 1;
941 ops
->quick_push (oelast
);
945 else if (integer_zerop (oelast
->op
))
947 if (ops
->length () != 1)
949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
950 fprintf (dump_file
, "Found | 0, removing\n");
952 reassociate_stats
.ops_eliminated
++;
957 if (integer_zerop (oelast
->op
)
958 || (FLOAT_TYPE_P (type
)
959 && !HONOR_NANS (type
)
960 && !HONOR_SIGNED_ZEROS (type
)
961 && real_zerop (oelast
->op
)))
963 if (ops
->length () != 1)
965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
966 fprintf (dump_file
, "Found * 0, removing all other ops\n");
968 reassociate_stats
.ops_eliminated
+= ops
->length () - 1;
970 ops
->quick_push (oelast
);
974 else if (integer_onep (oelast
->op
)
975 || (FLOAT_TYPE_P (type
)
976 && !HONOR_SNANS (type
)
977 && real_onep (oelast
->op
)))
979 if (ops
->length () != 1)
981 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
982 fprintf (dump_file
, "Found * 1, removing\n");
984 reassociate_stats
.ops_eliminated
++;
992 if (integer_zerop (oelast
->op
)
993 || (FLOAT_TYPE_P (type
)
994 && (opcode
== PLUS_EXPR
|| opcode
== MINUS_EXPR
)
995 && fold_real_zero_addition_p (type
, oelast
->op
,
996 opcode
== MINUS_EXPR
)))
998 if (ops
->length () != 1)
1000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1001 fprintf (dump_file
, "Found [|^+] 0, removing\n");
1003 reassociate_stats
.ops_eliminated
++;
1015 static void linearize_expr_tree (vec
<operand_entry_t
> *, gimple
,
1018 /* Structure for tracking and counting operands. */
1019 typedef struct oecount_s
{
1022 enum tree_code oecode
;
1027 /* The heap for the oecount hashtable and the sorted list of operands. */
1028 static vec
<oecount
> cvec
;
1031 /* Oecount hashtable helpers. */
1033 struct oecount_hasher
1035 typedef int value_type
;
1036 typedef int compare_type
;
1037 static inline hashval_t
hash (const value_type
&);
1038 static inline bool equal (const value_type
&, const compare_type
&);
1039 static bool is_deleted (int &v
) { return v
== 1; }
1040 static void mark_deleted (int &e
) { e
= 1; }
1041 static bool is_empty (int &v
) { return v
== 0; }
1042 static void mark_empty (int &e
) { e
= 0; }
1043 static void remove (int &) {}
1046 /* Hash function for oecount. */
1049 oecount_hasher::hash (const value_type
&p
)
1051 const oecount
*c
= &cvec
[p
- 42];
1052 return htab_hash_pointer (c
->op
) ^ (hashval_t
)c
->oecode
;
1055 /* Comparison function for oecount. */
1058 oecount_hasher::equal (const value_type
&p1
, const compare_type
&p2
)
1060 const oecount
*c1
= &cvec
[p1
- 42];
1061 const oecount
*c2
= &cvec
[p2
- 42];
1062 return (c1
->oecode
== c2
->oecode
1063 && c1
->op
== c2
->op
);
1066 /* Comparison function for qsort sorting oecount elements by count. */
1069 oecount_cmp (const void *p1
, const void *p2
)
1071 const oecount
*c1
= (const oecount
*)p1
;
1072 const oecount
*c2
= (const oecount
*)p2
;
1073 if (c1
->cnt
!= c2
->cnt
)
1074 return c1
->cnt
- c2
->cnt
;
1076 /* If counts are identical, use unique IDs to stabilize qsort. */
1077 return c1
->id
- c2
->id
;
1080 /* Return TRUE iff STMT represents a builtin call that raises OP
1081 to some exponent. */
1084 stmt_is_power_of_op (gimple stmt
, tree op
)
1088 if (!is_gimple_call (stmt
))
1091 fndecl
= gimple_call_fndecl (stmt
);
1094 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
1097 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
1099 CASE_FLT_FN (BUILT_IN_POW
):
1100 CASE_FLT_FN (BUILT_IN_POWI
):
1101 return (operand_equal_p (gimple_call_arg (stmt
, 0), op
, 0));
1108 /* Given STMT which is a __builtin_pow* call, decrement its exponent
1109 in place and return the result. Assumes that stmt_is_power_of_op
1110 was previously called for STMT and returned TRUE. */
1112 static HOST_WIDE_INT
1113 decrement_power (gimple stmt
)
1115 REAL_VALUE_TYPE c
, cint
;
1116 HOST_WIDE_INT power
;
1119 switch (DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
)))
1121 CASE_FLT_FN (BUILT_IN_POW
):
1122 arg1
= gimple_call_arg (stmt
, 1);
1123 c
= TREE_REAL_CST (arg1
);
1124 power
= real_to_integer (&c
) - 1;
1125 real_from_integer (&cint
, VOIDmode
, power
, SIGNED
);
1126 gimple_call_set_arg (stmt
, 1, build_real (TREE_TYPE (arg1
), cint
));
1129 CASE_FLT_FN (BUILT_IN_POWI
):
1130 arg1
= gimple_call_arg (stmt
, 1);
1131 power
= TREE_INT_CST_LOW (arg1
) - 1;
1132 gimple_call_set_arg (stmt
, 1, build_int_cst (TREE_TYPE (arg1
), power
));
1140 /* Find the single immediate use of STMT's LHS, and replace it
1141 with OP. Remove STMT. If STMT's LHS is the same as *DEF,
1142 replace *DEF with OP as well. */
1145 propagate_op_to_single_use (tree op
, gimple stmt
, tree
*def
)
1150 gimple_stmt_iterator gsi
;
1152 if (is_gimple_call (stmt
))
1153 lhs
= gimple_call_lhs (stmt
);
1155 lhs
= gimple_assign_lhs (stmt
);
1157 gcc_assert (has_single_use (lhs
));
1158 single_imm_use (lhs
, &use
, &use_stmt
);
1162 if (TREE_CODE (op
) != SSA_NAME
)
1163 update_stmt (use_stmt
);
1164 gsi
= gsi_for_stmt (stmt
);
1165 unlink_stmt_vdef (stmt
);
1166 reassoc_remove_stmt (&gsi
);
1167 release_defs (stmt
);
1170 /* Walks the linear chain with result *DEF searching for an operation
1171 with operand OP and code OPCODE removing that from the chain. *DEF
1172 is updated if there is only one operand but no operation left. */
1175 zero_one_operation (tree
*def
, enum tree_code opcode
, tree op
)
1177 gimple stmt
= SSA_NAME_DEF_STMT (*def
);
1183 if (opcode
== MULT_EXPR
1184 && stmt_is_power_of_op (stmt
, op
))
1186 if (decrement_power (stmt
) == 1)
1187 propagate_op_to_single_use (op
, stmt
, def
);
1191 name
= gimple_assign_rhs1 (stmt
);
1193 /* If this is the operation we look for and one of the operands
1194 is ours simply propagate the other operand into the stmts
1196 if (gimple_assign_rhs_code (stmt
) == opcode
1198 || gimple_assign_rhs2 (stmt
) == op
))
1201 name
= gimple_assign_rhs2 (stmt
);
1202 propagate_op_to_single_use (name
, stmt
, def
);
1206 /* We might have a multiply of two __builtin_pow* calls, and
1207 the operand might be hiding in the rightmost one. */
1208 if (opcode
== MULT_EXPR
1209 && gimple_assign_rhs_code (stmt
) == opcode
1210 && TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
1211 && has_single_use (gimple_assign_rhs2 (stmt
)))
1213 gimple stmt2
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
1214 if (stmt_is_power_of_op (stmt2
, op
))
1216 if (decrement_power (stmt2
) == 1)
1217 propagate_op_to_single_use (op
, stmt2
, def
);
1222 /* Continue walking the chain. */
1223 gcc_assert (name
!= op
1224 && TREE_CODE (name
) == SSA_NAME
);
1225 stmt
= SSA_NAME_DEF_STMT (name
);
1230 /* Returns true if statement S1 dominates statement S2. Like
1231 stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
1234 reassoc_stmt_dominates_stmt_p (gimple s1
, gimple s2
)
1236 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
1238 /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
1239 SSA_NAME. Assume it lives at the beginning of function and
1240 thus dominates everything. */
1241 if (!bb1
|| s1
== s2
)
1244 /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
1250 /* PHIs in the same basic block are assumed to be
1251 executed all in parallel, if only one stmt is a PHI,
1252 it dominates the other stmt in the same basic block. */
1253 if (gimple_code (s1
) == GIMPLE_PHI
)
1256 if (gimple_code (s2
) == GIMPLE_PHI
)
1259 gcc_assert (gimple_uid (s1
) && gimple_uid (s2
));
1261 if (gimple_uid (s1
) < gimple_uid (s2
))
1264 if (gimple_uid (s1
) > gimple_uid (s2
))
1267 gimple_stmt_iterator gsi
= gsi_for_stmt (s1
);
1268 unsigned int uid
= gimple_uid (s1
);
1269 for (gsi_next (&gsi
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1271 gimple s
= gsi_stmt (gsi
);
1272 if (gimple_uid (s
) != uid
)
1281 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
1284 /* Insert STMT after INSERT_POINT. */
1287 insert_stmt_after (gimple stmt
, gimple insert_point
)
1289 gimple_stmt_iterator gsi
;
1292 if (gimple_code (insert_point
) == GIMPLE_PHI
)
1293 bb
= gimple_bb (insert_point
);
1294 else if (!stmt_ends_bb_p (insert_point
))
1296 gsi
= gsi_for_stmt (insert_point
);
1297 gimple_set_uid (stmt
, gimple_uid (insert_point
));
1298 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1302 /* We assume INSERT_POINT is a SSA_NAME_DEF_STMT of some SSA_NAME,
1303 thus if it must end a basic block, it should be a call that can
1304 throw, or some assignment that can throw. If it throws, the LHS
1305 of it will not be initialized though, so only valid places using
1306 the SSA_NAME should be dominated by the fallthru edge. */
1307 bb
= find_fallthru_edge (gimple_bb (insert_point
)->succs
)->dest
;
1308 gsi
= gsi_after_labels (bb
);
1309 if (gsi_end_p (gsi
))
1311 gimple_stmt_iterator gsi2
= gsi_last_bb (bb
);
1312 gimple_set_uid (stmt
,
1313 gsi_end_p (gsi2
) ? 1 : gimple_uid (gsi_stmt (gsi2
)));
1316 gimple_set_uid (stmt
, gimple_uid (gsi_stmt (gsi
)));
1317 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1320 /* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
1321 the result. Places the statement after the definition of either
1322 OP1 or OP2. Returns the new statement. */
1325 build_and_add_sum (tree type
, tree op1
, tree op2
, enum tree_code opcode
)
1327 gimple op1def
= NULL
, op2def
= NULL
;
1328 gimple_stmt_iterator gsi
;
1332 /* Create the addition statement. */
1333 op
= make_ssa_name (type
);
1334 sum
= gimple_build_assign (op
, opcode
, op1
, op2
);
1336 /* Find an insertion place and insert. */
1337 if (TREE_CODE (op1
) == SSA_NAME
)
1338 op1def
= SSA_NAME_DEF_STMT (op1
);
1339 if (TREE_CODE (op2
) == SSA_NAME
)
1340 op2def
= SSA_NAME_DEF_STMT (op2
);
1341 if ((!op1def
|| gimple_nop_p (op1def
))
1342 && (!op2def
|| gimple_nop_p (op2def
)))
1344 gsi
= gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1345 if (gsi_end_p (gsi
))
1347 gimple_stmt_iterator gsi2
1348 = gsi_last_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
1349 gimple_set_uid (sum
,
1350 gsi_end_p (gsi2
) ? 1 : gimple_uid (gsi_stmt (gsi2
)));
1353 gimple_set_uid (sum
, gimple_uid (gsi_stmt (gsi
)));
1354 gsi_insert_before (&gsi
, sum
, GSI_NEW_STMT
);
1358 gimple insert_point
;
1359 if ((!op1def
|| gimple_nop_p (op1def
))
1360 || (op2def
&& !gimple_nop_p (op2def
)
1361 && reassoc_stmt_dominates_stmt_p (op1def
, op2def
)))
1362 insert_point
= op2def
;
1364 insert_point
= op1def
;
1365 insert_stmt_after (sum
, insert_point
);
1372 /* Perform un-distribution of divisions and multiplications.
1373 A * X + B * X is transformed into (A + B) * X and A / X + B / X
1374 to (A + B) / X for real X.
1376 The algorithm is organized as follows.
1378 - First we walk the addition chain *OPS looking for summands that
1379 are defined by a multiplication or a real division. This results
1380 in the candidates bitmap with relevant indices into *OPS.
1382 - Second we build the chains of multiplications or divisions for
1383 these candidates, counting the number of occurrences of (operand, code)
1384 pairs in all of the candidates chains.
1386 - Third we sort the (operand, code) pairs by number of occurrence and
1387 process them starting with the pair with the most uses.
1389 * For each such pair we walk the candidates again to build a
1390 second candidate bitmap noting all multiplication/division chains
1391 that have at least one occurrence of (operand, code).
1393 * We build an alternate addition chain only covering these
1394 candidates with one (operand, code) operation removed from their
1395 multiplication/division chain.
1397 * The first candidate gets replaced by the alternate addition chain
1398 multiplied/divided by the operand.
1400 * All candidate chains get disabled for further processing and
1401 processing of (operand, code) pairs continues.
1403 The alternate addition chains built are re-processed by the main
1404 reassociation algorithm which allows optimizing a * x * y + b * y * x
1405 to (a + b ) * x * y in one invocation of the reassociation pass. */
1408 undistribute_ops_list (enum tree_code opcode
,
1409 vec
<operand_entry_t
> *ops
, struct loop
*loop
)
1411 unsigned int length
= ops
->length ();
1412 operand_entry_t oe1
;
1414 sbitmap candidates
, candidates2
;
1415 unsigned nr_candidates
, nr_candidates2
;
1416 sbitmap_iterator sbi0
;
1417 vec
<operand_entry_t
> *subops
;
1418 bool changed
= false;
1419 int next_oecount_id
= 0;
1422 || opcode
!= PLUS_EXPR
)
1425 /* Build a list of candidates to process. */
1426 candidates
= sbitmap_alloc (length
);
1427 bitmap_clear (candidates
);
1429 FOR_EACH_VEC_ELT (*ops
, i
, oe1
)
1431 enum tree_code dcode
;
1434 if (TREE_CODE (oe1
->op
) != SSA_NAME
)
1436 oe1def
= SSA_NAME_DEF_STMT (oe1
->op
);
1437 if (!is_gimple_assign (oe1def
))
1439 dcode
= gimple_assign_rhs_code (oe1def
);
1440 if ((dcode
!= MULT_EXPR
1441 && dcode
!= RDIV_EXPR
)
1442 || !is_reassociable_op (oe1def
, dcode
, loop
))
1445 bitmap_set_bit (candidates
, i
);
1449 if (nr_candidates
< 2)
1451 sbitmap_free (candidates
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1457 fprintf (dump_file
, "searching for un-distribute opportunities ");
1458 print_generic_expr (dump_file
,
1459 (*ops
)[bitmap_first_set_bit (candidates
)]->op
, 0);
1460 fprintf (dump_file
, " %d\n", nr_candidates
);
1463 /* Build linearized sub-operand lists and the counting table. */
1466 hash_table
<oecount_hasher
> ctable (15);
1468 /* ??? Macro arguments cannot have multi-argument template types in
1469 them. This typedef is needed to workaround that limitation. */
1470 typedef vec
<operand_entry_t
> vec_operand_entry_t_heap
;
1471 subops
= XCNEWVEC (vec_operand_entry_t_heap
, ops
->length ());
1472 EXECUTE_IF_SET_IN_BITMAP (candidates
, 0, i
, sbi0
)
1475 enum tree_code oecode
;
1478 oedef
= SSA_NAME_DEF_STMT ((*ops
)[i
]->op
);
1479 oecode
= gimple_assign_rhs_code (oedef
);
1480 linearize_expr_tree (&subops
[i
], oedef
,
1481 associative_tree_code (oecode
), false);
1483 FOR_EACH_VEC_ELT (subops
[i
], j
, oe1
)
1490 c
.id
= next_oecount_id
++;
1493 idx
= cvec
.length () + 41;
1494 slot
= ctable
.find_slot (idx
, INSERT
);
1502 cvec
[*slot
- 42].cnt
++;
1507 /* Sort the counting table. */
1508 cvec
.qsort (oecount_cmp
);
1510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1513 fprintf (dump_file
, "Candidates:\n");
1514 FOR_EACH_VEC_ELT (cvec
, j
, c
)
1516 fprintf (dump_file
, " %u %s: ", c
->cnt
,
1517 c
->oecode
== MULT_EXPR
1518 ? "*" : c
->oecode
== RDIV_EXPR
? "/" : "?");
1519 print_generic_expr (dump_file
, c
->op
, 0);
1520 fprintf (dump_file
, "\n");
1524 /* Process the (operand, code) pairs in order of most occurrence. */
1525 candidates2
= sbitmap_alloc (length
);
1526 while (!cvec
.is_empty ())
1528 oecount
*c
= &cvec
.last ();
1532 /* Now collect the operands in the outer chain that contain
1533 the common operand in their inner chain. */
1534 bitmap_clear (candidates2
);
1536 EXECUTE_IF_SET_IN_BITMAP (candidates
, 0, i
, sbi0
)
1539 enum tree_code oecode
;
1541 tree op
= (*ops
)[i
]->op
;
1543 /* If we undistributed in this chain already this may be
1545 if (TREE_CODE (op
) != SSA_NAME
)
1548 oedef
= SSA_NAME_DEF_STMT (op
);
1549 oecode
= gimple_assign_rhs_code (oedef
);
1550 if (oecode
!= c
->oecode
)
1553 FOR_EACH_VEC_ELT (subops
[i
], j
, oe1
)
1555 if (oe1
->op
== c
->op
)
1557 bitmap_set_bit (candidates2
, i
);
1564 if (nr_candidates2
>= 2)
1566 operand_entry_t oe1
, oe2
;
1568 int first
= bitmap_first_set_bit (candidates2
);
1570 /* Build the new addition chain. */
1571 oe1
= (*ops
)[first
];
1572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1574 fprintf (dump_file
, "Building (");
1575 print_generic_expr (dump_file
, oe1
->op
, 0);
1577 zero_one_operation (&oe1
->op
, c
->oecode
, c
->op
);
1578 EXECUTE_IF_SET_IN_BITMAP (candidates2
, first
+1, i
, sbi0
)
1582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1584 fprintf (dump_file
, " + ");
1585 print_generic_expr (dump_file
, oe2
->op
, 0);
1587 zero_one_operation (&oe2
->op
, c
->oecode
, c
->op
);
1588 sum
= build_and_add_sum (TREE_TYPE (oe1
->op
),
1589 oe1
->op
, oe2
->op
, opcode
);
1590 oe2
->op
= build_zero_cst (TREE_TYPE (oe2
->op
));
1592 oe1
->op
= gimple_get_lhs (sum
);
1595 /* Apply the multiplication/division. */
1596 prod
= build_and_add_sum (TREE_TYPE (oe1
->op
),
1597 oe1
->op
, c
->op
, c
->oecode
);
1598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1600 fprintf (dump_file
, ") %s ", c
->oecode
== MULT_EXPR
? "*" : "/");
1601 print_generic_expr (dump_file
, c
->op
, 0);
1602 fprintf (dump_file
, "\n");
1605 /* Record it in the addition chain and disable further
1606 undistribution with this op. */
1607 oe1
->op
= gimple_assign_lhs (prod
);
1608 oe1
->rank
= get_rank (oe1
->op
);
1609 subops
[first
].release ();
1617 for (i
= 0; i
< ops
->length (); ++i
)
1618 subops
[i
].release ();
1621 sbitmap_free (candidates
);
1622 sbitmap_free (candidates2
);
1627 /* If OPCODE is BIT_IOR_EXPR or BIT_AND_EXPR and CURR is a comparison
1628 expression, examine the other OPS to see if any of them are comparisons
1629 of the same values, which we may be able to combine or eliminate.
1630 For example, we can rewrite (a < b) | (a == b) as (a <= b). */
1633 eliminate_redundant_comparison (enum tree_code opcode
,
1634 vec
<operand_entry_t
> *ops
,
1635 unsigned int currindex
,
1636 operand_entry_t curr
)
1639 enum tree_code lcode
, rcode
;
1644 if (opcode
!= BIT_IOR_EXPR
&& opcode
!= BIT_AND_EXPR
)
1647 /* Check that CURR is a comparison. */
1648 if (TREE_CODE (curr
->op
) != SSA_NAME
)
1650 def1
= SSA_NAME_DEF_STMT (curr
->op
);
1651 if (!is_gimple_assign (def1
))
1653 lcode
= gimple_assign_rhs_code (def1
);
1654 if (TREE_CODE_CLASS (lcode
) != tcc_comparison
)
1656 op1
= gimple_assign_rhs1 (def1
);
1657 op2
= gimple_assign_rhs2 (def1
);
1659 /* Now look for a similar comparison in the remaining OPS. */
1660 for (i
= currindex
+ 1; ops
->iterate (i
, &oe
); i
++)
1664 if (TREE_CODE (oe
->op
) != SSA_NAME
)
1666 def2
= SSA_NAME_DEF_STMT (oe
->op
);
1667 if (!is_gimple_assign (def2
))
1669 rcode
= gimple_assign_rhs_code (def2
);
1670 if (TREE_CODE_CLASS (rcode
) != tcc_comparison
)
1673 /* If we got here, we have a match. See if we can combine the
1675 if (opcode
== BIT_IOR_EXPR
)
1676 t
= maybe_fold_or_comparisons (lcode
, op1
, op2
,
1677 rcode
, gimple_assign_rhs1 (def2
),
1678 gimple_assign_rhs2 (def2
));
1680 t
= maybe_fold_and_comparisons (lcode
, op1
, op2
,
1681 rcode
, gimple_assign_rhs1 (def2
),
1682 gimple_assign_rhs2 (def2
));
1686 /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
1687 always give us a boolean_type_node value back. If the original
1688 BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
1689 we need to convert. */
1690 if (!useless_type_conversion_p (TREE_TYPE (curr
->op
), TREE_TYPE (t
)))
1691 t
= fold_convert (TREE_TYPE (curr
->op
), t
);
1693 if (TREE_CODE (t
) != INTEGER_CST
1694 && !operand_equal_p (t
, curr
->op
, 0))
1696 enum tree_code subcode
;
1697 tree newop1
, newop2
;
1698 if (!COMPARISON_CLASS_P (t
))
1700 extract_ops_from_tree (t
, &subcode
, &newop1
, &newop2
);
1701 STRIP_USELESS_TYPE_CONVERSION (newop1
);
1702 STRIP_USELESS_TYPE_CONVERSION (newop2
);
1703 if (!is_gimple_val (newop1
) || !is_gimple_val (newop2
))
1707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1709 fprintf (dump_file
, "Equivalence: ");
1710 print_generic_expr (dump_file
, curr
->op
, 0);
1711 fprintf (dump_file
, " %s ", op_symbol_code (opcode
));
1712 print_generic_expr (dump_file
, oe
->op
, 0);
1713 fprintf (dump_file
, " -> ");
1714 print_generic_expr (dump_file
, t
, 0);
1715 fprintf (dump_file
, "\n");
1718 /* Now we can delete oe, as it has been subsumed by the new combined
1720 ops
->ordered_remove (i
);
1721 reassociate_stats
.ops_eliminated
++;
1723 /* If t is the same as curr->op, we're done. Otherwise we must
1724 replace curr->op with t. Special case is if we got a constant
1725 back, in which case we add it to the end instead of in place of
1726 the current entry. */
1727 if (TREE_CODE (t
) == INTEGER_CST
)
1729 ops
->ordered_remove (currindex
);
1730 add_to_ops_vec (ops
, t
);
1732 else if (!operand_equal_p (t
, curr
->op
, 0))
1735 enum tree_code subcode
;
1738 gcc_assert (COMPARISON_CLASS_P (t
));
1739 extract_ops_from_tree (t
, &subcode
, &newop1
, &newop2
);
1740 STRIP_USELESS_TYPE_CONVERSION (newop1
);
1741 STRIP_USELESS_TYPE_CONVERSION (newop2
);
1742 gcc_checking_assert (is_gimple_val (newop1
)
1743 && is_gimple_val (newop2
));
1744 sum
= build_and_add_sum (TREE_TYPE (t
), newop1
, newop2
, subcode
);
1745 curr
->op
= gimple_get_lhs (sum
);
1753 /* Perform various identities and other optimizations on the list of
1754 operand entries, stored in OPS. The tree code for the binary
1755 operation between all the operands is OPCODE. */
1758 optimize_ops_list (enum tree_code opcode
,
1759 vec
<operand_entry_t
> *ops
)
1761 unsigned int length
= ops
->length ();
1764 operand_entry_t oelast
= NULL
;
1765 bool iterate
= false;
1770 oelast
= ops
->last ();
1772 /* If the last two are constants, pop the constants off, merge them
1773 and try the next two. */
1774 if (oelast
->rank
== 0 && is_gimple_min_invariant (oelast
->op
))
1776 operand_entry_t oelm1
= (*ops
)[length
- 2];
1778 if (oelm1
->rank
== 0
1779 && is_gimple_min_invariant (oelm1
->op
)
1780 && useless_type_conversion_p (TREE_TYPE (oelm1
->op
),
1781 TREE_TYPE (oelast
->op
)))
1783 tree folded
= fold_binary (opcode
, TREE_TYPE (oelm1
->op
),
1784 oelm1
->op
, oelast
->op
);
1786 if (folded
&& is_gimple_min_invariant (folded
))
1788 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1789 fprintf (dump_file
, "Merging constants\n");
1794 add_to_ops_vec (ops
, folded
);
1795 reassociate_stats
.constants_eliminated
++;
1797 optimize_ops_list (opcode
, ops
);
1803 eliminate_using_constants (opcode
, ops
);
1806 for (i
= 0; ops
->iterate (i
, &oe
);)
1810 if (eliminate_not_pairs (opcode
, ops
, i
, oe
))
1812 if (eliminate_duplicate_pair (opcode
, ops
, &done
, i
, oe
, oelast
)
1813 || (!done
&& eliminate_plus_minus_pair (opcode
, ops
, i
, oe
))
1814 || (!done
&& eliminate_redundant_comparison (opcode
, ops
, i
, oe
)))
1826 length
= ops
->length ();
1827 oelast
= ops
->last ();
1830 optimize_ops_list (opcode
, ops
);
1833 /* The following functions are subroutines to optimize_range_tests and allow
1834 it to try to change a logical combination of comparisons into a range
1838 X == 2 || X == 5 || X == 3 || X == 4
1842 (unsigned) (X - 2) <= 3
1844 For more information see comments above fold_test_range in fold-const.c,
1845 this implementation is for GIMPLE. */
1853 bool strict_overflow_p
;
1854 unsigned int idx
, next
;
1857 /* This is similar to make_range in fold-const.c, but on top of
1858 GIMPLE instead of trees. If EXP is non-NULL, it should be
1859 an SSA_NAME and STMT argument is ignored, otherwise STMT
1860 argument should be a GIMPLE_COND. */
1863 init_range_entry (struct range_entry
*r
, tree exp
, gimple stmt
)
1867 bool is_bool
, strict_overflow_p
;
1871 r
->strict_overflow_p
= false;
1873 r
->high
= NULL_TREE
;
1874 if (exp
!= NULL_TREE
1875 && (TREE_CODE (exp
) != SSA_NAME
|| !INTEGRAL_TYPE_P (TREE_TYPE (exp
))))
1878 /* Start with simply saying "EXP != 0" and then look at the code of EXP
1879 and see if we can refine the range. Some of the cases below may not
1880 happen, but it doesn't seem worth worrying about this. We "continue"
1881 the outer loop when we've changed something; otherwise we "break"
1882 the switch, which will "break" the while. */
1883 low
= exp
? build_int_cst (TREE_TYPE (exp
), 0) : boolean_false_node
;
1886 strict_overflow_p
= false;
1888 if (exp
== NULL_TREE
)
1890 else if (TYPE_PRECISION (TREE_TYPE (exp
)) == 1)
1892 if (TYPE_UNSIGNED (TREE_TYPE (exp
)))
1897 else if (TREE_CODE (TREE_TYPE (exp
)) == BOOLEAN_TYPE
)
1902 enum tree_code code
;
1903 tree arg0
, arg1
, exp_type
;
1907 if (exp
!= NULL_TREE
)
1909 if (TREE_CODE (exp
) != SSA_NAME
1910 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
1913 stmt
= SSA_NAME_DEF_STMT (exp
);
1914 if (!is_gimple_assign (stmt
))
1917 code
= gimple_assign_rhs_code (stmt
);
1918 arg0
= gimple_assign_rhs1 (stmt
);
1919 arg1
= gimple_assign_rhs2 (stmt
);
1920 exp_type
= TREE_TYPE (exp
);
1924 code
= gimple_cond_code (stmt
);
1925 arg0
= gimple_cond_lhs (stmt
);
1926 arg1
= gimple_cond_rhs (stmt
);
1927 exp_type
= boolean_type_node
;
1930 if (TREE_CODE (arg0
) != SSA_NAME
)
1932 loc
= gimple_location (stmt
);
1936 if (TREE_CODE (TREE_TYPE (exp
)) == BOOLEAN_TYPE
1937 /* Ensure the range is either +[-,0], +[0,0],
1938 -[-,0], -[0,0] or +[1,-], +[1,1], -[1,-] or
1939 -[1,1]. If it is e.g. +[-,-] or -[-,-]
1940 or similar expression of unconditional true or
1941 false, it should not be negated. */
1942 && ((high
&& integer_zerop (high
))
1943 || (low
&& integer_onep (low
))))
1956 if (TYPE_PRECISION (TREE_TYPE (arg0
)) == 1)
1958 if (TYPE_UNSIGNED (TREE_TYPE (arg0
)))
1963 else if (TREE_CODE (TREE_TYPE (arg0
)) == BOOLEAN_TYPE
)
1978 nexp
= make_range_step (loc
, code
, arg0
, arg1
, exp_type
,
1980 &strict_overflow_p
);
1981 if (nexp
!= NULL_TREE
)
1984 gcc_assert (TREE_CODE (exp
) == SSA_NAME
);
1997 r
->strict_overflow_p
= strict_overflow_p
;
2001 /* Comparison function for qsort. Sort entries
2002 without SSA_NAME exp first, then with SSA_NAMEs sorted
2003 by increasing SSA_NAME_VERSION, and for the same SSA_NAMEs
2004 by increasing ->low and if ->low is the same, by increasing
2005 ->high. ->low == NULL_TREE means minimum, ->high == NULL_TREE
2009 range_entry_cmp (const void *a
, const void *b
)
2011 const struct range_entry
*p
= (const struct range_entry
*) a
;
2012 const struct range_entry
*q
= (const struct range_entry
*) b
;
2014 if (p
->exp
!= NULL_TREE
&& TREE_CODE (p
->exp
) == SSA_NAME
)
2016 if (q
->exp
!= NULL_TREE
&& TREE_CODE (q
->exp
) == SSA_NAME
)
2018 /* Group range_entries for the same SSA_NAME together. */
2019 if (SSA_NAME_VERSION (p
->exp
) < SSA_NAME_VERSION (q
->exp
))
2021 else if (SSA_NAME_VERSION (p
->exp
) > SSA_NAME_VERSION (q
->exp
))
2023 /* If ->low is different, NULL low goes first, then by
2025 if (p
->low
!= NULL_TREE
)
2027 if (q
->low
!= NULL_TREE
)
2029 tree tem
= fold_binary (LT_EXPR
, boolean_type_node
,
2031 if (tem
&& integer_onep (tem
))
2033 tem
= fold_binary (GT_EXPR
, boolean_type_node
,
2035 if (tem
&& integer_onep (tem
))
2041 else if (q
->low
!= NULL_TREE
)
2043 /* If ->high is different, NULL high goes last, before that by
2045 if (p
->high
!= NULL_TREE
)
2047 if (q
->high
!= NULL_TREE
)
2049 tree tem
= fold_binary (LT_EXPR
, boolean_type_node
,
2051 if (tem
&& integer_onep (tem
))
2053 tem
= fold_binary (GT_EXPR
, boolean_type_node
,
2055 if (tem
&& integer_onep (tem
))
2061 else if (q
->high
!= NULL_TREE
)
2063 /* If both ranges are the same, sort below by ascending idx. */
2068 else if (q
->exp
!= NULL_TREE
&& TREE_CODE (q
->exp
) == SSA_NAME
)
2071 if (p
->idx
< q
->idx
)
2075 gcc_checking_assert (p
->idx
> q
->idx
);
2080 /* Helper routine of optimize_range_test.
2081 [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
2082 RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
2083 OPCODE and OPS are arguments of optimize_range_tests. If OTHERRANGE
2084 is NULL, OTHERRANGEP should not be and then OTHERRANGEP points to
2085 an array of COUNT pointers to other ranges. Return
2086 true if the range merge has been successful.
2087 If OPCODE is ERROR_MARK, this is called from within
2088 maybe_optimize_range_tests and is performing inter-bb range optimization.
2089 In that case, whether an op is BIT_AND_EXPR or BIT_IOR_EXPR is found in
2093 update_range_test (struct range_entry
*range
, struct range_entry
*otherrange
,
2094 struct range_entry
**otherrangep
,
2095 unsigned int count
, enum tree_code opcode
,
2096 vec
<operand_entry_t
> *ops
, tree exp
, gimple_seq seq
,
2097 bool in_p
, tree low
, tree high
, bool strict_overflow_p
)
2099 operand_entry_t oe
= (*ops
)[range
->idx
];
2101 gimple stmt
= op
? SSA_NAME_DEF_STMT (op
) :
2102 last_stmt (BASIC_BLOCK_FOR_FN (cfun
, oe
->id
));
2103 location_t loc
= gimple_location (stmt
);
2104 tree optype
= op
? TREE_TYPE (op
) : boolean_type_node
;
2105 tree tem
= build_range_check (loc
, optype
, unshare_expr (exp
),
2107 enum warn_strict_overflow_code wc
= WARN_STRICT_OVERFLOW_COMPARISON
;
2108 gimple_stmt_iterator gsi
;
2111 if (tem
== NULL_TREE
)
2114 if (strict_overflow_p
&& issue_strict_overflow_warning (wc
))
2115 warning_at (loc
, OPT_Wstrict_overflow
,
2116 "assuming signed overflow does not occur "
2117 "when simplifying range test");
2119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2121 struct range_entry
*r
;
2122 fprintf (dump_file
, "Optimizing range tests ");
2123 print_generic_expr (dump_file
, range
->exp
, 0);
2124 fprintf (dump_file
, " %c[", range
->in_p
? '+' : '-');
2125 print_generic_expr (dump_file
, range
->low
, 0);
2126 fprintf (dump_file
, ", ");
2127 print_generic_expr (dump_file
, range
->high
, 0);
2128 fprintf (dump_file
, "]");
2129 for (i
= 0; i
< count
; i
++)
2135 fprintf (dump_file
, " and %c[", r
->in_p
? '+' : '-');
2136 print_generic_expr (dump_file
, r
->low
, 0);
2137 fprintf (dump_file
, ", ");
2138 print_generic_expr (dump_file
, r
->high
, 0);
2139 fprintf (dump_file
, "]");
2141 fprintf (dump_file
, "\n into ");
2142 print_generic_expr (dump_file
, tem
, 0);
2143 fprintf (dump_file
, "\n");
2146 if (opcode
== BIT_IOR_EXPR
2147 || (opcode
== ERROR_MARK
&& oe
->rank
== BIT_IOR_EXPR
))
2148 tem
= invert_truthvalue_loc (loc
, tem
);
2150 tem
= fold_convert_loc (loc
, optype
, tem
);
2151 gsi
= gsi_for_stmt (stmt
);
2152 unsigned int uid
= gimple_uid (stmt
);
2153 /* In rare cases range->exp can be equal to lhs of stmt.
2154 In that case we have to insert after the stmt rather then before
2155 it. If stmt is a PHI, insert it at the start of the basic block. */
2156 if (op
!= range
->exp
)
2158 gsi_insert_seq_before (&gsi
, seq
, GSI_SAME_STMT
);
2159 tem
= force_gimple_operand_gsi (&gsi
, tem
, true, NULL_TREE
, true,
2163 else if (gimple_code (stmt
) != GIMPLE_PHI
)
2165 gsi_insert_seq_after (&gsi
, seq
, GSI_CONTINUE_LINKING
);
2166 tem
= force_gimple_operand_gsi (&gsi
, tem
, true, NULL_TREE
, false,
2167 GSI_CONTINUE_LINKING
);
2171 gsi
= gsi_after_labels (gimple_bb (stmt
));
2172 if (!gsi_end_p (gsi
))
2173 uid
= gimple_uid (gsi_stmt (gsi
));
2176 gsi
= gsi_start_bb (gimple_bb (stmt
));
2178 while (!gsi_end_p (gsi
))
2180 uid
= gimple_uid (gsi_stmt (gsi
));
2184 gsi_insert_seq_before (&gsi
, seq
, GSI_SAME_STMT
);
2185 tem
= force_gimple_operand_gsi (&gsi
, tem
, true, NULL_TREE
, true,
2187 if (gsi_end_p (gsi
))
2188 gsi
= gsi_last_bb (gimple_bb (stmt
));
2192 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2193 if (gimple_uid (gsi_stmt (gsi
)))
2196 gimple_set_uid (gsi_stmt (gsi
), uid
);
2203 range
->strict_overflow_p
= false;
2205 for (i
= 0; i
< count
; i
++)
2208 range
= otherrange
+ i
;
2210 range
= otherrangep
[i
];
2211 oe
= (*ops
)[range
->idx
];
2212 /* Now change all the other range test immediate uses, so that
2213 those tests will be optimized away. */
2214 if (opcode
== ERROR_MARK
)
2217 oe
->op
= build_int_cst (TREE_TYPE (oe
->op
),
2218 oe
->rank
== BIT_IOR_EXPR
? 0 : 1);
2220 oe
->op
= (oe
->rank
== BIT_IOR_EXPR
2221 ? boolean_false_node
: boolean_true_node
);
2224 oe
->op
= error_mark_node
;
2225 range
->exp
= NULL_TREE
;
2230 /* Optimize X == CST1 || X == CST2
2231 if popcount (CST1 ^ CST2) == 1 into
2232 (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
2233 Similarly for ranges. E.g.
2234 X != 2 && X != 3 && X != 10 && X != 11
2235 will be transformed by the previous optimization into
2236 !((X - 2U) <= 1U || (X - 10U) <= 1U)
2237 and this loop can transform that into
2238 !(((X & ~8) - 2U) <= 1U). */
2241 optimize_range_tests_xor (enum tree_code opcode
, tree type
,
2242 tree lowi
, tree lowj
, tree highi
, tree highj
,
2243 vec
<operand_entry_t
> *ops
,
2244 struct range_entry
*rangei
,
2245 struct range_entry
*rangej
)
2247 tree lowxor
, highxor
, tem
, exp
;
2248 /* Check lowi ^ lowj == highi ^ highj and
2249 popcount (lowi ^ lowj) == 1. */
2250 lowxor
= fold_binary (BIT_XOR_EXPR
, type
, lowi
, lowj
);
2251 if (lowxor
== NULL_TREE
|| TREE_CODE (lowxor
) != INTEGER_CST
)
2253 if (!integer_pow2p (lowxor
))
2255 highxor
= fold_binary (BIT_XOR_EXPR
, type
, highi
, highj
);
2256 if (!tree_int_cst_equal (lowxor
, highxor
))
2259 tem
= fold_build1 (BIT_NOT_EXPR
, type
, lowxor
);
2260 exp
= fold_build2 (BIT_AND_EXPR
, type
, rangei
->exp
, tem
);
2261 lowj
= fold_build2 (BIT_AND_EXPR
, type
, lowi
, tem
);
2262 highj
= fold_build2 (BIT_AND_EXPR
, type
, highi
, tem
);
2263 if (update_range_test (rangei
, rangej
, NULL
, 1, opcode
, ops
, exp
,
2264 NULL
, rangei
->in_p
, lowj
, highj
,
2265 rangei
->strict_overflow_p
2266 || rangej
->strict_overflow_p
))
2271 /* Optimize X == CST1 || X == CST2
2272 if popcount (CST2 - CST1) == 1 into
2273 ((X - CST1) & ~(CST2 - CST1)) == 0.
2274 Similarly for ranges. E.g.
2275 X == 43 || X == 76 || X == 44 || X == 78 || X == 77 || X == 46
2276 || X == 75 || X == 45
2277 will be transformed by the previous optimization into
2278 (X - 43U) <= 3U || (X - 75U) <= 3U
2279 and this loop can transform that into
2280 ((X - 43U) & ~(75U - 43U)) <= 3U. */
2282 optimize_range_tests_diff (enum tree_code opcode
, tree type
,
2283 tree lowi
, tree lowj
, tree highi
, tree highj
,
2284 vec
<operand_entry_t
> *ops
,
2285 struct range_entry
*rangei
,
2286 struct range_entry
*rangej
)
2288 tree tem1
, tem2
, mask
;
2289 /* Check highi - lowi == highj - lowj. */
2290 tem1
= fold_binary (MINUS_EXPR
, type
, highi
, lowi
);
2291 if (tem1
== NULL_TREE
|| TREE_CODE (tem1
) != INTEGER_CST
)
2293 tem2
= fold_binary (MINUS_EXPR
, type
, highj
, lowj
);
2294 if (!tree_int_cst_equal (tem1
, tem2
))
2296 /* Check popcount (lowj - lowi) == 1. */
2297 tem1
= fold_binary (MINUS_EXPR
, type
, lowj
, lowi
);
2298 if (tem1
== NULL_TREE
|| TREE_CODE (tem1
) != INTEGER_CST
)
2300 if (!integer_pow2p (tem1
))
2303 type
= unsigned_type_for (type
);
2304 tem1
= fold_convert (type
, tem1
);
2305 tem2
= fold_convert (type
, tem2
);
2306 lowi
= fold_convert (type
, lowi
);
2307 mask
= fold_build1 (BIT_NOT_EXPR
, type
, tem1
);
2308 tem1
= fold_binary (MINUS_EXPR
, type
,
2309 fold_convert (type
, rangei
->exp
), lowi
);
2310 tem1
= fold_build2 (BIT_AND_EXPR
, type
, tem1
, mask
);
2311 lowj
= build_int_cst (type
, 0);
2312 if (update_range_test (rangei
, rangej
, NULL
, 1, opcode
, ops
, tem1
,
2313 NULL
, rangei
->in_p
, lowj
, tem2
,
2314 rangei
->strict_overflow_p
2315 || rangej
->strict_overflow_p
))
2320 /* It does some common checks for function optimize_range_tests_xor and
2321 optimize_range_tests_diff.
2322 If OPTIMIZE_XOR is TRUE, it calls optimize_range_tests_xor.
2323 Else it calls optimize_range_tests_diff. */
2326 optimize_range_tests_1 (enum tree_code opcode
, int first
, int length
,
2327 bool optimize_xor
, vec
<operand_entry_t
> *ops
,
2328 struct range_entry
*ranges
)
2331 bool any_changes
= false;
2332 for (i
= first
; i
< length
; i
++)
2334 tree lowi
, highi
, lowj
, highj
, type
, tem
;
2336 if (ranges
[i
].exp
== NULL_TREE
|| ranges
[i
].in_p
)
2338 type
= TREE_TYPE (ranges
[i
].exp
);
2339 if (!INTEGRAL_TYPE_P (type
))
2341 lowi
= ranges
[i
].low
;
2342 if (lowi
== NULL_TREE
)
2343 lowi
= TYPE_MIN_VALUE (type
);
2344 highi
= ranges
[i
].high
;
2345 if (highi
== NULL_TREE
)
2347 for (j
= i
+ 1; j
< length
&& j
< i
+ 64; j
++)
2350 if (ranges
[i
].exp
!= ranges
[j
].exp
|| ranges
[j
].in_p
)
2352 lowj
= ranges
[j
].low
;
2353 if (lowj
== NULL_TREE
)
2355 highj
= ranges
[j
].high
;
2356 if (highj
== NULL_TREE
)
2357 highj
= TYPE_MAX_VALUE (type
);
2358 /* Check lowj > highi. */
2359 tem
= fold_binary (GT_EXPR
, boolean_type_node
,
2361 if (tem
== NULL_TREE
|| !integer_onep (tem
))
2364 changes
= optimize_range_tests_xor (opcode
, type
, lowi
, lowj
,
2366 ranges
+ i
, ranges
+ j
);
2368 changes
= optimize_range_tests_diff (opcode
, type
, lowi
, lowj
,
2370 ranges
+ i
, ranges
+ j
);
2381 /* Helper function of optimize_range_tests_to_bit_test. Handle a single
2382 range, EXP, LOW, HIGH, compute bit mask of bits to test and return
2383 EXP on success, NULL otherwise. */
2386 extract_bit_test_mask (tree exp
, int prec
, tree totallow
, tree low
, tree high
,
2387 wide_int
*mask
, tree
*totallowp
)
2389 tree tem
= int_const_binop (MINUS_EXPR
, high
, low
);
2390 if (tem
== NULL_TREE
2391 || TREE_CODE (tem
) != INTEGER_CST
2392 || TREE_OVERFLOW (tem
)
2393 || tree_int_cst_sgn (tem
) == -1
2394 || compare_tree_int (tem
, prec
) != -1)
2397 unsigned HOST_WIDE_INT max
= tree_to_uhwi (tem
) + 1;
2398 *mask
= wi::shifted_mask (0, max
, false, prec
);
2399 if (TREE_CODE (exp
) == BIT_AND_EXPR
2400 && TREE_CODE (TREE_OPERAND (exp
, 1)) == INTEGER_CST
)
2402 widest_int msk
= wi::to_widest (TREE_OPERAND (exp
, 1));
2403 msk
= wi::zext (~msk
, TYPE_PRECISION (TREE_TYPE (exp
)));
2404 if (wi::popcount (msk
) == 1
2405 && wi::ltu_p (msk
, prec
- max
))
2407 *mask
|= wi::shifted_mask (msk
.to_uhwi (), max
, false, prec
);
2408 max
+= msk
.to_uhwi ();
2409 exp
= TREE_OPERAND (exp
, 0);
2410 if (integer_zerop (low
)
2411 && TREE_CODE (exp
) == PLUS_EXPR
2412 && TREE_CODE (TREE_OPERAND (exp
, 1)) == INTEGER_CST
)
2414 tree ret
= TREE_OPERAND (exp
, 0);
2417 = wi::neg (wi::sext (wi::to_widest (TREE_OPERAND (exp
, 1)),
2418 TYPE_PRECISION (TREE_TYPE (low
))));
2419 tree tbias
= wide_int_to_tree (TREE_TYPE (ret
), bias
);
2425 else if (!tree_int_cst_lt (totallow
, tbias
))
2427 bias
= wi::to_widest (tbias
);
2428 bias
-= wi::to_widest (totallow
);
2429 if (wi::ges_p (bias
, 0) && wi::lts_p (bias
, prec
- max
))
2431 *mask
= wi::lshift (*mask
, bias
);
2439 if (!tree_int_cst_lt (totallow
, low
))
2441 tem
= int_const_binop (MINUS_EXPR
, low
, totallow
);
2442 if (tem
== NULL_TREE
2443 || TREE_CODE (tem
) != INTEGER_CST
2444 || TREE_OVERFLOW (tem
)
2445 || compare_tree_int (tem
, prec
- max
) == 1)
2448 *mask
= wi::lshift (*mask
, wi::to_widest (tem
));
2452 /* Attempt to optimize small range tests using bit test.
2454 X != 43 && X != 76 && X != 44 && X != 78 && X != 49
2455 && X != 77 && X != 46 && X != 75 && X != 45 && X != 82
2456 has been by earlier optimizations optimized into:
2457 ((X - 43U) & ~32U) > 3U && X != 49 && X != 82
2458 As all the 43 through 82 range is less than 64 numbers,
2459 for 64-bit word targets optimize that into:
2460 (X - 43U) > 40U && ((1 << (X - 43U)) & 0x8F0000004FULL) == 0 */
2463 optimize_range_tests_to_bit_test (enum tree_code opcode
, int first
, int length
,
2464 vec
<operand_entry_t
> *ops
,
2465 struct range_entry
*ranges
)
2468 bool any_changes
= false;
2469 int prec
= GET_MODE_BITSIZE (word_mode
);
2470 auto_vec
<struct range_entry
*, 64> candidates
;
2472 for (i
= first
; i
< length
- 2; i
++)
2474 tree lowi
, highi
, lowj
, highj
, type
;
2476 if (ranges
[i
].exp
== NULL_TREE
|| ranges
[i
].in_p
)
2478 type
= TREE_TYPE (ranges
[i
].exp
);
2479 if (!INTEGRAL_TYPE_P (type
))
2481 lowi
= ranges
[i
].low
;
2482 if (lowi
== NULL_TREE
)
2483 lowi
= TYPE_MIN_VALUE (type
);
2484 highi
= ranges
[i
].high
;
2485 if (highi
== NULL_TREE
)
2488 tree exp
= extract_bit_test_mask (ranges
[i
].exp
, prec
, lowi
, lowi
,
2489 highi
, &mask
, &lowi
);
2490 if (exp
== NULL_TREE
)
2492 bool strict_overflow_p
= ranges
[i
].strict_overflow_p
;
2493 candidates
.truncate (0);
2494 int end
= MIN (i
+ 64, length
);
2495 for (j
= i
+ 1; j
< end
; j
++)
2498 if (ranges
[j
].exp
== NULL_TREE
|| ranges
[j
].in_p
)
2500 if (ranges
[j
].exp
== exp
)
2502 else if (TREE_CODE (ranges
[j
].exp
) == BIT_AND_EXPR
)
2504 exp2
= TREE_OPERAND (ranges
[j
].exp
, 0);
2507 else if (TREE_CODE (exp2
) == PLUS_EXPR
)
2509 exp2
= TREE_OPERAND (exp2
, 0);
2519 lowj
= ranges
[j
].low
;
2520 if (lowj
== NULL_TREE
)
2522 highj
= ranges
[j
].high
;
2523 if (highj
== NULL_TREE
)
2524 highj
= TYPE_MAX_VALUE (type
);
2526 exp2
= extract_bit_test_mask (ranges
[j
].exp
, prec
, lowi
, lowj
,
2527 highj
, &mask2
, NULL
);
2531 strict_overflow_p
|= ranges
[j
].strict_overflow_p
;
2532 candidates
.safe_push (&ranges
[j
]);
2535 /* If we need otherwise 3 or more comparisons, use a bit test. */
2536 if (candidates
.length () >= 2)
2538 tree high
= wide_int_to_tree (TREE_TYPE (lowi
),
2539 wi::to_widest (lowi
)
2540 + prec
- 1 - wi::clz (mask
));
2541 operand_entry_t oe
= (*ops
)[ranges
[i
].idx
];
2543 gimple stmt
= op
? SSA_NAME_DEF_STMT (op
)
2544 : last_stmt (BASIC_BLOCK_FOR_FN (cfun
, oe
->id
));
2545 location_t loc
= gimple_location (stmt
);
2546 tree optype
= op
? TREE_TYPE (op
) : boolean_type_node
;
2548 /* See if it isn't cheaper to pretend the minimum value of the
2549 range is 0, if maximum value is small enough.
2550 We can avoid then subtraction of the minimum value, but the
2551 mask constant could be perhaps more expensive. */
2552 if (compare_tree_int (lowi
, 0) > 0
2553 && compare_tree_int (high
, prec
) < 0)
2556 HOST_WIDE_INT m
= tree_to_uhwi (lowi
);
2557 rtx reg
= gen_raw_REG (word_mode
, 10000);
2558 bool speed_p
= optimize_bb_for_speed_p (gimple_bb (stmt
));
2559 cost_diff
= set_rtx_cost (gen_rtx_PLUS (word_mode
, reg
,
2560 GEN_INT (-m
)), speed_p
);
2561 rtx r
= immed_wide_int_const (mask
, word_mode
);
2562 cost_diff
+= set_src_cost (gen_rtx_AND (word_mode
, reg
, r
),
2564 r
= immed_wide_int_const (wi::lshift (mask
, m
), word_mode
);
2565 cost_diff
-= set_src_cost (gen_rtx_AND (word_mode
, reg
, r
),
2569 mask
= wi::lshift (mask
, m
);
2570 lowi
= build_zero_cst (TREE_TYPE (lowi
));
2574 tree tem
= build_range_check (loc
, optype
, unshare_expr (exp
),
2576 if (tem
== NULL_TREE
|| is_gimple_val (tem
))
2578 tree etype
= unsigned_type_for (TREE_TYPE (exp
));
2579 exp
= fold_build2_loc (loc
, MINUS_EXPR
, etype
,
2580 fold_convert_loc (loc
, etype
, exp
),
2581 fold_convert_loc (loc
, etype
, lowi
));
2582 exp
= fold_convert_loc (loc
, integer_type_node
, exp
);
2583 tree word_type
= lang_hooks
.types
.type_for_mode (word_mode
, 1);
2584 exp
= fold_build2_loc (loc
, LSHIFT_EXPR
, word_type
,
2585 build_int_cst (word_type
, 1), exp
);
2586 exp
= fold_build2_loc (loc
, BIT_AND_EXPR
, word_type
, exp
,
2587 wide_int_to_tree (word_type
, mask
));
2588 exp
= fold_build2_loc (loc
, EQ_EXPR
, optype
, exp
,
2589 build_zero_cst (word_type
));
2590 if (is_gimple_val (exp
))
2593 /* The shift might have undefined behavior if TEM is true,
2594 but reassociate_bb isn't prepared to have basic blocks
2595 split when it is running. So, temporarily emit a code
2596 with BIT_IOR_EXPR instead of &&, and fix it up in
2599 tem
= force_gimple_operand (tem
, &seq
, true, NULL_TREE
);
2600 gcc_assert (TREE_CODE (tem
) == SSA_NAME
);
2601 gimple_set_visited (SSA_NAME_DEF_STMT (tem
), true);
2603 exp
= force_gimple_operand (exp
, &seq2
, true, NULL_TREE
);
2604 gimple_seq_add_seq_without_update (&seq
, seq2
);
2605 gcc_assert (TREE_CODE (exp
) == SSA_NAME
);
2606 gimple_set_visited (SSA_NAME_DEF_STMT (exp
), true);
2607 gimple g
= gimple_build_assign (make_ssa_name (optype
),
2608 BIT_IOR_EXPR
, tem
, exp
);
2609 gimple_set_location (g
, loc
);
2610 gimple_seq_add_stmt_without_update (&seq
, g
);
2611 exp
= gimple_assign_lhs (g
);
2612 tree val
= build_zero_cst (optype
);
2613 if (update_range_test (&ranges
[i
], NULL
, candidates
.address (),
2614 candidates
.length (), opcode
, ops
, exp
,
2615 seq
, false, val
, val
, strict_overflow_p
))
2618 reassoc_branch_fixups
.safe_push (tem
);
2621 gimple_seq_discard (seq
);
2627 /* Optimize range tests, similarly how fold_range_test optimizes
2628 it on trees. The tree code for the binary
2629 operation between all the operands is OPCODE.
2630 If OPCODE is ERROR_MARK, optimize_range_tests is called from within
2631 maybe_optimize_range_tests for inter-bb range optimization.
2632 In that case if oe->op is NULL, oe->id is bb->index whose
2633 GIMPLE_COND is && or ||ed into the test, and oe->rank says
2634 the actual opcode. */
2637 optimize_range_tests (enum tree_code opcode
,
2638 vec
<operand_entry_t
> *ops
)
2640 unsigned int length
= ops
->length (), i
, j
, first
;
2642 struct range_entry
*ranges
;
2643 bool any_changes
= false;
2648 ranges
= XNEWVEC (struct range_entry
, length
);
2649 for (i
= 0; i
< length
; i
++)
2653 init_range_entry (ranges
+ i
, oe
->op
,
2655 last_stmt (BASIC_BLOCK_FOR_FN (cfun
, oe
->id
)));
2656 /* For | invert it now, we will invert it again before emitting
2657 the optimized expression. */
2658 if (opcode
== BIT_IOR_EXPR
2659 || (opcode
== ERROR_MARK
&& oe
->rank
== BIT_IOR_EXPR
))
2660 ranges
[i
].in_p
= !ranges
[i
].in_p
;
2663 qsort (ranges
, length
, sizeof (*ranges
), range_entry_cmp
);
2664 for (i
= 0; i
< length
; i
++)
2665 if (ranges
[i
].exp
!= NULL_TREE
&& TREE_CODE (ranges
[i
].exp
) == SSA_NAME
)
2668 /* Try to merge ranges. */
2669 for (first
= i
; i
< length
; i
++)
2671 tree low
= ranges
[i
].low
;
2672 tree high
= ranges
[i
].high
;
2673 int in_p
= ranges
[i
].in_p
;
2674 bool strict_overflow_p
= ranges
[i
].strict_overflow_p
;
2675 int update_fail_count
= 0;
2677 for (j
= i
+ 1; j
< length
; j
++)
2679 if (ranges
[i
].exp
!= ranges
[j
].exp
)
2681 if (!merge_ranges (&in_p
, &low
, &high
, in_p
, low
, high
,
2682 ranges
[j
].in_p
, ranges
[j
].low
, ranges
[j
].high
))
2684 strict_overflow_p
|= ranges
[j
].strict_overflow_p
;
2690 if (update_range_test (ranges
+ i
, ranges
+ i
+ 1, NULL
, j
- i
- 1,
2691 opcode
, ops
, ranges
[i
].exp
, NULL
, in_p
,
2692 low
, high
, strict_overflow_p
))
2697 /* Avoid quadratic complexity if all merge_ranges calls would succeed,
2698 while update_range_test would fail. */
2699 else if (update_fail_count
== 64)
2702 ++update_fail_count
;
2705 any_changes
|= optimize_range_tests_1 (opcode
, first
, length
, true,
2708 if (BRANCH_COST (optimize_function_for_speed_p (cfun
), false) >= 2)
2709 any_changes
|= optimize_range_tests_1 (opcode
, first
, length
, false,
2711 if (lshift_cheap_p (optimize_function_for_speed_p (cfun
)))
2712 any_changes
|= optimize_range_tests_to_bit_test (opcode
, first
, length
,
2715 if (any_changes
&& opcode
!= ERROR_MARK
)
2718 FOR_EACH_VEC_ELT (*ops
, i
, oe
)
2720 if (oe
->op
== error_mark_node
)
2729 XDELETEVEC (ranges
);
2733 /* Return true if STMT is a cast like:
2739 # _345 = PHI <_123(N), 1(...), 1(...)>
2740 where _234 has bool type, _123 has single use and
2741 bb N has a single successor M. This is commonly used in
2742 the last block of a range test. */
2745 final_range_test_p (gimple stmt
)
2747 basic_block bb
, rhs_bb
;
2750 use_operand_p use_p
;
2753 if (!gimple_assign_cast_p (stmt
))
2755 bb
= gimple_bb (stmt
);
2756 if (!single_succ_p (bb
))
2758 e
= single_succ_edge (bb
);
2759 if (e
->flags
& EDGE_COMPLEX
)
2762 lhs
= gimple_assign_lhs (stmt
);
2763 rhs
= gimple_assign_rhs1 (stmt
);
2764 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2765 || TREE_CODE (rhs
) != SSA_NAME
2766 || TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2769 /* Test whether lhs is consumed only by a PHI in the only successor bb. */
2770 if (!single_imm_use (lhs
, &use_p
, &use_stmt
))
2773 if (gimple_code (use_stmt
) != GIMPLE_PHI
2774 || gimple_bb (use_stmt
) != e
->dest
)
2777 /* And that the rhs is defined in the same loop. */
2778 rhs_bb
= gimple_bb (SSA_NAME_DEF_STMT (rhs
));
2780 || !flow_bb_inside_loop_p (loop_containing_stmt (stmt
), rhs_bb
))
2786 /* Return true if BB is suitable basic block for inter-bb range test
2787 optimization. If BACKWARD is true, BB should be the only predecessor
2788 of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
2789 or compared with to find a common basic block to which all conditions
2790 branch to if true resp. false. If BACKWARD is false, TEST_BB should
2791 be the only predecessor of BB. */
2794 suitable_cond_bb (basic_block bb
, basic_block test_bb
, basic_block
*other_bb
,
2797 edge_iterator ei
, ei2
;
2801 bool other_edge_seen
= false;
2806 /* Check last stmt first. */
2807 stmt
= last_stmt (bb
);
2809 || (gimple_code (stmt
) != GIMPLE_COND
2810 && (backward
|| !final_range_test_p (stmt
)))
2811 || gimple_visited_p (stmt
)
2812 || stmt_could_throw_p (stmt
)
2815 is_cond
= gimple_code (stmt
) == GIMPLE_COND
;
2818 /* If last stmt is GIMPLE_COND, verify that one of the succ edges
2819 goes to the next bb (if BACKWARD, it is TEST_BB), and the other
2820 to *OTHER_BB (if not set yet, try to find it out). */
2821 if (EDGE_COUNT (bb
->succs
) != 2)
2823 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2825 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2827 if (e
->dest
== test_bb
)
2836 if (*other_bb
== NULL
)
2838 FOR_EACH_EDGE (e2
, ei2
, test_bb
->succs
)
2839 if (!(e2
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2841 else if (e
->dest
== e2
->dest
)
2842 *other_bb
= e
->dest
;
2843 if (*other_bb
== NULL
)
2846 if (e
->dest
== *other_bb
)
2847 other_edge_seen
= true;
2851 if (*other_bb
== NULL
|| !other_edge_seen
)
2854 else if (single_succ (bb
) != *other_bb
)
2857 /* Now check all PHIs of *OTHER_BB. */
2858 e
= find_edge (bb
, *other_bb
);
2859 e2
= find_edge (test_bb
, *other_bb
);
2860 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2862 gphi
*phi
= gsi
.phi ();
2863 /* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments
2864 corresponding to BB and TEST_BB predecessor must be the same. */
2865 if (!operand_equal_p (gimple_phi_arg_def (phi
, e
->dest_idx
),
2866 gimple_phi_arg_def (phi
, e2
->dest_idx
), 0))
2868 /* Otherwise, if one of the blocks doesn't end with GIMPLE_COND,
2869 one of the PHIs should have the lhs of the last stmt in
2870 that block as PHI arg and that PHI should have 0 or 1
2871 corresponding to it in all other range test basic blocks
2875 if (gimple_phi_arg_def (phi
, e
->dest_idx
)
2876 == gimple_assign_lhs (stmt
)
2877 && (integer_zerop (gimple_phi_arg_def (phi
, e2
->dest_idx
))
2878 || integer_onep (gimple_phi_arg_def (phi
,
2884 gimple test_last
= last_stmt (test_bb
);
2885 if (gimple_code (test_last
) != GIMPLE_COND
2886 && gimple_phi_arg_def (phi
, e2
->dest_idx
)
2887 == gimple_assign_lhs (test_last
)
2888 && (integer_zerop (gimple_phi_arg_def (phi
, e
->dest_idx
))
2889 || integer_onep (gimple_phi_arg_def (phi
, e
->dest_idx
))))
2899 /* Return true if BB doesn't have side-effects that would disallow
2900 range test optimization, all SSA_NAMEs set in the bb are consumed
2901 in the bb and there are no PHIs. */
2904 no_side_effect_bb (basic_block bb
)
2906 gimple_stmt_iterator gsi
;
2909 if (!gimple_seq_empty_p (phi_nodes (bb
)))
2911 last
= last_stmt (bb
);
2912 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2914 gimple stmt
= gsi_stmt (gsi
);
2916 imm_use_iterator imm_iter
;
2917 use_operand_p use_p
;
2919 if (is_gimple_debug (stmt
))
2921 if (gimple_has_side_effects (stmt
))
2925 if (!is_gimple_assign (stmt
))
2927 lhs
= gimple_assign_lhs (stmt
);
2928 if (TREE_CODE (lhs
) != SSA_NAME
)
2930 if (gimple_assign_rhs_could_trap_p (stmt
))
2932 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2934 gimple use_stmt
= USE_STMT (use_p
);
2935 if (is_gimple_debug (use_stmt
))
2937 if (gimple_bb (use_stmt
) != bb
)
2944 /* If VAR is set by CODE (BIT_{AND,IOR}_EXPR) which is reassociable,
2945 return true and fill in *OPS recursively. */
2948 get_ops (tree var
, enum tree_code code
, vec
<operand_entry_t
> *ops
,
2951 gimple stmt
= SSA_NAME_DEF_STMT (var
);
2955 if (!is_reassociable_op (stmt
, code
, loop
))
2958 rhs
[0] = gimple_assign_rhs1 (stmt
);
2959 rhs
[1] = gimple_assign_rhs2 (stmt
);
2960 gimple_set_visited (stmt
, true);
2961 for (i
= 0; i
< 2; i
++)
2962 if (TREE_CODE (rhs
[i
]) == SSA_NAME
2963 && !get_ops (rhs
[i
], code
, ops
, loop
)
2964 && has_single_use (rhs
[i
]))
2966 operand_entry_t oe
= (operand_entry_t
) pool_alloc (operand_entry_pool
);
2972 ops
->safe_push (oe
);
2977 /* Find the ops that were added by get_ops starting from VAR, see if
2978 they were changed during update_range_test and if yes, create new
2982 update_ops (tree var
, enum tree_code code
, vec
<operand_entry_t
> ops
,
2983 unsigned int *pidx
, struct loop
*loop
)
2985 gimple stmt
= SSA_NAME_DEF_STMT (var
);
2989 if (!is_reassociable_op (stmt
, code
, loop
))
2992 rhs
[0] = gimple_assign_rhs1 (stmt
);
2993 rhs
[1] = gimple_assign_rhs2 (stmt
);
2996 for (i
= 0; i
< 2; i
++)
2997 if (TREE_CODE (rhs
[i
]) == SSA_NAME
)
2999 rhs
[2 + i
] = update_ops (rhs
[i
], code
, ops
, pidx
, loop
);
3000 if (rhs
[2 + i
] == NULL_TREE
)
3002 if (has_single_use (rhs
[i
]))
3003 rhs
[2 + i
] = ops
[(*pidx
)++]->op
;
3005 rhs
[2 + i
] = rhs
[i
];
3008 if ((rhs
[2] != rhs
[0] || rhs
[3] != rhs
[1])
3009 && (rhs
[2] != rhs
[1] || rhs
[3] != rhs
[0]))
3011 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
3012 var
= make_ssa_name (TREE_TYPE (var
));
3013 gassign
*g
= gimple_build_assign (var
, gimple_assign_rhs_code (stmt
),
3015 gimple_set_uid (g
, gimple_uid (stmt
));
3016 gimple_set_visited (g
, true);
3017 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
3022 /* Structure to track the initial value passed to get_ops and
3023 the range in the ops vector for each basic block. */
3025 struct inter_bb_range_test_entry
3028 unsigned int first_idx
, last_idx
;
3031 /* Inter-bb range test optimization. */
3034 maybe_optimize_range_tests (gimple stmt
)
3036 basic_block first_bb
= gimple_bb (stmt
);
3037 basic_block last_bb
= first_bb
;
3038 basic_block other_bb
= NULL
;
3042 auto_vec
<operand_entry_t
> ops
;
3043 auto_vec
<inter_bb_range_test_entry
> bbinfo
;
3044 bool any_changes
= false;
3046 /* Consider only basic blocks that end with GIMPLE_COND or
3047 a cast statement satisfying final_range_test_p. All
3048 but the last bb in the first_bb .. last_bb range
3049 should end with GIMPLE_COND. */
3050 if (gimple_code (stmt
) == GIMPLE_COND
)
3052 if (EDGE_COUNT (first_bb
->succs
) != 2)
3055 else if (final_range_test_p (stmt
))
3056 other_bb
= single_succ (first_bb
);
3060 if (stmt_could_throw_p (stmt
))
3063 /* As relative ordering of post-dominator sons isn't fixed,
3064 maybe_optimize_range_tests can be called first on any
3065 bb in the range we want to optimize. So, start searching
3066 backwards, if first_bb can be set to a predecessor. */
3067 while (single_pred_p (first_bb
))
3069 basic_block pred_bb
= single_pred (first_bb
);
3070 if (!suitable_cond_bb (pred_bb
, first_bb
, &other_bb
, true))
3072 if (!no_side_effect_bb (first_bb
))
3076 /* If first_bb is last_bb, other_bb hasn't been computed yet.
3077 Before starting forward search in last_bb successors, find
3078 out the other_bb. */
3079 if (first_bb
== last_bb
)
3082 /* As non-GIMPLE_COND last stmt always terminates the range,
3083 if forward search didn't discover anything, just give up. */
3084 if (gimple_code (stmt
) != GIMPLE_COND
)
3086 /* Look at both successors. Either it ends with a GIMPLE_COND
3087 and satisfies suitable_cond_bb, or ends with a cast and
3088 other_bb is that cast's successor. */
3089 FOR_EACH_EDGE (e
, ei
, first_bb
->succs
)
3090 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
))
3091 || e
->dest
== first_bb
)
3093 else if (single_pred_p (e
->dest
))
3095 stmt
= last_stmt (e
->dest
);
3097 && gimple_code (stmt
) == GIMPLE_COND
3098 && EDGE_COUNT (e
->dest
->succs
) == 2)
3100 if (suitable_cond_bb (first_bb
, e
->dest
, &other_bb
, true))
3106 && final_range_test_p (stmt
)
3107 && find_edge (first_bb
, single_succ (e
->dest
)))
3109 other_bb
= single_succ (e
->dest
);
3110 if (other_bb
== first_bb
)
3114 if (other_bb
== NULL
)
3117 /* Now do the forward search, moving last_bb to successor bbs
3118 that aren't other_bb. */
3119 while (EDGE_COUNT (last_bb
->succs
) == 2)
3121 FOR_EACH_EDGE (e
, ei
, last_bb
->succs
)
3122 if (e
->dest
!= other_bb
)
3126 if (!single_pred_p (e
->dest
))
3128 if (!suitable_cond_bb (e
->dest
, last_bb
, &other_bb
, false))
3130 if (!no_side_effect_bb (e
->dest
))
3134 if (first_bb
== last_bb
)
3136 /* Here basic blocks first_bb through last_bb's predecessor
3137 end with GIMPLE_COND, all of them have one of the edges to
3138 other_bb and another to another block in the range,
3139 all blocks except first_bb don't have side-effects and
3140 last_bb ends with either GIMPLE_COND, or cast satisfying
3141 final_range_test_p. */
3142 for (bb
= last_bb
; ; bb
= single_pred (bb
))
3144 enum tree_code code
;
3146 inter_bb_range_test_entry bb_ent
;
3148 bb_ent
.op
= NULL_TREE
;
3149 bb_ent
.first_idx
= ops
.length ();
3150 bb_ent
.last_idx
= bb_ent
.first_idx
;
3151 e
= find_edge (bb
, other_bb
);
3152 stmt
= last_stmt (bb
);
3153 gimple_set_visited (stmt
, true);
3154 if (gimple_code (stmt
) != GIMPLE_COND
)
3156 use_operand_p use_p
;
3161 lhs
= gimple_assign_lhs (stmt
);
3162 rhs
= gimple_assign_rhs1 (stmt
);
3163 gcc_assert (bb
== last_bb
);
3170 # _345 = PHI <_123(N), 1(...), 1(...)>
3172 or 0 instead of 1. If it is 0, the _234
3173 range test is anded together with all the
3174 other range tests, if it is 1, it is ored with
3176 single_imm_use (lhs
, &use_p
, &phi
);
3177 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
);
3178 e2
= find_edge (first_bb
, other_bb
);
3180 gcc_assert (gimple_phi_arg_def (phi
, e
->dest_idx
) == lhs
);
3181 if (integer_zerop (gimple_phi_arg_def (phi
, d
)))
3182 code
= BIT_AND_EXPR
;
3185 gcc_checking_assert (integer_onep (gimple_phi_arg_def (phi
, d
)));
3186 code
= BIT_IOR_EXPR
;
3189 /* If _234 SSA_NAME_DEF_STMT is
3191 (or &, corresponding to 1/0 in the phi arguments,
3192 push into ops the individual range test arguments
3193 of the bitwise or resp. and, recursively. */
3194 if (!get_ops (rhs
, code
, &ops
,
3195 loop_containing_stmt (stmt
))
3196 && has_single_use (rhs
))
3198 /* Otherwise, push the _234 range test itself. */
3200 = (operand_entry_t
) pool_alloc (operand_entry_pool
);
3210 bb_ent
.last_idx
= ops
.length ();
3212 bbinfo
.safe_push (bb_ent
);
3215 /* Otherwise stmt is GIMPLE_COND. */
3216 code
= gimple_cond_code (stmt
);
3217 lhs
= gimple_cond_lhs (stmt
);
3218 rhs
= gimple_cond_rhs (stmt
);
3219 if (TREE_CODE (lhs
) == SSA_NAME
3220 && INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
3221 && ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3222 || rhs
!= boolean_false_node
3223 /* Either push into ops the individual bitwise
3224 or resp. and operands, depending on which
3225 edge is other_bb. */
3226 || !get_ops (lhs
, (((e
->flags
& EDGE_TRUE_VALUE
) == 0)
3227 ^ (code
== EQ_EXPR
))
3228 ? BIT_AND_EXPR
: BIT_IOR_EXPR
, &ops
,
3229 loop_containing_stmt (stmt
))))
3231 /* Or push the GIMPLE_COND stmt itself. */
3233 = (operand_entry_t
) pool_alloc (operand_entry_pool
);
3236 oe
->rank
= (e
->flags
& EDGE_TRUE_VALUE
)
3237 ? BIT_IOR_EXPR
: BIT_AND_EXPR
;
3238 /* oe->op = NULL signs that there is no SSA_NAME
3239 for the range test, and oe->id instead is the
3240 basic block number, at which's end the GIMPLE_COND
3248 else if (ops
.length () > bb_ent
.first_idx
)
3251 bb_ent
.last_idx
= ops
.length ();
3253 bbinfo
.safe_push (bb_ent
);
3257 if (ops
.length () > 1)
3258 any_changes
= optimize_range_tests (ERROR_MARK
, &ops
);
3262 /* update_ops relies on has_single_use predicates returning the
3263 same values as it did during get_ops earlier. Additionally it
3264 never removes statements, only adds new ones and it should walk
3265 from the single imm use and check the predicate already before
3266 making those changes.
3267 On the other side, the handling of GIMPLE_COND directly can turn
3268 previously multiply used SSA_NAMEs into single use SSA_NAMEs, so
3269 it needs to be done in a separate loop afterwards. */
3270 for (bb
= last_bb
, idx
= 0; ; bb
= single_pred (bb
), idx
++)
3272 if (bbinfo
[idx
].first_idx
< bbinfo
[idx
].last_idx
3273 && bbinfo
[idx
].op
!= NULL_TREE
)
3277 stmt
= last_stmt (bb
);
3278 new_op
= update_ops (bbinfo
[idx
].op
,
3280 ops
[bbinfo
[idx
].first_idx
]->rank
,
3281 ops
, &bbinfo
[idx
].first_idx
,
3282 loop_containing_stmt (stmt
));
3283 if (new_op
== NULL_TREE
)
3285 gcc_assert (bb
== last_bb
);
3286 new_op
= ops
[bbinfo
[idx
].first_idx
++]->op
;
3288 if (bbinfo
[idx
].op
!= new_op
)
3290 imm_use_iterator iter
;
3291 use_operand_p use_p
;
3292 gimple use_stmt
, cast_stmt
= NULL
;
3294 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, bbinfo
[idx
].op
)
3295 if (is_gimple_debug (use_stmt
))
3297 else if (gimple_code (use_stmt
) == GIMPLE_COND
3298 || gimple_code (use_stmt
) == GIMPLE_PHI
)
3299 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
3300 SET_USE (use_p
, new_op
);
3301 else if (gimple_assign_cast_p (use_stmt
))
3302 cast_stmt
= use_stmt
;
3307 gcc_assert (bb
== last_bb
);
3308 tree lhs
= gimple_assign_lhs (cast_stmt
);
3309 tree new_lhs
= make_ssa_name (TREE_TYPE (lhs
));
3310 enum tree_code rhs_code
3311 = gimple_assign_rhs_code (cast_stmt
);
3313 if (is_gimple_min_invariant (new_op
))
3315 new_op
= fold_convert (TREE_TYPE (lhs
), new_op
);
3316 g
= gimple_build_assign (new_lhs
, new_op
);
3319 g
= gimple_build_assign (new_lhs
, rhs_code
, new_op
);
3320 gimple_stmt_iterator gsi
= gsi_for_stmt (cast_stmt
);
3321 gimple_set_uid (g
, gimple_uid (cast_stmt
));
3322 gimple_set_visited (g
, true);
3323 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
3324 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
3325 if (is_gimple_debug (use_stmt
))
3327 else if (gimple_code (use_stmt
) == GIMPLE_COND
3328 || gimple_code (use_stmt
) == GIMPLE_PHI
)
3329 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
3330 SET_USE (use_p
, new_lhs
);
3339 for (bb
= last_bb
, idx
= 0; ; bb
= single_pred (bb
), idx
++)
3341 if (bbinfo
[idx
].first_idx
< bbinfo
[idx
].last_idx
3342 && bbinfo
[idx
].op
== NULL_TREE
3343 && ops
[bbinfo
[idx
].first_idx
]->op
!= NULL_TREE
)
3345 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (bb
));
3346 if (integer_zerop (ops
[bbinfo
[idx
].first_idx
]->op
))
3347 gimple_cond_make_false (cond_stmt
);
3348 else if (integer_onep (ops
[bbinfo
[idx
].first_idx
]->op
))
3349 gimple_cond_make_true (cond_stmt
);
3352 gimple_cond_set_code (cond_stmt
, NE_EXPR
);
3353 gimple_cond_set_lhs (cond_stmt
,
3354 ops
[bbinfo
[idx
].first_idx
]->op
);
3355 gimple_cond_set_rhs (cond_stmt
, boolean_false_node
);
3357 update_stmt (cond_stmt
);
3365 /* Return true if OPERAND is defined by a PHI node which uses the LHS
3366 of STMT in it's operands. This is also known as a "destructive
3367 update" operation. */
3370 is_phi_for_stmt (gimple stmt
, tree operand
)
3375 use_operand_p arg_p
;
3378 if (TREE_CODE (operand
) != SSA_NAME
)
3381 lhs
= gimple_assign_lhs (stmt
);
3383 def_stmt
= SSA_NAME_DEF_STMT (operand
);
3384 def_phi
= dyn_cast
<gphi
*> (def_stmt
);
3388 FOR_EACH_PHI_ARG (arg_p
, def_phi
, i
, SSA_OP_USE
)
3389 if (lhs
== USE_FROM_PTR (arg_p
))
3394 /* Remove def stmt of VAR if VAR has zero uses and recurse
3395 on rhs1 operand if so. */
3398 remove_visited_stmt_chain (tree var
)
3401 gimple_stmt_iterator gsi
;
3405 if (TREE_CODE (var
) != SSA_NAME
|| !has_zero_uses (var
))
3407 stmt
= SSA_NAME_DEF_STMT (var
);
3408 if (is_gimple_assign (stmt
) && gimple_visited_p (stmt
))
3410 var
= gimple_assign_rhs1 (stmt
);
3411 gsi
= gsi_for_stmt (stmt
);
3412 reassoc_remove_stmt (&gsi
);
3413 release_defs (stmt
);
3420 /* This function checks three consequtive operands in
3421 passed operands vector OPS starting from OPINDEX and
3422 swaps two operands if it is profitable for binary operation
3423 consuming OPINDEX + 1 abnd OPINDEX + 2 operands.
3425 We pair ops with the same rank if possible.
3427 The alternative we try is to see if STMT is a destructive
3428 update style statement, which is like:
3431 In that case, we want to use the destructive update form to
3432 expose the possible vectorizer sum reduction opportunity.
3433 In that case, the third operand will be the phi node. This
3434 check is not performed if STMT is null.
3436 We could, of course, try to be better as noted above, and do a
3437 lot of work to try to find these opportunities in >3 operand
3438 cases, but it is unlikely to be worth it. */
3441 swap_ops_for_binary_stmt (vec
<operand_entry_t
> ops
,
3442 unsigned int opindex
, gimple stmt
)
3444 operand_entry_t oe1
, oe2
, oe3
;
3447 oe2
= ops
[opindex
+ 1];
3448 oe3
= ops
[opindex
+ 2];
3450 if ((oe1
->rank
== oe2
->rank
3451 && oe2
->rank
!= oe3
->rank
)
3452 || (stmt
&& is_phi_for_stmt (stmt
, oe3
->op
)
3453 && !is_phi_for_stmt (stmt
, oe1
->op
)
3454 && !is_phi_for_stmt (stmt
, oe2
->op
)))
3456 struct operand_entry temp
= *oe3
;
3458 oe3
->rank
= oe1
->rank
;
3460 oe1
->rank
= temp
.rank
;
3462 else if ((oe1
->rank
== oe3
->rank
3463 && oe2
->rank
!= oe3
->rank
)
3464 || (stmt
&& is_phi_for_stmt (stmt
, oe2
->op
)
3465 && !is_phi_for_stmt (stmt
, oe1
->op
)
3466 && !is_phi_for_stmt (stmt
, oe3
->op
)))
3468 struct operand_entry temp
= *oe2
;
3470 oe2
->rank
= oe1
->rank
;
3472 oe1
->rank
= temp
.rank
;
3476 /* If definition of RHS1 or RHS2 dominates STMT, return the later of those
3477 two definitions, otherwise return STMT. */
3479 static inline gimple
3480 find_insert_point (gimple stmt
, tree rhs1
, tree rhs2
)
3482 if (TREE_CODE (rhs1
) == SSA_NAME
3483 && reassoc_stmt_dominates_stmt_p (stmt
, SSA_NAME_DEF_STMT (rhs1
)))
3484 stmt
= SSA_NAME_DEF_STMT (rhs1
);
3485 if (TREE_CODE (rhs2
) == SSA_NAME
3486 && reassoc_stmt_dominates_stmt_p (stmt
, SSA_NAME_DEF_STMT (rhs2
)))
3487 stmt
= SSA_NAME_DEF_STMT (rhs2
);
3491 /* Recursively rewrite our linearized statements so that the operators
3492 match those in OPS[OPINDEX], putting the computation in rank
3493 order. Return new lhs. */
3496 rewrite_expr_tree (gimple stmt
, unsigned int opindex
,
3497 vec
<operand_entry_t
> ops
, bool changed
)
3499 tree rhs1
= gimple_assign_rhs1 (stmt
);
3500 tree rhs2
= gimple_assign_rhs2 (stmt
);
3501 tree lhs
= gimple_assign_lhs (stmt
);
3504 /* The final recursion case for this function is that you have
3505 exactly two operations left.
3506 If we had exactly one op in the entire list to start with, we
3507 would have never called this function, and the tail recursion
3508 rewrites them one at a time. */
3509 if (opindex
+ 2 == ops
.length ())
3511 operand_entry_t oe1
, oe2
;
3514 oe2
= ops
[opindex
+ 1];
3516 if (rhs1
!= oe1
->op
|| rhs2
!= oe2
->op
)
3518 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
3519 unsigned int uid
= gimple_uid (stmt
);
3521 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3523 fprintf (dump_file
, "Transforming ");
3524 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3527 /* Even when changed is false, reassociation could have e.g. removed
3528 some redundant operations, so unless we are just swapping the
3529 arguments or unless there is no change at all (then we just
3530 return lhs), force creation of a new SSA_NAME. */
3531 if (changed
|| ((rhs1
!= oe2
->op
|| rhs2
!= oe1
->op
) && opindex
))
3533 gimple insert_point
= find_insert_point (stmt
, oe1
->op
, oe2
->op
);
3534 lhs
= make_ssa_name (TREE_TYPE (lhs
));
3536 = gimple_build_assign (lhs
, gimple_assign_rhs_code (stmt
),
3538 gimple_set_uid (stmt
, uid
);
3539 gimple_set_visited (stmt
, true);
3540 if (insert_point
== gsi_stmt (gsi
))
3541 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3543 insert_stmt_after (stmt
, insert_point
);
3547 gcc_checking_assert (find_insert_point (stmt
, oe1
->op
, oe2
->op
)
3549 gimple_assign_set_rhs1 (stmt
, oe1
->op
);
3550 gimple_assign_set_rhs2 (stmt
, oe2
->op
);
3554 if (rhs1
!= oe1
->op
&& rhs1
!= oe2
->op
)
3555 remove_visited_stmt_chain (rhs1
);
3557 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3559 fprintf (dump_file
, " into ");
3560 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3566 /* If we hit here, we should have 3 or more ops left. */
3567 gcc_assert (opindex
+ 2 < ops
.length ());
3569 /* Rewrite the next operator. */
3572 /* Recurse on the LHS of the binary operator, which is guaranteed to
3573 be the non-leaf side. */
3575 = rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1
), opindex
+ 1, ops
,
3576 changed
|| oe
->op
!= rhs2
);
3578 if (oe
->op
!= rhs2
|| new_rhs1
!= rhs1
)
3580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3582 fprintf (dump_file
, "Transforming ");
3583 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3586 /* If changed is false, this is either opindex == 0
3587 or all outer rhs2's were equal to corresponding oe->op,
3588 and powi_result is NULL.
3589 That means lhs is equivalent before and after reassociation.
3590 Otherwise ensure the old lhs SSA_NAME is not reused and
3591 create a new stmt as well, so that any debug stmts will be
3592 properly adjusted. */
3595 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
3596 unsigned int uid
= gimple_uid (stmt
);
3597 gimple insert_point
= find_insert_point (stmt
, new_rhs1
, oe
->op
);
3599 lhs
= make_ssa_name (TREE_TYPE (lhs
));
3600 stmt
= gimple_build_assign (lhs
, gimple_assign_rhs_code (stmt
),
3602 gimple_set_uid (stmt
, uid
);
3603 gimple_set_visited (stmt
, true);
3604 if (insert_point
== gsi_stmt (gsi
))
3605 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
3607 insert_stmt_after (stmt
, insert_point
);
3611 gcc_checking_assert (find_insert_point (stmt
, new_rhs1
, oe
->op
)
3613 gimple_assign_set_rhs1 (stmt
, new_rhs1
);
3614 gimple_assign_set_rhs2 (stmt
, oe
->op
);
3618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3620 fprintf (dump_file
, " into ");
3621 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3627 /* Find out how many cycles we need to compute statements chain.
3628 OPS_NUM holds number os statements in a chain. CPU_WIDTH is a
3629 maximum number of independent statements we may execute per cycle. */
3632 get_required_cycles (int ops_num
, int cpu_width
)
3638 /* While we have more than 2 * cpu_width operands
3639 we may reduce number of operands by cpu_width
3641 res
= ops_num
/ (2 * cpu_width
);
3643 /* Remained operands count may be reduced twice per cycle
3644 until we have only one operand. */
3645 rest
= (unsigned)(ops_num
- res
* cpu_width
);
3646 elog
= exact_log2 (rest
);
3650 res
+= floor_log2 (rest
) + 1;
3655 /* Returns an optimal number of registers to use for computation of
3656 given statements. */
3659 get_reassociation_width (int ops_num
, enum tree_code opc
,
3662 int param_width
= PARAM_VALUE (PARAM_TREE_REASSOC_WIDTH
);
3667 if (param_width
> 0)
3668 width
= param_width
;
3670 width
= targetm
.sched
.reassociation_width (opc
, mode
);
3675 /* Get the minimal time required for sequence computation. */
3676 cycles_best
= get_required_cycles (ops_num
, width
);
3678 /* Check if we may use less width and still compute sequence for
3679 the same time. It will allow us to reduce registers usage.
3680 get_required_cycles is monotonically increasing with lower width
3681 so we can perform a binary search for the minimal width that still
3682 results in the optimal cycle count. */
3684 while (width
> width_min
)
3686 int width_mid
= (width
+ width_min
) / 2;
3688 if (get_required_cycles (ops_num
, width_mid
) == cycles_best
)
3690 else if (width_min
< width_mid
)
3691 width_min
= width_mid
;
3699 /* Recursively rewrite our linearized statements so that the operators
3700 match those in OPS[OPINDEX], putting the computation in rank
3701 order and trying to allow operations to be executed in
3705 rewrite_expr_tree_parallel (gassign
*stmt
, int width
,
3706 vec
<operand_entry_t
> ops
)
3708 enum tree_code opcode
= gimple_assign_rhs_code (stmt
);
3709 int op_num
= ops
.length ();
3710 int stmt_num
= op_num
- 1;
3711 gimple
*stmts
= XALLOCAVEC (gimple
, stmt_num
);
3712 int op_index
= op_num
- 1;
3714 int ready_stmts_end
= 0;
3716 tree last_rhs1
= gimple_assign_rhs1 (stmt
);
3718 /* We start expression rewriting from the top statements.
3719 So, in this loop we create a full list of statements
3720 we will work with. */
3721 stmts
[stmt_num
- 1] = stmt
;
3722 for (i
= stmt_num
- 2; i
>= 0; i
--)
3723 stmts
[i
] = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmts
[i
+1]));
3725 for (i
= 0; i
< stmt_num
; i
++)
3729 /* Determine whether we should use results of
3730 already handled statements or not. */
3731 if (ready_stmts_end
== 0
3732 && (i
- stmt_index
>= width
|| op_index
< 1))
3733 ready_stmts_end
= i
;
3735 /* Now we choose operands for the next statement. Non zero
3736 value in ready_stmts_end means here that we should use
3737 the result of already generated statements as new operand. */
3738 if (ready_stmts_end
> 0)
3740 op1
= gimple_assign_lhs (stmts
[stmt_index
++]);
3741 if (ready_stmts_end
> stmt_index
)
3742 op2
= gimple_assign_lhs (stmts
[stmt_index
++]);
3743 else if (op_index
>= 0)
3744 op2
= ops
[op_index
--]->op
;
3747 gcc_assert (stmt_index
< i
);
3748 op2
= gimple_assign_lhs (stmts
[stmt_index
++]);
3751 if (stmt_index
>= ready_stmts_end
)
3752 ready_stmts_end
= 0;
3757 swap_ops_for_binary_stmt (ops
, op_index
- 2, NULL
);
3758 op2
= ops
[op_index
--]->op
;
3759 op1
= ops
[op_index
--]->op
;
3762 /* If we emit the last statement then we should put
3763 operands into the last statement. It will also
3765 if (op_index
< 0 && stmt_index
== i
)
3768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3770 fprintf (dump_file
, "Transforming ");
3771 print_gimple_stmt (dump_file
, stmts
[i
], 0, 0);
3774 /* We keep original statement only for the last one. All
3775 others are recreated. */
3776 if (i
== stmt_num
- 1)
3778 gimple_assign_set_rhs1 (stmts
[i
], op1
);
3779 gimple_assign_set_rhs2 (stmts
[i
], op2
);
3780 update_stmt (stmts
[i
]);
3783 stmts
[i
] = build_and_add_sum (TREE_TYPE (last_rhs1
), op1
, op2
, opcode
);
3785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3787 fprintf (dump_file
, " into ");
3788 print_gimple_stmt (dump_file
, stmts
[i
], 0, 0);
3792 remove_visited_stmt_chain (last_rhs1
);
3795 /* Transform STMT, which is really (A +B) + (C + D) into the left
3796 linear form, ((A+B)+C)+D.
3797 Recurse on D if necessary. */
3800 linearize_expr (gimple stmt
)
3802 gimple_stmt_iterator gsi
;
3803 gimple binlhs
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
3804 gimple binrhs
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
3805 gimple oldbinrhs
= binrhs
;
3806 enum tree_code rhscode
= gimple_assign_rhs_code (stmt
);
3807 gimple newbinrhs
= NULL
;
3808 struct loop
*loop
= loop_containing_stmt (stmt
);
3809 tree lhs
= gimple_assign_lhs (stmt
);
3811 gcc_assert (is_reassociable_op (binlhs
, rhscode
, loop
)
3812 && is_reassociable_op (binrhs
, rhscode
, loop
));
3814 gsi
= gsi_for_stmt (stmt
);
3816 gimple_assign_set_rhs2 (stmt
, gimple_assign_rhs1 (binrhs
));
3817 binrhs
= gimple_build_assign (make_ssa_name (TREE_TYPE (lhs
)),
3818 gimple_assign_rhs_code (binrhs
),
3819 gimple_assign_lhs (binlhs
),
3820 gimple_assign_rhs2 (binrhs
));
3821 gimple_assign_set_rhs1 (stmt
, gimple_assign_lhs (binrhs
));
3822 gsi_insert_before (&gsi
, binrhs
, GSI_SAME_STMT
);
3823 gimple_set_uid (binrhs
, gimple_uid (stmt
));
3825 if (TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
)
3826 newbinrhs
= SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt
));
3828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3830 fprintf (dump_file
, "Linearized: ");
3831 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3834 reassociate_stats
.linearized
++;
3837 gsi
= gsi_for_stmt (oldbinrhs
);
3838 reassoc_remove_stmt (&gsi
);
3839 release_defs (oldbinrhs
);
3841 gimple_set_visited (stmt
, true);
3842 gimple_set_visited (binlhs
, true);
3843 gimple_set_visited (binrhs
, true);
3845 /* Tail recurse on the new rhs if it still needs reassociation. */
3846 if (newbinrhs
&& is_reassociable_op (newbinrhs
, rhscode
, loop
))
3847 /* ??? This should probably be linearize_expr (newbinrhs) but I don't
3848 want to change the algorithm while converting to tuples. */
3849 linearize_expr (stmt
);
3852 /* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return
3853 it. Otherwise, return NULL. */
3856 get_single_immediate_use (tree lhs
)
3858 use_operand_p immuse
;
3861 if (TREE_CODE (lhs
) == SSA_NAME
3862 && single_imm_use (lhs
, &immuse
, &immusestmt
)
3863 && is_gimple_assign (immusestmt
))
3869 /* Recursively negate the value of TONEGATE, and return the SSA_NAME
3870 representing the negated value. Insertions of any necessary
3871 instructions go before GSI.
3872 This function is recursive in that, if you hand it "a_5" as the
3873 value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
3874 transform b_3 + b_4 into a_5 = -b_3 + -b_4. */
3877 negate_value (tree tonegate
, gimple_stmt_iterator
*gsip
)
3879 gimple negatedefstmt
= NULL
;
3880 tree resultofnegate
;
3881 gimple_stmt_iterator gsi
;
3884 /* If we are trying to negate a name, defined by an add, negate the
3885 add operands instead. */
3886 if (TREE_CODE (tonegate
) == SSA_NAME
)
3887 negatedefstmt
= SSA_NAME_DEF_STMT (tonegate
);
3888 if (TREE_CODE (tonegate
) == SSA_NAME
3889 && is_gimple_assign (negatedefstmt
)
3890 && TREE_CODE (gimple_assign_lhs (negatedefstmt
)) == SSA_NAME
3891 && has_single_use (gimple_assign_lhs (negatedefstmt
))
3892 && gimple_assign_rhs_code (negatedefstmt
) == PLUS_EXPR
)
3894 tree rhs1
= gimple_assign_rhs1 (negatedefstmt
);
3895 tree rhs2
= gimple_assign_rhs2 (negatedefstmt
);
3896 tree lhs
= gimple_assign_lhs (negatedefstmt
);
3899 gsi
= gsi_for_stmt (negatedefstmt
);
3900 rhs1
= negate_value (rhs1
, &gsi
);
3902 gsi
= gsi_for_stmt (negatedefstmt
);
3903 rhs2
= negate_value (rhs2
, &gsi
);
3905 gsi
= gsi_for_stmt (negatedefstmt
);
3906 lhs
= make_ssa_name (TREE_TYPE (lhs
));
3907 gimple_set_visited (negatedefstmt
, true);
3908 g
= gimple_build_assign (lhs
, PLUS_EXPR
, rhs1
, rhs2
);
3909 gimple_set_uid (g
, gimple_uid (negatedefstmt
));
3910 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
3914 tonegate
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (tonegate
), tonegate
);
3915 resultofnegate
= force_gimple_operand_gsi (gsip
, tonegate
, true,
3916 NULL_TREE
, true, GSI_SAME_STMT
);
3918 uid
= gimple_uid (gsi_stmt (gsi
));
3919 for (gsi_prev (&gsi
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
3921 gimple stmt
= gsi_stmt (gsi
);
3922 if (gimple_uid (stmt
) != 0)
3924 gimple_set_uid (stmt
, uid
);
3926 return resultofnegate
;
3929 /* Return true if we should break up the subtract in STMT into an add
3930 with negate. This is true when we the subtract operands are really
3931 adds, or the subtract itself is used in an add expression. In
3932 either case, breaking up the subtract into an add with negate
3933 exposes the adds to reassociation. */
3936 should_break_up_subtract (gimple stmt
)
3938 tree lhs
= gimple_assign_lhs (stmt
);
3939 tree binlhs
= gimple_assign_rhs1 (stmt
);
3940 tree binrhs
= gimple_assign_rhs2 (stmt
);
3942 struct loop
*loop
= loop_containing_stmt (stmt
);
3944 if (TREE_CODE (binlhs
) == SSA_NAME
3945 && is_reassociable_op (SSA_NAME_DEF_STMT (binlhs
), PLUS_EXPR
, loop
))
3948 if (TREE_CODE (binrhs
) == SSA_NAME
3949 && is_reassociable_op (SSA_NAME_DEF_STMT (binrhs
), PLUS_EXPR
, loop
))
3952 if (TREE_CODE (lhs
) == SSA_NAME
3953 && (immusestmt
= get_single_immediate_use (lhs
))
3954 && is_gimple_assign (immusestmt
)
3955 && (gimple_assign_rhs_code (immusestmt
) == PLUS_EXPR
3956 || gimple_assign_rhs_code (immusestmt
) == MULT_EXPR
))
3961 /* Transform STMT from A - B into A + -B. */
3964 break_up_subtract (gimple stmt
, gimple_stmt_iterator
*gsip
)
3966 tree rhs1
= gimple_assign_rhs1 (stmt
);
3967 tree rhs2
= gimple_assign_rhs2 (stmt
);
3969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3971 fprintf (dump_file
, "Breaking up subtract ");
3972 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3975 rhs2
= negate_value (rhs2
, gsip
);
3976 gimple_assign_set_rhs_with_ops (gsip
, PLUS_EXPR
, rhs1
, rhs2
);
3980 /* Determine whether STMT is a builtin call that raises an SSA name
3981 to an integer power and has only one use. If so, and this is early
3982 reassociation and unsafe math optimizations are permitted, place
3983 the SSA name in *BASE and the exponent in *EXPONENT, and return TRUE.
3984 If any of these conditions does not hold, return FALSE. */
3987 acceptable_pow_call (gimple stmt
, tree
*base
, HOST_WIDE_INT
*exponent
)
3990 REAL_VALUE_TYPE c
, cint
;
3992 if (!first_pass_instance
3993 || !flag_unsafe_math_optimizations
3994 || !is_gimple_call (stmt
)
3995 || !has_single_use (gimple_call_lhs (stmt
)))
3998 fndecl
= gimple_call_fndecl (stmt
);
4001 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
4004 switch (DECL_FUNCTION_CODE (fndecl
))
4006 CASE_FLT_FN (BUILT_IN_POW
):
4007 if (flag_errno_math
)
4010 *base
= gimple_call_arg (stmt
, 0);
4011 arg1
= gimple_call_arg (stmt
, 1);
4013 if (TREE_CODE (arg1
) != REAL_CST
)
4016 c
= TREE_REAL_CST (arg1
);
4018 if (REAL_EXP (&c
) > HOST_BITS_PER_WIDE_INT
)
4021 *exponent
= real_to_integer (&c
);
4022 real_from_integer (&cint
, VOIDmode
, *exponent
, SIGNED
);
4023 if (!real_identical (&c
, &cint
))
4028 CASE_FLT_FN (BUILT_IN_POWI
):
4029 *base
= gimple_call_arg (stmt
, 0);
4030 arg1
= gimple_call_arg (stmt
, 1);
4032 if (!tree_fits_shwi_p (arg1
))
4035 *exponent
= tree_to_shwi (arg1
);
4042 /* Expanding negative exponents is generally unproductive, so we don't
4043 complicate matters with those. Exponents of zero and one should
4044 have been handled by expression folding. */
4045 if (*exponent
< 2 || TREE_CODE (*base
) != SSA_NAME
)
4051 /* Recursively linearize a binary expression that is the RHS of STMT.
4052 Place the operands of the expression tree in the vector named OPS. */
4055 linearize_expr_tree (vec
<operand_entry_t
> *ops
, gimple stmt
,
4056 bool is_associative
, bool set_visited
)
4058 tree binlhs
= gimple_assign_rhs1 (stmt
);
4059 tree binrhs
= gimple_assign_rhs2 (stmt
);
4060 gimple binlhsdef
= NULL
, binrhsdef
= NULL
;
4061 bool binlhsisreassoc
= false;
4062 bool binrhsisreassoc
= false;
4063 enum tree_code rhscode
= gimple_assign_rhs_code (stmt
);
4064 struct loop
*loop
= loop_containing_stmt (stmt
);
4065 tree base
= NULL_TREE
;
4066 HOST_WIDE_INT exponent
= 0;
4069 gimple_set_visited (stmt
, true);
4071 if (TREE_CODE (binlhs
) == SSA_NAME
)
4073 binlhsdef
= SSA_NAME_DEF_STMT (binlhs
);
4074 binlhsisreassoc
= (is_reassociable_op (binlhsdef
, rhscode
, loop
)
4075 && !stmt_could_throw_p (binlhsdef
));
4078 if (TREE_CODE (binrhs
) == SSA_NAME
)
4080 binrhsdef
= SSA_NAME_DEF_STMT (binrhs
);
4081 binrhsisreassoc
= (is_reassociable_op (binrhsdef
, rhscode
, loop
)
4082 && !stmt_could_throw_p (binrhsdef
));
4085 /* If the LHS is not reassociable, but the RHS is, we need to swap
4086 them. If neither is reassociable, there is nothing we can do, so
4087 just put them in the ops vector. If the LHS is reassociable,
4088 linearize it. If both are reassociable, then linearize the RHS
4091 if (!binlhsisreassoc
)
4093 /* If this is not a associative operation like division, give up. */
4094 if (!is_associative
)
4096 add_to_ops_vec (ops
, binrhs
);
4100 if (!binrhsisreassoc
)
4102 if (rhscode
== MULT_EXPR
4103 && TREE_CODE (binrhs
) == SSA_NAME
4104 && acceptable_pow_call (binrhsdef
, &base
, &exponent
))
4106 add_repeat_to_ops_vec (ops
, base
, exponent
);
4107 gimple_set_visited (binrhsdef
, true);
4110 add_to_ops_vec (ops
, binrhs
);
4112 if (rhscode
== MULT_EXPR
4113 && TREE_CODE (binlhs
) == SSA_NAME
4114 && acceptable_pow_call (binlhsdef
, &base
, &exponent
))
4116 add_repeat_to_ops_vec (ops
, base
, exponent
);
4117 gimple_set_visited (binlhsdef
, true);
4120 add_to_ops_vec (ops
, binlhs
);
4125 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4127 fprintf (dump_file
, "swapping operands of ");
4128 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4131 swap_ssa_operands (stmt
,
4132 gimple_assign_rhs1_ptr (stmt
),
4133 gimple_assign_rhs2_ptr (stmt
));
4136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4138 fprintf (dump_file
, " is now ");
4139 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4142 /* We want to make it so the lhs is always the reassociative op,
4144 std::swap (binlhs
, binrhs
);
4146 else if (binrhsisreassoc
)
4148 linearize_expr (stmt
);
4149 binlhs
= gimple_assign_rhs1 (stmt
);
4150 binrhs
= gimple_assign_rhs2 (stmt
);
4153 gcc_assert (TREE_CODE (binrhs
) != SSA_NAME
4154 || !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs
),
4156 linearize_expr_tree (ops
, SSA_NAME_DEF_STMT (binlhs
),
4157 is_associative
, set_visited
);
4159 if (rhscode
== MULT_EXPR
4160 && TREE_CODE (binrhs
) == SSA_NAME
4161 && acceptable_pow_call (SSA_NAME_DEF_STMT (binrhs
), &base
, &exponent
))
4163 add_repeat_to_ops_vec (ops
, base
, exponent
);
4164 gimple_set_visited (SSA_NAME_DEF_STMT (binrhs
), true);
4167 add_to_ops_vec (ops
, binrhs
);
4170 /* Repropagate the negates back into subtracts, since no other pass
4171 currently does it. */
4174 repropagate_negates (void)
4179 FOR_EACH_VEC_ELT (plus_negates
, i
, negate
)
4181 gimple user
= get_single_immediate_use (negate
);
4183 if (!user
|| !is_gimple_assign (user
))
4186 /* The negate operand can be either operand of a PLUS_EXPR
4187 (it can be the LHS if the RHS is a constant for example).
4189 Force the negate operand to the RHS of the PLUS_EXPR, then
4190 transform the PLUS_EXPR into a MINUS_EXPR. */
4191 if (gimple_assign_rhs_code (user
) == PLUS_EXPR
)
4193 /* If the negated operand appears on the LHS of the
4194 PLUS_EXPR, exchange the operands of the PLUS_EXPR
4195 to force the negated operand to the RHS of the PLUS_EXPR. */
4196 if (gimple_assign_rhs1 (user
) == negate
)
4198 swap_ssa_operands (user
,
4199 gimple_assign_rhs1_ptr (user
),
4200 gimple_assign_rhs2_ptr (user
));
4203 /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
4204 the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. */
4205 if (gimple_assign_rhs2 (user
) == negate
)
4207 tree rhs1
= gimple_assign_rhs1 (user
);
4208 tree rhs2
= get_unary_op (negate
, NEGATE_EXPR
);
4209 gimple_stmt_iterator gsi
= gsi_for_stmt (user
);
4210 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, rhs1
, rhs2
);
4214 else if (gimple_assign_rhs_code (user
) == MINUS_EXPR
)
4216 if (gimple_assign_rhs1 (user
) == negate
)
4221 which we transform into
4224 This pushes down the negate which we possibly can merge
4225 into some other operation, hence insert it into the
4226 plus_negates vector. */
4227 gimple feed
= SSA_NAME_DEF_STMT (negate
);
4228 tree a
= gimple_assign_rhs1 (feed
);
4229 tree b
= gimple_assign_rhs2 (user
);
4230 gimple_stmt_iterator gsi
= gsi_for_stmt (feed
);
4231 gimple_stmt_iterator gsi2
= gsi_for_stmt (user
);
4232 tree x
= make_ssa_name (TREE_TYPE (gimple_assign_lhs (feed
)));
4233 gimple g
= gimple_build_assign (x
, PLUS_EXPR
, a
, b
);
4234 gsi_insert_before (&gsi2
, g
, GSI_SAME_STMT
);
4235 gimple_assign_set_rhs_with_ops (&gsi2
, NEGATE_EXPR
, x
);
4236 user
= gsi_stmt (gsi2
);
4238 reassoc_remove_stmt (&gsi
);
4239 release_defs (feed
);
4240 plus_negates
.safe_push (gimple_assign_lhs (user
));
4244 /* Transform "x = -a; y = b - x" into "y = b + a", getting
4245 rid of one operation. */
4246 gimple feed
= SSA_NAME_DEF_STMT (negate
);
4247 tree a
= gimple_assign_rhs1 (feed
);
4248 tree rhs1
= gimple_assign_rhs1 (user
);
4249 gimple_stmt_iterator gsi
= gsi_for_stmt (user
);
4250 gimple_assign_set_rhs_with_ops (&gsi
, PLUS_EXPR
, rhs1
, a
);
4251 update_stmt (gsi_stmt (gsi
));
4257 /* Returns true if OP is of a type for which we can do reassociation.
4258 That is for integral or non-saturating fixed-point types, and for
4259 floating point type when associative-math is enabled. */
4262 can_reassociate_p (tree op
)
4264 tree type
= TREE_TYPE (op
);
4265 if ((INTEGRAL_TYPE_P (type
) && TYPE_OVERFLOW_WRAPS (type
))
4266 || NON_SAT_FIXED_POINT_TYPE_P (type
)
4267 || (flag_associative_math
&& FLOAT_TYPE_P (type
)))
4272 /* Break up subtract operations in block BB.
4274 We do this top down because we don't know whether the subtract is
4275 part of a possible chain of reassociation except at the top.
4284 we want to break up k = t - q, but we won't until we've transformed q
4285 = b - r, which won't be broken up until we transform b = c - d.
4287 En passant, clear the GIMPLE visited flag on every statement
4288 and set UIDs within each basic block. */
4291 break_up_subtract_bb (basic_block bb
)
4293 gimple_stmt_iterator gsi
;
4295 unsigned int uid
= 1;
4297 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4299 gimple stmt
= gsi_stmt (gsi
);
4300 gimple_set_visited (stmt
, false);
4301 gimple_set_uid (stmt
, uid
++);
4303 if (!is_gimple_assign (stmt
)
4304 || !can_reassociate_p (gimple_assign_lhs (stmt
)))
4307 /* Look for simple gimple subtract operations. */
4308 if (gimple_assign_rhs_code (stmt
) == MINUS_EXPR
)
4310 if (!can_reassociate_p (gimple_assign_rhs1 (stmt
))
4311 || !can_reassociate_p (gimple_assign_rhs2 (stmt
)))
4314 /* Check for a subtract used only in an addition. If this
4315 is the case, transform it into add of a negate for better
4316 reassociation. IE transform C = A-B into C = A + -B if C
4317 is only used in an addition. */
4318 if (should_break_up_subtract (stmt
))
4319 break_up_subtract (stmt
, &gsi
);
4321 else if (gimple_assign_rhs_code (stmt
) == NEGATE_EXPR
4322 && can_reassociate_p (gimple_assign_rhs1 (stmt
)))
4323 plus_negates
.safe_push (gimple_assign_lhs (stmt
));
4325 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
4327 son
= next_dom_son (CDI_DOMINATORS
, son
))
4328 break_up_subtract_bb (son
);
4331 /* Used for repeated factor analysis. */
4332 struct repeat_factor_d
4334 /* An SSA name that occurs in a multiply chain. */
4337 /* Cached rank of the factor. */
4340 /* Number of occurrences of the factor in the chain. */
4341 HOST_WIDE_INT count
;
4343 /* An SSA name representing the product of this factor and
4344 all factors appearing later in the repeated factor vector. */
4348 typedef struct repeat_factor_d repeat_factor
, *repeat_factor_t
;
4349 typedef const struct repeat_factor_d
*const_repeat_factor_t
;
4352 static vec
<repeat_factor
> repeat_factor_vec
;
4354 /* Used for sorting the repeat factor vector. Sort primarily by
4355 ascending occurrence count, secondarily by descending rank. */
4358 compare_repeat_factors (const void *x1
, const void *x2
)
4360 const_repeat_factor_t rf1
= (const_repeat_factor_t
) x1
;
4361 const_repeat_factor_t rf2
= (const_repeat_factor_t
) x2
;
4363 if (rf1
->count
!= rf2
->count
)
4364 return rf1
->count
- rf2
->count
;
4366 return rf2
->rank
- rf1
->rank
;
4369 /* Look for repeated operands in OPS in the multiply tree rooted at
4370 STMT. Replace them with an optimal sequence of multiplies and powi
4371 builtin calls, and remove the used operands from OPS. Return an
4372 SSA name representing the value of the replacement sequence. */
4375 attempt_builtin_powi (gimple stmt
, vec
<operand_entry_t
> *ops
)
4377 unsigned i
, j
, vec_len
;
4380 repeat_factor_t rf1
, rf2
;
4381 repeat_factor rfnew
;
4382 tree result
= NULL_TREE
;
4383 tree target_ssa
, iter_result
;
4384 tree type
= TREE_TYPE (gimple_get_lhs (stmt
));
4385 tree powi_fndecl
= mathfn_built_in (type
, BUILT_IN_POWI
);
4386 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
4387 gimple mul_stmt
, pow_stmt
;
4389 /* Nothing to do if BUILT_IN_POWI doesn't exist for this type and
4394 /* Allocate the repeated factor vector. */
4395 repeat_factor_vec
.create (10);
4397 /* Scan the OPS vector for all SSA names in the product and build
4398 up a vector of occurrence counts for each factor. */
4399 FOR_EACH_VEC_ELT (*ops
, i
, oe
)
4401 if (TREE_CODE (oe
->op
) == SSA_NAME
)
4403 FOR_EACH_VEC_ELT (repeat_factor_vec
, j
, rf1
)
4405 if (rf1
->factor
== oe
->op
)
4407 rf1
->count
+= oe
->count
;
4412 if (j
>= repeat_factor_vec
.length ())
4414 rfnew
.factor
= oe
->op
;
4415 rfnew
.rank
= oe
->rank
;
4416 rfnew
.count
= oe
->count
;
4417 rfnew
.repr
= NULL_TREE
;
4418 repeat_factor_vec
.safe_push (rfnew
);
4423 /* Sort the repeated factor vector by (a) increasing occurrence count,
4424 and (b) decreasing rank. */
4425 repeat_factor_vec
.qsort (compare_repeat_factors
);
4427 /* It is generally best to combine as many base factors as possible
4428 into a product before applying __builtin_powi to the result.
4429 However, the sort order chosen for the repeated factor vector
4430 allows us to cache partial results for the product of the base
4431 factors for subsequent use. When we already have a cached partial
4432 result from a previous iteration, it is best to make use of it
4433 before looking for another __builtin_pow opportunity.
4435 As an example, consider x * x * y * y * y * z * z * z * z.
4436 We want to first compose the product x * y * z, raise it to the
4437 second power, then multiply this by y * z, and finally multiply
4438 by z. This can be done in 5 multiplies provided we cache y * z
4439 for use in both expressions:
4447 If we instead ignored the cached y * z and first multiplied by
4448 the __builtin_pow opportunity z * z, we would get the inferior:
4457 vec_len
= repeat_factor_vec
.length ();
4459 /* Repeatedly look for opportunities to create a builtin_powi call. */
4462 HOST_WIDE_INT power
;
4464 /* First look for the largest cached product of factors from
4465 preceding iterations. If found, create a builtin_powi for
4466 it if the minimum occurrence count for its factors is at
4467 least 2, or just use this cached product as our next
4468 multiplicand if the minimum occurrence count is 1. */
4469 FOR_EACH_VEC_ELT (repeat_factor_vec
, j
, rf1
)
4471 if (rf1
->repr
&& rf1
->count
> 0)
4481 iter_result
= rf1
->repr
;
4483 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4487 fputs ("Multiplying by cached product ", dump_file
);
4488 for (elt
= j
; elt
< vec_len
; elt
++)
4490 rf
= &repeat_factor_vec
[elt
];
4491 print_generic_expr (dump_file
, rf
->factor
, 0);
4492 if (elt
< vec_len
- 1)
4493 fputs (" * ", dump_file
);
4495 fputs ("\n", dump_file
);
4500 iter_result
= make_temp_ssa_name (type
, NULL
, "reassocpow");
4501 pow_stmt
= gimple_build_call (powi_fndecl
, 2, rf1
->repr
,
4502 build_int_cst (integer_type_node
,
4504 gimple_call_set_lhs (pow_stmt
, iter_result
);
4505 gimple_set_location (pow_stmt
, gimple_location (stmt
));
4506 gsi_insert_before (&gsi
, pow_stmt
, GSI_SAME_STMT
);
4508 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4512 fputs ("Building __builtin_pow call for cached product (",
4514 for (elt
= j
; elt
< vec_len
; elt
++)
4516 rf
= &repeat_factor_vec
[elt
];
4517 print_generic_expr (dump_file
, rf
->factor
, 0);
4518 if (elt
< vec_len
- 1)
4519 fputs (" * ", dump_file
);
4521 fprintf (dump_file
, ")^" HOST_WIDE_INT_PRINT_DEC
"\n",
4528 /* Otherwise, find the first factor in the repeated factor
4529 vector whose occurrence count is at least 2. If no such
4530 factor exists, there are no builtin_powi opportunities
4532 FOR_EACH_VEC_ELT (repeat_factor_vec
, j
, rf1
)
4534 if (rf1
->count
>= 2)
4543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4547 fputs ("Building __builtin_pow call for (", dump_file
);
4548 for (elt
= j
; elt
< vec_len
; elt
++)
4550 rf
= &repeat_factor_vec
[elt
];
4551 print_generic_expr (dump_file
, rf
->factor
, 0);
4552 if (elt
< vec_len
- 1)
4553 fputs (" * ", dump_file
);
4555 fprintf (dump_file
, ")^" HOST_WIDE_INT_PRINT_DEC
"\n", power
);
4558 reassociate_stats
.pows_created
++;
4560 /* Visit each element of the vector in reverse order (so that
4561 high-occurrence elements are visited first, and within the
4562 same occurrence count, lower-ranked elements are visited
4563 first). Form a linear product of all elements in this order
4564 whose occurrencce count is at least that of element J.
4565 Record the SSA name representing the product of each element
4566 with all subsequent elements in the vector. */
4567 if (j
== vec_len
- 1)
4568 rf1
->repr
= rf1
->factor
;
4571 for (ii
= vec_len
- 2; ii
>= (int)j
; ii
--)
4575 rf1
= &repeat_factor_vec
[ii
];
4576 rf2
= &repeat_factor_vec
[ii
+ 1];
4578 /* Init the last factor's representative to be itself. */
4580 rf2
->repr
= rf2
->factor
;
4585 target_ssa
= make_temp_ssa_name (type
, NULL
, "reassocpow");
4586 mul_stmt
= gimple_build_assign (target_ssa
, MULT_EXPR
,
4588 gimple_set_location (mul_stmt
, gimple_location (stmt
));
4589 gsi_insert_before (&gsi
, mul_stmt
, GSI_SAME_STMT
);
4590 rf1
->repr
= target_ssa
;
4592 /* Don't reprocess the multiply we just introduced. */
4593 gimple_set_visited (mul_stmt
, true);
4597 /* Form a call to __builtin_powi for the maximum product
4598 just formed, raised to the power obtained earlier. */
4599 rf1
= &repeat_factor_vec
[j
];
4600 iter_result
= make_temp_ssa_name (type
, NULL
, "reassocpow");
4601 pow_stmt
= gimple_build_call (powi_fndecl
, 2, rf1
->repr
,
4602 build_int_cst (integer_type_node
,
4604 gimple_call_set_lhs (pow_stmt
, iter_result
);
4605 gimple_set_location (pow_stmt
, gimple_location (stmt
));
4606 gsi_insert_before (&gsi
, pow_stmt
, GSI_SAME_STMT
);
4609 /* If we previously formed at least one other builtin_powi call,
4610 form the product of this one and those others. */
4613 tree new_result
= make_temp_ssa_name (type
, NULL
, "reassocpow");
4614 mul_stmt
= gimple_build_assign (new_result
, MULT_EXPR
,
4615 result
, iter_result
);
4616 gimple_set_location (mul_stmt
, gimple_location (stmt
));
4617 gsi_insert_before (&gsi
, mul_stmt
, GSI_SAME_STMT
);
4618 gimple_set_visited (mul_stmt
, true);
4619 result
= new_result
;
4622 result
= iter_result
;
4624 /* Decrement the occurrence count of each element in the product
4625 by the count found above, and remove this many copies of each
4627 for (i
= j
; i
< vec_len
; i
++)
4632 rf1
= &repeat_factor_vec
[i
];
4633 rf1
->count
-= power
;
4635 FOR_EACH_VEC_ELT_REVERSE (*ops
, n
, oe
)
4637 if (oe
->op
== rf1
->factor
)
4641 ops
->ordered_remove (n
);
4657 /* At this point all elements in the repeated factor vector have a
4658 remaining occurrence count of 0 or 1, and those with a count of 1
4659 don't have cached representatives. Re-sort the ops vector and
4661 ops
->qsort (sort_by_operand_rank
);
4662 repeat_factor_vec
.release ();
4664 /* Return the final product computed herein. Note that there may
4665 still be some elements with single occurrence count left in OPS;
4666 those will be handled by the normal reassociation logic. */
4670 /* Transform STMT at *GSI into a copy by replacing its rhs with NEW_RHS. */
4673 transform_stmt_to_copy (gimple_stmt_iterator
*gsi
, gimple stmt
, tree new_rhs
)
4677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4679 fprintf (dump_file
, "Transforming ");
4680 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4683 rhs1
= gimple_assign_rhs1 (stmt
);
4684 gimple_assign_set_rhs_from_tree (gsi
, new_rhs
);
4686 remove_visited_stmt_chain (rhs1
);
4688 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4690 fprintf (dump_file
, " into ");
4691 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4695 /* Transform STMT at *GSI into a multiply of RHS1 and RHS2. */
4698 transform_stmt_to_multiply (gimple_stmt_iterator
*gsi
, gimple stmt
,
4699 tree rhs1
, tree rhs2
)
4701 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4703 fprintf (dump_file
, "Transforming ");
4704 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4707 gimple_assign_set_rhs_with_ops (gsi
, MULT_EXPR
, rhs1
, rhs2
);
4708 update_stmt (gsi_stmt (*gsi
));
4709 remove_visited_stmt_chain (rhs1
);
4711 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4713 fprintf (dump_file
, " into ");
4714 print_gimple_stmt (dump_file
, stmt
, 0, 0);
4718 /* Reassociate expressions in basic block BB and its post-dominator as
4722 reassociate_bb (basic_block bb
)
4724 gimple_stmt_iterator gsi
;
4726 gimple stmt
= last_stmt (bb
);
4728 if (stmt
&& !gimple_visited_p (stmt
))
4729 maybe_optimize_range_tests (stmt
);
4731 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
4733 stmt
= gsi_stmt (gsi
);
4735 if (is_gimple_assign (stmt
)
4736 && !stmt_could_throw_p (stmt
))
4738 tree lhs
, rhs1
, rhs2
;
4739 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
4741 /* If this is not a gimple binary expression, there is
4742 nothing for us to do with it. */
4743 if (get_gimple_rhs_class (rhs_code
) != GIMPLE_BINARY_RHS
)
4746 /* If this was part of an already processed statement,
4747 we don't need to touch it again. */
4748 if (gimple_visited_p (stmt
))
4750 /* This statement might have become dead because of previous
4752 if (has_zero_uses (gimple_get_lhs (stmt
)))
4754 reassoc_remove_stmt (&gsi
);
4755 release_defs (stmt
);
4756 /* We might end up removing the last stmt above which
4757 places the iterator to the end of the sequence.
4758 Reset it to the last stmt in this case which might
4759 be the end of the sequence as well if we removed
4760 the last statement of the sequence. In which case
4761 we need to bail out. */
4762 if (gsi_end_p (gsi
))
4764 gsi
= gsi_last_bb (bb
);
4765 if (gsi_end_p (gsi
))
4772 lhs
= gimple_assign_lhs (stmt
);
4773 rhs1
= gimple_assign_rhs1 (stmt
);
4774 rhs2
= gimple_assign_rhs2 (stmt
);
4776 /* For non-bit or min/max operations we can't associate
4777 all types. Verify that here. */
4778 if (rhs_code
!= BIT_IOR_EXPR
4779 && rhs_code
!= BIT_AND_EXPR
4780 && rhs_code
!= BIT_XOR_EXPR
4781 && rhs_code
!= MIN_EXPR
4782 && rhs_code
!= MAX_EXPR
4783 && (!can_reassociate_p (lhs
)
4784 || !can_reassociate_p (rhs1
)
4785 || !can_reassociate_p (rhs2
)))
4788 if (associative_tree_code (rhs_code
))
4790 auto_vec
<operand_entry_t
> ops
;
4791 tree powi_result
= NULL_TREE
;
4793 /* There may be no immediate uses left by the time we
4794 get here because we may have eliminated them all. */
4795 if (TREE_CODE (lhs
) == SSA_NAME
&& has_zero_uses (lhs
))
4798 gimple_set_visited (stmt
, true);
4799 linearize_expr_tree (&ops
, stmt
, true, true);
4800 ops
.qsort (sort_by_operand_rank
);
4801 optimize_ops_list (rhs_code
, &ops
);
4802 if (undistribute_ops_list (rhs_code
, &ops
,
4803 loop_containing_stmt (stmt
)))
4805 ops
.qsort (sort_by_operand_rank
);
4806 optimize_ops_list (rhs_code
, &ops
);
4809 if (rhs_code
== BIT_IOR_EXPR
|| rhs_code
== BIT_AND_EXPR
)
4810 optimize_range_tests (rhs_code
, &ops
);
4812 if (first_pass_instance
4813 && rhs_code
== MULT_EXPR
4814 && flag_unsafe_math_optimizations
)
4815 powi_result
= attempt_builtin_powi (stmt
, &ops
);
4817 /* If the operand vector is now empty, all operands were
4818 consumed by the __builtin_powi optimization. */
4819 if (ops
.length () == 0)
4820 transform_stmt_to_copy (&gsi
, stmt
, powi_result
);
4821 else if (ops
.length () == 1)
4823 tree last_op
= ops
.last ()->op
;
4826 transform_stmt_to_multiply (&gsi
, stmt
, last_op
,
4829 transform_stmt_to_copy (&gsi
, stmt
, last_op
);
4833 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
4834 int ops_num
= ops
.length ();
4835 int width
= get_reassociation_width (ops_num
, rhs_code
, mode
);
4838 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4840 "Width = %d was chosen for reassociation\n", width
);
4843 && ops
.length () > 3)
4844 rewrite_expr_tree_parallel (as_a
<gassign
*> (stmt
),
4848 /* When there are three operands left, we want
4849 to make sure the ones that get the double
4850 binary op are chosen wisely. */
4851 int len
= ops
.length ();
4853 swap_ops_for_binary_stmt (ops
, len
- 3, stmt
);
4855 new_lhs
= rewrite_expr_tree (stmt
, 0, ops
,
4856 powi_result
!= NULL
);
4859 /* If we combined some repeated factors into a
4860 __builtin_powi call, multiply that result by the
4861 reassociated operands. */
4864 gimple mul_stmt
, lhs_stmt
= SSA_NAME_DEF_STMT (lhs
);
4865 tree type
= TREE_TYPE (lhs
);
4866 tree target_ssa
= make_temp_ssa_name (type
, NULL
,
4868 gimple_set_lhs (lhs_stmt
, target_ssa
);
4869 update_stmt (lhs_stmt
);
4871 target_ssa
= new_lhs
;
4872 mul_stmt
= gimple_build_assign (lhs
, MULT_EXPR
,
4873 powi_result
, target_ssa
);
4874 gimple_set_location (mul_stmt
, gimple_location (stmt
));
4875 gsi_insert_after (&gsi
, mul_stmt
, GSI_NEW_STMT
);
4881 for (son
= first_dom_son (CDI_POST_DOMINATORS
, bb
);
4883 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
4884 reassociate_bb (son
);
4887 /* Add jumps around shifts for range tests turned into bit tests.
4888 For each SSA_NAME VAR we have code like:
4889 VAR = ...; // final stmt of range comparison
4890 // bit test here...;
4891 OTHERVAR = ...; // final stmt of the bit test sequence
4892 RES = VAR | OTHERVAR;
4893 Turn the above into:
4900 // bit test here...;
4903 # RES = PHI<1(l1), OTHERVAR(l2)>; */
4911 FOR_EACH_VEC_ELT (reassoc_branch_fixups
, i
, var
)
4913 gimple def_stmt
= SSA_NAME_DEF_STMT (var
);
4916 bool ok
= single_imm_use (var
, &use
, &use_stmt
);
4918 && is_gimple_assign (use_stmt
)
4919 && gimple_assign_rhs_code (use_stmt
) == BIT_IOR_EXPR
4920 && gimple_bb (def_stmt
) == gimple_bb (use_stmt
));
4922 basic_block cond_bb
= gimple_bb (def_stmt
);
4923 basic_block then_bb
= split_block (cond_bb
, def_stmt
)->dest
;
4924 basic_block merge_bb
= split_block (then_bb
, use_stmt
)->dest
;
4926 gimple_stmt_iterator gsi
= gsi_for_stmt (def_stmt
);
4927 gimple g
= gimple_build_cond (NE_EXPR
, var
,
4928 build_zero_cst (TREE_TYPE (var
)),
4929 NULL_TREE
, NULL_TREE
);
4930 location_t loc
= gimple_location (use_stmt
);
4931 gimple_set_location (g
, loc
);
4932 gsi_insert_after (&gsi
, g
, GSI_NEW_STMT
);
4934 edge etrue
= make_edge (cond_bb
, merge_bb
, EDGE_TRUE_VALUE
);
4935 etrue
->probability
= REG_BR_PROB_BASE
/ 2;
4936 etrue
->count
= cond_bb
->count
/ 2;
4937 edge efalse
= find_edge (cond_bb
, then_bb
);
4938 efalse
->flags
= EDGE_FALSE_VALUE
;
4939 efalse
->probability
-= etrue
->probability
;
4940 efalse
->count
-= etrue
->count
;
4941 then_bb
->count
-= etrue
->count
;
4943 tree othervar
= NULL_TREE
;
4944 if (gimple_assign_rhs1 (use_stmt
) == var
)
4945 othervar
= gimple_assign_rhs2 (use_stmt
);
4946 else if (gimple_assign_rhs2 (use_stmt
) == var
)
4947 othervar
= gimple_assign_rhs1 (use_stmt
);
4950 tree lhs
= gimple_assign_lhs (use_stmt
);
4951 gphi
*phi
= create_phi_node (lhs
, merge_bb
);
4952 add_phi_arg (phi
, build_one_cst (TREE_TYPE (lhs
)), etrue
, loc
);
4953 add_phi_arg (phi
, othervar
, single_succ_edge (then_bb
), loc
);
4954 gsi
= gsi_for_stmt (use_stmt
);
4955 gsi_remove (&gsi
, true);
4957 set_immediate_dominator (CDI_DOMINATORS
, merge_bb
, cond_bb
);
4958 set_immediate_dominator (CDI_POST_DOMINATORS
, cond_bb
, merge_bb
);
4960 reassoc_branch_fixups
.release ();
4963 void dump_ops_vector (FILE *file
, vec
<operand_entry_t
> ops
);
4964 void debug_ops_vector (vec
<operand_entry_t
> ops
);
4966 /* Dump the operand entry vector OPS to FILE. */
4969 dump_ops_vector (FILE *file
, vec
<operand_entry_t
> ops
)
4974 FOR_EACH_VEC_ELT (ops
, i
, oe
)
4976 fprintf (file
, "Op %d -> rank: %d, tree: ", i
, oe
->rank
);
4977 print_generic_expr (file
, oe
->op
, 0);
4981 /* Dump the operand entry vector OPS to STDERR. */
4984 debug_ops_vector (vec
<operand_entry_t
> ops
)
4986 dump_ops_vector (stderr
, ops
);
4992 break_up_subtract_bb (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4993 reassociate_bb (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4996 /* Initialize the reassociation pass. */
5003 int *bbs
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
5005 /* Find the loops, so that we can prevent moving calculations in
5007 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
5009 memset (&reassociate_stats
, 0, sizeof (reassociate_stats
));
5011 operand_entry_pool
= create_alloc_pool ("operand entry pool",
5012 sizeof (struct operand_entry
), 30);
5013 next_operand_entry_id
= 0;
5015 /* Reverse RPO (Reverse Post Order) will give us something where
5016 deeper loops come later. */
5017 pre_and_rev_post_order_compute (NULL
, bbs
, false);
5018 bb_rank
= XCNEWVEC (long, last_basic_block_for_fn (cfun
));
5019 operand_rank
= new hash_map
<tree
, long>;
5021 /* Give each default definition a distinct rank. This includes
5022 parameters and the static chain. Walk backwards over all
5023 SSA names so that we get proper rank ordering according
5024 to tree_swap_operands_p. */
5025 for (i
= num_ssa_names
- 1; i
> 0; --i
)
5027 tree name
= ssa_name (i
);
5028 if (name
&& SSA_NAME_IS_DEFAULT_DEF (name
))
5029 insert_operand_rank (name
, ++rank
);
5032 /* Set up rank for each BB */
5033 for (i
= 0; i
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; i
++)
5034 bb_rank
[bbs
[i
]] = ++rank
<< 16;
5037 calculate_dominance_info (CDI_POST_DOMINATORS
);
5038 plus_negates
= vNULL
;
5041 /* Cleanup after the reassociation pass, and print stats if
5047 statistics_counter_event (cfun
, "Linearized",
5048 reassociate_stats
.linearized
);
5049 statistics_counter_event (cfun
, "Constants eliminated",
5050 reassociate_stats
.constants_eliminated
);
5051 statistics_counter_event (cfun
, "Ops eliminated",
5052 reassociate_stats
.ops_eliminated
);
5053 statistics_counter_event (cfun
, "Statements rewritten",
5054 reassociate_stats
.rewritten
);
5055 statistics_counter_event (cfun
, "Built-in pow[i] calls encountered",
5056 reassociate_stats
.pows_encountered
);
5057 statistics_counter_event (cfun
, "Built-in powi calls created",
5058 reassociate_stats
.pows_created
);
5060 delete operand_rank
;
5061 free_alloc_pool (operand_entry_pool
);
5063 plus_negates
.release ();
5064 free_dominance_info (CDI_POST_DOMINATORS
);
5065 loop_optimizer_finalize ();
5068 /* Gate and execute functions for Reassociation. */
5071 execute_reassoc (void)
5076 repropagate_negates ();
5085 const pass_data pass_data_reassoc
=
5087 GIMPLE_PASS
, /* type */
5088 "reassoc", /* name */
5089 OPTGROUP_NONE
, /* optinfo_flags */
5090 TV_TREE_REASSOC
, /* tv_id */
5091 ( PROP_cfg
| PROP_ssa
), /* properties_required */
5092 0, /* properties_provided */
5093 0, /* properties_destroyed */
5094 0, /* todo_flags_start */
5095 TODO_update_ssa_only_virtuals
, /* todo_flags_finish */
5098 class pass_reassoc
: public gimple_opt_pass
5101 pass_reassoc (gcc::context
*ctxt
)
5102 : gimple_opt_pass (pass_data_reassoc
, ctxt
)
5105 /* opt_pass methods: */
5106 opt_pass
* clone () { return new pass_reassoc (m_ctxt
); }
5107 virtual bool gate (function
*) { return flag_tree_reassoc
!= 0; }
5108 virtual unsigned int execute (function
*) { return execute_reassoc (); }
5110 }; // class pass_reassoc
5115 make_pass_reassoc (gcc::context
*ctxt
)
5117 return new pass_reassoc (ctxt
);