1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2019 Free Software Foundation, Inc.
3 Contributed by Devang Patel <dpatel@apple.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements a tree level if-conversion of loops. Its
22 initial goal is to help the vectorizer to vectorize loops with
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
91 #include "tree-pass.h"
94 #include "optabs-query.h"
95 #include "gimple-pretty-print.h"
97 #include "fold-const.h"
98 #include "stor-layout.h"
99 #include "gimple-fold.h"
100 #include "gimplify.h"
101 #include "gimple-iterator.h"
102 #include "gimplify-me.h"
103 #include "tree-cfg.h"
104 #include "tree-into-ssa.h"
105 #include "tree-ssa.h"
107 #include "tree-data-ref.h"
108 #include "tree-scalar-evolution.h"
109 #include "tree-ssa-loop.h"
110 #include "tree-ssa-loop-niter.h"
111 #include "tree-ssa-loop-ivopts.h"
112 #include "tree-ssa-address.h"
114 #include "tree-hash-traits.h"
116 #include "builtins.h"
119 #include "internal-fn.h"
120 #include "fold-const.h"
121 #include "tree-ssa-sccvn.h"
122 #include "tree-cfgcleanup.h"
123 #include "tree-ssa-dse.h"
125 /* Only handle PHIs with no more arguments unless we are asked to by
127 #define MAX_PHI_ARG_NUM \
128 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))
130 /* True if we've converted a statement that was only executed when some
131 condition C was true, and if for correctness we need to predicate the
132 statement to ensure that it is a no-op when C is false. See
133 predicate_statements for the kinds of predication we support. */
134 static bool need_to_predicate
;
136 /* Indicate if there are any complicated PHIs that need to be handled in
137 if-conversion. Complicated PHI has more than two arguments and can't
138 be degenerated to two arguments PHI. See more information in comment
139 before phi_convertible_by_degenerating_args. */
140 static bool any_complicated_phi
;
142 /* Hash for struct innermost_loop_behavior. It depends on the user to
145 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
147 static inline hashval_t
hash (const value_type
&);
148 static inline bool equal (const value_type
&,
149 const compare_type
&);
153 innermost_loop_behavior_hash::hash (const value_type
&e
)
157 hash
= iterative_hash_expr (e
->base_address
, 0);
158 hash
= iterative_hash_expr (e
->offset
, hash
);
159 hash
= iterative_hash_expr (e
->init
, hash
);
160 return iterative_hash_expr (e
->step
, hash
);
164 innermost_loop_behavior_hash::equal (const value_type
&e1
,
165 const compare_type
&e2
)
167 if ((e1
->base_address
&& !e2
->base_address
)
168 || (!e1
->base_address
&& e2
->base_address
)
169 || (!e1
->offset
&& e2
->offset
)
170 || (e1
->offset
&& !e2
->offset
)
171 || (!e1
->init
&& e2
->init
)
172 || (e1
->init
&& !e2
->init
)
173 || (!e1
->step
&& e2
->step
)
174 || (e1
->step
&& !e2
->step
))
177 if (e1
->base_address
&& e2
->base_address
178 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
180 if (e1
->offset
&& e2
->offset
181 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
183 if (e1
->init
&& e2
->init
184 && !operand_equal_p (e1
->init
, e2
->init
, 0))
186 if (e1
->step
&& e2
->step
187 && !operand_equal_p (e1
->step
, e2
->step
, 0))
193 /* List of basic blocks in if-conversion-suitable order. */
194 static basic_block
*ifc_bbs
;
196 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
197 static hash_map
<innermost_loop_behavior_hash
,
198 data_reference_p
> *innermost_DR_map
;
200 /* Hash table to store <base reference, DR> pairs. */
201 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
203 /* List of redundant SSA names: the first should be replaced by the second. */
204 static vec
< std::pair
<tree
, tree
> > redundant_ssa_names
;
206 /* Structure used to predicate basic blocks. This is attached to the
207 ->aux field of the BBs in the loop to be if-converted. */
208 struct bb_predicate
{
210 /* The condition under which this basic block is executed. */
213 /* PREDICATE is gimplified, and the sequence of statements is
214 recorded here, in order to avoid the duplication of computations
215 that occur in previous conditions. See PR44483. */
216 gimple_seq predicate_gimplified_stmts
;
219 /* Returns true when the basic block BB has a predicate. */
222 bb_has_predicate (basic_block bb
)
224 return bb
->aux
!= NULL
;
227 /* Returns the gimplified predicate for basic block BB. */
230 bb_predicate (basic_block bb
)
232 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
235 /* Sets the gimplified predicate COND for basic block BB. */
238 set_bb_predicate (basic_block bb
, tree cond
)
240 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
241 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
242 || is_gimple_condexpr (cond
));
243 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
246 /* Returns the sequence of statements of the gimplification of the
247 predicate for basic block BB. */
249 static inline gimple_seq
250 bb_predicate_gimplified_stmts (basic_block bb
)
252 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
255 /* Sets the sequence of statements STMTS of the gimplification of the
256 predicate for basic block BB. */
259 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
261 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
264 /* Adds the sequence of statements STMTS to the sequence of statements
265 of the predicate for basic block BB. */
268 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
270 /* We might have updated some stmts in STMTS via force_gimple_operand
271 calling fold_stmt and that producing multiple stmts. Delink immediate
272 uses so update_ssa after loop versioning doesn't get confused for
273 the not yet inserted predicates.
274 ??? This should go away once we reliably avoid updating stmts
276 for (gimple_stmt_iterator gsi
= gsi_start (stmts
);
277 !gsi_end_p (gsi
); gsi_next (&gsi
))
279 gimple
*stmt
= gsi_stmt (gsi
);
280 delink_stmt_imm_use (stmt
);
281 gimple_set_modified (stmt
, true);
283 gimple_seq_add_seq_without_update
284 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
287 /* Initializes to TRUE the predicate of basic block BB. */
290 init_bb_predicate (basic_block bb
)
292 bb
->aux
= XNEW (struct bb_predicate
);
293 set_bb_predicate_gimplified_stmts (bb
, NULL
);
294 set_bb_predicate (bb
, boolean_true_node
);
297 /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
300 release_bb_predicate (basic_block bb
)
302 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
305 /* Ensure that these stmts haven't yet been added to a bb. */
307 for (gimple_stmt_iterator i
= gsi_start (stmts
);
308 !gsi_end_p (i
); gsi_next (&i
))
309 gcc_assert (! gimple_bb (gsi_stmt (i
)));
312 gimple_seq_discard (stmts
);
313 set_bb_predicate_gimplified_stmts (bb
, NULL
);
317 /* Free the predicate of basic block BB. */
320 free_bb_predicate (basic_block bb
)
322 if (!bb_has_predicate (bb
))
325 release_bb_predicate (bb
);
330 /* Reinitialize predicate of BB with the true predicate. */
333 reset_bb_predicate (basic_block bb
)
335 if (!bb_has_predicate (bb
))
336 init_bb_predicate (bb
);
339 release_bb_predicate (bb
);
340 set_bb_predicate (bb
, boolean_true_node
);
344 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
345 the expression EXPR. Inserts the statement created for this
346 computation before GSI and leaves the iterator GSI at the same
350 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
352 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
353 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
354 gimple_set_vuse (stmt
, gimple_vuse (gsi_stmt (*gsi
)));
355 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
359 /* Return true when COND is a false predicate. */
362 is_false_predicate (tree cond
)
364 return (cond
!= NULL_TREE
365 && (cond
== boolean_false_node
366 || integer_zerop (cond
)));
369 /* Return true when COND is a true predicate. */
372 is_true_predicate (tree cond
)
374 return (cond
== NULL_TREE
375 || cond
== boolean_true_node
376 || integer_onep (cond
));
379 /* Returns true when BB has a predicate that is not trivial: true or
383 is_predicated (basic_block bb
)
385 return !is_true_predicate (bb_predicate (bb
));
388 /* Parses the predicate COND and returns its comparison code and
389 operands OP0 and OP1. */
391 static enum tree_code
392 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
396 if (TREE_CODE (cond
) == SSA_NAME
397 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
399 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
401 *op0
= gimple_assign_rhs1 (s
);
402 *op1
= gimple_assign_rhs2 (s
);
403 return gimple_assign_rhs_code (s
);
406 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
408 tree op
= gimple_assign_rhs1 (s
);
409 tree type
= TREE_TYPE (op
);
410 enum tree_code code
= parse_predicate (op
, op0
, op1
);
412 return code
== ERROR_MARK
? ERROR_MARK
413 : invert_tree_comparison (code
, HONOR_NANS (type
));
419 if (COMPARISON_CLASS_P (cond
))
421 *op0
= TREE_OPERAND (cond
, 0);
422 *op1
= TREE_OPERAND (cond
, 1);
423 return TREE_CODE (cond
);
429 /* Returns the fold of predicate C1 OR C2 at location LOC. */
432 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
434 tree op1a
, op1b
, op2a
, op2b
;
435 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
436 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
438 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
440 tree t
= maybe_fold_or_comparisons (boolean_type_node
, code1
, op1a
, op1b
,
446 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
449 /* Returns either a COND_EXPR or the folded expression if the folded
450 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
451 a constant or a SSA_NAME. */
454 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
456 tree rhs1
, lhs1
, cond_expr
;
458 /* If COND is comparison r != 0 and r has boolean type, convert COND
459 to SSA_NAME to accept by vect bool pattern. */
460 if (TREE_CODE (cond
) == NE_EXPR
)
462 tree op0
= TREE_OPERAND (cond
, 0);
463 tree op1
= TREE_OPERAND (cond
, 1);
464 if (TREE_CODE (op0
) == SSA_NAME
465 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
466 && (integer_zerop (op1
)))
469 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
, rhs
, lhs
);
471 if (cond_expr
== NULL_TREE
)
472 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
474 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
476 if (is_gimple_val (cond_expr
))
479 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
481 rhs1
= TREE_OPERAND (cond_expr
, 1);
482 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
483 if (is_gimple_val (rhs1
))
484 return build1 (ABS_EXPR
, type
, rhs1
);
487 if (TREE_CODE (cond_expr
) == MIN_EXPR
488 || TREE_CODE (cond_expr
) == MAX_EXPR
)
490 lhs1
= TREE_OPERAND (cond_expr
, 0);
491 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
492 rhs1
= TREE_OPERAND (cond_expr
, 1);
493 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
494 if (is_gimple_val (rhs1
) && is_gimple_val (lhs1
))
495 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
497 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
500 /* Add condition NC to the predicate list of basic block BB. LOOP is
501 the loop to be if-converted. Use predicate of cd-equivalent block
502 for join bb if it exists: we call basic blocks bb1 and bb2
503 cd-equivalent if they are executed under the same condition. */
506 add_to_predicate_list (class loop
*loop
, basic_block bb
, tree nc
)
511 if (is_true_predicate (nc
))
514 /* If dominance tells us this basic block is always executed,
515 don't record any predicates for it. */
516 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
519 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
520 /* We use notion of cd equivalence to get simpler predicate for
521 join block, e.g. if join block has 2 predecessors with predicates
522 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
523 p1 & p2 | p1 & !p2. */
524 if (dom_bb
!= loop
->header
525 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
527 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
528 bc
= bb_predicate (dom_bb
);
529 if (!is_true_predicate (bc
))
530 set_bb_predicate (bb
, bc
);
532 gcc_assert (is_true_predicate (bb_predicate (bb
)));
533 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
534 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
535 dom_bb
->index
, bb
->index
);
539 if (!is_predicated (bb
))
543 bc
= bb_predicate (bb
);
544 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
545 if (is_true_predicate (bc
))
547 reset_bb_predicate (bb
);
552 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
553 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
554 tp
= &TREE_OPERAND (bc
, 0);
557 if (!is_gimple_condexpr (*tp
))
560 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
561 add_bb_predicate_gimplified_stmts (bb
, stmts
);
563 set_bb_predicate (bb
, bc
);
566 /* Add the condition COND to the previous condition PREV_COND, and add
567 this to the predicate list of the destination of edge E. LOOP is
568 the loop to be if-converted. */
571 add_to_dst_predicate_list (class loop
*loop
, edge e
,
572 tree prev_cond
, tree cond
)
574 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
577 if (!is_true_predicate (prev_cond
))
578 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
581 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
582 add_to_predicate_list (loop
, e
->dest
, cond
);
585 /* Return true if one of the successor edges of BB exits LOOP. */
588 bb_with_exit_edge_p (class loop
*loop
, basic_block bb
)
593 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
594 if (loop_exit_edge_p (loop
, e
))
600 /* Given PHI which has more than two arguments, this function checks if
601 it's if-convertible by degenerating its arguments. Specifically, if
602 below two conditions are satisfied:
604 1) Number of PHI arguments with different values equals to 2 and one
605 argument has the only occurrence.
606 2) The edge corresponding to the unique argument isn't critical edge.
608 Such PHI can be handled as PHIs have only two arguments. For example,
611 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
613 can be transformed into:
615 res = (predicate of e3) ? A_2 : A_1;
617 Return TRUE if it is the case, FALSE otherwise. */
620 phi_convertible_by_degenerating_args (gphi
*phi
)
623 tree arg
, t1
= NULL
, t2
= NULL
;
624 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
625 unsigned int num_args
= gimple_phi_num_args (phi
);
627 gcc_assert (num_args
> 2);
629 for (i
= 0; i
< num_args
; i
++)
631 arg
= gimple_phi_arg_def (phi
, i
);
632 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
638 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
648 if (n1
!= 1 && n2
!= 1)
651 /* Check if the edge corresponding to the unique arg is critical. */
652 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
653 if (EDGE_COUNT (e
->src
->succs
) > 1)
659 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
660 and it belongs to basic block BB. Note at this point, it is sure
661 that PHI is if-convertible. This function updates global variable
662 ANY_COMPLICATED_PHI if PHI is complicated. */
665 if_convertible_phi_p (class loop
*loop
, basic_block bb
, gphi
*phi
)
667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
669 fprintf (dump_file
, "-------------------------\n");
670 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
673 if (bb
!= loop
->header
674 && gimple_phi_num_args (phi
) > 2
675 && !phi_convertible_by_degenerating_args (phi
))
676 any_complicated_phi
= true;
681 /* Records the status of a data reference. This struct is attached to
682 each DR->aux field. */
685 bool rw_unconditionally
;
686 bool w_unconditionally
;
687 bool written_at_least_once
;
691 tree base_w_predicate
;
694 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
695 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
696 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
697 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
699 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
700 HASH tables. While storing them in HASH table, it checks if the
701 reference is unconditionally read or written and stores that as a flag
702 information. For base reference it checks if it is written atlest once
703 unconditionally and stores it as flag information along with DR.
704 In other words for every data reference A in STMT there exist other
705 accesses to a data reference with the same base with predicates that
706 add up (OR-up) to the true predicate: this ensures that the data
707 reference A is touched (read or written) on every iteration of the
708 if-converted loop. */
710 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
713 data_reference_p
*master_dr
, *base_master_dr
;
714 tree base_ref
= DR_BASE_OBJECT (a
);
715 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
716 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
719 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
725 IFC_DR (*master_dr
)->w_predicate
726 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
727 IFC_DR (*master_dr
)->w_predicate
);
728 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
729 DR_W_UNCONDITIONALLY (*master_dr
) = true;
731 IFC_DR (*master_dr
)->rw_predicate
732 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
733 IFC_DR (*master_dr
)->rw_predicate
);
734 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
735 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
739 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
742 IFC_DR (*base_master_dr
)->base_w_predicate
743 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
744 IFC_DR (*base_master_dr
)->base_w_predicate
);
745 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
746 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
750 /* Return TRUE if can prove the index IDX of an array reference REF is
751 within array bound. Return false otherwise. */
754 idx_within_array_bound (tree ref
, tree
*idx
, void *dta
)
756 wi::overflow_type overflow
;
757 widest_int niter
, valid_niter
, delta
, wi_step
;
760 class loop
*loop
= (class loop
*) dta
;
762 /* Only support within-bound access for array references. */
763 if (TREE_CODE (ref
) != ARRAY_REF
)
766 /* For arrays at the end of the structure, we are not guaranteed that they
767 do not really extend over their declared size. However, for arrays of
768 size greater than one, this is unlikely to be intended. */
769 if (array_at_struct_end_p (ref
))
772 ev
= analyze_scalar_evolution (loop
, *idx
);
773 ev
= instantiate_parameters (loop
, ev
);
774 init
= initial_condition (ev
);
775 step
= evolution_part_in_loop_num (ev
, loop
->num
);
777 if (!init
|| TREE_CODE (init
) != INTEGER_CST
778 || (step
&& TREE_CODE (step
) != INTEGER_CST
))
781 low
= array_ref_low_bound (ref
);
782 high
= array_ref_up_bound (ref
);
784 /* The case of nonconstant bounds could be handled, but it would be
786 if (TREE_CODE (low
) != INTEGER_CST
787 || !high
|| TREE_CODE (high
) != INTEGER_CST
)
790 /* Check if the intial idx is within bound. */
791 if (wi::to_widest (init
) < wi::to_widest (low
)
792 || wi::to_widest (init
) > wi::to_widest (high
))
795 /* The idx is always within bound. */
796 if (!step
|| integer_zerop (step
))
799 if (!max_loop_iterations (loop
, &niter
))
802 if (wi::to_widest (step
) < 0)
804 delta
= wi::to_widest (init
) - wi::to_widest (low
);
805 wi_step
= -wi::to_widest (step
);
809 delta
= wi::to_widest (high
) - wi::to_widest (init
);
810 wi_step
= wi::to_widest (step
);
813 valid_niter
= wi::div_floor (delta
, wi_step
, SIGNED
, &overflow
);
814 /* The iteration space of idx is within array bound. */
815 if (!overflow
&& niter
<= valid_niter
)
821 /* Return TRUE if ref is a within bound array reference. */
824 ref_within_array_bound (gimple
*stmt
, tree ref
)
826 class loop
*loop
= loop_containing_stmt (stmt
);
828 gcc_assert (loop
!= NULL
);
829 return for_each_index (&ref
, idx_within_array_bound
, loop
);
833 /* Given a memory reference expression T, return TRUE if base object
834 it refers to is writable. The base object of a memory reference
835 is the main object being referenced, which is returned by function
839 base_object_writable (tree ref
)
841 tree base_tree
= get_base_address (ref
);
844 && DECL_P (base_tree
)
845 && decl_binds_to_current_def_p (base_tree
)
846 && !TREE_READONLY (base_tree
));
849 /* Return true when the memory references of STMT won't trap in the
850 if-converted code. There are two things that we have to check for:
852 - writes to memory occur to writable memory: if-conversion of
853 memory writes transforms the conditional memory writes into
854 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
855 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
856 be executed at all in the original code, it may be a readonly
857 memory. To check that A is not const-qualified, we check that
858 there exists at least an unconditional write to A in the current
861 - reads or writes to memory are valid memory accesses for every
862 iteration. To check that the memory accesses are correctly formed
863 and that we are allowed to read and write in these locations, we
864 check that the memory accesses to be if-converted occur at every
865 iteration unconditionally.
867 Returns true for the memory reference in STMT, same memory reference
868 is read or written unconditionally atleast once and the base memory
869 reference is written unconditionally once. This is to check reference
870 will not write fault. Also retuns true if the memory reference is
871 unconditionally read once then we are conditionally writing to memory
872 which is defined as read and write and is bound to the definition
875 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
877 /* If DR didn't see a reference here we can't use it to tell
878 whether the ref traps or not. */
879 if (gimple_uid (stmt
) == 0)
882 data_reference_p
*master_dr
, *base_master_dr
;
883 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
885 tree base
= DR_BASE_OBJECT (a
);
886 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
888 gcc_assert (DR_STMT (a
) == stmt
);
889 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
890 || DR_INIT (a
) || DR_STEP (a
));
892 master_dr
= innermost_DR_map
->get (innermost
);
893 gcc_assert (master_dr
!= NULL
);
895 base_master_dr
= baseref_DR_map
->get (base
);
897 /* If a is unconditionally written to it doesn't trap. */
898 if (DR_W_UNCONDITIONALLY (*master_dr
))
901 /* If a is unconditionally accessed then ...
903 Even a is conditional access, we can treat it as an unconditional
904 one if it's an array reference and all its index are within array
906 if (DR_RW_UNCONDITIONALLY (*master_dr
)
907 || ref_within_array_bound (stmt
, DR_REF (a
)))
909 /* an unconditional read won't trap. */
913 /* an unconditionaly write won't trap if the base is written
914 to unconditionally. */
916 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
917 return flag_store_data_races
;
918 /* or the base is known to be not readonly. */
919 else if (base_object_writable (DR_REF (a
)))
920 return flag_store_data_races
;
926 /* Return true if STMT could be converted into a masked load or store
927 (conditional load or store based on a mask computed from bb predicate). */
930 ifcvt_can_use_mask_load_store (gimple
*stmt
)
932 /* Check whether this is a load or store. */
933 tree lhs
= gimple_assign_lhs (stmt
);
936 if (gimple_store_p (stmt
))
938 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
943 else if (gimple_assign_load_p (stmt
))
946 ref
= gimple_assign_rhs1 (stmt
);
951 if (may_be_nonaddressable_p (ref
))
954 /* Mask should be integer mode of the same size as the load/store
956 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
957 if (!int_mode_for_mode (mode
).exists () || VECTOR_MODE_P (mode
))
960 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
966 /* Return true if STMT could be converted from an operation that is
967 unconditional to one that is conditional on a bb predicate mask. */
970 ifcvt_can_predicate (gimple
*stmt
)
972 basic_block bb
= gimple_bb (stmt
);
974 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
975 || bb
->loop_father
->dont_vectorize
976 || gimple_has_volatile_ops (stmt
))
979 if (gimple_assign_single_p (stmt
))
980 return ifcvt_can_use_mask_load_store (stmt
);
982 tree_code code
= gimple_assign_rhs_code (stmt
);
983 tree lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
984 tree rhs_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
985 if (!types_compatible_p (lhs_type
, rhs_type
))
987 internal_fn cond_fn
= get_conditional_internal_fn (code
);
988 return (cond_fn
!= IFN_LAST
989 && vectorized_internal_fn_supported_p (cond_fn
, lhs_type
));
992 /* Return true when STMT is if-convertible.
994 GIMPLE_ASSIGN statement is not if-convertible if,
997 - LHS is not var decl. */
1000 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
1001 vec
<data_reference_p
> refs
)
1003 tree lhs
= gimple_assign_lhs (stmt
);
1005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1007 fprintf (dump_file
, "-------------------------\n");
1008 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1011 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
1014 /* Some of these constrains might be too conservative. */
1015 if (stmt_ends_bb_p (stmt
)
1016 || gimple_has_volatile_ops (stmt
)
1017 || (TREE_CODE (lhs
) == SSA_NAME
1018 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1019 || gimple_has_side_effects (stmt
))
1021 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1022 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
1026 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
1027 in between if_convertible_loop_p and combine_blocks
1028 we can perform loop versioning. */
1029 gimple_set_plf (stmt
, GF_PLF_2
, false);
1031 if ((! gimple_vuse (stmt
)
1032 || gimple_could_trap_p_1 (stmt
, false, false)
1033 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
1034 && gimple_could_trap_p (stmt
))
1036 if (ifcvt_can_predicate (stmt
))
1038 gimple_set_plf (stmt
, GF_PLF_2
, true);
1039 need_to_predicate
= true;
1042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1043 fprintf (dump_file
, "tree could trap...\n");
1047 /* When if-converting stores force versioning, likewise if we
1048 ended up generating store data races. */
1049 if (gimple_vdef (stmt
))
1050 need_to_predicate
= true;
1055 /* Return true when STMT is if-convertible.
1057 A statement is if-convertible if:
1058 - it is an if-convertible GIMPLE_ASSIGN,
1059 - it is a GIMPLE_LABEL or a GIMPLE_COND,
1060 - it is builtins call. */
1063 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
1065 switch (gimple_code (stmt
))
1073 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
1077 tree fndecl
= gimple_call_fndecl (stmt
);
1080 int flags
= gimple_call_flags (stmt
);
1081 if ((flags
& ECF_CONST
)
1082 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
1083 /* We can only vectorize some builtins at the moment,
1084 so restrict if-conversion to those. */
1085 && fndecl_built_in_p (fndecl
))
1092 /* Don't know what to do with 'em so don't do anything. */
1093 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1095 fprintf (dump_file
, "don't know what to do\n");
1096 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1104 /* Assumes that BB has more than 1 predecessors.
1105 Returns false if at least one successor is not on critical edge
1106 and true otherwise. */
1109 all_preds_critical_p (basic_block bb
)
1114 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1115 if (EDGE_COUNT (e
->src
->succs
) == 1)
1120 /* Return true when BB is if-convertible. This routine does not check
1121 basic block's statements and phis.
1123 A basic block is not if-convertible if:
1124 - it is non-empty and it is after the exit block (in BFS order),
1125 - it is after the exit block but before the latch,
1126 - its edges are not normal.
1128 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1132 if_convertible_bb_p (class loop
*loop
, basic_block bb
, basic_block exit_bb
)
1137 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1138 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1140 if (EDGE_COUNT (bb
->succs
) > 2)
1145 if (bb
!= loop
->latch
)
1147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1148 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1151 else if (!empty_block_p (bb
))
1153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1154 fprintf (dump_file
, "non empty basic block after exit bb\n");
1157 else if (bb
== loop
->latch
1159 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1162 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1167 /* Be less adventurous and handle only normal edges. */
1168 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1169 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1171 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1172 fprintf (dump_file
, "Difficult to handle edges\n");
1179 /* Return true when all predecessor blocks of BB are visited. The
1180 VISITED bitmap keeps track of the visited blocks. */
1183 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1187 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1188 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1194 /* Get body of a LOOP in suitable order for if-conversion. It is
1195 caller's responsibility to deallocate basic block list.
1196 If-conversion suitable order is, breadth first sort (BFS) order
1197 with an additional constraint: select a block only if all its
1198 predecessors are already selected. */
1200 static basic_block
*
1201 get_loop_body_in_if_conv_order (const class loop
*loop
)
1203 basic_block
*blocks
, *blocks_in_bfs_order
;
1206 unsigned int index
= 0;
1207 unsigned int visited_count
= 0;
1209 gcc_assert (loop
->num_nodes
);
1210 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1212 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1213 visited
= BITMAP_ALLOC (NULL
);
1215 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1218 while (index
< loop
->num_nodes
)
1220 bb
= blocks_in_bfs_order
[index
];
1222 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1224 free (blocks_in_bfs_order
);
1225 BITMAP_FREE (visited
);
1230 if (!bitmap_bit_p (visited
, bb
->index
))
1232 if (pred_blocks_visited_p (bb
, &visited
)
1233 || bb
== loop
->header
)
1235 /* This block is now visited. */
1236 bitmap_set_bit (visited
, bb
->index
);
1237 blocks
[visited_count
++] = bb
;
1243 if (index
== loop
->num_nodes
1244 && visited_count
!= loop
->num_nodes
)
1248 free (blocks_in_bfs_order
);
1249 BITMAP_FREE (visited
);
1253 /* Returns true when the analysis of the predicates for all the basic
1254 blocks in LOOP succeeded.
1256 predicate_bbs first allocates the predicates of the basic blocks.
1257 These fields are then initialized with the tree expressions
1258 representing the predicates under which a basic block is executed
1259 in the LOOP. As the loop->header is executed at each iteration, it
1260 has the "true" predicate. Other statements executed under a
1261 condition are predicated with that condition, for example
1268 S1 will be predicated with "x", and
1269 S2 will be predicated with "!x". */
1272 predicate_bbs (loop_p loop
)
1276 for (i
= 0; i
< loop
->num_nodes
; i
++)
1277 init_bb_predicate (ifc_bbs
[i
]);
1279 for (i
= 0; i
< loop
->num_nodes
; i
++)
1281 basic_block bb
= ifc_bbs
[i
];
1285 /* The loop latch and loop exit block are always executed and
1286 have no extra conditions to be processed: skip them. */
1287 if (bb
== loop
->latch
1288 || bb_with_exit_edge_p (loop
, bb
))
1290 reset_bb_predicate (bb
);
1294 cond
= bb_predicate (bb
);
1295 stmt
= last_stmt (bb
);
1296 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1299 edge true_edge
, false_edge
;
1300 location_t loc
= gimple_location (stmt
);
1301 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1303 gimple_cond_lhs (stmt
),
1304 gimple_cond_rhs (stmt
));
1306 /* Add new condition into destination's predicate list. */
1307 extract_true_false_edges_from_block (gimple_bb (stmt
),
1308 &true_edge
, &false_edge
);
1310 /* If C is true, then TRUE_EDGE is taken. */
1311 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1314 /* If C is false, then FALSE_EDGE is taken. */
1315 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1317 add_to_dst_predicate_list (loop
, false_edge
,
1318 unshare_expr (cond
), c2
);
1323 /* If current bb has only one successor, then consider it as an
1324 unconditional goto. */
1325 if (single_succ_p (bb
))
1327 basic_block bb_n
= single_succ (bb
);
1329 /* The successor bb inherits the predicate of its
1330 predecessor. If there is no predicate in the predecessor
1331 bb, then consider the successor bb as always executed. */
1332 if (cond
== NULL_TREE
)
1333 cond
= boolean_true_node
;
1335 add_to_predicate_list (loop
, bb_n
, cond
);
1339 /* The loop header is always executed. */
1340 reset_bb_predicate (loop
->header
);
1341 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1342 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1345 /* Build region by adding loop pre-header and post-header blocks. */
1347 static vec
<basic_block
>
1348 build_region (class loop
*loop
)
1350 vec
<basic_block
> region
= vNULL
;
1351 basic_block exit_bb
= NULL
;
1353 gcc_assert (ifc_bbs
);
1354 /* The first element is loop pre-header. */
1355 region
.safe_push (loop_preheader_edge (loop
)->src
);
1357 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
1359 basic_block bb
= ifc_bbs
[i
];
1360 region
.safe_push (bb
);
1361 /* Find loop postheader. */
1364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1365 if (loop_exit_edge_p (loop
, e
))
1371 /* The last element is loop post-header. */
1372 gcc_assert (exit_bb
);
1373 region
.safe_push (exit_bb
);
1377 /* Return true when LOOP is if-convertible. This is a helper function
1378 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1379 in if_convertible_loop_p. */
1382 if_convertible_loop_p_1 (class loop
*loop
, vec
<data_reference_p
> *refs
)
1385 basic_block exit_bb
= NULL
;
1386 vec
<basic_block
> region
;
1388 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1391 calculate_dominance_info (CDI_DOMINATORS
);
1393 /* Allow statements that can be handled during if-conversion. */
1394 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1398 fprintf (dump_file
, "Irreducible loop\n");
1402 for (i
= 0; i
< loop
->num_nodes
; i
++)
1404 basic_block bb
= ifc_bbs
[i
];
1406 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1409 if (bb_with_exit_edge_p (loop
, bb
))
1413 for (i
= 0; i
< loop
->num_nodes
; i
++)
1415 basic_block bb
= ifc_bbs
[i
];
1416 gimple_stmt_iterator gsi
;
1418 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1419 switch (gimple_code (gsi_stmt (gsi
)))
1426 gimple_set_uid (gsi_stmt (gsi
), 0);
1433 data_reference_p dr
;
1436 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1437 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1439 /* Compute post-dominator tree locally. */
1440 region
= build_region (loop
);
1441 calculate_dominance_info_for_region (CDI_POST_DOMINATORS
, region
);
1443 predicate_bbs (loop
);
1445 /* Free post-dominator tree since it is not used after predication. */
1446 free_dominance_info_for_region (cfun
, CDI_POST_DOMINATORS
, region
);
1449 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1451 tree ref
= DR_REF (dr
);
1453 dr
->aux
= XNEW (struct ifc_dr
);
1454 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1455 DR_RW_UNCONDITIONALLY (dr
) = false;
1456 DR_W_UNCONDITIONALLY (dr
) = false;
1457 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1458 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1459 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1460 if (gimple_uid (DR_STMT (dr
)) == 0)
1461 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1463 /* If DR doesn't have innermost loop behavior or it's a compound
1464 memory reference, we synthesize its innermost loop behavior
1466 if (TREE_CODE (ref
) == COMPONENT_REF
1467 || TREE_CODE (ref
) == IMAGPART_EXPR
1468 || TREE_CODE (ref
) == REALPART_EXPR
1469 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1470 || DR_INIT (dr
) || DR_STEP (dr
)))
1472 while (TREE_CODE (ref
) == COMPONENT_REF
1473 || TREE_CODE (ref
) == IMAGPART_EXPR
1474 || TREE_CODE (ref
) == REALPART_EXPR
)
1475 ref
= TREE_OPERAND (ref
, 0);
1477 memset (&DR_INNERMOST (dr
), 0, sizeof (DR_INNERMOST (dr
)));
1478 DR_BASE_ADDRESS (dr
) = ref
;
1480 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1483 for (i
= 0; i
< loop
->num_nodes
; i
++)
1485 basic_block bb
= ifc_bbs
[i
];
1486 gimple_stmt_iterator itr
;
1488 /* Check the if-convertibility of statements in predicated BBs. */
1489 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1490 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1491 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1495 /* Checking PHIs needs to be done after stmts, as the fact whether there
1496 are any masked loads or stores affects the tests. */
1497 for (i
= 0; i
< loop
->num_nodes
; i
++)
1499 basic_block bb
= ifc_bbs
[i
];
1502 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1503 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1508 fprintf (dump_file
, "Applying if-conversion\n");
1513 /* Return true when LOOP is if-convertible.
1514 LOOP is if-convertible if:
1516 - it has two or more basic blocks,
1517 - it has only one exit,
1518 - loop header is not the exit edge,
1519 - if its basic blocks and phi nodes are if convertible. */
1522 if_convertible_loop_p (class loop
*loop
)
1527 vec
<data_reference_p
> refs
;
1529 /* Handle only innermost loop. */
1530 if (!loop
|| loop
->inner
)
1532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1533 fprintf (dump_file
, "not innermost loop\n");
1537 /* If only one block, no need for if-conversion. */
1538 if (loop
->num_nodes
<= 2)
1540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1541 fprintf (dump_file
, "less than 2 basic blocks\n");
1545 /* More than one loop exit is too much to handle. */
1546 if (!single_exit (loop
))
1548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1549 fprintf (dump_file
, "multiple exits\n");
1553 /* If one of the loop header's edge is an exit edge then do not
1554 apply if-conversion. */
1555 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1556 if (loop_exit_edge_p (loop
, e
))
1560 res
= if_convertible_loop_p_1 (loop
, &refs
);
1562 data_reference_p dr
;
1564 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1567 free_data_refs (refs
);
1569 delete innermost_DR_map
;
1570 innermost_DR_map
= NULL
;
1572 delete baseref_DR_map
;
1573 baseref_DR_map
= NULL
;
1578 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1579 which is in predicated basic block.
1580 In fact, the following PHI pattern is searching:
1582 reduc_1 = PHI <..., reduc_2>
1586 reduc_2 = PHI <reduc_1, reduc_3>
1588 ARG_0 and ARG_1 are correspondent PHI arguments.
1589 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1590 EXTENDED is true if PHI has > 2 arguments. */
1593 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1594 tree
*op0
, tree
*op1
, bool extended
)
1596 tree lhs
, r_op1
, r_op2
;
1598 gimple
*header_phi
= NULL
;
1599 enum tree_code reduction_op
;
1600 basic_block bb
= gimple_bb (phi
);
1601 class loop
*loop
= bb
->loop_father
;
1602 edge latch_e
= loop_latch_edge (loop
);
1603 imm_use_iterator imm_iter
;
1604 use_operand_p use_p
;
1607 bool result
= false;
1608 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1611 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1614 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1615 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1617 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1620 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1621 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1625 if (gimple_bb (header_phi
) != loop
->header
)
1628 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1631 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1632 || gimple_has_volatile_ops (stmt
))
1635 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1638 if (!is_predicated (gimple_bb (stmt
)))
1641 /* Check that stmt-block is predecessor of phi-block. */
1642 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1651 if (!has_single_use (lhs
))
1654 reduction_op
= gimple_assign_rhs_code (stmt
);
1655 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1657 r_op1
= gimple_assign_rhs1 (stmt
);
1658 r_op2
= gimple_assign_rhs2 (stmt
);
1660 /* Make R_OP1 to hold reduction variable. */
1661 if (r_op2
== PHI_RESULT (header_phi
)
1662 && reduction_op
== PLUS_EXPR
)
1663 std::swap (r_op1
, r_op2
);
1664 else if (r_op1
!= PHI_RESULT (header_phi
))
1667 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1668 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1670 gimple
*use_stmt
= USE_STMT (use_p
);
1671 if (is_gimple_debug (use_stmt
))
1673 if (use_stmt
== stmt
)
1675 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1679 *op0
= r_op1
; *op1
= r_op2
;
1684 /* Converts conditional scalar reduction into unconditional form, e.g.
1686 if (_5 != 0) goto bb_5 else goto bb_6
1692 # res_2 = PHI <res_13(4), res_6(5)>
1695 will be converted into sequence
1696 _ifc__1 = _5 != 0 ? 1 : 0;
1697 res_2 = res_13 + _ifc__1;
1698 Argument SWAP tells that arguments of conditional expression should be
1700 Returns rhs of resulting PHI assignment. */
1703 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1704 tree cond
, tree op0
, tree op1
, bool swap
)
1706 gimple_stmt_iterator stmt_it
;
1709 tree rhs1
= gimple_assign_rhs1 (reduc
);
1710 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1712 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1716 fprintf (dump_file
, "Found cond scalar reduction.\n");
1717 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1720 /* Build cond expression using COND and constant operand
1721 of reduction rhs. */
1722 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1723 unshare_expr (cond
),
1727 /* Create assignment stmt and insert it at GSI. */
1728 new_assign
= gimple_build_assign (tmp
, c
);
1729 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1730 /* Build rhs for unconditional increment/decrement. */
1731 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1732 TREE_TYPE (rhs1
), op0
, tmp
);
1734 /* Delete original reduction stmt. */
1735 stmt_it
= gsi_for_stmt (reduc
);
1736 gsi_remove (&stmt_it
, true);
1737 release_defs (reduc
);
1741 /* Produce condition for all occurrences of ARG in PHI node. */
1744 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1745 gimple_stmt_iterator
*gsi
)
1749 tree cond
= NULL_TREE
;
1753 len
= occur
->length ();
1754 gcc_assert (len
> 0);
1755 for (i
= 0; i
< len
; i
++)
1757 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1758 c
= bb_predicate (e
->src
);
1759 if (is_true_predicate (c
))
1764 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1765 is_gimple_condexpr
, NULL_TREE
,
1766 true, GSI_SAME_STMT
);
1767 if (cond
!= NULL_TREE
)
1769 /* Must build OR expression. */
1770 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1771 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1772 is_gimple_condexpr
, NULL_TREE
,
1773 true, GSI_SAME_STMT
);
1778 gcc_assert (cond
!= NULL_TREE
);
1782 /* Local valueization callback that follows all-use SSA edges. */
1785 ifcvt_follow_ssa_use_edges (tree val
)
1790 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1791 This routine can handle PHI nodes with more than two arguments.
1794 S1: A = PHI <x1(1), x2(5)>
1796 S2: A = cond ? x1 : x2;
1798 The generated code is inserted at GSI that points to the top of
1799 basic block's statement list.
1800 If PHI node has more than two arguments a chain of conditional
1801 expression is produced. */
1805 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1807 gimple
*new_stmt
= NULL
, *reduc
;
1808 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1810 unsigned int index0
;
1811 unsigned int max
, args_len
;
1816 res
= gimple_phi_result (phi
);
1817 if (virtual_operand_p (res
))
1820 if ((rhs
= degenerate_phi_result (phi
))
1821 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1823 && !chrec_contains_undetermined (scev
)
1825 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1829 fprintf (dump_file
, "Degenerate phi!\n");
1830 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1832 new_stmt
= gimple_build_assign (res
, rhs
);
1833 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1834 update_stmt (new_stmt
);
1838 bb
= gimple_bb (phi
);
1839 if (EDGE_COUNT (bb
->preds
) == 2)
1841 /* Predicate ordinary PHI node with 2 arguments. */
1842 edge first_edge
, second_edge
;
1843 basic_block true_bb
;
1844 first_edge
= EDGE_PRED (bb
, 0);
1845 second_edge
= EDGE_PRED (bb
, 1);
1846 cond
= bb_predicate (first_edge
->src
);
1847 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1848 std::swap (first_edge
, second_edge
);
1849 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1851 cond
= bb_predicate (second_edge
->src
);
1852 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1853 cond
= TREE_OPERAND (cond
, 0);
1855 first_edge
= second_edge
;
1858 cond
= bb_predicate (first_edge
->src
);
1859 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1860 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1861 is_gimple_condexpr
, NULL_TREE
,
1862 true, GSI_SAME_STMT
);
1863 true_bb
= first_edge
->src
;
1864 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1866 arg0
= gimple_phi_arg_def (phi
, 1);
1867 arg1
= gimple_phi_arg_def (phi
, 0);
1871 arg0
= gimple_phi_arg_def (phi
, 0);
1872 arg1
= gimple_phi_arg_def (phi
, 1);
1874 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1876 /* Convert reduction stmt into vectorizable form. */
1877 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1878 true_bb
!= gimple_bb (reduc
));
1880 /* Build new RHS using selected condition and arguments. */
1881 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1883 new_stmt
= gimple_build_assign (res
, rhs
);
1884 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1885 gimple_stmt_iterator new_gsi
= gsi_for_stmt (new_stmt
);
1886 if (fold_stmt (&new_gsi
, ifcvt_follow_ssa_use_edges
))
1888 new_stmt
= gsi_stmt (new_gsi
);
1889 update_stmt (new_stmt
);
1892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1894 fprintf (dump_file
, "new phi replacement stmt\n");
1895 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1900 /* Create hashmap for PHI node which contain vector of argument indexes
1901 having the same value. */
1903 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1904 unsigned int num_args
= gimple_phi_num_args (phi
);
1906 /* Vector of different PHI argument values. */
1907 auto_vec
<tree
> args (num_args
);
1909 /* Compute phi_arg_map. */
1910 for (i
= 0; i
< num_args
; i
++)
1914 arg
= gimple_phi_arg_def (phi
, i
);
1915 if (!phi_arg_map
.get (arg
))
1916 args
.quick_push (arg
);
1917 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1920 /* Determine element with max number of occurrences. */
1923 args_len
= args
.length ();
1924 for (i
= 0; i
< args_len
; i
++)
1927 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1934 /* Put element with max number of occurences to the end of ARGS. */
1935 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1936 std::swap (args
[args_len
- 1], args
[max_ind
]);
1938 /* Handle one special case when number of arguments with different values
1939 is equal 2 and one argument has the only occurrence. Such PHI can be
1940 handled as if would have only 2 arguments. */
1941 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1944 indexes
= phi_arg_map
.get (args
[0]);
1945 index0
= (*indexes
)[0];
1948 e
= gimple_phi_arg_edge (phi
, index0
);
1949 cond
= bb_predicate (e
->src
);
1950 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1953 cond
= TREE_OPERAND (cond
, 0);
1955 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1956 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1957 is_gimple_condexpr
, NULL_TREE
,
1958 true, GSI_SAME_STMT
);
1959 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1961 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1965 /* Convert reduction stmt into vectorizable form. */
1966 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1968 new_stmt
= gimple_build_assign (res
, rhs
);
1969 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1970 update_stmt (new_stmt
);
1976 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1979 for (i
= 0; i
< args_len
; i
++)
1982 indexes
= phi_arg_map
.get (args
[i
]);
1983 if (i
!= args_len
- 1)
1984 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1987 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1988 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1990 new_stmt
= gimple_build_assign (lhs
, rhs
);
1991 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1992 update_stmt (new_stmt
);
1997 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1999 fprintf (dump_file
, "new extended phi replacement stmt\n");
2000 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
2004 /* Replaces in LOOP all the scalar phi nodes other than those in the
2005 LOOP->header block with conditional modify expressions. */
2008 predicate_all_scalar_phis (class loop
*loop
)
2011 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2014 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2017 gimple_stmt_iterator gsi
;
2018 gphi_iterator phi_gsi
;
2021 if (bb
== loop
->header
)
2024 phi_gsi
= gsi_start_phis (bb
);
2025 if (gsi_end_p (phi_gsi
))
2028 gsi
= gsi_after_labels (bb
);
2029 while (!gsi_end_p (phi_gsi
))
2031 phi
= phi_gsi
.phi ();
2032 if (virtual_operand_p (gimple_phi_result (phi
)))
2033 gsi_next (&phi_gsi
);
2036 predicate_scalar_phi (phi
, &gsi
);
2037 remove_phi_node (&phi_gsi
, false);
2043 /* Insert in each basic block of LOOP the statements produced by the
2044 gimplification of the predicates. */
2047 insert_gimplified_predicates (loop_p loop
)
2051 for (i
= 0; i
< loop
->num_nodes
; i
++)
2053 basic_block bb
= ifc_bbs
[i
];
2055 if (!is_predicated (bb
))
2056 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
2057 if (!is_predicated (bb
))
2059 /* Do not insert statements for a basic block that is not
2060 predicated. Also make sure that the predicate of the
2061 basic block is set to true. */
2062 reset_bb_predicate (bb
);
2066 stmts
= bb_predicate_gimplified_stmts (bb
);
2069 if (need_to_predicate
)
2071 /* Insert the predicate of the BB just after the label,
2072 as the if-conversion of memory writes will use this
2074 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2075 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2079 /* Insert the predicate of the BB at the end of the BB
2080 as this would reduce the register pressure: the only
2081 use of this predicate will be in successor BBs. */
2082 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2085 || stmt_ends_bb_p (gsi_stmt (gsi
)))
2086 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2088 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
2091 /* Once the sequence is code generated, set it to NULL. */
2092 set_bb_predicate_gimplified_stmts (bb
, NULL
);
2097 /* Helper function for predicate_statements. Returns index of existent
2098 mask if it was created for given SIZE and -1 otherwise. */
2101 mask_exists (int size
, vec
<int> vec
)
2105 FOR_EACH_VEC_ELT (vec
, ix
, v
)
2111 /* Helper function for predicate_statements. STMT is a memory read or
2112 write and it needs to be predicated by MASK. Return a statement
2116 predicate_load_or_store (gimple_stmt_iterator
*gsi
, gassign
*stmt
, tree mask
)
2120 tree lhs
= gimple_assign_lhs (stmt
);
2121 tree rhs
= gimple_assign_rhs1 (stmt
);
2122 tree ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2123 mark_addressable (ref
);
2124 tree addr
= force_gimple_operand_gsi (gsi
, build_fold_addr_expr (ref
),
2125 true, NULL_TREE
, true, GSI_SAME_STMT
);
2126 tree ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2127 get_object_alignment (ref
));
2128 /* Copy points-to info if possible. */
2129 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2130 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2132 if (TREE_CODE (lhs
) == SSA_NAME
)
2135 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2137 gimple_call_set_lhs (new_stmt
, lhs
);
2138 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2143 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2145 gimple_move_vops (new_stmt
, stmt
);
2147 gimple_call_set_nothrow (new_stmt
, true);
2151 /* STMT uses OP_LHS. Check whether it is equivalent to:
2153 ... = OP_MASK ? OP_LHS : X;
2155 Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2156 known to have value OP_COND. */
2159 check_redundant_cond_expr (gimple
*stmt
, tree op_mask
, tree op_cond
,
2162 gassign
*assign
= dyn_cast
<gassign
*> (stmt
);
2163 if (!assign
|| gimple_assign_rhs_code (assign
) != COND_EXPR
)
2166 tree use_cond
= gimple_assign_rhs1 (assign
);
2167 tree if_true
= gimple_assign_rhs2 (assign
);
2168 tree if_false
= gimple_assign_rhs3 (assign
);
2170 if ((use_cond
== op_mask
|| operand_equal_p (use_cond
, op_cond
, 0))
2171 && if_true
== op_lhs
)
2174 if (inverse_conditions_p (use_cond
, op_cond
) && if_false
== op_lhs
)
2180 /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2181 the set of SSA names defined earlier in STMT's block. */
2184 value_available_p (gimple
*stmt
, hash_set
<tree_ssa_name_hash
> *ssa_names
,
2187 if (is_gimple_min_invariant (value
))
2190 if (TREE_CODE (value
) == SSA_NAME
)
2192 if (SSA_NAME_IS_DEFAULT_DEF (value
))
2195 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (value
));
2196 basic_block use_bb
= gimple_bb (stmt
);
2197 return (def_bb
== use_bb
2198 ? ssa_names
->contains (value
)
2199 : dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
));
2205 /* Helper function for predicate_statements. STMT is a potentially-trapping
2206 arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2207 has value COND. Return a statement that does so. SSA_NAMES is the set of
2208 SSA names defined earlier in STMT's block. */
2211 predicate_rhs_code (gassign
*stmt
, tree mask
, tree cond
,
2212 hash_set
<tree_ssa_name_hash
> *ssa_names
)
2214 tree lhs
= gimple_assign_lhs (stmt
);
2215 tree_code code
= gimple_assign_rhs_code (stmt
);
2216 unsigned int nops
= gimple_num_ops (stmt
);
2217 internal_fn cond_fn
= get_conditional_internal_fn (code
);
2219 /* Construct the arguments to the conditional internal function. */
2220 auto_vec
<tree
, 8> args
;
2221 args
.safe_grow (nops
+ 1);
2223 for (unsigned int i
= 1; i
< nops
; ++i
)
2224 args
[i
] = gimple_op (stmt
, i
);
2225 args
[nops
] = NULL_TREE
;
2227 /* Look for uses of the result to see whether they are COND_EXPRs that can
2228 be folded into the conditional call. */
2229 imm_use_iterator imm_iter
;
2231 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, lhs
)
2233 tree new_else
= check_redundant_cond_expr (use_stmt
, mask
, cond
, lhs
);
2234 if (new_else
&& value_available_p (stmt
, ssa_names
, new_else
))
2237 args
[nops
] = new_else
;
2238 if (operand_equal_p (new_else
, args
[nops
], 0))
2242 LHS = IFN_COND (MASK, ..., ELSE);
2243 X = MASK ? LHS : ELSE;
2245 which makes X equivalent to LHS. */
2246 tree use_lhs
= gimple_assign_lhs (use_stmt
);
2247 redundant_ssa_names
.safe_push (std::make_pair (use_lhs
, lhs
));
2252 args
[nops
] = targetm
.preferred_else_value (cond_fn
, TREE_TYPE (lhs
),
2253 nops
- 1, &args
[1]);
2255 /* Create and insert the call. */
2256 gcall
*new_stmt
= gimple_build_call_internal_vec (cond_fn
, args
);
2257 gimple_call_set_lhs (new_stmt
, lhs
);
2258 gimple_call_set_nothrow (new_stmt
, true);
2263 /* Predicate each write to memory in LOOP.
2265 This function transforms control flow constructs containing memory
2268 | for (i = 0; i < N; i++)
2272 into the following form that does not contain control flow:
2274 | for (i = 0; i < N; i++)
2275 | A[i] = cond ? expr : A[i];
2277 The original CFG looks like this:
2284 | if (i < N) goto bb_5 else goto bb_2
2288 | cond = some_computation;
2289 | if (cond) goto bb_3 else goto bb_4
2301 insert_gimplified_predicates inserts the computation of the COND
2302 expression at the beginning of the destination basic block:
2309 | if (i < N) goto bb_5 else goto bb_2
2313 | cond = some_computation;
2314 | if (cond) goto bb_3 else goto bb_4
2318 | cond = some_computation;
2327 predicate_statements is then predicating the memory write as follows:
2334 | if (i < N) goto bb_5 else goto bb_2
2338 | if (cond) goto bb_3 else goto bb_4
2342 | cond = some_computation;
2343 | A[i] = cond ? expr : A[i];
2351 and finally combine_blocks removes the basic block boundaries making
2352 the loop vectorizable:
2356 | if (i < N) goto bb_5 else goto bb_1
2360 | cond = some_computation;
2361 | A[i] = cond ? expr : A[i];
2362 | if (i < N) goto bb_5 else goto bb_4
2371 predicate_statements (loop_p loop
)
2373 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2374 auto_vec
<int, 1> vect_sizes
;
2375 auto_vec
<tree
, 1> vect_masks
;
2376 hash_set
<tree_ssa_name_hash
> ssa_names
;
2378 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2380 gimple_stmt_iterator gsi
;
2381 basic_block bb
= ifc_bbs
[i
];
2382 tree cond
= bb_predicate (bb
);
2386 if (is_true_predicate (cond
))
2390 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2393 cond
= TREE_OPERAND (cond
, 0);
2396 vect_sizes
.truncate (0);
2397 vect_masks
.truncate (0);
2399 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
2401 gassign
*stmt
= dyn_cast
<gassign
*> (gsi_stmt (gsi
));
2404 else if (is_false_predicate (cond
)
2405 && gimple_vdef (stmt
))
2407 unlink_stmt_vdef (stmt
);
2408 gsi_remove (&gsi
, true);
2409 release_defs (stmt
);
2412 else if (gimple_plf (stmt
, GF_PLF_2
))
2414 tree lhs
= gimple_assign_lhs (stmt
);
2417 gimple_seq stmts
= NULL
;
2418 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
2419 /* We checked before setting GF_PLF_2 that an equivalent
2420 integer mode exists. */
2421 int bitsize
= GET_MODE_BITSIZE (mode
).to_constant ();
2422 if (!vect_sizes
.is_empty ()
2423 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2424 /* Use created mask. */
2425 mask
= vect_masks
[index
];
2428 if (COMPARISON_CLASS_P (cond
))
2429 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2431 TREE_OPERAND (cond
, 0),
2432 TREE_OPERAND (cond
, 1));
2439 = constant_boolean_node (true, TREE_TYPE (mask
));
2440 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2441 TREE_TYPE (mask
), mask
, true_val
);
2443 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2445 /* Save mask and its size for further use. */
2446 vect_sizes
.safe_push (bitsize
);
2447 vect_masks
.safe_push (mask
);
2449 if (gimple_assign_single_p (stmt
))
2450 new_stmt
= predicate_load_or_store (&gsi
, stmt
, mask
);
2452 new_stmt
= predicate_rhs_code (stmt
, mask
, cond
, &ssa_names
);
2454 gsi_replace (&gsi
, new_stmt
, true);
2456 else if (gimple_vdef (stmt
))
2458 tree lhs
= gimple_assign_lhs (stmt
);
2459 tree rhs
= gimple_assign_rhs1 (stmt
);
2460 tree type
= TREE_TYPE (lhs
);
2462 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2463 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2465 std::swap (lhs
, rhs
);
2466 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2467 is_gimple_condexpr
, NULL_TREE
,
2468 true, GSI_SAME_STMT
);
2469 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2470 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2473 tree lhs
= gimple_get_lhs (gsi_stmt (gsi
));
2474 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
2475 ssa_names
.add (lhs
);
2482 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2483 other than the exit and latch of the LOOP. Also resets the
2484 GIMPLE_DEBUG information. */
2487 remove_conditions_and_labels (loop_p loop
)
2489 gimple_stmt_iterator gsi
;
2492 for (i
= 0; i
< loop
->num_nodes
; i
++)
2494 basic_block bb
= ifc_bbs
[i
];
2496 if (bb_with_exit_edge_p (loop
, bb
)
2497 || bb
== loop
->latch
)
2500 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2501 switch (gimple_code (gsi_stmt (gsi
)))
2505 gsi_remove (&gsi
, true);
2509 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2510 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2512 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2513 update_stmt (gsi_stmt (gsi
));
2524 /* Combine all the basic blocks from LOOP into one or two super basic
2525 blocks. Replace PHI nodes with conditional modify expressions. */
2528 combine_blocks (class loop
*loop
)
2530 basic_block bb
, exit_bb
, merge_target_bb
;
2531 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2536 remove_conditions_and_labels (loop
);
2537 insert_gimplified_predicates (loop
);
2538 predicate_all_scalar_phis (loop
);
2540 if (need_to_predicate
)
2541 predicate_statements (loop
);
2543 /* Merge basic blocks: first remove all the edges in the loop,
2544 except for those from the exit block. */
2546 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2547 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2550 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2551 free_bb_predicate (bb
);
2552 if (bb_with_exit_edge_p (loop
, bb
))
2554 gcc_assert (exit_bb
== NULL
);
2558 gcc_assert (exit_bb
!= loop
->latch
);
2560 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2564 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2566 if (e
->src
== exit_bb
)
2573 if (exit_bb
!= NULL
)
2575 if (exit_bb
!= loop
->header
)
2577 /* Connect this node to loop header. */
2578 make_single_succ_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2579 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2582 /* Redirect non-exit edges to loop->latch. */
2583 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2585 if (!loop_exit_edge_p (loop
, e
))
2586 redirect_edge_and_branch (e
, loop
->latch
);
2588 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2592 /* If the loop does not have an exit, reconnect header and latch. */
2593 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2594 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2597 merge_target_bb
= loop
->header
;
2599 /* Get at the virtual def valid for uses starting at the first block
2600 we merge into the header. Without a virtual PHI the loop has the
2601 same virtual use on all stmts. */
2602 gphi
*vphi
= get_virtual_phi (loop
->header
);
2603 tree last_vdef
= NULL_TREE
;
2606 last_vdef
= gimple_phi_result (vphi
);
2607 for (gimple_stmt_iterator gsi
= gsi_start_bb (loop
->header
);
2608 ! gsi_end_p (gsi
); gsi_next (&gsi
))
2609 if (gimple_vdef (gsi_stmt (gsi
)))
2610 last_vdef
= gimple_vdef (gsi_stmt (gsi
));
2612 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2614 gimple_stmt_iterator gsi
;
2615 gimple_stmt_iterator last
;
2619 if (bb
== exit_bb
|| bb
== loop
->latch
)
2622 /* We release virtual PHIs late because we have to propagate them
2623 out using the current VUSE. The def might be the one used
2625 vphi
= get_virtual_phi (bb
);
2628 imm_use_iterator iter
;
2629 use_operand_p use_p
;
2631 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, gimple_phi_result (vphi
))
2633 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2634 SET_USE (use_p
, last_vdef
);
2636 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi
)))
2637 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef
) = 1;
2638 gsi
= gsi_for_stmt (vphi
);
2639 remove_phi_node (&gsi
, true);
2642 /* Make stmts member of loop->header and clear range info from all stmts
2643 in BB which is now no longer executed conditional on a predicate we
2644 could have derived it from. */
2645 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2647 gimple
*stmt
= gsi_stmt (gsi
);
2648 gimple_set_bb (stmt
, merge_target_bb
);
2649 /* Update virtual operands. */
2652 use_operand_p use_p
= ssa_vuse_operand (stmt
);
2654 && USE_FROM_PTR (use_p
) != last_vdef
)
2655 SET_USE (use_p
, last_vdef
);
2656 if (gimple_vdef (stmt
))
2657 last_vdef
= gimple_vdef (stmt
);
2663 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2664 reset_flow_sensitive_info (op
);
2668 /* Update stmt list. */
2669 last
= gsi_last_bb (merge_target_bb
);
2670 gsi_insert_seq_after_without_update (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2671 set_bb_seq (bb
, NULL
);
2673 delete_basic_block (bb
);
2676 /* If possible, merge loop header to the block with the exit edge.
2677 This reduces the number of basic blocks to two, to please the
2678 vectorizer that handles only loops with two nodes. */
2680 && exit_bb
!= loop
->header
)
2682 /* We release virtual PHIs late because we have to propagate them
2683 out using the current VUSE. The def might be the one used
2685 vphi
= get_virtual_phi (exit_bb
);
2688 imm_use_iterator iter
;
2689 use_operand_p use_p
;
2691 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, gimple_phi_result (vphi
))
2693 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2694 SET_USE (use_p
, last_vdef
);
2696 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi
)))
2697 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef
) = 1;
2698 gimple_stmt_iterator gsi
= gsi_for_stmt (vphi
);
2699 remove_phi_node (&gsi
, true);
2702 if (can_merge_blocks_p (loop
->header
, exit_bb
))
2703 merge_blocks (loop
->header
, exit_bb
);
2711 /* Version LOOP before if-converting it; the original loop
2712 will be if-converted, the new copy of the loop will not,
2713 and the LOOP_VECTORIZED internal call will be guarding which
2714 loop to execute. The vectorizer pass will fold this
2715 internal call into either true or false.
2717 Note that this function intentionally invalidates profile. Both edges
2718 out of LOOP_VECTORIZED must have 100% probability so the profile remains
2719 consistent after the condition is folded in the vectorizer. */
2722 version_loop_for_if_conversion (class loop
*loop
, vec
<gimple
*> *preds
)
2724 basic_block cond_bb
;
2725 tree cond
= make_ssa_name (boolean_type_node
);
2726 class loop
*new_loop
;
2728 gimple_stmt_iterator gsi
;
2729 unsigned int save_length
;
2731 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2732 build_int_cst (integer_type_node
, loop
->num
),
2734 gimple_call_set_lhs (g
, cond
);
2736 /* Save BB->aux around loop_version as that uses the same field. */
2737 save_length
= loop
->inner
? loop
->inner
->num_nodes
: loop
->num_nodes
;
2738 void **saved_preds
= XALLOCAVEC (void *, save_length
);
2739 for (unsigned i
= 0; i
< save_length
; i
++)
2740 saved_preds
[i
] = ifc_bbs
[i
]->aux
;
2742 initialize_original_copy_tables ();
2743 /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
2744 is re-merged in the vectorizer. */
2745 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2746 profile_probability::always (),
2747 profile_probability::always (),
2748 profile_probability::always (),
2749 profile_probability::always (), true);
2750 free_original_copy_tables ();
2752 for (unsigned i
= 0; i
< save_length
; i
++)
2753 ifc_bbs
[i
]->aux
= saved_preds
[i
];
2755 if (new_loop
== NULL
)
2758 new_loop
->dont_vectorize
= true;
2759 new_loop
->force_vectorize
= false;
2760 gsi
= gsi_last_bb (cond_bb
);
2761 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2763 preds
->safe_push (g
);
2764 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2765 update_ssa (TODO_update_ssa
);
2769 /* Return true when LOOP satisfies the follow conditions that will
2770 allow it to be recognized by the vectorizer for outer-loop
2772 - The loop is not the root node of the loop tree.
2773 - The loop has exactly one inner loop.
2774 - The loop has a single exit.
2775 - The loop header has a single successor, which is the inner
2777 - Each of the inner and outer loop latches have a single
2779 - The loop exit block has a single predecessor, which is the
2780 inner loop's exit block. */
2783 versionable_outer_loop_p (class loop
*loop
)
2785 if (!loop_outer (loop
)
2786 || loop
->dont_vectorize
2788 || loop
->inner
->next
2789 || !single_exit (loop
)
2790 || !single_succ_p (loop
->header
)
2791 || single_succ (loop
->header
) != loop
->inner
->header
2792 || !single_pred_p (loop
->latch
)
2793 || !single_pred_p (loop
->inner
->latch
))
2796 basic_block outer_exit
= single_pred (loop
->latch
);
2797 basic_block inner_exit
= single_pred (loop
->inner
->latch
);
2799 if (!single_pred_p (outer_exit
) || single_pred (outer_exit
) != inner_exit
)
2803 fprintf (dump_file
, "Found vectorizable outer loop for versioning\n");
2808 /* Performs splitting of critical edges. Skip splitting and return false
2809 if LOOP will not be converted because:
2811 - LOOP is not well formed.
2812 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
2814 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
2817 ifcvt_split_critical_edges (class loop
*loop
, bool aggressive_if_conv
)
2821 unsigned int num
= loop
->num_nodes
;
2826 auto_vec
<edge
> critical_edges
;
2828 /* Loop is not well formed. */
2829 if (num
<= 2 || loop
->inner
|| !single_exit (loop
))
2832 body
= get_loop_body (loop
);
2833 for (i
= 0; i
< num
; i
++)
2836 if (!aggressive_if_conv
2838 && EDGE_COUNT (bb
->preds
) > MAX_PHI_ARG_NUM
)
2840 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2842 "BB %d has complicated PHI with more than %u args.\n",
2843 bb
->index
, MAX_PHI_ARG_NUM
);
2848 if (bb
== loop
->latch
|| bb_with_exit_edge_p (loop
, bb
))
2851 stmt
= last_stmt (bb
);
2852 /* Skip basic blocks not ending with conditional branch. */
2853 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2856 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2857 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2858 critical_edges
.safe_push (e
);
2862 while (critical_edges
.length () > 0)
2864 e
= critical_edges
.pop ();
2865 /* Don't split if bb can be predicated along non-critical edge. */
2866 if (EDGE_COUNT (e
->dest
->preds
) > 2 || all_preds_critical_p (e
->dest
))
2873 /* Delete redundant statements produced by predication which prevents
2874 loop vectorization. */
2877 ifcvt_local_dce (class loop
*loop
)
2882 gimple_stmt_iterator gsi
;
2883 auto_vec
<gimple
*> worklist
;
2884 enum gimple_code code
;
2885 use_operand_p use_p
;
2886 imm_use_iterator imm_iter
;
2887 std::pair
<tree
, tree
> *name_pair
;
2890 FOR_EACH_VEC_ELT (redundant_ssa_names
, i
, name_pair
)
2891 replace_uses_by (name_pair
->first
, name_pair
->second
);
2892 redundant_ssa_names
.release ();
2894 /* The loop has a single BB only. */
2895 basic_block bb
= loop
->header
;
2896 tree latch_vdef
= NULL_TREE
;
2898 worklist
.create (64);
2899 /* Consider all phi as live statements. */
2900 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2902 phi
= gsi_stmt (gsi
);
2903 gimple_set_plf (phi
, GF_PLF_2
, true);
2904 worklist
.safe_push (phi
);
2905 if (virtual_operand_p (gimple_phi_result (phi
)))
2906 latch_vdef
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2908 /* Consider load/store statements, CALL and COND as live. */
2909 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2911 stmt
= gsi_stmt (gsi
);
2912 if (gimple_store_p (stmt
)
2913 || gimple_assign_load_p (stmt
)
2914 || is_gimple_debug (stmt
))
2916 gimple_set_plf (stmt
, GF_PLF_2
, true);
2917 worklist
.safe_push (stmt
);
2920 code
= gimple_code (stmt
);
2921 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2923 gimple_set_plf (stmt
, GF_PLF_2
, true);
2924 worklist
.safe_push (stmt
);
2927 gimple_set_plf (stmt
, GF_PLF_2
, false);
2929 if (code
== GIMPLE_ASSIGN
)
2931 tree lhs
= gimple_assign_lhs (stmt
);
2932 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2934 stmt1
= USE_STMT (use_p
);
2935 if (gimple_bb (stmt1
) != bb
)
2937 gimple_set_plf (stmt
, GF_PLF_2
, true);
2938 worklist
.safe_push (stmt
);
2944 /* Propagate liveness through arguments of live stmt. */
2945 while (worklist
.length () > 0)
2948 use_operand_p use_p
;
2951 stmt
= worklist
.pop ();
2952 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2954 use
= USE_FROM_PTR (use_p
);
2955 if (TREE_CODE (use
) != SSA_NAME
)
2957 stmt1
= SSA_NAME_DEF_STMT (use
);
2958 if (gimple_bb (stmt1
) != bb
2959 || gimple_plf (stmt1
, GF_PLF_2
))
2961 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2962 worklist
.safe_push (stmt1
);
2965 /* Delete dead statements. */
2966 gsi
= gsi_start_bb (bb
);
2967 while (!gsi_end_p (gsi
))
2969 stmt
= gsi_stmt (gsi
);
2970 if (gimple_store_p (stmt
))
2972 tree lhs
= gimple_get_lhs (stmt
);
2974 ao_ref_init (&write
, lhs
);
2976 if (dse_classify_store (&write
, stmt
, false, NULL
, NULL
, latch_vdef
)
2978 delete_dead_or_redundant_assignment (&gsi
, "dead");
2984 if (gimple_plf (stmt
, GF_PLF_2
))
2989 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2991 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2992 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2994 gsi_remove (&gsi
, true);
2995 release_defs (stmt
);
2999 /* If-convert LOOP when it is legal. For the moment this pass has no
3000 profitability analysis. Returns non-zero todo flags when something
3004 tree_if_conversion (class loop
*loop
, vec
<gimple
*> *preds
)
3006 unsigned int todo
= 0;
3007 bool aggressive_if_conv
;
3014 need_to_predicate
= false;
3015 any_complicated_phi
= false;
3017 /* Apply more aggressive if-conversion when loop or its outer loop were
3018 marked with simd pragma. When that's the case, we try to if-convert
3019 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
3020 aggressive_if_conv
= loop
->force_vectorize
;
3021 if (!aggressive_if_conv
)
3023 class loop
*outer_loop
= loop_outer (loop
);
3024 if (outer_loop
&& outer_loop
->force_vectorize
)
3025 aggressive_if_conv
= true;
3028 if (!ifcvt_split_critical_edges (loop
, aggressive_if_conv
))
3031 if (!if_convertible_loop_p (loop
)
3032 || !dbg_cnt (if_conversion_tree
))
3035 if ((need_to_predicate
|| any_complicated_phi
)
3036 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
3037 || loop
->dont_vectorize
))
3040 /* Since we have no cost model, always version loops unless the user
3041 specified -ftree-loop-if-convert or unless versioning is required.
3042 Either version this loop, or if the pattern is right for outer-loop
3043 vectorization, version the outer loop. In the latter case we will
3044 still if-convert the original inner loop. */
3045 if (need_to_predicate
3046 || any_complicated_phi
3047 || flag_tree_loop_if_convert
!= 1)
3050 = (versionable_outer_loop_p (loop_outer (loop
))
3051 ? loop_outer (loop
) : loop
);
3052 class loop
*nloop
= version_loop_for_if_conversion (vloop
, preds
);
3057 /* If versionable_outer_loop_p decided to version the
3058 outer loop, version also the inner loop of the non-vectorized
3059 loop copy. So we transform:
3063 if (LOOP_VECTORIZED (1, 3))
3069 loop3 (copy of loop1)
3070 if (LOOP_VECTORIZED (4, 5))
3071 loop4 (copy of loop2)
3073 loop5 (copy of loop4) */
3074 gcc_assert (nloop
->inner
&& nloop
->inner
->next
== NULL
);
3075 rloop
= nloop
->inner
;
3079 /* Now all statements are if-convertible. Combine all the basic
3080 blocks into one huge basic block doing the if-conversion
3082 combine_blocks (loop
);
3084 /* Perform local CSE, this esp. helps the vectorizer analysis if loads
3085 and stores are involved. CSE only the loop body, not the entry
3086 PHIs, those are to be kept in sync with the non-if-converted copy.
3087 ??? We'll still keep dead stores though. */
3088 exit_bbs
= BITMAP_ALLOC (NULL
);
3089 bitmap_set_bit (exit_bbs
, single_exit (loop
)->dest
->index
);
3090 bitmap_set_bit (exit_bbs
, loop
->latch
->index
);
3091 todo
|= do_rpo_vn (cfun
, loop_preheader_edge (loop
), exit_bbs
);
3093 /* Delete dead predicate computations. */
3094 ifcvt_local_dce (loop
);
3095 BITMAP_FREE (exit_bbs
);
3097 todo
|= TODO_cleanup_cfg
;
3104 for (i
= 0; i
< loop
->num_nodes
; i
++)
3105 free_bb_predicate (ifc_bbs
[i
]);
3119 /* Tree if-conversion pass management. */
3123 const pass_data pass_data_if_conversion
=
3125 GIMPLE_PASS
, /* type */
3127 OPTGROUP_NONE
, /* optinfo_flags */
3128 TV_TREE_LOOP_IFCVT
, /* tv_id */
3129 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3130 0, /* properties_provided */
3131 0, /* properties_destroyed */
3132 0, /* todo_flags_start */
3133 0, /* todo_flags_finish */
3136 class pass_if_conversion
: public gimple_opt_pass
3139 pass_if_conversion (gcc::context
*ctxt
)
3140 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
3143 /* opt_pass methods: */
3144 virtual bool gate (function
*);
3145 virtual unsigned int execute (function
*);
3147 }; // class pass_if_conversion
3150 pass_if_conversion::gate (function
*fun
)
3152 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
3153 && flag_tree_loop_if_convert
!= 0)
3154 || flag_tree_loop_if_convert
== 1);
3158 pass_if_conversion::execute (function
*fun
)
3163 if (number_of_loops (fun
) <= 1)
3166 auto_vec
<gimple
*> preds
;
3167 FOR_EACH_LOOP (loop
, 0)
3168 if (flag_tree_loop_if_convert
== 1
3169 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
3170 && !loop
->dont_vectorize
))
3171 todo
|= tree_if_conversion (loop
, &preds
);
3175 free_numbers_of_iterations_estimates (fun
);
3182 FOR_EACH_BB_FN (bb
, fun
)
3183 gcc_assert (!bb
->aux
);
3186 /* Perform IL update now, it might elide some loops. */
3187 if (todo
& TODO_cleanup_cfg
)
3189 cleanup_tree_cfg ();
3190 if (need_ssa_update_p (fun
))
3191 todo
|= TODO_update_ssa
;
3193 if (todo
& TODO_update_ssa_any
)
3194 update_ssa (todo
& TODO_update_ssa_any
);
3196 /* If if-conversion elided the loop fall back to the original one. */
3197 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3199 gimple
*g
= preds
[i
];
3202 unsigned ifcvt_loop
= tree_to_uhwi (gimple_call_arg (g
, 0));
3203 if (!get_loop (fun
, ifcvt_loop
))
3206 fprintf (dump_file
, "If-converted loop vanished\n");
3207 fold_loop_internal_call (g
, boolean_false_node
);
3217 make_pass_if_conversion (gcc::context
*ctxt
)
3219 return new pass_if_conversion (ctxt
);