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"
124 /* Only handle PHIs with no more arguments unless we are asked to by
126 #define MAX_PHI_ARG_NUM \
127 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))
129 /* True if we've converted a statement that was only executed when some
130 condition C was true, and if for correctness we need to predicate the
131 statement to ensure that it is a no-op when C is false. See
132 predicate_statements for the kinds of predication we support. */
133 static bool need_to_predicate
;
135 /* Indicate if there are any complicated PHIs that need to be handled in
136 if-conversion. Complicated PHI has more than two arguments and can't
137 be degenerated to two arguments PHI. See more information in comment
138 before phi_convertible_by_degenerating_args. */
139 static bool any_complicated_phi
;
141 /* Hash for struct innermost_loop_behavior. It depends on the user to
144 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
146 static inline hashval_t
hash (const value_type
&);
147 static inline bool equal (const value_type
&,
148 const compare_type
&);
152 innermost_loop_behavior_hash::hash (const value_type
&e
)
156 hash
= iterative_hash_expr (e
->base_address
, 0);
157 hash
= iterative_hash_expr (e
->offset
, hash
);
158 hash
= iterative_hash_expr (e
->init
, hash
);
159 return iterative_hash_expr (e
->step
, hash
);
163 innermost_loop_behavior_hash::equal (const value_type
&e1
,
164 const compare_type
&e2
)
166 if ((e1
->base_address
&& !e2
->base_address
)
167 || (!e1
->base_address
&& e2
->base_address
)
168 || (!e1
->offset
&& e2
->offset
)
169 || (e1
->offset
&& !e2
->offset
)
170 || (!e1
->init
&& e2
->init
)
171 || (e1
->init
&& !e2
->init
)
172 || (!e1
->step
&& e2
->step
)
173 || (e1
->step
&& !e2
->step
))
176 if (e1
->base_address
&& e2
->base_address
177 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
179 if (e1
->offset
&& e2
->offset
180 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
182 if (e1
->init
&& e2
->init
183 && !operand_equal_p (e1
->init
, e2
->init
, 0))
185 if (e1
->step
&& e2
->step
186 && !operand_equal_p (e1
->step
, e2
->step
, 0))
192 /* List of basic blocks in if-conversion-suitable order. */
193 static basic_block
*ifc_bbs
;
195 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
196 static hash_map
<innermost_loop_behavior_hash
,
197 data_reference_p
> *innermost_DR_map
;
199 /* Hash table to store <base reference, DR> pairs. */
200 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
202 /* List of redundant SSA names: the first should be replaced by the second. */
203 static vec
< std::pair
<tree
, tree
> > redundant_ssa_names
;
205 /* Structure used to predicate basic blocks. This is attached to the
206 ->aux field of the BBs in the loop to be if-converted. */
207 struct bb_predicate
{
209 /* The condition under which this basic block is executed. */
212 /* PREDICATE is gimplified, and the sequence of statements is
213 recorded here, in order to avoid the duplication of computations
214 that occur in previous conditions. See PR44483. */
215 gimple_seq predicate_gimplified_stmts
;
218 /* Returns true when the basic block BB has a predicate. */
221 bb_has_predicate (basic_block bb
)
223 return bb
->aux
!= NULL
;
226 /* Returns the gimplified predicate for basic block BB. */
229 bb_predicate (basic_block bb
)
231 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
234 /* Sets the gimplified predicate COND for basic block BB. */
237 set_bb_predicate (basic_block bb
, tree cond
)
239 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
240 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
241 || is_gimple_condexpr (cond
));
242 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
245 /* Returns the sequence of statements of the gimplification of the
246 predicate for basic block BB. */
248 static inline gimple_seq
249 bb_predicate_gimplified_stmts (basic_block bb
)
251 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
254 /* Sets the sequence of statements STMTS of the gimplification of the
255 predicate for basic block BB. */
258 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
260 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
263 /* Adds the sequence of statements STMTS to the sequence of statements
264 of the predicate for basic block BB. */
267 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
269 /* We might have updated some stmts in STMTS via force_gimple_operand
270 calling fold_stmt and that producing multiple stmts. Delink immediate
271 uses so update_ssa after loop versioning doesn't get confused for
272 the not yet inserted predicates.
273 ??? This should go away once we reliably avoid updating stmts
275 for (gimple_stmt_iterator gsi
= gsi_start (stmts
);
276 !gsi_end_p (gsi
); gsi_next (&gsi
))
278 gimple
*stmt
= gsi_stmt (gsi
);
279 delink_stmt_imm_use (stmt
);
280 gimple_set_modified (stmt
, true);
282 gimple_seq_add_seq_without_update
283 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
286 /* Initializes to TRUE the predicate of basic block BB. */
289 init_bb_predicate (basic_block bb
)
291 bb
->aux
= XNEW (struct bb_predicate
);
292 set_bb_predicate_gimplified_stmts (bb
, NULL
);
293 set_bb_predicate (bb
, boolean_true_node
);
296 /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
299 release_bb_predicate (basic_block bb
)
301 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
304 /* Ensure that these stmts haven't yet been added to a bb. */
306 for (gimple_stmt_iterator i
= gsi_start (stmts
);
307 !gsi_end_p (i
); gsi_next (&i
))
308 gcc_assert (! gimple_bb (gsi_stmt (i
)));
311 gimple_seq_discard (stmts
);
312 set_bb_predicate_gimplified_stmts (bb
, NULL
);
316 /* Free the predicate of basic block BB. */
319 free_bb_predicate (basic_block bb
)
321 if (!bb_has_predicate (bb
))
324 release_bb_predicate (bb
);
329 /* Reinitialize predicate of BB with the true predicate. */
332 reset_bb_predicate (basic_block bb
)
334 if (!bb_has_predicate (bb
))
335 init_bb_predicate (bb
);
338 release_bb_predicate (bb
);
339 set_bb_predicate (bb
, boolean_true_node
);
343 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
344 the expression EXPR. Inserts the statement created for this
345 computation before GSI and leaves the iterator GSI at the same
349 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
351 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
352 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
353 gimple_set_vuse (stmt
, gimple_vuse (gsi_stmt (*gsi
)));
354 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
358 /* Return true when COND is a false predicate. */
361 is_false_predicate (tree cond
)
363 return (cond
!= NULL_TREE
364 && (cond
== boolean_false_node
365 || integer_zerop (cond
)));
368 /* Return true when COND is a true predicate. */
371 is_true_predicate (tree cond
)
373 return (cond
== NULL_TREE
374 || cond
== boolean_true_node
375 || integer_onep (cond
));
378 /* Returns true when BB has a predicate that is not trivial: true or
382 is_predicated (basic_block bb
)
384 return !is_true_predicate (bb_predicate (bb
));
387 /* Parses the predicate COND and returns its comparison code and
388 operands OP0 and OP1. */
390 static enum tree_code
391 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
395 if (TREE_CODE (cond
) == SSA_NAME
396 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
398 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
400 *op0
= gimple_assign_rhs1 (s
);
401 *op1
= gimple_assign_rhs2 (s
);
402 return gimple_assign_rhs_code (s
);
405 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
407 tree op
= gimple_assign_rhs1 (s
);
408 tree type
= TREE_TYPE (op
);
409 enum tree_code code
= parse_predicate (op
, op0
, op1
);
411 return code
== ERROR_MARK
? ERROR_MARK
412 : invert_tree_comparison (code
, HONOR_NANS (type
));
418 if (COMPARISON_CLASS_P (cond
))
420 *op0
= TREE_OPERAND (cond
, 0);
421 *op1
= TREE_OPERAND (cond
, 1);
422 return TREE_CODE (cond
);
428 /* Returns the fold of predicate C1 OR C2 at location LOC. */
431 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
433 tree op1a
, op1b
, op2a
, op2b
;
434 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
435 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
437 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
439 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
445 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
448 /* Returns either a COND_EXPR or the folded expression if the folded
449 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
450 a constant or a SSA_NAME. */
453 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
455 tree rhs1
, lhs1
, cond_expr
;
457 /* If COND is comparison r != 0 and r has boolean type, convert COND
458 to SSA_NAME to accept by vect bool pattern. */
459 if (TREE_CODE (cond
) == NE_EXPR
)
461 tree op0
= TREE_OPERAND (cond
, 0);
462 tree op1
= TREE_OPERAND (cond
, 1);
463 if (TREE_CODE (op0
) == SSA_NAME
464 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
465 && (integer_zerop (op1
)))
468 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
, rhs
, lhs
);
470 if (cond_expr
== NULL_TREE
)
471 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
473 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
475 if (is_gimple_val (cond_expr
))
478 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
480 rhs1
= TREE_OPERAND (cond_expr
, 1);
481 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
482 if (is_gimple_val (rhs1
))
483 return build1 (ABS_EXPR
, type
, rhs1
);
486 if (TREE_CODE (cond_expr
) == MIN_EXPR
487 || TREE_CODE (cond_expr
) == MAX_EXPR
)
489 lhs1
= TREE_OPERAND (cond_expr
, 0);
490 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
491 rhs1
= TREE_OPERAND (cond_expr
, 1);
492 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
493 if (is_gimple_val (rhs1
) && is_gimple_val (lhs1
))
494 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
496 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
499 /* Add condition NC to the predicate list of basic block BB. LOOP is
500 the loop to be if-converted. Use predicate of cd-equivalent block
501 for join bb if it exists: we call basic blocks bb1 and bb2
502 cd-equivalent if they are executed under the same condition. */
505 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
510 if (is_true_predicate (nc
))
513 /* If dominance tells us this basic block is always executed,
514 don't record any predicates for it. */
515 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
518 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
519 /* We use notion of cd equivalence to get simpler predicate for
520 join block, e.g. if join block has 2 predecessors with predicates
521 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
522 p1 & p2 | p1 & !p2. */
523 if (dom_bb
!= loop
->header
524 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
526 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
527 bc
= bb_predicate (dom_bb
);
528 if (!is_true_predicate (bc
))
529 set_bb_predicate (bb
, bc
);
531 gcc_assert (is_true_predicate (bb_predicate (bb
)));
532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
533 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
534 dom_bb
->index
, bb
->index
);
538 if (!is_predicated (bb
))
542 bc
= bb_predicate (bb
);
543 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
544 if (is_true_predicate (bc
))
546 reset_bb_predicate (bb
);
551 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
552 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
553 tp
= &TREE_OPERAND (bc
, 0);
556 if (!is_gimple_condexpr (*tp
))
559 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
560 add_bb_predicate_gimplified_stmts (bb
, stmts
);
562 set_bb_predicate (bb
, bc
);
565 /* Add the condition COND to the previous condition PREV_COND, and add
566 this to the predicate list of the destination of edge E. LOOP is
567 the loop to be if-converted. */
570 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
571 tree prev_cond
, tree cond
)
573 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
576 if (!is_true_predicate (prev_cond
))
577 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
580 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
581 add_to_predicate_list (loop
, e
->dest
, cond
);
584 /* Return true if one of the successor edges of BB exits LOOP. */
587 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
592 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
593 if (loop_exit_edge_p (loop
, e
))
599 /* Given PHI which has more than two arguments, this function checks if
600 it's if-convertible by degenerating its arguments. Specifically, if
601 below two conditions are satisfied:
603 1) Number of PHI arguments with different values equals to 2 and one
604 argument has the only occurrence.
605 2) The edge corresponding to the unique argument isn't critical edge.
607 Such PHI can be handled as PHIs have only two arguments. For example,
610 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
612 can be transformed into:
614 res = (predicate of e3) ? A_2 : A_1;
616 Return TRUE if it is the case, FALSE otherwise. */
619 phi_convertible_by_degenerating_args (gphi
*phi
)
622 tree arg
, t1
= NULL
, t2
= NULL
;
623 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
624 unsigned int num_args
= gimple_phi_num_args (phi
);
626 gcc_assert (num_args
> 2);
628 for (i
= 0; i
< num_args
; i
++)
630 arg
= gimple_phi_arg_def (phi
, i
);
631 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
637 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
647 if (n1
!= 1 && n2
!= 1)
650 /* Check if the edge corresponding to the unique arg is critical. */
651 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
652 if (EDGE_COUNT (e
->src
->succs
) > 1)
658 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
659 and it belongs to basic block BB. Note at this point, it is sure
660 that PHI is if-convertible. This function updates global variable
661 ANY_COMPLICATED_PHI if PHI is complicated. */
664 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
)
666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
668 fprintf (dump_file
, "-------------------------\n");
669 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
672 if (bb
!= loop
->header
673 && gimple_phi_num_args (phi
) > 2
674 && !phi_convertible_by_degenerating_args (phi
))
675 any_complicated_phi
= true;
680 /* Records the status of a data reference. This struct is attached to
681 each DR->aux field. */
684 bool rw_unconditionally
;
685 bool w_unconditionally
;
686 bool written_at_least_once
;
690 tree base_w_predicate
;
693 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
694 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
695 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
696 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
698 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
699 HASH tables. While storing them in HASH table, it checks if the
700 reference is unconditionally read or written and stores that as a flag
701 information. For base reference it checks if it is written atlest once
702 unconditionally and stores it as flag information along with DR.
703 In other words for every data reference A in STMT there exist other
704 accesses to a data reference with the same base with predicates that
705 add up (OR-up) to the true predicate: this ensures that the data
706 reference A is touched (read or written) on every iteration of the
707 if-converted loop. */
709 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
712 data_reference_p
*master_dr
, *base_master_dr
;
713 tree base_ref
= DR_BASE_OBJECT (a
);
714 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
715 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
718 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
724 IFC_DR (*master_dr
)->w_predicate
725 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
726 IFC_DR (*master_dr
)->w_predicate
);
727 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
728 DR_W_UNCONDITIONALLY (*master_dr
) = true;
730 IFC_DR (*master_dr
)->rw_predicate
731 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
732 IFC_DR (*master_dr
)->rw_predicate
);
733 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
734 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
738 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
741 IFC_DR (*base_master_dr
)->base_w_predicate
742 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
743 IFC_DR (*base_master_dr
)->base_w_predicate
);
744 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
745 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
749 /* Return TRUE if can prove the index IDX of an array reference REF is
750 within array bound. Return false otherwise. */
753 idx_within_array_bound (tree ref
, tree
*idx
, void *dta
)
755 wi::overflow_type overflow
;
756 widest_int niter
, valid_niter
, delta
, wi_step
;
759 struct loop
*loop
= (struct loop
*) dta
;
761 /* Only support within-bound access for array references. */
762 if (TREE_CODE (ref
) != ARRAY_REF
)
765 /* For arrays at the end of the structure, we are not guaranteed that they
766 do not really extend over their declared size. However, for arrays of
767 size greater than one, this is unlikely to be intended. */
768 if (array_at_struct_end_p (ref
))
771 ev
= analyze_scalar_evolution (loop
, *idx
);
772 ev
= instantiate_parameters (loop
, ev
);
773 init
= initial_condition (ev
);
774 step
= evolution_part_in_loop_num (ev
, loop
->num
);
776 if (!init
|| TREE_CODE (init
) != INTEGER_CST
777 || (step
&& TREE_CODE (step
) != INTEGER_CST
))
780 low
= array_ref_low_bound (ref
);
781 high
= array_ref_up_bound (ref
);
783 /* The case of nonconstant bounds could be handled, but it would be
785 if (TREE_CODE (low
) != INTEGER_CST
786 || !high
|| TREE_CODE (high
) != INTEGER_CST
)
789 /* Check if the intial idx is within bound. */
790 if (wi::to_widest (init
) < wi::to_widest (low
)
791 || wi::to_widest (init
) > wi::to_widest (high
))
794 /* The idx is always within bound. */
795 if (!step
|| integer_zerop (step
))
798 if (!max_loop_iterations (loop
, &niter
))
801 if (wi::to_widest (step
) < 0)
803 delta
= wi::to_widest (init
) - wi::to_widest (low
);
804 wi_step
= -wi::to_widest (step
);
808 delta
= wi::to_widest (high
) - wi::to_widest (init
);
809 wi_step
= wi::to_widest (step
);
812 valid_niter
= wi::div_floor (delta
, wi_step
, SIGNED
, &overflow
);
813 /* The iteration space of idx is within array bound. */
814 if (!overflow
&& niter
<= valid_niter
)
820 /* Return TRUE if ref is a within bound array reference. */
823 ref_within_array_bound (gimple
*stmt
, tree ref
)
825 struct loop
*loop
= loop_containing_stmt (stmt
);
827 gcc_assert (loop
!= NULL
);
828 return for_each_index (&ref
, idx_within_array_bound
, loop
);
832 /* Given a memory reference expression T, return TRUE if base object
833 it refers to is writable. The base object of a memory reference
834 is the main object being referenced, which is returned by function
838 base_object_writable (tree ref
)
840 tree base_tree
= get_base_address (ref
);
843 && DECL_P (base_tree
)
844 && decl_binds_to_current_def_p (base_tree
)
845 && !TREE_READONLY (base_tree
));
848 /* Return true when the memory references of STMT won't trap in the
849 if-converted code. There are two things that we have to check for:
851 - writes to memory occur to writable memory: if-conversion of
852 memory writes transforms the conditional memory writes into
853 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
854 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
855 be executed at all in the original code, it may be a readonly
856 memory. To check that A is not const-qualified, we check that
857 there exists at least an unconditional write to A in the current
860 - reads or writes to memory are valid memory accesses for every
861 iteration. To check that the memory accesses are correctly formed
862 and that we are allowed to read and write in these locations, we
863 check that the memory accesses to be if-converted occur at every
864 iteration unconditionally.
866 Returns true for the memory reference in STMT, same memory reference
867 is read or written unconditionally atleast once and the base memory
868 reference is written unconditionally once. This is to check reference
869 will not write fault. Also retuns true if the memory reference is
870 unconditionally read once then we are conditionally writing to memory
871 which is defined as read and write and is bound to the definition
874 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
876 /* If DR didn't see a reference here we can't use it to tell
877 whether the ref traps or not. */
878 if (gimple_uid (stmt
) == 0)
881 data_reference_p
*master_dr
, *base_master_dr
;
882 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
884 tree base
= DR_BASE_OBJECT (a
);
885 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
887 gcc_assert (DR_STMT (a
) == stmt
);
888 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
889 || DR_INIT (a
) || DR_STEP (a
));
891 master_dr
= innermost_DR_map
->get (innermost
);
892 gcc_assert (master_dr
!= NULL
);
894 base_master_dr
= baseref_DR_map
->get (base
);
896 /* If a is unconditionally written to it doesn't trap. */
897 if (DR_W_UNCONDITIONALLY (*master_dr
))
900 /* If a is unconditionally accessed then ...
902 Even a is conditional access, we can treat it as an unconditional
903 one if it's an array reference and all its index are within array
905 if (DR_RW_UNCONDITIONALLY (*master_dr
)
906 || ref_within_array_bound (stmt
, DR_REF (a
)))
908 /* an unconditional read won't trap. */
912 /* an unconditionaly write won't trap if the base is written
913 to unconditionally. */
915 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
916 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
917 /* or the base is known to be not readonly. */
918 else if (base_object_writable (DR_REF (a
)))
919 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
925 /* Return true if STMT could be converted into a masked load or store
926 (conditional load or store based on a mask computed from bb predicate). */
929 ifcvt_can_use_mask_load_store (gimple
*stmt
)
931 /* Check whether this is a load or store. */
932 tree lhs
= gimple_assign_lhs (stmt
);
935 if (gimple_store_p (stmt
))
937 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
942 else if (gimple_assign_load_p (stmt
))
945 ref
= gimple_assign_rhs1 (stmt
);
950 if (may_be_nonaddressable_p (ref
))
953 /* Mask should be integer mode of the same size as the load/store
955 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
956 if (!int_mode_for_mode (mode
).exists () || VECTOR_MODE_P (mode
))
959 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
965 /* Return true if STMT could be converted from an operation that is
966 unconditional to one that is conditional on a bb predicate mask. */
969 ifcvt_can_predicate (gimple
*stmt
)
971 basic_block bb
= gimple_bb (stmt
);
973 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
974 || bb
->loop_father
->dont_vectorize
975 || gimple_has_volatile_ops (stmt
))
978 if (gimple_assign_single_p (stmt
))
979 return ifcvt_can_use_mask_load_store (stmt
);
981 tree_code code
= gimple_assign_rhs_code (stmt
);
982 tree lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
983 tree rhs_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
984 if (!types_compatible_p (lhs_type
, rhs_type
))
986 internal_fn cond_fn
= get_conditional_internal_fn (code
);
987 return (cond_fn
!= IFN_LAST
988 && vectorized_internal_fn_supported_p (cond_fn
, lhs_type
));
991 /* Return true when STMT is if-convertible.
993 GIMPLE_ASSIGN statement is not if-convertible if,
996 - LHS is not var decl. */
999 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
1000 vec
<data_reference_p
> refs
)
1002 tree lhs
= gimple_assign_lhs (stmt
);
1004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1006 fprintf (dump_file
, "-------------------------\n");
1007 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1010 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
1013 /* Some of these constrains might be too conservative. */
1014 if (stmt_ends_bb_p (stmt
)
1015 || gimple_has_volatile_ops (stmt
)
1016 || (TREE_CODE (lhs
) == SSA_NAME
1017 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1018 || gimple_has_side_effects (stmt
))
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1021 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
1025 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
1026 in between if_convertible_loop_p and combine_blocks
1027 we can perform loop versioning. */
1028 gimple_set_plf (stmt
, GF_PLF_2
, false);
1030 if ((! gimple_vuse (stmt
)
1031 || gimple_could_trap_p_1 (stmt
, false, false)
1032 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
1033 && gimple_could_trap_p (stmt
))
1035 if (ifcvt_can_predicate (stmt
))
1037 gimple_set_plf (stmt
, GF_PLF_2
, true);
1038 need_to_predicate
= true;
1041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1042 fprintf (dump_file
, "tree could trap...\n");
1046 /* When if-converting stores force versioning, likewise if we
1047 ended up generating store data races. */
1048 if (gimple_vdef (stmt
))
1049 need_to_predicate
= true;
1054 /* Return true when STMT is if-convertible.
1056 A statement is if-convertible if:
1057 - it is an if-convertible GIMPLE_ASSIGN,
1058 - it is a GIMPLE_LABEL or a GIMPLE_COND,
1059 - it is builtins call. */
1062 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
1064 switch (gimple_code (stmt
))
1072 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
1076 tree fndecl
= gimple_call_fndecl (stmt
);
1079 int flags
= gimple_call_flags (stmt
);
1080 if ((flags
& ECF_CONST
)
1081 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
1082 /* We can only vectorize some builtins at the moment,
1083 so restrict if-conversion to those. */
1084 && fndecl_built_in_p (fndecl
))
1091 /* Don't know what to do with 'em so don't do anything. */
1092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1094 fprintf (dump_file
, "don't know what to do\n");
1095 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1103 /* Assumes that BB has more than 1 predecessors.
1104 Returns false if at least one successor is not on critical edge
1105 and true otherwise. */
1108 all_preds_critical_p (basic_block bb
)
1113 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1114 if (EDGE_COUNT (e
->src
->succs
) == 1)
1119 /* Return true when BB is if-convertible. This routine does not check
1120 basic block's statements and phis.
1122 A basic block is not if-convertible if:
1123 - it is non-empty and it is after the exit block (in BFS order),
1124 - it is after the exit block but before the latch,
1125 - its edges are not normal.
1127 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1131 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1137 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1139 if (EDGE_COUNT (bb
->succs
) > 2)
1144 if (bb
!= loop
->latch
)
1146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1147 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1150 else if (!empty_block_p (bb
))
1152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1153 fprintf (dump_file
, "non empty basic block after exit bb\n");
1156 else if (bb
== loop
->latch
1158 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1161 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1166 /* Be less adventurous and handle only normal edges. */
1167 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1168 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1171 fprintf (dump_file
, "Difficult to handle edges\n");
1178 /* Return true when all predecessor blocks of BB are visited. The
1179 VISITED bitmap keeps track of the visited blocks. */
1182 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1186 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1187 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1193 /* Get body of a LOOP in suitable order for if-conversion. It is
1194 caller's responsibility to deallocate basic block list.
1195 If-conversion suitable order is, breadth first sort (BFS) order
1196 with an additional constraint: select a block only if all its
1197 predecessors are already selected. */
1199 static basic_block
*
1200 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1202 basic_block
*blocks
, *blocks_in_bfs_order
;
1205 unsigned int index
= 0;
1206 unsigned int visited_count
= 0;
1208 gcc_assert (loop
->num_nodes
);
1209 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1211 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1212 visited
= BITMAP_ALLOC (NULL
);
1214 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1217 while (index
< loop
->num_nodes
)
1219 bb
= blocks_in_bfs_order
[index
];
1221 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1223 free (blocks_in_bfs_order
);
1224 BITMAP_FREE (visited
);
1229 if (!bitmap_bit_p (visited
, bb
->index
))
1231 if (pred_blocks_visited_p (bb
, &visited
)
1232 || bb
== loop
->header
)
1234 /* This block is now visited. */
1235 bitmap_set_bit (visited
, bb
->index
);
1236 blocks
[visited_count
++] = bb
;
1242 if (index
== loop
->num_nodes
1243 && visited_count
!= loop
->num_nodes
)
1247 free (blocks_in_bfs_order
);
1248 BITMAP_FREE (visited
);
1252 /* Returns true when the analysis of the predicates for all the basic
1253 blocks in LOOP succeeded.
1255 predicate_bbs first allocates the predicates of the basic blocks.
1256 These fields are then initialized with the tree expressions
1257 representing the predicates under which a basic block is executed
1258 in the LOOP. As the loop->header is executed at each iteration, it
1259 has the "true" predicate. Other statements executed under a
1260 condition are predicated with that condition, for example
1267 S1 will be predicated with "x", and
1268 S2 will be predicated with "!x". */
1271 predicate_bbs (loop_p loop
)
1275 for (i
= 0; i
< loop
->num_nodes
; i
++)
1276 init_bb_predicate (ifc_bbs
[i
]);
1278 for (i
= 0; i
< loop
->num_nodes
; i
++)
1280 basic_block bb
= ifc_bbs
[i
];
1284 /* The loop latch and loop exit block are always executed and
1285 have no extra conditions to be processed: skip them. */
1286 if (bb
== loop
->latch
1287 || bb_with_exit_edge_p (loop
, bb
))
1289 reset_bb_predicate (bb
);
1293 cond
= bb_predicate (bb
);
1294 stmt
= last_stmt (bb
);
1295 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1298 edge true_edge
, false_edge
;
1299 location_t loc
= gimple_location (stmt
);
1300 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1302 gimple_cond_lhs (stmt
),
1303 gimple_cond_rhs (stmt
));
1305 /* Add new condition into destination's predicate list. */
1306 extract_true_false_edges_from_block (gimple_bb (stmt
),
1307 &true_edge
, &false_edge
);
1309 /* If C is true, then TRUE_EDGE is taken. */
1310 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1313 /* If C is false, then FALSE_EDGE is taken. */
1314 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1316 add_to_dst_predicate_list (loop
, false_edge
,
1317 unshare_expr (cond
), c2
);
1322 /* If current bb has only one successor, then consider it as an
1323 unconditional goto. */
1324 if (single_succ_p (bb
))
1326 basic_block bb_n
= single_succ (bb
);
1328 /* The successor bb inherits the predicate of its
1329 predecessor. If there is no predicate in the predecessor
1330 bb, then consider the successor bb as always executed. */
1331 if (cond
== NULL_TREE
)
1332 cond
= boolean_true_node
;
1334 add_to_predicate_list (loop
, bb_n
, cond
);
1338 /* The loop header is always executed. */
1339 reset_bb_predicate (loop
->header
);
1340 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1341 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1344 /* Build region by adding loop pre-header and post-header blocks. */
1346 static vec
<basic_block
>
1347 build_region (struct loop
*loop
)
1349 vec
<basic_block
> region
= vNULL
;
1350 basic_block exit_bb
= NULL
;
1352 gcc_assert (ifc_bbs
);
1353 /* The first element is loop pre-header. */
1354 region
.safe_push (loop_preheader_edge (loop
)->src
);
1356 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
1358 basic_block bb
= ifc_bbs
[i
];
1359 region
.safe_push (bb
);
1360 /* Find loop postheader. */
1363 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1364 if (loop_exit_edge_p (loop
, e
))
1370 /* The last element is loop post-header. */
1371 gcc_assert (exit_bb
);
1372 region
.safe_push (exit_bb
);
1376 /* Return true when LOOP is if-convertible. This is a helper function
1377 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1378 in if_convertible_loop_p. */
1381 if_convertible_loop_p_1 (struct loop
*loop
, vec
<data_reference_p
> *refs
)
1384 basic_block exit_bb
= NULL
;
1385 vec
<basic_block
> region
;
1387 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1390 calculate_dominance_info (CDI_DOMINATORS
);
1392 /* Allow statements that can be handled during if-conversion. */
1393 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1396 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1397 fprintf (dump_file
, "Irreducible loop\n");
1401 for (i
= 0; i
< loop
->num_nodes
; i
++)
1403 basic_block bb
= ifc_bbs
[i
];
1405 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1408 if (bb_with_exit_edge_p (loop
, bb
))
1412 for (i
= 0; i
< loop
->num_nodes
; i
++)
1414 basic_block bb
= ifc_bbs
[i
];
1415 gimple_stmt_iterator gsi
;
1417 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1418 switch (gimple_code (gsi_stmt (gsi
)))
1425 gimple_set_uid (gsi_stmt (gsi
), 0);
1432 data_reference_p dr
;
1435 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1436 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1438 /* Compute post-dominator tree locally. */
1439 region
= build_region (loop
);
1440 calculate_dominance_info_for_region (CDI_POST_DOMINATORS
, region
);
1442 predicate_bbs (loop
);
1444 /* Free post-dominator tree since it is not used after predication. */
1445 free_dominance_info_for_region (cfun
, CDI_POST_DOMINATORS
, region
);
1448 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1450 tree ref
= DR_REF (dr
);
1452 dr
->aux
= XNEW (struct ifc_dr
);
1453 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1454 DR_RW_UNCONDITIONALLY (dr
) = false;
1455 DR_W_UNCONDITIONALLY (dr
) = false;
1456 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1457 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1458 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1459 if (gimple_uid (DR_STMT (dr
)) == 0)
1460 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1462 /* If DR doesn't have innermost loop behavior or it's a compound
1463 memory reference, we synthesize its innermost loop behavior
1465 if (TREE_CODE (ref
) == COMPONENT_REF
1466 || TREE_CODE (ref
) == IMAGPART_EXPR
1467 || TREE_CODE (ref
) == REALPART_EXPR
1468 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1469 || DR_INIT (dr
) || DR_STEP (dr
)))
1471 while (TREE_CODE (ref
) == COMPONENT_REF
1472 || TREE_CODE (ref
) == IMAGPART_EXPR
1473 || TREE_CODE (ref
) == REALPART_EXPR
)
1474 ref
= TREE_OPERAND (ref
, 0);
1476 memset (&DR_INNERMOST (dr
), 0, sizeof (DR_INNERMOST (dr
)));
1477 DR_BASE_ADDRESS (dr
) = ref
;
1479 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1482 for (i
= 0; i
< loop
->num_nodes
; i
++)
1484 basic_block bb
= ifc_bbs
[i
];
1485 gimple_stmt_iterator itr
;
1487 /* Check the if-convertibility of statements in predicated BBs. */
1488 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1489 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1490 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1494 /* Checking PHIs needs to be done after stmts, as the fact whether there
1495 are any masked loads or stores affects the tests. */
1496 for (i
= 0; i
< loop
->num_nodes
; i
++)
1498 basic_block bb
= ifc_bbs
[i
];
1501 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1502 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1507 fprintf (dump_file
, "Applying if-conversion\n");
1512 /* Return true when LOOP is if-convertible.
1513 LOOP is if-convertible if:
1515 - it has two or more basic blocks,
1516 - it has only one exit,
1517 - loop header is not the exit edge,
1518 - if its basic blocks and phi nodes are if convertible. */
1521 if_convertible_loop_p (struct loop
*loop
)
1526 vec
<data_reference_p
> refs
;
1528 /* Handle only innermost loop. */
1529 if (!loop
|| loop
->inner
)
1531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1532 fprintf (dump_file
, "not innermost loop\n");
1536 /* If only one block, no need for if-conversion. */
1537 if (loop
->num_nodes
<= 2)
1539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1540 fprintf (dump_file
, "less than 2 basic blocks\n");
1544 /* More than one loop exit is too much to handle. */
1545 if (!single_exit (loop
))
1547 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1548 fprintf (dump_file
, "multiple exits\n");
1552 /* If one of the loop header's edge is an exit edge then do not
1553 apply if-conversion. */
1554 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1555 if (loop_exit_edge_p (loop
, e
))
1559 res
= if_convertible_loop_p_1 (loop
, &refs
);
1561 data_reference_p dr
;
1563 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1566 free_data_refs (refs
);
1568 delete innermost_DR_map
;
1569 innermost_DR_map
= NULL
;
1571 delete baseref_DR_map
;
1572 baseref_DR_map
= NULL
;
1577 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1578 which is in predicated basic block.
1579 In fact, the following PHI pattern is searching:
1581 reduc_1 = PHI <..., reduc_2>
1585 reduc_2 = PHI <reduc_1, reduc_3>
1587 ARG_0 and ARG_1 are correspondent PHI arguments.
1588 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1589 EXTENDED is true if PHI has > 2 arguments. */
1592 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1593 tree
*op0
, tree
*op1
, bool extended
)
1595 tree lhs
, r_op1
, r_op2
;
1597 gimple
*header_phi
= NULL
;
1598 enum tree_code reduction_op
;
1599 basic_block bb
= gimple_bb (phi
);
1600 struct loop
*loop
= bb
->loop_father
;
1601 edge latch_e
= loop_latch_edge (loop
);
1602 imm_use_iterator imm_iter
;
1603 use_operand_p use_p
;
1606 bool result
= false;
1607 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1610 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1613 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1614 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1616 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1619 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1620 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1624 if (gimple_bb (header_phi
) != loop
->header
)
1627 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1630 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1631 || gimple_has_volatile_ops (stmt
))
1634 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1637 if (!is_predicated (gimple_bb (stmt
)))
1640 /* Check that stmt-block is predecessor of phi-block. */
1641 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1650 if (!has_single_use (lhs
))
1653 reduction_op
= gimple_assign_rhs_code (stmt
);
1654 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1656 r_op1
= gimple_assign_rhs1 (stmt
);
1657 r_op2
= gimple_assign_rhs2 (stmt
);
1659 /* Make R_OP1 to hold reduction variable. */
1660 if (r_op2
== PHI_RESULT (header_phi
)
1661 && reduction_op
== PLUS_EXPR
)
1662 std::swap (r_op1
, r_op2
);
1663 else if (r_op1
!= PHI_RESULT (header_phi
))
1666 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1667 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1669 gimple
*use_stmt
= USE_STMT (use_p
);
1670 if (is_gimple_debug (use_stmt
))
1672 if (use_stmt
== stmt
)
1674 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1678 *op0
= r_op1
; *op1
= r_op2
;
1683 /* Converts conditional scalar reduction into unconditional form, e.g.
1685 if (_5 != 0) goto bb_5 else goto bb_6
1691 # res_2 = PHI <res_13(4), res_6(5)>
1694 will be converted into sequence
1695 _ifc__1 = _5 != 0 ? 1 : 0;
1696 res_2 = res_13 + _ifc__1;
1697 Argument SWAP tells that arguments of conditional expression should be
1699 Returns rhs of resulting PHI assignment. */
1702 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1703 tree cond
, tree op0
, tree op1
, bool swap
)
1705 gimple_stmt_iterator stmt_it
;
1708 tree rhs1
= gimple_assign_rhs1 (reduc
);
1709 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1711 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1715 fprintf (dump_file
, "Found cond scalar reduction.\n");
1716 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1719 /* Build cond expression using COND and constant operand
1720 of reduction rhs. */
1721 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1722 unshare_expr (cond
),
1726 /* Create assignment stmt and insert it at GSI. */
1727 new_assign
= gimple_build_assign (tmp
, c
);
1728 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1729 /* Build rhs for unconditional increment/decrement. */
1730 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1731 TREE_TYPE (rhs1
), op0
, tmp
);
1733 /* Delete original reduction stmt. */
1734 stmt_it
= gsi_for_stmt (reduc
);
1735 gsi_remove (&stmt_it
, true);
1736 release_defs (reduc
);
1740 /* Produce condition for all occurrences of ARG in PHI node. */
1743 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1744 gimple_stmt_iterator
*gsi
)
1748 tree cond
= NULL_TREE
;
1752 len
= occur
->length ();
1753 gcc_assert (len
> 0);
1754 for (i
= 0; i
< len
; i
++)
1756 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1757 c
= bb_predicate (e
->src
);
1758 if (is_true_predicate (c
))
1763 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1764 is_gimple_condexpr
, NULL_TREE
,
1765 true, GSI_SAME_STMT
);
1766 if (cond
!= NULL_TREE
)
1768 /* Must build OR expression. */
1769 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1770 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1771 is_gimple_condexpr
, NULL_TREE
,
1772 true, GSI_SAME_STMT
);
1777 gcc_assert (cond
!= NULL_TREE
);
1781 /* Local valueization callback that follows all-use SSA edges. */
1784 ifcvt_follow_ssa_use_edges (tree val
)
1789 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1790 This routine can handle PHI nodes with more than two arguments.
1793 S1: A = PHI <x1(1), x2(5)>
1795 S2: A = cond ? x1 : x2;
1797 The generated code is inserted at GSI that points to the top of
1798 basic block's statement list.
1799 If PHI node has more than two arguments a chain of conditional
1800 expression is produced. */
1804 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1806 gimple
*new_stmt
= NULL
, *reduc
;
1807 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1809 unsigned int index0
;
1810 unsigned int max
, args_len
;
1815 res
= gimple_phi_result (phi
);
1816 if (virtual_operand_p (res
))
1819 if ((rhs
= degenerate_phi_result (phi
))
1820 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1822 && !chrec_contains_undetermined (scev
)
1824 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1828 fprintf (dump_file
, "Degenerate phi!\n");
1829 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1831 new_stmt
= gimple_build_assign (res
, rhs
);
1832 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1833 update_stmt (new_stmt
);
1837 bb
= gimple_bb (phi
);
1838 if (EDGE_COUNT (bb
->preds
) == 2)
1840 /* Predicate ordinary PHI node with 2 arguments. */
1841 edge first_edge
, second_edge
;
1842 basic_block true_bb
;
1843 first_edge
= EDGE_PRED (bb
, 0);
1844 second_edge
= EDGE_PRED (bb
, 1);
1845 cond
= bb_predicate (first_edge
->src
);
1846 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1847 std::swap (first_edge
, second_edge
);
1848 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1850 cond
= bb_predicate (second_edge
->src
);
1851 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1852 cond
= TREE_OPERAND (cond
, 0);
1854 first_edge
= second_edge
;
1857 cond
= bb_predicate (first_edge
->src
);
1858 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1859 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1860 is_gimple_condexpr
, NULL_TREE
,
1861 true, GSI_SAME_STMT
);
1862 true_bb
= first_edge
->src
;
1863 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1865 arg0
= gimple_phi_arg_def (phi
, 1);
1866 arg1
= gimple_phi_arg_def (phi
, 0);
1870 arg0
= gimple_phi_arg_def (phi
, 0);
1871 arg1
= gimple_phi_arg_def (phi
, 1);
1873 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1875 /* Convert reduction stmt into vectorizable form. */
1876 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1877 true_bb
!= gimple_bb (reduc
));
1879 /* Build new RHS using selected condition and arguments. */
1880 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1882 new_stmt
= gimple_build_assign (res
, rhs
);
1883 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1884 gimple_stmt_iterator new_gsi
= gsi_for_stmt (new_stmt
);
1885 if (fold_stmt (&new_gsi
, ifcvt_follow_ssa_use_edges
))
1887 new_stmt
= gsi_stmt (new_gsi
);
1888 update_stmt (new_stmt
);
1891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1893 fprintf (dump_file
, "new phi replacement stmt\n");
1894 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1899 /* Create hashmap for PHI node which contain vector of argument indexes
1900 having the same value. */
1902 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1903 unsigned int num_args
= gimple_phi_num_args (phi
);
1905 /* Vector of different PHI argument values. */
1906 auto_vec
<tree
> args (num_args
);
1908 /* Compute phi_arg_map. */
1909 for (i
= 0; i
< num_args
; i
++)
1913 arg
= gimple_phi_arg_def (phi
, i
);
1914 if (!phi_arg_map
.get (arg
))
1915 args
.quick_push (arg
);
1916 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1919 /* Determine element with max number of occurrences. */
1922 args_len
= args
.length ();
1923 for (i
= 0; i
< args_len
; i
++)
1926 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1933 /* Put element with max number of occurences to the end of ARGS. */
1934 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1935 std::swap (args
[args_len
- 1], args
[max_ind
]);
1937 /* Handle one special case when number of arguments with different values
1938 is equal 2 and one argument has the only occurrence. Such PHI can be
1939 handled as if would have only 2 arguments. */
1940 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1943 indexes
= phi_arg_map
.get (args
[0]);
1944 index0
= (*indexes
)[0];
1947 e
= gimple_phi_arg_edge (phi
, index0
);
1948 cond
= bb_predicate (e
->src
);
1949 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1952 cond
= TREE_OPERAND (cond
, 0);
1954 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1955 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1956 is_gimple_condexpr
, NULL_TREE
,
1957 true, GSI_SAME_STMT
);
1958 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1960 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1964 /* Convert reduction stmt into vectorizable form. */
1965 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1967 new_stmt
= gimple_build_assign (res
, rhs
);
1968 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1969 update_stmt (new_stmt
);
1975 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1978 for (i
= 0; i
< args_len
; i
++)
1981 indexes
= phi_arg_map
.get (args
[i
]);
1982 if (i
!= args_len
- 1)
1983 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1986 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1987 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1989 new_stmt
= gimple_build_assign (lhs
, rhs
);
1990 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1991 update_stmt (new_stmt
);
1996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1998 fprintf (dump_file
, "new extended phi replacement stmt\n");
1999 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
2003 /* Replaces in LOOP all the scalar phi nodes other than those in the
2004 LOOP->header block with conditional modify expressions. */
2007 predicate_all_scalar_phis (struct loop
*loop
)
2010 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2013 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2016 gimple_stmt_iterator gsi
;
2017 gphi_iterator phi_gsi
;
2020 if (bb
== loop
->header
)
2023 phi_gsi
= gsi_start_phis (bb
);
2024 if (gsi_end_p (phi_gsi
))
2027 gsi
= gsi_after_labels (bb
);
2028 while (!gsi_end_p (phi_gsi
))
2030 phi
= phi_gsi
.phi ();
2031 if (virtual_operand_p (gimple_phi_result (phi
)))
2032 gsi_next (&phi_gsi
);
2035 predicate_scalar_phi (phi
, &gsi
);
2036 remove_phi_node (&phi_gsi
, false);
2042 /* Insert in each basic block of LOOP the statements produced by the
2043 gimplification of the predicates. */
2046 insert_gimplified_predicates (loop_p loop
)
2050 for (i
= 0; i
< loop
->num_nodes
; i
++)
2052 basic_block bb
= ifc_bbs
[i
];
2054 if (!is_predicated (bb
))
2055 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
2056 if (!is_predicated (bb
))
2058 /* Do not insert statements for a basic block that is not
2059 predicated. Also make sure that the predicate of the
2060 basic block is set to true. */
2061 reset_bb_predicate (bb
);
2065 stmts
= bb_predicate_gimplified_stmts (bb
);
2068 if (need_to_predicate
)
2070 /* Insert the predicate of the BB just after the label,
2071 as the if-conversion of memory writes will use this
2073 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2074 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2078 /* Insert the predicate of the BB at the end of the BB
2079 as this would reduce the register pressure: the only
2080 use of this predicate will be in successor BBs. */
2081 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2084 || stmt_ends_bb_p (gsi_stmt (gsi
)))
2085 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2087 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
2090 /* Once the sequence is code generated, set it to NULL. */
2091 set_bb_predicate_gimplified_stmts (bb
, NULL
);
2096 /* Helper function for predicate_statements. Returns index of existent
2097 mask if it was created for given SIZE and -1 otherwise. */
2100 mask_exists (int size
, vec
<int> vec
)
2104 FOR_EACH_VEC_ELT (vec
, ix
, v
)
2110 /* Helper function for predicate_statements. STMT is a memory read or
2111 write and it needs to be predicated by MASK. Return a statement
2115 predicate_load_or_store (gimple_stmt_iterator
*gsi
, gassign
*stmt
, tree mask
)
2119 tree lhs
= gimple_assign_lhs (stmt
);
2120 tree rhs
= gimple_assign_rhs1 (stmt
);
2121 tree ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2122 mark_addressable (ref
);
2123 tree addr
= force_gimple_operand_gsi (gsi
, build_fold_addr_expr (ref
),
2124 true, NULL_TREE
, true, GSI_SAME_STMT
);
2125 tree ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2126 get_object_alignment (ref
));
2127 /* Copy points-to info if possible. */
2128 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2129 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2131 if (TREE_CODE (lhs
) == SSA_NAME
)
2134 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2136 gimple_call_set_lhs (new_stmt
, lhs
);
2137 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2142 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2144 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2145 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
2146 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt
)) = new_stmt
;
2148 gimple_call_set_nothrow (new_stmt
, true);
2152 /* STMT uses OP_LHS. Check whether it is equivalent to:
2154 ... = OP_MASK ? OP_LHS : X;
2156 Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2157 known to have value OP_COND. */
2160 check_redundant_cond_expr (gimple
*stmt
, tree op_mask
, tree op_cond
,
2163 gassign
*assign
= dyn_cast
<gassign
*> (stmt
);
2164 if (!assign
|| gimple_assign_rhs_code (assign
) != COND_EXPR
)
2167 tree use_cond
= gimple_assign_rhs1 (assign
);
2168 tree if_true
= gimple_assign_rhs2 (assign
);
2169 tree if_false
= gimple_assign_rhs3 (assign
);
2171 if ((use_cond
== op_mask
|| operand_equal_p (use_cond
, op_cond
, 0))
2172 && if_true
== op_lhs
)
2175 if (inverse_conditions_p (use_cond
, op_cond
) && if_false
== op_lhs
)
2181 /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2182 the set of SSA names defined earlier in STMT's block. */
2185 value_available_p (gimple
*stmt
, hash_set
<tree_ssa_name_hash
> *ssa_names
,
2188 if (is_gimple_min_invariant (value
))
2191 if (TREE_CODE (value
) == SSA_NAME
)
2193 if (SSA_NAME_IS_DEFAULT_DEF (value
))
2196 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (value
));
2197 basic_block use_bb
= gimple_bb (stmt
);
2198 return (def_bb
== use_bb
2199 ? ssa_names
->contains (value
)
2200 : dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
));
2206 /* Helper function for predicate_statements. STMT is a potentially-trapping
2207 arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2208 has value COND. Return a statement that does so. SSA_NAMES is the set of
2209 SSA names defined earlier in STMT's block. */
2212 predicate_rhs_code (gassign
*stmt
, tree mask
, tree cond
,
2213 hash_set
<tree_ssa_name_hash
> *ssa_names
)
2215 tree lhs
= gimple_assign_lhs (stmt
);
2216 tree_code code
= gimple_assign_rhs_code (stmt
);
2217 unsigned int nops
= gimple_num_ops (stmt
);
2218 internal_fn cond_fn
= get_conditional_internal_fn (code
);
2220 /* Construct the arguments to the conditional internal function. */
2221 auto_vec
<tree
, 8> args
;
2222 args
.safe_grow (nops
+ 1);
2224 for (unsigned int i
= 1; i
< nops
; ++i
)
2225 args
[i
] = gimple_op (stmt
, i
);
2226 args
[nops
] = NULL_TREE
;
2228 /* Look for uses of the result to see whether they are COND_EXPRs that can
2229 be folded into the conditional call. */
2230 imm_use_iterator imm_iter
;
2232 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, lhs
)
2234 tree new_else
= check_redundant_cond_expr (use_stmt
, mask
, cond
, lhs
);
2235 if (new_else
&& value_available_p (stmt
, ssa_names
, new_else
))
2238 args
[nops
] = new_else
;
2239 if (operand_equal_p (new_else
, args
[nops
], 0))
2243 LHS = IFN_COND (MASK, ..., ELSE);
2244 X = MASK ? LHS : ELSE;
2246 which makes X equivalent to LHS. */
2247 tree use_lhs
= gimple_assign_lhs (use_stmt
);
2248 redundant_ssa_names
.safe_push (std::make_pair (use_lhs
, lhs
));
2253 args
[nops
] = targetm
.preferred_else_value (cond_fn
, TREE_TYPE (lhs
),
2254 nops
- 1, &args
[1]);
2256 /* Create and insert the call. */
2257 gcall
*new_stmt
= gimple_build_call_internal_vec (cond_fn
, args
);
2258 gimple_call_set_lhs (new_stmt
, lhs
);
2259 gimple_call_set_nothrow (new_stmt
, true);
2264 /* Predicate each write to memory in LOOP.
2266 This function transforms control flow constructs containing memory
2269 | for (i = 0; i < N; i++)
2273 into the following form that does not contain control flow:
2275 | for (i = 0; i < N; i++)
2276 | A[i] = cond ? expr : A[i];
2278 The original CFG looks like this:
2285 | if (i < N) goto bb_5 else goto bb_2
2289 | cond = some_computation;
2290 | if (cond) goto bb_3 else goto bb_4
2302 insert_gimplified_predicates inserts the computation of the COND
2303 expression at the beginning of the destination basic block:
2310 | if (i < N) goto bb_5 else goto bb_2
2314 | cond = some_computation;
2315 | if (cond) goto bb_3 else goto bb_4
2319 | cond = some_computation;
2328 predicate_statements is then predicating the memory write as follows:
2335 | if (i < N) goto bb_5 else goto bb_2
2339 | if (cond) goto bb_3 else goto bb_4
2343 | cond = some_computation;
2344 | A[i] = cond ? expr : A[i];
2352 and finally combine_blocks removes the basic block boundaries making
2353 the loop vectorizable:
2357 | if (i < N) goto bb_5 else goto bb_1
2361 | cond = some_computation;
2362 | A[i] = cond ? expr : A[i];
2363 | if (i < N) goto bb_5 else goto bb_4
2372 predicate_statements (loop_p loop
)
2374 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2375 auto_vec
<int, 1> vect_sizes
;
2376 auto_vec
<tree
, 1> vect_masks
;
2377 hash_set
<tree_ssa_name_hash
> ssa_names
;
2379 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2381 gimple_stmt_iterator gsi
;
2382 basic_block bb
= ifc_bbs
[i
];
2383 tree cond
= bb_predicate (bb
);
2387 if (is_true_predicate (cond
))
2391 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2394 cond
= TREE_OPERAND (cond
, 0);
2397 vect_sizes
.truncate (0);
2398 vect_masks
.truncate (0);
2400 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
2402 gassign
*stmt
= dyn_cast
<gassign
*> (gsi_stmt (gsi
));
2405 else if (is_false_predicate (cond
)
2406 && gimple_vdef (stmt
))
2408 unlink_stmt_vdef (stmt
);
2409 gsi_remove (&gsi
, true);
2410 release_defs (stmt
);
2413 else if (gimple_plf (stmt
, GF_PLF_2
))
2415 tree lhs
= gimple_assign_lhs (stmt
);
2418 gimple_seq stmts
= NULL
;
2419 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
2420 /* We checked before setting GF_PLF_2 that an equivalent
2421 integer mode exists. */
2422 int bitsize
= GET_MODE_BITSIZE (mode
).to_constant ();
2423 if (!vect_sizes
.is_empty ()
2424 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2425 /* Use created mask. */
2426 mask
= vect_masks
[index
];
2429 if (COMPARISON_CLASS_P (cond
))
2430 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2432 TREE_OPERAND (cond
, 0),
2433 TREE_OPERAND (cond
, 1));
2440 = constant_boolean_node (true, TREE_TYPE (mask
));
2441 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2442 TREE_TYPE (mask
), mask
, true_val
);
2444 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2446 /* Save mask and its size for further use. */
2447 vect_sizes
.safe_push (bitsize
);
2448 vect_masks
.safe_push (mask
);
2450 if (gimple_assign_single_p (stmt
))
2451 new_stmt
= predicate_load_or_store (&gsi
, stmt
, mask
);
2453 new_stmt
= predicate_rhs_code (stmt
, mask
, cond
, &ssa_names
);
2455 gsi_replace (&gsi
, new_stmt
, true);
2457 else if (gimple_vdef (stmt
))
2459 tree lhs
= gimple_assign_lhs (stmt
);
2460 tree rhs
= gimple_assign_rhs1 (stmt
);
2461 tree type
= TREE_TYPE (lhs
);
2463 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2464 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2466 std::swap (lhs
, rhs
);
2467 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2468 is_gimple_condexpr
, NULL_TREE
,
2469 true, GSI_SAME_STMT
);
2470 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2471 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2474 tree lhs
= gimple_get_lhs (gsi_stmt (gsi
));
2475 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
2476 ssa_names
.add (lhs
);
2483 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2484 other than the exit and latch of the LOOP. Also resets the
2485 GIMPLE_DEBUG information. */
2488 remove_conditions_and_labels (loop_p loop
)
2490 gimple_stmt_iterator gsi
;
2493 for (i
= 0; i
< loop
->num_nodes
; i
++)
2495 basic_block bb
= ifc_bbs
[i
];
2497 if (bb_with_exit_edge_p (loop
, bb
)
2498 || bb
== loop
->latch
)
2501 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2502 switch (gimple_code (gsi_stmt (gsi
)))
2506 gsi_remove (&gsi
, true);
2510 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2511 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2513 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2514 update_stmt (gsi_stmt (gsi
));
2525 /* Combine all the basic blocks from LOOP into one or two super basic
2526 blocks. Replace PHI nodes with conditional modify expressions. */
2529 combine_blocks (struct loop
*loop
)
2531 basic_block bb
, exit_bb
, merge_target_bb
;
2532 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2537 remove_conditions_and_labels (loop
);
2538 insert_gimplified_predicates (loop
);
2539 predicate_all_scalar_phis (loop
);
2541 if (need_to_predicate
)
2542 predicate_statements (loop
);
2544 /* Merge basic blocks: first remove all the edges in the loop,
2545 except for those from the exit block. */
2547 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2548 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2551 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2552 free_bb_predicate (bb
);
2553 if (bb_with_exit_edge_p (loop
, bb
))
2555 gcc_assert (exit_bb
== NULL
);
2559 gcc_assert (exit_bb
!= loop
->latch
);
2561 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2565 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2567 if (e
->src
== exit_bb
)
2574 if (exit_bb
!= NULL
)
2576 if (exit_bb
!= loop
->header
)
2578 /* Connect this node to loop header. */
2579 make_single_succ_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2580 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2583 /* Redirect non-exit edges to loop->latch. */
2584 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2586 if (!loop_exit_edge_p (loop
, e
))
2587 redirect_edge_and_branch (e
, loop
->latch
);
2589 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2593 /* If the loop does not have an exit, reconnect header and latch. */
2594 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2595 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2598 merge_target_bb
= loop
->header
;
2600 /* Get at the virtual def valid for uses starting at the first block
2601 we merge into the header. Without a virtual PHI the loop has the
2602 same virtual use on all stmts. */
2603 gphi
*vphi
= get_virtual_phi (loop
->header
);
2604 tree last_vdef
= NULL_TREE
;
2607 last_vdef
= gimple_phi_result (vphi
);
2608 for (gimple_stmt_iterator gsi
= gsi_start_bb (loop
->header
);
2609 ! gsi_end_p (gsi
); gsi_next (&gsi
))
2610 if (gimple_vdef (gsi_stmt (gsi
)))
2611 last_vdef
= gimple_vdef (gsi_stmt (gsi
));
2613 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2615 gimple_stmt_iterator gsi
;
2616 gimple_stmt_iterator last
;
2620 if (bb
== exit_bb
|| bb
== loop
->latch
)
2623 /* We release virtual PHIs late because we have to propagate them
2624 out using the current VUSE. The def might be the one used
2626 vphi
= get_virtual_phi (bb
);
2629 imm_use_iterator iter
;
2630 use_operand_p use_p
;
2632 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, gimple_phi_result (vphi
))
2634 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2635 SET_USE (use_p
, last_vdef
);
2637 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi
)))
2638 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef
) = 1;
2639 gsi
= gsi_for_stmt (vphi
);
2640 remove_phi_node (&gsi
, true);
2643 /* Make stmts member of loop->header and clear range info from all stmts
2644 in BB which is now no longer executed conditional on a predicate we
2645 could have derived it from. */
2646 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2648 gimple
*stmt
= gsi_stmt (gsi
);
2649 gimple_set_bb (stmt
, merge_target_bb
);
2650 /* Update virtual operands. */
2653 use_operand_p use_p
= ssa_vuse_operand (stmt
);
2655 && USE_FROM_PTR (use_p
) != last_vdef
)
2656 SET_USE (use_p
, last_vdef
);
2657 if (gimple_vdef (stmt
))
2658 last_vdef
= gimple_vdef (stmt
);
2664 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2665 reset_flow_sensitive_info (op
);
2669 /* Update stmt list. */
2670 last
= gsi_last_bb (merge_target_bb
);
2671 gsi_insert_seq_after_without_update (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2672 set_bb_seq (bb
, NULL
);
2674 delete_basic_block (bb
);
2677 /* If possible, merge loop header to the block with the exit edge.
2678 This reduces the number of basic blocks to two, to please the
2679 vectorizer that handles only loops with two nodes. */
2681 && exit_bb
!= loop
->header
)
2683 /* We release virtual PHIs late because we have to propagate them
2684 out using the current VUSE. The def might be the one used
2686 vphi
= get_virtual_phi (exit_bb
);
2689 imm_use_iterator iter
;
2690 use_operand_p use_p
;
2692 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, gimple_phi_result (vphi
))
2694 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2695 SET_USE (use_p
, last_vdef
);
2697 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi
)))
2698 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef
) = 1;
2699 gimple_stmt_iterator gsi
= gsi_for_stmt (vphi
);
2700 remove_phi_node (&gsi
, true);
2703 if (can_merge_blocks_p (loop
->header
, exit_bb
))
2704 merge_blocks (loop
->header
, exit_bb
);
2712 /* Version LOOP before if-converting it; the original loop
2713 will be if-converted, the new copy of the loop will not,
2714 and the LOOP_VECTORIZED internal call will be guarding which
2715 loop to execute. The vectorizer pass will fold this
2716 internal call into either true or false.
2718 Note that this function intentionally invalidates profile. Both edges
2719 out of LOOP_VECTORIZED must have 100% probability so the profile remains
2720 consistent after the condition is folded in the vectorizer. */
2722 static struct loop
*
2723 version_loop_for_if_conversion (struct loop
*loop
, vec
<gimple
*> *preds
)
2725 basic_block cond_bb
;
2726 tree cond
= make_ssa_name (boolean_type_node
);
2727 struct loop
*new_loop
;
2729 gimple_stmt_iterator gsi
;
2730 unsigned int save_length
;
2732 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2733 build_int_cst (integer_type_node
, loop
->num
),
2735 gimple_call_set_lhs (g
, cond
);
2737 /* Save BB->aux around loop_version as that uses the same field. */
2738 save_length
= loop
->inner
? loop
->inner
->num_nodes
: loop
->num_nodes
;
2739 void **saved_preds
= XALLOCAVEC (void *, save_length
);
2740 for (unsigned i
= 0; i
< save_length
; i
++)
2741 saved_preds
[i
] = ifc_bbs
[i
]->aux
;
2743 initialize_original_copy_tables ();
2744 /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
2745 is re-merged in the vectorizer. */
2746 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2747 profile_probability::always (),
2748 profile_probability::always (),
2749 profile_probability::always (),
2750 profile_probability::always (), true);
2751 free_original_copy_tables ();
2753 for (unsigned i
= 0; i
< save_length
; i
++)
2754 ifc_bbs
[i
]->aux
= saved_preds
[i
];
2756 if (new_loop
== NULL
)
2759 new_loop
->dont_vectorize
= true;
2760 new_loop
->force_vectorize
= false;
2761 gsi
= gsi_last_bb (cond_bb
);
2762 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2764 preds
->safe_push (g
);
2765 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2766 update_ssa (TODO_update_ssa
);
2770 /* Return true when LOOP satisfies the follow conditions that will
2771 allow it to be recognized by the vectorizer for outer-loop
2773 - The loop is not the root node of the loop tree.
2774 - The loop has exactly one inner loop.
2775 - The loop has a single exit.
2776 - The loop header has a single successor, which is the inner
2778 - Each of the inner and outer loop latches have a single
2780 - The loop exit block has a single predecessor, which is the
2781 inner loop's exit block. */
2784 versionable_outer_loop_p (struct loop
*loop
)
2786 if (!loop_outer (loop
)
2787 || loop
->dont_vectorize
2789 || loop
->inner
->next
2790 || !single_exit (loop
)
2791 || !single_succ_p (loop
->header
)
2792 || single_succ (loop
->header
) != loop
->inner
->header
2793 || !single_pred_p (loop
->latch
)
2794 || !single_pred_p (loop
->inner
->latch
))
2797 basic_block outer_exit
= single_pred (loop
->latch
);
2798 basic_block inner_exit
= single_pred (loop
->inner
->latch
);
2800 if (!single_pred_p (outer_exit
) || single_pred (outer_exit
) != inner_exit
)
2804 fprintf (dump_file
, "Found vectorizable outer loop for versioning\n");
2809 /* Performs splitting of critical edges. Skip splitting and return false
2810 if LOOP will not be converted because:
2812 - LOOP is not well formed.
2813 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
2815 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
2818 ifcvt_split_critical_edges (struct loop
*loop
, bool aggressive_if_conv
)
2822 unsigned int num
= loop
->num_nodes
;
2827 auto_vec
<edge
> critical_edges
;
2829 /* Loop is not well formed. */
2830 if (num
<= 2 || loop
->inner
|| !single_exit (loop
))
2833 body
= get_loop_body (loop
);
2834 for (i
= 0; i
< num
; i
++)
2837 if (!aggressive_if_conv
2839 && EDGE_COUNT (bb
->preds
) > MAX_PHI_ARG_NUM
)
2841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2843 "BB %d has complicated PHI with more than %u args.\n",
2844 bb
->index
, MAX_PHI_ARG_NUM
);
2849 if (bb
== loop
->latch
|| bb_with_exit_edge_p (loop
, bb
))
2852 stmt
= last_stmt (bb
);
2853 /* Skip basic blocks not ending with conditional branch. */
2854 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2857 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2858 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2859 critical_edges
.safe_push (e
);
2863 while (critical_edges
.length () > 0)
2865 e
= critical_edges
.pop ();
2866 /* Don't split if bb can be predicated along non-critical edge. */
2867 if (EDGE_COUNT (e
->dest
->preds
) > 2 || all_preds_critical_p (e
->dest
))
2874 /* Delete redundant statements produced by predication which prevents
2875 loop vectorization. */
2878 ifcvt_local_dce (basic_block bb
)
2883 gimple_stmt_iterator gsi
;
2884 auto_vec
<gimple
*> worklist
;
2885 enum gimple_code code
;
2886 use_operand_p use_p
;
2887 imm_use_iterator imm_iter
;
2888 std::pair
<tree
, tree
> *name_pair
;
2891 FOR_EACH_VEC_ELT (redundant_ssa_names
, i
, name_pair
)
2892 replace_uses_by (name_pair
->first
, name_pair
->second
);
2893 redundant_ssa_names
.release ();
2895 worklist
.create (64);
2896 /* Consider all phi as live statements. */
2897 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2899 phi
= gsi_stmt (gsi
);
2900 gimple_set_plf (phi
, GF_PLF_2
, true);
2901 worklist
.safe_push (phi
);
2903 /* Consider load/store statements, CALL and COND as live. */
2904 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2906 stmt
= gsi_stmt (gsi
);
2907 if (gimple_store_p (stmt
)
2908 || gimple_assign_load_p (stmt
)
2909 || is_gimple_debug (stmt
))
2911 gimple_set_plf (stmt
, GF_PLF_2
, true);
2912 worklist
.safe_push (stmt
);
2915 code
= gimple_code (stmt
);
2916 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2918 gimple_set_plf (stmt
, GF_PLF_2
, true);
2919 worklist
.safe_push (stmt
);
2922 gimple_set_plf (stmt
, GF_PLF_2
, false);
2924 if (code
== GIMPLE_ASSIGN
)
2926 tree lhs
= gimple_assign_lhs (stmt
);
2927 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2929 stmt1
= USE_STMT (use_p
);
2930 if (gimple_bb (stmt1
) != bb
)
2932 gimple_set_plf (stmt
, GF_PLF_2
, true);
2933 worklist
.safe_push (stmt
);
2939 /* Propagate liveness through arguments of live stmt. */
2940 while (worklist
.length () > 0)
2943 use_operand_p use_p
;
2946 stmt
= worklist
.pop ();
2947 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2949 use
= USE_FROM_PTR (use_p
);
2950 if (TREE_CODE (use
) != SSA_NAME
)
2952 stmt1
= SSA_NAME_DEF_STMT (use
);
2953 if (gimple_bb (stmt1
) != bb
2954 || gimple_plf (stmt1
, GF_PLF_2
))
2956 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2957 worklist
.safe_push (stmt1
);
2960 /* Delete dead statements. */
2961 gsi
= gsi_start_bb (bb
);
2962 while (!gsi_end_p (gsi
))
2964 stmt
= gsi_stmt (gsi
);
2965 if (gimple_plf (stmt
, GF_PLF_2
))
2970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2972 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2973 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2975 gsi_remove (&gsi
, true);
2976 release_defs (stmt
);
2980 /* If-convert LOOP when it is legal. For the moment this pass has no
2981 profitability analysis. Returns non-zero todo flags when something
2985 tree_if_conversion (struct loop
*loop
, vec
<gimple
*> *preds
)
2987 unsigned int todo
= 0;
2988 bool aggressive_if_conv
;
2995 need_to_predicate
= false;
2996 any_complicated_phi
= false;
2998 /* Apply more aggressive if-conversion when loop or its outer loop were
2999 marked with simd pragma. When that's the case, we try to if-convert
3000 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
3001 aggressive_if_conv
= loop
->force_vectorize
;
3002 if (!aggressive_if_conv
)
3004 struct loop
*outer_loop
= loop_outer (loop
);
3005 if (outer_loop
&& outer_loop
->force_vectorize
)
3006 aggressive_if_conv
= true;
3009 if (!ifcvt_split_critical_edges (loop
, aggressive_if_conv
))
3012 if (!if_convertible_loop_p (loop
)
3013 || !dbg_cnt (if_conversion_tree
))
3016 if ((need_to_predicate
|| any_complicated_phi
)
3017 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
3018 || loop
->dont_vectorize
))
3021 /* Since we have no cost model, always version loops unless the user
3022 specified -ftree-loop-if-convert or unless versioning is required.
3023 Either version this loop, or if the pattern is right for outer-loop
3024 vectorization, version the outer loop. In the latter case we will
3025 still if-convert the original inner loop. */
3026 if (need_to_predicate
3027 || any_complicated_phi
3028 || flag_tree_loop_if_convert
!= 1)
3031 = (versionable_outer_loop_p (loop_outer (loop
))
3032 ? loop_outer (loop
) : loop
);
3033 struct loop
*nloop
= version_loop_for_if_conversion (vloop
, preds
);
3038 /* If versionable_outer_loop_p decided to version the
3039 outer loop, version also the inner loop of the non-vectorized
3040 loop copy. So we transform:
3044 if (LOOP_VECTORIZED (1, 3))
3050 loop3 (copy of loop1)
3051 if (LOOP_VECTORIZED (4, 5))
3052 loop4 (copy of loop2)
3054 loop5 (copy of loop4) */
3055 gcc_assert (nloop
->inner
&& nloop
->inner
->next
== NULL
);
3056 rloop
= nloop
->inner
;
3060 /* Now all statements are if-convertible. Combine all the basic
3061 blocks into one huge basic block doing the if-conversion
3063 combine_blocks (loop
);
3065 /* Delete dead predicate computations. */
3066 ifcvt_local_dce (loop
->header
);
3068 /* Perform local CSE, this esp. helps the vectorizer analysis if loads
3069 and stores are involved. CSE only the loop body, not the entry
3070 PHIs, those are to be kept in sync with the non-if-converted copy.
3071 ??? We'll still keep dead stores though. */
3072 exit_bbs
= BITMAP_ALLOC (NULL
);
3073 bitmap_set_bit (exit_bbs
, single_exit (loop
)->dest
->index
);
3074 bitmap_set_bit (exit_bbs
, loop
->latch
->index
);
3075 todo
|= do_rpo_vn (cfun
, loop_preheader_edge (loop
), exit_bbs
);
3076 BITMAP_FREE (exit_bbs
);
3078 todo
|= TODO_cleanup_cfg
;
3085 for (i
= 0; i
< loop
->num_nodes
; i
++)
3086 free_bb_predicate (ifc_bbs
[i
]);
3100 /* Tree if-conversion pass management. */
3104 const pass_data pass_data_if_conversion
=
3106 GIMPLE_PASS
, /* type */
3108 OPTGROUP_NONE
, /* optinfo_flags */
3109 TV_TREE_LOOP_IFCVT
, /* tv_id */
3110 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3111 0, /* properties_provided */
3112 0, /* properties_destroyed */
3113 0, /* todo_flags_start */
3114 0, /* todo_flags_finish */
3117 class pass_if_conversion
: public gimple_opt_pass
3120 pass_if_conversion (gcc::context
*ctxt
)
3121 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
3124 /* opt_pass methods: */
3125 virtual bool gate (function
*);
3126 virtual unsigned int execute (function
*);
3128 }; // class pass_if_conversion
3131 pass_if_conversion::gate (function
*fun
)
3133 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
3134 && flag_tree_loop_if_convert
!= 0)
3135 || flag_tree_loop_if_convert
== 1);
3139 pass_if_conversion::execute (function
*fun
)
3144 if (number_of_loops (fun
) <= 1)
3147 auto_vec
<gimple
*> preds
;
3148 FOR_EACH_LOOP (loop
, 0)
3149 if (flag_tree_loop_if_convert
== 1
3150 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
3151 && !loop
->dont_vectorize
))
3152 todo
|= tree_if_conversion (loop
, &preds
);
3156 free_numbers_of_iterations_estimates (fun
);
3163 FOR_EACH_BB_FN (bb
, fun
)
3164 gcc_assert (!bb
->aux
);
3167 /* Perform IL update now, it might elide some loops. */
3168 if (todo
& TODO_cleanup_cfg
)
3170 cleanup_tree_cfg ();
3171 if (need_ssa_update_p (fun
))
3172 todo
|= TODO_update_ssa
;
3174 if (todo
& TODO_update_ssa_any
)
3175 update_ssa (todo
& TODO_update_ssa_any
);
3177 /* If if-conversion elided the loop fall back to the original one. */
3178 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3180 gimple
*g
= preds
[i
];
3183 unsigned ifcvt_loop
= tree_to_uhwi (gimple_call_arg (g
, 0));
3184 if (!get_loop (fun
, ifcvt_loop
))
3187 fprintf (dump_file
, "If-converted loop vanished\n");
3188 fold_loop_internal_call (g
, boolean_false_node
);
3198 make_pass_if_conversion (gcc::context
*ctxt
)
3200 return new pass_if_conversion (ctxt
);