1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2024 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"
95 #include "optabs-tree.h"
96 #include "gimple-pretty-print.h"
98 #include "fold-const.h"
99 #include "stor-layout.h"
100 #include "gimple-iterator.h"
101 #include "gimple-fold.h"
102 #include "gimplify.h"
103 #include "gimplify-me.h"
104 #include "tree-cfg.h"
105 #include "tree-into-ssa.h"
106 #include "tree-ssa.h"
108 #include "tree-data-ref.h"
109 #include "tree-scalar-evolution.h"
110 #include "tree-ssa-loop.h"
111 #include "tree-ssa-loop-niter.h"
112 #include "tree-ssa-loop-ivopts.h"
113 #include "tree-ssa-address.h"
115 #include "tree-hash-traits.h"
117 #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"
124 #include "tree-vectorizer.h"
128 /* For lang_hooks.types.type_for_mode. */
129 #include "langhooks.h"
131 /* Only handle PHIs with no more arguments unless we are asked to by
133 #define MAX_PHI_ARG_NUM \
134 ((unsigned) param_max_tree_if_conversion_phi_args)
136 /* True if we've converted a statement that was only executed when some
137 condition C was true, and if for correctness we need to predicate the
138 statement to ensure that it is a no-op when C is false. See
139 predicate_statements for the kinds of predication we support. */
140 static bool need_to_predicate
;
142 /* True if we have to rewrite stmts that may invoke undefined behavior
143 when a condition C was false so it doesn't if it is always executed.
144 See predicate_statements for the kinds of predication we support. */
145 static bool need_to_rewrite_undefined
;
147 /* Indicate if there are any complicated PHIs that need to be handled in
148 if-conversion. Complicated PHI has more than two arguments and can't
149 be degenerated to two arguments PHI. See more information in comment
150 before phi_convertible_by_degenerating_args. */
151 static bool any_complicated_phi
;
153 /* True if we have bitfield accesses we can lower. */
154 static bool need_to_lower_bitfields
;
156 /* True if there is any ifcvting to be done. */
157 static bool need_to_ifcvt
;
159 /* Hash for struct innermost_loop_behavior. It depends on the user to
162 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
164 static inline hashval_t
hash (const value_type
&);
165 static inline bool equal (const value_type
&,
166 const compare_type
&);
170 innermost_loop_behavior_hash::hash (const value_type
&e
)
174 hash
= iterative_hash_expr (e
->base_address
, 0);
175 hash
= iterative_hash_expr (e
->offset
, hash
);
176 hash
= iterative_hash_expr (e
->init
, hash
);
177 return iterative_hash_expr (e
->step
, hash
);
181 innermost_loop_behavior_hash::equal (const value_type
&e1
,
182 const compare_type
&e2
)
184 if ((e1
->base_address
&& !e2
->base_address
)
185 || (!e1
->base_address
&& e2
->base_address
)
186 || (!e1
->offset
&& e2
->offset
)
187 || (e1
->offset
&& !e2
->offset
)
188 || (!e1
->init
&& e2
->init
)
189 || (e1
->init
&& !e2
->init
)
190 || (!e1
->step
&& e2
->step
)
191 || (e1
->step
&& !e2
->step
))
194 if (e1
->base_address
&& e2
->base_address
195 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
197 if (e1
->offset
&& e2
->offset
198 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
200 if (e1
->init
&& e2
->init
201 && !operand_equal_p (e1
->init
, e2
->init
, 0))
203 if (e1
->step
&& e2
->step
204 && !operand_equal_p (e1
->step
, e2
->step
, 0))
210 /* List of basic blocks in if-conversion-suitable order. */
211 static basic_block
*ifc_bbs
;
213 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
214 static hash_map
<innermost_loop_behavior_hash
,
215 data_reference_p
> *innermost_DR_map
;
217 /* Hash table to store <base reference, DR> pairs. */
218 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
220 /* List of redundant SSA names: the first should be replaced by the second. */
221 static vec
< std::pair
<tree
, tree
> > redundant_ssa_names
;
223 /* Structure used to predicate basic blocks. This is attached to the
224 ->aux field of the BBs in the loop to be if-converted. */
225 struct bb_predicate
{
227 /* The condition under which this basic block is executed. */
230 /* PREDICATE is gimplified, and the sequence of statements is
231 recorded here, in order to avoid the duplication of computations
232 that occur in previous conditions. See PR44483. */
233 gimple_seq predicate_gimplified_stmts
;
235 /* Records the number of statements recorded into
236 PREDICATE_GIMPLIFIED_STMTS. */
237 unsigned no_predicate_stmts
;
240 /* Returns true when the basic block BB has a predicate. */
243 bb_has_predicate (basic_block bb
)
245 return bb
->aux
!= NULL
;
248 /* Returns the gimplified predicate for basic block BB. */
251 bb_predicate (basic_block bb
)
253 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
256 /* Sets the gimplified predicate COND for basic block BB. */
259 set_bb_predicate (basic_block bb
, tree cond
)
261 auto aux
= (struct bb_predicate
*) bb
->aux
;
262 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
263 && is_gimple_val (TREE_OPERAND (cond
, 0)))
264 || is_gimple_val (cond
));
265 aux
->predicate
= cond
;
266 aux
->no_predicate_stmts
++;
268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
269 fprintf (dump_file
, "Recording block %d value %d\n", bb
->index
,
270 aux
->no_predicate_stmts
);
273 /* Returns the sequence of statements of the gimplification of the
274 predicate for basic block BB. */
276 static inline gimple_seq
277 bb_predicate_gimplified_stmts (basic_block bb
)
279 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
282 /* Sets the sequence of statements STMTS of the gimplification of the
283 predicate for basic block BB. If PRESERVE_COUNTS then don't clear the predicate
287 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
,
288 bool preserve_counts
)
290 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
291 if (stmts
== NULL
&& !preserve_counts
)
292 ((struct bb_predicate
*) bb
->aux
)->no_predicate_stmts
= 0;
295 /* Adds the sequence of statements STMTS to the sequence of statements
296 of the predicate for basic block BB. */
299 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
301 /* We might have updated some stmts in STMTS via force_gimple_operand
302 calling fold_stmt and that producing multiple stmts. Delink immediate
303 uses so update_ssa after loop versioning doesn't get confused for
304 the not yet inserted predicates.
305 ??? This should go away once we reliably avoid updating stmts
307 for (gimple_stmt_iterator gsi
= gsi_start (stmts
);
308 !gsi_end_p (gsi
); gsi_next (&gsi
))
310 gimple
*stmt
= gsi_stmt (gsi
);
311 delink_stmt_imm_use (stmt
);
312 gimple_set_modified (stmt
, true);
313 ((struct bb_predicate
*) bb
->aux
)->no_predicate_stmts
++;
315 gimple_seq_add_seq_without_update
316 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
319 /* Return the number of statements the predicate of the basic block consists
322 static inline unsigned
323 get_bb_num_predicate_stmts (basic_block bb
)
325 return ((struct bb_predicate
*) bb
->aux
)->no_predicate_stmts
;
328 /* Initializes to TRUE the predicate of basic block BB. */
331 init_bb_predicate (basic_block bb
)
333 bb
->aux
= XNEW (struct bb_predicate
);
334 set_bb_predicate_gimplified_stmts (bb
, NULL
, false);
335 set_bb_predicate (bb
, boolean_true_node
);
338 /* Release the SSA_NAMEs associated with the predicate of basic block BB. */
341 release_bb_predicate (basic_block bb
)
343 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
346 /* Ensure that these stmts haven't yet been added to a bb. */
348 for (gimple_stmt_iterator i
= gsi_start (stmts
);
349 !gsi_end_p (i
); gsi_next (&i
))
350 gcc_assert (! gimple_bb (gsi_stmt (i
)));
353 gimple_seq_discard (stmts
);
354 set_bb_predicate_gimplified_stmts (bb
, NULL
, false);
358 /* Free the predicate of basic block BB. */
361 free_bb_predicate (basic_block bb
)
363 if (!bb_has_predicate (bb
))
366 release_bb_predicate (bb
);
371 /* Reinitialize predicate of BB with the true predicate. */
374 reset_bb_predicate (basic_block bb
)
376 if (!bb_has_predicate (bb
))
377 init_bb_predicate (bb
);
380 release_bb_predicate (bb
);
381 set_bb_predicate (bb
, boolean_true_node
);
385 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
386 the expression EXPR. Inserts the statement created for this
387 computation before GSI and leaves the iterator GSI at the same
391 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
393 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
394 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
395 gimple_set_vuse (stmt
, gimple_vuse (gsi_stmt (*gsi
)));
396 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
400 /* Return true when COND is a false predicate. */
403 is_false_predicate (tree cond
)
405 return (cond
!= NULL_TREE
406 && (cond
== boolean_false_node
407 || integer_zerop (cond
)));
410 /* Return true when COND is a true predicate. */
413 is_true_predicate (tree cond
)
415 return (cond
== NULL_TREE
416 || cond
== boolean_true_node
417 || integer_onep (cond
));
420 /* Returns true when BB has a predicate that is not trivial: true or
424 is_predicated (basic_block bb
)
426 return !is_true_predicate (bb_predicate (bb
));
429 /* Parses the predicate COND and returns its comparison code and
430 operands OP0 and OP1. */
432 static enum tree_code
433 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
437 if (TREE_CODE (cond
) == SSA_NAME
438 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
440 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
442 *op0
= gimple_assign_rhs1 (s
);
443 *op1
= gimple_assign_rhs2 (s
);
444 return gimple_assign_rhs_code (s
);
447 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
449 tree op
= gimple_assign_rhs1 (s
);
450 tree type
= TREE_TYPE (op
);
451 enum tree_code code
= parse_predicate (op
, op0
, op1
);
453 return code
== ERROR_MARK
? ERROR_MARK
454 : invert_tree_comparison (code
, HONOR_NANS (type
));
460 if (COMPARISON_CLASS_P (cond
))
462 *op0
= TREE_OPERAND (cond
, 0);
463 *op1
= TREE_OPERAND (cond
, 1);
464 return TREE_CODE (cond
);
470 /* Returns the fold of predicate C1 OR C2 at location LOC. */
473 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
475 tree op1a
, op1b
, op2a
, op2b
;
476 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
477 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
479 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
481 tree t
= maybe_fold_or_comparisons (boolean_type_node
, code1
, op1a
, op1b
,
487 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
490 /* Returns either a COND_EXPR or the folded expression if the folded
491 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
492 a constant or a SSA_NAME. */
495 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
497 /* If COND is comparison r != 0 and r has boolean type, convert COND
498 to SSA_NAME to accept by vect bool pattern. */
499 if (TREE_CODE (cond
) == NE_EXPR
)
501 tree op0
= TREE_OPERAND (cond
, 0);
502 tree op1
= TREE_OPERAND (cond
, 1);
503 if (TREE_CODE (op0
) == SSA_NAME
504 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
505 && (integer_zerop (op1
)))
509 gimple_match_op
cexpr (gimple_match_cond::UNCOND
, COND_EXPR
,
510 type
, cond
, rhs
, lhs
);
511 if (cexpr
.resimplify (NULL
, follow_all_ssa_edges
))
513 if (gimple_simplified_result_is_gimple_val (&cexpr
))
515 else if (cexpr
.code
== ABS_EXPR
)
516 return build1 (ABS_EXPR
, type
, cexpr
.ops
[0]);
517 else if (cexpr
.code
== MIN_EXPR
518 || cexpr
.code
== MAX_EXPR
)
519 return build2 ((tree_code
)cexpr
.code
, type
, cexpr
.ops
[0], cexpr
.ops
[1]);
522 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
525 /* Add condition NC to the predicate list of basic block BB. LOOP is
526 the loop to be if-converted. Use predicate of cd-equivalent block
527 for join bb if it exists: we call basic blocks bb1 and bb2
528 cd-equivalent if they are executed under the same condition. */
531 add_to_predicate_list (class loop
*loop
, basic_block bb
, tree nc
)
536 if (is_true_predicate (nc
))
539 /* If dominance tells us this basic block is always executed,
540 don't record any predicates for it. */
541 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
544 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
545 /* We use notion of cd equivalence to get simpler predicate for
546 join block, e.g. if join block has 2 predecessors with predicates
547 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
548 p1 & p2 | p1 & !p2. */
549 if (dom_bb
!= loop
->header
550 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
552 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
553 bc
= bb_predicate (dom_bb
);
554 if (!is_true_predicate (bc
))
555 set_bb_predicate (bb
, bc
);
557 gcc_assert (is_true_predicate (bb_predicate (bb
)));
558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
559 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
560 dom_bb
->index
, bb
->index
);
564 if (!is_predicated (bb
))
568 bc
= bb_predicate (bb
);
569 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
570 if (is_true_predicate (bc
))
572 reset_bb_predicate (bb
);
577 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
578 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
579 tp
= &TREE_OPERAND (bc
, 0);
582 if (!is_gimple_val (*tp
))
585 *tp
= force_gimple_operand (*tp
, &stmts
, true, NULL_TREE
);
586 add_bb_predicate_gimplified_stmts (bb
, stmts
);
588 set_bb_predicate (bb
, bc
);
591 /* Add the condition COND to the previous condition PREV_COND, and add
592 this to the predicate list of the destination of edge E. LOOP is
593 the loop to be if-converted. */
596 add_to_dst_predicate_list (class loop
*loop
, edge e
,
597 tree prev_cond
, tree cond
)
599 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
602 if (!is_true_predicate (prev_cond
))
603 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
606 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
607 add_to_predicate_list (loop
, e
->dest
, cond
);
610 /* Return true if one of the successor edges of BB exits LOOP. */
613 bb_with_exit_edge_p (const class loop
*loop
, basic_block bb
)
618 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
619 if (loop_exit_edge_p (loop
, e
))
625 /* Given PHI which has more than two arguments, this function checks if
626 it's if-convertible by degenerating its arguments. Specifically, if
627 below two conditions are satisfied:
629 1) Number of PHI arguments with different values equals to 2 and one
630 argument has the only occurrence.
631 2) The edge corresponding to the unique argument isn't critical edge.
633 Such PHI can be handled as PHIs have only two arguments. For example,
636 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
638 can be transformed into:
640 res = (predicate of e3) ? A_2 : A_1;
642 Return TRUE if it is the case, FALSE otherwise. */
645 phi_convertible_by_degenerating_args (gphi
*phi
)
648 tree arg
, t1
= NULL
, t2
= NULL
;
649 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
650 unsigned int num_args
= gimple_phi_num_args (phi
);
652 gcc_assert (num_args
> 2);
654 for (i
= 0; i
< num_args
; i
++)
656 arg
= gimple_phi_arg_def (phi
, i
);
657 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
663 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
673 if (n1
!= 1 && n2
!= 1)
676 /* Check if the edge corresponding to the unique arg is critical. */
677 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
678 if (EDGE_COUNT (e
->src
->succs
) > 1)
684 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
685 and it belongs to basic block BB. Note at this point, it is sure
686 that PHI is if-convertible. This function updates global variable
687 ANY_COMPLICATED_PHI if PHI is complicated. */
690 if_convertible_phi_p (class loop
*loop
, basic_block bb
, gphi
*phi
)
692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
694 fprintf (dump_file
, "-------------------------\n");
695 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
698 if (bb
!= loop
->header
699 && gimple_phi_num_args (phi
) > 2
700 && !phi_convertible_by_degenerating_args (phi
))
701 any_complicated_phi
= true;
706 /* Records the status of a data reference. This struct is attached to
707 each DR->aux field. */
710 bool rw_unconditionally
;
711 bool w_unconditionally
;
712 bool written_at_least_once
;
716 tree base_w_predicate
;
719 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
720 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
721 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
722 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
724 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
725 HASH tables. While storing them in HASH table, it checks if the
726 reference is unconditionally read or written and stores that as a flag
727 information. For base reference it checks if it is written atlest once
728 unconditionally and stores it as flag information along with DR.
729 In other words for every data reference A in STMT there exist other
730 accesses to a data reference with the same base with predicates that
731 add up (OR-up) to the true predicate: this ensures that the data
732 reference A is touched (read or written) on every iteration of the
733 if-converted loop. */
735 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
738 data_reference_p
*master_dr
, *base_master_dr
;
739 tree base_ref
= DR_BASE_OBJECT (a
);
740 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
741 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
744 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
750 IFC_DR (*master_dr
)->w_predicate
751 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
752 IFC_DR (*master_dr
)->w_predicate
);
753 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
754 DR_W_UNCONDITIONALLY (*master_dr
) = true;
756 IFC_DR (*master_dr
)->rw_predicate
757 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
758 IFC_DR (*master_dr
)->rw_predicate
);
759 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
760 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
764 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
767 IFC_DR (*base_master_dr
)->base_w_predicate
768 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
769 IFC_DR (*base_master_dr
)->base_w_predicate
);
770 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
771 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
775 /* Return TRUE if can prove the index IDX of an array reference REF is
776 within array bound. Return false otherwise. */
779 idx_within_array_bound (tree ref
, tree
*idx
, void *dta
)
781 wi::overflow_type overflow
;
782 widest_int niter
, valid_niter
, delta
, wi_step
;
785 class loop
*loop
= (class loop
*) dta
;
787 /* Only support within-bound access for array references. */
788 if (TREE_CODE (ref
) != ARRAY_REF
)
791 /* For arrays that might have flexible sizes, it is not guaranteed that they
792 do not extend over their declared size. */
793 if (array_ref_flexible_size_p (ref
))
796 ev
= analyze_scalar_evolution (loop
, *idx
);
797 ev
= instantiate_parameters (loop
, ev
);
798 init
= initial_condition (ev
);
799 step
= evolution_part_in_loop_num (ev
, loop
->num
);
801 if (!init
|| TREE_CODE (init
) != INTEGER_CST
802 || (step
&& TREE_CODE (step
) != INTEGER_CST
))
805 low
= array_ref_low_bound (ref
);
806 high
= array_ref_up_bound (ref
);
808 /* The case of nonconstant bounds could be handled, but it would be
810 if (TREE_CODE (low
) != INTEGER_CST
811 || !high
|| TREE_CODE (high
) != INTEGER_CST
)
814 /* Check if the intial idx is within bound. */
815 if (wi::to_widest (init
) < wi::to_widest (low
)
816 || wi::to_widest (init
) > wi::to_widest (high
))
819 /* The idx is always within bound. */
820 if (!step
|| integer_zerop (step
))
823 if (!max_loop_iterations (loop
, &niter
))
826 if (wi::to_widest (step
) < 0)
828 delta
= wi::to_widest (init
) - wi::to_widest (low
);
829 wi_step
= -wi::to_widest (step
);
833 delta
= wi::to_widest (high
) - wi::to_widest (init
);
834 wi_step
= wi::to_widest (step
);
837 valid_niter
= wi::div_floor (delta
, wi_step
, SIGNED
, &overflow
);
838 /* The iteration space of idx is within array bound. */
839 if (!overflow
&& niter
<= valid_niter
)
845 /* Return TRUE if ref is a within bound array reference. */
848 ref_within_array_bound (gimple
*stmt
, tree ref
)
850 class loop
*loop
= loop_containing_stmt (stmt
);
852 gcc_assert (loop
!= NULL
);
853 return for_each_index (&ref
, idx_within_array_bound
, loop
);
857 /* Given a memory reference expression T, return TRUE if base object
858 it refers to is writable. The base object of a memory reference
859 is the main object being referenced, which is returned by function
863 base_object_writable (tree ref
)
865 tree base_tree
= get_base_address (ref
);
868 && DECL_P (base_tree
)
869 && decl_binds_to_current_def_p (base_tree
)
870 && !TREE_READONLY (base_tree
));
873 /* Return true when the memory references of STMT won't trap in the
874 if-converted code. There are two things that we have to check for:
876 - writes to memory occur to writable memory: if-conversion of
877 memory writes transforms the conditional memory writes into
878 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
879 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
880 be executed at all in the original code, it may be a readonly
881 memory. To check that A is not const-qualified, we check that
882 there exists at least an unconditional write to A in the current
885 - reads or writes to memory are valid memory accesses for every
886 iteration. To check that the memory accesses are correctly formed
887 and that we are allowed to read and write in these locations, we
888 check that the memory accesses to be if-converted occur at every
889 iteration unconditionally.
891 Returns true for the memory reference in STMT, same memory reference
892 is read or written unconditionally atleast once and the base memory
893 reference is written unconditionally once. This is to check reference
894 will not write fault. Also retuns true if the memory reference is
895 unconditionally read once then we are conditionally writing to memory
896 which is defined as read and write and is bound to the definition
899 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
901 /* If DR didn't see a reference here we can't use it to tell
902 whether the ref traps or not. */
903 if (gimple_uid (stmt
) == 0)
906 data_reference_p
*master_dr
, *base_master_dr
;
907 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
909 tree base
= DR_BASE_OBJECT (a
);
910 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
912 gcc_assert (DR_STMT (a
) == stmt
);
913 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
914 || DR_INIT (a
) || DR_STEP (a
));
916 master_dr
= innermost_DR_map
->get (innermost
);
917 gcc_assert (master_dr
!= NULL
);
919 base_master_dr
= baseref_DR_map
->get (base
);
921 /* If a is unconditionally written to it doesn't trap. */
922 if (DR_W_UNCONDITIONALLY (*master_dr
))
925 /* If a is unconditionally accessed then ...
927 Even a is conditional access, we can treat it as an unconditional
928 one if it's an array reference and all its index are within array
930 if (DR_RW_UNCONDITIONALLY (*master_dr
)
931 || ref_within_array_bound (stmt
, DR_REF (a
)))
933 /* an unconditional read won't trap. */
937 /* an unconditionaly write won't trap if the base is written
938 to unconditionally. */
940 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
941 return flag_store_data_races
;
942 /* or the base is known to be not readonly. */
943 else if (base_object_writable (DR_REF (a
)))
944 return flag_store_data_races
;
950 /* Return true if STMT could be converted into a masked load or store
951 (conditional load or store based on a mask computed from bb predicate). */
954 ifcvt_can_use_mask_load_store (gimple
*stmt
)
956 /* Check whether this is a load or store. */
957 tree lhs
= gimple_assign_lhs (stmt
);
960 if (gimple_store_p (stmt
))
962 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
967 else if (gimple_assign_load_p (stmt
))
970 ref
= gimple_assign_rhs1 (stmt
);
975 if (may_be_nonaddressable_p (ref
))
978 /* Mask should be integer mode of the same size as the load/store
980 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
981 if (!int_mode_for_mode (mode
).exists () || VECTOR_MODE_P (mode
))
984 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
990 /* Return true if STMT could be converted from an operation that is
991 unconditional to one that is conditional on a bb predicate mask. */
994 ifcvt_can_predicate (gimple
*stmt
)
996 basic_block bb
= gimple_bb (stmt
);
998 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
999 || bb
->loop_father
->dont_vectorize
1000 || gimple_has_volatile_ops (stmt
))
1003 if (gimple_assign_single_p (stmt
))
1004 return ifcvt_can_use_mask_load_store (stmt
);
1006 tree_code code
= gimple_assign_rhs_code (stmt
);
1007 tree lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1008 tree rhs_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
1009 if (!types_compatible_p (lhs_type
, rhs_type
))
1011 internal_fn cond_fn
= get_conditional_internal_fn (code
);
1012 return (cond_fn
!= IFN_LAST
1013 && vectorized_internal_fn_supported_p (cond_fn
, lhs_type
));
1016 /* Return true when STMT is if-convertible.
1018 GIMPLE_ASSIGN statement is not if-convertible if,
1019 - it is not movable,
1021 - LHS is not var decl. */
1024 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
1025 vec
<data_reference_p
> refs
)
1027 tree lhs
= gimple_assign_lhs (stmt
);
1029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1031 fprintf (dump_file
, "-------------------------\n");
1032 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1035 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
1038 /* Some of these constrains might be too conservative. */
1039 if (stmt_ends_bb_p (stmt
)
1040 || gimple_has_volatile_ops (stmt
)
1041 || (TREE_CODE (lhs
) == SSA_NAME
1042 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1043 || gimple_has_side_effects (stmt
))
1045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1046 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
1050 /* tree-into-ssa.cc uses GF_PLF_1, so avoid it, because
1051 in between if_convertible_loop_p and combine_blocks
1052 we can perform loop versioning. */
1053 gimple_set_plf (stmt
, GF_PLF_2
, false);
1055 if ((! gimple_vuse (stmt
)
1056 || gimple_could_trap_p_1 (stmt
, false, false)
1057 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
1058 && gimple_could_trap_p (stmt
))
1060 if (ifcvt_can_predicate (stmt
))
1062 gimple_set_plf (stmt
, GF_PLF_2
, true);
1063 need_to_predicate
= true;
1066 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1067 fprintf (dump_file
, "tree could trap...\n");
1070 else if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
1071 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
1072 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs
))
1073 && arith_code_with_undefined_signed_overflow
1074 (gimple_assign_rhs_code (stmt
)))
1075 /* We have to rewrite stmts with undefined overflow. */
1076 need_to_rewrite_undefined
= true;
1078 /* When if-converting stores force versioning, likewise if we
1079 ended up generating store data races. */
1080 if (gimple_vdef (stmt
))
1081 need_to_predicate
= true;
1086 /* Return true when STMT is if-convertible.
1088 A statement is if-convertible if:
1089 - it is an if-convertible GIMPLE_ASSIGN,
1090 - it is a GIMPLE_LABEL or a GIMPLE_COND,
1091 - it is builtins call,
1092 - it is a call to a function with a SIMD clone. */
1095 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
1097 switch (gimple_code (stmt
))
1105 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
1109 /* There are some IFN_s that are used to replace builtins but have the
1110 same semantics. Even if MASK_CALL cannot handle them vectorable_call
1111 will insert the proper selection, so do not block conversion. */
1112 int flags
= gimple_call_flags (stmt
);
1113 if ((flags
& ECF_CONST
)
1114 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
1115 && gimple_call_combined_fn (stmt
) != CFN_LAST
)
1118 tree fndecl
= gimple_call_fndecl (stmt
);
1121 /* We can vectorize some builtins and functions with SIMD
1122 "inbranch" clones. */
1123 struct cgraph_node
*node
= cgraph_node::get (fndecl
);
1124 if (node
&& node
->simd_clones
!= NULL
)
1125 /* Ensure that at least one clone can be "inbranch". */
1126 for (struct cgraph_node
*n
= node
->simd_clones
; n
!= NULL
;
1127 n
= n
->simdclone
->next_clone
)
1128 if (n
->simdclone
->inbranch
)
1130 gimple_set_plf (stmt
, GF_PLF_2
, true);
1131 need_to_predicate
= true;
1140 /* Don't know what to do with 'em so don't do anything. */
1141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1143 fprintf (dump_file
, "don't know what to do\n");
1144 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1150 /* Assumes that BB has more than 1 predecessors.
1151 Returns false if at least one successor is not on critical edge
1152 and true otherwise. */
1155 all_preds_critical_p (basic_block bb
)
1160 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1161 if (EDGE_COUNT (e
->src
->succs
) == 1)
1166 /* Return true when BB is if-convertible. This routine does not check
1167 basic block's statements and phis.
1169 A basic block is not if-convertible if:
1170 - it is non-empty and it is after the exit block (in BFS order),
1171 - it is after the exit block but before the latch,
1172 - its edges are not normal.
1174 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1178 if_convertible_bb_p (class loop
*loop
, basic_block bb
, basic_block exit_bb
)
1183 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1184 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1186 if (EDGE_COUNT (bb
->succs
) > 2)
1189 if (gcall
*call
= safe_dyn_cast
<gcall
*> (*gsi_last_bb (bb
)))
1190 if (gimple_call_ctrl_altering_p (call
))
1195 if (bb
!= loop
->latch
)
1197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1198 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1201 else if (!empty_block_p (bb
))
1203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1204 fprintf (dump_file
, "non empty basic block after exit bb\n");
1207 else if (bb
== loop
->latch
1209 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1211 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1212 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1217 /* Be less adventurous and handle only normal edges. */
1218 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1219 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1221 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1222 fprintf (dump_file
, "Difficult to handle edges\n");
1229 /* Return true when all predecessor blocks of BB are visited. The
1230 VISITED bitmap keeps track of the visited blocks. */
1233 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1237 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1238 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1244 /* Get body of a LOOP in suitable order for if-conversion. It is
1245 caller's responsibility to deallocate basic block list.
1246 If-conversion suitable order is, breadth first sort (BFS) order
1247 with an additional constraint: select a block only if all its
1248 predecessors are already selected. */
1250 static basic_block
*
1251 get_loop_body_in_if_conv_order (const class loop
*loop
)
1253 basic_block
*blocks
, *blocks_in_bfs_order
;
1256 unsigned int index
= 0;
1257 unsigned int visited_count
= 0;
1259 gcc_assert (loop
->num_nodes
);
1260 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1262 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1263 visited
= BITMAP_ALLOC (NULL
);
1265 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1268 while (index
< loop
->num_nodes
)
1270 bb
= blocks_in_bfs_order
[index
];
1272 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1274 free (blocks_in_bfs_order
);
1275 BITMAP_FREE (visited
);
1280 if (!bitmap_bit_p (visited
, bb
->index
))
1282 if (pred_blocks_visited_p (bb
, &visited
)
1283 || bb
== loop
->header
)
1285 /* This block is now visited. */
1286 bitmap_set_bit (visited
, bb
->index
);
1287 blocks
[visited_count
++] = bb
;
1293 if (index
== loop
->num_nodes
1294 && visited_count
!= loop
->num_nodes
)
1298 free (blocks_in_bfs_order
);
1299 BITMAP_FREE (visited
);
1301 /* Go through loop and reject if-conversion or lowering of bitfields if we
1302 encounter statements we do not believe the vectorizer will be able to
1303 handle. If adding a new type of statement here, make sure
1304 'ifcvt_local_dce' is also able to handle it propertly. */
1305 for (index
= 0; index
< loop
->num_nodes
; index
++)
1307 basic_block bb
= blocks
[index
];
1308 gimple_stmt_iterator gsi
;
1310 bool may_have_nonlocal_labels
1311 = bb_with_exit_edge_p (loop
, bb
) || bb
== loop
->latch
;
1312 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1313 switch (gimple_code (gsi_stmt (gsi
)))
1316 if (!may_have_nonlocal_labels
)
1319 = gimple_label_label (as_a
<glabel
*> (gsi_stmt (gsi
)));
1320 if (DECL_NONLOCAL (label
) || FORCED_LABEL (label
))
1331 gimple_set_uid (gsi_stmt (gsi
), 0);
1341 /* Returns true when the analysis of the predicates for all the basic
1342 blocks in LOOP succeeded.
1344 predicate_bbs first allocates the predicates of the basic blocks.
1345 These fields are then initialized with the tree expressions
1346 representing the predicates under which a basic block is executed
1347 in the LOOP. As the loop->header is executed at each iteration, it
1348 has the "true" predicate. Other statements executed under a
1349 condition are predicated with that condition, for example
1356 S1 will be predicated with "x", and
1357 S2 will be predicated with "!x". */
1360 predicate_bbs (loop_p loop
)
1364 for (i
= 0; i
< loop
->num_nodes
; i
++)
1365 init_bb_predicate (ifc_bbs
[i
]);
1367 for (i
= 0; i
< loop
->num_nodes
; i
++)
1369 basic_block bb
= ifc_bbs
[i
];
1372 /* The loop latch and loop exit block are always executed and
1373 have no extra conditions to be processed: skip them. */
1374 if (bb
== loop
->latch
1375 || bb_with_exit_edge_p (loop
, bb
))
1377 reset_bb_predicate (bb
);
1381 cond
= bb_predicate (bb
);
1382 if (gcond
*stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
)))
1385 edge true_edge
, false_edge
;
1386 location_t loc
= gimple_location (stmt
);
1388 /* gcc.dg/fold-bopcond-1.c shows that despite all forwprop passes
1389 conditions can remain unfolded because of multiple uses so
1390 try to re-fold here, especially to get precision changing
1391 conversions sorted out. Do not simply fold the stmt since
1392 this is analysis only. When conditions were embedded in
1393 COND_EXPRs those were folded separately before folding the
1394 COND_EXPR but as they are now outside we have to make sure
1395 to fold them. Do it here - another opportunity would be to
1396 fold predicates as they are inserted. */
1397 gimple_match_op
cexpr (gimple_match_cond::UNCOND
,
1398 gimple_cond_code (stmt
),
1400 gimple_cond_lhs (stmt
),
1401 gimple_cond_rhs (stmt
));
1402 if (cexpr
.resimplify (NULL
, follow_all_ssa_edges
)
1403 && cexpr
.code
.is_tree_code ()
1404 && TREE_CODE_CLASS ((tree_code
)cexpr
.code
) == tcc_comparison
)
1405 c
= build2_loc (loc
, (tree_code
)cexpr
.code
, boolean_type_node
,
1406 cexpr
.ops
[0], cexpr
.ops
[1]);
1408 c
= build2_loc (loc
, gimple_cond_code (stmt
),
1410 gimple_cond_lhs (stmt
),
1411 gimple_cond_rhs (stmt
));
1413 /* Add new condition into destination's predicate list. */
1414 extract_true_false_edges_from_block (gimple_bb (stmt
),
1415 &true_edge
, &false_edge
);
1417 /* If C is true, then TRUE_EDGE is taken. */
1418 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1421 /* If C is false, then FALSE_EDGE is taken. */
1422 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1424 add_to_dst_predicate_list (loop
, false_edge
,
1425 unshare_expr (cond
), c2
);
1430 /* If current bb has only one successor, then consider it as an
1431 unconditional goto. */
1432 if (single_succ_p (bb
))
1434 basic_block bb_n
= single_succ (bb
);
1436 /* The successor bb inherits the predicate of its
1437 predecessor. If there is no predicate in the predecessor
1438 bb, then consider the successor bb as always executed. */
1439 if (cond
== NULL_TREE
)
1440 cond
= boolean_true_node
;
1442 add_to_predicate_list (loop
, bb_n
, cond
);
1446 /* The loop header is always executed. */
1447 reset_bb_predicate (loop
->header
);
1448 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1449 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1452 /* Build region by adding loop pre-header and post-header blocks. */
1454 static vec
<basic_block
>
1455 build_region (class loop
*loop
)
1457 vec
<basic_block
> region
= vNULL
;
1458 basic_block exit_bb
= NULL
;
1460 gcc_assert (ifc_bbs
);
1461 /* The first element is loop pre-header. */
1462 region
.safe_push (loop_preheader_edge (loop
)->src
);
1464 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
1466 basic_block bb
= ifc_bbs
[i
];
1467 region
.safe_push (bb
);
1468 /* Find loop postheader. */
1471 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1472 if (loop_exit_edge_p (loop
, e
))
1478 /* The last element is loop post-header. */
1479 gcc_assert (exit_bb
);
1480 region
.safe_push (exit_bb
);
1484 /* Return true when LOOP is if-convertible. This is a helper function
1485 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1486 in if_convertible_loop_p. */
1489 if_convertible_loop_p_1 (class loop
*loop
, vec
<data_reference_p
> *refs
)
1492 basic_block exit_bb
= NULL
;
1493 vec
<basic_block
> region
;
1495 calculate_dominance_info (CDI_DOMINATORS
);
1497 for (i
= 0; i
< loop
->num_nodes
; i
++)
1499 basic_block bb
= ifc_bbs
[i
];
1501 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1504 if (bb_with_exit_edge_p (loop
, bb
))
1508 data_reference_p dr
;
1511 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1512 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1514 /* Compute post-dominator tree locally. */
1515 region
= build_region (loop
);
1516 calculate_dominance_info_for_region (CDI_POST_DOMINATORS
, region
);
1518 predicate_bbs (loop
);
1520 /* Free post-dominator tree since it is not used after predication. */
1521 free_dominance_info_for_region (cfun
, CDI_POST_DOMINATORS
, region
);
1524 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1526 tree ref
= DR_REF (dr
);
1528 dr
->aux
= XNEW (struct ifc_dr
);
1529 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1530 DR_RW_UNCONDITIONALLY (dr
) = false;
1531 DR_W_UNCONDITIONALLY (dr
) = false;
1532 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1533 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1534 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1535 if (gimple_uid (DR_STMT (dr
)) == 0)
1536 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1538 /* If DR doesn't have innermost loop behavior or it's a compound
1539 memory reference, we synthesize its innermost loop behavior
1541 if (TREE_CODE (ref
) == COMPONENT_REF
1542 || TREE_CODE (ref
) == IMAGPART_EXPR
1543 || TREE_CODE (ref
) == REALPART_EXPR
1544 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1545 || DR_INIT (dr
) || DR_STEP (dr
)))
1547 while (TREE_CODE (ref
) == COMPONENT_REF
1548 || TREE_CODE (ref
) == IMAGPART_EXPR
1549 || TREE_CODE (ref
) == REALPART_EXPR
)
1550 ref
= TREE_OPERAND (ref
, 0);
1552 memset (&DR_INNERMOST (dr
), 0, sizeof (DR_INNERMOST (dr
)));
1553 DR_BASE_ADDRESS (dr
) = ref
;
1555 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1558 for (i
= 0; i
< loop
->num_nodes
; i
++)
1560 basic_block bb
= ifc_bbs
[i
];
1561 gimple_stmt_iterator itr
;
1563 /* Check the if-convertibility of statements in predicated BBs. */
1564 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1565 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1566 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1570 /* Checking PHIs needs to be done after stmts, as the fact whether there
1571 are any masked loads or stores affects the tests. */
1572 for (i
= 0; i
< loop
->num_nodes
; i
++)
1574 basic_block bb
= ifc_bbs
[i
];
1577 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1578 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1583 fprintf (dump_file
, "Applying if-conversion\n");
1588 /* Return true when LOOP is if-convertible.
1589 LOOP is if-convertible if:
1591 - it has two or more basic blocks,
1592 - it has only one exit,
1593 - loop header is not the exit edge,
1594 - if its basic blocks and phi nodes are if convertible. */
1597 if_convertible_loop_p (class loop
*loop
, vec
<data_reference_p
> *refs
)
1603 /* Handle only innermost loop. */
1604 if (!loop
|| loop
->inner
)
1606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1607 fprintf (dump_file
, "not innermost loop\n");
1611 /* If only one block, no need for if-conversion. */
1612 if (loop
->num_nodes
<= 2)
1614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1615 fprintf (dump_file
, "less than 2 basic blocks\n");
1619 /* If one of the loop header's edge is an exit edge then do not
1620 apply if-conversion. */
1621 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1622 if (loop_exit_edge_p (loop
, e
))
1625 res
= if_convertible_loop_p_1 (loop
, refs
);
1627 delete innermost_DR_map
;
1628 innermost_DR_map
= NULL
;
1630 delete baseref_DR_map
;
1631 baseref_DR_map
= NULL
;
1636 /* Return reduc_1 if has_nop.
1639 tmp1 = (unsigned type) reduc_1;
1641 reduc_3 = (signed type) tmp2. */
1643 strip_nop_cond_scalar_reduction (bool has_nop
, tree op
)
1648 if (TREE_CODE (op
) != SSA_NAME
)
1651 gassign
*stmt
= safe_dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (op
));
1653 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt
))
1654 || !tree_nop_conversion_p (TREE_TYPE (op
), TREE_TYPE
1655 (gimple_assign_rhs1 (stmt
))))
1658 return gimple_assign_rhs1 (stmt
);
1661 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1662 which is in predicated basic block.
1663 In fact, the following PHI pattern is searching:
1665 reduc_1 = PHI <..., reduc_2>
1669 reduc_2 = PHI <reduc_1, reduc_3>
1671 ARG_0 and ARG_1 are correspondent PHI arguments.
1672 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1673 EXTENDED is true if PHI has > 2 arguments. */
1676 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1677 tree
*op0
, tree
*op1
, bool extended
, bool* has_nop
,
1680 tree lhs
, r_op1
, r_op2
, r_nop1
, r_nop2
;
1682 gimple
*header_phi
= NULL
;
1683 enum tree_code reduction_op
;
1684 basic_block bb
= gimple_bb (phi
);
1685 class loop
*loop
= bb
->loop_father
;
1686 edge latch_e
= loop_latch_edge (loop
);
1687 imm_use_iterator imm_iter
;
1688 use_operand_p use_p
;
1691 bool result
= *has_nop
= false;
1692 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1695 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1698 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1699 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1701 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1704 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1705 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1709 if (gimple_bb (header_phi
) != loop
->header
)
1712 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1715 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1716 || gimple_has_volatile_ops (stmt
))
1719 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1722 if (!is_predicated (gimple_bb (stmt
)))
1725 /* Check that stmt-block is predecessor of phi-block. */
1726 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1735 if (!has_single_use (lhs
))
1738 reduction_op
= gimple_assign_rhs_code (stmt
);
1740 /* Catch something like below
1743 reduc_1 = PHI <..., reduc_2>
1746 tmp1 = (unsigned type) reduc_1;
1748 reduc_3 = (signed type) tmp2;
1750 reduc_2 = PHI <reduc_1, reduc_3>
1754 reduc_2 = PHI <0, reduc_1>
1755 tmp1 = (unsigned type)reduc_1;
1756 ifcvt = cond_expr ? rhs2 : 0
1757 tmp2 = tmp1 +/- ifcvt;
1758 reduc_1 = (signed type)tmp2; */
1760 if (CONVERT_EXPR_CODE_P (reduction_op
))
1762 lhs
= gimple_assign_rhs1 (stmt
);
1763 if (TREE_CODE (lhs
) != SSA_NAME
1764 || !has_single_use (lhs
))
1768 stmt
= SSA_NAME_DEF_STMT (lhs
);
1769 if (gimple_bb (stmt
) != gimple_bb (*nop_reduc
)
1770 || !is_gimple_assign (stmt
))
1774 reduction_op
= gimple_assign_rhs_code (stmt
);
1777 if (reduction_op
!= PLUS_EXPR
1778 && reduction_op
!= MINUS_EXPR
1779 && reduction_op
!= MULT_EXPR
1780 && reduction_op
!= BIT_IOR_EXPR
1781 && reduction_op
!= BIT_XOR_EXPR
1782 && reduction_op
!= BIT_AND_EXPR
)
1784 r_op1
= gimple_assign_rhs1 (stmt
);
1785 r_op2
= gimple_assign_rhs2 (stmt
);
1787 r_nop1
= strip_nop_cond_scalar_reduction (*has_nop
, r_op1
);
1788 r_nop2
= strip_nop_cond_scalar_reduction (*has_nop
, r_op2
);
1790 /* Make R_OP1 to hold reduction variable. */
1791 if (r_nop2
== PHI_RESULT (header_phi
)
1792 && commutative_tree_code (reduction_op
))
1794 std::swap (r_op1
, r_op2
);
1795 std::swap (r_nop1
, r_nop2
);
1797 else if (r_nop1
!= PHI_RESULT (header_phi
))
1802 /* Check that R_NOP1 is used in nop_stmt or in PHI only. */
1803 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_nop1
)
1805 gimple
*use_stmt
= USE_STMT (use_p
);
1806 if (is_gimple_debug (use_stmt
))
1808 if (use_stmt
== SSA_NAME_DEF_STMT (r_op1
))
1810 if (use_stmt
!= phi
)
1815 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1816 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1818 gimple
*use_stmt
= USE_STMT (use_p
);
1819 if (is_gimple_debug (use_stmt
))
1821 if (use_stmt
== stmt
)
1823 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1827 *op0
= r_op1
; *op1
= r_op2
;
1832 /* Converts conditional scalar reduction into unconditional form, e.g.
1834 if (_5 != 0) goto bb_5 else goto bb_6
1840 # res_2 = PHI <res_13(4), res_6(5)>
1843 will be converted into sequence
1844 _ifc__1 = _5 != 0 ? 1 : 0;
1845 res_2 = res_13 + _ifc__1;
1846 Argument SWAP tells that arguments of conditional expression should be
1848 If LOOP_VERSIONED is true if we assume that we versioned the loop for
1849 vectorization. In that case we can create a COND_OP.
1850 Returns rhs of resulting PHI assignment. */
1853 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1854 tree cond
, tree op0
, tree op1
, bool swap
,
1855 bool has_nop
, gimple
* nop_reduc
,
1856 bool loop_versioned
)
1858 gimple_stmt_iterator stmt_it
;
1861 tree rhs1
= gimple_assign_rhs1 (reduc
);
1862 tree lhs
= gimple_assign_lhs (reduc
);
1863 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1865 enum tree_code reduction_op
= gimple_assign_rhs_code (reduc
);
1866 tree op_nochange
= neutral_op_for_reduction (TREE_TYPE (rhs1
), reduction_op
,
1868 gimple_seq stmts
= NULL
;
1870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1872 fprintf (dump_file
, "Found cond scalar reduction.\n");
1873 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1876 /* If possible create a COND_OP instead of a COND_EXPR and an OP_EXPR.
1877 The COND_OP will have a neutral_op else value. */
1879 ifn
= get_conditional_internal_fn (reduction_op
);
1880 if (loop_versioned
&& ifn
!= IFN_LAST
1881 && vectorized_internal_fn_supported_p (ifn
, TREE_TYPE (lhs
))
1884 gcall
*cond_call
= gimple_build_call_internal (ifn
, 4,
1885 unshare_expr (cond
),
1887 gsi_insert_before (gsi
, cond_call
, GSI_SAME_STMT
);
1888 gimple_call_set_lhs (cond_call
, tmp
);
1893 /* Build cond expression using COND and constant operand
1894 of reduction rhs. */
1895 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1896 unshare_expr (cond
),
1897 swap
? op_nochange
: op1
,
1898 swap
? op1
: op_nochange
);
1899 /* Create assignment stmt and insert it at GSI. */
1900 new_assign
= gimple_build_assign (tmp
, c
);
1901 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1902 /* Build rhs for unconditional increment/decrement/logic_operation. */
1903 rhs
= gimple_build (&stmts
, reduction_op
,
1904 TREE_TYPE (rhs1
), op0
, tmp
);
1909 rhs
= gimple_convert (&stmts
,
1910 TREE_TYPE (gimple_assign_lhs (nop_reduc
)), rhs
);
1911 stmt_it
= gsi_for_stmt (nop_reduc
);
1912 gsi_remove (&stmt_it
, true);
1913 release_defs (nop_reduc
);
1915 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
1917 /* Delete original reduction stmt. */
1918 stmt_it
= gsi_for_stmt (reduc
);
1919 gsi_remove (&stmt_it
, true);
1920 release_defs (reduc
);
1924 /* Generate a simplified conditional. */
1927 gen_simplified_condition (tree cond
, scalar_cond_masked_set_type
&cond_set
)
1929 /* Check if the value is already live in a previous branch. This resolves
1930 nested conditionals from diamond PHI reductions. */
1931 if (TREE_CODE (cond
) == SSA_NAME
)
1933 gimple
*stmt
= SSA_NAME_DEF_STMT (cond
);
1934 gassign
*assign
= NULL
;
1935 if ((assign
= as_a
<gassign
*> (stmt
))
1936 && gimple_assign_rhs_code (assign
) == BIT_AND_EXPR
)
1938 tree arg1
= gimple_assign_rhs1 (assign
);
1939 tree arg2
= gimple_assign_rhs2 (assign
);
1940 if (cond_set
.contains ({ arg1
, 1 }))
1941 arg1
= boolean_true_node
;
1943 arg1
= gen_simplified_condition (arg1
, cond_set
);
1945 if (cond_set
.contains ({ arg2
, 1 }))
1946 arg2
= boolean_true_node
;
1948 arg2
= gen_simplified_condition (arg2
, cond_set
);
1950 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
, arg1
, arg2
);
1956 /* Structure used to track meta-data on PHI arguments used to generate
1957 most efficient comparison sequence to slatten a PHI node. */
1959 typedef struct ifcvt_arg_entry
1961 /* The PHI node argument value. */
1964 /* The number of compares required to reach this PHI node from start of the
1965 BB being if-converted. */
1966 unsigned num_compares
;
1968 /* The number of times this PHI node argument appears in the current PHI
1972 /* The indices at which this PHI arg occurs inside the PHI node. */
1974 } ifcvt_arg_entry_t
;
1976 /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT
1977 as to whether the condition is inverted. */
1980 gen_phi_arg_condition (gphi
*phi
, ifcvt_arg_entry_t
&arg
,
1981 gimple_stmt_iterator
*gsi
,
1982 scalar_cond_masked_set_type
&cond_set
, bool *invert
)
1986 tree cond
= NULL_TREE
;
1991 len
= arg
.indexes
->length ();
1992 gcc_assert (len
> 0);
1993 for (i
= 0; i
< len
; i
++)
1995 e
= gimple_phi_arg_edge (phi
, (*arg
.indexes
)[i
]);
1996 c
= bb_predicate (e
->src
);
1997 if (is_true_predicate (c
))
2002 /* If we have just a single inverted predicate, signal that and
2003 instead invert the COND_EXPR arms. */
2004 if (len
== 1 && TREE_CODE (c
) == TRUTH_NOT_EXPR
)
2006 c
= TREE_OPERAND (c
, 0);
2010 c
= gen_simplified_condition (c
, cond_set
);
2011 c
= force_gimple_operand_gsi (gsi
, unshare_expr (c
),
2012 true, NULL_TREE
, true, GSI_SAME_STMT
);
2013 if (cond
!= NULL_TREE
)
2015 /* Must build OR expression. */
2016 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
2017 cond
= force_gimple_operand_gsi (gsi
, unshare_expr (cond
), true,
2018 NULL_TREE
, true, GSI_SAME_STMT
);
2023 /* Register the new possibly simplified conditional. When more than 2
2024 entries in a phi node we chain entries in the false branch, so the
2025 inverted condition is active. */
2026 scalar_cond_masked_key
pred_cond ({ cond
, 1 });
2028 pred_cond
.inverted_p
= !pred_cond
.inverted_p
;
2029 cond_set
.add (pred_cond
);
2031 gcc_assert (cond
!= NULL_TREE
);
2035 /* Create the smallest nested conditional possible. On pre-order we record
2036 which conditionals are live, and on post-order rewrite the chain by removing
2037 already active conditions.
2039 As an example we simplify:
2043 _22 = a_10 < e_11(D);
2045 _ifc__42 = _23 ? t_13 : 0;
2046 t_6 = _7 ? 1 : _ifc__42
2051 _22 = a_10 < e_11(D);
2052 _ifc__42 = _22 ? t_13 : 0;
2053 t_6 = _7 ? 1 : _ifc__42;
2055 which produces better code. */
2058 gen_phi_nest_statement (gphi
*phi
, gimple_stmt_iterator
*gsi
,
2059 scalar_cond_masked_set_type
&cond_set
, tree type
,
2060 gimple
**res_stmt
, tree lhs0
,
2061 vec
<struct ifcvt_arg_entry
> &args
, unsigned idx
)
2063 if (idx
== args
.length ())
2064 return args
[idx
- 1].arg
;
2067 tree cond
= gen_phi_arg_condition (phi
, args
[idx
- 1], gsi
, cond_set
,
2069 tree arg1
= gen_phi_nest_statement (phi
, gsi
, cond_set
, type
, res_stmt
, lhs0
,
2072 unsigned prev
= idx
;
2073 unsigned curr
= prev
- 1;
2074 tree arg0
= args
[curr
].arg
;
2077 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
2082 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
2085 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
2087 gassign
*new_stmt
= gimple_build_assign (lhs
, rhs
);
2088 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
2089 update_stmt (new_stmt
);
2090 *res_stmt
= new_stmt
;
2094 /* When flattening a PHI node we have a choice of which conditions to test to
2095 for all the paths from the start of the dominator block of the BB with the
2096 PHI node. If the PHI node has X arguments we have to only test X - 1
2097 conditions as the last one is implicit. It does matter which conditions we
2098 test first. We should test the shortest condition first (distance here is
2099 measures in the number of logical operators in the condition) and the
2100 longest one last. This allows us to skip testing the most expensive
2101 condition. To accomplish this we need to sort the conditions. P1 and P2
2102 are sorted first based on the number of logical operations (num_compares)
2103 and then by how often they occur in the PHI node. */
2106 cmp_arg_entry (const void *p1
, const void *p2
, void * /* data. */)
2108 const ifcvt_arg_entry sval1
= *(const ifcvt_arg_entry
*)p1
;
2109 const ifcvt_arg_entry sval2
= *(const ifcvt_arg_entry
*)p2
;
2111 if (sval1
.num_compares
< sval2
.num_compares
)
2113 else if (sval1
.num_compares
> sval2
.num_compares
)
2116 if (sval1
.occurs
< sval2
.occurs
)
2118 else if (sval1
.occurs
> sval2
.occurs
)
2124 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
2125 This routine can handle PHI nodes with more than two arguments.
2128 S1: A = PHI <x1(1), x2(5)>
2130 S2: A = cond ? x1 : x2;
2132 The generated code is inserted at GSI that points to the top of
2133 basic block's statement list.
2134 If PHI node has more than two arguments a chain of conditional
2135 expression is produced.
2136 LOOP_VERSIONED should be true if we know that the loop was versioned for
2141 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
, bool loop_versioned
)
2143 gimple
*new_stmt
= NULL
, *reduc
, *nop_reduc
;
2144 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
2146 unsigned int index0
;
2152 res
= gimple_phi_result (phi
);
2153 if (virtual_operand_p (res
))
2156 if ((rhs
= degenerate_phi_result (phi
))
2157 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
2159 && !chrec_contains_undetermined (scev
)
2161 && (rhs
= gimple_phi_arg_def (phi
, 0))))
2163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2165 fprintf (dump_file
, "Degenerate phi!\n");
2166 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
2168 new_stmt
= gimple_build_assign (res
, rhs
);
2169 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
2170 update_stmt (new_stmt
);
2174 bb
= gimple_bb (phi
);
2175 /* Keep track of conditionals already seen. */
2176 scalar_cond_masked_set_type cond_set
;
2177 if (EDGE_COUNT (bb
->preds
) == 2)
2179 /* Predicate ordinary PHI node with 2 arguments. */
2180 edge first_edge
, second_edge
;
2181 basic_block true_bb
;
2182 first_edge
= EDGE_PRED (bb
, 0);
2183 second_edge
= EDGE_PRED (bb
, 1);
2184 cond
= bb_predicate (first_edge
->src
);
2185 cond_set
.add ({ cond
, 1 });
2186 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2187 std::swap (first_edge
, second_edge
);
2188 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
2190 cond
= bb_predicate (second_edge
->src
);
2191 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2192 cond
= TREE_OPERAND (cond
, 0);
2194 first_edge
= second_edge
;
2197 cond
= bb_predicate (first_edge
->src
);
2199 /* Gimplify the condition to a valid cond-expr conditonal operand. */
2200 cond
= gen_simplified_condition (cond
, cond_set
);
2201 cond
= force_gimple_operand_gsi (gsi
, unshare_expr (cond
), true,
2202 NULL_TREE
, true, GSI_SAME_STMT
);
2203 true_bb
= first_edge
->src
;
2204 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
2206 arg0
= gimple_phi_arg_def (phi
, 1);
2207 arg1
= gimple_phi_arg_def (phi
, 0);
2211 arg0
= gimple_phi_arg_def (phi
, 0);
2212 arg1
= gimple_phi_arg_def (phi
, 1);
2214 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
2215 &op0
, &op1
, false, &has_nop
,
2218 /* Convert reduction stmt into vectorizable form. */
2219 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
2220 true_bb
!= gimple_bb (reduc
),
2223 redundant_ssa_names
.safe_push (std::make_pair (res
, rhs
));
2226 /* Build new RHS using selected condition and arguments. */
2227 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
2229 new_stmt
= gimple_build_assign (res
, rhs
);
2230 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
2231 gimple_stmt_iterator new_gsi
= gsi_for_stmt (new_stmt
);
2232 if (fold_stmt (&new_gsi
, follow_all_ssa_edges
))
2234 new_stmt
= gsi_stmt (new_gsi
);
2235 update_stmt (new_stmt
);
2238 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2240 fprintf (dump_file
, "new phi replacement stmt\n");
2241 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
2246 /* Create hashmap for PHI node which contain vector of argument indexes
2247 having the same value. */
2249 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
2250 unsigned int num_args
= gimple_phi_num_args (phi
);
2251 /* Vector of different PHI argument values. */
2252 auto_vec
<ifcvt_arg_entry_t
> args
;
2254 /* Compute phi_arg_map, determine the list of unique PHI args and the indices
2255 where they are in the PHI node. The indices will be used to determine
2256 the conditions to apply and their complexity. */
2257 for (i
= 0; i
< num_args
; i
++)
2261 arg
= gimple_phi_arg_def (phi
, i
);
2262 if (!phi_arg_map
.get (arg
))
2263 args
.safe_push ({ arg
, 0, 0, NULL
});
2264 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
2267 /* Determine element with max number of occurrences and complexity. Looking
2268 at only number of occurrences as a measure for complexity isn't enough as
2269 all usages can be unique but the comparisons to reach the PHI node differ
2271 for (unsigned i
= 0; i
< args
.length (); i
++)
2273 unsigned int len
= 0;
2274 vec
<int> *indices
= phi_arg_map
.get (args
[i
].arg
);
2275 for (int index
: *indices
)
2277 edge e
= gimple_phi_arg_edge (phi
, index
);
2278 len
+= get_bb_num_predicate_stmts (e
->src
);
2281 unsigned occur
= indices
->length ();
2282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2283 fprintf (dump_file
, "Ranking %d as len=%d, idx=%d\n", i
, len
, occur
);
2284 args
[i
].num_compares
= len
;
2285 args
[i
].occurs
= occur
;
2286 args
[i
].indexes
= indices
;
2289 /* Sort elements based on rankings ARGS. */
2290 args
.stablesort (cmp_arg_entry
, NULL
);
2292 /* Handle one special case when number of arguments with different values
2293 is equal 2 and one argument has the only occurrence. Such PHI can be
2294 handled as if would have only 2 arguments. */
2295 if (args
.length () == 2
2296 && args
[0].indexes
->length () == 1)
2298 index0
= (*args
[0].indexes
)[0];
2301 e
= gimple_phi_arg_edge (phi
, index0
);
2302 cond
= bb_predicate (e
->src
);
2303 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2306 cond
= TREE_OPERAND (cond
, 0);
2308 /* Gimplify the condition to a valid cond-expr conditonal operand. */
2309 cond
= force_gimple_operand_gsi (gsi
, unshare_expr (cond
), true,
2310 NULL_TREE
, true, GSI_SAME_STMT
);
2311 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
2312 &op0
, &op1
, true, &has_nop
, &nop_reduc
)))
2313 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
2315 swap
? arg0
: arg1
);
2318 /* Convert reduction stmt into vectorizable form. */
2319 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
2320 swap
, has_nop
, nop_reduc
,
2322 redundant_ssa_names
.safe_push (std::make_pair (res
, rhs
));
2324 new_stmt
= gimple_build_assign (res
, rhs
);
2325 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
2326 update_stmt (new_stmt
);
2331 tree type
= TREE_TYPE (gimple_phi_result (phi
));
2332 gen_phi_nest_statement (phi
, gsi
, cond_set
, type
, &new_stmt
, res
,
2336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2338 fprintf (dump_file
, "new extended phi replacement stmt\n");
2339 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
2343 /* Replaces in LOOP all the scalar phi nodes other than those in the
2344 LOOP->header block with conditional modify expressions.
2345 LOOP_VERSIONED should be true if we know that the loop was versioned for
2349 predicate_all_scalar_phis (class loop
*loop
, bool loop_versioned
)
2352 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2355 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2358 gimple_stmt_iterator gsi
;
2359 gphi_iterator phi_gsi
;
2362 if (bb
== loop
->header
)
2365 phi_gsi
= gsi_start_phis (bb
);
2366 if (gsi_end_p (phi_gsi
))
2369 gsi
= gsi_after_labels (bb
);
2370 while (!gsi_end_p (phi_gsi
))
2372 phi
= phi_gsi
.phi ();
2373 if (virtual_operand_p (gimple_phi_result (phi
)))
2374 gsi_next (&phi_gsi
);
2377 predicate_scalar_phi (phi
, &gsi
, loop_versioned
);
2378 remove_phi_node (&phi_gsi
, false);
2384 /* Insert in each basic block of LOOP the statements produced by the
2385 gimplification of the predicates. */
2388 insert_gimplified_predicates (loop_p loop
)
2392 for (i
= 0; i
< loop
->num_nodes
; i
++)
2394 basic_block bb
= ifc_bbs
[i
];
2396 if (!is_predicated (bb
))
2397 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
2398 if (!is_predicated (bb
))
2400 /* Do not insert statements for a basic block that is not
2401 predicated. Also make sure that the predicate of the
2402 basic block is set to true. */
2403 reset_bb_predicate (bb
);
2407 stmts
= bb_predicate_gimplified_stmts (bb
);
2410 if (need_to_predicate
)
2412 /* Insert the predicate of the BB just after the label,
2413 as the if-conversion of memory writes will use this
2415 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
2416 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2420 /* Insert the predicate of the BB at the end of the BB
2421 as this would reduce the register pressure: the only
2422 use of this predicate will be in successor BBs. */
2423 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2426 || stmt_ends_bb_p (gsi_stmt (gsi
)))
2427 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2429 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
2432 /* Once the sequence is code generated, set it to NULL. */
2433 set_bb_predicate_gimplified_stmts (bb
, NULL
, true);
2438 /* Helper function for predicate_statements. Returns index of existent
2439 mask if it was created for given SIZE and -1 otherwise. */
2442 mask_exists (int size
, const vec
<int> &vec
)
2446 FOR_EACH_VEC_ELT (vec
, ix
, v
)
2452 /* Helper function for predicate_statements. STMT is a memory read or
2453 write and it needs to be predicated by MASK. Return a statement
2457 predicate_load_or_store (gimple_stmt_iterator
*gsi
, gassign
*stmt
, tree mask
)
2461 tree lhs
= gimple_assign_lhs (stmt
);
2462 tree rhs
= gimple_assign_rhs1 (stmt
);
2463 tree ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2464 mark_addressable (ref
);
2465 tree addr
= force_gimple_operand_gsi (gsi
, build_fold_addr_expr (ref
),
2466 true, NULL_TREE
, true, GSI_SAME_STMT
);
2467 tree ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2468 get_object_alignment (ref
));
2469 /* Copy points-to info if possible. */
2470 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2471 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2473 if (TREE_CODE (lhs
) == SSA_NAME
)
2476 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2478 gimple_call_set_lhs (new_stmt
, lhs
);
2479 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2484 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2486 gimple_move_vops (new_stmt
, stmt
);
2488 gimple_call_set_nothrow (new_stmt
, true);
2492 /* STMT uses OP_LHS. Check whether it is equivalent to:
2494 ... = OP_MASK ? OP_LHS : X;
2496 Return X if so, otherwise return null. OP_MASK is an SSA_NAME that is
2497 known to have value OP_COND. */
2500 check_redundant_cond_expr (gimple
*stmt
, tree op_mask
, tree op_cond
,
2503 gassign
*assign
= dyn_cast
<gassign
*> (stmt
);
2504 if (!assign
|| gimple_assign_rhs_code (assign
) != COND_EXPR
)
2507 tree use_cond
= gimple_assign_rhs1 (assign
);
2508 tree if_true
= gimple_assign_rhs2 (assign
);
2509 tree if_false
= gimple_assign_rhs3 (assign
);
2511 if ((use_cond
== op_mask
|| operand_equal_p (use_cond
, op_cond
, 0))
2512 && if_true
== op_lhs
)
2515 if (inverse_conditions_p (use_cond
, op_cond
) && if_false
== op_lhs
)
2521 /* Return true if VALUE is available for use at STMT. SSA_NAMES is
2522 the set of SSA names defined earlier in STMT's block. */
2525 value_available_p (gimple
*stmt
, hash_set
<tree_ssa_name_hash
> *ssa_names
,
2528 if (is_gimple_min_invariant (value
))
2531 if (TREE_CODE (value
) == SSA_NAME
)
2533 if (SSA_NAME_IS_DEFAULT_DEF (value
))
2536 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (value
));
2537 basic_block use_bb
= gimple_bb (stmt
);
2538 return (def_bb
== use_bb
2539 ? ssa_names
->contains (value
)
2540 : dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
));
2546 /* Helper function for predicate_statements. STMT is a potentially-trapping
2547 arithmetic operation that needs to be predicated by MASK, an SSA_NAME that
2548 has value COND. Return a statement that does so. SSA_NAMES is the set of
2549 SSA names defined earlier in STMT's block. */
2552 predicate_rhs_code (gassign
*stmt
, tree mask
, tree cond
,
2553 hash_set
<tree_ssa_name_hash
> *ssa_names
)
2555 tree lhs
= gimple_assign_lhs (stmt
);
2556 tree_code code
= gimple_assign_rhs_code (stmt
);
2557 unsigned int nops
= gimple_num_ops (stmt
);
2558 internal_fn cond_fn
= get_conditional_internal_fn (code
);
2560 /* Construct the arguments to the conditional internal function. */
2561 auto_vec
<tree
, 8> args
;
2562 args
.safe_grow (nops
+ 1, true);
2564 for (unsigned int i
= 1; i
< nops
; ++i
)
2565 args
[i
] = gimple_op (stmt
, i
);
2566 args
[nops
] = NULL_TREE
;
2568 /* Look for uses of the result to see whether they are COND_EXPRs that can
2569 be folded into the conditional call. */
2570 imm_use_iterator imm_iter
;
2572 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, lhs
)
2574 tree new_else
= check_redundant_cond_expr (use_stmt
, mask
, cond
, lhs
);
2575 if (new_else
&& value_available_p (stmt
, ssa_names
, new_else
))
2578 args
[nops
] = new_else
;
2579 if (operand_equal_p (new_else
, args
[nops
], 0))
2583 LHS = IFN_COND (MASK, ..., ELSE);
2584 X = MASK ? LHS : ELSE;
2586 which makes X equivalent to LHS. */
2587 tree use_lhs
= gimple_assign_lhs (use_stmt
);
2588 redundant_ssa_names
.safe_push (std::make_pair (use_lhs
, lhs
));
2593 args
[nops
] = targetm
.preferred_else_value (cond_fn
, TREE_TYPE (lhs
),
2594 nops
- 1, &args
[1]);
2596 /* Create and insert the call. */
2597 gcall
*new_stmt
= gimple_build_call_internal_vec (cond_fn
, args
);
2598 gimple_call_set_lhs (new_stmt
, lhs
);
2599 gimple_call_set_nothrow (new_stmt
, true);
2604 /* Predicate each write to memory in LOOP.
2606 This function transforms control flow constructs containing memory
2609 | for (i = 0; i < N; i++)
2613 into the following form that does not contain control flow:
2615 | for (i = 0; i < N; i++)
2616 | A[i] = cond ? expr : A[i];
2618 The original CFG looks like this:
2625 | if (i < N) goto bb_5 else goto bb_2
2629 | cond = some_computation;
2630 | if (cond) goto bb_3 else goto bb_4
2642 insert_gimplified_predicates inserts the computation of the COND
2643 expression at the beginning of the destination basic block:
2650 | if (i < N) goto bb_5 else goto bb_2
2654 | cond = some_computation;
2655 | if (cond) goto bb_3 else goto bb_4
2659 | cond = some_computation;
2668 predicate_statements is then predicating the memory write as follows:
2675 | if (i < N) goto bb_5 else goto bb_2
2679 | if (cond) goto bb_3 else goto bb_4
2683 | cond = some_computation;
2684 | A[i] = cond ? expr : A[i];
2692 and finally combine_blocks removes the basic block boundaries making
2693 the loop vectorizable:
2697 | if (i < N) goto bb_5 else goto bb_1
2701 | cond = some_computation;
2702 | A[i] = cond ? expr : A[i];
2703 | if (i < N) goto bb_5 else goto bb_4
2712 predicate_statements (loop_p loop
)
2714 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2715 auto_vec
<int, 1> vect_sizes
;
2716 auto_vec
<tree
, 1> vect_masks
;
2717 hash_set
<tree_ssa_name_hash
> ssa_names
;
2719 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2721 gimple_stmt_iterator gsi
;
2722 basic_block bb
= ifc_bbs
[i
];
2723 tree cond
= bb_predicate (bb
);
2727 if (is_true_predicate (cond
))
2731 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2734 cond
= TREE_OPERAND (cond
, 0);
2737 vect_sizes
.truncate (0);
2738 vect_masks
.truncate (0);
2740 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
2742 gassign
*stmt
= dyn_cast
<gassign
*> (gsi_stmt (gsi
));
2746 else if (is_false_predicate (cond
)
2747 && gimple_vdef (stmt
))
2749 unlink_stmt_vdef (stmt
);
2750 gsi_remove (&gsi
, true);
2751 release_defs (stmt
);
2754 else if (gimple_plf (stmt
, GF_PLF_2
)
2755 && is_gimple_assign (stmt
))
2757 tree lhs
= gimple_assign_lhs (stmt
);
2760 gimple_seq stmts
= NULL
;
2761 machine_mode mode
= TYPE_MODE (TREE_TYPE (lhs
));
2762 /* We checked before setting GF_PLF_2 that an equivalent
2763 integer mode exists. */
2764 int bitsize
= GET_MODE_BITSIZE (mode
).to_constant ();
2765 if (!vect_sizes
.is_empty ()
2766 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2767 /* Use created mask. */
2768 mask
= vect_masks
[index
];
2771 if (COMPARISON_CLASS_P (cond
))
2772 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2774 TREE_OPERAND (cond
, 0),
2775 TREE_OPERAND (cond
, 1));
2782 = constant_boolean_node (true, TREE_TYPE (mask
));
2783 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2784 TREE_TYPE (mask
), mask
, true_val
);
2786 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2788 /* Save mask and its size for further use. */
2789 vect_sizes
.safe_push (bitsize
);
2790 vect_masks
.safe_push (mask
);
2792 if (gimple_assign_single_p (stmt
))
2793 new_stmt
= predicate_load_or_store (&gsi
, stmt
, mask
);
2795 new_stmt
= predicate_rhs_code (stmt
, mask
, cond
, &ssa_names
);
2797 gsi_replace (&gsi
, new_stmt
, true);
2799 else if (((lhs
= gimple_assign_lhs (stmt
)), true)
2800 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
2801 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
2802 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs
))
2803 && arith_code_with_undefined_signed_overflow
2804 (gimple_assign_rhs_code (stmt
)))
2805 rewrite_to_defined_overflow (&gsi
);
2806 else if (gimple_vdef (stmt
))
2808 tree lhs
= gimple_assign_lhs (stmt
);
2809 tree rhs
= gimple_assign_rhs1 (stmt
);
2810 tree type
= TREE_TYPE (lhs
);
2812 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2813 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2815 std::swap (lhs
, rhs
);
2816 cond
= force_gimple_operand_gsi (&gsi
, unshare_expr (cond
), true,
2817 NULL_TREE
, true, GSI_SAME_STMT
);
2818 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2819 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2823 if (gimple_plf (gsi_stmt (gsi
), GF_PLF_2
)
2824 && is_gimple_call (gsi_stmt (gsi
)))
2826 /* Convert functions that have a SIMD clone to IFN_MASK_CALL.
2827 This will cause the vectorizer to match the "in branch"
2828 clone variants, and serves to build the mask vector
2829 in a natural way. */
2830 gcall
*call
= dyn_cast
<gcall
*> (gsi_stmt (gsi
));
2831 tree orig_fn
= gimple_call_fn (call
);
2832 int orig_nargs
= gimple_call_num_args (call
);
2833 auto_vec
<tree
> args
;
2834 args
.safe_push (orig_fn
);
2835 for (int i
= 0; i
< orig_nargs
; i
++)
2836 args
.safe_push (gimple_call_arg (call
, i
));
2837 args
.safe_push (cond
);
2839 /* Replace the call with a IFN_MASK_CALL that has the extra
2840 condition parameter. */
2841 gcall
*new_call
= gimple_build_call_internal_vec (IFN_MASK_CALL
,
2843 gimple_call_set_lhs (new_call
, gimple_call_lhs (call
));
2844 gsi_replace (&gsi
, new_call
, true);
2847 lhs
= gimple_get_lhs (gsi_stmt (gsi
));
2848 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
2849 ssa_names
.add (lhs
);
2856 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2857 other than the exit and latch of the LOOP. Also resets the
2858 GIMPLE_DEBUG information. */
2861 remove_conditions_and_labels (loop_p loop
)
2863 gimple_stmt_iterator gsi
;
2866 for (i
= 0; i
< loop
->num_nodes
; i
++)
2868 basic_block bb
= ifc_bbs
[i
];
2870 if (bb_with_exit_edge_p (loop
, bb
)
2871 || bb
== loop
->latch
)
2874 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2875 switch (gimple_code (gsi_stmt (gsi
)))
2879 gsi_remove (&gsi
, true);
2883 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2884 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2886 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2887 update_stmt (gsi_stmt (gsi
));
2898 /* Combine all the basic blocks from LOOP into one or two super basic
2899 blocks. Replace PHI nodes with conditional modify expressions.
2900 LOOP_VERSIONED should be true if we know that the loop was versioned for
2904 combine_blocks (class loop
*loop
, bool loop_versioned
)
2906 basic_block bb
, exit_bb
, merge_target_bb
;
2907 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2912 /* Reset flow-sensitive info before predicating stmts or PHIs we
2914 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2915 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2918 predicated
[i
] = is_predicated (bb
);
2921 for (auto gsi
= gsi_start_phis (bb
);
2922 !gsi_end_p (gsi
); gsi_next (&gsi
))
2923 reset_flow_sensitive_info (gimple_phi_result (*gsi
));
2924 for (auto gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2926 gimple
*stmt
= gsi_stmt (gsi
);
2929 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2930 reset_flow_sensitive_info (op
);
2935 remove_conditions_and_labels (loop
);
2936 insert_gimplified_predicates (loop
);
2937 predicate_all_scalar_phis (loop
, loop_versioned
);
2939 if (need_to_predicate
|| need_to_rewrite_undefined
)
2940 predicate_statements (loop
);
2942 /* Merge basic blocks. */
2943 exit_bb
= single_exit (loop
)->src
;
2944 gcc_assert (exit_bb
!= loop
->latch
);
2945 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2948 free_bb_predicate (bb
);
2951 merge_target_bb
= loop
->header
;
2953 /* Get at the virtual def valid for uses starting at the first block
2954 we merge into the header. Without a virtual PHI the loop has the
2955 same virtual use on all stmts. */
2956 gphi
*vphi
= get_virtual_phi (loop
->header
);
2957 tree last_vdef
= NULL_TREE
;
2960 last_vdef
= gimple_phi_result (vphi
);
2961 for (gimple_stmt_iterator gsi
= gsi_start_bb (loop
->header
);
2962 ! gsi_end_p (gsi
); gsi_next (&gsi
))
2963 if (gimple_vdef (gsi_stmt (gsi
)))
2964 last_vdef
= gimple_vdef (gsi_stmt (gsi
));
2966 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2968 gimple_stmt_iterator gsi
;
2969 gimple_stmt_iterator last
;
2973 if (bb
== exit_bb
|| bb
== loop
->latch
)
2976 /* We release virtual PHIs late because we have to propagate them
2977 out using the current VUSE. The def might be the one used
2979 vphi
= get_virtual_phi (bb
);
2982 /* When there's just loads inside the loop a stray virtual
2983 PHI merging the uses can appear, update last_vdef from
2986 last_vdef
= gimple_phi_arg_def (vphi
, 0);
2987 imm_use_iterator iter
;
2988 use_operand_p use_p
;
2990 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, gimple_phi_result (vphi
))
2992 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2993 SET_USE (use_p
, last_vdef
);
2995 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi
)))
2996 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef
) = 1;
2997 gsi
= gsi_for_stmt (vphi
);
2998 remove_phi_node (&gsi
, true);
3001 /* Make stmts member of loop->header and clear range info from all stmts
3002 in BB which is now no longer executed conditional on a predicate we
3003 could have derived it from. */
3004 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3006 gimple
*stmt
= gsi_stmt (gsi
);
3007 gimple_set_bb (stmt
, merge_target_bb
);
3008 /* Update virtual operands. */
3011 use_operand_p use_p
= ssa_vuse_operand (stmt
);
3013 && USE_FROM_PTR (use_p
) != last_vdef
)
3014 SET_USE (use_p
, last_vdef
);
3015 if (gimple_vdef (stmt
))
3016 last_vdef
= gimple_vdef (stmt
);
3019 /* If this is the first load we arrive at update last_vdef
3020 so we handle stray PHIs correctly. */
3021 last_vdef
= gimple_vuse (stmt
);
3024 /* Update stmt list. */
3025 last
= gsi_last_bb (merge_target_bb
);
3026 gsi_insert_seq_after_without_update (&last
, bb_seq (bb
), GSI_NEW_STMT
);
3027 set_bb_seq (bb
, NULL
);
3030 /* Fixup virtual operands in the exit block. */
3032 && exit_bb
!= loop
->header
)
3034 /* We release virtual PHIs late because we have to propagate them
3035 out using the current VUSE. The def might be the one used
3037 vphi
= get_virtual_phi (exit_bb
);
3040 /* When there's just loads inside the loop a stray virtual
3041 PHI merging the uses can appear, update last_vdef from
3044 last_vdef
= gimple_phi_arg_def (vphi
, 0);
3045 imm_use_iterator iter
;
3046 use_operand_p use_p
;
3048 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, gimple_phi_result (vphi
))
3050 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
3051 SET_USE (use_p
, last_vdef
);
3053 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (vphi
)))
3054 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (last_vdef
) = 1;
3055 gimple_stmt_iterator gsi
= gsi_for_stmt (vphi
);
3056 remove_phi_node (&gsi
, true);
3060 /* Now remove all the edges in the loop, except for those from the exit
3061 block and delete the blocks we elided. */
3062 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
3066 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
3068 if (e
->src
== exit_bb
)
3074 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
3078 if (bb
== exit_bb
|| bb
== loop
->latch
)
3081 delete_basic_block (bb
);
3084 /* Re-connect the exit block. */
3085 if (exit_bb
!= NULL
)
3087 if (exit_bb
!= loop
->header
)
3089 /* Connect this node to loop header. */
3090 make_single_succ_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
3091 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
3094 /* Redirect non-exit edges to loop->latch. */
3095 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
3097 if (!loop_exit_edge_p (loop
, e
))
3098 redirect_edge_and_branch (e
, loop
->latch
);
3100 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
3104 /* If the loop does not have an exit, reconnect header and latch. */
3105 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
3106 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
3109 /* If possible, merge loop header to the block with the exit edge.
3110 This reduces the number of basic blocks to two, to please the
3111 vectorizer that handles only loops with two nodes. */
3113 && exit_bb
!= loop
->header
)
3115 if (can_merge_blocks_p (loop
->header
, exit_bb
))
3116 merge_blocks (loop
->header
, exit_bb
);
3124 /* Version LOOP before if-converting it; the original loop
3125 will be if-converted, the new copy of the loop will not,
3126 and the LOOP_VECTORIZED internal call will be guarding which
3127 loop to execute. The vectorizer pass will fold this
3128 internal call into either true or false.
3130 Note that this function intentionally invalidates profile. Both edges
3131 out of LOOP_VECTORIZED must have 100% probability so the profile remains
3132 consistent after the condition is folded in the vectorizer. */
3135 version_loop_for_if_conversion (class loop
*loop
, vec
<gimple
*> *preds
)
3137 basic_block cond_bb
;
3138 tree cond
= make_ssa_name (boolean_type_node
);
3139 class loop
*new_loop
;
3141 gimple_stmt_iterator gsi
;
3142 unsigned int save_length
= 0;
3144 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
3145 build_int_cst (integer_type_node
, loop
->num
),
3147 gimple_call_set_lhs (g
, cond
);
3149 void **saved_preds
= NULL
;
3150 if (any_complicated_phi
|| need_to_predicate
)
3152 /* Save BB->aux around loop_version as that uses the same field. */
3153 save_length
= loop
->inner
? loop
->inner
->num_nodes
: loop
->num_nodes
;
3154 saved_preds
= XALLOCAVEC (void *, save_length
);
3155 for (unsigned i
= 0; i
< save_length
; i
++)
3156 saved_preds
[i
] = ifc_bbs
[i
]->aux
;
3159 initialize_original_copy_tables ();
3160 /* At this point we invalidate porfile confistency until IFN_LOOP_VECTORIZED
3161 is re-merged in the vectorizer. */
3162 new_loop
= loop_version (loop
, cond
, &cond_bb
,
3163 profile_probability::always (),
3164 profile_probability::always (),
3165 profile_probability::always (),
3166 profile_probability::always (), true);
3167 free_original_copy_tables ();
3169 if (any_complicated_phi
|| need_to_predicate
)
3170 for (unsigned i
= 0; i
< save_length
; i
++)
3171 ifc_bbs
[i
]->aux
= saved_preds
[i
];
3173 if (new_loop
== NULL
)
3176 new_loop
->dont_vectorize
= true;
3177 new_loop
->force_vectorize
= false;
3178 gsi
= gsi_last_bb (cond_bb
);
3179 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
3181 preds
->safe_push (g
);
3182 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
3183 update_ssa (TODO_update_ssa_no_phi
);
3187 /* Return true when LOOP satisfies the follow conditions that will
3188 allow it to be recognized by the vectorizer for outer-loop
3190 - The loop is not the root node of the loop tree.
3191 - The loop has exactly one inner loop.
3192 - The loop has a single exit.
3193 - The loop header has a single successor, which is the inner
3195 - Each of the inner and outer loop latches have a single
3197 - The loop exit block has a single predecessor, which is the
3198 inner loop's exit block. */
3201 versionable_outer_loop_p (class loop
*loop
)
3203 if (!loop_outer (loop
)
3204 || loop
->dont_vectorize
3206 || loop
->inner
->next
3207 || !single_exit (loop
)
3208 || !single_succ_p (loop
->header
)
3209 || single_succ (loop
->header
) != loop
->inner
->header
3210 || !single_pred_p (loop
->latch
)
3211 || !single_pred_p (loop
->inner
->latch
))
3214 basic_block outer_exit
= single_pred (loop
->latch
);
3215 basic_block inner_exit
= single_pred (loop
->inner
->latch
);
3217 if (!single_pred_p (outer_exit
) || single_pred (outer_exit
) != inner_exit
)
3221 fprintf (dump_file
, "Found vectorizable outer loop for versioning\n");
3226 /* Performs splitting of critical edges. Skip splitting and return false
3227 if LOOP will not be converted because:
3229 - LOOP is not well formed.
3230 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
3232 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
3235 ifcvt_split_critical_edges (class loop
*loop
, bool aggressive_if_conv
)
3239 unsigned int num
= loop
->num_nodes
;
3243 auto_vec
<edge
> critical_edges
;
3245 /* Loop is not well formed. */
3249 body
= get_loop_body (loop
);
3250 for (i
= 0; i
< num
; i
++)
3253 if (!aggressive_if_conv
3255 && EDGE_COUNT (bb
->preds
) > MAX_PHI_ARG_NUM
)
3257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3259 "BB %d has complicated PHI with more than %u args.\n",
3260 bb
->index
, MAX_PHI_ARG_NUM
);
3265 if (bb
== loop
->latch
|| bb_with_exit_edge_p (loop
, bb
))
3268 /* Skip basic blocks not ending with conditional branch. */
3269 if (!safe_is_a
<gcond
*> (*gsi_last_bb (bb
)))
3272 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3273 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
3274 critical_edges
.safe_push (e
);
3278 while (critical_edges
.length () > 0)
3280 e
= critical_edges
.pop ();
3281 /* Don't split if bb can be predicated along non-critical edge. */
3282 if (EDGE_COUNT (e
->dest
->preds
) > 2 || all_preds_critical_p (e
->dest
))
3289 /* Delete redundant statements produced by predication which prevents
3290 loop vectorization. */
3293 ifcvt_local_dce (class loop
*loop
)
3298 gimple_stmt_iterator gsi
;
3299 auto_vec
<gimple
*> worklist
;
3300 enum gimple_code code
;
3301 use_operand_p use_p
;
3302 imm_use_iterator imm_iter
;
3304 /* The loop has a single BB only. */
3305 basic_block bb
= loop
->header
;
3306 tree latch_vdef
= NULL_TREE
;
3308 worklist
.create (64);
3309 /* Consider all phi as live statements. */
3310 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3312 phi
= gsi_stmt (gsi
);
3313 gimple_set_plf (phi
, GF_PLF_2
, true);
3314 worklist
.safe_push (phi
);
3315 if (virtual_operand_p (gimple_phi_result (phi
)))
3316 latch_vdef
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3318 /* Consider load/store statements, CALL and COND as live. */
3319 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3321 stmt
= gsi_stmt (gsi
);
3322 if (is_gimple_debug (stmt
))
3324 gimple_set_plf (stmt
, GF_PLF_2
, true);
3327 if (gimple_store_p (stmt
) || gimple_assign_load_p (stmt
))
3329 gimple_set_plf (stmt
, GF_PLF_2
, true);
3330 worklist
.safe_push (stmt
);
3333 code
= gimple_code (stmt
);
3334 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
3336 gimple_set_plf (stmt
, GF_PLF_2
, true);
3337 worklist
.safe_push (stmt
);
3340 gimple_set_plf (stmt
, GF_PLF_2
, false);
3342 if (code
== GIMPLE_ASSIGN
)
3344 tree lhs
= gimple_assign_lhs (stmt
);
3345 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
3347 stmt1
= USE_STMT (use_p
);
3348 if (!is_gimple_debug (stmt1
) && gimple_bb (stmt1
) != bb
)
3350 gimple_set_plf (stmt
, GF_PLF_2
, true);
3351 worklist
.safe_push (stmt
);
3357 /* Propagate liveness through arguments of live stmt. */
3358 while (worklist
.length () > 0)
3361 use_operand_p use_p
;
3364 stmt
= worklist
.pop ();
3365 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
3367 use
= USE_FROM_PTR (use_p
);
3368 if (TREE_CODE (use
) != SSA_NAME
)
3370 stmt1
= SSA_NAME_DEF_STMT (use
);
3371 if (gimple_bb (stmt1
) != bb
|| gimple_plf (stmt1
, GF_PLF_2
))
3373 gimple_set_plf (stmt1
, GF_PLF_2
, true);
3374 worklist
.safe_push (stmt1
);
3377 /* Delete dead statements. */
3378 gsi
= gsi_last_bb (bb
);
3379 while (!gsi_end_p (gsi
))
3381 gimple_stmt_iterator gsiprev
= gsi
;
3382 gsi_prev (&gsiprev
);
3383 stmt
= gsi_stmt (gsi
);
3384 if (gimple_store_p (stmt
) && gimple_vdef (stmt
))
3386 tree lhs
= gimple_get_lhs (stmt
);
3388 ao_ref_init (&write
, lhs
);
3390 if (dse_classify_store (&write
, stmt
, false, NULL
, NULL
, latch_vdef
)
3392 delete_dead_or_redundant_assignment (&gsi
, "dead");
3397 if (gimple_plf (stmt
, GF_PLF_2
))
3402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3404 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
3405 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3407 gsi_remove (&gsi
, true);
3408 release_defs (stmt
);
3413 /* Return true if VALUE is already available on edge PE. */
3416 ifcvt_available_on_edge_p (edge pe
, tree value
)
3418 if (is_gimple_min_invariant (value
))
3421 if (TREE_CODE (value
) == SSA_NAME
)
3423 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (value
));
3424 if (!def_bb
|| dominated_by_p (CDI_DOMINATORS
, pe
->dest
, def_bb
))
3431 /* Return true if STMT can be hoisted from if-converted loop LOOP to
3435 ifcvt_can_hoist (class loop
*loop
, edge pe
, gimple
*stmt
)
3437 if (auto *call
= dyn_cast
<gcall
*> (stmt
))
3439 if (gimple_call_internal_p (call
)
3440 && internal_fn_mask_index (gimple_call_internal_fn (call
)) >= 0)
3443 else if (auto *assign
= dyn_cast
<gassign
*> (stmt
))
3445 if (gimple_assign_rhs_code (assign
) == COND_EXPR
)
3451 if (gimple_has_side_effects (stmt
)
3452 || gimple_could_trap_p (stmt
)
3453 || stmt_could_throw_p (cfun
, stmt
)
3454 || gimple_vdef (stmt
)
3455 || gimple_vuse (stmt
))
3458 int num_args
= gimple_num_args (stmt
);
3459 if (pe
!= loop_preheader_edge (loop
))
3461 for (int i
= 0; i
< num_args
; ++i
)
3462 if (!ifcvt_available_on_edge_p (pe
, gimple_arg (stmt
, i
)))
3467 for (int i
= 0; i
< num_args
; ++i
)
3468 if (!expr_invariant_in_loop_p (loop
, gimple_arg (stmt
, i
)))
3475 /* Hoist invariant statements from LOOP to edge PE. */
3478 ifcvt_hoist_invariants (class loop
*loop
, edge pe
)
3480 /* Only hoist from the now unconditionally executed part of the loop. */
3481 basic_block bb
= loop
->header
;
3482 gimple_stmt_iterator hoist_gsi
= {};
3483 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
3485 gimple
*stmt
= gsi_stmt (gsi
);
3486 if (ifcvt_can_hoist (loop
, pe
, stmt
))
3488 /* Once we've hoisted one statement, insert other statements
3490 gsi_remove (&gsi
, false);
3492 gsi_insert_after (&hoist_gsi
, stmt
, GSI_NEW_STMT
);
3495 gsi_insert_on_edge_immediate (pe
, stmt
);
3496 hoist_gsi
= gsi_for_stmt (stmt
);
3504 /* Returns the DECL_FIELD_BIT_OFFSET of the bitfield accesse in stmt iff its
3505 type mode is not BLKmode. If BITPOS is not NULL it will hold the poly_int64
3506 value of the DECL_FIELD_BIT_OFFSET of the bitfield access and STRUCT_EXPR,
3507 if not NULL, will hold the tree representing the base struct of this
3511 get_bitfield_rep (gassign
*stmt
, bool write
, tree
*bitpos
,
3514 tree comp_ref
= write
? gimple_assign_lhs (stmt
)
3515 : gimple_assign_rhs1 (stmt
);
3517 tree field_decl
= TREE_OPERAND (comp_ref
, 1);
3518 tree ref_offset
= component_ref_field_offset (comp_ref
);
3519 tree rep_decl
= DECL_BIT_FIELD_REPRESENTATIVE (field_decl
);
3521 /* Bail out if the representative is not a suitable type for a scalar
3522 register variable. */
3523 if (!is_gimple_reg_type (TREE_TYPE (rep_decl
)))
3526 /* Bail out if the DECL_SIZE of the field_decl isn't the same as the BF's
3528 unsigned HOST_WIDE_INT bf_prec
3529 = TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (stmt
)));
3530 if (compare_tree_int (DECL_SIZE (field_decl
), bf_prec
) != 0)
3533 if (TREE_CODE (DECL_FIELD_OFFSET (rep_decl
)) != INTEGER_CST
3534 || TREE_CODE (ref_offset
) != INTEGER_CST
)
3536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3537 fprintf (dump_file
, "\t Bitfield NOT OK to lower,"
3538 " offset is non-constant.\n");
3543 *struct_expr
= TREE_OPERAND (comp_ref
, 0);
3547 /* To calculate the bitposition of the BITFIELD_REF we have to determine
3548 where our bitfield starts in relation to the container REP_DECL. The
3549 DECL_FIELD_OFFSET of the original bitfield's member FIELD_DECL tells
3550 us how many bytes from the start of the structure there are until the
3551 start of the group of bitfield members the FIELD_DECL belongs to,
3552 whereas DECL_FIELD_BIT_OFFSET will tell us how many bits from that
3553 position our actual bitfield member starts. For the container
3554 REP_DECL adding DECL_FIELD_OFFSET and DECL_FIELD_BIT_OFFSET will tell
3555 us the distance between the start of the structure and the start of
3556 the container, though the first is in bytes and the later other in
3557 bits. With this in mind we calculate the bit position of our new
3558 BITFIELD_REF by subtracting the number of bits between the start of
3559 the structure and the container from the number of bits from the start
3560 of the structure and the actual bitfield member. */
3561 tree bf_pos
= fold_build2 (MULT_EXPR
, bitsizetype
,
3563 build_int_cst (bitsizetype
, BITS_PER_UNIT
));
3564 bf_pos
= fold_build2 (PLUS_EXPR
, bitsizetype
, bf_pos
,
3565 DECL_FIELD_BIT_OFFSET (field_decl
));
3566 tree rep_pos
= fold_build2 (MULT_EXPR
, bitsizetype
,
3567 DECL_FIELD_OFFSET (rep_decl
),
3568 build_int_cst (bitsizetype
, BITS_PER_UNIT
));
3569 rep_pos
= fold_build2 (PLUS_EXPR
, bitsizetype
, rep_pos
,
3570 DECL_FIELD_BIT_OFFSET (rep_decl
));
3572 *bitpos
= fold_build2 (MINUS_EXPR
, bitsizetype
, bf_pos
, rep_pos
);
3579 /* Lowers the bitfield described by DATA.
3586 __ifc_1 = struct.<representative>;
3587 __ifc_2 = BIT_INSERT_EXPR (__ifc_1, _1, bitpos);
3588 struct.<representative> = __ifc_2;
3596 __ifc_1 = struct.<representative>;
3597 _1 = BIT_FIELD_REF (__ifc_1, bitsize, bitpos);
3599 where representative is a legal load that contains the bitfield value,
3600 bitsize is the size of the bitfield and bitpos the offset to the start of
3601 the bitfield within the representative. */
3604 lower_bitfield (gassign
*stmt
, bool write
)
3608 tree rep_decl
= get_bitfield_rep (stmt
, write
, &bitpos
, &struct_expr
);
3609 tree rep_type
= TREE_TYPE (rep_decl
);
3610 tree bf_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
3612 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
3613 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3615 fprintf (dump_file
, "Lowering:\n");
3616 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3617 fprintf (dump_file
, "to:\n");
3620 /* REP_COMP_REF is a COMPONENT_REF for the representative. NEW_VAL is it's
3621 defining SSA_NAME. */
3622 tree rep_comp_ref
= build3 (COMPONENT_REF
, rep_type
, struct_expr
, rep_decl
,
3624 tree new_val
= ifc_temp_var (rep_type
, rep_comp_ref
, &gsi
);
3626 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3627 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (new_val
), 0, TDF_SLIM
);
3631 new_val
= ifc_temp_var (rep_type
,
3632 build3 (BIT_INSERT_EXPR
, rep_type
, new_val
,
3633 unshare_expr (gimple_assign_rhs1 (stmt
)),
3636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3637 print_gimple_stmt (dump_file
, SSA_NAME_DEF_STMT (new_val
), 0, TDF_SLIM
);
3639 gimple
*new_stmt
= gimple_build_assign (unshare_expr (rep_comp_ref
),
3641 gimple_move_vops (new_stmt
, stmt
);
3642 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
3644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3645 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
3649 tree bfr
= build3 (BIT_FIELD_REF
, bf_type
, new_val
,
3650 build_int_cst (bitsizetype
, TYPE_PRECISION (bf_type
)),
3652 new_val
= ifc_temp_var (bf_type
, bfr
, &gsi
);
3654 gimple
*new_stmt
= gimple_build_assign (gimple_assign_lhs (stmt
),
3656 gimple_move_vops (new_stmt
, stmt
);
3657 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
3659 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3660 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
3663 gsi_remove (&gsi
, true);
3666 /* Return TRUE if there are bitfields to lower in this LOOP. Fill TO_LOWER
3667 with data structures representing these bitfields. */
3670 bitfields_to_lower_p (class loop
*loop
,
3671 vec
<gassign
*> &reads_to_lower
,
3672 vec
<gassign
*> &writes_to_lower
)
3674 gimple_stmt_iterator gsi
;
3676 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3678 fprintf (dump_file
, "Analyzing loop %d for bitfields:\n", loop
->num
);
3681 for (unsigned i
= 0; i
< loop
->num_nodes
; ++i
)
3683 basic_block bb
= ifc_bbs
[i
];
3684 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3686 gassign
*stmt
= dyn_cast
<gassign
*> (gsi_stmt (gsi
));
3690 tree op
= gimple_assign_lhs (stmt
);
3691 bool write
= TREE_CODE (op
) == COMPONENT_REF
;
3694 op
= gimple_assign_rhs1 (stmt
);
3696 if (TREE_CODE (op
) != COMPONENT_REF
)
3699 if (DECL_BIT_FIELD_TYPE (TREE_OPERAND (op
, 1)))
3701 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3702 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3704 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
3706 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3707 fprintf (dump_file
, "\t Bitfield NO OK to lower,"
3708 " field type is not Integral.\n");
3712 if (!get_bitfield_rep (stmt
, write
, NULL
, NULL
))
3714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3715 fprintf (dump_file
, "\t Bitfield NOT OK to lower,"
3716 " representative is BLKmode.\n");
3720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3721 fprintf (dump_file
, "\tBitfield OK to lower.\n");
3723 writes_to_lower
.safe_push (stmt
);
3725 reads_to_lower
.safe_push (stmt
);
3729 return !reads_to_lower
.is_empty () || !writes_to_lower
.is_empty ();
3733 /* If-convert LOOP when it is legal. For the moment this pass has no
3734 profitability analysis. Returns non-zero todo flags when something
3738 tree_if_conversion (class loop
*loop
, vec
<gimple
*> *preds
)
3740 unsigned int todo
= 0;
3741 bool aggressive_if_conv
;
3743 auto_vec
<gassign
*, 4> reads_to_lower
;
3744 auto_vec
<gassign
*, 4> writes_to_lower
;
3747 auto_vec
<data_reference_p
, 10> refs
;
3748 bool loop_versioned
;
3753 need_to_lower_bitfields
= false;
3754 need_to_ifcvt
= false;
3755 need_to_predicate
= false;
3756 need_to_rewrite_undefined
= false;
3757 any_complicated_phi
= false;
3758 loop_versioned
= false;
3760 /* Apply more aggressive if-conversion when loop or its outer loop were
3761 marked with simd pragma. When that's the case, we try to if-convert
3762 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
3763 aggressive_if_conv
= loop
->force_vectorize
;
3764 if (!aggressive_if_conv
)
3766 class loop
*outer_loop
= loop_outer (loop
);
3767 if (outer_loop
&& outer_loop
->force_vectorize
)
3768 aggressive_if_conv
= true;
3771 /* If there are more than two BBs in the loop then there is at least one if
3773 if (loop
->num_nodes
> 2
3774 && !ifcvt_split_critical_edges (loop
, aggressive_if_conv
))
3777 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
3780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3781 fprintf (dump_file
, "Irreducible loop\n");
3785 if (find_data_references_in_loop (loop
, &refs
) == chrec_dont_know
)
3788 if (loop
->num_nodes
> 2)
3790 /* More than one loop exit is too much to handle. */
3791 if (!single_exit (loop
))
3793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3794 fprintf (dump_file
, "Can not ifcvt due to multiple exits\n");
3798 need_to_ifcvt
= true;
3800 if (!if_convertible_loop_p (loop
, &refs
)
3801 || !dbg_cnt (if_conversion_tree
))
3804 if ((need_to_predicate
|| any_complicated_phi
)
3805 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
3806 || loop
->dont_vectorize
))
3811 if ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
3812 && !loop
->dont_vectorize
)
3813 need_to_lower_bitfields
= bitfields_to_lower_p (loop
, reads_to_lower
,
3816 if (!need_to_ifcvt
&& !need_to_lower_bitfields
)
3819 /* The edge to insert invariant stmts on. */
3820 pe
= loop_preheader_edge (loop
);
3822 /* Since we have no cost model, always version loops unless the user
3823 specified -ftree-loop-if-convert or unless versioning is required.
3824 Either version this loop, or if the pattern is right for outer-loop
3825 vectorization, version the outer loop. In the latter case we will
3826 still if-convert the original inner loop. */
3827 if (need_to_lower_bitfields
3828 || need_to_predicate
3829 || any_complicated_phi
3830 || flag_tree_loop_if_convert
!= 1)
3833 = (versionable_outer_loop_p (loop_outer (loop
))
3834 ? loop_outer (loop
) : loop
);
3835 class loop
*nloop
= version_loop_for_if_conversion (vloop
, preds
);
3840 /* If versionable_outer_loop_p decided to version the
3841 outer loop, version also the inner loop of the non-vectorized
3842 loop copy. So we transform:
3846 if (LOOP_VECTORIZED (1, 3))
3852 loop3 (copy of loop1)
3853 if (LOOP_VECTORIZED (4, 5))
3854 loop4 (copy of loop2)
3856 loop5 (copy of loop4) */
3857 gcc_assert (nloop
->inner
&& nloop
->inner
->next
== NULL
);
3858 rloop
= nloop
->inner
;
3861 /* If we versioned loop then make sure to insert invariant
3862 stmts before the .LOOP_VECTORIZED check since the vectorizer
3863 will re-use that for things like runtime alias versioning
3864 whose condition can end up using those invariants. */
3865 pe
= single_pred_edge (gimple_bb (preds
->last ()));
3867 loop_versioned
= true;
3870 if (need_to_lower_bitfields
)
3872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3874 fprintf (dump_file
, "-------------------------\n");
3875 fprintf (dump_file
, "Start lowering bitfields\n");
3877 while (!reads_to_lower
.is_empty ())
3878 lower_bitfield (reads_to_lower
.pop (), false);
3879 while (!writes_to_lower
.is_empty ())
3880 lower_bitfield (writes_to_lower
.pop (), true);
3882 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3884 fprintf (dump_file
, "Done lowering bitfields\n");
3885 fprintf (dump_file
, "-------------------------\n");
3890 /* Before we rewrite edges we'll record their original position in the
3891 edge map such that we can map the edges between the ifcvt and the
3892 non-ifcvt loop during peeling. */
3894 for (edge exit
: get_loop_exit_edges (loop
))
3895 exit
->aux
= (void*)idx
++;
3897 /* Now all statements are if-convertible. Combine all the basic
3898 blocks into one huge basic block doing the if-conversion
3900 combine_blocks (loop
, loop_versioned
);
3903 std::pair
<tree
, tree
> *name_pair
;
3904 unsigned ssa_names_idx
;
3905 FOR_EACH_VEC_ELT (redundant_ssa_names
, ssa_names_idx
, name_pair
)
3906 replace_uses_by (name_pair
->first
, name_pair
->second
);
3907 redundant_ssa_names
.release ();
3909 /* Perform local CSE, this esp. helps the vectorizer analysis if loads
3910 and stores are involved. CSE only the loop body, not the entry
3911 PHIs, those are to be kept in sync with the non-if-converted copy.
3912 ??? We'll still keep dead stores though. */
3913 exit_bbs
= BITMAP_ALLOC (NULL
);
3914 for (edge exit
: get_loop_exit_edges (loop
))
3915 bitmap_set_bit (exit_bbs
, exit
->dest
->index
);
3916 todo
|= do_rpo_vn (cfun
, loop_preheader_edge (loop
), exit_bbs
,
3919 /* Delete dead predicate computations. */
3920 ifcvt_local_dce (loop
);
3921 BITMAP_FREE (exit_bbs
);
3923 ifcvt_hoist_invariants (loop
, pe
);
3925 todo
|= TODO_cleanup_cfg
;
3928 data_reference_p dr
;
3930 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
3941 for (i
= 0; i
< loop
->num_nodes
; i
++)
3942 free_bb_predicate (ifc_bbs
[i
]);
3950 reads_to_lower
.truncate (0);
3951 writes_to_lower
.truncate (0);
3958 /* Tree if-conversion pass management. */
3962 const pass_data pass_data_if_conversion
=
3964 GIMPLE_PASS
, /* type */
3966 OPTGROUP_NONE
, /* optinfo_flags */
3967 TV_TREE_LOOP_IFCVT
, /* tv_id */
3968 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3969 0, /* properties_provided */
3970 0, /* properties_destroyed */
3971 0, /* todo_flags_start */
3972 0, /* todo_flags_finish */
3975 class pass_if_conversion
: public gimple_opt_pass
3978 pass_if_conversion (gcc::context
*ctxt
)
3979 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
3982 /* opt_pass methods: */
3983 bool gate (function
*) final override
;
3984 unsigned int execute (function
*) final override
;
3986 }; // class pass_if_conversion
3989 pass_if_conversion::gate (function
*fun
)
3991 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
3992 && flag_tree_loop_if_convert
!= 0)
3993 || flag_tree_loop_if_convert
== 1);
3997 pass_if_conversion::execute (function
*fun
)
4001 if (number_of_loops (fun
) <= 1)
4004 auto_vec
<gimple
*> preds
;
4005 for (auto loop
: loops_list (cfun
, 0))
4006 if (flag_tree_loop_if_convert
== 1
4007 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
4008 && !loop
->dont_vectorize
))
4009 todo
|= tree_if_conversion (loop
, &preds
);
4013 free_numbers_of_iterations_estimates (fun
);
4020 FOR_EACH_BB_FN (bb
, fun
)
4021 gcc_assert (!bb
->aux
);
4024 /* Perform IL update now, it might elide some loops. */
4025 if (todo
& TODO_cleanup_cfg
)
4027 cleanup_tree_cfg ();
4028 if (need_ssa_update_p (fun
))
4029 todo
|= TODO_update_ssa
;
4031 if (todo
& TODO_update_ssa_any
)
4032 update_ssa (todo
& TODO_update_ssa_any
);
4034 /* If if-conversion elided the loop fall back to the original one. */
4035 for (unsigned i
= 0; i
< preds
.length (); ++i
)
4037 gimple
*g
= preds
[i
];
4040 unsigned ifcvt_loop
= tree_to_uhwi (gimple_call_arg (g
, 0));
4041 unsigned orig_loop
= tree_to_uhwi (gimple_call_arg (g
, 1));
4042 if (!get_loop (fun
, ifcvt_loop
) || !get_loop (fun
, orig_loop
))
4045 fprintf (dump_file
, "If-converted loop vanished\n");
4046 fold_loop_internal_call (g
, boolean_false_node
);
4056 make_pass_if_conversion (gcc::context
*ctxt
)
4058 return new pass_if_conversion (ctxt
);